Оптимальное количество процессорных элементов

Давно известно, что для некоторых параллельных масштабируемых программ увеличение количества используемых процессоров лишь до некоторого момента ведет к увеличению быстродействия, а затем быстродействие снижает [55]. Здесь будет теоретически обосновано данное явление и для некоторого класса программ для различных коммуникационных сетей будет вычислено оптимальное количество процессоров. Для получения формулы оптимального количества процессоров используется модель времени вычисления программ (рассматриваемого класса), учитывающая время пересылок данных. Без учета пересылок данных время выполнения программ рассматривалось, например, в [114].  

Принцип сдваивания

Пусть * – некоторая ассоциативная операция и рассматривается задача параллельного вычисления последовательности из n-1 таких операций a₁*a₂*...*a_n . Тогда это вычисление можно выполнить на n/2 ПЭ за ]log₂n[ шагов [25]. (Здесь ]x[ означает наименьшее целое число, которое не меньше x). Идея этого алгоритма – уменьшение на каждом шаге размерности задачи вдвое – называется принципом сдваивания. Поскольку операция * бинарная, очевидно, что меньшее количество шагов невозможно. Данный результат следующим очевидным образом обобщается на случай p (<n/2) ПЭ.

Теорема 16.  Пусть * – ассоциативная операция. Тогда параллельное вычисление последовательности из n-1 такой операции a₁*a₂*...*a_n на p (<n/2) ПЭ можно выполнить за ]n/p[+]log₂p[ шагов. Если p – степень двойки, то меньшее количество шагов невозможно. В общем случае наименьшее количество шагов может быть равно ]n/p[+]log₂p[-1.

Подсчитаем затраты времени на пересылки данных при использовании принципа сдваивания.

Для универсального коммутатора, очевидно, количество тактов с пересылками равно ]log₂p[.

Для гиперкуба тоже достаточно ]log₂p[ пересылок. Действительно, при первом такте пересылок, следует брать данные в ПЭ с номерами вида (1,x2,x3,...,xm) и пересылать в (0,x2,x3,...,xm) для всех xiÎ{0,1}, i=2,...,k. После этого задача вычисления a₁*a₂*...*a_n сводится к точно такой же, но для вдвое меньшего числа данных, которые следует обработать на гиперкубе размерности на 1 меньше.

На кольцевой сети тоже достаточно ]log₂p[ пересылок [81]. Но на первом шаге данные пересылаются в соседние ПЭ, на втором шаге – пересылаются через один ПЭ, ..., на k-ом шаге – через 2 **(k-1)-1 ПЭ. Всего потребуется времени T1* ]log₂p[ + T2*(p-1).

Рассмотрим m-мерную решетку, как декартово произведение m колец C1´C2´...´Cm. Тогда алгоритм сдваивания сначала следует выполнить на кольцах первой размерности за ]log₂ |C1|[ шагов (здесь |C1| – количество узлов в кольце C1), затем на кольцах второй размерности и т.д..

Теорема 17. Пусть дана функция f(x₁,...,x_n) от n переменных и данные x₁,...,x_n размещены в p (<n) ПЭ так, что ни одно данное не записано дважды и каждый ПЭ содержит хотя бы одно данное. Тогда для вычисления функции f кроме арифметических операций требуется не менее ]log₂p[ тактов межпроцессорных пересылок.

Доказательство. Не умаляя общности можно считать, что n=p , то есть в каждом ПЭ находится ровно одно данное. Воспользуемся методом математической индукции.

Используя лишь один такт межпроцессорных пересылок можно вычислить лишь функцию двух аргументов, лежащих в разных ПЭ. Три аргумента уже нельзя собрать в одном ПЭ за один такт, поскольку ПЭ может читать за один такт лишь одно данное. Предположим, что, используя k тактов межпроцессорных пересылок можно вычислить функцию 2^k аргументов. Докажем, что за k+1 шаг можно вычислить функцию не более чем 2^k+1 аргументов. Действительно, на последнем шаге можно будет вычислить функцию двух промежуточных аргументов. Каждый из этих промежуточных аргументов был вычислен за k шагов и, следовательно, не может быть функцией более чем 2^k+1 исходных данных. Итого, за k+1 шаг можно вычислить функцию 2^k+1 переменных.

       Конец доказательства.