Таинственная комбинация

Question

Я решил изучить параллелизм и хотел узнать, как много способов могут перекрывать инструкции из двух разных процессов. Код для обоих процессов представляет собой всего лишь 10 циклов итерации с тремя инструкциями, выполняемыми на каждой итерации. Я выяснил, что проблема заключалась в том, чтобы оставить X-инструкции фиксированными в точке, а затем поместить другие инструкции X из другого процесса между пространствами, принимая во внимание, что они должны быть заказаны (инструкция 4 процесса B должна всегда поступать перед инструкцией 20).

Я написал программу для подсчета этого числа, посмотрев на результаты, я выяснил, что решение n. Комбинация k, где k - количество команд, выполняемых по всему циклу одного процесса, поэтому для 10 итераций это будет 30, а n - k * 2 (2 процесса). Другими словами, n число объектов с n/2 фиксировано и должно соответствовать n/2 среди пространств без последнего n/2, теряющего свой порядок.

Ok проблема решена. Нет, не совсем. Я понятия не имею, почему это так, я понимаю, что определение комбинации состоит в том, сколько способов вы можете взять k элементов из группы из n, чтобы все группы были разными, но порядок, в котором вы принимаете элементы, . В этом случае у нас есть n элементов, и мы фактически берем их все, потому что выполняются все инструкции (n C n).

Если вы объясните это, указав, что в сумке есть 2k синих (A) и красных (B) предметов, и вы берете k предметов из сумки, вы все еще принимаете только k инструкций, когда фактически выполняются инструкции 2k. Не могли бы вы пролить свет на это?

Заранее спасибо.

Answer 1

Как правило, я согласен с ответом Петера, но поскольку он, похоже, не полностью нажал на OP, вот мой выстрел в него (чисто с математической/комбинаторной точки зрения).

У вас есть 2 набора из 30 (k) инструкций, которые вы собираете вместе, в общей сложности 60 (n) инструкций. Поскольку каждый набор из 30 должен поддерживаться в порядке, нам не нужно отслеживать, какая команда в каждом наборе, с которой установлена ​​инструкция. Итак, у нас есть 60 слотов, в которые можно разместить 30 команд из одного набора (скажем, красного) и 30 инструкций из другого набора (например, синий).

Начнем с размещения 30 красных инструкций в 60 слотах. Существуют способы (60 выбрать 30) = 60!/(30! 30!) (Мы выбираем, какие 30 слотов из 60 заполнены красными инструкциями). Теперь у нас все еще есть 30 синих инструкций, но у нас осталось только 30 открытых слотов. Существует (30 выбрать 30) = 30!/(30! 0!) = 1 способ разместить синие инструкции в остальных слотах. Итак, в общей сложности есть (60 выберите 30) * (30 выберите 30) = (60 выберите 30) * 1 = (60 выберите 30) способы сделать это.

Теперь предположим, что вместо 2 наборов из 30 вы имеете 3 набора (красный, зеленый, синий) из k инструкций. У вас есть всего 3k слота для заполнения. Сначала поместите красные: (3k выберите k) = (3k)!/(K! (3k-k)!) = (3k)!/(K! (2k)!). Теперь поместите зеленые в оставшиеся 2k слоты: (2k выберите k) = (2k)!/(K! K!). Наконец, поместите синие в последние k слотов: (k выберите k) = k!/(K! 0!) = 1. Всего: (3k выберите k) * (2k выберите k) * (k выберите k) = ((3k)! * (2k)! * K!)/(K! (2k)! * K! K! * K! 0!) = (3k)!/(K! K! K!).

В качестве дополнительных расширений (хотя я не собираюсь, чтобы обеспечить полное объяснение):

• если у вас есть 3 набора инструкций с длиной а, б, в, число возможностей есть (+ Ь + с)!/(а! б! с!).
• Если у вас есть n наборов инструкций, в которых i-й набор имеет инструкции ki, число возможностей (k1 + k2 + ... + kn)!/(K1! K2! ... kn!).

Answer 2

FWIW его можно рассматривать, как это: у вас есть мешок с к синих и к красных шарами. Шары одинакового цвета неразличимы (по аналогии с ограничением того, что порядок инструкций в одном процессе/потоке фиксирован - что не так в современных процессорах, но давайте просто будем это делать). Сколько разных способов вы можете вытащить все шары из сумки?

Мои комбинаторные навыки довольно ржавый, но мое первое предположение

(2k!) 
----- 
2*k! 

, который, по словам Wikipedia, на самом деле равна

(2k) 
(k) 

(извините, у меня нет лучше понять, как показать это).

Для п процессов, она может быть обобщена, имеющими шарами п разного цвета в сумке.

Обновление: Обратите внимание, что в строгом смысле это моделирует только ситуацию, когда разные процессы выполняются на одном процессоре, поэтому все инструкции всех процессов должны быть упорядочены линейно на уровне процессора. В многопроцессорной среде несколько команд могут выполняться буквально одновременно.

Answer 3

Ответ Петера достаточно хорош, но это не объясняет, почему параллелизм затруднен. Это потому, что все чаще и чаще в настоящее время у вас есть несколько доступных исполнительных блоков (будь то ядра, процессоры, узлы, компьютеры, что угодно). Это, в свою очередь, означает, что возможности перекрытия между инструкциями еще больше возрастают; нет никакой гарантии, что то, что происходит, может быть правильно смоделировано с любым обычным чередованием.

Вот почему важно думать с точки зрения использования семафоров/мьютексов правильно и почему существуют барьеры памяти. Это потому, что все эти вещи превращают истинную неприятную картину во что-то, что намного легче понять. Но поскольку мьютексы уменьшают количество возможных исполнений, они снижают общую производительность и потенциальную эффективность. Это определенно сложно, и это, в свою очередь, потому, что это намного лучше, если вы можете работать в терминах передачи сообщений между потоками активности, которые иначе не взаимодействуют; это проще понять и лучше иметь меньшую синхронизацию.