Гранулярность (параллельные вычисления) - Granularity (parallel computing)

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

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

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

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

Типы параллелизма

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

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

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

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

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

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

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

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

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

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

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

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