Содержание к диссертации
Стр.
Аннотация работы 5
Введение 6
Глава 1. Обзор языков и сред параллельного программирования 12
Введение 12
Примитивы параллельного программирования 12
Распараллеливание последовательных программ 13
Модели и средства описания параллелизма на процессном уровне 15
Сети Петри 16
MPI,PVM и Нити 18
MPI 19
PVM и его сравнение с MPI 23
Нити 25
1.3.3. Другие проблемно-ориентированные языки и средства
параллельного программирования 27
DVM 28
НРС++ :. 30
HPF 32
Linda 33
МС# 33
Mentat 35
Mosix 36
mpC 37
Функциональное параллельное программирование 38
Сравнение языков и сред параллельного программирования 42
Заключение 45
Глава 2. Граф-схемное потоковое параллельное программирование и
его сравнение с MPI 47
Введение 47
2.1. Язык граф-схемного потокового параллельного программирования ... 48
Структура и интерпретация программы на ЯГСІШП 48
Операционная семантика 52
Примеры построения программ на ЯГСППП 56
Формальная операционная семантика ЯГСППП 64
Сравнительный анализ выразительных возможностей МРІ и і
ЯГСППП 67
Заключение 69
Глава 3. Методы, технологии и инструментальные среды
параллельного программирования 71
Введение 71
Методы и технологии разработки параллельных программ 72
Технологии и инструментальные среды параллельного
программирования 78
Заключение 90
Глава 4. Исследование эффективности выполнения параллельных
программ на кластере МЭИ (ТУ) 91
Ведение 91
Кластерные ВС и их технические характеристики 91
О кластере МЭИ (ТУ) и его характеристиках 93
Критерии и основные параметры эффективности выполнения параллельных программ на кластерах 94
Стандартные смеси для проверки эффективности работы ВС 97
Известные тесты для кластеров 98
Исследование эффективности кластера МЭИ (ТУ) на тесте HPL 100
Влияние на эффективность сложности задачи 101
Влияние на эффективность обмена страницами с дисковой памятью 103
4.5. Исследование эффективности параллельной работы кластера
МЭИ (ТУ) на различных задачах 105
Перемножение матриц 106'
Решение систем линейных'алгебраических уравнений 109
Метод Гаусса ПО
Метод Якоби 114
Заключение 125
Заключение 128
Список литературы 132
Приложение 1. Примеры граф-схемных потоковых параллельных
программ 143
Программ управлением процессом сборки автомобилей 143
Перемножение матриц на ЯГСППП 149
Приложение 2. Программы для исследования эффективности
выполнения параллельных программ на кластере МЭИ (ТУ) 155
Параллельная программа перемножения матриц на MPI 155
Программа генерации коэффициентов матриц СЛАУ на языке С 160
Последовательная программа решения СЛАУ методом Гаусса на языке С 162
Параллельная программа решения СЛАУ методом Гаусса на MPI 164
Последовательная программа решения СЛАУ методом Якоби на языке С 171
Программа решения СЛАУ методом Якоби с использованием механизма нитей на языке С 173
2.7. Параллельная программа решения СЛАУ методом Якоби на MPI 177
Приложение 3. Тест HPL (High Performance UNPACK) 184
Аннотация работы
Работа посвящена сравнительному анализу методов и средств параллельного программирования (языков, технологий и инструментальных сред), разработке критериев и методов экспериментального исследования эффективности кластерных систем и их применению для исследования кластера МЭИ (ТУ).
В практической части работы излагаются результаты исследования эффективности решения известных вычислительных задач на кластере МЭИ (ТУ).
Работа состоит из введения, четырех глав, заключения, списка литературы, трех приложений, включающего в себя основной код реализации предложенных задач на кластере МЭИ (ТУ).
Введение к работе
Актуальность проблемы.
В настоящее время существует большое количество задач, требующих применения мощных вычислительных систем (ВС), среди которых задачи моделирования работы систем массового обслуживания и управления, распределённых систем, сложные вычислительные задачи и др. Для решения таких задач всё шире используются кластеры, которые становятся общедоступными и дешёвыми аппаратными платформами для высокопроизводительных вычислений. Кластер представляет собой множество компьютеров (узлов), соединенных между собой высокоскоростными каналами связи, а специальное программное обеспечение позволяет организовать параллельную работу узлов. Современные мощные кластеры уже содержат несколько сотен тысяч процессорных элементов (кластер BlueGene/L Ливерморской национальной лаборатории содержит 131072 процессора).
Однако эффективность применения кластерных систем в настоящее время наталкивается на целый ряд нерешённых проблем, касающихся как их программного обеспечения (языков, технологий и инструментальных сред параллельного программирования), так и собственно организации параллельных вычислений и эффективности их выполнения. Для сравнения эффективности работы кластеров сегодня разработаны различные стандартные тесты, однако они, как правило, основаны на известных задачах вычислительной математики, часто оптимизированы на соответствующие архитектуры и плохо приспособлены для того, чтобы исследовать работу кластеров в реальных критических ситуациях решения сложных задач (когда не хватает оперативной памяти и возникает постраничный обмен, когда велика интенсивность межузловых обменов и др.).
Поэтому проблема комплексного анализа эффективности организации параллельных вычислений на кластерах, определения их предельных
возможностей и их узких мест на реальных сложных задачах является актуальной.
Цель диссертационной работы.
Целью диссертационной работы является сравнительный анализ языков, технологий и инструментальных сред параллельного программирования, разработка критериев и методов экспериментального исследования эффективности кластерных систем и их применение для исследования кластера МЭИ (ТУ).
В качестве критериев эффективности обычно рассматривают время выполнения параллельной программы, использование ресурсов ВС и др. На эти критерии существенное влияние оказывают различные факторы, среди которых наиболее значимыми являются:
архитектура ВС (многопроцессорная, многомашинная, смешанная) и её ресурсы;
качество параллельной программы, которое существенно зависит от языка программирования, метода решения и распараллеливания задачи, степени распараллеливания (зернистости);
средства управления ВС при параллельной работе.
Научная новизна.
Научная новизна полученных в диссертации результатов состоит в том, что
сделана попытка сравнительного анализа языков и сред параллельного программирования на основе системы объективных критериев, определяющих спектр их основных возможностей с точки зрения практического использования,
введено расширение сетей Петри, которое может оказаться полезным для описания процессных языков и систем со свойством динамического порождения процессов,
3. введена система критериев, позволяющая комплексно оценивать эффективность параллельной работы кластеров и на её основе получены достаточно общего характера выводы, базирующиеся на исследованиях эффективности кластера МЭИ (ТУ).
Основные задачи диссертации.
В диссертации ставятся и решаются следующие задачи:
Анализ методов, языков и сред параллельного программирования;
Формализация операционной параллельной семантики языка граф-схемного потокового параллельного программирования и сравнительный анализ на её основе выразительных возможностей в представлении параллелизма этого языка и MPI;
Разработка критериев и методов экспериментального исследования эффективности параллельного решения различных задач на кластерах и её применение для исследования эффективности кластера МЭИ (ТУ).
Методы исследования.
Поставленные задачи решаются на основе определения критериев для сравнительного анализа ВС и их программного обеспечения, использования формальных моделей и экспериментирования на реальных задачах.
Практическая значимость.
Практическая значимость диссертации состоит в том, что в ней предложена технология экспериментального исследования кластеров, успешно примененная при исследовании кластера МЭИ (ТУ). Эта технология используется в НИО «Центр суперкомпьютерных технологий МЭИ (ТУ)» при решении практических задач на кластере.
Достоверность результатов работы.
Достоверность результатов работы подтверждена экспериментальным исследованием параллельного решения различных задач на кластере МЭИ (ТУ).
Реализация результатов работы.
Результаты работы используются при решении сложных задач на кластере МЭИ (ТУ), они внедрены в учебный процесс на кафедре Прикладной математики МЭИ (ТУ) при проведении лабораторных работ по курсу «Параллельные системы и параллельные вычисления».
Работа выполнялась в рамках проекта РФФИ № 06-01-00817 по теме «Разработка и исследование методов и алгоритмов принятия решений и управления параллельными процессами в больших компьютерных системах» (научный руководитель: д.т.н., проф. Кутепов В.П.).
Апробация работы.
Основные результаты диссертационной работы были представлены:
на Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования», Новороссийск, сентябрь 2006 г.;
на Международной научной конференции «2006 International Symposium on Distributed Computing and Applications to Business, Engineering and Science» (2006 Международный симпозиум по распределённым вычислениям и приложениям для бизнеса, инженерии и науки), Ханчжоу, Китай, октябрь 2006 г.;
на шестом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», Санкт-Петербург, декабрь 2006 г.;
на Международной научной конференции «2007 International Symposium on Distributed Computing and Applications to Business, Engineering and Science» (2007 Международный симпозиум по распределённым вычислениям и приложениям для бизнеса, инженерии и науки), Ичан, Китай, август 2007 г.;
на Всероссийской научной конференции «Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ», Новороссийск, сентябрь 2007 г.;
в теоретическом и научно-практическом журнале «Вестник МЭИ)», 2007, № 5;
на научных семинарах, проводимых на кафедре Прикладной математики МЭИ (ТУ).
Публикации.
Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 6 печатных работах.
Структура работы.
Диссертация состоит из введения, четырёх глав, заключения, списка использованной литературы из 113-х наименований и 3-х приложений. Диссертация содержит 186 страницы машинописного текста, включая 56 рисунков и 15 таблиц.
Во введении приводится общая характеристика работы, обсуждается актуальность рассматриваемой темы и дается аннотация основных положений работы.
В главе 1 представлен анализ основных подходов к созданию языков и сред параллельного программирования, а также описаны наиболее известные примитивы и языки для описания параллелизма.
