Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

n
, а при конвейерном —
min (n, k).
Максимально достижимое ускорение, при условии, что затраты на 
передачу данных –
нулевые, в случае геометрического параллелизма равно 
n
, 
а в случае конвейерного 
‒
 min(n, k). 
 
9.2. 
Диффузная балансировка загрузки
 
В отличие от предыдущих методов, использующих метод статической 
балансировки загрузки процессоров, метод диффузной балансировки 
загрузки является методом динамической балансировки загрузки 
процессоров. 
В данном случае перераспределение вычислительной нагрузки 
выполняется между логически соседними процессорами. Данный метод 
применяется при решении задач с квазистационарным (т. е. медленно 
меняющимся) распределением вычислительной нагрузки по узлам сетки и 
обеспечивает сохранение свойства «локальности» алгоритма,
не требуя 
непосредственного взаимодействия каждого из процессоров со всеми 
остальными.
(17)

---

92 
Пусть известно распределение узлов вычислительной сетки по 
процессорам и известно, что это распределение не является оптимальным. 
Это может быть обусловлено:
-
неудачным начальным распределением работ;
-
изменением эффективной производительности процессоров или 
изменением трудоемкости обработки узлов уже в ходе выполнения работы. 
Изменение трудоемкости может быть вызвано следующими 
причинами:
1.
Не всегда возможно указать трудоемкость обработки узлов сетки. 
Граничные и внутренние узлы сетки требуют разных времен обработки, 
точное соотношение которого неизвестно.
2.
Используемые процессоры могут обладать разной, неизвестной 
заранее, производительностью.
3.
Трудоемкость обработки каждого из узлов расчетной сетки может 
отличаться на разных моментах модельного времени.
4.
Эффективная производительность процессоров может меняться с 
течением времени.
Приведем пример вычисления нового распределения узлов сетки по 
процессорам при условии, что известно текущее распределение узлов и 
время, затраченное каждым из процессоров, на обработку этих узлов.
Пусть расчетная сетка содержит n узлов, и на шаге