Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

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

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Талалаев, Александр Анатольевич. Модели, алгоритмы и программно-инструментальные средства для организации конвейерно-параллельных вычислений на мультипроцессорных системах : диссертация ... кандидата технических наук : 05.13.11 / Талалаев Александр Анатольевич; [Место защиты: Ин-т програм. систем им. А.К. Айламазяна РАН].- Переславль-Залесский, 2012.- 112 с.: ил. РГБ ОД, 61 12-5/3508

Содержание к диссертации

Введение

Глава 1. Обзор технологий организации высокопроизводительных вычислений 8

1.1. Обзор аппаратных платформ 8

1.2. Обзор программных библиотек поддержки высокопроизводительных вычислений на МВУ 14

1.3. Обзор программно-инструментальных средств для организации вычислений намвс 19

1.4. Сравнение основных характеристик программно-инструментальных комплексов 24

1.5. Выводы и постановка задачи 25

Глава 2. Общие принципы построения комплекса инструментальных средств 27

2.1. Общая архитектура программного комплекса 27

2.2. Структурная модель ядра программного комплекса 30

2.3. Модель системы диспетчеризации 32

2.4. Модель представления прикладной задачи 37

2.5. Пользовательский интерфейс системы 39

2.6. Принципы расширения функциональных возможностей пс для решения прикладных задач 49

2.7. Основные выводы 63

Глава 3. Разработка и исследование системы диспетчеризации и модели вычислителя 65

3.1. Разработка и исследование системы диспетчеризации 65

3.2. Разработка и исследование модели вычислителей 72

3.3. Основные выводы 75

Глава 4. Реализация прикладных систем с использованием инструментальных средств и исследование эффективности комплекса 77

4.1. Библиотека модулей для решения прикладных задач 77

4.2. Тестирование на задаче поиска и распознавания объектов 82

4.3. Тестирование на задаче обработки изображений ДЗЗ 91

4.4. Тестирование на задаче контроля и диагностики подсистем ка 97

Заключение 104

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

Введение к работе

Актуальность работы

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

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

В настоящее время имеется несколько универсальных систем, которые можно рассматривать как комплекс инструментальных средств для разработки прикладных систем. К ним можно отнести такие системы как, например, HeNCE, GRADE, CODE, Triana, BMDFM, технологию Microsoft Workflow Foundation, ANSYS EKM, Kepler.

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

Вопросами организации высокопроизводительных вычислений занимались различные исследователи: Е. Валях, Прангишвили И.В. и Трахтенгерц Э.А. (распараллеливание в процессе трансляции), Гергель В.П., Воеводин В.В., Карцев М.А., Абрамов С.М. (динамическое распараллеливание Т-система) и др.

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

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

Основной целью работы является обеспечение достаточно высоких показателей алгоритмов конвейерно-параллельных вычислений по быстродействию при минимальных временных затратах на их разработку с использованием инструментальных средств. При этом учитывается возможность кроссплатформенной реализации с сохранением принципов универсализма, гибкости и расширяемости программного комплекса. Разработанные автором комплексные решения прошли апробацию в рамках проектов «Триада» и «Космос-НТ», обеспечив достаточно высокие показатели на отечественных вычислителях кластерного типа «СКИФ-Аврора ЮУрГУ» и «К-100» Межведомственного суперкомпьютерного центра РАН (МСЦ РАН).

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

Для достижения поставленной цели необходимо решить следующие задачи:

Исследовать существующие методы организации конвейерно-параллельных вычислений на мультипроцессорных вычислительных системах;

Разработать структурную модель комплекса инструментальных средств, удовлетворяющую принципам гибкости и расширяемости и позволяющую адаптировать разрабатываемое ПО к ряду аппаратных архитектур;

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

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

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

Результаты, выносимые на защиту:

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

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


Научная новизна работы:

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

Предметом научной новизны являются:

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

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

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

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

Программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоемких компьютерных технологий на базе мультипроцессорных вычислительных систем», шифр «ТРИАДА» (проект ПР5 «Разработка новых алгоритмов, принципов создания систем обработки изображений и другой информации от космических средств наблюдения, ориентированных на применение многопроцессорных вычислительных кластеров повышенной вычислительной мощности»);

