Параллелизм данных

Распараллеливание на нескольких процессорах в параллельных вычислительных средах

Последовательное и параллельное по данным выполнение заданий

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

Параллельное задание по данным на массиве из n элементов можно разделить поровну между всеми процессорами. Предположим, что мы хотим суммировать все элементы заданного массива, а время для одной операции сложения составляет Ta единиц времени. В случае последовательного выполнения время, затраченное процессом, составит n × Ta единиц времени, поскольку он суммирует все элементы массива. С другой стороны, если мы выполним это задание как параллельное задание по данным на 4 процессорах, затраченное время сократится до ( n /4) × Ta + единицы времени накладных расходов на слияние. Параллельное выполнение приводит к ускорению в 4 раза по сравнению с последовательным выполнением. Важно отметить, что локальность ссылок на данные играет важную роль в оценке производительности модели параллельного программирования данных. Локальность данных зависит от доступа к памяти, выполняемого программой, а также от размера кэша.

История

Эксплуатация концепции параллелизма данных началась в 1960-х годах с разработкой машины Соломона. ^[1] Машина Соломона, также называемая векторным процессором , была разработана для ускорения выполнения математических операций путем работы с большим массивом данных (работая с несколькими данными в последовательных временных шагах). Параллелизм операций с данными также использовался путем работы с несколькими данными одновременно с использованием одной инструкции. Эти процессоры назывались «процессорами массивов». ^[2] В 1980-х годах этот термин был введен ^[3] для описания этого стиля программирования, который широко использовался для программирования машин соединений на языках параллельной обработки данных, таких как C* . Сегодня параллелизм данных лучше всего иллюстрируется графическими процессорами (GPU), которые используют обе техники работы с несколькими данными в пространстве и времени с использованием одной инструкции.

Большинство аппаратных средств параллельной обработки данных поддерживают только фиксированное количество параллельных уровней, часто только один. Это означает, что в рамках параллельной операции невозможно запустить больше параллельных операций рекурсивно, и означает, что программисты не могут использовать вложенный аппаратный параллелизм. Язык программирования NESL был ранней попыткой реализовать модель вложенного программирования параллельных данных на машинах с плоскими параллельными вычислительными единицами и, в частности, ввел преобразование выравнивания , которое преобразует вложенный параллелизм данных в плоский параллелизм данных. Эта работа была продолжена другими языками, такими как Data Parallel Haskell и Futhark , хотя произвольный вложенный параллелизм данных не так широко доступен в современных языках программирования параллельных данных.

Описание

В многопроцессорной системе, выполняющей один набор инструкций ( SIMD ), параллелизм данных достигается, когда каждый процессор выполняет одну и ту же задачу на разных распределенных данных. В некоторых ситуациях один поток выполнения управляет операциями на всех данных. В других случаях разные потоки управляют операцией, но они выполняют один и тот же код.

Например, рассмотрим последовательное умножение и сложение матриц , как обсуждалось в примере.

Пример

Ниже представлен последовательный псевдокод для умножения и сложения двух матриц, где результат сохраняется в матрице C. Псевдокод для умножения вычисляет скалярное произведение двух матриц A , B и сохраняет результат в выходной матрице C.

Если бы следующие программы выполнялись последовательно, время, необходимое для вычисления результата, составило бы (предполагая, что длины строк и столбцов обеих матриц равны n) и для умножения и сложения соответственно. ${\displaystyle O(n^{3})}$ ${\displaystyle O(n)}$

// Умножение матриц для ( i = 0 ; i < row_length_A ; i ++ ) { для ( k = 0 ; k < column_length_B ; k ++ ) { sum = 0 ; для ( j = 0 ; j < column_length_A ; j ++ ) { sum += A [ i ][ j ] * B [ j ][ k ]; } C [ i ][ k ] = sum ; } }                                      

// Сложение массива для ( i = 0 ; i < n ; i ++ ) { c [ i ] = a [ i ] + b [ i ]; }             

Мы можем использовать параллелизм данных в предыдущем коде, чтобы выполнить его быстрее, поскольку арифметика независима от цикла. Распараллеливание кода умножения матриц достигается с помощью OpenMP . Директива OpenMP "omp parallel for" предписывает компилятору выполнять код в цикле for параллельно. Для умножения мы можем разделить матрицы A и B на блоки по строкам и столбцам соответственно. Это позволяет нам вычислять каждый элемент в матрице C по отдельности, тем самым делая задачу параллельной. Например: A[mxn] dot B [nxk] может быть завершено за вместо того, чтобы при параллельном выполнении с использованием m*k процессоров. ${\displaystyle O(n)}$ ${\displaystyle O(m*n*k)}$

