Шаг 25.
Параллельные алгоритмы. Общая характеристика механизмов передачи данных. Оценка трудоемкости операций передачи данных

    На этом шаге мы приведем различные оценки трудоемкости операций передачи данных.

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

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

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

tпд(m) = tн + m*tк + tc .

    Оценка подобного вида следует из соотношений для метода передачи пакетов при единичной длине пути передачи данных, т.е. при l=1. Отмечая возможность подобного подхода, вместе с этим можно заметить, что в рамках рассматриваемой модели время подготовки данных tн предполагается постоянным (не зависящим от объема передаваемых данных), время передачи служебных данных tс не зависит от количества передаваемых пакетов и т.п. Эти предположения не в полной мере соответствуют действительности, и временные оценки, получаемые в результате использования модели, могут не обладать необходимой точностью.

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

где n = [m/(Vmax-Vc)] есть количество пакетов, на которое разбивается передаваемое сообщение, величина Vmax определяет максимальный размер пакета, который может быть доставлен в сети (по умолчанию для операционной системы MS Windows в сети Fast Ethernet Vmax=1500 байт), а Vc есть объем служебных данных в каждом из пересылаемых пакетов (для протокола TCP/IP, ОС Windows 2000 и сети Fast Ethernet Vc=78 байт). Поясним также, что в приведенных соотношениях константа tнач0 характеризует аппаратную составляющую латентности и зависит от параметров используемого сетевого оборудования, значение tнач1 задает время подготовки одного байта данных для передачи по сети. Как результат, величина латентности

tн = tнач0 + v*tнач1

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

tн = tнач0 + (Vmax - Vc)*tнач1.

    Помимо латентности, в предлагаемых выражениях для оценки трудоемкости коммуникационной операции можно уточнить также правило вычисления времени передачи данных

(m + Vc*n)*tк,

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

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

tпд(m) = tн + mtк.

    Это модель C, предложенная Хокни.

    Данная модель имеет наиболее простой вид среди всех рассмотренных. С учетом последнего обстоятельства, далее для оценки трудоемкости операций передачи данных будет применяться именно модель C (модель Хокни), при этом для модели будет использоваться форма записи, приведенная к обозначениям, которые приняты в работе Хокни:

tпд(m) = альфа + m/бета,

где альфа есть латентность сети передачи данных (т.е. альфа = tн), а бета обозначает пропускную способность сети (т.е. бета = R = 1/tк).

    Со следующего шага мы начнем рассматривать создание алгоритмов и программ.




Предыдущий шаг Содержание Следующий шаг