Соотношения между количеством данных, обрабатываемых в узле МВС на каждом шаге вычислений, и количеством данных, пересылаемых между узлами в конце шага

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

Счет вычислительной модели на МВС складывается из выполнения шагов счета на каждом процессоре без межпроцессорных обменов внутри шага и обменов насчитанными данными между процессорами после окончания каждого шага. В некоторых случаях удается совместить счет с обменами, но это требует разработки специальных схем счета и не всегда возможно в основном из за дополнительных трудозатрат на соответствующую модификацию уже существующего алгоритма. Эффективность параллельного счета зависит прежде всего от отношения времени счета шага и времени обмена данными, не совмещенного с временем процессорного счета (проще говоря, это время простоя процессоров). Если это отношение равно, например 9, то даже без использования по тем или иным причинам совмещения счета и обменов мы получим ускорение счета модели на 100 процессорах в 90 раз по сравнению со счетом на одном процессоре (КР=0.9).

//___________________________________________________________________//

Связь коэффициента распараллеливания и отношения обмены/счет.

КР = 1/(1+КО) где КО = ТО / ТП

Здесь:

ТО - астрономическое время обменов, не совмещенных с счетом, для одного процессора. Рассматривается упрощенная ситуация, когда времена счета и обменов одни и те же для всех процессоров.

ТП - астрономическое время счета одного процессора без учета простоев.

//___________________________________________________________________//

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

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

4.3.1. Физическая среда

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

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

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

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

Случай «мгновенного» распространения нового значения в случае поля должен компенсироваться относительно малой частотой изменений поля по отношению к остальным моделируемым процессам.

4.3.2. Вычислительный алгоритм

Идеальным является случай, когда счет совмещается с обменами. Такой алгоритм должен начинаться с обсчета ячеек в приграничной полосе, предназначенной для обмена с соседними подобластями, запускать отсылку значений из обсчитанной приграничной полосы и лишь после этого переходить к счету внутренней части подобласти, который в этом случае будет совмещен с обменом. В этом случае простои процессоров отсутствуют, требования к системе обмена минимальны и КР=1.

4.3.3. Аппаратура

Из сказанного выше следуют вполне определенные требования к аппаратуре.

Соотношение вычислительной мощности процессора, объема памяти и времени обмена (время передачи плюс время запуска операции обмена) должно быть в некотором смысле «подобно» физической среде. Если, например, для физической среды характерна очень большая скорость распространения возмущений, то большая часть процессоров будет простаивать, дожидаясь окончания обменов, если скорость обменов мала, или мал объем оперативной памяти, или производительность процессоров слишком большая.

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

5. Программирование примеров для МВС

5.1. Параллельное умножение матриц

5.1.1. Реализация через MPI и С++

5.1.2. Реализация через OST

5.2. Решение уравнения параболического типа на интервале [0,L]

3. 
   Реализация через MPI и С++
   
4. 
   Реализация через OST
   

Приложение Х. Коэффициент распараллеливания

Рассмотрим зависимость коэффициента распараллеливания от числа используемых процессоров, так как известно, что после увеличения числа процессоров выше некоторого предела эффективность распараллеливания существенно падает. Поскольку в рассматриваемом нами случае КР = 1 / (1 + КО) будем рассматривать зависимость доли обменов КО от Р (числа используемых процессоров) или точнее от числа подобластей (так как процессоры могут быть и виртуальными). Будем считать, что и время счета и время обменов линейно зависят от количества обрабатываемых и соответственно передаваемых данных. Предполагается, что такое упрощение не влияет существенно на качественные результаты анализа. На самом деле, во-первых, зависимость является кусочно-линейной из за организационных расходов в начале и конце как очередного шага счета на процессоре, так и очередного обмена. Во-вторых, хотя на практике считается, что процессорное время одного шага линейно зависит от числа обсчитываемых ячеек сетки для большинства используемых алгоритмов, однако, например, при умножении матриц процессорное время растет как n**1.5 (где n — число элементов матрицы, правда это существенно только для плотно заполненных матриц, которые по-видимому не описывают реальных физических систем, так как полностью заполненная матрица отражает «мгновенную» связь между всеми частями системы).

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

Рассмотрим сначала двумерный случай. Очевидно, что в практически интересных случаях по мере дробления области длина границ будет расти расти как квадратный корень от числа подобластей. Так как число параллельно запускаемых операций ввода/вывода линейно растет с увеличением числа процессоров (подобластей), то казалось бы качество распараллеливания должно только расти с увеличением числа процессоров (со скоростью n**0.5). И это действительно верно для тех случаев, когда величина накладных расходов на пуск/стоп обменов и шагов счета мала по сравнению с временем передачи через среду связи в случае обменов и временем «чистого» счета шага на процессоре. В реальности эти накладные расходы достаточно велики и их необходимо учитывать. Дело в том, что эти расходы в случае пересылки блока данных практически не зависят от длины блока. При увеличении числа подобластей и соответственно уменьшении количества передаваемых и обсчитываемых данных в пределе основное время будут занимать именно накладные расходы. В результате с увеличением числа процессоров астрономическое время счета будет оставаться постоянным, а соответственно коэффициент распараллеливания будет уменьшаться в обратной пропорциональной зависимости от числа процессоров. И такая ситуация достаточно часто наблюдается на практике.

Итоговый вывод совершенно тривиален — дробление области и соответственно увеличение числа процессоров нужно остановить в тот момент, когда накладные расходы на операции «пуск/стоп» будут составлять существенную долю от самого счета и обменов.

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

Приложение Z. OST и функциональное программирование

Попытаемся сравнить программирование на OST и каком либо функциональном языке, например, языке Норма.

Начнем с того, что вызов операции в объекте и факт наличия связи между вызываемым и вызывающим объектом может быть записан в “фукциональном” стиле в виде:

А.У = B.F(А.X)

Где:

А.У – переменная-результат внутри вызывающего объекта А. Так как в функциональных языках отсутствуют переменные, меняющие свое состояние в процессе исполнения, здесь используется лишь “стилизация” под функциональную запись, а не строгое следование всем принципам функционального программирования.

В.F – операция, которую умеет выполнять вызываемый объект В

А.Х – переменная-аргумент внутри А

Тогда, повидимому, можно утверждать, что описание внешних интерфейсов всех объектов модели (в обычном смысле объектно-ориентированных языков в виде описания операций и их параметров) плюс описание топологии связей объектов фактически является функциональным. Действительно, оно почти эквивалентно заданию множества равенств вида А.У = B.F(А.X). Так как описание связей в OST основано на использовании координат объектов, которые могут меняться в момент счета, то в отличие от известных функциональных языков отношения в OST мост могут изменяться динамически.

Можно утверждать, что, OST предлагает для программирования “внутренности” объектов, вообще говоря, любой стиль программирования (из соображений эффективности, конечно прежде всего процедурный или в терминологии функциональных языков императивный), а для “внешнего” по отношению к объектам, составляющим модель, программирования предлагает функциональный стиль. Кроме того в отличие от функциональных языков предлагается конкретный механизм интерпретации функиональной записи. Вводится понятие локального времени объекта, времени выполнения операции и упорядочения актов выполнения операций путем разрешения выполнения операции только при равенстве локальных времен вызывающего и вызываемого объектов.

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