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

На правах рукописи

АНТОНОВ Александр Викторович

ЭФФЕКТИВНАЯ ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ НАОСНОВЕ КЛАСТЕРНОЙ ТЕХНОЛОГИИ

Специальность 05.13.15 - Вычислительные машины и системы.

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

ПЕНЗА 2005

Работа выполнена на кафедре «Вычислительная техника» Пензенского государственного университета.

Научный руководитель -Научный консультант -Официальные оппоненты:

кандидат технических наук, профессор Шашков Б. Д.

доктор технических наук, профессор Горбаченко В. И.;

кандидат технических наук, доцент Бикташев Р. А.

доктор технических наук, доцент Князьков В. С.

Ведущая организация - ОАО «Научно-производственное

предприятие "Рубин"» (г. Пенза).

Защита состоится 21 апреля 2005 г., в 14 часов, на заседании диссертационного совета Д 212.186.01 в Пензенском государственном университете по адресу: 440026, г. Пенза, ул. Красная, 40.

С диссертацией можно ознакомиться в библиотеке Пензенского государственного университета.

Автореферат разослан 2005 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Савельев Б. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Параллельное программирование возникло в 1962 г. с изобретением каналов - независимых аппаратных контроллеров. Слово «параллельное» в данном случае означает «происходящее одновременно». К середине 70-х гг. стало ясно, что для преодоления сложности, присущей параллельным программам, необходимо использовать формальные методы их анализа и оценки по различным параметрам.

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

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

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

Поставленная цель достигается решением следующих задач.

1. Анализ вариантов классификации распределенных вычислительных систем и вариантов распараллеливания алгоритмов.

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

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

4. Разработка способа оценки трудоемкости параллельных алгоритмов и параллельного вычислительного процесса на гетерогенных вычислительных системах.

5. Повышение эффективности параллельных вычислений за счет эффективной организации вычислительного процесса на гетерогенных вычислительных системах.

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

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

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

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

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

В результате проведенных исследований достигнуто следующее:

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

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

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

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

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

Реализация и внедрение результатов работы. Диссертация является теоретическим обобщением научно-исследовательских работ, выполненных автором в Пензенском государственном университете. Данная диссертационная работа проводилась по гранту для поддержки научно-исследовательской работы аспирантов высших учебных заведений Минобразования России по теме «Высокопроизводительная вычислительная система повышенной надежности с динамическим распределением ресурсов» (шифр АОЗ-3.16-361). Также результаты диссертации использовались для проведения работ по гранту Минобразования России по теме «Теория и методы организации управления распределенными вычислительными процессами в многопроцессорных вычислительных системах и метакомпьютерных сетях» (шифр Т02-03.3-2476). Результаты работы были использованы в рамках создания «Регионального центра суперкомпьютерных вычислений и телекоммуникационных баз данных коллективного пользования». Также результаты диссертационной работы применялись при организации учебного процесса на кафедре «Вычислительная техника» Пензенского государственного университета.

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

-на XII и XIII международных школах-семинарах «Синтез и сложность управляющих систем» (Пенза, октябрь 2000 и 2001 гг.);

- на XIII научно-технической конференции студентов и профессорско-преподавательского состава Пензенского государственного университета (2002 г.);

-на V и VI международных научно-технических конференциях «Новые информационные технологии и системы» (Пенза, 2002 и 2004 гг.);

- на международном юбилейном симпозиуме «Актуальные проблемы науки и образования» (Пенза, 2003 г.);

- на V и VI всероссийских научно-практических молодежных конференциях «Антикризисное управление в России в современных условиях» (Москва, МГТУ им. Баумана, 2003 и 2004 гг.).

Основные положения, выносимые на защиту:

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

2. Методика построения модели параллельных вычислительных процессов на основе теории марковских процессов, позволяющая проводить оценки их трудоемкости.

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

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

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

Публикации. По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей и 9 тезисов докладов.

Структура и объем работы. Данная диссертационная работа состоит из четырех глав, заключения, списка использованной литературы, включающего 70 наименований, и шести приложений. Объем работы: 130 страниц основного машинописного текста, 22 рисунка, 21 таблица, 49 страниц приложений.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проводится обзор существующих классификаций вычислительных систем. По классификации Флинна параллельные вычислительные системы относятся к классу MIMD (множественный поток команд и множественный поток данных), причем системы могут быть SMP (Shared Memory multiprocessing - системы с разделяемой общей памятью) и МРР (Mass-Parallel Processing - системы с массовым параллелизмом) в зависимости от реализации.

Анализируются варианты построения высокопроизводительных систем с параллельной обработкой данных. Кроме суперкомпьютеров - многопроцессорных станций, построенных по SMP архитектуре, существуют кластерные МРР системы, так называемые «Кластеры рабочих станций» (Clusters Of Workstation - COW). Они строятся на основе обычных персональных компьютеров - узлов системы, объединенных в вычислительный комплекс.

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

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

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

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

