WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |

j R (k ) ( j) (k ) ( j ) (k +1) (n + j) = (n + j - i) + ( j) + ( j) ( j), j = 1, R. (3) i i i=1 i=( Матричные коэффициенты i j) описывают зависимость от предыстории (значений на левой границе); i( j) – от значений на правой границе. Треугольная матрица ( j ) определяет линейное преобразование белого шума к заданной корреляционной ( структуре. Принципиальным отличием (3) от (2) является то, что i j),i( j ),( j) зависят от j = 1, R, т.е. выражение (3) на интервале t [0,R] описывает нестационарный процесс, (k +1) эволюция которого определяется значениями (t), t = 1,2,...

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

Рассмотрим факторную модель пространственно-временного базиса на основе разложений по ортогональному базису в форме:

L (r,t) = m(r) + (t)k (r) + (r,t). (4) ak k =Здесь t = 1,T, а скалярная переменная r = 1, K индексирует узлы сеточной области. Сеточная функция m(r) суть среднее значение поля, k (•) - базисные функции, заданные на сеточной области, (•,•) - сеточная функция гауссова белого шума с дисперсией D (r), не зависящей от t.

Скалярные коэффициенты ak (t) рассматриваются как система некоррелированных гауссовых случайных функций, задаваемых, например (2).

Выражение (4), несмотря на его алгоритмическую наглядность, при фиксированных значениях коэффициентов ak (t) допускает сразу три различных способа распараллеливания, см. рис. 5:

• Распараллеливание по ансамблю (по t) с использованием принципа перемешивания.

• Распараллеливание по индексирующей переменной r : декомпозиция расчетной пространственной области.

• Распараллеливание по слагаемым. Этот Рис. 5. Способ параллельной подход очевиден в том случае, если декомпозиции факторной модели (4) по коэффициенты в разложении (4) индексирующей переменной.

независимы.

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

Описанные выше статистические модели имеют существенную практическую значимость. Например, модель авторегрессии (2-3) применяется для синтеза различных экономических [Айвазян и Мхитарян, 1999], гидрометеорологических [Рожков, Трапезников, 1990], технологических [Марпл мл., 1990] и др. процессов. Факторная модель случайного поля (5) используется для описания многомасштабной изменчивости гидрометеорологических полей [Boukhanovsky et al., 2003].

ОСНОВНЫЕ ИДЕИ РАЗДЕЛА Использование естественных способов распараллеливания для задачи статистической обработки данных позволяет строить количественные модели производительности в параметрической форме. Параметры моделей производительности совокупно учитывают архитектуру вычислительных систем, особенности системного программного обеспечения и характеристики параллельного алгоритма.

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

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

Модель функционирования параллельной программы обработки данных Для наглядности изложения методологии количественного анализа параллельной производительности рассмотрим наиболее простой способ организации параллельной программы в рамках способа «хозяин-и-работники» («master-slave»), что соответствует архитектуре вычислительной фермы. На рис. 6 определено место четырех основных операций: рассылка независимых фрагментов данных с узла ввода-вывода на параллельные ветви (ПВ) «А», применение вычислительной процедуры к данным на каждой ПВ «В», сбор результатов расчета на одной из параллельных ветвей (будем называть ее главной, ГПВ) «С». Дополнительно может рассматриваться операция «D» - обработка (согласование) результатов расчетов каждой из ПВ на ГПВ с целью получения окончательного результата A C B D B B B Рис. 6. Схема организации простейшей параллельной программы обработки данных Такому способу организации параллельной программы соответствует, например, N задача статистической обработки m -мерных данных объема с помощью процедуры «B», которая выполняется параллельно на p вычислительных узлах. Приведение задачи к параллельной форме выполняется посредством принципа декомпозиции по ансамблю p или по индексирующей переменной, который позволяет представить N =. В ni i=простейшем случае задействованы три этапа схемы на рис. 6:

• Рассылка с узла ввода-вывода объема данных mni на узел #i, i = 2, p (операция «А»).

• Параллельная обработка объема данных mni на каждом узле (включая узел вводавывода, операция «В»).

• Сбор m результатов обработки с узлов #i, i = 2, p на узел ввода-вывода. Здесь - количество статистик, которые строятся по данным (операция «С») Этапы подготовки данных и согласования результатов расчетов на узле вводавывода («D») здесь не рассматриваются.

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

• Модель передачи сообщений. Она реализуется путем запуска копий одного и того же приложения на нескольких параллельных узлах, с последующим обменом данными между ними в явной форме. Такая модель может быть реализована и на параллельных компьютерах SMP и MPP-архитектур, а также в гиперсетях (например, GRID при использовании библиотеки MPI в среде Globus).

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

Таким образом, обе модели управления многопроцессорной системой можно p описать неориентированным графом,С, где множество вершин = {i,i} i=соответствует вычислительным узлам (процессорам) производительности P с локальной i оперативной памятью i. Процессор P1, в зависимости от архитектуры вычислительной системы, может одновременно реализовывать операции ввода-вывода. Множество ребер C = {c } задает пропускную способность коммуникационной сети между j вычислительными узлами. При отображении конкретного алгоритма на архитектуру многопроцессорной системы задействуются далеко не все связи между процессорами C = {c }, а только те, которые задействованы в схеме. Тогда такая задача j характеризуется тремя группами величин:

• p – количество вычислительных узлов (включая узел ввода-вывода).

• tc – время характерной (для данного алгоритма) вычислительной операции на узле i (tc tc I / O ).

• tw – время передачи характерного объема данных между узлом, на котором хранятся i данные, и вычислительным узлом (предполагается одинаковой в обоих направлениях). В некоторых архитектурах узел ввода-вывода не осуществляет напрямую рассылку данных на другие узлы, а передает их на виртуальный коммуникатор. В этом случае значение tw определяется не только характеристиками i канала между интерфейсным компьютером и сервером данных, но именно связями сервера с другими узлами.