Параллелизм данных при умножении матриц

// Параллельное умножение матриц #pragma omp parallel for schedule(dynamic,1) collapse(2) for ( i = 0 ; i < row_length_A ; i ++ ){ for ( k = 0 ; k < column_length_B ; k ++ ){ sum = 0 ; for ( j = 0 ; j < column_length_A ; j ++ ){ sum += A [ i ][ j ] * B [ j ][ k ]; } C [ i ][ k ] = sum ; } }                                    

Из примера можно увидеть, что потребуется много процессоров, поскольку размеры матриц продолжают увеличиваться. Сохранение низкого времени выполнения является приоритетом, но по мере увеличения размера матрицы мы сталкиваемся с другими ограничениями, такими как сложность такой системы и связанные с ней затраты. Поэтому, ограничивая количество процессоров в системе, мы все равно можем применить тот же принцип и разделить данные на более крупные фрагменты для вычисления произведения двух матриц. ^[4]

Для сложения массивов в реализации параллельной обработки данных предположим более скромную систему с двумя центральными процессорами (ЦП) A и B, ЦП A может складывать все элементы из верхней половины массивов, в то время как ЦП B может складывать все элементы из нижней половины массивов. Поскольку два процессора работают параллельно, работа по сложению массивов займет половину времени выполнения той же операции последовательно с использованием только одного ЦП.

Программа, представленная в псевдокоде ниже, которая применяет некоторую произвольную операцию fooк каждому элементу массива, dиллюстрирует параллелизм данных: ^{[примечание 1]}

если ЦП = "а" , то нижний_лимит := 1 верхний_предел := раунд(d.длина / 2)иначе если ЦП = "b" тогда нижний_предел := раунд(d.длина / 2) + 1 верхний_предел := d.длинадля i от нижнего_предела до верхнего_предела на 1 сделать фу(д[я])

В системе SPMD , работающей на двухпроцессорной системе, оба ЦП будут выполнять код.

Параллелизм данных подчеркивает распределенную (параллельную) природу данных, в отличие от обработки (параллелизм задач). Большинство реальных программ находятся где-то на континууме между параллелизмом задач и параллелизмом данных.

Шаги к распараллеливанию

Процесс распараллеливания последовательной программы можно разбить на четыре отдельных шага. ^[5]

Параллелизм данных против параллелизма задач

Параллелизм данных против параллелизма моделей

^[6]

Смешанный параллелизм данных и задач

Параллелизм данных и задач может быть реализован одновременно путем их объединения для одного приложения. Это называется смешанным параллелизмом данных и задач. Смешанный параллелизм требует сложных алгоритмов планирования и программной поддержки. Это лучший вид параллелизма, когда связь медленная, а количество процессоров велико. ^[7]

Смешанный параллелизм данных и задач имеет множество приложений. Он особенно используется в следующих приложениях:

1. Смешанный параллелизм данных и задач находит применение в моделировании глобального климата. Большие параллельные вычисления данных выполняются путем создания сеток данных, представляющих атмосферу и океаны Земли, а параллелизм задач используется для моделирования функции и модели физических процессов.
2. В моделировании схем на основе синхронизации данные распределяются между различными подсхемами, а параллелизм достигается за счет оркестровки задач.

Среды параллельного программирования данных

Сегодня доступны различные среды параллельного программирования данных, наиболее широко используемые из которых:

1. Интерфейс передачи сообщений : это кроссплатформенный интерфейс программирования передачи сообщений для параллельных компьютеров. Он определяет семантику библиотечных функций, чтобы пользователи могли писать переносимые программы передачи сообщений на C, C++ и Fortran.
2. Open Multi Processing ^[8] (Open MP): это интерфейс прикладного программирования (API), который поддерживает модели программирования общей памяти на нескольких платформах многопроцессорных систем. Начиная с версии 4.5, OpenMP также может работать с устройствами, отличными от типичных ЦП. Он может программировать ПЛИС, ЦСП, графические процессоры и многое другое. Он не ограничивается графическими процессорами, как OpenACC.
3. CUDA и OpenACC : CUDA и OpenACC (соответственно) — это API-платформы параллельных вычислений, позволяющие инженерам-программистам использовать вычислительные блоки графических процессоров для обработки данных общего назначения.
4. Threading Building Blocks и RaftLib : обе среды программирования с открытым исходным кодом, которые обеспечивают смешанный параллелизм данных/задач в средах C/C++ с использованием гетерогенных ресурсов.

