Параллельные модели

Рассмотрим также функции ошибок: и . Также рассмотрим соответствующие уравнения для них:

Если норма данных функций будет стремиться к нулю при увеличении количества итераций, то метод построенная модель действительно будет давать решение уравнения.

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

, 0≤x≤L.

Для этого определим вспомогательную функцию , как решения уравнения:

Решение этого уравнения легко угадать, оно будет единственным, причем независящим от t:

По построению мы имеем на

. Так как

принадлежит ядру дифференциального оператора, то согласно принципу максимума мы имеем

на всей рассматриваемой области, а это значит, что

Точно также на границах и принадлежит ядру дифференциального оператора, откуда получаем

Объединяя, эти два результата в итоге имеем

Так как правая часть не зависит от t, мы можем взять супремум по t и получить доказываемую оценку для

Применяя, только что доказанную оценку к функциям ошибок получаем

,

и

, .

Если взять в соответствующих неравенствах, то применяя второе из них к первому, и наоборот первое ко второму получаем

,

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

,

и

.

Используя эти и предыдущие неравенства, выводим оценки

,

и

,

которые доказывают сходимость метода при выбранном нами диапазоне значений �� и ��.

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

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

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

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

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

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

Рассмотрим теперь область , такую что:

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

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

3.3.3.3. Использование приграничных «потоков» для композиции подобластей

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

Для примера рассмотрим двумерную систему уравнений Сен-Венана (уравнения мелкой воды), записанных в консервативной форме.

,

где

соответственно,

функция источнкиа.

Уравнения могут быть переписаны в виде:

где

Неизвестные, которые необходимо найти:

При дискретизации область сеткой разбивается на ячейки или контрольные объемы. Запишем уравнения в интегральной форме для некоторого контрольного объема (на рисунке – Control volume)

После применения теоремы Гаусса последнее выражения может быть переписано в виде:

Где обозначает границу контрольного объема, а единичный вектор нормали к границе, направленный наружу.

Запишем это выражения для каждой ячейки сетки, введя при этом среднее значение на и площадь

Применим самую простую аппроксимацию по времени для первого члена и правило средней точки для интеграла по границе. После вынесения в левую часть получим:

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

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

Рассмотрим расчет ячейки IV: для нахождения в ней необходимо знать эти значения из ячеек I, V и VI. Ячейка I находится на другом процессоре, соответственно данные с нее необходимо передать перед началом счета. То же самое актуально для остальных ячеек на границе и их соседей с другого процессора. После же того как граница просчитана, можно переходить к внутренним ячейкам, для расчета которых имеются все данные на процессоре.

Таким образом, для каждого процессора алгоритм расчета на шаге по времени n+1 можно представить так:

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

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

3.4. Уравнения и параллелизм – уровень математической модели

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

По аналогии с функциональными языками про уравнения можно сказать, что они, описывая лишь отношения между переменными (и задавая тем самым лишь связи между частями физической модели), с одной стороны никак не ограничивают возможности по построению параллельных программных моделей. С другой стороны в них нет никакой информации (и это обратная сторона медали) об эффективном отображении математической модели на множество последовательных процессоров и построение такого отображения является трудной задачей индивидуально для каждого типа уравнений. Дело в том, что из уравнений нужно извлечь информацию о том, какие действия над данными, моделирующие эволюцию частей физической системы, можно выполнять параллельно, а какие последовательно. Обязательное выполнение некоторых действий чисто последовательно можно интерпретировать как наличие в физическом системе причинно-следственной связи между этими действиями. К сожалению в тех разделах математики, которые используются при построении вычислительных моделей, отсутствует общеизвестная конструкция, специально предназначенная, для отражения такой существенной для моделирования физических систем черты как причинно-следственная зависимость между двумя действиями. В программировании такой конструкцией является оператор присваивания. Выражение Y := f(X) означает, что из переменной Х в конкретный момент исполнения программы выбирается значение, это значение используется при вычислении функции f и полученное значение этой функции присваивается переменной Y в некоторый следующий момент исполнения программы. В результате можно утверждать, что причиной появления в некоторый момент конкретного значения переменной Y стало значение переменной Х в некоторый предыдущий момент времени. Запись в программе последовательности из нескольких операторов присваивания можно трактовать лишь как упорядочение действий во времени, но не обязательно причинно-следственную связь, так как последовательно выполняемые действий могут относится к разным переменным. Напротив в математике запись y=f(x), вообще говоря, может быть записана в виде u(x,y)=0. И что является причиной, а что следствием в данной записи не находит никакого отражения. Поскольку обнаружение причинно-следственных зависимостей в физических системах является чуть ли не главной целью их моделирования, то было бы естественно в математических моделях использовать соответствующую конструкцию. Например, «направленное» равенство, аналогичное оператору присваивания в программировании.

В итоге можно сказать, что в механизме уравнений не находят явного отражения два взаимосвязанных понятия - «причинная зависимость действий» и «независимость действий», хотя сами действия в уравнениях присутствуют. Как следствие уравнения, так сказать, «перпендикулярны» к проблемам распараллеливания.

4. Эффективность распараллеливания

Эффективность при создании и счете параллельных программно-аппаратных моделей можно оценивать самым обычным образом в терминах «производительность - стоимость». Как обычно, можно оптимизировать, например, производительность за счет стоимости или наоборот. Производительность можно измерять в терминах астрономического времени счета тестовой задачи или представительной смеси задач (см.,например, []). Обозначим это время как ТА. Стоимость можно измерять в суммарном «платном» времени процессоров, использованных для счета. Обозначим это время как ТP. Тогда ТP = ТА * P . Здесь P — это число использованных процессоров. Конечно, на практике и стоимость счета может не быть пропорциональна времени использования и количеству использованных процессоров, и процессоры могут быть использованы разные даже в в пределах одного счета. Однако для целей сравнения качества различных программно-аппаратных моделей эти характеристики по мнению авторов вполне пригодны.

Коэффициент ускорения при распараллеливании

Из соотношения ТP = ТА * P видно, что если бы время счета уменьшалось пропорционально числу использованных процессоров, то можно было бы ничего не оптимизировать. Стоимость счета с увеличением числа процессоров не увеличивалась бы, а время счета уменьшалось. Можно было бы просто запрашивать максимально доступное число процессоров. Однако, хорошо известно, что при увеличении числа участвующих в счете процессоров чаще всего не происходит пропорционального уменьшения времени счета, а иногда время счета увеличивается. Поэтому качество программно-аппаратной модели в целом удобно оценивать величиной, показывающей насколько реально ускоряется счет при увеличении числа процессоров. Будем называть эту величину коэффициентом распараллеливания КР и определим ее как:

КР = (ТА1 / TA2) / (P2 / P1)

Здесь

Р1 и ТА1 — это число процессоров, использованных для счета, и измеренное астрономическое время счета в первом тесте, а Р2 и ТА2 — соответствующие значения во втором тесте одной и той же программно-аппаратной модели. Зная значение КР для конкретной программно-аппаратной конфигурации, можно оценить эффект использования большего или меньшего числа процессоров. Например, при использовании 10 процессоров вместо одного при КР = 1 время счета уменьшится в 10 раз, а при КР = 0.5 только в 5 раз.

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

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

<предыдущая страница | следующая страница>