WWW.DISSERS.RU

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

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


Pages:     | 1 || 3 | 4 |   ...   | 6 |

Математическое обеспечение статистической обработки данных имеет большую историю. Существует множество программных систем и математических библиотек (например, StatLib, IMSL), оперирующих моделями случайной величины и (или) функции. Помимо стандартных статистических библиотек, в отдельных прикладных направлениях (например, в гидрометеорологии) разработаны специализированные библиотеки статистического анализа, учитывающие особенности обрабатываемых процессов и специфику данных. В области программного обеспечения МСА обширные результаты были получены в 70-90 гг. XX века. Например, в работе [Cooley, Lohness, 1971], пожалуй, впервые предпринята попытка изложения МСА в рамках единой системы представлений вычислительной линейной алгебры. Главной особенностью перечисленных выше решений является их ориентация на однопроцессорные вычислительные платформы.

Отличительными чертами процесса адаптации алгоритмов МСА для многопроцессорных вычислительных систем являются:

• отсутствие очевидных (trivial) способов распараллеливания ряда традиционных алгоритмов МСА. Этот факт объясним спецификой самой дисциплины, поскольку основной задачей многомерной статистики является формализация статистических связей (желательно – в явной форме), что препятствует параллельной декомпозиции;

• многомерность обрабатываемых данных (связанная с их пространственной, временной, межэлементной, межкомпонентной изменчивостью), приводящая к неоднозначности параллельной агломерации на этапе проектирования параллельной программы;

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

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

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

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

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

Процесс создания математического обеспечения не сводится только к разработке и тестированию программ. Именно потому для его описания недостаточно использовать типовые приемы инженерии программного обеспечения [Соммервил, 2002].

Требования к параллельному математическому обеспечению Идея создания параллельных (многопроцессорных, распределенных) вычислительных систем, сформулированная в 50-х годах XX века, преследовала целью повышение их производительности, не прибегая к принципиальному усовершенствованию элементной базы. Практическая значимость подобных разработок целиком определяется уровнем развития их прикладного математического обеспечения Процесс проектирования параллельного математического обеспечения определяется специфицированием требований к нему. На рис. 2 приведены сгруппированные требования по трем основным категориям:

• как к критической программной системе (работоспособность, безотказность, безопасность, защищенность).

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

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

Требования к Назначение параллельных Требования к критическим системам вычислительных комплексов параллельному ПО Работоспособность Высокопроизводительные Ускорение вычислений Безотказность Высокой готовности Масштабируемость Безопасность Многопоточные Переносимость Защищенность Адаптивность Рис. 2. Требования к параллельному математическому обеспечению.

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

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

Достижение этого показателя связано со следующими проблемами:

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

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

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

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

В классической монографии [Foster, 1995] формулируются следующие этапы архитектурного проектирования параллельных алгоритмов и программ:

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

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

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

Проблема переносимости обычно решается на этапе программной реализации.

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

естественные способы параллельной декомпозиции.

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

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

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

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

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

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

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

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

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

Связывание и Отображение на Декомпозиция агломерация архитектуру Построение Реализация принципа Формулирование количественных конкуренции: выбор естественных моделей наилучшего алгоритма способов производительности по сопоставлению распараллеливания в параметрической моделей форме производительности Выявление и Измерение устранение параметров модели возможного для заданной дисбаланса нагрузки архитектуры в системе Рис. 3. Этапы разработки параллельного алгоритма в рамках естественной парадигмы.

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

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

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

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

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

Для однородной выборки точечная оценка * некоторой вероятностной Z характеристики Z по этому ансамблю может рассматриваться как линейный функционал * * (X ) = (x)dP(x) = (x)dP(x) =. (1) Z n Z Z n n X X n p Следовательно, вся область интегрирования = X в (1) разбивается на p UXk k =независимых частей, над каждой из которых задается функционал. Очевидно, что оценки * суть также случайные величины, однако объем их выборки (равный n количеству процессоров p) существенно меньше, чем исходный.

Декомпозиция на основе принципа перемешивания Декомпозиция на основе принципа перемешивания обобщает принцип декомпозиции по статистическому ансамблю на модель случайной функции (поля) в терминах динамической системы. Сам принцип перемешивания изначально был введен M. Rosenblatt в 1956 г. для описания эргодичности реализаций случайных функций. Он заключается в том, что значения случайной функции ( t ) и ( s ) становятся статистически несвязанными при t - s >> 1. С точки зрения организации параллельных вычислений достаточно длинные фрагменты реализаций случайной функции могут быть синтезированы параллельно. Однако накладные расходы, обусловленные связностью, заключаются в необходимости последующего попарного объединения этих фрагментов посредством специального алгоритма (например, в форме регрессии).

Рассмотрим модель авторегрессии порядка R, описывающую L-мерную T случайную функцию (t) = [1(t),K,L(t)] одной переменной t :

R (t) = (t - k) + (t). (2) k k=Здесь k,, k = 1, R – соответственно матрицы коэффициентов авторегрессии и линейного преобразования (треугольная) вектора некоррелированного гауссова белого шума ( t ) = [1( t ),K, ( t )]T, где L cov(i (t), (t)) = ij, i, j = 1, L.

j Естественный способ декомпозиции основывается на принципе перемешивания, который в данном случае состоит в том, что зависимостью (2) связаны только (R+1) последовательных членов ряда.

Следовательно, отрезки (t), разделенные такими фрагментами, можно рассматривать независимо и моделировать параллельно.

Иллюстрация этого приема приведена на рис. 4.

Объединение фрагментов реализаций (k ) (k +1) (t) и (t), k = 1, p -1, требует i i постановки краевой задачи, которая учитывает регрессионную зависимость, как Рис. 4. Способ параллельной от предыдущих значений декомпозиции модели авторегрессии (k ) (n - j), j =1,2,..., так и последующих (2) на основе принципа (k +1) перемешивания.

( j), j =1,2,...:

Pages:     | 1 || 3 | 4 |   ...   | 6 |






















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

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