Граф-схемное потоковое параллельное программирование (Граф-схемное потоковое параллельное программирование 2)

ГРАФ-СХЕМНОЕ ПОТОКОВОЕ ПАРАЛЛЕЛЬНОЕПРОГРАММИРОВАНИЕ И ЕГО РЕАЛИЗАЦИЯ НАКЛАСТЕРНЫХ СИСТЕМАХ 2004 г. Д.В. Котляров, В.П. Кутепов, М.А. ОсиповМосковский энергетический институт (технический университет)В статье описана реализация на кластерах система граф – схемного потокового параллельногопрограммирования, которая включает язык модульного визуального параллельногопрограммирования, инструментальные средства разработки программ и средства управленияпараллельным их выполнением на кластере.ВведениеПервая версия языка граф-схем, которая была создана в начале 70-х годов на волнеактивных исследований по параллелизму и параллельным системам, задумывалась как“мягкое” развитие структурных (блочно-схемных) форм описания последовательныхпрограмм с предполагаемой реализацией на многомашинных и (или) многопроцессорныхсистемах [1-3].Следующие принципиального характера требования ставились при формулировкеязыка:− модульный принцип построения параллельной программы, причем с возможностьюпрограммирования модулей как многовходовых-многовыходовых процедур напоследовательных языках программирования;− наглядное граф-схемное описание структуры параллельной программы в виде двухкомпонентов: граф-схемы и интерпретации, однозначно сопоставляющей каждомумодулю (блоку граф-схемы) подпрограмму (или процедуру) на соответствующемязыке программирования;− интерпретация связей между модулями как связей по данным (а не по управлению),правда, с таким ограничением, чтобы у корректных, т.е.

однозначных граф-схем [4]на каждом входе модуля не накапливалось более одного данного (естественноенаследование принципа выполнения любой команды или операторапоследовательной программы);− экспликация параллелизма как информационной независимости различных модулейграф-схемы.Уже первая попытка реализации такого граф-схемного модульного языкапараллельного программирования [5] на многомашинных комплексах М6000/М7000 попринципу децентрализованного управления оказалась вполне успешной, особенно в ссравнении с популярными в то время системами параллельных вычислений Сумма иМинимакс [6], позволявшими описывать параллелизм более примитивными иограниченными средствами.Затем эта же версия языка граф-схем была реализована в централизованном вариантена многомашинных комплексах СМ1/СМ2, причем в этой реализации существенное развитиеполучила система машинной поддержки процесса конструирования граф-схемныхпараллельных программ, их модификации и отладки.В [3] в язык граф-схем было введено простое, но весьма важное по практическимсоображениям расширение, касающееся векторного динамического параллелизма ивозможности его компактного параметрического схемного отражения.В работе [7] был сделан радикальный шаг в развитии граф-схемного языка,состоящий в интерпретации информационных связей между модулями как буферов с FIFO(первое поступившее данное считывается первым) дисциплиной их обслуживания.

Какследствие, пространственная (информационно-независимая) и основанная на временномРабота выполнена при поддержке РФФИ, проект 03-01-00588совмещении выполнения различных частей программы по принципу конвейера, формыпараллелизма могли быть одинаково представлены в граф-схемной модели. Утвердившийсязатем термин “потоковые вычисления” [8] объединяет эти различные формы параллелизма, аклассификационное разделение принципов функционирования параллельных систем по типуSIMD (один поток команд и многопотоков данных), MIMD (много потоков команд и много потоков данных) и др.

отражаетособенности реализации потоковых схем.Эта версия граф-схемного языка интересна еще и тем, что она базируется на строгомпонятии асинхронной вычислительной сети и описании процесса функционирования сетикак композиции процессов, индуцируемых конечно-автономной интерпретацией процессоввыполнения модулей граф-схемы. Естественно, что формализм сетей Петри оказалсянаиболее подходящей моделью для формального описания процесса выполнения граф-схем[7].Реализация этой версии граф-схемного языка, выполненная на многопроцессорных имногомашинных комплексах ЕС ЭВМ [9], – первая профессионально выполненнаяразработка системы параллельного программирования для подобной универсальнойорганизации вычислительных систем на базе серийных ЭВМ.

