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

Талалаев, Александр Анатольевич

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

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

кандидата технических наук: Талалаев, Александр Анатольевич
город: Переславль-Залесский
год: 2012
специальность ВАК РФ: 05.13.11

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

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

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

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

МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНО-ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ОРГАНИЗАЦИИ КОНВЕЙЕРНО-ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ

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

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

1 2 5(7? 20:2

Переславль-Залесский 2012

005018401

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

Научный руководитель

профессор, доктор технических наук Хачумов Вячеслав Михайлович

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

д.ф.-м.н., доц., зав. лаб. ИЦСА, ИПС им. А.К. Айламазяна РАН Знаменский Сергей Витальевич

к. т. н., с.н.с. Лаборатории 0-2, ИСА РАН Тихомиров Илья Александрович

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

ОАО Научно-исследовательский центр электронной вычислительной техники (ОАО «НИЦЭВТ»)

Защита состоится 27 апреля 2012 г. в 13.00 часов на заседании Диссертационного совета ДМ 002.084.01 при Федеральном государственном бюджетном учреждении науки Институте программных систем им. А.К. Айламазяна Российской академии наук по адресу: 152020, Ярославская обл., Переславский район, с. Веськово, ул. Петра Первого, д. 4а.

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

Автореферат разослан Л » Ы&О. 012 г.

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

Пономарева С.М.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1 - Сравнение основных характеристик программно-инструментальных средств разработки параллельного ПО__

Разработ анная ПС Kepler ANSYS ЕКМ Microsoft Workflow Foundation CODE

1 Параллелизм исполнения задачи + + + + +

2 Конвейеризация исполнения задачи + + - - -

3 Поддержка модулей системы с внутренним параллелизмом + - - - -

4 Возможность исполнения задачи на SMP-apxin-einype + + + + +

5 Возможность исполнения задачи с использованием КВУ + + + + +

6 GUI с поддержкой визуального программирования + + + + +

7 Кроссплатформенность + + + - -

8 Открытый исходный код + + - - +

9 Язык (платформа) реализации С/С++ Java Java .NET Tel

Информация о ряде систем, которые можно отнести к программно-инструментальным средствам разработки параллельного (или конвейерно-параллельного) ПО, таких как HeNCE, GRADE, Triana, BMDFM не включена в результаты сравнительного анализа, поскольку данные системы не превосходят приведенные в таблице по функциональным возможностям.

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

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

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

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

Рисунок 1 - Общая архитектура программно-инструментального комплекса

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

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

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

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

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

Рисунок 2 - Структурная модель ядра ПС

Приведенная схема демонстрирует основные компоненты ядра системы, наиболее важными из которых являются:

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

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

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

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

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

Из особенностей вычислительного ядра можно выделить следующее:

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

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

Приведена информация о предлагаемом формате данных, использованном для описания БЗ. В качестве основы выбран формат xml-описаний. Основными для системы являются декларативные описания решаемой прикладной задачи и описание модулей обработки. Общий формат оптеаниязадачи имеет следующий_вид^_______

у VIT| "1 „ , .„TT-j П И ' I : ' ' г; ... . л " 9 > *

. .. , ^ '! И W 4- . Т /Vï . . ' . . . II t

! .'7:: ' ' ; : . >

> ... ..., ; . . i ^ - .' ¿V . .. . rt H л Il If О "

— ... . « « -ч . / . . -, .

Структурно, описание задачи состоит из двух основных секций:

1. Секции описания модулей (определена тегом <тос1и!ез>), которые необходимо загрузить вычислительному ядру для решения прикладной задачи, с указанием параметров их инициализации.

2. Секция описания каналов передачи данных (определена тегом <сЬаппе1з>), указывающая, каким образом необходимо связать между собой модули.

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

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

Г<?зш1~т7егвТоп-" 1Г0"* ёпсосЙ-пд»'Ч*г-8"?> "

• <лю(3и1е рага11е1="" пос1есоипШ1п="" пос!есоип'Шах="">

<с!ез1дпег с1а55=" "> \ <гаос1и1ес1езс пате="" с1е.5с="" />' <^агс1езс паше=" " <1езс="" /> ссЬаппеЫегс пате=" " с1езс="" /> </с1ез1дпег> \

<init> •

<уаг пате="" type=""></var> ! </л.ш.1:> !

<сЬаппе1з>

<сЬаппе1 г.уре="" пате="" с]а1аЬуре="" £'агде(:=""/> </с1га:ппе1з> . )

• </тос1и1е>

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

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

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

Рисунок 3 - Пример сети Петри, демонстрирующей прикладную задачу

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

• ModuleA - непараллельная реализация поставщика ресурсов;

• ModuleB - модуль обработчик данных, имеющий параллельную реализацию;

• ModuleC - непараллельная реализация потребителя ресурсов.

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

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

Указанный граф S является конечным автоматом, описывающим основные состояния работы системы диспетчеризации, и может быть формально определен как S = (Q, X, 8, q0, F) где:

Q = {Start, Init, Update, Select, Apply, Wait, End} - конечное множество состояний автомата, описывающих фазы функционирования диспетчера задач;

X = Я CMDJSENDED, EVENT_RECEIVED, CMD_SELECTED, NO_A PPLICABLE_CMDS, CMD S_NOT_AVAIL ABLE} - входной алфавит KA, указанные входные символы подаются на вход КА после вычисления предикатов, оценивающих внутреннее состояние системы диспетчеризации (описываемое таблицами занятости вычислителей, списками доступных и применяемых в настоящий момент команд)

