Говорят, что программное обеспечение демонстрирует масштабируемый параллелизм , если оно может использовать дополнительные процессоры для решения более крупных задач, т. е. этот термин относится к программному обеспечению, для которого выполняется закон Густафсона . Рассмотрим программу, время выполнения которой определяется одним или несколькими циклами, каждый из которых обновляет каждый элемент массива --- например, следующий расчет трафарета конечно-разностного уравнения теплопроводности :
для t := 0 до T сделать для i := 1 до N-1 сделать новый(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // явная прямая разность с R = 0,25 конец для i := 1 до N-1 сделать А(i) := новый(i) конец конец
В приведенном выше коде мы можем выполнить все итерации каждого цикла "i" одновременно, т. е. превратить каждый в параллельный цикл . В таких случаях часто можно эффективно использовать вдвое больше процессоров для задачи с размером массива 2N, чем для задачи с размером массива N. Как в этом примере, масштабируемый параллелизм обычно является формой параллелизма данных . Эта форма параллелизма часто является целью автоматического распараллеливания циклов .
Распределенные вычислительные системы и архитектуры с неравномерным доступом к памяти обычно наиболее легко масштабируются до большого количества процессоров и, таким образом, кажутся естественной целью для программного обеспечения, демонстрирующего масштабируемый параллелизм. Однако приложения с масштабируемым параллелизмом могут не иметь параллелизма достаточно грубой зернистости для эффективной работы на таких системах (если только программное обеспечение не является ошеломляюще параллельным ). В нашем примере выше второй цикл «i» ошеломляюще параллелен, но в первом цикле каждая итерация требует результатов, полученных в нескольких предыдущих итерациях. Таким образом, для первого цикла параллелизация может включать в себя обширную коммуникацию или синхронизацию между процессорами и, таким образом, приводить к чистому ускорению только в том случае, если такие взаимодействия имеют очень низкие накладные расходы или если код может быть преобразован для решения этой проблемы (т. е. путем комбинированной оптимизации масштабируемой локальности /масштабируемого параллелизма [1] ).