На основании проведенного анализа формулируются задачи дальнейшего исследования.

Во второй главе предлагается использование модели недетерминированных цифровых автоматов (НДА) и модели марковских процессов в качестве моделей параллельного вычислительного процесса.

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

Рассматриваются и анализируются возможности модели параллельных алгоритмов на базе НДА, которую удобно представлять в виде графа (рис. 2), причем в зависимости от условий анализа ее можно строить как для всего алгоритма, так и для его основной -серверной - части (рис. 3). Каждое состояние Sx является набором операций программы - подпрограммой. Переходы из состояния в состояние показывают последовательность выполнения различных частей программы. Сигналы образованные сочетанием двоичных элементарных снгнатов, или абстрактные сигналы гу отмечают переход из состояния г в состояние_/. Можно считать, что данные сигналы выдаются по завершении подпрограммы, выполняющейся в состоянии. Автоматная модель позволяет проследить функционирование параллельного алгоритма, но не позволяет проводить временные оценки.

Рис 2 Цифровой автомат, описывающий работу параллельной программы с двумя параллельными ветвями

2:8

50 \и 52 Я ¥Ц 54 V-/ 55 56 УЦ £7

Рис. 3. Цифровой автомат для серверного процесса

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

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

Чем больше параллельных процессов будет участвовать в решении задачи, тем больше будет вершин детерминированного автомата. К детерминированному автомату (рис. 4), полученному из НДА с двумя параллельными ветвями, содержащего 12 состояний (см. рис. 2), можно применить положения теории марковских процессов. Он содержит 20 вершин. Определив вероятности переходов полученного автомата, его можно проанализировать по трудоемкости с использованием системы Кронекера.

Параллельную программу в общем случае можно представить графом, содержащим непараллельную начальную часть из т состояний, параллельную часть, содержащую п параллельных ветвей, и конечную непараллельную часть из / состояний (рис. 5). В нем «Н» -начальная вершина, «К» - конечная, «-» - разветвитель, «+» -соединитель, «ЯХ;х> - некоторые состояния процесса (Я0.х -непараллельная часть), причем число вершин внутри каждой ветви может быть различным где х - номер ветви.

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

Рис. 4. Цифровой автомат после детерминизации

Рис 5 Граф программы с п-параллельными ветвями

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

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

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

На основе системы Кронекера определяется трудоемкость алгоритма. Под трудоемкостью понимается временная сложность, т. е. время, затраченное на выполнение требуемого набора операций, или количество элементарных операций, выпоттятг^пихся и кяжцом состоянии. Она рассчитывается по формуле 0, = > ГДе К - количество условных операций в данной вершине, а п1 - соответственно число попаданий в данную вершину из системы Кронекера.

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

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

£ _ ^РЕАЛЬНАЯ

^МАКСИМАЛЬНАЯ

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

В третьей главе предложены две методики построения моделей параллельного алгоритма на основе теории цифровых автоматов и теории марковских процессов.

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

1. Необходимо синтезировать НДА из алгоритма программы.

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

3. Построить граф серверного процесса с учетом реального алгоритма работы программы.

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

5. Составить систему уравнений Кронекера, по ней определить трудоемкость алгоритма серверного процесса.

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

7. Составить систему Кронекера, по ней определить трудоемкость алгоритма.

Методика построения моделей параллельного алгоритма на основе теории марковских процессов выглядит следующим образом:

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

2. Просчитать количество условных операций в каждой уникальной вершине.

3. Выделить в графе параллельную и непараллельную части.

4. Заменить параллельную часть одним состоянием «Р»

5. Провести анализ непараллельной части алгоритма по трудоемкости: составить матрицу вероятностей переходов, составить систему уравнений Кронекера, записать формулу трудоемкости.

6. Провести анализ параллельной части по трудоемкости: выбрать различные ветви для проведения анализа, составить матрицы вероятностей переходов, составить систему уравнений Кронекера, записать формулы трудоемкости и рассчитать трудоемкости.

7. Выбрать одну из ветвей для анализа в зависимости от его условий (по максимальной, средней или минимальной трудоемкости).

8. Подставить уравнения из системы для выбранной параллельной ветви вместо уравнения для состояния «Р» в системе Кронекера.

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

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

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

2. Вычислительная параллельная часть - решение задачи.

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

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

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

1. Построить модель параллельного алгоритма на основе теории марковских процессов.

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

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

4. Рассчитать показатель эффективности и определить эффективность программы.

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

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

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

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

каждого узла - число узлов в вычислительной

N

,=\ Лн

