Какое выполнение объема кода я должен параллелизировать?
Если я хочу параллелизировать осуществление алгоритма, каковы блоки запахов кода, который я должен разделить?
Классическим примером является алгоритм сортировки. Поскольку, какой размер элемента или типичное время выполнения имеет смысл разделять сортировку между несколькими потоками? Или когда больше издержки для ожидания на другом потоке, чем время выполнения на единственном потоке?
Есть ли какие-либо простые правила? Это зависит от ОС?
4 ответа
Ключевое правило - "вилка только тогда, когда накладные расходы на разветвление намного меньше, чем объем работы, который будет выполнять вилка ". Поскольку накладные расходы на разветвление - это свойство конкретной технологии, которую вы используете, а также усилия по выполнению работы, вам в некотором смысле необходимо определить это эмпирически. Скорее всего, в вашем коде будет некоторая константа настройки порога, представляющая этот компромисс.
На практике вы обнаружите, что найти отдельные части работы на самом деле сложно. Если вы сделаете рабочий блок маленьким, у него не будет много зависимостей, и вы можете запланировать его, когда все его входные потоки данных будут готовы. Но небольшие фрагменты обычно означают небольшую работу, а накладные расходы на разветвление обычно сводят на нет выигрыш. Если вы попытаетесь сделать куски большими, у них будет столько зависимостей, что вы не сможете разбить их, чтобы составить график.
Некоторым везет, и они могут найти такие большие куски; мы называем большинство этих людей физиками и / или программистами на Фортране, и они пользуются преимуществом параллелизма данных, вызванного разделением мира на как можно больше крошечных частей.
Единственное достойное лекарство, которое я знаю, - это использовать невероятно быстрый механизм разветвления, чтобы вы могли найти самые маленькие практические куски. К сожалению, предлагаемые для этого библиотеки параллелизма - это ... библиотеки, вызываемые динамически, с соответствующими накладными расходами на динамический вызов. В типичных библиотеках, содержащих примитивы параллелизма, для реализации «вилки» требуется от 100 до тысяч циклов; это плохая новость, если ваша работа состоит из 100 машинных инструкций.
Я твердо уверен, что для получения таких быстрых механизмов разветвления компилятор языка должен знать, что вы выполняете вилку, например, «вилка» (как бы она ни писалась :-) было ключевым словом в языке. Затем компилятор может увидеть вилки и предварительно выделить все необходимое, чтобы минимизировать время на выполнение этого, и сгенерировать специальный код для управления этапами разветвления (и соединения).
Язык PARLANSE , который я разработал и который мы используем в Semantic Designs, является одним из таких языков. Он похож на Lisp по синтаксису (но не по семантике). Его оператор параллелизма записывается как «(|| ...)». Вы можете увидеть это ниже в модуле Quicksort, который мы используем ежедневно, ниже. Вы также можете увидеть явное значение QuickSortParallelThreshold, определенное эмпирически. Эта Quicksort линейно масштабируется до 8 ядер в системе Intel x86.
(define QuickSort
(module
(;; (define Value nu)
(compileifthen (~ (defined QuickSortWithParlanseBuiltInOrderingOfNu))
(define QuickSortWithParlanseBuiltInOrderingOfNu ~f) ; use PARLANSE comparison operators
)compileifthen
(compileifthen (~ (defined QuickSortParallelThreshold))
(define QuickSortParallelThreshold 100)
)compileifthen
(compileifthen (~ (defined QuickSortThreshold))
(compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(define QuickSortThreshold 16)
(define QuickSortThreshold 8)
)compileifthenelse
)compileifthen
(compileifthenelse (~ (defined QuickSortWithCompareByReference))
(define QuickSortWithCompareByReference ~f)
(compileifthen QuickSortWithParlanseBuiltInOrderingOfNu
(define QuickSortWithCompareByReference ~f)
)compileifthen
)compileifthenelse
(define SortRange
(action (procedure (structure (compileifthen (~ QuickSortWithParlanseBuiltInOrderingOfNu)
(compileifthenelse (~ QuickSortWithCompareByReference)
[compare (function (sort integer (range -1 +1)) (structure [value1 Value] [value2 Value]))]
[compare (function (sort integer (range -1 +1)) (structure [value1 (reference Value)] [value2 (reference Value)]))]
)compileifthenelse
)compileifthen
[a (reference (array Value 1 dynamic))]
[from natural]
[to natural]
)structure
)procedure
(local (;; (define quicksort
(action (procedure (structure [l integer] [r integer])))
)define
(define quicksort
(action (procedure (structure [l integer] [r integer]))
(ifthenelse (<= (- r l) (coerce integer QuickSortThreshold))
(do [i integer] (++ l) r +1
(local (= [exch Value] a:i)
(block exit_if_inserted
(;; (do [j integer] (-- i) l -1
(ifthenelse (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(> a:j exch)
(compileifthenelse (~ QuickSortWithCompareByReference)
(== (compare a:j exch) +1)
(== (compare (. a:j) (. exch)) +1)
)compileifthenelse
)compileifthenelse
(= a:(++ j) a:j)
(;; (= a:(++ j) exch)
(exitblock exit_if_inserted)
);;
)ifthenelse
)do
(= a:l exch)
);;
)block
)local
)do
(local (;; (= [i integer] l)
(= [j integer] r)
(= [p integer] l)
(= [q integer] r)
[exch Value]
);;
(;;
`use middle element as pivot':
(local (= [m integer] (// (+ l r) +2))
(;; (= exch a:m)
(= a:m a:r)
(= a:r exch)
);;
)local
`4-way partitioning = < > =':
(loop exit_if_partitioned
(;;
`find element greater than pivot':
(loop exit_if_greater_than_found
(;; (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(ifthenelse (< a:i a:r)
(consume ~t)
(ifthenelse (> a:i a:r)
(exitblock exit_if_greater_than_found)
(;; (ifthen (>= i j)
(exitblock exit_if_partitioned)
)ifthen
(= exch a:p)
(= a:p a:i)
(= a:i exch)
(+= p 1)
);;
)ifthenelse
)ifthenelse
(case (compileifthenelse (~ QuickSortWithCompareByReference)
(compare a:i a:r)
(compare (. a:i) (. a:r))
)compileifthenelse
-1
(consume ~t)
+1
(exitblock exit_if_greater_than_found)
else (;; (ifthen (>= i j)
(exitblock exit_if_partitioned)
)ifthen
(= exch a:p)
(= a:p a:i)
(= a:i exch)
(+= p 1)
);;
)case
)compileifthenelse
(+= i 1)
);;
)loop
`find element less than to pivot':
(loop exit_if_less_than_found
(;; (-= j 1)
(ifthen (>= i j)
(exitblock exit_if_partitioned)
)ifthen
(compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(ifthenelse (< a:j a:r)
(exitblock exit_if_less_than_found)
(ifthenelse (> a:j a:r)
(consume ~t)
(;; (-= q 1)
(= exch a:j)
(= a:j a:q)
(= a:q exch)
);;
)ifthenelse
)ifthenelse
(case (compileifthenelse (~ QuickSortWithCompareByReference)
(compare a:j a:r)
(compare (. a:j) (. a:r))
)compileifthenelse
-1
(exitblock exit_if_less_than_found)
+1
(consume ~t)
else (;; (-= q 1)
(= exch a:j)
(= a:j a:q)
(= a:q exch)
);;
)case
)compileifthenelse
);;
)loop
`move found elements to proper partitions':
(;; (= exch a:i)
(= a:i a:j)
(= a:j exch)
);;
`increment index':
(+= i 1)
);;
)loop
`3-way partitioning < = >':
(;;
`move pivot to final location':
(;; (= exch a:i)
(= a:i a:r)
(= a:r exch)
(= j (-- i))
(= i (++ i))
);;
`move elements equal to pivot to final locations':
(;; (do [k integer] l (-- p) +1
(;; (= exch a:k)
(= a:k a:j)
(= a:j exch)
(-= j 1)
);;
)do
(do [k integer] (-- r) q -1
(;; (= exch a:i)
(= a:i a:k)
(= a:k exch)
(+= i 1)
);;
)do
);;
);;
`sort partitions not equal to pivot':
(ifthenelse (<= (- r l) (coerce integer QuickSortParallelThreshold))
(;; (quicksort l j)
(quicksort i r)
);;
(|| (quicksort l j)
(quicksort i r)
)||
)ifthenelse
);;
)local
)ifthenelse
)action
)define
);;
(;; (quicksort (coerce integer from) (coerce integer to))
(ifdebug (do [i integer] (coerce integer from) (-- (coerce integer to)) +1
(trust (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(<= a:i a:(++ i))
(compileifthenelse (~ QuickSortWithCompareByReference)
(<= (compare a:i a:(++ i)) +0)
(<= (compare (. a:i) (. a:(++ i))) +0)
)compileifthenelse
)compileifthenelse
`QuickSort:Sort -> The array is not sorted.'
)trust
)do
)ifdebug
);;
)local
)action
)define
(define Sort
(action (procedure (structure (compileifthen (~ QuickSortWithParlanseBuiltInOrderingOfNu)
(compileifthenelse (~ QuickSortWithCompareByReference)
[compare (function (sort integer (range -1 +1)) (structure [value1 Value] [value2 Value]))]
[compare (function (sort integer (range -1 +1)) (structure [value1 (reference Value)] [value2 (reference Value)]))]
)compileifthenelse
)compileifthen
[a (reference (array Value 1 dynamic))]
)structure
)procedure
(compileifthenelse (~ QuickSortWithParlanseBuiltInOrderingOfNu)
(SortRange compare a (coerce natural (lowerbound (@ a) 1)) (coerce natural (upperbound (@ a) 1)))
(SortRange a (coerce natural (lowerbound (@ a) 1)) (coerce natural (upperbound (@ a) 1)))
)compileifthenelse
)action
)define
);;
)module
)define
Пройдите несколько курсов по параллельному и параллельному программированию. Изучите несколько технологий, таких как простая старая вилка и забыть или «ручная» многопоточность (потоки Java или pthreads), MPI, OpenMP, BSP, может быть, даже CUDA или OpenCL. Затем либо решите стать экспертом, либо позвольте экспертам разработать и реализовать эффективные и правильные параллельные алгоритмы. «Параллельная» часть проста, «эффективная» и «правильная» - нет, когда необходимы обе части. Даже коллекция параллельных векторов Java, разработанная и реализованная экспертами, не была свободна от ошибок в первых версиях. Простое определение модели памяти не было ясным в первых версиях стандарта Java!
Простейшее правило: используйте готовые к использованию компоненты , разработанные и реализованные экспертами , и не пытайтесь достичь правильности и эффективности, разрабатывая собственные параллельные алгоритмы, если вы не являетесь экспертом. .
Решение этой проблемы программным способом является одним из святых граалей параллельных вычислений, и существует множество библиотек, которые могут приблизиться к оптимальному параллелизму для конкретных задач (например, Data Параллельный Haskell).
В любом случае, чтобы сделать это вручную, вам необходимо понять:
- Алгоритм, который вы хотите распараллелить (можно ли распараллелить?)
- Характеристики данных, например, размеры, расположение (на диске, в памяти) и т. д.
- Аппаратное обеспечение, на котором вы работаете, например, количество ядер, задержка памяти, размеры / строки / ассоциативность кэша и т. д.
- Поточная модель обоих языков реализации (сопрограммы, зеленый потоки, потоки ОС) и ОС.
- Стоимость создания и переключения контекста между потоками.
Предполагая, что алгоритм является распараллеливаемым, ваша цель - найти количество потоков и относительный размер блока данных, чтобы вы могли оптимально использовать оборудование для генерации решения.
Это довольно сложно обойтись без множества экспериментов. Я предпочитаю выяснить это, выполнив большое количество тестов и получив данные о производительности в зависимости от одной или нескольких комбинаций следующих параметров:
- Количество потоков.
- Размеры буфера (если данные не находятся в ОЗУ), увеличивающиеся с некоторым разумным значением (например, размер блока, размер пакета, размер кеша и т. Д.)
- Различные размеры фрагментов (если вы можете обрабатывать данные постепенно).
- Различные ручки настройки для ОС или языковой среды выполнения.
- Прикрепление потоков к ЦП для улучшения локальности.
- И т. Д.
Как бы то ни было, это непростая задача, и существуют инструменты и библиотеки, которые помогут вам выжать из ваших распараллеливаемых задач как можно больше производительности. Единственный разумный способ сделать это правильно, если хорошо разбираться в своих данных, коде и среде выполнения.
Это зависит от накладных расходов на межпотоковое взаимодействие. Я протестировал openMP с обработкой изображения, и там была удобная линия пикселей, дающая хорошие ускорения. Мое изображение было мегапиксельным, поэтому было 1000 задач, чего, наверное, более чем достаточно, чтобы сегодняшние многоядерные машины были заняты. Вам также не нужно ограничивать себя работой, которая занимает больше секунды или около того. В этом примере ускорение заданий порядка 10 миллисекунд там, где это четко видно.
Теперь это был приятный алгоритм, потому что он не был рекурсивным, поэтому не было никаких зависимостей одной задачи от другой, и все задачи автоматически имели одинаковый размер.
Сортировать алгоритмы будет сложнее, так как задачи разного размера. Вам захочется поэкспериментировать с этим, и, возможно, выбрать сорт, который легче парализовать.