автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование эффективности параллельных вычислений на кластере Московского энергетического института

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

Лю Лян (КНР)

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА КЛАСТЕРЕ МОСКОВСКОГО ЭНЕРГЕТИЧЕСКОГО ИНСТИТУТА (ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА)

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

иио 1Ь>25"77"

лМ'

Москва-2007 г

003162577

Работа выполнена на кафедре Прикладной математики Московского энергетического института (Технического университета)

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

Кутепов Виталий Павлович

Официальные оппоненты

доктор технических наук, профессор Дзегеленок Игорь Игоревич

кандидат технических наук Бебчик Антон Михайлович

Ведущая организация

Российский государственный социальный университет (РГСУ), г Москва

Защита диссертации состоится «9» ноября 2007 г в 16 час 00 мин на заседании диссертационного совета Д 212 157 01 при Московском энергетическом институте (Техническом университете), по адресу 111250, Москва, Красноказарменная ул, д 17(ауд Г-306)

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета)

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу 111250, Москва, Красноказарменная ул, д 14, Ученый Совет МЭИ (ТУ)

Автореферат разослан « /6 » октября 2007 г

Ученый секретарь

диссертационного совета Д 212 157 01 кандидат технических наук, профессор I * Ладыгин И И

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

Актуальность проблемы. В настоящее время существует большое количество задач, требующих применения мощных вычислительных систем (ВС), среди которых задачи моделирования работы систем массового обслуживания и управления, распределенных систем, сложные вычислительные задачи и др Для решения таких задач все шире используются кластеры, которые становятся общедоступными и дешевыми аппаратными платформами для высокопроизводительных вычислений. Кластер представляет собой множество компьютеров (узлов), соединенных между собой высокоскоростными каналами связи, а специальное программное обеспечение позволяет организовать параллельную работу узлов Современные мощные кластеры уже содержат несколько сотен тысяч процессорных элементов (кластер Blue Gene/L Ливерморской национальной лаборатории содержат 131072 процессора)

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

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

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

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

- архитектура ВС (многопроцессорная, многомашинная, смешанная) и ее ресурсы,

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

задачи, степени распараллеливания (зернистости),

- средства управления ВС при параллельной работе

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

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

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

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

Основные задачи диссертации. В диссертации ставятся и решаются следующие задачи

1 Анализ методов, языков и сред параллельного программирования,

2 Формализация операционной параллельной семантики языка граф-схемного потокового параллельного программирования и сравнительный анализ на ее основе выразительных возможностей в представлении параллелизма этого языка и МР1,

3 Разработка критериев и методов экспериментального исследования эффективности параллельного решения различных задач на кластерах и ее применение для исследования эффективности кластера МЭИ

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

Практическая значимость диссертации состоит в том, что в ней предложена технология экспериментального исследования кластеров, успешно примененная при исследовании кластера МЭИ Эта технология используется в НИО «Центр суперкомпьютерных технологий МЭИ (ТУ)» при решении практических задач на кластере

Достоверность результатов работы подтверждена экспериментальным исследованием параллельного решения различных задач на кластере МЭИ

Реализация результатов работы. Результаты работы используются при решении сложных задач на кластере МЭИ, они внедрены в учебный процесс

на кафедре Прикладной математики МЭИ (ТУ) при проведении лабораторных работ по курсу «Параллельные системы и параллельные вычисления»

Работа выполнялась в рамках проекта РФФИ № 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 г), на научных семинарах, проводимых на кафедре Прикладной математики МЭИ (ТУ)

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

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 113-х наименований и 3-х приложений Диссертация содержит 142 страницы машинописного текста (без приложений), включая 56 рисунков и 15 таблиц, и 44 страницы приложений

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

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

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

примитивы и языки для задания параллелизма в программах

Выделено три основных подхода Первый подход основан на расширении последовательных языков путем введения в них средств задания параллелизма Это известные конструкции задания векторного параллелизма (parbegin parend) и нитевого параллелизма (fork join) Этот подход нацелен на сохранение последовательного стиля программирования на традиционных императивных и объектно-ориентированных языках, операционная семантика которых по-прежнему базируется на модели строго последовательной программы фон-Неймана Широко используется автоматическое распараллеливание последовательных программ, однако оно наталкивается на целый ряд принципиально непреодолимых проблем В частности, пока не создано алгоритмов, которые бы последовательную программу преобразовывали в абсолютно параллельную Однако для определенных конструкций, в частности, регулярных интерактивных циклов, в которых как показывает статистика, сосредоточен основной параллелизм, созданы вполне пригодные для практики алгоритмы Для более глубокого и качественного распараллеливания введен стандарт ОрепМР, который дает программисту возможность указывать участки программы, которые должен распараллеливать компилятор, используя комментарии

Второй подход основан на создании достаточно общих средств для описания взаимодействий одновременно протекающих последовательных процессов Это позволяет в определенной степени сохранить традиционный стиль последовательного программирования на уровне описания относительно независимых участков программы, а их информационную зависимость свести либо к использованию общих переменных (fork и join конструкции, Multithreading используют для этой цели общие данные, хранящиеся в общей памяти), либо к введению средств прямой передачи данных между процессами, используя соответствующие команды (в MPI и PVM введены различного рода команды передачи send и приема данных receive через сообщения) Данный подход делает параллельное программирование двухаспектным программист должен уметь хорошо декомпозировать программу задачи на независимые участки, а потом описывать достаточно сложные схемы их синхронизации при выполнении взаимодействий по данным

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

параллельного программирования FPTL (Functional Parallel Typified Language язык функционального параллельного программирования) * , объектно-ориентированный язык граф-схемного потокового параллельного программирования , другие проблемно-ориентированные языки параллельного программирования В этой главе также описаны наиболее интересные языки параллельного программирования, в которых есть средства структурного описания последовательных программ, их визуализации и тп , которые существенны для того, чтобы процесс разработки параллельных программ сделать более эффективным

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

Вторая глава посвящена сравнительному анализу граф-схемной модели потокового параллельного программирования и созданного на ее основе языка и известных API средств параллельного программирования для кластеров MPI

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

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

При выполнении параллельной программы в независимом процессе (подпрограмме) могут использоваться специальные системные команды для обеспечения межмодульного взаимодействия [2, 3] WRITE (запись данных в КГВых (конъюнктивные группы выходов)) и READ (чтение данных из КГВх (конъюнктивных групп входов)) Для более "тонкой" работы с

