Оценка коммуникационной трудоемкости параллельных алгоритмов

3.2.3. Передача данных от всех процессоров всем процессорам сети

Операция передачи данных от всех процессоров всем процессорам сети ( all-to-all broadcast или multinode broadcast ) является естественным обобщением одиночной операции рассылки, двойственная ей операция – прием сообщений на каждом процессоре от всех процессоров сети ( multinode accumulation ). Подобные операции широко используются, например, при реализации матричных вычислений.

Возможный способ реализации операции множественной рассылки состоит в выполнении соответствующего набора операций одиночной рассылки. Однако такой подход не является оптимальным для многих топологий сети, поскольку часть необходимых операций одиночной рассылки потенциально может быть выполнена параллельно. Как и ранее, материал будет рассматриваться раздельно для разных методов передачи данных (см. п. 3.1.2).

Передача сообщений. Для кольцевой топологии каждый процессор может инициировать рассылку своего сообщения одновременно (в каком-либо выбранном направлении по кольцу). В любой момент каждый процессор выполняет прием и передачу данных, завершение операции множественной рассылки произойдет через p-1 цикл передачи данных. Длительность выполнения операции рассылки оценивается соотношением:$$t_{\textit{пд}} = (t_{\textit{н}} + mt_{\textit{к}})(p-1).$$

Для топологии типа решетка-тор множественная рассылка сообщений может быть выполнена при помощи алгоритма, получаемого обобщением способа передачи данных для кольцевой структуры сети. Схема обобщения состоит в следующем. На первом этапе организуется передача сообщений раздельно по всем процессорам сети, располагающимся на одних и тех же горизонталях решетки (в результате на каждом процессоре одной и той же горизонтали формируются укрупненные сообщения размера $$m \sqrt{p}$$, объединяющие все сообщения горизонтали). Время выполнения этапа:$$t'_{\textit{пд}} = (t_{\textit{н}} + mt_{\textit{к}})(\sqrt{p}-1).$$

На втором этапе рассылка данных выполняется по процессорам сети, образующим вертикали решетки. Длительность этого этапа:$$t''_{\textit{пд}} = (t_{\textit{н}} + m\sqrt{p}t_{\textit{к}})(\sqrt{p}-1).$$

Общая длительность операции рассылки определяется соотношением:$$t_{\textit{пд}} = 2t_{\textit{н}}(\sqrt{p}-1) + mt_{\textit{к}}(p-1).$$

Для гиперкуба алгоритм множественной рассылки сообщений может быть получен путем обобщения ранее описанного способа передачи данных для топологии типа решетки на размерность гиперкуба N. В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1<=i<=N, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i -ой размерности и формируют объединенные сообщения. Время операции рассылки может быть получено при помощи выражения:$$t_{\textit{пд}} = \sum_{i=1}^{\log_2 p} (t_{\textit{н}} + 2^{i-1}mt_{\textit{к}}) = t_{\textit{н}} \log_2 p + mt_{\textit{к}} (p-1).$$

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

Широко распространенным примером операции множественной рассылки является задача редукции ( reduction ), которая определяется в общем виде как процедура выполнения той или иной обработки данных, получаемых на каждом процессоре в ходе множественной рассылки (в качестве примера такой задачи может быть рассмотрена проблема вычисления суммы значений, находящихся на разных процессорах, и рассылки полученной суммы по всем процессорам сети). Способы решения задачи редукции могут состоять в следующем:

Другим типовым примером использования операции множественной рассылки является задача нахождения частных сумм последовательности значений Si (в англоязычной литературе эта задача известна под названием prefix sum problem )$$S_k = \sum_{i=1}^k x_i, \quad 1 \leqslant k \leqslant p$$ (будем предполагать, что количество значений совпадает с количеством процессоров, значение xi располагается на i -м процессоре и результат Sk должен получаться на процессоре с номером k ).

Алгоритм решения данной задачи также может быть получен при помощи конкретизации общего способа выполнения множественной операции рассылки, когда процессор выполняет суммирование полученного значения (но только в том случае, если процессор – отправитель значения имеет меньший номер, чем процессор-получатель).

