ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 004.75
МЕТОД МУЛЬТИАГЕНТНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ИНТЕЛЛЕКТУАЛЬНЫХ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
© 2007 г. Член-корреспондент РАН И.А. Каляев1, Э.В. Мельник1
Статья посвящена решению актуальной проблемы повышения эффективности применения многопроцессорных вычислительных систем. Предлагается подход, направленный на снижение доли ручного труда при подготовке решения сложных задач на многопроцессорных вычислительных системах с различной архитектурой, позволяющий снизить временные затраты на этапе разработки параллельной программы за счет его автоматизации. Важной составной частью реализации предложенного подхода является децентрализованный метод распределения вычислений по ресурсам многопроцессорных вычислительных систем на базе мультиагентного взаимодействия, описание и результаты исследования которого приведены в статье.
ВВЕДЕНИЕ
В последнее время многопроцессорные вычислительные системы (МВС) становятся все более популярными. Каждый уважающий себя университет или крупная фирма считают своим долгом приобрести какую-либо МВС, как правило кластерную. При этом исходят из тезиса, что быстрая машина должна быстро решать все задачи. Но после того как МВС установлена и запущена в эксплуатацию (что в свою очередь требует значительных временных и финансовых усилий), оказывается, что быстро решать задачи на МВС не всегда получается. Более того, выясняется, что многие задачи решаются с использованием МВС значительно дольше, чем с использованием однопроцессорной ЭВМ (ОЭВМ). Объясняется данная ситуация достаточно просто - время решения задачи состоит из четырех этапов: 1) разработка математической модели задачи, 2) разработка алгоритма ее решения, 3) разработка программы выполнения алгоритма, 4) реализация программы на том или ином вычислителе (рис. 1).
'ра
'рп
'рв
Рис. 1. Этапы решения задачи на ЭВМ: гмм - время разработки математической модели задачи, гра - время разработки алгоритма, /рп - время разработки программы, грв - время реализации вычислений
1 Научно-исследовательский институт многопроцессорных вычислительных систем Южного федерального университета, Таганрог.
Если сравнить полный баланс времени решения одной и той же задачи на ОЭВМ и МВС, то можно прийти к следующему выводу. Время этапа 1 - разработки математической модели -в обоих случаях одинаково. Время этапов 2 и 3 - разработки алгоритма и программы - для ОЭВМ значительно меньше времени тех же этапов для МВС, поскольку в последнем случае требуется выполнение достаточно сложных процедур распараллеливания. Более того, финансовые затраты на выполнение этапов 2 и 3 для МВС оказываются на порядок выше тех же затрат для ОЭВМ, поскольку для разработки параллельного алгоритма и параллельной программы на его основе требуется привлечение высококвалифицированных программистов, знающих не только программные средства МВС, но и ее внутренние архитектурные особенности. Наконец, время выполнения этапа 4 на МВС меньше, чем на ОЭВМ, однако этот выигрыш, как правило, оказывается существенно меньше проигрыша во времени при выполнении этапов 2 и 3.
Таким образом, если посчитать общий баланс времени решения задачи на ОЭВМ и МВС, то, как правило, суммарное время выполнения всех этапов (рис. 2) для ОЭВМ оказывается меньше, чем для МВС.
,ОЭВМ гОЭВМ гОЭВМ ¿ОЭВМ
ОЭВМ!-—-.---1---1-
МВС
МВС МВС
1рп 'ПИ
рв
Рис. 2. Суммарное время решения задачи на ОЭВМ и МВС
Безусловно, есть задачи, решение которых на МВС дает существенный выигрыш по сравнению с ОЭВМ. Это такие задачи, для которых суммарный выигрыш во времени, достигаемый на этапах разработки алгоритма и программы для ОЭВМ, будет меньше проигрыша во времени реализации на ОЭВМ по сравнению с МВС, т.е. в случае, когда
ОЭВМ ^ МВС рн рн '
где /рВ - время этапа реализации вычислении на ОЭВМ; - время этапа реализации вы-
числений на МВС.
Примером таких задач могут служить задачи обработки потоков данных, когда одна и та же задача должна решаться многократно при различных исходных данных, например, задачи обработки радиолокационной информации, обработки видеоинформации, метеопрогноза и т.д.
,мвс .мвс мвс ,мвс,мвс»мвс
'мм 'ра 'рп {рв 'рв *рв
МВС I-'-'-■-1-1-'
Рис. 3. Сравнение времени многократного решения задачи на ОЭВМ и МВС
В этом случае, один раз выполнив этапы разработки алгоритма и программы, можно получить существенный временной выигрыш при многократной реализации вычислений на МВС (рис. 3).
ПРОБЛЕМА СОЗДАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ПРОГРАММ
Для обеспечения использования МВС при решении широкого класса задач необходимо каким-то образом уменьшить временные затраты на выполнение этапов разработки параллельного алгоритма и программы для МВС.
В настоящее время для разработки параллельных алгоритмов и программ широко используются следующие подходы [1-4]:
- подход на базе модели передачи сообщений,
- подход, основанный на использовании распараллеливающих компиляторов,
- подход, основанный на использовании языков высокого уровня, в которых параллельность, взаимодействие и синхронизация не явны,
- подход на базе параллелизма по управлению с передачей сообщений.
Данные подходы различаются по степени автоматизации, используемым моделям параллелизма и эффективности получаемых в конечном итоге программ. На их базе реализован ряд средств и технологий параллельного программирования, например библиотеки MPI, PVM, средства HPF, технология ОрепМР, среда трС.
Анализ перечисленных подходов показал, что в настоящее время эффективность параллельных программ напрямую зависит от доли ручного труда, т.е. эффективность средств автоматизации разработки параллельных программ весьма низка. Кроме того, перечисленные подходы к разработке параллельных программ не обеспечивают достаточную эффективность организации вычислительного процесса на МВС с неоднородной структурой, например на кластерах, у которых ПУ обладают различной вычислительной мощностью [3]. Существуют также серьезные проблемы с переносимостью параллельных программ, разработанных с помощью описанных средств.
Как следует из сказанного выше, этап разработки параллельного алгоритма решения задачи на МВС - это наиболее интеллектуальный этап, который плохо формализуем, и во многом его успешное выполнение зависит от искусства пользователя. На данном этапе выполняется разработка алгоритма в соответствии с имеющейся математической моделью и выделение в нем параллельных фрагментов, которые либо очевидны для человека, либо могут быть выделены только человеком. Существующие средства позволяют автоматически распараллелить только определенные конструкции программы (в основном циклы в соответствии с моделью параллелизма по данным). Распараллеливание на уровне процессов (подзадач) выполняется вручную.
Этап разработки параллельной программы для МВС предполагает выполнение таких работ, как объединение подзадач алгоритма и размещение вычислений на ресурсах целевой МВС. Основой успешного выполнения указанных работ являются следующие факторы: доскональное знание архитектуры целевой МВС, причем следует отметить, что важно "знать" особенности архитектуры именно в момент запуска программы (например, какие ПУ в текущий момент времени работают, а какие вышли из строя); детальное представление входной информации (параллельного алгоритма), необходимое для учета особенностей архитектуры МВС [2]; нали-
чие эффективных методов распределения вычислений на ресурсах МВС (выполняющих объединение подзадач и размещение вычислений), способных работать с входной информацией, представленной с высокой детализацией.
ПРИНЦИПЫ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Обобщая изложенное выше, можно сделать вывод, что в общем случае выполнение этапов разработки параллельного алгоритма и параллельной программы подразумевает следующую последовательность действий [2, 5]: 1) разбиение задачи на минимальные относительно независимые подзадачи (partitioning); 2) установление связей между подзадачами (communication); 3) объединение подзадач в целях минимизации коммуникаций (agglomeration); 4) распределение укрупненных подзадач по ПУ (mapping); 5) программирование ПУ МВС.
Первые два пункта следует отнести к этапу разработки параллельного алгоритма, а последние три - к этапу разработки параллельной программы.
Как отмечено выше, разработка параллельного алгоритма (т.е. реализация первого и второго пунктов) - это трудно формализуемый процесс, который ложится на плечи пользователя. Результатом этого процесса должно быть некоторое формальное представление алгоритма в некой универсальной форме. В то же время процесс разработки параллельной программы (т.е. реализации пунктов 3,4 и 5) может быть алгоритмизирован и, соответственно, автоматизирован. При этом реализацию пунктов 3, 4 и 5 целесообразно поручить самой МВС, поскольку она лучше всего "знает" свои текущие функциональные и коммуникационные возможности. Более того, если некоторые ПУ МВС вышли из строя, то эта информация также будет доступна в первую очередь самой МВС, т.е. МВС будет обладать полной информацией, необходимой для реализации пунктов 3 и 4. Что касается пункта 5, то он может быть достаточно легко автоматизирован, если в памяти МВС будут храниться заранее подготовленные программные компоненты для реализации возможных подзадач, распределенных на данный ПУ.
С учетом приведенных выше соображений процесс создания параллельного алгоритма и параллельной программы может быть представ-
Рис. 4. Диаграмма процесса создания параллельного алгоритма и параллельной программы
лен в виде диаграммы (рис. 4). Параллельный алгоритм создается человеком с использованием инструментальных средств. Результатом этого процесса должно быть представление алгоритма в некой универсальной форме, доступной "для понимания" МВС. Иными словами, параллельный алгоритм должен быть описан (представлен) в виде неких универсальных конструкций (языка), элементы которых описывают подзадачи и связи между ними. Весь дальнейший процесс по "трансляции" этих конструкций в программы, реализуемые отдельными ПУ МВС, может быть
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.