*Бажанов СЕ, Кутепов ВП, Шестаков ДА Язык функционального параллельного программирования и его реализация на кластерных системах - М Издагельство РАН, Программирование,2005,№ 5 -С 18-51

"Kutepov VP, Kotlyarov D V, Malamn VN , Pankov N A Object-oriented Environment for Parallel Programming for Multicore Clusters Based on Flowgraph Stream Parallel Programming Language // DCABES2007 PROCEEDINGS «2007 International Symposium on Distributed Computing and Applications to Business, Engineering and Science», August 14-17, 2007, YiChang, China H Hubei Science and Technology Press, Wuhan China, Vol 1 -P 347-350

поступающими на входы модулей данными, в частности работы с сопоставляемыми им буферами, предусмотрены команды CHECK и GETTAG0

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

MPI не имеет средств визуализации программ, в нем отсутствуют механизмы описания задач с динамическим характером порождения процессов, что является естественным для языка граф-схемного потокового параллельного программирования

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

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

1,3,4 1,4 13,4,5

ООО

Ô Ô

3,5

9 9 9 9 9 9

Рис 1 Изображение порояедаюшего перехода

6 Ô б) 1,4 1,4

Рис 2 Порождение переходов (а),

результат их срабатывания (б)

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

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

Расширение позволяет формально представлять процессы параллельного выполнения граф-схемных параллельных потоковых программ [5], что важно для анализа их правильности и вычислительной сложности

Для представления граф-схемной программы в данном расширении сетей Петри порождающие переходы сопоставляются КГВх подпрограмм модулей, а их входные места содержат столько входных мест, сколько входов в КГВх (формальных параметров подпрограммы) Накапливаемые в них

подпрограмма А 1,2

фишки моделируют состояние буферов, в которые записываются поступающие данные Запись данных в буферы реализуются в подпрограммах путем использования команд WRITE (запись данных в КГВых), в параметрической части которой явно указывается, на какие входы и каких КГВх модулей передаются вычисленные в подпрограммы значения

На рис 3 приведено модельное представление выполнения команды WRITE в виде фрагмента расширенной сети Петри

В диссертации также разработано сетевое

представление процессов выполнения других

системных команд READ, CHECK и GETTAG, что позволяет вместе с представлением команды WRITE перейти к

команда WRITE

6 Ô подпрограмма С

Ô Ô подпрограмма D

Рис 3 Представление команды WRITE в расширенной модели сетей Петри

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

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

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

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

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

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

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

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

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

2 Средства автоматизация процессов разработки параллельных программ пока весьма ограничены

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

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

Четвертая глава является центральной в диссертации, в ней излагаются результаты исследования эффективности решения известных вычислительных задач на кластере МЭИ

Кластер МЭИ - современный многоядерный кластер, состоящий из 16 узлов, каждый из которых содержит 2 двухядерных процессора (частота процессора 2 20 Ггц), работающих с общей памятью объемом 4 Гб. Высокоскоростная коммуникационная сеть Infiniband имеет пропускную способность 10 Гбит/сек и латентность порядка 2-3 мксек

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

Основными критериями эффективности параллельного решения задачи на кластере являются [1]

1)время выполнения параллельной программы

Т

2)козффициент ускорения С(К) = —, где Тпосл - время выполнения

программы без распараллеливания (один компьютер или процессор), ТпаР(К) ~ время параллельного выполнения программы на К компьютерах или процессорах

3)эффективность использования ресурсов Q(K) = - "jT"^

Следующие параметры, от которых зависят критерии эффективности, являются основными [1].

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

2) характеристики вычислительной системы

- количество компьютеров или/и процессоров кластера и их производительность,

- пропускная способность коммуникаций,

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

3) L(t) - загруженность 1-го компьютера в момент t определяемая по загруженности его процессора (доля времени его полезной работы),

4) Л'(0 - интенсивность обменов страницами с дисковой памятью,

5) ЛД/) - интенсивность межкомпьютерных обменов,

6) X'"(t) - интенсивность появления команд ввода-вывода в выполняемых процессах,

7) v,(f) - свободная память компьютера,

8) Л'^ (г) - множество ожидающих выполнения процессов

Предельные возможности ВС обычно определяются пиковой

производительностью ВС М*К, где M - производительность одного процессора (предполагается, что все процессоры однотипны), К — количество процессоров Однако, реальная производительность (именно этот критерий считается основным при исследовании эффективности ВС), определяемая как N/Tmp(K) , где N - общее количество процессорных операций, зафиксированных при выполнении программы (например, последовательном выполнении) может быть существенно меньше пиковой

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

Программы разрабатывались в среде операционной системы Linux с использованием средств MPI на языке С Данный язык был выбран потому, что библиотеки MPI в стандартной поставке реализованы на языках С и Fortran, из которых С является более предпочтительным языком программирования Компиляция программы осуществлялась с помощью специального компилятора mpicc, подготавливающего программу для выполнения в среде MPI

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

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

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

Тест Lmpack - один из самых распространенных тестов, он состоит из задач решения систем линейных алгебраических уравнений (СЛАУ) с плотными матрицами (решение СЛАУ Ах = b методом LU-факторизации (LU-разложения) с выбором ведущего элемента столбца, где А - плотно заполненная матрица размерности п) Дня систем с распределенной памятью разработана специальная версия этого теста - тест HPL (High Performance Lmpack) Тест HPL обычно используемый для определения списка Тор500 Этот список публикуется дважды в год и содержит 500 наиболее производительных компьютерных систем

1. Исследование эффективности кластера МЭИ на тесте 11РЬ [1] а). Влияние на эффективность сложности задачи

Рис 4 Зависимость времени выполнения от размера матрицы

1

09 08 07 06 05 04 03 02 0 1 0

* ^ / / / / / / / j é Размер матрицы

Рис 5 Зависимость эффективности от размера матрицы

Будем использовать все 16 узлов кластера На каждом узле будет запускаться 4 процесса MPI Представим полученные результаты в виде зависимости критериев эффективности от размера матрицы (рис 4-6) Как следует из рис 5, использование процессоров кластера растет с ростом п - размера матрицы СЛАУ и при п порядка 32000 Рис б Зависимость производительности достигает предельного значения (они (GFlops) от размера матрицы полностью загружены работой в

процессе решения СЛАУ), а производительность близка к пиковой Можно также заметить уменьшение производной для всех критериев с увеличением