В общем случае такая вычислительная система должна рассматриваться как неоднородная. Неоднородность вычислительной системы обеспечивается следующими факторами:

• число узлов p может меняться от запуска к запуску приложения (во время одного запуска предполагается неизменным).

• Мощность вычислительных узлов различается: tci tc j (могут использоваться узлы с процессорами различной производительности, и даже архитектуры).

• Времена передачи данных между узлом ввода-вывода и вычислительными узлами различаются: tw tw. Это может быть обусловлено как нестационарностью i j загрузки сети, так и сложными маршрутами передачи данных между узлами (не напрямую в узел ввода-вывода, а через маршрутизаторы, другие узлы и пр.).

Описание изменчивости параметров (p,tc,tw ) с точки зрения пользователя i j можно соотнести с классификацией вычислительных систем, см. табл. 1.

Таблица Классификация вычислительных систем по типу управления параллельным приложением (p,tc,tw ).

i j № Параметры системы Характеристика SMP-система (для p = 1 – персональный p = const, tc = const, tw = компьютер) p = const, tc = tc = const,tw = tw = const 2 Однородная MPP-система i i p = const, tc i = const, tw i = tw = const 3 Неоднородная MPP-система (кластер) Гиперкластер или локальная сеть для p = const, tc i = const, twi = const распределенных вычислений p = const, tc = const, tw i – заранее не Локализованная вычислительная i гиперсеть (Testbed GRID) известны и меняются от запуска к запуску p, tc i, tw i – заранее не известны и Гиперсеть распределенных вычислений (GRID «в идеале») меняются от запуска к запуску Ускорение и эффективность параллельных программ Для описания производительности любого параллельного алгоритма можно использовать, как минимум, два параметра:

• Ускорение (speedup) S = T1 /Tp, где T1,Tp – реальное время выполнения p параллельного алгоритма на 1 и p процессорах соответственно.

• Эффективность (efficiency), = S / p, определяющая реальную выгоду от p использования многопроцессорных систем по сравнению с однопроцессорными.

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

К измерению производительности существует несколько подходов:

• «Аппаратный» подход, основанный на измерении производительности вычислительных систем с использованием набора стандартных тестов, например Linpack и пр. [Корнеев, 2004]. Он имеет целью скорее сравнение характеристик вычислительных комплексов, а не программного обеспечения, в силу отличий постановок тестовых задач от требований прикладного ПО.

• «Программный» подход, или benchmarking, основанный на прямом измерении производительности программных средств на вычислительных системах, используя различные входные данные. Он дает наилучшие результаты с точки зрения изучения возможностей прикладного ПО. Недостаток состоит в том, что такой подход является чисто поверочным – для его использования ПО должно быть полностью разработано.

• «Аналитический» подход, разрабатываемый научной школой В.В. Воеводина [Воеводин и Воеводин, 2002]. Он состоит в использовании специальных инструментальных средств трассировки параллельных приложений, которые позволяют проследить вклад в производительность основных факторов (аппаратного, системного и пр.) и сформулировать рекомендации по управлению ими. Этот подход ориентирован на работу с программными кодами. Он не использует никаких априорных знаний о реализуемом математическом методе или модели.

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

k i S( p) = S( p,,tw,tc ). (5) k i При этом значения tw и tc не обязательно соответствуют реальным операциям с плавающей точкой; они могут рассматриваться как некоторые обобщенные характеристики, определяющие базовые для рассматриваемого алгоритма действия (например, передача одной матрицы фиксированного размера, операция GAXPY и пр.). С одной стороны, это может показаться менее удобным, чем использование объективных оценок (например, числа операций с плавающей точкой), но для сопоставления различных алгоритмов такой подход более приемлем как в силу наглядности, так и простоты оценки параметров.

Получаемые значения специфичны для каждой многопроцессорной системы и определяются по результатам тестирования. В отдельных случаях (например, при сравнении нескольких алгоритмов) допустимо использовать временные характеристики указанных операций, полученные с помощью стандартных тестов (Linpack, SPEC, TPC и пр.), которые для подавляющего большинства многопроцессорных систем являются необходимой составляющей системной документации. Главным достоинством такого способа определения характеристик tw и tc является то, что тесты учитывают не только архитектурные особенности системы, но и возможности системного программного обеспечения, специфику компиляции программного кода и пр. Эти факторы, в комплексе определяющие эффективность использования МО, в настоящее время не представляется возможным определить теоретическим путем.

Модели производительности для МРР-систем Ниже мы рассмотрим способы построения моделей производительности для систем различных архитектур из табл. 1, на примере алгоритма обработки данных, описанного в начале этого раздела, рис. 6.

Рассмотрим многопроцессорную систему с p вычислительными узлами, в которой и вычислительные узлы, и коммуникации между ними отличаются друг от друга:

tci tc, twi tw. Для удобства изложения введем производительность каждого из j j -вычислительных узлов: i = tc (аналог частоты – количество базовых операций в блоке i «В» над данными, выполняемое за единицу времени). Мерой вычислительной неоднородности системы является удельный индекс производительности:

p k k = ; = – суммарная (пиковая) производительность. Выполняется свойство:

k i=p = 1. Для однородной вычислительной системы i = 1/ p, i.

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

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

S( p) =. (6) I / O p tw p p tw i i 1+ + t tc N i=2 k =1 i=ck i Знаменатель (6) является квадратичной формой относительно параметра i,k ki = tw / tc, несмотря на то, что напрямую передачи данных между двумя узлами i k (исключая узел ввода-вывода) не существует.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.