Детализация (параллельные вычисления)
В вычислениях параллельных степень детализации (или размер зерна ) задачи является мерой объема работы (или вычислений ), выполняемой этой задачей. [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 пикселей не зависит друг от друга.
Мелкозернистый параллелизм. Предположим, что за обработку изображения размером 10*10 отвечают 100 процессоров. Не обращая внимания на издержки связи, 100 процессоров могут обработать изображение размером 10*10 за 1 такт. Каждый процессор обрабатывает 1 пиксель изображения, а затем передает выходные данные другим процессорам. Это пример мелкозернистого параллелизма.
Среднезернистый параллелизм. Предположим, что изображение размером 10*10 обрабатывают 25 процессоров. Обработка изображения теперь будет занимать 4 такта. Это пример среднезернистого параллелизма.
Грубый параллелизм: Далее, если уменьшить количество процессоров до 2, то обработка займет 50 тактов. Каждому процессору необходимо обработать 50 элементов, что увеличивает время вычислений, но накладные расходы на связь уменьшаются по мере уменьшения количества процессоров, совместно использующих данные. Этот случай иллюстрирует крупнозернистый параллелизм.
| Мелкозернистый: псевдокод для 100 процессоров. | Среднезернистый: псевдокод для 25 процессоров. | Крупнозернистый: псевдокод для 2 процессоров. |
|---|---|---|
void main()
{
switch (Processor_ID)
{
case 1: Compute element 1; break;
case 2: Compute element 2; break;
case 3: Compute element 3; break;
.
.
.
.
case 100: Compute element 100;
break;
}
}
|
void main()
{
switch (Processor_ID)
{
case 1: Compute elements 1-4; break;
case 2: Compute elements 5-8; break;
case 3: Compute elements 9-12; break;
.
.
case 25: Compute elements 97-100;
break;
}
}
|
void main()
{
switch (Processor_ID)
{
case 1: Compute elements 1-50;
break;
case 2: Compute elements 51-100;
break;
}
}
|
| Время расчета - 1 такт | Время расчета - 4 такта | Время расчета - 50 тактов |
Уровни параллелизма
[ редактировать ]Детализация тесно связана с уровнем обработки. Программу можно разбить на 4 уровня параллелизма:
- Уровень инструкции.
- Уровень цикла
- Подпрограммный уровень и
- Программный уровень
Наибольший уровень параллелизма достигается на уровне инструкций , за ним следует параллелизм на уровне цикла . На уровне команд и циклов достигается детальный параллелизм. Типичный размер зерна на уровне инструкций составляет 20 инструкций, а размер зерна на уровне цикла — 500 инструкций. [1]
На уровне подпрограммы (или процедуры) размер зерна обычно составляет несколько тысяч инструкций. Среднезернистый параллелизм достигается на уровне подпрограмм. [1]
На программном уровне происходит параллельное выполнение программ. Детализация может достигать десятков тысяч инструкций. [1] На этом уровне используется грубый параллелизм.
В таблице ниже показана взаимосвязь между уровнями параллелизма, размером зерна и степенью параллелизма.
| Уровни | Размер зерна | Параллелизм |
|---|---|---|
| Уровень обучения | Отлично | Самый высокий |
| Уровень цикла | Отлично | Умеренный |
| Подпрограммный уровень | Середина | Умеренный |
| Уровень программы | Грубый | Наименее |
Влияние детализации на производительность
[ редактировать ]Детализация влияет на производительность параллельных компьютеров. Использование мелкой детализации или небольших задач приводит к большему параллелизму и, следовательно, к увеличению скорости . Однако накладные расходы на синхронизацию, стратегии планирования и т. д. могут отрицательно повлиять на производительность мелкозернистых задач. Одно только увеличение параллелизма не может обеспечить наилучшую производительность. [5]
Чтобы уменьшить накладные расходы на связь, можно увеличить степень детализации. Грубозернистые задачи требуют меньших затрат на связь, но часто вызывают дисбаланс нагрузки. Следовательно, оптимальная производительность достигается между двумя крайностями: мелкозернистым и крупнозернистым параллелизмом. [6]
Различные исследования [5] [7] [8] предложили свое решение, помогающее определить наилучшую степень детализации для параллельной обработки. Поиск наилучшего размера зерна зависит от ряда факторов и сильно варьируется от проблемы к проблеме.
См. также
[ редактировать ]Цитаты
[ редактировать ]- ^ Перейти обратно: а б с д и ж г час я дж к Хван, Кай (1992). Усовершенствованная компьютерная архитектура: параллелизм, масштабируемость, программируемость (1-е изд.). Высшее образование МакГроу-Хилл. ISBN 978-0070316225 .
- ^ Перейти обратно: а б Квятковский, Ян (9 сентября 2001 г.). «Оценка параллельных программ путем измерения их степени детализации». Параллельная обработка и прикладная математика . Конспекты лекций по информатике. Том. 2328. стр. 145–153. дои : 10.1007/3-540-48086-2_16 . ISBN 9783540437925 . ISBN 9783540480860 .
- ^ Барни, Блейз. Введение в параллельные вычисления .
- ^ Перейти обратно: а б Миллер, Расс; Стаут, Квентин Ф. (1996). Параллельные алгоритмы для регулярных архитектур: сетки и пирамиды . Кембридж, Массачусетс: MIT Press. стр. 5–6. ISBN 9780262132336 .
- ^ Перейти обратно: а б Чен, Дин-Кай; Су, Хун-Мэнь; Ю, Пен-Чунг (1 января 1990 г.). «Влияние синхронизации и детализации на параллельные системы». Материалы 17-го ежегодного международного симпозиума по компьютерной архитектуре . 18 (2СИ): 239–248. CiteSeerX 10.1.1.51.3389 . дои : 10.1145/325164.325150 . S2CID 16193537 .
- ^ Юнг, Дональд; Далли, Уильям Дж.; Агарвал, Анант. «Как выбрать размер зерна параллельного компьютера». CiteSeerX 10.1.1.66.3298 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ МакКрири, Кэролин; Гилл, Хелен (1 сентября 1989 г.). «Автоматическое определение размера зерна для эффективной параллельной обработки» . Коммун. АКМ . 32 (9): 1073–1078. дои : 10.1145/66451.66454 . ISSN 0001-0782 . S2CID 14807217 .
- ^ Круатрачу, Гордость; Льюис, Тед (1 января 1988 г.). «Определение размера зерна для параллельной обработки» . Программное обеспечение IEEE . 5 (1): 23–3 дои : 10.1109/52.1991 . ISSN 0740-7459 . S2CID 2034255 .
| Общий | |
|---|---|
| Уровни | |
| Многопоточность | |
| Теория | |
| Элементы | |
| Координация | |
| Программирование | |
| Аппаратное обеспечение | |
| API | |
| Проблемы | |