• X — лямбда-переход, оценка внутреннего состояния системы диспетчеризации не производится;

• СМГ)_8ЕМ)ЕП - выбранная (применимая) команда передана вычислителю;

• ЕУЕ1ЧТ_КЕСЕ1УЕВ - получено подтверждение от вычислителя о выполнении команды или создании ресурса подлежащего обработке;

• СМО_8Е1_ЕСТЕ1) - выбрана применимая команда;

• ЫО_АРРЦСАВЬЕ_СМЛ8 - нет применимых команд;

• С МI) 8_Ы О Т_ А V АIЬ А В Ь Е - список исполняемых в настоящий момент команд пуст.

5 : QxX —» Q - функция перехода КА;

q0 = Start - начальное состояние автомата;

F = {End} - множество терминальных состояний КА.

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

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

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

Алгоритм 1. Общий алгоритм функционирования системы

• Чтение хт1-файла с описанием решения задачи, чтение хш1-описания каждого из требуемых для решения задачи модулей.

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

• Инициализация каналов передачи данных. Первоначально все каналы находятся в отключенном состоянии. Установка связей переводит их в состояние ожидания.

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

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

• Завершение работы системы.

Общая схема взаимодействия «Диспетчер управляющих команд» <->Вычислители<->Модули, в ходе решения прикладной задачи, представлена на рисунке 5. На данной схеме введены следующие обозначения: Б - диспетчер управляющих команд, ^^ - вычислитель, ассоциированный с узлом т^ -модуль I, загруженный на узле].

Рисунок 5 - Схема взаимодействия компонент системы диспетчеризации

Данная схема определяет связи следующих типов:

1) «Диспетчер управляющих команд «-»Вычислители» - передача управляющих команд от диспетчера и подтверждений от вычислителей.

2) «Вычислитель<->Модули» и «Вычислитель<->Вычислитель» - данные связи позволяют обеспечить параллельно-конвейерную обработку данных средствами ядра системы в случае использования непараллельных модулей, реализуя межмодульное взаимодействие.

3) «Модуль<->Модуль» - связи, описывающие взаимодействие копий параллельных модулей находящихся на разных узлах.

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

Алгоритм 2. Общий алгоритм работы системы диспетчеризации

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

2) Построить список применимых команд

3) Если применимых команд нет, переход к пункту 7

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

5) Передать выбранную приоритетную команду вычислителю

6) Обновление внутреннего состояния системы, далее переход к п. 2

7) Если есть команды, переданные вычислителям, но еще не завершенные в текущем состоянии:

7.1) Ждать подтверждения от вычислителей

7.2) Обновление внутреннего состояния системы, далее переход к п. 2

8) Завершение работы.

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

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

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

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

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

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

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

В частности, в рамках нескольких научно исследовательских проектов, с использованием ПС были построены прикладные системы решающие следующие задачи:

• задача поиска и классификации объектов на изображениях, базирующейся на аппарате искусственных нейронных сетей. Данная задача, помимо реализации ИНС, включает в себя набор модулей предобработки (включая и параллельные реализации) и использует практически все функциональные возможности, предоставляемые разработанным инструментальным комплексом;