Программы Союзного государства «Космос-НТ» (НИР «Разработка прототипа программной нейросетевой системы контроля телеметрической информации, диагностики подсистем космических аппаратов, обработки космических снимков»);

Государственного контракта №02.740.11.0526. «Разработка технологии интеллектуальной обработки информации в командно-измерительных системах космического назначения» (шифр заявки «2010-1.1-411-009-033»), 2010-2012гг.;

Проекта РФФИ 07-07-12029-офи "Создание интеллектуальной технологии для анализа данных и распознавания образов" (2007-2008гг.);

Проекта РФФИ № 09-07-00006-а "Исследование методов и создание теоретических основ информационной технологии обнаружения, распознавания, определения географического положения и прогнозирования поведения динамических целей" (2009-2011гг.);

Программы фундаментальных исследований Отделения РАН № 1 «Информационные технологии и методы анализа сложных систем»,
проект № 2.2 «Развитие методов интеллектуального управления на основе анализа потоков данных» (2009-2011гг.).

Государственного контракта № 07.514.11.4048 от 06 октября 2011 г. на тему «Разработка интеллектуальных методов автоматизированного обнаружения и предотвращения распределенных сетевых атак и их реализация в современных системах облачных вычислений» (2011-2012гг.).

Внедрение результатов работы. Основные результаты диссертационной работы были использованы при разработке программного комплекса «ППС ИНС» для НИЦЭВТ по проекту «Триада» (свидетельство на регистрацию программы для ЭВМ № 2010610208), разработке программной системы по проекту «Космос-НТ» Союзного государства (заявка на регистрацию программы для ЭВМ № 2011618769 от 18 ноября 2011) и разработке ”Комплекса программ инструментальных средств построения универсальной моделирующей среды для высокопроизводительной вычислительной системы «СКИФ»” для ОАО «Российские космические системы». Получен акт использования результатов диссертационной работы от НИИ КС им. А.А. Максимова от 12 января 2012 г.

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

Вторая международная научно-практическая конференция “Исследование, разработка и применение высоких технологий в промышленности“. 07-09.01.2006, Санкт-Петербург, Россия.

Научно-техническая конференция ФГУП "РНИИ КП", посвященной. 60-летию предприятия (10-12 октября 2006 г.).

9th International Conference “Pattern Recognition and image analysis: New Information Technologies” (PRIA-9-2008) (Nizhni Novgorod, 14-20.09.2008).

First Specialized Symposium “Space & Global Security of Humanity” (November 2-4, 2009, Amathus Beach Hotel, Limassol, Cyprus).

III Всероссийская научно-техническая конференция «Актуальные проблемы ракетно-космического приборостроения и информационных технологий» (1-3 июня 2010 года).

Кроме того, результаты работы докладывались и обсуждались на семинарах Исследовательского центра мультипроцессорных систем ИПС им. А.К. Айламазяна РАН в г. Переславль-Залесский (2005-2012).

Публикации. Основные результаты диссертационной работы изложены в 15 печатных работах, в числе которых 7 статей опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.

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

Обзор программных библиотек поддержки высокопроизводительных вычислений на МВУ

Системы NUMA (Non-Uniform Memory Access systems) состоят из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединяются с помощью высокоскоростного коммутатора, при этом поддерживается единое адресное пространство и аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. В случае, если аппаратно поддерживается когерентность кэшей во всей системе (обычно это так), говорят об архитектуре cc-NUMA (cache-coherent NUMA). Масштабируемость NUMA-систем ограничивается объемом адресного пространства, возможностями аппаратуры поддержки когерентности кэшей и возможностями операционной системы по управлению большим числом процессоров. На сегодняшний день максимальное число процессоров в cc-NUMA-системах может достигать 512 (серия SGI Altix 4700 [19]). При разработке прикладного ПО также следуют модели общей памяти.

Массивно-параллельные системы (МРР - massive parallel processing) обладают большим количеством процессоров и разделяемой памятью. Использующие подобную модель суперкомпьютеры построены как массив отдельных машин (узлов), взаимодействующих через высокоскоростные каналы связи. Каждый узел получает доступ только к локальной памяти, выполняемое параллельное приложение оказывается разделенным на ряд параллельно выполняемых слабо взаимодействующих процессов, обменивающихся информацией путем передачи и приема сообщений. Схематически систему с распределенной памятью можно представить следующим образом (рисунок 2).