3.2.4. Обобщенная передача данных от одного процессора всем остальным процессорам сети

Общий случай передачи данных от одного процессора всем остальным процессорам сети состоит в том, что все рассылаемые сообщения являются различными ( one-to-all personalized communication или single-node scatter ). Двойственная операция передачи для данного типа взаимодействия процессоров – обобщенный прием сообщений ( single-node gather ) на одном процессоре от всех остальных процессоров сети (отличие данной операции от ранее рассмотренной процедуры сборки данных на одном процессоре состоит в том, что обобщенная операция сборки не предполагает какого-либо взаимодействия сообщений (например, редукции) в процессе передачи данных).

Трудоемкость операции обобщенной рассылки сопоставима со сложностью выполнения процедуры множественной передачи данных. Процессор – инициатор рассылки посылает каждому процессору сети сообщение размера m, и, тем самым, нижняя оценка длительности выполнения операции характеризуется величиной mtk(p–1).

Проведем более подробный анализ трудоемкости обобщенной рассылки для случая топологии типа гиперкуб. Возможный способ выполнения операции состоит в следующем. Процессор – инициатор рассылки передает половину своих сообщений одному из своих соседей (например, по первой размерности) – в результате исходный гиперкуб становится разделенным на два гиперкуба половинного размера, в каждом из которых содержится ровно половина исходных данных. Далее, действия по рассылке сообщений могут быть повторены, и общее количество повторений определяется исходной размерностью гиперкуба. Длительность операции обобщенной рассылки может быть охарактеризована соотношением:$$t_{\textit{пд}} = t_{\textit{н}} \log_2 p + mt_{\textit{к}}(p-1)$$ (как и отмечалась выше, трудоемкость операции совпадает с длительностью выполнения процедуры множественной рассылки).

3.2.5. Обобщенная передача данных от всех процессоров всем процессорам сети

Обобщенная передача данных от всех процессоров всем процессорам сети ( total exchange ) представляет собой наиболее общий случай коммуникационных действий. Необходимость выполнения подобных операций возникает в параллельных алгоритмах быстрого преобразования Фурье, транспонирования матриц и др.

Выполним краткую характеристику возможных способов выполнения обобщенной множественной рассылки для разных методов передачи данных (см. п. 3.1.2).

Передача сообщений. Общая схема алгоритма для кольцевой топологии состоит в следующем. Каждый процессор производит передачу всех своих исходных сообщений своему соседу (в каком-либо выбранном направлении по кольцу). Далее процессоры осуществляют прием направленных к ним данных, затем среди принятой информации выбирают свои сообщения, после чего выполняют дальнейшую рассылку оставшейся части данных. Длительность выполнения подобного набора передач данных оценивается при помощи выражения:$$t_{\textit{пд}} = (t_{\textit{н}} + \frac12 mpt_{\textit{к}})(p-1).$$

Способ получения алгоритма рассылки данных для топологии типа решетка-тор является тем же самым, что и в случае рассмотрения других коммуникационных операций. На первом этапе организуется передача сообщений раздельно по всем процессорам сети, располагающимся на одних и тех же горизонталях решетки (каждому процессору по горизонтали передаются только те исходные сообщения, что должны быть направлены процессорам соответствующей вертикали решетки). После завершения этапа на каждом процессоре собираются p сообщений, предназначенных для рассылки по одной из вертикалей решетки. На втором этапе рассылка данных выполняется по процессорам сети, образующим вертикали решетки. Общая длительность всех операций рассылок определяется соотношением:$$t_{\textit{пд}} = (2t_{\textit{н}} + mpt_{\textit{к}})(\sqrt{p}-1).$$