размера матрицы, что обусловлено увеличением времени на передачу данных между узлами кластера

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

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

1 сг 55000

I | 50000 •

| г 45000 -| 8 40000 -

1 « 35000 -

§ 30000 ■

£ 25000 -ё 20000

1 15000 ■

« 10000 -| 5000

ю о -

Рис 7 Зависимость Рис 8 Зависимость производительности

времени выполнения от размера матрицы (ОР1орв) от размера матрицы

2. Исследование эффективности параллельной работы кластера МЭИ (ТУ) на различных задачах

О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

50

45

й 40

я 3 35

& «г 30

« 7Л

\25 о с! 5 20

? £ 15

К 10

5

0 I»«

0 4 8 '2 16 20 24 28 32 36 40 44 4!

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

Рис 9 Зависимость времени перемножения матриц от К

Рис 10 Зависимость времени обмена данными от К

а). Перемножение матриц. Для распараллеливания вычисление элементов результирующей матрицы размерности п*п она разбивается равномерно на группы в зависимости о количества процессоров кластера К (п>К) по следующему принципу сначала на каждый процессор распределяется для вычисления по (~Ы~ - целая часть а) элементов, а

затем оставшиеся п-~\п/к[хк элементов добавляются по одному к выделенным группам по очереди пока не будут полностью исчерпаны

Графики на рис 9-12 показывают, как изменяется время перемножения матриц для п=20000, время обмена данными между узлами кластера, коэффициент ускорения и эффективность в зависимости от -К-количества используемых процессоров кластера

О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

О 4 8 12 16 20 24 28 32 36 40 44 4' Количество процессоров

Рис 12 Зависимость эффективности от К

Рис 11 Зависимость коэффициента ускорения от К Этот эксперимент наглядно показывает негативное влияние интенсивности обменов с увеличением п - сложности задачи (рис 10) на эффективность параллельной работы кластера

600

550

>■ 500

С" 450

400

350

ё 300

а к я 250

? 200

03 150

100

50

I О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64

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

Рис 13 Зависимость времени решения СЛАУ от К (размер матрицы и=500)

600000 560000 ^ 520000 3 480000 ё 440000 " § 400000

§ £. 360000

§ 8 320000 1 1 280000 8. ? 240000 5 ^ 200000 | 2. 160000 120000 80000 40000 0

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 14 Зависимость времени решения СЛАУ от К (размер матрицы и=5000)

-размер матрицы п=500 о- размер матрицы п=50001

3000 г 2750 2500 2250 | 2000 | 1750 8 1500 | 1250 | 1000 ~ 750 500 250 0

8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 15 Зависимость времени обмена данными от К

- размер матрицы п=500

размер матрицы п=5000}

41

42

49

36

33

30

27

Т. 24

и 7.1

18

15

•Я- 17

<>

К 6

Ч

0

0 4 8 12 16 20 24 28 32 36 40 44 .

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

Рис 16 Зависимость коэффициента ускорения от К

размер матрицы п=500_размер матрицы п=5000 \

О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 17 Зависимость эффективности от К

б). Решение СЛАУ методом

Гаусса. В исследуемой

МР1-параллельной программе

решения СЛАУ методом Гаусса исходная матрица коэффициентов распределяется по К процессорам кластера циклическими

горизонтальными полосами с шириной полосы в одну строку Первая строка матрицы А помещается в процессор 1, вторая строка - в процессор 2, и тд, К-я строка в процессор К Затем (К+1 )-я строка снова помещается в процессор 1, (К+2)-я строка - в процессор 2. и т д На рис 13-17 показаны графики изменения соответствующих критериев эффективности параллельного решения СЛАУ методом Гаусса для размера матрицы и=500 и «=5000 в зависимости от ^-количества выделенных процессоров кластера

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

в). Решение СЛАУ методом Якоби. Метод Якоби просто распараллеливается путем равномерного распределения вычислений значений х';, г=1,2, ,п, на К процессорах кластера аналогичного тому, как это делалось выше для перемножения матриц На рис 18-22 показаны зависимости от К соответствующих критериев эффективности решения СЛАУ размера матрицы я=500 и «=5000 с точностью 1 * 10'6 методом Якоби для различного количества процессоров К в кластере

О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 18 Зависимость времени решения СЛАУ от К (размер матрицы я=500)

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 19 Зависимость времени решения СЛАУ от К (размер матрицы и=5000)

- размер матрицы rr=SOO размер матрицы n=50001

5 а- „ sag

X ц

ID « 7

О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 20 Зависимость времени обмена данными от К

-размер матрицы п=500

размер матрицы n=50001

4 8 12 16 20 24 28 32 36 40 44 4S 52 56 60 64 Количество процессоров

Рис 21 Зависимость коэффициента ускорения от К

" роЗтср «аТрИцо! ii=wiv

ряЗМбр ш51упцщ П—-шуу/ |

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 Количество процессоров

Рис 22 Зависимость эффективности от К

|1

8 800

?1 S 3.

- ш 1 оит/сек