Вычислительные кластеры представляют собой системы, состоящие из множества узлов, связанных коммуникационной средой, при этом обычно используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Infiniband, Myrinet) на базе шинной архитектуры или коммутатора. Каждый из узлов кластера имеет локальную память, общей оперативной памяти нет. В составе кластера могут быть узлы с различной архитектурой и производительностью. В случае, когда все узлы кластера имеют одинаковую архитектуру и производительность, кластер называют однородным, иначе — неоднородным (гетерогенным). Архитектура вычислительного кластера подобна суперкомпьютерам МРР, кластеры часто используются в качестве их дешевой альтернативы, поскольку могут быть построены на базе уже имеющихся в организации персональных компьютеров. Любой кластер можно рассматривать как единую аппаратно-программную систему, имеющую единую коммуникационную систему, единый центр управления и планирования загрузки. Часто в целях уменьшения стоимости кластера в качестве узлов используются доступные в данный момент компьютеры, имеющие разные характеристики, и, возможно, частично загруженные решением других задач. Программирование на кластерных системах, как правило, придерживается модели передачи сообщений (чаще всего - MPI).

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

Векторно-конвейерные процессоры или процессоры SIMD-архитектуры работают с одним потоком команд, содержащим векторные инструкции. Каждая векторная инструкция выполняет определенную арифметическую операцию одновременно для всех элементов вектора данных. Основным недостатком векторных процессоров является их высокая стоимость. Основным признаком параллельно-векторных систем (PVP, Parallel Vector Processing) является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично МРР). Эффективное программирование подразумевает векторизацию циклов (для достижения разумной производительности одного процессора) и их распараллеливание для одновременной загрузки нескольких процессоров одним приложением.

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

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

Структурная модель ядра программного комплекса

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

Решаемые задачи: выделение/освобождение памяти, мониторинг доступных ресурсов. Достоинства: должен повысить надежность системы и дать возможность работы в условиях ограниченных аппаратных ресурсов. Транспортный уровень - программная прослойка, предоставляющая интерфейс для реализации передачи данных (MPI и SharedMemory приведены как пример возможных реализаций такого интерфейса).

Достоинства: Используя различные реализации транспортного уровня, можно реализовать ПС как для систем кластерного типа, так и для мультипроцессорных систем с SMP архитектурой, работающих под управлением ОС Windows и Linux.

Менеджер ресурсов - модуль ядра, непосредственно занимающийся управлением имеющимися аппаратными ресурсами через интерфейсы, предоставляемые аппаратным уровнем.

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

Достоинства: реализация менеджера ресурсов повышает гибкость системы (не требуется перекомпиляция исходных кодов ядра для добавления новых типов данных).

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

Решаемые задачи: создание/удаление каналов, реализация различных стратегий передачи данных, блокирование каналов, синхронизация данных.

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

Менеджер модулей - обеспечивает взаимодействие внешних модулей посредством выделения/предоставления аппаратных ресурсов и каналов передачи. Инкапсулирует в себе менеджер каналов, лишая разработчиков внешних модулей потенциальной возможности написания «опасного» кода. Решаемые задачи: работа с динамическими библиотеками внешних модулей, загрузка/выгрузка внешних модулей, проведение их инициализации.

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

Управляющий модуль - модуль ядра, занимающийся приемом извне и выполнением управляющих команд, таких как «завершить работу всей системы», и др.

Достоинства: предоставляет единственное, безопасное средство для управления системой. Любой пользовательский интерфейс (веб, графическое Win32 приложение, консоль, и др.) должен лишь позаботиться о поддержке предоставляемого протокола.

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

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

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