Для гиперкуба алгоритм обобщенной множественной рассылки сообщений может быть получен путем обобщения способа выполнения операции для топологии типа решетка на размерность гиперкуба N. В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1<=i<=N, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i -й размерности и формируют объединенные сообщения. При организации взаимодействия двух соседей канал связи между ними рассматривается как связующий элемент двух равных по размеру подгиперкубов исходного гиперкуба, и каждый процессор пары посылает другому процессору только те сообщения, что предназначены для процессоров соседнего подгиперкуба. Время операции рассылки может быть получено при помощи выражения:$$t_{\textit{пд}} = (t_{\textit{н}} + \frac12 mpt_{\textit{к}}) \log_2 p$$ (кроме затрат на пересылку, каждый процессор выполняет $$mp \log_2 p$$ операций по сортировке своих сообщений перед обменом информацией со своими соседями).

Передача пакетов. Как и в случае множественной рассылки, применение метода передачи пакетов не приводит к улучшению временных характеристик для операции обобщенной множественной рассылки. Рассмотрим как пример более подробно выполнение данной коммуникационной операции для сети с топологией типа гиперкуб. В этом случае рассылка может быть выполнена за p-1 итерацию. На каждой итерации все процессоры разбиваются на взаимодействующие пары процессоров, причем это разбиение на пары может быть выполнено таким образом, чтобы передаваемые между разными парами сообщения не использовали одни и те же пути передачи данных. Как результат, общая длительность операции обобщенной рассылки может быть определена в соответствии с выражением:$$t_{\textit{пд}} = (t_{\textit{н}} + mt_{\textit{к}})(p-1) + \frac12 t_{\textit{с}} p \log_2 p.$$

3.2.6. Циклический сдвиг

Частный случай обобщенной множественной рассылки есть процедура перестановки ( permutation ), представляющая собой операцию перераспределения информации между процессорами сети, в которой каждый процессор передает сообщение определенному неким способом другому процессору сети. Конкретный вариант перестановки – циклический q-сдвиг ( cirlular q-shift ), при котором каждый процессор i, 1<=i<=N, передает данные процессору с номером $$(i+q)\text{mod}p$$. Подобная операция сдвига используется, например, при организации матричных вычислений.

Поскольку выполнение циклического сдвига для кольцевой топологии может быть обеспечено при помощи простых алгоритмов передачи данных, рассмотрим возможные способы выполнения данной коммуникационной операции только для топологий решетка-тор и гиперкуб при разных методах передачи данных (см. п. 3.1.2).

Передача сообщений. Общая схема алгоритма циклического сдвига для топологии типа решетка-тор состоит в следующем. Пусть процессоры перенумерованы по строкам решетки от 0 до p-1. На первом этапе организуется циклический сдвиг с шагом $$q \text{mod} \sqrt{p}$$ по каждой строке в отдельности (если при реализации такого сдвига сообщения передаются через правые границы строк, то после выполнения каждой такой передачи необходимо осуществить компенсационный сдвиг вверх на 1 для процессоров первого столбца решетки). На втором этапе реализуется циклический сдвиг вверх с шагом $$\lfloor q/ \sqrt{p} \rfloor$$ для каждого столбца решетки. Общая длительность всех операций рассылок определяется соотношением:$$t_{\textit{пд}} = (t_{\textit{н}} + mt_{\textit{к}})(2 \lfloor \sqrt{p} / 2 \rfloor + 1).$$

Для гиперкуба алгоритм циклического сдвига может быть получен путем логического представления топологии гиперкуба в виде кольцевой структуры. Для получения такого представления установим взаимно-однозначное соответствие между вершинами кольца и гиперкуба. Необходимое соответствие может быть получено, например, при помощи известного кода Грея. Более подробное изложение механизма установки такого соответствия осуществляется в подразделе 3.3; для наглядности на рис. 3.1 приводится вид гиперкуба для размерности N=3 с указанием для каждого процессора гиперкуба соответствующей вершины кольца. Положительным свойством выбора такого соответствия является тот факт, что для любых двух вершин в кольце, расстояние между которыми равно l=2i для некоторого значения i, путь между соответствующими вершинами в гиперкубе содержит только две линии связи (за исключением случая i=0, когда путь в гиперкубе имеет единичную длину).