Во-первых, в этой реализациимаксимально использовались средства операционной системы ЕС ЭВМ для выполненияпрограмм модулей граф-схемы, для организации межмашинных обменов и др. Управлениепараллельным выполнением граф-схемных программ в этой реализации построено по строгодецентрализованному принципу, причем предварительно граф-схема разрезается на nподсхем, где n – количество машин в системе, таким образом, чтобы после “назначения”подсхем на n ЭВМ достигался определенный баланс их загрузки и загрузки каналов обменамежду машинами. Подобное статическое планирование параллельных вычислений, недопускающее динамического перераспределения работ между ЭВМ в процессе ихфункционирования, является ограничительным, однако оказалось достаточно простым вреализации.В [10] средства управления параллельным выполнением граф-схем были расширенывведением специальных программ реакции на отказы и сбои в системе и управленияреконфигурированием системы, это существенно повысило ее значение, особенно в сферевоенных приложений.

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

Активно ведутся работы по созданиюпрограммных средств для эффективной организации параллельных и распределенныхвычислений на кластерах. Кроме известных расширений последовательных языковпрограммирования (High performance C и C++, mpC, DVM, параллельный ФОРТРАН,CHARM++, Mosix и др.), сегодня широко используются стандартизированные API-средства(Application Parallel Interface) и библиотеки: MPI, PVM и др.

(см. сайт parallel.ru и др.).Внимательный анализ этого уже достаточно обширного арсенала программныхсредств для кластеров показывает [12], что они обычно базируются на расширениях языковпоследовательного программирования (Фортрана, C, C++ и др.), а в реализации дляорганизации параллельного выполнения программ используются специальные библиотекифункций, позволяющие описывать межпроцессное (и межкомпьютерное) взаимодействие.При этом за программистом остается основная работа не только в написании корректной и2эффективной программы, но также и ее реализация (распределение процессов накомпьютеры кластера). Из программных систем для кластеров, возможно, только в проектеMosix задача управления параллельными процессами рассматривается как центральная, отрешения которой прямо зависит эффективность работы кластера [13] (см.

также сайтmosix.tcs.huji.ac.il).В нашем проекте три главных составляющих, определяющих эффективностьпараллельных вычислений на кластере: язык программирования, инструментальная средаразработки параллельных программ и программные средства управления параллельнымвыполнением программ рассматриваются и реализуются комплексно.Раздел 1 статьи посвящен описанию разработанного языка граф-схемного потоковогопараллельного программирования, раздел 2 – описанию инструментальной средыпрограммирования на этом языке, в разделе 3 рассмотрена реализация управленияпараллельным управлением программ на кластерных системах, в разделе 4 описанапрограммная реализация системы граф-схемного потокового программирования длякластерных систем.1.

Язык граф-схемного потокового параллельногопрограммирования (ЯГСПП)ЯГСПП ориентирован на крупноблочное (модульное) потоковое программированиезадач, он также может эффективно применяться для программного моделированияраспределенных систем, систем массового обслуживания и др., информационные связимежду компонентами которых структурированы и управляются потоками данных,передаваемых по этим связям.Язык позволяет эффективно и единообразно представлять в программах три видапараллелизма:− параллелизм информационно-независимых фрагментов;− потоковый параллелизм, обязанный своим происхождением конвейерномупринципу обработки данных;− параллелизм множества данных, реализуемый в ЯГСПП через механизмтегирования, когда одна и та же программа или ее фрагмент применяются кразличным данным;Другими, важными с позиции программирования, особенностями ЯГСПП являются:− возможность визуального графического и текстового представленийпрограмм;− возможность простого структурирования программы и отражениядекомпозиционной иерархии при ее построении путем использованияотношения «схема-подсхема»;− использованиетрадиционныхпоследовательныхязыковприпрограммировании модулей.1.1 Графическая версия ЯГСППГраф-схемная параллельная программа (ГСПП) представляется в виде пары <ГС,I>,где ГС – граф-схема, I – интерпретация.Граф-схема или просто схема позволяет визуально представлять строящуюся измодулей программу решения задачи; интерпретация сопоставляет каждому модулюмножество подпрограмм, а связям между модулями – типы данных, передаваемых междуподпрограммами модулей в процессе выполнения ГСПП.Основным «строительным» блоком ГСПП является модуль, графическоепредставление которого приведено на рис.

1. Все входы и выходы модулей строготипизированы и разделены на группы (отдавая дань предыстории ЯГСПП, они называютсяконъюнктивными группами входов (КГВх) и конъюнктивными группами выходов (КГВых)3соответственно) и отражают структуру потоков данных, передаваемых междуподпрограммами модулей. Каждой КГВх модуля однозначно сопоставляется подпрограммана одном из последовательных языков программирования (C/C++, Pascal, Java и др.), причемперечисленные формальные параметры и их типы в задании подпрограммы должнысовпадать с порядком изображения (слева направо) входов КГВх и их типамисоответственно.