системе. Общее число параллельных процессов п V-

/»I

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

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

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

1. Определить производительность всех вычислительных узлов по некоторой тестовой программе.

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

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

4. Определить рекомендуемое число параллельных процессов.

5. Задать в настройках системы рекомендуемое число параллельных ветвей.

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

РВС MathNet построена по технологии Beowulf. Beowulf кластер -это многомашинная однородная или неоднородная вычислительная система, построенная путем объединения некоторого количества компьютеров (вычислительных узлов) через локальную или глобальную сеть, причем один компьютер является выделенным сервером: на нем запускается программа вычислений и получается результат, узлы кластера имеют постоянную или временную связь с сервером для получения программного кода и/или данных для проведения вычислений и отправки результатов работы.

Структура ПК РВС MathNet (рис. 6) может динамически изменяться (меняется число клиентских узлов), и при достаточно большом количестве параллельных подзадач в алгоритме есть возможность реализовать загрузку узлов, близкую к равномерной. Вычислительный узел, с большей производительностью, решит больше подзадач, чем узел с меньшей.

Рис. 6. Структура ПК «РВС "Ма&КеГ»

Разработана технология написания программ для ПК «РВС "МаШ№1"», программа для которой должна представлять собой код на языке С++, содержащий определенные функции:

— Initialize - серверная функция - выполняет ввод исходных данных, разбиение задачи на подзадачи, сборку и выдачу результата;

— Calculate - клиентская функция - вычисляет подзадачу.

Данные для каждой подзадачи и результаты их выполнения должны передаваться в специальном буфере, который представляет собой область памяти с данными любых типов. Программа для системы MathNet выполняется в виде отдельного независимого модуля, в случае использования ОС Windows - это DLL (Dynamic Link Library) -динамически подключаемая библиотека.

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

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

При реализации для MPI

