Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Последовательное и параллельное выполнение заданий

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

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

История [ править ]

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

Описание [ править ]

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

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

Пример [ править ]

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

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

// Умножение матрицы для  ( i  =  0 ;  i  <  row_length_A ;  i ++ ) {  for  ( k  =  0 ;  k  <  column_length_B ;  k ++ )  {  sum  =  0 ;  для  ( j  =  0 ;  j  <  column_length_A ;  j ++ )  {  sum  + =  A [ i ] [ j ] *  B [ j ] [ k ];  }  C [ я ] [ k ]  =  сумма ;  } }
// Сложение массива для  ( i  =  0 ;  i  <  n ;  i ++ )  {  c [ i ]  =  a [ i ]  +  b [ i ]; }

Мы можем использовать параллелизм данных в предыдущем коде, чтобы выполнить его быстрее, поскольку арифметика не зависит от цикла. Распараллеливание кода умножения матриц достигается с помощью OpenMP . Директива OpenMP «omp parallel for» предписывает компилятору выполнять код цикла for параллельно. Для умножения мы можем разделить матрицу A и B на блоки по строкам и столбцам соответственно. Это позволяет нам вычислять каждый элемент в матрице C индивидуально, тем самым делая задачу параллельной. Например: A [mxn] точка B [nxk] может быть завершена вместо того, чтобы выполняться параллельно с использованием процессоров m * 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 ++ ) {  сумма  =  0 ;  for  ( j  =  0 ;  j  <  column_length_A ;  j ++ ) {  sum  + =  A [ i] [ j ]  *  B [ j ] [ k ];  }  C [ я ] [ k ]  =  сумма ;  } }

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

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

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

если CPU = "a", то lower_limit: = 1 upper_limit: = круглый (длина d / 2)иначе, если CPU = "b", то lower_limit: = раунд (длина d / 2) + 1 верхний_лимит: = d.lengthдля i от lower_limit до upper_limit на 1 делаю foo (d [i])

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

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

Шаги к распараллеливанию [ править ]

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

ТипОписание
РазложениеПрограмма разбита на задачи, наименьшую возможную единицу согласования.
НазначениеЗадачи назначаются процессам.
ОркестровкаДоступ к данным, связь и синхронизация процессов.
КартографияПроцессы привязаны к процессорам.

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

Параллелизм данныхПараллелизм задач
Одни и те же операции выполняются с разными подмножествами одних и тех же данных.Разные операции выполняются с одними и теми же или разными данными.
Синхронное вычислениеАсинхронное вычисление
Ускорение больше, поскольку есть только один поток выполнения, работающий со всеми наборами данных.Ускорение меньше, поскольку каждый процессор будет выполнять свой поток или процесс с одним и тем же или другим набором данных.
Объем распараллеливания пропорционален размеру входных данных.Объем распараллеливания пропорционален количеству независимых задач, которые необходимо выполнить.
Разработан для оптимального баланса нагрузки в многопроцессорной системе.Балансировка нагрузки зависит от доступности оборудования и алгоритмов планирования, таких как статическое и динамическое планирование.

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

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

Смешанный параллелизм данных и задач [7] [ править ]

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

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

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

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

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

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

Приложения [ править ]

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

См. Также [ править ]

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

Примечания [ править ]

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

Ссылки [ править ]

  1. ^ "Компьютер Соломона" .
  2. ^ "SIMD / Vector / GPU" (PDF) . Проверено 7 сентября 2016 .
  3. ^ Хиллис, У. Дэниел и Стил, Гай Л. , Передача данных параллельных алгоритмов ACM, декабрь 1986 г.
  4. ^ Барни, Блэз. «Введение в параллельные вычисления» . computing.llnl.gov . Проверено 7 сентября 2016 .
  5. ^ Солихин, Ян (2016). Основы параллельной архитектуры . Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4.
  6. ^ «Как распараллелить глубокое обучение на графических процессорах. Часть 2/2: Параллелизм моделей» . Тим Деттмерс . 2014-11-09 . Проверено 13 сентября 2016 .
  7. ^ "Netlib" (PDF) .
  8. ^ "OpenMP.org" . openmp.org . Архивировано из оригинала на 2016-09-05 . Проверено 7 сентября 2016 .
  9. ^ Boyer, L. L; Поули, Г.С. (1988-10-01). «Молекулярная динамика кластеров частиц, взаимодействующих с парными силами с использованием массивно-параллельного компьютера». Журнал вычислительной физики . 78 (2): 405–423. Bibcode : 1988JCoPh..78..405B . DOI : 10.1016 / 0021-9991 (88) 90057-5 .
  10. ^ Яп, ТЗ; Frieder, O .; Мартино, Р.Л. (1998). «Документ IEEE Xplore - Параллельные вычисления в анализе биологической последовательности». Транзакции IEEE в параллельных и распределенных системах . 9 (3): 283–294. CiteSeerX 10.1.1.30.2819 . DOI : 10.1109 / 71.674320 . 
  11. ^ Сингх, H .; Ли, Мин-Хау; Лу, Гуанмин; Курдахи, Ф.Дж.; Багерзаде, Н .; Филхо, Э.М. Чавес (2000-06-01). «MorphoSys: интегрированная реконфигурируемая система для параллельных данных и приложений с интенсивными вычислениями» . Транзакции IEEE на компьютерах . 49 (5): 465–481. DOI : 10.1109 / 12.859540 . ISSN 0018-9340 . 
  • Хиллис, У. Дэниел и Стил, Гай Л. , Передача данных параллельных алгоритмов ACM, декабрь 1986 г.
  • Blelloch, Guy E, Vector Models for Data-Parallel Computing MIT Press 1990. ISBN 0-262-02313-X