Процесс диспетчеризации построен на системе управляющих команд. При этом, в связи с имеющимися ограничениями, определенными постановкой задачи, используется алгоритм, оперирующий лишь текущим состоянием системы. Прежде чем перейти к описанию принципов функционирования системы диспетчеризации, рассмотрим общий алгоритм работы системы. Алгоритм 1. Общий алгоритм функционирования системы 1) Чтение xml-файла с описанием решения задачи, чтение xml-описания каждого из требуемых для решения задачи модулей. 2) Передача вычислительному ядру списка модулей, которые необходимо загрузить. Равномерная загрузка модулей на вычислительных узлах МВС с учетом наложенных пользователем ограничений. 3) Инициализация каналов передачи данных. Первоначально все каналы находятся в отключенном состоянии. Установка связей переводит их в состояние ожидания. 4) Начальная инициализация всех модулей на заданных узлах МВС. Ядру передаются значения переменных, которые необходимо установить для каждого из загруженных модулей. 5) Запуск системы, передача данных через каналы, ожидание завершения работы всех модулей. 6) Завершение работы системы. Общая схема взаимодействия «Диспетчер управляющих команд» - -Вычислители - Модули в ходе решения прикладной задачи, представлена на рисунке 9. На данной схеме введены следующие обозначения: S - диспетчер управляющих команд, Wj- вычислитель, ассоциированный с узлом], піу- модуль і, загруженный на узле].

Разработка и исследование модели вычислителей

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

Введем некоторые обозначения для сущностей определенных в рамках системы: «Модуль» - объект, реализующий некоторую функцию обработки данных, значения аргументов реализованной функции определяются данными, поступающими на входы модуля по каналам передачи данных. Выходные значения, если они определены, передаются на выходы модуля; «Канал передачи данных» - объект, связывающий модули, использованные для решения прикладной задачи, обеспечивающий процесс пересылки данных между ними; «Схема обработки данных» - древовидная схема, которая позволяет задать произвольный набор модулей и связей между ними (каналов передачи данных), необходимых для решения прикладной задачи; «Вычислитель» - объект, копии которого существуют на каждом из доступных вычислительных узлов, принимает команды от системы диспетчеризации и выполняет их, отсылая планировщику уведомления о выполнении. Имеет пул потоков, в которых могут быть выполнены функции загруженных модулей; «Диспетчер управляющих команд» - объект, существующий в единственном экземпляре, хранит информацию о доступности на узлах модулей обработки, состоянии вычислителей (свободен/занят) и данных, готовых для обработки.

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

В качестве примера рассмотрим тестовую схему, содержащую 6 модулей (Ml, М2, МЗ, М4, М5, Мб), использующие три атомарных ресурса (с именами А, В и С) и 2 «составных» ресурса (поименованных как АВ и ВС). Каждый из модулей в данной схеме имеет один вход (с именем In ) или один выход (с именем Out ), ресурс АВ имеет поля с типами А и В , а ВС имеет поля типов В и С.

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

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

Наименование операции Графическое представление Краткое описание Прямое соединение(Direct) 1 А 1 А(DT) @ТА ИДИ ТА Операция буферизации данных, не выполняющая их дополнительной обработки. Может использоваться в случае прямого соединения модулей (выход/вход). Блоккопированияресурса(Сору) І АВк ) Р&/ \АВ Операция рассылки копий объекта на множество выходов. Блокразделенияресурса (Split) 1 АВ hf \ В Операция выделения составных частей ресурса и рассылки их получателям. Блокобъединения данных (Gather) АВ\/АВ Операция сборки в единый поток однотипных ресурсов приходящих по нескольким входам.

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

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

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

Тестирование на задаче обработки изображений ДЗЗ

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

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

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

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

Запуск модуля для обработки ресурса (заданное распределение START_PLUGIN_RES и динамическая балансировка START_PLUGIN_RES_DYN)

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

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

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

На этапе завершения работы системы, как корректного, по факту завершения счета задачи, так и по факту возникновения ошибок в ходе её выполнения, вычислителям передаются команды деинициализации: Останов модуля (STOP_PLUGIN) Команда останова модуля закрывает все каналы модуля и переводит его в неактивное состояние. Останов вычислителя (STOP_WORKER) Команда останова вычислителя производит деинициализацию вычислителя, очищая очереди команд и запросов на передачу данных.

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

Предложенный алгоритм диспетчеризации является «жадным» алгоритмом локально оптимального выбора применимых команд, но, не смотря на простоту, является достаточно эффективным решением, позволяющим задать ограничения на количество используемых аппаратных ресурсов МВС. Говоря об аналогичных системах, следует указать, что используемые в них принципы диспетчеризации, по мнению автора, уступают предложенному. Система CODE не имеет диспетчера нагрузки, поскольку является, по своей сути, системой кодогенерации. Технология Microsoft Workflow Foundation использует принцип очереди заданий без приоритетов, последовательно запуская

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