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

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

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

Параллельное задание по данным на массиве из 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) и для умножения и сложения соответственно. $O(n^{3})$ $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 процессоров. $O(n)$ $O(м*н*к)$

// Параллельное умножение матриц #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]

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

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

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

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

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

Приложения

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

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

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

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

Примечания

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

Ссылки

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

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

[5] Некоторые входные данные (например, когда 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 .

[Solihin-6] Солихин, Ян (2016). Основы параллельной архитектуры . Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4.

[7] «Как распараллелить глубокое обучение на графических процессорах. Часть 2/2: Параллелизм моделей». Тим Деттмерс . 2014-11-09 . Получено 2016-09-13 .

[8] «Netlib» (PDF) .

[9] "OpenMP.org". openmp.org . Архивировано из оригинала 2016-09-05 . Получено 2016-09-07 .

[10] 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.

[11] Яп, ТК; Фридер, О.; Мартино, Р.Л. (1998). «Параллельные вычисления в анализе биологических последовательностей». Труды IEEE по параллельным и распределенным системам . 9 (3): 283–294. CiteSeerX 10.1.1.30.2819 . doi :10.1109/71.674320.

[12] Сингх, Х.; Ли, Мин-Хау; Лу, Гуанмин; Курдахи, Ф.Дж.; Багерзаде, Н.; Филхо, Э.М. Чавес (2000-06-01). «MorphoSys: интегрированная реконфигурируемая система для параллельных по данным и ресурсоемких приложений». IEEE Transactions on Computers . 49 (5): 465–481. doi :10.1109/12.859540. ISSN 0018-9340.

[13] Справочник по облачным вычислениям, «Технологии обработки больших объемов данных для облачных вычислений», автор AM Middleton. Справочник по облачным вычислениям. Springer, 2010.