Масштабируемость параллельной программы

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

Основные способы получения динамических характеристик:

• профилирование – сбор статистической информации о времени выполнения различных частей программы и частоте их вызова;
• трассировка – сбор информации о порядке выполнения в исследуемой программе определённых заранее событий;
• моделирование работы – создание модели исследуемого приложения и вычисление на её основе характеристик работы программы;
• эмуляция вычислений – выполнение реальных вычислений меньшего масштаба, с экстраполяцией на интересующую конфигурацию системы.

Из динамических характеристик программ на практике чаще всего рассматривают максимальную реальную производительность ${\displaystyle R_{max}}$, а из параметров запуска – число параллельных процессов p и вычислительную сложность решаемой задачи ${\displaystyle W}$.

Совместное рассмотрение производительности ${\displaystyle R_{max}}$, числа параллельных процессов ${\displaystyle p}$ и вычислительной сложности решаемой задачи ${\displaystyle W}$ определяет наиболее используемые виды масштабируемости. Так, чаще всего на практике рассматривают зависимость производительности от числа процессов приложения, фиксируя размер задачи (вычислительную сложность). Эту зависимость принято называть сильной масштабируемостью. Во многих случаях, если не делается специальная оговорка, то имеется в виду именно сильная масштабируемость.

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

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

Для многих задач при увеличении вычислительной сложности задачи растёт эффективность распараллеливания ${\displaystyle E_{p}}$. Если при одновременном увеличении числа процессов и вычислительной сложности задачи эффективность распараллеливания остаётся прежней, то данную задачу на данном компьютере можно считать масштабируемой.

Одной из известных метрик масштабируемости является функция изоэффективности (англ. isoefficiency function), показывающая необходимый уровень роста вычислительной сложности задачи для поддержания заданного уровня эффективности распараллеливания (Grama. 1993).