® = W + tlNITPROC + (" + / RECV +(8 + ANUM + n)s +

при реализации для ПК «РВС "MathNet"»

где п - число ветвей; S - время выполнения одной операции сложения; М - время выполнения одной операции умножения; D -время выполнения одной операции деления; fx - время вычисления функции; NUM- количество интервалов; {¡^¡т - время инициализации программы; - время инициализации параллельного процесса;

- время передачи одного набора данных; - время

выполнения завершающих действий.

Для алгоритма программы умножения матриц формулы трудоемкости выглядят следующим образом.

При обычной реализации на MPI кластере

© = ©S0 + ©Si + ®sk + (numproc - 1)(©S2 + &S5 ) + ©S3 + str @SA,

где ©a - трудоемкость соответствующего состояния программы, Str - число строк в матрице; питргос - количество параллельных ветвей

При реализации на ПК «РВС "MathNet"»

где ®sehd/recv - трудоемкость передачи одной строки матрицы, а ©СШ.С - трудоемкость вычисления одной строки матрицы, str - число строк в матрице; ©дет - трудоемкость инициализации программы, - трудоемкость инициализации пользовательской части программы; ©userend - трудоемкость завершающей пользовательской части; - трудоемкость завершения программы

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

Результаты, полученные при расчетах по приведенным выше формулам, представлены ниже в виде графиков: для алгоритма вычисления интеграла по методу Симпсона (рис. 7);

Рис 7 Зависимость времени выполнения программы на основе алгоритма вычисления интеграла методом Симпсона от количества узлов

для алгоритма умножения матриц (рис 8)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Количество узлов

MPI обычный anroptmw ■♦■MPIусовершенствованный алгоритм MathNet

Рис 8 Зависимость времени выполнения программы на основе алгоритма умножения матриц от количества узлов

Данные, порученные в результате тестовых запусков программ, приведены ниже в виде графиков. Для алгоритма вычисления интеграла методом Симпсона - рис. 9.

I 0 —1—г—|—|—|—|—|—|—|—|—|—|—I—|—|—|—(—1—I—I—I—г—i—I

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Количество процессов

MPI обычный алгоритм MPI усовершенствованный алгоритм —àr- MathNct

Рис 9 Результаты замеров времени для программы на основе алгоритма вычисления интеграла методом Симпсона

Исходя из полученных данных, видно, что расчетные данные на практике подтвердились и эффективность алгоритма была повышена на 22% Скачки на графике объясняются тем, что в этих точках в кластере задействован более медленный узел Это может быть как подключение более медленного компьютера (7-й узел) или запуск на одном узле более одного процесса (13-й и 19-й узел).

Для алгоритма умножения матриц - рис. 10.

! 60

to

5

123456789 10

Количество процессов I

I_МРГ обычный алгоритм MPI усовершенствованный алгоритм Ma'hNt'î

Рис. 10. Результаты замеров времени для программа: на основе алгоритма умножения матриц

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

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

В заключении перечислены основные результаты работы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

5. Разработана вычислительная система кластерного типа -МаШ№1 - для эффективной организации параллельных распределенных вычислений с доступным пользовательским интерфейсом и простой, по сравнению с другими системами, технологией программирования.

6. Разработано программное обеспечение для проектирования и верификации алгоритмов цифровых устройств обработки информации - «Система описания, моделирования, преобразования алгоритмов» (СОМПА).

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Подсистема синтеза и верификации алгоритмов, заданных на языке регулярных выражений алгебры событий / Н. П. Вашкевич, О. С. Виноградов, Е. И. Калиниченко, А. В. Антонов, А. Н. Токарев // Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. науч. тр. - Пенза: Изд-во Пенз. гос. ун-та, 1998.-Вып. 25.-С. 52-54.

2. Антонов А. В. Инструментальная система проектирования и верификации алгоритмов цифровых устройств обработки информации / А. В. Антонов, А. Н. Токарев // Студент и научно-технический прогресс: Материалы XXXVIII Междунар. науч. студенческой конф. -Новосибирск: Изд-во НГУ, 2000. - С. 67-68.

3. Антонов А. В. Инструментальная подсистема автоматизации проектирования управляющей и операционной частей цифровых

устройств / А. В. Антонов, А. Н. Токарев // Тез. докл. VIII Междунар. студенческой школы-семинара (г. Судак). - М.: Изд-во МГИЭМ, 2000.-С. 184-185.

4. Антонов А. В. Построение и анализ кластерной вычислительной системы на базе ПЭВМ, объединенных сетью «Fast Ethernet» / А. В. Антонов, А. Н. Токарев // Синтез и сложность управляющих систем: Материалы XII Междунар. школы-семинара (г. Пенза, 15-21 октября 2001 г.).Ч.1.-М.:Изд-воМГУ,2001.-С. 13-17.

5. АНТОНОВА. В. Принципы организации параллельной вычислительной системы с доступом через Интернет / А. В. Антонов, А. Н. Токарев // Синтез и сложность управляющих систем: Материалы XIII Междунар. школы-семинара» (г. Пенза, 14-20 октября 2002 г.) Ч. I / Под общ. ред. чл.-корр. РАН О. Б. Лупанова. - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С. 21-25.

6. Программное обеспечение вычислительного комплекса верх-неего уровня АСУ ТП. Интерфейс сетевого взаимодействия / А. В. Антонов, Н. П. Вашкевич, А. В. Никишин, А. Н. Токарев, Н. А. Голдуев // Новые информационные технологии и системы: Тр. V Междунар. науч.-техн. конф. - Пенза: Изд-во Пенз. гос. ун-та, 2002. - С. 45-49.

7. Антонов А. В. Структура распределенной вычислительной системы и организация удаленного доступа к ней / А. В. Антонов, А. Н. Токарев // Новые информационные технологии и системы: Тр. V Междунар. науч.-техн. конф. - Пенза: Изд-во Пенз. гос. ун-та, 2002.-С. 100-103.

8. Высокопроизводительная вычислительная система повышенной надежности с динамическим распределением ресурсов / А. В. Антонов, А. В. Дубравин, А. Н. Токарев, Б. Д. Шашков // Актуальные проблемы науки и образования: Тр. Междунар. юбилейного симп. -Пенза: Изд-во Пенз гос. ун-та, 2003. - С. 385-387.

9. Антонов А. В. Параллельное программирование в системе распределенных вычислений «MathNet» // Антикризисное управление в России в современных условиях: Материалы V Всерос. науч.-практ. молодежной конф. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. -С. 25-26.

10. Антонов А. В. Модель параллельной программы / А. В. Антонов, Б. Д. Шашков // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2004. - № 2. - С. 87-95.

11. Антонов А. В. Марковская модель организации параллельных вычислений в распределенной вычислительной системе / А. В. Антонов, Б. Д. Шашков // Новые информационные технологии и системы: Тр. VI Междунар. науч.-техн. конф. - Пенза: Изд-во Пенз. гос. ун-та, 2004. - С. 69-78.

12. Антонов А. В. Оценка эффективности параллельных алгоритмов // Антикризисное управление в России в современных условиях: Материалы VI Всерос. науч.-практ. молодежной конф. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2004. - С. 21-22.

13. Программный комплекс «Система распределенных вычислений "МаШ№1"» / А. В. Антонов, А. В. Дубравин, А. Н. Токарев, Б. Д. Шашков // Вычислительные системы и технологии обработки информации: Сб. науч. тр. - Пенза: Изд-во Пенз. гос. ун-та, 2005. -Вып. 3.-С. 90-100.

14. Антонов А. В. Программный комплекс «Система распределенных вычислений "МаШ№1"». Параллельное программирование // Вычислительные системы и технологии обработки информации: Сб. науч. тр. - Пенза: Изд-во Пенз. гос. ун-та, 2005. - Вып. 3. -С. 101-110.

Антонов Александр Викторович

Эффективная организация параллельных распределенных вычислений на основе кластерной технологии

Специальность 05 13 15 - Вычислительные машины и системы Специальность 05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Редактор Т Н Судовчихина Технический редактор Н А Вьялкова

Корректор Н А Сидельникова Компьютерная верстка С Л Черновой

ИД №06494 от 26 12 01 Сдано в производство 17 03 05 Формат 60х84'/16 Бумага писчая Печать офсетная Уел печ л 1,39 Заказ № 161 Тираж 100

Издательство Пензенского государственного университета 440026, Пенза, Красная, 40

05. il - 95. /3

!fU> 48

Введение.

Глава 1. Анализ моделей вычислений, вычислительных систем и способов повышения их эффективности.

1.1. Классификация вычислительных систем.

1.1.1. Классификация Флинна.

1.1.2. Классификация Хокни.

1.1.3. Классификация 8МР/МРР.

1.2. Кластеры рабочих станций.

1.2.1. Технология построения кластерных вычислительных систем.

1.2.2. Организация параллельных вычислений.

1.3. Распараллеливание программ.

1.4. Модели параллельных вычислительных процессов.

1.4.1. Использование модели на основе теории сетей Петри.

1.4.2. Использование логической модели параллельных программ.

1.4.3. Использование модели конечных недетерминированных цифровых автоматов.

1.4.4. Использование модели марковских процессов.

1.5. Эффективность параллельных вычислений.

1.6. Выводы по главе.

Глава 2. Модели параллельного вычислительного процесса.

2.1. Основные понятия.

2.2. Алгоритм параллельной программы.

2.3. Автоматная модель параллельной программы.

2.4. Марковская модель параллельного алгоритма на основе цифрового автомата.

2.4.1. Применимость марковской модели для описания параллельного алгоритма.

2.4.2. Переход от модели недетерминированного цифрового автомата к модели марковских процессов.

2.5. Марковская модель работы параллельного алгоритма.

2.5.1. Анализ непараллельной (основной) части программы.

2.5.2. Анализ параллельных ветвей.

2.5.3. Анализ трудоемкости.

2.6. Выводы по главе.

Глава 3. Повышение эффективности параллельных вычислений и параллельное программирование.

3.1. Эффективность параллельных вычислений.

3.1.1. Методики построения моделей параллельного алгоритма.

3.1.2. Эффективность параллельного алгоритма.

3.1.3. Эффективная организация вычислительной системы.

3.1.4. Повышение эффективности параллельных вычислений.

3.2. Построение высокопроизводительной вычислительной системы на основе кластерной технологии.

3.2.1. Программный комплекс «Распределенная вычислительная система «MathNet».

3.2.2. Организация доступа к кластеру.

3.3. Технология параллельного программирования.

3.3.1. Технология написания параллельной программы для ПК «РВС «MathNet».

3.3.2. Алгоритм параллельной программы для ПК «РВС «MathNet».

3.4. Выводы по главе.

Глава 4. Анализ параллельных алгоритмов.

4.1. Аналитический анализ алгоритмов.

4.1.1. Анализ алгоритма программы вычисления интеграла методом Симпсона для MPI.

4.1.2. Анализ алгоритма программы вычисления интеграла методом Симпсона для ПК «РВС «MathNet».

4.1.3. Анализ алгоритм программы умножения матриц для MPI.

4.1.4. Анализ алгоритма программы умножения матриц для ПК «РВС

MathNet».

4.2. Анализ полученных результатов.

4.2.1. Результаты тестирования программы вычисления интеграла методом Симпсона.

4.2.2. Результаты тестирования программы умножение матриц.

4.3. Выводы по главе.

Параллельное программирование возникло в 1962г. с изобретением каналов - независимых аппаратных контроллеров, позволяющих центральному процессору выполнять новую прикладную программу одновременно с операциями ввода-вывода других (приостановленных) программ. Слово «параллельное» в данном случае означает «происходящее одновременно». В конце 60-х годов были созданы многопроцессорные машины, что поставило новые задачи и дало новые возможности программистам.

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

К середине 70-х годов стало ясно, что для преодоления сложности, присущей параллельным программам, необходимо использовать формальные методы их анализа и оценки по различным параметрам [15]. На рубеже 70-х и 80-х годов появились компьютерные сети. Для глобальных сетей стандартом стала сеть Arpanet, а для локальных - Ethernet. Сети привели к росту распределенного программирования, которое стало основным направлением работ в 80-х и, особенно, в 90-х годах. Суть распределенного программирования состоит в организации взаимодействия процессов путем передачи сообщений, а не записи и чтения разделяемых переменных.

Разрабатываемые подходы использования компьютеров основаны на тезисе: компьютер — это инструмент познания, с помощью которого добывают новую информацию об исследуемом объекте или явлении [16]. Следовательно, квалифицированный пользователь должен владеть современной методологией познания - моделированием. Моделирование - это не только конструирование объекта познания, но и метод познания. Моделирование есть методология работы, эффективность которой раскрывается лишь при высокой квалификации специалистов и при их свободном владении современными средствами формализации - логикой и математикой.

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

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

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

В работе В. Гергеля и Р. Стронгина (Нижегородский государственный университет им. Лобачевского) предлагается использовать модель программы в виде сетей Петри; в работе С. Востокина (Самарский государственный аэрокосмический университет) предлагается логическая модель, позволяющая описывать функционирование параллельных процессов. Данные модели не обладают такими широкими возможностями, как, например, модель марковских процессов. А марковские цепи не допускают наличия совместных состояний. Один из возможных вариантов — использование модели недетерминированных цифровых автоматов, которая подробно рассмотрена в работах Н.П. Вашкевича (Пензенский государственный университет). Применение их более перспективно совместно с другими моделями, например с моделью марковских процессов.

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

Поставленная цель достигается решением следующих задач:

1. Анализ вариантов классификации распределенных вычислительных систем и вариантов распараллеливания алгоритмов.

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

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

4. Разработка способа оценки трудоемкости параллельных алгоритмов и параллельного вычислительного процесса на гетерогенных вычислительных системах.

5. Повышение эффективности параллельных вычислений за счет эффективной организации вычислительного процесса на гетерогенной вычислительной системе.

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

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

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

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

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

В результате проведенных исследований было предложено следующее:

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

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

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

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

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

Реализация и внедрение результатов работы. Диссертация является теоретическим обобщением научно-исследовательских работ, выполненных автором в Пензенском государственном университете. Данная диссертационная работа проводилась по гранту для поддержки научно-исследовательской работы аспирантов высших учебных заведений Минобразования России по теме «Высокопроизводительная вычислительная система повышенной надежности с динамическим распределением ресурсов» (шифр АОЗ-3.16-361). Результаты диссертации использовались также для проведения работ по гранту Минобразования России на тему «Теория и методы организации управления распределенными вычислительными процессами в многопроцессорных вычислительных системах и метакомпьютерных сетях» (шифр Т02-03.3-2476). Результаты работы были использованы в рамках создания «Регионального центра суперкомпьютерных вычислений и телекоммуникационных баз данных коллективного пользования». Результаты диссертационной работы применялись при организации учебного процесса на кафедре «Вычислительная техника» Пензенского государственного университета.

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

- XII и XIII международная школы-семинары «Синтез и сложность управляющих систем» (Пенза, октябрь 2001 и 2000гг);

- XIII научно-технической конференция студентов и профессорско-преподавательского состава Пензенского государственного университета. (Пенза, 2002г.);

- V и VI международные научно-технические конференции «Новые информационные технологии и системы» (Пенза, 2002 и 2004 гг.);

- Международный юбилейный симпозиум «Актуальные проблемы науки и образования» (Пенза, 2003 г.);

- V и VI всероссийские научно-практические молодежные конференции «Антикризисное управление в России в современных условиях» (Москва, МГТУ им. Н.Э. Баумана, 2003 и 2004гг).

Публикации. По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей и 9 тезисов докладов.

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

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

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

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

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

В заключении перечислены основные результаты работы.

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

Основные положения, выносимые на защиту:

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

2. Методика построения модели параллельных алгоритмов на основе теории марковских процессов, позволяющая проводить оценки алгоритмов по трудоемкости.

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

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

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

4.3. Выводы по главе

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

Основные полученные результаты:

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

2. По полученным алгоритмам были созданы программы с использованием систем MPI и MathNet.

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

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

ЗАКЛЮЧЕНИЕ

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

Получены следующие основные результаты:

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

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

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

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

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

6. Разработано программное обеспечение для проектирования и верификации алгоритмов цифровых устройств обработки информации -«Система описания, моделирования, преобразования алгоритмов» (СОМПА).

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

1. Антонов А. В. Параллельное программирование в системе распределенных вычислений «MathNet» // Антикризисное управление в России в современных условиях: Материалы V Всерос. науч.-практ. молодежной конф. М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. - С. 25-26.

2. Ю.Антонов А. В. Модель параллельной программы / А. В. Антонов, Б. Д. Шашков // Известия высших учебных заведений. Поволжский регион. Технические науки. 2004. - № 2. - С. 87-95

3. Антонов А. В. Оценка эффективности параллельных алгоритмов // Антикризисное управление в России в современных условиях: Материалы VI Всерос. науч.-практ. молодежной конф. М.: Изд-во МГТУ им. Н. Э. Баумана, 2004.-С. 21-22.

4. Антонов А. В. Программный комплекс «Система распределенныхвычислений "MathNet"». Параллельное программирование // Вычислительные системы и технологии обработки информации: Сб. науч. тр Пенза: Изд-во Пенз. гос. ун-та, 2005. - Вып. 3. - С. 101-110

5. ЭндрюсГ. Р. Основы многопоточного, параллельного и распределенного программирования.: Пер. с англ. -М.: Издательский дом «Вильяме», 2003. -512 с.

6. Бочаров Н. В. Технологии и техника параллельного программирования Казань: Институт механики и машиностроения Казанского научного центра Российской Академии наук, 2003. - 340 с.

7. Воеводин В. В., Параллельные вычисления / В.В.Воеводин, Вл. В. Воеводин СПб.: БХВ-Петербург, 2002. - 608 с.

8. Flynn М. Very high-speed computing system // Proc. IEEE. 1966. -N 54. P.1901-1909.

9. FlynnM. Some Computer Organisations and Their Effectiveness // IEEE Transactions on Computers. 1972. - V.21. -N 9. P.948-960

10. HockneyR. Parallel Computers: Architecture and Performance // Proc. of Int. Conf. Parallel Computing'85. 1986. -P.33-69.

11. HockneyR. Classification and Evaluation of Parallel Computer Systems // Lecture Notes in Computer Science. 1987. -N 295. - P. 13-25.

12. Бикташев P. А. Многопроцессорные системы. Архитектура, топология, анализ производительности: Учебное пособие. / Р. А. Бикташев, В. С. Князьков Пенза: Изд-во Пенз. гос. ун-та, 2003. — 126 с.

13. Князьков В. С. Архитектура параллельных вычислительных систем / В. С. Князьков, Р. А. Бикташев Пенза: Изд-во Пенз. политехи, ин-та, 1993. -166 с.

14. Комолкин А. В., Программирование для высокопроизводительных ЭВМ / А. В. Комолкин, С. А. Немнюгин Электронный ресурс.: http://www.hpc.nw.ru/KOI/COURSES/HPC/index.html Загл. с экрана

15. Ремизов К. А. Исследование и анализ эффективности работы кластерных систем типа клиент-сервер с неразделяемыми серверамиприложений Электронный ресурс.:http://www.uran.donetsk.ua/~masters/2003/iVti/remizov/diss/index.htm Загл. с экрана 2003. .

16. Владимиров Д. Кластерная система Condor // Открытые системы — 2000. -№7-8.

17. Волков Д. Дума о миграции // Открытые системы 1999. - №4.

18. Описание решения Cluster 1600 Электронный ресурс.: http://www.ibm.com/ru/eserver/pseries/cluster/1600desc.html Загл. с экрана

19. Radajewski J., Eadline D. Beowulf HO WTO

20. Ashton D. User's Guide for MPICH, a Portable Implementation of MPI / D. Ashton, W. Gropp, E. Lusk.

21. Коржов В. Объединяй и властвуй // Сети. 2003. - №04-05

22. Черняк Л. Общая шина предприятия // Открытые системы.- 2003.04.

23. Foster I. Globus: A Metacomputing Infrastructure Toolkit / I. Foster., C. Kesselman // Intl J. Supercomputer Applications, 11, 1997.

24. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment / Foster I., Geisler J., Nickless W., Smith W., Tuecke S.// Proc. 5th IEEE Symposium on High Performance Distributed Computing 1997.-Pp. 562-571

25. Воеводин В. Суперкомпьютер на выходные / В.Воеводин, М. Филамофитский // Открытые системы.- 2003. № 5.

26. Соколенко П. Т. Заметки о технологии Hyper-Threading. Электронный ресурс.: http://www.macro.aaanet.ru/apnd9.html Загл. с экрана

27. Шоу А. Логическое проектирование операционных систем. М.:1. Мир, 1981.-360 с.

28. Гергель В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие / В. П. Гергель, Р. Г. Стронгин Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003.-184 с.

29. Малышкин В. Э. Основы параллельных вычислений: Учеб. пособие. Часть 1. Новосибирск: Изд-во НГТУ, 1998. - 104 с.

30. Вашкевич Н. П. Недетерминированные автоматы и их использование для синтеза систем управления / Н. П. Вашкевич, С. Н. Вашкевич Пенза: Изд. Пенз. гос. техн. ун-та, 1996. - 88 с.

31. Вашкевич Н. П. Синтез и отладка алгоритмов функционирования цифровых устройств управления: Учеб. пособие. / Н. П. Вашкевич, Е. И. Калиниченко — Пенза: Изд-во Пенз. гос. ун-та, 2001. 44 с.

32. Вашкевич Н. П. Синтез микропрограммных управляющих автоматов: Учебное пособие Пенза: Изд-во Пенз. политехи, ин-та, 1990. - 56 с.

33. ГлушковВ. М. Введение в кибернетику Киев: Изд. Академии наук Украинской ССР, 1964. - 324 с.

34. Гладкий B.C. Вероятностные вычислительные модели. М.: Наука, 1973.-300 с.

35. Немченко А. В. Параллельные цифровые автоматы подготовка к синтезу Электронный ресурс.: http://www.softcraft.ru/auto/etc/avn/avn2.shtml — Загл. с экрана

36. Вашкевич Н. П. Недетерминированные автоматы в проектировании систем параллельной обработки. Учеб. пособие Пенза: Изд-во Пенз. гос. унта, 2004. - 280 с.

37. Вентцель Е. С. Исследование операций М.: Советское радио, 1972. —552 с.

38. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 272 с.

39. Марков Н. Г. Моделирование параллельного программного обеспечения с использованием PS-сетей. / Н. Г. Марков, Е. А. Мирошниченко,

40. A. В. Сарайкин // Программирование. 1995 № 5. - С. 24-32.

41. Основы теории вычислительных систем./ Под ред. Майорова С. А. — М.: Высшая школа, 1978.-408 с.

42. Ларионов А. М. Вычислительные комплексы, системы и сети: учебник для вузов / А. М. Ларионов, С. А. Майоров, Г. И. Новиков — Л.: Энергоатомиздат. Ленингр. отд., 1987.-288 с.

43. Бикташев Р. А. Оценка трудоемкости параллельных алгоритмов // Новые информационные технологии и системы: Труды VI Междунар. науч.-техн. конф. — Пенза: Изд-во Пенз. гос. ун-та, 2004. С. 50-54

44. Карцев В. А. Вычислительные системы и синхронная арифметика /

45. B. А. Карцев, В. А. Брик -М.: Радио и связь, 1981. 360 с.

46. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ: Пер. с англ. / Под. ред. Я. Ковалика. М.: Радио и связь, 1988. - 432 с.

47. Богданов A.B. Параллельное программирование и использование прикладного ПО на параллельных суперкомпьютерах // Курсы лекций и методические материалы. СПб.: Изд-во СПб. гос. тех. ун-та, 2001. - 165 с.

48. Amdahl G. Validity of the single-processor approach to achieving large-scale computing capabilities // Proc. 1967 AFIPS Conf., AFIPS Press. 1967.

49. Букатов А. А. Программирование многопроцессорных вычислительных систем / А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Ростов-на-Дону: Изд-во ООО «ЦВВР», 2003. - 244 с.

50. Антонов A.C. Под законом Амдала// Компьютера. 2002г. №5 62.3убинский А. Кластеры - о главном // Компьютерное обозрение.2002г.-№18-19,

51. Антонов А. С. Введение в параллельные вычисления: Метод, пособие. М.: Изд-во МГУ, 2002. - 46 с.

52. Foster I. Designing and Building Parallel Programs 1995.

53. Lowenthal D., James M. Run-Time Selection of Block Size in Pipelined Parallel Programs. The University of Georgia 2000.

54. Большой Энциклопедический словарь Электронный ресурс.: http://dic.academic.ru/library.nsf/enc3p/

55. Толковый словарь Ушакова Электронный ресурс.: http://dic.academic.ru/library.nsfushakov/

56. Князьков В. С. Об одном подходе к оценке эффективности организации параллельных вычислений // Новые информационные технологии и системы: Тр. VI Междунар. науч.-техн. конф. Пенза: Изд-во Пенз. гос. унта, 2004.-С. 101-115.

57. Усачев Ю. Е. ВМ, сети и системы телекоммуникаций Электронный ресурс.: http://salink.bashnet.ru/Inet/newbook/ekonominform/vmsl/vms.htm Загл. с экрана

58. Шпаковский Г. И. Программирование для многопроцессорных систем в стандарте MPI: Пособие / Г. И Шпаковский, Н. В Серикова. Мн.: Изд-во БГУ, 2002. — 96 с.

59. Удаленный коллективный доступ к многопроцессорной системе / А. Б. Вавренюк, Л.Д.Забродин, В.В.Макаров, А.Н.Никитин, Е. В.Чепин -М.: Изд-во Моск. гос. инж.-физ. инст-та, 2000. 68 с.

60. Воеводин В. В., Матрицы и вычисления / В.В.Воеводин, Ю. А. Кузнецов -М.: Наука, 1984г. 312 с.