iuu моит/сек I

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 ( Количество процессоров

Рис 23 Зависимость времени решения СЛАУ от К

О —•—'—1—'—'—1—'—'--——<—'

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 "6 j

Количество узлов 1 ____________I

Рис 24 Зависимость коэффициента ускорения от К

09

08

07

о 06

Я Й 05

i 04

■в* m 03

02

0 1

0

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

Рис 25 Зависимость эффективности от К

На рис 23-25 приведены результаты параллельного решения СЛАУ методом Якоби для размера матриц п-5000 с точностью 1 хЮ"6 на кластере из обычных 16 двухядерных компьютеров, объединенных сетью Ethernet 100 Мбит/сек Эти эксперименты показывают, что время параллельного решения задач на кластере МЭИ в среднем на 20-50% меньше, чем аналогичное время для кластера, организованного из персональных компьютеров (см рис 23)

На рис 26 и 27 показаны зависимости времени решения СЛАУ методом .Якоби с точностью 1х10'6 и обмена данными между узлами в зависимости от сложности задачи (размера матрицы) для количества процессоров равного 64 на кластере МЭИ

200000 >, 180000 5 _ 160000 5 | 140000

5 | 120000 1 8 100000 I. | 80000 | | 60000 40000 20000 0

се

^ ^ # ¿Г^ Л<Г,$5>

Размер матрицы

11000 10000 9000 8000 7000 ' 6000 5000 4000 3000 2000 1000 О

# # # # # # # # <5? Размер матрицы

Рис 26 Зависимость времени решения СЛАУ от размера матрицы

Рис 27 Зависимость времени обмена данными от размера матрицы

При размере матрицы (я=85000) объем данных, соответствующих каждому блоку ее разбиения на 64 части и соответственно используемых каждым из 64 процессов МР1-программы, таков, что они не могут быть размещены в оперативной памяти узла

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

в зависимости от сложности (п"' > п" >п')

На рис 28 показан общий характер зависимости между сложностью СЛАУ и

эффективностью ее параллельного решения на кластере Из рисунка видно, что для заданной сложности СЛАУ п существует оптимальное количество процессов и

соответственно процессоров копт, для которого время решения задачи достигает минимума

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

1 Выполнен анализ языков, технологий и инструментальных сред, используемых для разработки параллельных программ Этот анализ показывает следующее

1 1 Доминирующие средства параллельного программирования MPI, PVM для кластеров и Multithreading для многопроцессорных (многоядерных) ВС с общей памятью основаны на процессных моделях, причем в MPI и PVM использованы весьма простые и ограничивающие возможности распараллеливания реальных задач средствами описания взаимодействия процессов

12 Отсутствие у этих средств возможности структурирования и визуализации программ существенно усложняет процесс разработки программы, отражения в нем декомпозиционных стратегий программирования

13 Инструментальные среды для MPI и PVM, за исключением включенных в них библиотек, ограничены Гораздо шире инструментарий для проектирования нитевых параллельного программирования, включающий стандарт «ручного» распараллеливания ОрепМР, средства анализа нитевых программ (Trace Analyzer) и настройки на конкретную ВС (Tuner) Однако, «чисто» процессная модель, лежащая в основе нитевого программирования, требует от программиста больших усилий по обеспечению корректности нитевых программ, разделяющих общие переменные, выбору оптимального количества нитей, их синхронизации и др

2 Представлен сравнительный анализ граф-схемного подхода и созданной на его основе технологии граф-схемного потокового программирования со средствами параллельного программирования MPI [4, 6] Показаны преимущества первого подхода по сравнению со вторым в части структурного визуального проектирования параллельных программ, простого отражения в программе различных форм параллелизма, возникающих при программировании реальных задач Кроме того, среда граф-схемного параллельного программирования [2, 3] содержит развитые средства планирования параллельных процессов и управления загруженностью узлов ВС при выполнении параллельных программ, чего нет в MPI и Multithreading Это существенно упрощает задачу программиста по организации эффективного выполнения параллельной программы на конкретной ВС

3 Разработана модель-расширение сетей Петри [5] с целью формального описания и исследования параллельных процессов, индуцируемых при выполнении граф-схемных потоковых программ

4 Выполнено исследование эффективности реализации параллельных

вычислений на кластере МЭИ

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

4 2 Для различных типичных математических задач построены параллельные MPI программы и выполнено экспериментальное исследование эффективности их выполнения на кластере МЭИ, из которого можно сделать следующие выводы

4 2 1 С увеличением сложности задачи эффективность (по всем перечисленным критериям) есть неубывающая функция, ограниченная определенным порогом для заданного количества узлов кластера Этот порог сложности определяется объемом оперативной памяти, которая необходима параллельной программе, чтобы не возникало обменов страницами с дисковой памятью При переходе через этот порог начинается свопинг, и эффективность работы кластера резко снижается [1]

4 2 2 Кластер МЭИ имеет современные коммуникации Infimband с предельной пропускной способностью 10 Гбит/сек и латентностью порядка 2-3 мксек Реальная скорость обмена, однако, порядка 1 Гбит/сек, что связно с латентностью и временем, затрачиваемым на организацию функций обмена Однако, даже для рассмотренных задач с небольшой относительно интенсивностью обменов между процессами с увеличением их количества с целью большего распараллеливания задачи увеличивается время, затрачиваемое на обмены, и коэффициент ускорения начинает уменьшаться Дополнительные исследования эффективности на кластере, организованном из персональных компьютеров с пропускной способностью сети 100 Мбит/сек, подтверждают, что с уменьшением пропускной способности сети это влияние более значительно

4 2 3 Метод решения задачи может оказывать принципиальное влияние на возможность ускорения решения сложной задачи, иногда изменяя его на порядок и более Это подтверждают эксперименты параллельного решения СЛАУ методом Гаусса и итерационным методом Якоби Однако, если метод Гаусса не вызывает сомнений с позиций его точности, то метод Якоби требует большой предварительной работы по выяснению «определенности» СЛАУ, выбору начальных приближений неизвестных и точности

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

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

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

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

1. Лю Лян. Исследование эффективности реализации параллельных вычислений на кластере МЭИ. II Вестник МЭИ, 2007, № 5.

2 Лазуткин В.А., Лю Лян, Осипов М.А. Средства граф-схемного потокового параллельного программирования для кластеров // Труды Всероссийской научной конференции «Научный сервис в сети Интернет технологии параллельного программирования», г Новороссийск, 18-23 сентября 2006 г - M Издательство Московского университета, 2006 - С 93-96

3 Kutepov V.P., Lazutkin V.A., Liu Liang, Osipov M.A. The Means of Flowgraph Stream Parallel Programmmg for Clusters // DCABES2006 PROCEEDINGS «2006 International Symposium on Distributed Computing and Applications to Business, Engineering and Science», October 11-15, 2006, Hangzhou, Chma //Shanghai Umversxty Press, 2006, Vol 1 -P 189-194

4 Кутепов В.П., Лазуткин B.A., Лю Лян, Осипов М.А. Технологические аспекты построения граф-схемных параллельных потоковых программ // Материалы шестого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах», Санкт-Петербург, 12-17 декабря 2006 г, - СПб. Санкт-Петербургский госуниверситет, 2007, Том 1 - С 263-270

5 Kutepov V.P., Lazutkin V.A., Liu Liang. The Extension of Petn Nets for the Description of Operational Semantics of Flowgraph Stream Parallel Programmmg Language // DCABES2007 PROCEEDINGS «2007 International Symposium on Distributed Computing and Applications to Business, Engineering and Science», August 14-17, 2007, YiChang, Chma // Hubei Science and Technology Press, Wuhan China, 2007, Vol 1 - P 404-407

6 Лазуткин B.A., Лю Лян. Технологические аспекты построения граф-схемных параллельных потоковых программ // Труды Всероссийской научной конференции «Научный сервис в сети Интернет многоядерный компьютерный мир 15 лет РФФИ», г Новороссийск, 24-29 сентября 2007 г -М Издательство Московского университета, 2007 - С 174-177

Подписано в печать Ь К- M г Зак. Тир. fûO П. л.

Полиграфический центр МЭИ (ТУ)

111250, г. Москва, ул. Красноказарменная, д. 13

Аннотация работы.

Введение.

Глава 1. Обзор языков и сред параллельного программирования.

Введение.

1.1. Примитивы параллельного программирования.

1.2. Распараллеливание последовательных программ.

1.3. Модели и средства описания параллелизма на процессном уровне.

1.3.1. Сети Петри.

1.3.2. MPI, PVM и Нити.

1.3.2.1. MPI.

1.3.2.2. PVM и его сравнение с MPI.

1.3.2.3. Нити.

1.3.3. Другие проблемно-ориентированные языки и средства параллельного программирования.

1.3.3.1. DVM.

1.3.3.2. НРС++.:.

1.3.3.3. HPF.

1.3.3.4. Linda.

1.3.3.5. МС#.

1.3.3.6. Mentat.

1.3.3.7. Mosix.

1.3.3.8. mpC.

1.4. Функциональное параллельное программирование.

1.5. Сравнение языков и сред параллельного программирования.

J>

2.1. Язык граф-схемного потокового параллельного программирования . 48

2.1.1. Структура и интерпретация программы на ЯГС111Ш.48

2.1.2. Операционная семантика.52

2.1.3. Примеры построения программ на ЯГСППП.56

2.2. Формальная операционная семантика ЯГСППП.64

2.3. Сравнительный анализ выразительных возможностей MPI и !

ЯГСППП.67

Заключение.69

Глава 3. Методы, технологии и инструментальные среды параллельного программирования.71

Введение.71

3.1. Методы и технологии разработки параллельных программ.72

3.2. Технологии и инструментальные среды параллельного программирования.78

Заключение.90 1

Глава 4. Исследование эффективности выполнения параллельных программ на кластере МЭИ (ТУ).91

Ведение.91

4.1. Кластерные ВС и их технические характеристики.91

4.2. О кластере МЭИ (ТУ) и его характеристиках.93

4.3. Критерии и основные параметры эффективности выполнения параллельных программ на кластерах.94

4.4. Стандартные смеси для проверки эффективности работы ВС.97

4.4.1. Известные тесты для кластеров.98

4.4.2. Исследование эффективности кластера МЭИ (ТУ) на тесте HPL 100

4.4.2.1. Влияние на эффективность сложности задачи.101

4.4.2.2. Влияние на эффективность обмена страницами с дисковой памятью.103

4.5. Исследование эффективности параллельной работы кластера

МЭИ (ТУ) на различных задачах.105

4.5.1. Перемножение матриц.106'

4.5.2. Решение систем линейных'алгебраических уравнений.109

4.5.2.1. Метод Гаусса.110

4.5.2.2. Метод Якоби.114

Заключение.125

Заключение.128

Список литературы.132

Приложение 1. Примеры граф-схемных потоковых параллельных программ.143

1.1. Программ управлением процессом сборки автомобилей.143

1.2. Перемножение матриц на ЯГСППП.149

Приложение 2. Программы для исследования эффективности выполнения параллельных программ на кластере МЭИ (ТУ).155

2.1. Параллельная программа перемножения матриц на MPI.155

2.2. Программа генерации коэффициентов матриц СЛАУ на языке С.160

2.3. Последовательная программа решения СЛАУ методом Гаусса на языке С.162

2.4. Параллельная программа решения СЛАУ методом Гаусса на MPI.164

2.5. Последовательная программа решения СЛАУ методом Якоби на языке С.171

2.6. Программа решения СЛАУ методом Якоби с использованием механизма нитей на языке С.173

2.7. Параллельная программа решения СЛАУ методом Якоби на MPI.177

Приложение 3. Тест HPL (High Performance UNPACK).184

Аннотация работы

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

В практической части работы излагаются результаты исследования эффективности решения известных вычислительных задач на кластере МЭИ (ТУ).

Работа состоит из введения, четырех глав, заключения, списка литературы, трех приложений, включающего в себя основной код реализации предложенных задач на кластере МЭИ (ТУ).

Введение

Актуальность проблемы.

В настоящее время существует большое количество задач, требующих применения мощных вычислительных систем (ВС), среди которых задачи моделирования работы систем массового обслуживания и управления, распределённых систем, сложные вычислительные задачи и др. Для решения таких задач всё шире используются кластеры, которые становятся общедоступными и дешёвыми аппаратными платформами для высокопроизводительных вычислений. Кластер представляет собой множество компьютеров (узлов), соединенных между собой высокоскоростными каналами связи, а специальное программное обеспечение позволяет организовать параллельную работу узлов. Современные мощные кластеры уже содержат несколько сотен тысяч процессорных элементов (кластер BlueGene/L Ливерморской национальной лаборатории содержит 131072 процессора).

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

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

Цель диссертационной работы.

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

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

- архитектура ВС (многопроцессорная, многомашинная, смешанная) и её ресурсы;

- качество параллельной программы, которое существенно зависит от языка программирования, метода решения и распараллеливания задачи, степени распараллеливания (зернистости);

- средства управления ВС при параллельной работе.

Научная новизна.

Научная новизна полученных в диссертации результатов состоит в том, что

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

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

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

Основные задачи диссертации.

В диссертации ставятся и решаются следующие задачи:

1. Анализ методов, языков и сред параллельного программирования;

2. Формализация операционной параллельной семантики языка граф-схемного потокового параллельного программирования и сравнительный анализ на её основе выразительных возможностей в представлении параллелизма этого языка и MPI;

3. Разработка критериев и методов экспериментального исследования эффективности параллельного решения различных задач на кластерах и её применение для исследования эффективности кластера МЭИ (ТУ).

Методы исследования.

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

Практическая значимость.

Практическая значимость диссертации состоит в том, что в ней предложена технология экспериментального исследования кластеров, успешно примененная при исследовании кластера МЭИ (ТУ). Эта технология используется в НИО «Центр суперкомпьютерных технологий МЭИ (ТУ)» при решении практических задач на кластере.

Достоверность результатов работы.

Достоверность результатов работы подтверждена экспериментальным исследованием параллельного решения различных задач на кластере МЭИ (ТУ).

Реализация результатов работы.

Результаты работы используются при решении сложных задач на кластере МЭИ (ТУ), они внедрены в учебный процесс на кафедре Прикладной математики МЭИ (ТУ) при проведении лабораторных работ по курсу «Параллельные системы и параллельные вычисления».

Работа выполнялась в рамках проекта РФФИ № 06-01-00817 по теме «Разработка и исследование методов и алгоритмов принятия решений и управления параллельными процессами в больших компьютерных системах» (научный руководитель: д.т.н., проф. Кутепов В.П.).

Апробация работы.

Основные результаты диссертационной работы были представлены:

1. на Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования», Новороссийск, сентябрь 2006 г.;

2. на Международной научной конференции «2006 International Symposium on Distributed Computing and Applications to Business, Engineering and Science» (2006 Международный симпозиум по распределённым вычислениям и приложениям для бизнеса, инженерии и науки), Ханчжоу, Китай, октябрь 2006 г.;

3. на шестом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», Санкт-Петербург, декабрь 2006 г.;

4. на Международной научной конференции «2007 International Symposium on Distributed Computing and Applications to Business, Engineering and Science» (2007 Международный симпозиум по распределённым вычислениям и приложениям для бизнеса, инженерии и науки), Ичан, Китай, август 2007 г.;

5. на Всероссийской научной конференции «Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ», Новороссийск, сентябрь 2007 г.;

6. в теоретическом и научно-практическом журнале «Вестник МЭИ)», 2007, № 5;

7. на научных семинарах, проводимых на кафедре Прикладной математики МЭИ (ТУ).

Публикации.

Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 6 печатных работах.

Структура работы.

Диссертация состоит из введения, четырёх глав, заключения, списка использованной литературы из 113-х наименований и 3-х приложений. Диссертация содержит 186 страницы машинописного текста, включая 56 рисунков и 15 таблиц.

Заключение

Перечислим основные результаты, полученные в работе:

1. Выполнен анализ языков, технологий и инструментальных сред, используемых для разработки параллельных программ (главы 1-3). Этот анализ показывает следующее:

1.1.Доминирующие средства параллельного программирования MPI, PVM для кластеров и Multithreading для многопроцессорных (многоядерных) ВС с общей памятью основаны на процессных моделях, причем в MPI и PVM использованы весьма простые и ограничивающие возможности распараллеливания реальных задач средствами описания взаимодействия процессов. 1.2.0тсутствие у этих средств возможности структурирования и визуализации программ существенно усложняет процесс разработки программы, отражения в нём декомпозиционных стратегий программирования. 1.3.Инструментальные среды для MPI и PVM, за исключением включенных в них библиотек, ограничены. Гораздо шире инструментарий для проектирования нитевых параллельного программирования, включающий стандарт «ручного» распараллеливания ОрепМР, средства анализа нитевых программ (Trace Analyzer) и настройки на конкретную ВС (Tuner). Однако, «чисто» процессная модель, лежащая в основе нитевого программирования, требует от программиста больших усилий по обеспечению корректности нитевых программ, разделяющих общие переменные, выбору оптимального количества нитей, их синхронизации и др.

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

MPI (глава 2).

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

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

4. Выполнено исследование эффективности реализации параллельных вычислений на кластере МЭИ.

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

4.2.Для различных типичных математических задач построены параллельные MPI программы и выполнено экспериментальное исследование эффективности их выполнения на кластере МЭИ, из которого можно сделать следующие выводы. 4.2.1. С увеличением сложности задачи эффективность (по всем перечисленным критериям) есть неубывающая функция, ограниченная определенным порогом для заданного количества узлов кластера. Этот порог сложности определяется объёмом оперативной памяти, которая необходима параллельной программе, чтобы не возникало обменов страницами с дисковой памятью. При переходе через этот порог начинается свопинг, и эффективность работы кластера резко снижается.

4.2.2. Кластер МЭИ имеет современные коммуникации Infiniband с предельной пропускной способностью 10 Гбит/сек и латентностью порядка 2-3 мксек. Реальная скорость обмена, однако, порядка 1 Гбит/сек, что связно с латентностью и временем, затрачиваемым на организацию функций обмена. Однако, даже для рассмотренных задач с небольшой относительно интенсивностью обменов между процессами с увеличением их количества с целью большего распараллеливания задачи увеличивается время, затрачиваемое на обмены, и коэффициент ускорения начинает уменьшаться. Дополнительные исследования эффективности на кластере, организованном из персональных компьютеров с пропускной способностью сети 100 Мбит/сек, подтверждают, что с уменьшением пропускной способности сети это влияние более значительно.

4.2.3. Метод решения задачи может оказывать принципиальное влияние на возможность ускорения решения сложной задачи, иногда изменяя его на порядок и более. Это подтверждают эксперименты параллельного решения СЛАУ методом Гаусса и итерационным методом Якоби. Однако, если метод Гаусса не вызывает сомнений с позиций его точности, то метод Якоби требует большой предварительной работы по выяснению «определенности» СЛАУ, выбору начальных приближений неизвестных и точности.

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

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

1. Антонов А.С. Введение в параллельные вычисления (методическое пособие). М.: Издательство МГУ, 2002. - 69 с.

2. Антонов А.С. Параллельное Программирование с использование технологии MPI. М.: Издательство МГУ, 2004. - 71 с.

3. Арефьев А.А. и др. Язык граф-схем параллельных алгоритмов и его расширения. -М.: Издательство РАН, Программирование, 1981, № 4.

4. Афанасьев К.Е., Стуколов С.В., Демидов А.В., Малышенко В.В. Многопроцессорные вычислительные системы и параллельное программирование. М.: Кемеровский государственный университет, 2004. - 182 с (http://oldunesco.kemsu.ru/mps/).

5. Бажанов С.Е., Воронцов М.М., Кутепов В.П., Шестаков Д.А. Структурный анализ и планирование процессов параллельного выполнения функциональных программ. // Известия РАН, Теория и системы управления, 2005, № 6. С. 131-146.

6. Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Язык функционального параллельного программирования и его реализация на кластерных системах. М.: Издательство РАН, Программирование, 2005, № 5. - С. 18-51.

7. Балашов К.В. Проектирование структур программ в системах искусственного интеллекта. // Кибернетика, 1994, № 2.

8. Борздова Т.В. Разработка структурно-функциональных методов в параллельном программировании. // Кандидатская диссертация, МЭИ, 1984.

9. Букатов А.А., Дацюк B.H., Жегуло А.И. Программирование многопроцессорных вычислительных систем. М.: Ростовский государственный университет, 2003. - 208 с.

10. Буч Г., Рамбо Дж., Джекобсон А. Язык UML. // Руководство пользователя. М.: ДМК, 2000. - 432 с.

11. Буч. Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. // Rational Санта-Клара, Калифорния, 1999. М.: Бином, - СПб: Невский диалект, 1999. - 560 с.

12. Бэкон Д., Харрис Т. Операционные системы. // Пер. с англ. СПБ.: Питер; Киев: Издательская группа BHV, 2004. - 800 с.

13. Вендров A.M. Современные технологии создания программного обеспечения (Обзор) (http://www.jetinfo.rU/2004/4/2004.4.pdf Интернет-ресурс по Jet Info Online).

14. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб: БХВ-Петербург, 2004. - 599 с.

15. Гарви М. Дейтел. Введение в операционные системы. // Пер. с англ. В 2-х т. М.: Мир, 1987. Т.1. - 359 е., Т.2. - 398 с.

16. Грызунов В.Б. Разработка и реализация системы функционального программирования. // Кандидатская диссертация, М.: МЭИ, 1990.

17. Гузев В.Б., Сердюк Ю.П. Технический отчет «Механизмы взаимодействия объектов в параллельном объектно-ориентированном языке программирования МС#». // Декабрь, 2003 (http://u.pereslavl.ru/~vadim/MCShaф/index.ru.html).

18. Демидович Б.П., Марон И.А. Основы вычислительной математики. -М.: Наука, 1970.-664 с.

19. Джоунз Г. Программирование на языке Оккам. // Пер. с англ. М.: Мир, 1989.-208 с.

20. Димитриев Ю.К., Хорошевский В.Г. Вычислительные системы из мини-ЭВМ. М.: Радио и связь, 1982. - 304 с.

21. Дмитриев Ю.К., Хорошевский В.Г. Вычислительные системы из мини

22. ЭВМ. М.: Радио и связь, 1982. - 304 с.

23. Душкин Р.В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2006. - С. 608.

24. Жангисина Г.Д. Исследование и разработка специализированной базы математических знаний для систем функционального программирования. // Автореферат кандидатской диссертации. М.: Национальная академия наук Республики Казахстан, Алмата, 1995.

25. Калашян А.Н., Калянов Г.Н. Структурные модели бизнеса: DFD-технологии. М.: Финансы и статистика, 2003. - 256 с.

26. Камерон Хыоз. Трейси Хыоз. Параллельное и распределенное программирование с использованием С++. // Пер. с англ. М.: Вильяме, 2004.-667 с.

27. Кватрани Т. Визуальное моделирование с помощью Rational Rose 2002 и UML. -М.: Вильяме, 2003. 192 с.

28. Клини С.К. Введение в метаматематику. М.: ИЛ, 1957. - 524 с.

29. Кораблин Ю.П. Проблема корректности граф-схем параллельных алгоритмов. М.: Издательство РАН, Программирование, 1978, № 5.

30. Кораблин Ю.П. Языки параллельных алгоритмов и принципы их реализации. //Автореферат кандидатской диссертации. -М.: МЭИ, 1977.

31. Корнеев В.В. Вычислительные системы. Москва. М.: Гелиос АРВ, 2004. -512 с.

32. Котляров Д.В., Кутепов В.П., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах. // Известия РАН, Теория и системы управления, 2005, № 1. С. 75-96.

33. Котов В.Е. Сети Петри. М.: Наука, 1984. -160 с.

34. Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей. М.: Информационные технологии и вычислительные системы, 2003, № 1-2. - С. 42-61.

35. Кутепов В.П. Интеллектуальное управление процессами ввычислительных системах. // Известия РАН, Теория и системы управления, 2007, № 5.

36. Кутепов В.П. Информатика на пути к интеграции. // Вестник МЭИ, 1995, №4.

37. Кутепов В.П. Исчисление функциональных схем и параллельные алгоритмы. М.: Издательство РАН, Программирование, 1976, № 6.

38. Кутепов В.П. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения. // Известия РАН, Теория и системы управления, 1996, № 5. С. 97-114.

39. Кутепов В.П. Организация параллельных вычислений на системах. М.: МЭИ, 1988.-64 с.

40. Кутепов В.П. Фальк В.Н. Направленные отношения: теория и приложения. М.: Издательство РАН. Техническая кибернетика, 1994, № 4, №5.

41. Кутепов В.П. Языки параллельных алгоритмов. М.: МЭИ, 1978. - 91 с.

42. Кутепов В.П., Жангисина Г.Д. Организация специализированной базы знаний для решения задач линейной алгебры. // Тез. Докл. Межд. конференции «Высокопроизводительные вычислительные системы в управлении и научных исследованиях». М.: ИПУ, 1991.

43. Кутепов В.П., Котляров Д.В., Маланин В.Н, Панков Н.А. Средства управления выполнением объектно-ориентированных граф-схемных потоковых параллельных программ на кластерах. // Материалы шестого Международного научно-практического семинара

44. Высокопроизводительные параллельные вычисления на кластерных системах», Санкт-Петербург, 12-17 декабря 2006 г. СПб: Санкт-Петербургский госуниверситет, 2007, Том 1. - С. 271-276.

45. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты. // Кибернетика, 1979, № 1. С. 46-58.

46. Лазуткин В.А. Исследование методов и разработка технологии и инструментальной среды для проектирования граф-схемных параллельных потоковых программ. М.: Магистерская диссертация, 2005.- 102 с.

47. Лазуткин В.А., Лю Лян. Технологические аспекты построения граф-схемных параллельных потоковых программ. // Труды

48. Всероссийской научной конференции «Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ», г. Новороссийск, 24-29 сентября 2007 г. -М.: Издательство Московского университета, 2007. С. 174-177.

49. Лобанов В.П. Разработка алгоритмов и программных средств обеспечения надежности параллельных вычислений на вычислительных комплексах. // Автореферат кандидатской диссертации. -М.: МЭИ, 1985.

50. Лю Лян. Исследование эффективности реализации параллельных вычислений на кластере МЭИ. // Вестник МЭИ, 2007, № 5. С. 90-96.

51. Масликов Сергей. Пути потоков неисповедимы (http://mycomp.com.ua/text/7740).

52. Немнюгин Сергей, Стесик Ольга. Параллельное программирование для многопроцессорных вычислительных систем. СПб: БХВ-Петербург, 2002.-400 с.

53. Питерсон Дж. Теория сетей Петри и моделирование систем. // Пер. с англ. -М.: Мир, 1984.-264 с.

54. Розенберг Д., Скотт К. Применение объектного моделирования с использованием UML и анализ прецедентов. -М.: ДМК Пресс, 2002. -160 с.

55. Саати Т.Л. Элементы теории массового обслуживания и её приложения». М.: Советское Радио, 1971. - 520 с.

56. Самарский А. А. Введение в численные методы. // 3-изд. СПБ.: Лань, 2005.-288 с.

57. Сидякин И.М. Многозадачность Windows. М: Московский Государственный Технический Университет им. Н.Э. Баумана, 1998. -28 с.

58. Смирнов А.В., Шерементов Л.Б. Организация взаимодействия агентов в многокомпонентных САПР, Автоматизация проектирования, № 02, 1999.-36 с.

59. Строева Т.М. Асинхронные вычислительные сети и их применение всистемах параллельного программирования. // Автореферат кандидатской диссертации. -М.: МЭИ, 1981.

60. Строева Т.М., Фальк В.Н. Асинхронные вычислительные сети (ABC): ABC-модель и ABC система программирования. -М.: Кибернетика, 1981, № 3. С. 90-96.

61. Таненбаум Э. Архитектура компьютера. // 4-изд. СПБ.: Питер, 2006. -699 с.

62. Таненбаум Э. Современные операционные системы. // 2-изд. СПБ.: Питер, 2005. -1038 с.

63. Филд А., Харрисон П. Функциональное программирование. М.: Мир, 1993.-637 с.

64. Финн В.К. Правдоподобные выводы и правдоподобные рассуждения. // Итоги науки и техники. Сер. Теория вероятностей, математическая статистика, теоретическая кибернетика. М.: ВИНИТИ, Т.28, 1988. - С. 3-84.

65. Хоар Ч. Взаимодействующие последовательные процессы. // Пер. с англ.- М.: Мир, 1989.-264 с.

66. Хорев П.Б. Технологии объектно-ориентированного программирования.- М.: Издательский центр «Академия», 2004. 448 с.

67. Черемных С.В., Семенов И.О., Ручкин B.C. Структурный анализ систем: IDEF- технологии. М.: Финансы и статистика, 2001. - 208 с.

68. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. // Пер. с англ. М.: Вильяме, 2003. - 512 с.

69. Alexey Lastovetsky. шрС a Multi-Paradigm Programming Language for Massively Parallel Computers. // ACM SIGPLAN Notices, 31 (2): 13-20, February 1996.-P. 13-20.

70. Amnon Barak et. A Scalable cluster computing with Mosix for Linux: Institute of Computer Science. // The Hebrew University of Jerusalem, 1999.

71. Amon Barak and Oren Laadan. The MOSIX Multicomputer Operating System for High Performance Cluster Computinghttp://www.cs.huji.ac.il/rnosix).

72. Bazhanov S.E., Vorontsov M.M., Kutepov V.P., Shestakov D.A. Structural Analysis and Planning of Processes of Parallel Execution of Functional programs. // Journal of Computer and Systems Sciences International, Vol. 44, No. 6,2005.-P. 942-957.

73. Cheung D. W., Ng V. Т., Fu A. W., Fu Y. Efficient Mining of Association Rules in Distributed Databases. IEEE Transactions on Knowledge and Data Engineering, 8(6): P. 911-912,1996.

74. Dennis J.B. First version of data flow language. // In Proc. Colloque sur la Programmation, vol.19 (Lecture notes in computer science), 1974. P. 241-271.

75. Dubois D., Lang J., Parde H. Towards possibilistic logic programming. // Proceedings of the 8-th International Conference on Logic Programming 91. -Paris: The Mit Press, 1991. P. 581-595.

76. Foster Ian. Designing and Building Parallel Programs. 1995 (http://www.hensa.ac.uk/parallel/books/addison-wesley/dbpp) (http://rsusul.rnd.runnet.ru/ncube/design/dbpp/book-info.html).

77. Kotlyarov D.V., Kutepov V.P., and Osipov M.A. Flowgraph Stream Parallel Programming and Its Implementation on Cluster Systems. // Journal of Computer and Systems Sciences International, Vol. 44, No. 1,2005. P. 70-89.

78. Kutepov V., Falk V. Integrated tools for functional logical and data flow parallel programming and controlling parallel computations on computer systems. // Proceedings of International conference on parallel computing technologies, Novosibirsk, 1991.

79. Kutepov V., Falk V. Intellectual environment for computeraided programming. // Proceedings of Japan CIS symposium on knowledge based software engineering, Pereslavl-Zaleskiy, 1994.

80. Kutepov V.P., Lazutkin V.A., Liu Liang. The Extension of Petri Nets for the Description of Operational Semantics of Flowgraph Stream Parallel

81. Loidl H-W., et al. Comparing Parallel Function Languages: Programming Performance. // Kluwer Academic Publishers, 2003. 59 p.

82. Mary W. Hall, et al. Detecting Coarse-Grain Parallelism Using an Interprocedural Parallelizing Compiler (http://suif.stanford.edu/papers/mhall95a/paper.html).

83. Milner R. A Calculus of Communicating Systems. // LNCS vol.92, Springer Verlag,- 171 p.