В параллельных вычислениях степень детализации (или размер зерна ) задачи является мерой объема работы (или вычислений ), выполняемой этой задачей. [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 элементов, что увеличивает время вычислений, но накладные расходы на связь уменьшаются по мере уменьшения количества процессоров, совместно использующих данные. Этот случай иллюстрирует крупнозернистый параллелизм.
Детализация тесно связана с уровнем обработки. Программу можно разбить на 4 уровня параллелизма:
Наибольший уровень параллелизма достигается на уровне инструкций , за ним следует параллелизм на уровне цикла . На уровне команд и циклов достигается детальный параллелизм. Типичный размер зерна на уровне инструкций составляет 20 инструкций, а размер зерна на уровне цикла — 500 инструкций. [1]
На уровне подпрограммы (или процедуры) размер зерна обычно составляет несколько тысяч инструкций. Среднезернистый параллелизм достигается на уровне подпрограмм. [1]
На программном уровне происходит параллельное выполнение программ. Детализация может достигать десятков тысяч инструкций. [1] На этом уровне используется грубый параллелизм.
В таблице ниже показана взаимосвязь между уровнями параллелизма, размером зерна и степенью параллелизма.
Детализация влияет на производительность параллельных компьютеров. Использование мелкой детализации или небольших задач приводит к большему параллелизму и, следовательно, к увеличению скорости . Однако накладные расходы на синхронизацию, стратегии планирования и т. д. могут отрицательно повлиять на производительность мелкозернистых задач. Одно лишь увеличение параллелизма не может обеспечить наилучшую производительность. [5]
Чтобы уменьшить накладные расходы на связь, можно увеличить степень детализации. Грубо детализированные задачи требуют меньших затрат на коммуникацию, но часто вызывают дисбаланс нагрузки. Следовательно, оптимальная производительность достигается между двумя крайностями: мелкозернистым и крупнозернистым параллелизмом. [6]
Различные исследования [5] [7] [8] предложили свое решение, помогающее определить наилучшую степень детализации для параллельной обработки. Поиск наилучшего размера зерна зависит от ряда факторов и сильно варьируется от проблемы к проблеме.
{{cite journal}}: Требуется цитировать журнал |journal=( помощь )