• задача обработки снимков ДЗЗ;

• задача контроля и диагностики подсистем космического аппарата.

Результаты тестирования в виде графиков производительности

представлены в таблицах 2-5 и на рисунках 6-8 соответственно.

1) Прикладная задача поиска и распознавания объектов

Таблица 2 - Результаты тестирования производительности (ускорение счета)

Кол-во вычислительных потоков на узел

1 2 3 4 5 6 7 8

1 - - - - - - - -

2 1,00 2,19 2,72 2,77 2,93 2,96 2,94 2,96

Кол-во узлов 3 1,20 3,67 3,59 4,73 4,59 4,61 4,58 4,49

КВУ 4 1,26 3,60 3,34 4,81 5,17 5,09 4,83 5,03

5 1,23 3,43 3,60 5,46 5,78 5,92 5,69 5,56

6 1,22 3,60 3,08 5,38 4,13 4,73 5,35 3,46

Ускорение

Я 5,00-7.00 ■ 3,00-5,00 Я 1,00-3,00

8 7

5 4

3 Потоков на узел

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

Рисунок 6 - График эффективности параллельной реализации Тестирование показывает, что конвейеризация счета в пределах одного вычислительного узла дает прирост производительности почти в три раза. Наивысшая производительность достигнута при запуске счета задачи в конфигурации 5 узлов КВУ, по шесть вычислительных потоков на каждом, при этом максимальное достигнутое ускорение составляет 5.92.

2) Прикладная задача обработки изображений ДЗЗ

Таблица 3 - Результаты тестирования производительности (ускорение счета)

Кол-во вычислительных потоков на узел

1 2 3 4 5 6 7 8

Кол-во узлов КВУ 1 1,00 1,03 1,03 1,03 1,04 1,04 1,03 1,03

2 2,00 2,05 2,05 2,05 2,05 2,05 2,05 2,05

3 2,93 2,96 2,96 2,97 2,96 2,96 2,95 2,95

4 3,08 3,10 3,09 3,67 3,66 3,10 3,09 3,67

5 3,78 3,82 3,82 3,74 3,81 3,82 3,82 3,81

6 5,52 5,65 5,56 5,59 5,65 5,61 5,62 5,64

Рисунок 7 - График эффективности параллельной реализации

Ускорение

■ 5,00-7.00 я 3,00-5,00 т 1,00-3,00

7,00

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

8 7

3 Потоков

на узел

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

3) Прикладная задача контроли и диагностики подсистем КА Таблица 4 - Результаты тестирования производительности (ускорение счета)

Кол-во вычислительных потоков на узел

1 2 3 4 5 6 7 8

1 1,00 1,97 2,43 2,51 2,55 2,55 2,59 2,58

2 1,77 3,45 3,87 4,59 4,73 4,80 4,78 4,79

Кол-во узлов 3 2,42 4,54 5,57 6,39 6,47 6,44 6,45 6,47

КВУ 4 3,11 5,63 6,35 7,09 7,10 7,21 7,13 7,23

5 3,60 5,73 7,35 7,90 8,15 8,25 8,06 8,26

6 3,99 6,33 8,50 8,21 8,12 8,04 8,08 8,10

Ускорение

* 7,00-5,00

* 5,00-7,00 ■ 3,00-5,00 Ш 1,00-3,00

9,00 7,00 5,00 3,00 1,00

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

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

Заключение содержит основные результаты и выводы по диссертационной работе.

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

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

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

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

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

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

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

работы из списка, рекомендованного ВАК РФ

1. Виноградов А.Н., Калугин Ф.В., Недев М.Д., Погодин C.B., Талалаев A.A., Тищенко И.П., Фраленко В.П., Хачумов В.М. Выделение и распознавание локальных объектов на аэрокосмических снимках. -Авиакосмическое приборостроение, 2007, №9, с.39-45. (лично автором -1с.)

2. Ватутин В.М., Круглов A.B., Сашов A.A., Заднепровский В.Ф., Недев М.Д., Талалаев A.A., Фраленко В.П., Хромов О.В., Хачумов В.М., Снегирев В.М. Использование нейронных сетей и средств распараллеливания для высокопроизводительной обработки данных. -Информационно-измерительные и управляющие системы, 2007, №7, т.5, с.48-53. (лично автором -1 с.)