Представим величину сдвига q в виде двоичного кода. Количество ненулевых позиций кода определяет количество этапов в схеме реализации операции циклического сдвига. На каждом этапе выполняется операция сдвига с величиной шага, задаваемой наиболее старшей ненулевой позицией значения q (например, при исходной величине сдвига q=5=1012 на первом этапе выполняется сдвиг с шагом 4, на втором этапе шаг сдвига равен 1). Выполнение каждого этапа (кроме сдвига с шагом 1) состоит в передаче данных по пути, включающему две линии связи. Как результат, верхняя оценка для длительности выполнения операции циклического сдвига определяется соотношением:$$t_{\textit{пд}} = (t_{\textit{н}} + mt_{\textit{к}})(2 \log_2 p-1).$$

Передача пакетов. Использование пересылки пакетов может повысить эффективность выполнения операции циклического сдвига для топологии гиперкуб. Реализация всех необходимых коммуникационных действий в этом случае может быть обеспечена путем отправления каждым процессором всех пересылаемых данных непосредственно процессорам назначения. Применение метода покоординатной маршрутизации (см. п. 3.1.1) позволит избежать коллизий при использовании линий передачи данных (в каждый момент времени для каждого канала будет существовать не более одного готового для отправки сообщения). Длина наибольшего пути при такой рассылке данных определяется как $$log_{2}p-\gamma (q)$$, где $$\gamma (q)$$ есть наибольшее целое значение j такое, что 2j есть делитель величины сдвига q. Тогда длительность операции циклического сдвига может быть охарактеризована при помощи выражения$$t_{\textit{пд}} = t_{\textit{н}} + mt_{\textit{к}} + t_{\textit{с}}(\log_2 p - \gamma(q))$$ (при достаточно больших размерах сообщений временем передачи служебных данных можно пренебречь и время выполнения операции может быть определено как $$t_{\textit{пд}} = t_{\textit{н}} + mt_{\textit{к}}$$ ).

3.3. Методы логического представления топологии коммуникационной среды

Как показало рассмотрение основных коммуникационных операций в подразделе 3.1, ряд алгоритмов передачи данных допускает более простое изложение при использовании вполне определенных топологий сети межпроцессорных соединений. Кроме того, многие методы коммуникации могут быть получены при помощи того или иного логического представления исследуемой топологии. Как результат, важным моментом при организации параллельных вычислений является возможность логического представления разнообразных топологий на основе конкретных (физических) межпроцессорных структур.

Способы логического представления (отображения) топологий характеризуются следующими тремя основными характеристиками:

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