Приложения

Параллелизм данных находит применение в различных областях, от физики, химии, биологии, материаловедения до обработки сигналов. Науки подразумевают параллелизм данных для моделирования таких моделей, как молекулярная динамика ^[9] , анализ последовательностей геномных данных ^[10] и других физических явлений. Движущими силами в обработке сигналов для параллелизма данных являются видеокодирование, обработка изображений и графики, беспроводная связь ^[11] и многие другие.

Вычисления с интенсивным использованием данных

Интенсивные вычисления — это класс параллельных вычислительных приложений, которые используют параллельный подход к обработке больших объемов данных, обычно терабайт или петабайт , и обычно называются большими данными . Вычислительные приложения, которые посвящают большую часть своего времени выполнения вычислительным требованиям, считаются ресурсоемкими, тогда как приложения, которые считаются ресурсоемкими, требуют больших объемов данных и посвящают большую часть своего времени обработки вводу-выводу и манипулированию данными. ^[12]

Смотрите также

• Активное сообщение
• Параллелизм на уровне инструкций
• Модель параллельного программирования
• Префиксная сумма
• Масштабируемый параллелизм
• Сегментированное сканирование
• Параллелизм на уровне потоков

Примечания

1. Некоторые входные данные (например, когда d.lengthоценивается как 1 и roundокругляется до нуля [это всего лишь пример, нет никаких требований к типу округления]) приведут к тому, lower_limitчто значение будет больше upper_limit, предполагается, что цикл немедленно завершится (т.е. произойдет ноль итераций), когда это произойдет.

Ссылки

1. «Компьютер Соломона».
2. "SIMD/Vector/GPU" (PDF) . Получено 2016-09-07 .
3. Хиллис, В. Дэниел и Стил, Гай Л. , Параллельные алгоритмы передачи данных, ACM, декабрь 1986 г.
4. Барни, Блейз. «Введение в параллельные вычисления». computing.llnl.gov . Архивировано из оригинала 2013-06-10 . Получено 2016-09-07 .
5. Солихин, Ян (2016). Основы параллельной архитектуры . Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4.
6. «Как распараллелить глубокое обучение на графических процессорах. Часть 2/2: Параллелизм моделей». Тим Деттмерс . 2014-11-09 . Получено 2016-09-13 .
7. «Netlib» (PDF) .
8. "OpenMP.org". openmp.org . Архивировано из оригинала 2016-09-05 . Получено 2016-09-07 .
9. Boyer, L. L; Pawley, G. S (1988-10-01). «Молекулярная динамика кластеров частиц, взаимодействующих с парными силами с использованием массивно-параллельного компьютера». Журнал вычислительной физики . 78 (2): 405–423. Bibcode : 1988JCoPh..78..405B. doi : 10.1016/0021-9991(88)90057-5.
10. Яп, ТК; Фридер, О.; Мартино, Р.Л. (1998). «Параллельные вычисления в анализе биологических последовательностей». Труды IEEE по параллельным и распределенным системам . 9 (3): 283–294. CiteSeerX 10.1.1.30.2819 . doi :10.1109/71.674320. 
11. Сингх, Х.; Ли, Мин-Хау; Лу, Гуанмин; Курдахи, Ф.Дж.; Багерзаде, Н.; Филхо, Э.М. Чавес (2000-06-01). «MorphoSys: интегрированная реконфигурируемая система для параллельных по данным и ресурсоемких приложений». IEEE Transactions on Computers . 49 (5): 465–481. doi :10.1109/12.859540. ISSN  0018-9340.
12. Справочник по облачным вычислениям, «Технологии обработки больших объемов данных для облачных вычислений», автор AM Middleton. Справочник по облачным вычислениям. Springer, 2010.

• Хиллис, В. Дэниел и Стил, Гай Л. , Параллельные алгоритмы передачи данных , сообщения ACM, декабрь 1986 г.
• Блеллок, Гай Э. Векторные модели для параллельных вычислений данных. MIT Press, 1990. ISBN 0-262-02313-X