Модель ускорения при фиксированном размере памяти

В 1993 году Сан и Ни (Xian-He Sun, Lionel Ni) [SUNN93] представили модель ускорения при ограничениях на память вычислительной системы, которая распространяет законы Амдала и Густафсона на максимизацию использования возможностей как процессоров, так и памяти. Большие научные и инженерные вычисления требует наличия памяти значительной емкости. Когда для решения большой задачи совместно используется много узлов многопроцессорной вычислительной системы, емкость доступной памяти пропорционально возрастает. Модель ограниченной памяти была разработана исходя из этой философии. Идея состоит в решении максимально большой задачи, ограниченной только емкостью памяти, с достижением наибольшего ускорения, более высокой точности и лучшего использования ресурсов при условии масштабируемой рабочей нагрузки.

Пусть M — это требования к емкости памяти, необходимой для решения определенной проблемы, а W — вычислительная нагрузка. Эти два фактора влияют друг на друга по-разному, в зависимости от адресного пространства и архитектурных ограничений. Запишем это в виде W = g(M) или M = g-1(W). В многопроцессорной системе емкость памяти растет линейно с увеличением числа узлов. Запишем рабочую нагрузку последовательного выполнения вычислений на одном узле, как , а масштабированную рабочую нагрузку для выполнения на n узлах — , где m* — максимальная степень параллелизма в масштабированной (увеличенной) задаче. Тогда требования к емкости памяти для активного узла можно записать в виде .

Ускорение при фиксированной памяти определяется аналогично тому, как это рассматривалось раньше:

Ранее уже отмечалось, что с увеличением числа узлов системы пропорционально увеличивается и емкость памяти. Для гомогенной системы из n узлов полагаем, что g*(nM) = G(n)g(M) = G(n). Здесь коэффициент G(n) отражает рост рабочей нагрузки с увеличением памяти в n раз. В предположении о том, что W_i = 0, если i ¹ 1 или i ¹ n и Q(n) = 0, последнее выражение для ускорения можно записать в виде:

.

Модель фиксированной памяти также предполагает масштабируемую рабочую нагрузку и допускает небольшое увеличение времени вычислений. Увеличение рабочей нагрузки (размера задачи) ограничено размером памяти. Рост размера системы при большом числе процессоров ограничен увеличением времени на обмен информацией между процессорами.

Проиллюстрируем эту концепцию для алгоритма перемножения матриц. Полагаем, что алгоритм содержит фиксированную последовательную часть и полностью распараллеливаемую остальную часть. Положим также, что для одного процессора размерность матрицы равна m. Время последовательного исполнения равно

T(1) = W1 + Wn = W1 + m3
При n процессорах можно обработать матрицы размерности поэтому гипотетическое время последовательного исполнения будет

T*(1)=W1+n3/2m3

Но с n процессорами мы получаем

T*(1)=W1+n1/2m3

Таким образом, ускорение равно

Для матричного умножения время вычисления возрастает быстрее, чем требования к памяти. Следовательно, чем мощнее ВС, тем большая проблема может быть решена, но время выполнения растет, даже если система становится все быстрее и быстрее. В терминах ускорения это дает даже более оптимистичную картину по сравнению с ускорением при фиксированном времени.