stringtranslate.com

Детализация (параллельные вычисления)

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

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

Если T comp — это время вычислений, а T comm — время связи, то степень детализации 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 элементов, что увеличивает время вычислений, но накладные расходы на связь уменьшаются по мере уменьшения числа процессоров, которые совместно используют данные. Этот случай иллюстрирует крупнозернистый параллелизм.

Уровни параллелизма

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

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

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

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

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

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

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

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

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

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

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

Цитаты

  1. ^ abcdefghijk Хванг, Кай (1992). Advanced Computer Architecture: Parallelism, Scalability, Programmability (1-е изд.). McGraw-Hill Higher Education. ISBN 978-0070316225.
  2. ^ ab Kwiatkowski, Jan (9 сентября 2001 г.). "Оценка параллельных программ путем измерения их гранулярности". Параллельная обработка и прикладная математика . Конспект лекций по информатике. Том 2328. С. 145–153. doi :10.1007/3-540-48086-2_16. ISBN 9783540437925. ISBN  9783540480860 .
  3. ^ Барни, Блейз. Введение в параллельные вычисления.
  4. ^ ab Miller, Russ; Stout, Quentin F. (1996). Параллельные алгоритмы для регулярных архитектур: сетки и пирамиды. Кембридж, Массачусетс: MIT Press. стр. 5–6. ISBN 9780262132336.
  5. ^ ab Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1 января 1990 г.). "Влияние синхронизации и гранулярности на параллельные системы". Труды 17-го ежегодного международного симпозиума по компьютерной архитектуре - ISCA '90 . Том 18. стр. 239–248. CiteSeerX 10.1.1.51.3389 . doi :10.1145/325164.325150. ISBN  0-89791-366-3. S2CID  16193537.
  6. ^ Йенг, Дональд; Далли, Уильям Дж.; Агарвал, Анант. «Как выбрать размер зерна параллельного компьютера». CiteSeerX 10.1.1.66.3298 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  7. ^ МакКрири, Кэролин; Гилл, Хелен (1 сентября 1989 г.). «Автоматическое определение размера зерна для эффективной параллельной обработки». Commun. ACM . 32 (9): 1073–1078. doi : 10.1145/66451.66454 . ISSN  0001-0782. S2CID  14807217.
  8. ^ Круатрачу, Бунти; Льюис, Тед (1 января 1988 г.). «Определение размера зерна для параллельной обработки». Программное обеспечение IEEE . 5 (1): 23–32. дои : 10.1109/52.1991. ISSN  0740-7459. S2CID  2034255.