3. Талалаев A.A. Особенности архитектуры параллельной программной системы распознавания графических образов на основе искусственных нейронных сетей - «Нейрокомпьютеры: разработка, применение», 2008, №9, с.43-51.

4. Константинов К.А., Талалаев A.A., Тищенко И.П., Хачумов В.М. Концепция архитектуры нейросетевой системы контроля, диагностики и обработки изображений космического назначения - Авиакосмическое приборостроение, 2009, №5, с.39-47. (лично автором - 3 с.)

5. Недев М.Д., Талалаев A.A., Тищенко И.П., Хачумов В.М. Задачи распознавания, географической привязки и наблюдения объектов на основе анализа полутоновых снимков - Авиакосмическое приборостроение, 2009, №12, с. 19-24. (лично автором-2 с.)

6. Талалаев A.A. Организация конвейерно-параллельных вычислений для обработки потоков данных - Информационные технологии и вычислительные системы, 2011, №1, с.8-13.

7. Хачумов В.М. Талалаев A.A. Технические характеристики кластерных вычислителей и анализ эффективности параллельных программных

средств обработки потоков данных - Авиакосмическое приборостроение, 2011, №12, с.3-17 (лично автором-4 с.)

другие работы

8. Талалаев A.A., Тищенко И.П., Фраленко В.П., Хачумов В.М. Анализ эффективности применения искусственных нейронных сетей для решения задач распознавания, сжатия и прогнозирования. Искусственный интеллект и принятие решений, 2008, №2, с.24-33.

9. Талалаев A.A., Тищенко И.П., Хачумов М.В. Выделение и кластеризация текстовых и графических элементов на полутоновых снимках. -Искусственный интеллект и принятие решений, 2008, №3, с.72-84.

10. Виноградов А.Н., Коданев И.В., Талалаев A.A., Хачумов В.М. Программная система для распознавания графических образов с помощью моделей искусственных нейронных сетей. - Высокие технологии, фундаментальные и прикладные исследования, образование. Сборник трудов Второй международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности". 07-09.01.2006, Санкт-Петербург, Россия. / Под ред. А.П. Кудинова, Г.Г. Матвиенко, В.Ф. Самохина. СПб.: Изд-во Политехи, ун-та, Т. 6:, 2006, с. 6.

И. Виноградов А.Н., Коданев И.В., Талалаев A.A., Тищенко И.П., Хачумов В.М., Щербаков A.B. Библиотека нейронных сетей для распознавания графических образов на кластерном вычислительном устройстве. - Сб. трудов 2-ой Международной научн.-пракгической конференции «Исследование, разработка и применение высоких технологий в промышленности» (07-09.02.2006, Санкт-Петербург) - Санкт-Петербург: Издат.-во Политехнического университета, 2006, с.8-10.

12. Круглов A.B., Ватутин В.М., Заднепровский В.Ф., Талалаев A.A. Применение нейронных сетей и средств распараллеливания для высокоскоростной обработки потоков данных. - Тезисы докладов научно-технической конференции ФГУП "РНИИ КП", посвященной. 60-летию предприятия (10-12 октября 2006 г.) - М.: ФГУП "РНИИ КП", 2006, с.79-80.

13. Talalaev A.A., Tishchenko I.P., Fralenko V.P., Khachumov V.M.. Neural methods in aerospace systems. - 9th International Conference "Pattern Recognition and image analysis: New Information Technologies" (PRIA-9-2008): Conference proceedings. (Nizhni Novgorod, 14-20.09.2008) - H. Новгород, издательство "Диалог Культур", т. 2, с. 193-196.

14. Khachumov V.M., Talalaev A.A., Tishenko I.P., Fralenko V.P., Emelyanova J.G., Konstantinov K.A., Pogodin S.V. Program neural network system of telemetric information control, spacecraft subsystems diagnostic and space images processing. - First Specialized Symposium "Space & Global Security of Humanity" (November 2-4, 2009, Amathus Beach Hotel, Limassol, Cyprus).

15. Круглов A.B., Ватутин B.M., Попов C.B., Заднепровский В.Ф., Талалаев A.A., Хачумов В.М. Методы контроля и диагностики космических подсистем с применением суперкомпьютерных технологий -тезисы трудов III Всероссийской научно-технической конференции «Актуальные проблемы ракетно-космического приборостроения и информационных технологий» (электронный сборник, 1-3 июня 2010 года).

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

