WWW.DISSERS.RU

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

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


Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |
А.В. Бухановский, С.В. Иванов Проектирование прикладного математического обеспечения параллельной обработки данных Учебные материалы Зимней школы-практикума «Технологии параллельного программирования 2006» Санкт-Петербург - Нижний Новгород, 2006 Учебные материалы подготовлены сотрудниками лаборатории параллельного математического обеспечения Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУИТМО) Александром Валерьевичем Бухановским (профессором кафедры информационных технологий, руководителем лаборатории; e-mail: avb_mail@mail.ru) и Сергеем Владимировичем Ивановым (младшим научным сотрудником; e-mail: zarva@hotbox.ru). В данном курсе обобщен практический опыт, полученный авторами в ходе реализации ряда проектов в области разработки параллельного математического обеспечения статистической обработки больших объемов гидрометеорологической, биомедицинской и технической информации.

Авторы искренне благодарны старшему научному сотруднику лаборатории параллельного математического обеспечения СПбГУИТМО А.Е. Луценко за первичное редактирование рукописи.

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

© А.В. Бухановский, С.В. Иванов (2006) 1 От авторов (вместо введения)……………………………………………………………. 2 Раздел 1. Предметная область………………………………………………………….. 4 Обработка данных с целью извлечения знаний………………………………………… 4 Математическое обеспечение обработки данных………………………………………. 6 Требования к параллельному математическому обеспечению………………………... 7 Раздел 2. Декомпозиция алгоритмов………………………………………………...... 10 Естественные способы параллельной декомпозиции…………………………………... 10 Декомпозиция по статистическому ансамблю………………………………………….. 12 Декомпозиция на основе принципа перемешивания…………………………………… Декомпозиция по индексирующей переменной………………………………………... Раздел 3. Анализ производительности………………………………………………... Модель функционирования параллельной программы обработки данных…………... Ускорение и эффективность параллельных программ…………………………………. Модели производительности для MPP-систем…………………………………………. Можно ли описать производительность в GRID ……………………………………… Пример: расчет ковариационной функции……………………………………………… Раздел 4. Отображение на архитектуру……………………………………………….. Статическая оптимизация и принцип конкуренции……………………………………. Динамическая оптимизация. Балансировка нагрузки………………………………...... Адаптация параллельного математического обеспечения под особенности программно-аппаратных комплексов………………………………... Раздел 5. Программная реализация…………………………………………………… Заключение………………………………………………………………………………… Литература по параллельным вычислениям…………………………………………….. Цитируемая литература…………………………………………………………………... Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года… (редактор издательства Prentice Hall, 1957г) От авторов (вместо введения) Что появилось первым – курица или яйцо Что является двигателем научного прогресса – возможность корректно ставить сложные вычислительные задачи, или наличие адекватных вычислительных мощностей для их решения Мы были далеко не первыми, когда задали себе этот вопрос в процессе подготовки данных учебных материалов. Что действительно нового мы можем внести в столь востребованное и динамично развивающееся направление, как параллельные вычисления, по сравнению с многочисленными российскими и зарубежными учебными курсами В нашем восприятии параллельные вычисления не являются самоцелью или собственно объектом изучения. Позиционируя себя, как специалисты по статистической обработке данных, мы прагматично подходим к ним как к возможному (но не единственному) инструменту, позволяющему получать вычислительные результаты там, где традиционные подходы оказались неприемлемы или неэффективны.

Пожалуй, впервые серьезно задуматься о возможностях использования этого аппарата нам пришлось в 1998 г. на Международной конференции «Экспедиционные исследования Мирового океана», проходившей под эгидой Росгидромета в г. Обнинск.

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

В основе ЕСИМО была использована новая на то время концепция получения информационных массивов характеристик океана и атмосферы с помощью расчетов по гидродинамическим моделям [Мирзоев и др., 1999]. Результатом таких модельных расчетов являются пространственно (x, y, z) – временные (t) поля (охватывающие весь Земной шар); их непрерывная длительность составляет десятки лет, а временной шаг, с которым выполняются расчеты – от 1 часа до 15 минут. В отличие от традиционных суперкомпьютерных задач прогноза погоды, конечным результатом которых является получение конкретной пространственной картины в фиксированный момент времени, в данном случае постановка задачи осложняется тем, что объектом изучения является весь ансамбль возможных реализаций, характеризующий климатическую изменчивость гидрометеорологических характеристик, с учетом их мелкомасштабных, синоптических, сезонных и межгодовых вариаций.



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

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

В 2002-2004 г. мы смогли успешно адаптировать его в совершенно неожиданной области – при создании кардиологической экспертной системы нового поколения на основе суперкомпьютеров семейства «СКИФ» [Бухановский и др., 2003] в рамках Целевой программы «Разработка и освоение в серийном производстве семейства высокопроизводительных вычислительных систем с параллельной архитектурой (суперкомпьютеров) и создание прикладных программно-аппаратных комплексов на их основе». С 2003 г. мы принимаем участие в Международном проекте, курируемом университетом г. Амстердам, по разработке другой медицинской системы - экспертной системы диагностики ВИЧ-1, функционирующей в распределенной вычислительной среде GRID. Объектом обработки являются информационные массивы вирусной ДНК глобальной (всемирной) популяции ВИЧ-1 [Sloot et al., 2005].

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

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

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

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

Формой представления знаний является статистическая модель. В качестве основного аппарата ее идентификации рассматривается многомерный статистический анализ, а в качестве аппарата определения достоверности полученных знаний – методы статистического моделирования (Монте-Карло).

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

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

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





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

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

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

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

Базовым инструментом идентификации статистических моделей DM является многомерный статистический анализ (МСА). Классический МСА детально разработан и систематизирован во второй половине ХХ века для модели многомерной случайной величины. Он предназначен для решения трех основных задач: снижения мерности исходной информации, установления зависимости и выявления неоднородности.

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

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

Метод Монте-Карло лежит в основе такой дисциплины, как вычислительная статистика. В 1981 году R. Rubinstein достаточно четко сформулировал так называемый регенеративный подход к статистической обработке данных (который на эвристическом уровне всемирно применялся еще в 50-60 гг. XX века). Его сущность состоит в том, что результатом статистического анализа выборки заданного объема является статистическая (имитационная) модель – форма записи случайного явления (события, величины, функции), позволяющая методом Монте-Карло воспроизвести ансамбль реализаций, аналогичный исходному в смысле вероятностного описания. Это позволяет свести многие трудноформализуемые и ресурсоемкие задачи статистического анализа к обработке модельных выборок большого объема.

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

Классический МСА подробно описан в монографиях [Бартлетт, 1958;

Андерсон, 1963, Рао, 1968]. С основами метода Монте-Карло и способами построения статистических моделей можно познакомиться в монографиях [Соболь, 1973; Ермаков, Михайлов, 1982; Шалыгин, Палагин, 1986].

Математическое обеспечение обработки данных Как и понятие «обработка данных», понятие математического обеспечения (МО) в настоящее время тоже имеет разные, порой – очень изощренные толкования. Например, в начале 90-х годов в Ленинградском кораблестроительном институте (ныне – СанктПетербургском государственном морском техническом университете) читался курс «Математическое обеспечение ЭВМ», в котором слушатели учились пользоваться командами MS-DOS, файловым менеджером Norton Commander и архиватором ARJ.

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

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

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










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

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