BC/NW 2008, №2 (13): 8.1

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

Приходько А.В., Филатов А.В., Черный Ф.О.

(Москва, Московский энергетический институт (Технический Университет), Россия)

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

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

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

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

1) каждый алгоритм необходимо реализовать в виде параллельной программы, что является весьма трудоёмким мероприятием;

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

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

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

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

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

На рис. 1 представлена схема комплекса по выбору лучшего алгоритма. Комплекс состоит из трёх частей:

- блок генерации алгоритмов решения пользовательской задачи;

- блок определения параметров кластерной вычислительной системы;

- блок определения лучшего алгоритма решения задачи.

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

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

В задачу блока генерации алгоритмов входит:

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

- выявление возможностей независимого выполнения тех или иных операций, то есть распараллеливание;

- формирование набора алгоритмов решения задачи пользователя на многопроцессорной вычислительной системе;

- формирование правил исполнения алгоритмов.

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

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

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

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

Наиболее распространёнными языками программирования кластеров, на сегодняшний день являются языки C и C++ и Fortran. Каждая ветвь параллельной программы описывается на этих языках как исходный текст отдельного последовательного процесса. Для обеспечения взаимодействия между ветвями программы в исходные тексты процессов включаются вызовы функций интерфейса MPI (Message passing interface) [1]. Вызывая функции MPI, процессы могут передавать друг-другу данные, синхронизироваться, выполнять некоторые настройки среды и т.п.

Программный комплекс ориентирован пока только на работу с языками C и C++, поддержку языка Fortran планируется включить позднее.

Программа формирования тестовых программ формирует:

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

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

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

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

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

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

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

Блок определения лучшего алгоритма решения задачи осуществляет оценку времени выполнения вычислений по каждому алгоритму путём имитации его программной реализации на кластерной системе.

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

Результатами работы блока определения лучшего алгоритма, являются:

- алгоритм наиболее быстрого выполнения пользовательской задачи;

- режим выполнения параллельной программы (распределение процессов) при котором достигается минимальное время выполнения алгоритма;

- оценочное время выполнения выбранного алгоритма.

Выбранный алгоритм, пользователь может реализовать в виде готовой параллельной программы. Перед запуском программы на выполнение на кластерной вычислительной системе, готовую программу можно предварительно испытать с помощью разработанного ранее моделирующего комплекса, описанного в [2].

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

ЛИТЕРАТУРА

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

2. Верстаков В.В., Филатов А.В. Программный комплекс для моделирования выполнения реальной параллельной программы на многопроцессорной вычислительной системе // Информационные средства и технологии: Труды Междунар. Конф. –М.: Янус-К, 2006. Т.2. С. 178-181.