3.3.1. Представление кольцевой топологии в виде гиперкуба

Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i, N) ( binary reflected Gray code ), определяемого в соответствии с выражениями:$$\begin{aligned} G(0,1)=0, \quad G(1,1)=1, \\ G(i,s+1)= \left\{ \begin{aligned} G(i,s), i < 2^s, \\ 2^s + G(2^{s+1} - 1 -i,s), \quad i \ge 2^s, \end{aligned} \right. \end{aligned}$$ где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода в табл. 3.1 показывается отображение кольцевой топологии на гиперкуб для сети из p=8 процессоров.

Важное свойство кода Грея: соседние значения G(i,N) и G(i+1,N) имеют только одну различающуюся битовую позицию. Как результат, соседние вершины в кольцевой топологии отображаются на соседние процессоры в гиперкубе.

3.3.2. Отображение топологии решетки на гиперкуб

Отображение топологии решетки на гиперкуб может быть выполнено в рамках подхода, использованного для кольцевой структуры сети.

Тогда для отображения решетки $$2^r \times 2^s$$ на гиперкуб размерности N=r+s можно принять правило, что элементу решетки с координатами (i, j) соответствует процессор гиперкуба с номером:

G(i,r)||G(j,s),

где операция || означает конкатенацию кодов Грея.

3.4. Оценка трудоемкости операций передачи данных для кластерных систем

Для кластерных вычислительных систем (см. п. 1.2.2) одним из широко применяемых способов построения коммуникационной среды является использование концентраторов ( hub ) или коммуникаторов ( switch ) для объединения процессорных узлов кластера в единую вычислительную сеть. В этих случаях топология сети кластера представляет собой полный граф, в котором, однако, имеются определенные ограничения на одновременность выполнения коммуникационных операций. Так, при использовании концентраторов передача данных в каждый текущий момент может выполняться только между двумя процессорными узлами; коммуникаторы могут обеспечивать взаимодействие нескольких непересекающихся пар процессоров.

Другое часто применяемое решение при создании кластеров состоит в использовании метода передачи пакетов (часто реализуемого на основе стека протоколов TCP/IP) в качестве основного способа выполнения коммуникационных операций.

Если выбрать для дальнейшего анализа кластеры данного распространенного типа (топология в виде полного графа, пакетный способ передачи сообщений), то трудоемкость операции коммуникации между двумя процессорными узлами может быть оценена в соответствии с выражением ( модель А )$$t_{\textit{пд}}(m) = t_{\textit{н}} + m^*t_{\textit{к}} + t_{\textit{с}};$$ оценка подобного вида следует из соотношений для метода передачи пакетов при единичной длине пути передачи данных, т.е. при l=1. Отмечая возможность подобного подхода, вместе с этим можно заметить, что в рамках рассматриваемой модели время подготовки данных tн предполагается постоянным (не зависящим от объема передаваемых данных), время передачи служебных данных tс не зависит от количества передаваемых пакетов и т.п. Эти предположения не в полной мере соответствуют действительности, и временные оценки, получаемые в результате использования модели, могут не обладать необходимой точностью.

С учетом приведенных замечаний, схема построения временных оценок может быть уточнена; в рамках новой расширенной модели трудоемкость передачи данных между двумя процессорами определяется в соответствии со следующими выражениями ( модель В ):$$t_{\textit{пд}} = \left\{ \begin{aligned} t_{\text{нач}_0} + m \cdot t_{\text{нач}_1} + (m + V_{\textit{с}}) \cdot t_{\textit{к}} \, , n=1 \\ t_{\text{нач}_0} + (V_{\max}- V_{\textit{с}}) \cdot t_{\text{нач}_1} + (m + V_{\textit{с}} \cdot n) \cdot t_{\textit{к}} \, , \quad n > 1 \end{aligned} \right. ,$$ где $$n=\lceil m/(V_{max}–V_c)\rceil$$ есть количество пакетов, на которое разбивается передаваемое сообщение, величина Vmax определяет максимальный размер пакета, который может быть доставлен в сети (по умолчанию для операционной системы MS Windows в сети Fast Ethernet Vmax=1500 байт), а Vc есть объем служебных данных в каждом из пересылаемых пакетов (для протокола TCP/IP, ОС Windows 2000 и сети Fast Ethernet Vc=78 байт). Поясним также, что в приведенных соотношениях константа $$t_{\textit{нач}_0}$$ характеризует аппаратную составляющую латентности и зависит от параметров используемого сетевого оборудования, значение $$t_{\textit{нач}_1}$$ задает время подготовки одного байта данных для передачи по сети. Как результат, величина латентности$$t_{\textit{н}} = t_{\textit{нач}_0} + \nu \cdot t_{\textit{нач}_1}$$ увеличивается линейно в зависимости от объема передаваемых данных. При этом предполагается, что подготовка данных для передачи второго и всех последующих пакетов может быть совмещена с пересылкой по сети предшествующих пакетов и латентность, тем самым, не может превышать величины:$$t_{\textit{н}} = t_{\textit{нач}_0} + (V_{\max}-V_c) \cdot t_{\textit{нач}_1}.$$

Помимо латентности, в предлагаемых выражениях для оценки трудоемкости коммуникационной операции можно уточнить также правило вычисления времени передачи данных$$(m + V_c \cdot n) \cdot t_{\textit{к}} \, ,$$ что позволяет теперь учитывать эффект увеличения объема передаваемых данных при росте числа пересылаемых пакетов за счет добавления служебной информации (заголовков пакетов).

Завершая анализ проблемы построения теоретических оценок трудоемкости коммуникационных операций, следует отметить, что для практического применения перечисленных моделей необходимо выполнить оценку значений параметров используемых соотношений. В этом отношении полезным может оказаться использование и более простых способов вычисления временных затрат на передачу данных – одной из известных схем подобного вида является подход, в котором трудоемкость операции коммуникации между двумя процессорными узлами кластера оценивается в соответствии с выражением:$$t_{\textit{пд}}(m) = t_{\textit{н}} + mt_{\textit{к}}$$ это модель C, предложенная Хокни ( the Hockney model ) – см., например, [46].

Для проверки адекватности рассмотренных моделей реальным процессам передачи данных приведем результаты выполненных экспериментов в сети многопроцессорного кластера Нижегородского университета (компьютеры IBM PC Pentium 4 1300 MГц и сеть Fast Etherrnet). При проведении экспериментов для реализации коммуникационных операций использовалась библиотека MPI.

Часть экспериментов была выполнена для оценки параметров моделей:

В ходе экспериментов осуществлялась передача данных между двумя узлами кластера, размер передаваемых сообщений варьировался от 0 до 8 Мб. Для получения более точных оценок выполнение каждой операции осуществлялось многократно (более 100 000 раз), после чего полученные результаты усреднялись. Для иллюстрации ниже приведен результат одного эксперимента, при проведении которого размер передаваемых сообщений изменялся от 2000 до 60 000 байт.

В табл. 3.2 приводится ряд числовых данных по погрешности рассмотренных моделей трудоемкости коммуникационных операций (величина погрешности дается в виде относительного отклонения от реального времени выполнения операции передачи данных).

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

Вместе с этим важно отметить, что для предварительного анализа временных затрат на выполнение коммуникационных операций точности модели C может оказаться достаточно. Кроме того, данная модель имеет наиболее простой вид среди всех рассмотренных. С учетом последнего обстоятельства, далее во всех последующих лекциях для оценки трудоемкости операций передачи данных будет применяться именно модель C (модель Хокни), при этом для модели будет использоваться форма записи, приведенная к обозначениям, которые приняты в работе Хокни [46]:$$t_{\textit{пд}}(m) = \alpha + m/ \beta,$$ где $$\alpha$$ есть латентность сети передачи данных (т.е. $$\alpha =t_{н}$$ ), а $$\beta$$ обозначает пропускную способность сети (т.е. $$\beta =R=1/t_{к}$$ ).

3.5. Краткий обзор лекции

Данная лекция посвящена оценке коммуникационной сложности параллельных алгоритмов.

В подразделе 3.1 представлена общая характеристика алгоритмов маршрутизации и методов передачи данных. Для подробного рассмотрения выделены метод передачи сообщений и метод передачи пакетов, для которых определены оценки времени выполнения коммуникационных операций.

В подразделе 3.2 определены основные типы операций передачи данных, выполняемых в ходе параллельных вычислений. К основным коммуникационным операциям относятся:

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

В подразделе 3.3 рассмотрены методы логического представления топологий на основе конкретных (физических) межпроцессорных структур. Использование логических топологий позволяет получить более простое изложение для ряда алгоритмов передачи данных, снизить затраты на реализацию коммуникационных операций и т.п.

В подразделе 3.4 более подробно обсуждаются модели, при помощи которых могут быть получены оценки времени выполнения операций передачи данных для кластерных вычислительных систем. Точность формирования временных оценок сравнивается при помощи проведения вычислительных экспериментов. По результатам экспериментов определена наиболее точная модель (модель B ). Кроме того, отмечается, что для предварительного анализа временной трудоемкости коммуникационных операций целесообразно использовать более простую модель – модель C ( модель Хокни ).

3.6. Обзор литературы

В качестве дополнительного учебного материала для данной лекции могут быть рекомендованы работы [51, 63].

Вопросы построения моделей для оценки времени выполнения коммуникационных операций широко обсуждаются в литературе. При изучении лекции могут быть полезны работы [, , ]. Модель Хокни впервые была опубликована в []. Модель B из подраздела 3.4 представлена в работе [].

3.7. Контрольные вопросы

3.8. Задачи и упражнения