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

В параллельных вычислениях , зернистость (или зерна размера) задача является мерой количества работы (или вычисления) , которая выполняется с помощью этой задачи. [1]

Другое определение гранулярности учитывает накладные расходы на обмен данными между несколькими процессорами или элементами обработки. Он определяет степень детализации как отношение времени вычислений к времени связи, при этом время вычислений - это время, необходимое для выполнения вычисления задачи, а время связи - это время, необходимое для обмена данными между процессорами. [2]

Если - время вычисления и обозначает время связи, то Гранулярность G задачи может быть рассчитана как: [2]

Гранулярность обычно измеряется количеством инструкций, выполненных в конкретной задаче. [1] В качестве альтернативы, степень детализации также может быть указана в терминах времени выполнения программы, объединяя время вычислений и время связи. [1]

Типы параллелизма [ править ]

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

Мелкозернистый параллелизм [ править ]

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

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

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

Программистам сложно обнаружить параллелизм в программе, поэтому обычно ответственность за обнаружение мелкозернистого параллелизма лежит на компиляторах . [1]

Примером мелкозернистой системы (извне области параллельных вычислений) является система нейронов в нашем мозгу . [4]

Connection Machine (CM-2) и J-Machine - примеры компьютеров с мелкозернистым параллелизмом, размер зерна которых находится в диапазоне 4-5 мкс. [1]

Крупнозернистый параллелизм [ править ]

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

Архитектура передачи сообщений требует много времени для передачи данных между процессами, что делает ее пригодной для крупномасштабного параллелизма. [1]

Cray Y-MP - это пример крупнозернистого параллельного компьютера с размером зерна около 20 с. [1]

Среднезернистый параллелизм [ править ]

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

Intel iPSC - это пример среднезернистого параллельного компьютера с размером зерна около 10 мс. [1]

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

Рассмотрим изображение размером 10 * 10, которое необходимо обработать, учитывая, что обработка 100 пикселей не зависит друг от друга.

Детальный параллелизм: предположим, что есть 100 процессоров, которые отвечают за обработку изображения 10 * 10. Игнорируя накладные расходы на связь, 100 процессоров могут обрабатывать изображение 10 * 10 за 1 такт. Каждый процессор обрабатывает 1 пиксель изображения, а затем передает выходные данные другим процессорам. Это пример мелкозернистого параллелизма.

Среднезернистый параллелизм: примите во внимание, что есть 25 процессоров, обрабатывающих изображение 10 * 10. Обработка изображения теперь займет 4 такта. Это пример среднезернистого параллелизма.

Крупнозернистый параллелизм: если мы уменьшим количество процессоров до 2, то обработка займет 50 тактов. Каждому процессору необходимо обработать 50 элементов, что увеличивает время вычислений, но накладные расходы связи уменьшаются по мере уменьшения количества процессоров, которые совместно используют данные. Этот случай иллюстрирует крупномасштабный параллелизм.

Мелкозернистый: Псевдокод для 100 процессоровСреднезернистый: Псевдокод для 25 процессоровКрупнозернистый: Псевдокод для 2-х процессоров
void  main () {  switch  ( Processor_ID )  {  case  1 :  вычислить  элемент  1 ;  перерыв ;  случай  2 :  вычислить  элемент  2 ;  перерыв ;  случай  3 :  вычислить  элемент  3 ;  перерыв ;  .  .  .  .  case  100 :  Вычислить  элемент  100 ;  перерыв ;  } }
void  main () {  switch  ( Processor_ID )  {  case  1 :  вычислить  элементы  1-4 ;  перерыв ;  случай  2 :  вычислить  элементы  5-8 ;  перерыв ;  случай  3 :  вычислить  элементы  9–12 ;  перерыв ;  .  .  случай  25 :  вычислить  элементы  97–100 ;  перерыв ;  } }
void  main () {  switch  ( Processor_ID )  {  case  1 :  вычислить  элементы  1-50 ;  перерыв ;  случай  2 :  вычислить  элементы  51–100 ;  перерыв ;  } }
Время расчета - 1 тактВремя расчета - 4 тактаВремя расчета - 50 тактов

Уровни параллелизма [ править ]

Гранулярность тесно связана с уровнем обработки. Программа может быть разбита на 4 уровня параллелизма:

  1. Уровень обучения.
  2. Уровень петли
  3. Уровень подпрограммы и
  4. Программный уровень

Наивысший уровень параллелизма достигается на уровне инструкций , за которым следует параллелизм на уровне цикла . На уровне инструкций и циклов достигается мелкозернистый параллелизм. Типичный размер зерна на уровне инструкций составляет 20 инструкций, в то время как размер зерна на уровне цикла составляет 500 инструкций. [1]

На уровне подпрограммы (или процедуры) размер зерна обычно составляет несколько тысяч инструкций. Среднезернистый параллелизм достигается на подпрограммном уровне. [1]

На программном уровне имеет место параллельное выполнение программ. Гранулярность может составлять десятки тысяч инструкций. [1] На этом уровне используется грубый параллелизм.

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

УровниРазмером с зернышкоПараллелизм
Уровень обученияОтличноНаибольший
Уровень петлиОтличноУмеренный
Уровень подпрограммыСерединаУмеренный
Уровень программыГрубыйНаименее

Влияние детализации на производительность [ править ]

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

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

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

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

  • Параллелизм на уровне инструкций
  • Параллелизм данных

Цитаты [ править ]

  1. ^ Б с д е е г ч я J K Hwang, Кай (1992). Расширенная компьютерная архитектура: параллелизм, масштабируемость, программируемость (1-е изд.). Макгроу-Хилл Высшее образование. ISBN 978-0070316225.
  2. ^ a b Квятковски, январь (9 сентября 2001 г.). Оценка параллельных программ путем измерения их детализации . Параллельная обработка и прикладная математика . Конспект лекций по информатике. 2328 . С. 145–153. DOI : 10.1007 / 3-540-48086-2_16 . ISBN 9783540437925. ISBN  9783540480860 .
  3. ^ Барни, Блейз. Введение в параллельные вычисления .
  4. ^ a b Миллер, Расс; Стаут, Квентин Ф. (1996). Параллельные алгоритмы для регулярных архитектур: сетки и пирамиды . Кембридж, Массачусетс: MIT Press. С. 5–6. ISBN 9780262132336.
  5. ^ а б Чен, Дин-Кай; Су, Хун-Мэн; Ю, Пен-Чунг (1 января 1990 г.). «Влияние синхронизации и детализации на параллельные системы». Материалы 17-го ежегодного международного симпозиума по компьютерной архитектуре . 18 (2SI): 239–248. CiteSeerX 10.1.1.51.3389 . DOI : 10.1145 / 325164.325150 . 
  6. ^ Юнг, Дональд; Далли, Уильям Дж .; Агарвал, Анант. «Как выбрать размер зерна параллельного компьютера». CiteSeerX 10.1.1.66.3298 .  Цитировать журнал требует |journal=( помощь )
  7. ^ МакКрири, Кэролайн; Гилл, Хелен (1 сентября 1989 г.). «Автоматическое определение размера зерна для эффективной параллельной обработки». Commun. ACM . 32 (9): 1073–1078. DOI : 10.1145 / 66451.66454 . ISSN 0001-0782 . 
  8. ^ Kruatrachue, Boontee; Льюис, Тед (1 января 1988 г.). «Определение размера зерна для параллельной обработки» . IEEE Softw . 5 (1): 23–32. DOI : 10.1109 / 52.1991 . ISSN 0740-7459 .