61 12-5/3508

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

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

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

МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНО-ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ОРГАНИЗАЦИИ КОНВЕЙРНО-ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ

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

машин, комплексов и компьютерных сетей»

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н., профессор В.М. Хачумов

Переславль-Залесский 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..................................................................................................................................3

ГЛАВА 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

СПИСОК ЛИТЕРАТУРЫ.....................................................................................................105

Введение

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

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

Вопросами организации высокопроизводительных вычислений занимались различные исследователи: Е. Валях [1], Прангишвили И.В. [2] и Трахтенгерц Э.А. [3,4] (распараллеливание в процессе трансляции), Гергель В.П. [5,6], Воеводин В.В. [7,8], Карцев М.А. [9], Абрамов С.М. [10-12] (динамическое распараллеливание Т-система) и др.

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

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

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

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

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

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

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

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

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

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

ориентированных на применение многопроцессорных вычислительных кластеров повышенной вычислительной мощности»);

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

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

внедрено в Научно-исследовательском институте космических систем им. А. А. Максимова.

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

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

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

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

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

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

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

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

Первая глава диссертационной работы посвящена обзору аппаратных и программных платформ, предназначенных для организации высокопроизводительных вычислений. Приведена информация о существующих на сегодняшний день программных комплексах, предоставляющих собой высокоуровневые инструментальные средства для проектирования и поддержки исполнения прикладных программ, функционирующих в параллельном и конвейерно-параллельном режиме, выполнен анализ их основных характеристик. При построении обзора были использованы материалы [8, 13,14,15,16] и ДР-

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

Существует множество вариантов классификации параллельных архитектур [17]. Согласно классификации Флинна, имеются два основных класса параллельных ЭВМ с крупнозернистым параллелизмом:

• SIMD (Single Instruction - Multiple Data) - одиночный поток команд и множественный поток данных. В таких ЭВМ выполняется единственная программа, но каждая команда обрабатывает массив данных. Это соответствует векторной форме параллелизма.

• MIMD (Multiple Instruction - Multiple Data) - множественный поток команд и множественный поток данных. В таких ЭВМ одновременно и независимо друг от друга выполняется несколько программных ветвей, обменивающихся данными. Такие системы обычно называют многопроцессорными.

MIMD-3BM имеют две разновидности: ЭВМ с общей (SMP) и распределенной (МРР) памятью. Нечто среднее между SMP и МРР представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом МРР. При поддержке команд обработки векторных данных говорят о векторно-конвейерных процессорах, которые, в свою очередь, могут объединяться в PVP-системы с использованием общей или распределенной памяти. Также все большую популярность в последнее время приобретают идеи комбинирования различных архитектур в одной системе и построения неоднородных систем, также как и использование специализированных вычислителей

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

1.1.1. Многопроцессорные системы с SMP-архитектурой

Архитектура SMP (symmetric multiprocessors) является наиболее распространенной на сегодняшний день. Данная архитектура представляет собой многопроцессорные вычислительные системы с общей памятью, в которых все процессоры обладают равной производительностью, являются равноправными при доступе к общей памяти и время доступа к памяти является одинаковым. Общая схема систем с SMP-архитектурой представлена на рисунке 1.

Рисунок 1 - Схематический вид SMP-архитектуры

Ведущие производители выпускают многопроцессорные системы, стремясь предоставить пользователям программное окружение, доступное в среде традиционных однопроцессорных компьютеров. На сегодняшний день основными производителями процессоров — Intel и AMD дальнейшее увеличение числа ядер процессоров признано как одно из приоритетных направлений увеличения производительности. Освоено производство 4-ядерных процессоров для компьютеров «домашнего» сегмента, а также 6-ядерных в серверных системах. По статистике на январь 2012-го года, лишь около 5% персональных компьютеров пользователей сети steam [18], снабжены одноядерными процессорами. При разработке ПО для данной архитектуры следуют модели общей памяти.

1.1.2. Системы с неоднородным доступом к памяти (NUMA)

Системы NUMA (Non-Uniform Memory Access systems) состоят из однородных

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

Похожие работы

Информатика, вычислительная техника и управление
05.13.00