Параллельный алгоритм расчета неоклассической модели межотраслевого баланса Мударисов И.М., студент 4 курса кафедры вычислительной математики, математический ф-т УдГУ, г. Ижевск

Описание модели N – число чистых отраслей A – число финансово-промышленных групп (ФПГ) M – число видов первичных ресурсов – производственная функция, описывающая выпуск продукта j-й отраслью, принадлежащей ФПГ, где – векторы продуктов и первичных ресурсов, затрачиваемых в ФПГ для выпуска j-го продукта – вогнутая функция полезности, описывающая спрос населения (индекс потребления), где – вектор конечного потребления продуктов населением. Рассматриваемая модель подробно описана в работе: Э.В. Автухович, С.М. Гуриев, Н.Н. Оленев, А.А. Петров, И.Г. Поспелов, А.А. Шананин, С.В. Чуканов «Математическая модель экономики переходного периода», вычислительный центр РАН, Москва Приведем краткое описание модели.

Описание модели

Основная задача модели Экономическая интерпретация задачи – это максимизация функции полезности (индекса потребления), при выполнении балансовых соотношений.

Описание функций, участвующих в задаче

Метод решения Метод одновременного решения пары двойственных задач [1] Метод сопряженных градиентов [1] [1] – Б.Т. Поляк «Введение в оптимизацию», «Наука», Москва 1983.

Оценка размерности задачи Число чистых отраслей N возьмем равным 50, финансово- промышленных групп (ФПГ) – 25, а первичных ресурсов – 10. Тогда dimU = ~ 4.5x2 20, dimW = ~ 6x2 20. Если каждая координата вектора u представляется одним числом типа double (8 bytes), то для хранения вектора u необходимо порядка 40 Mb. N=50 A=25 M=10 => u ~ 40Mb Хранение такого объема информации в оперативной памяти вполне реально для современных ЭВМ. Если же мы захотим разместить в памяти градиенты всех функций ограничений, то потребуется матрица размером dimU x dimW. Ее объем оценивается в 2x10 5 Gb. Это совершенно нереальный для хранения объем информации.

Mathematica 4.1 Пакет Mathematica использовался для формирования тестовых примеров. Основная ценность реализации в точности получаемых результатов. С++ Основная ценность реализации – это создание основы для параллельного варианта численной реализации методов. Программа на языке C++ характеризуется следующим: исходные данные хранятся на внешнем носителе в файлах, результаты каждой итерации (новые приближения прямых и двойственных переменных и значение целевых функций) включаются в файл отчета. Ведется учет времени по итерациям. Использование языка C++, а не С, обусловлено удобством работы с файлами. Средства реализации до этапа распараллеливания

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

Реализация идей распараллеливания Первый путь привел к распараллеливанию основного алгоритма за счет множителя Второй путь выявил следующее: расчет градиента квад- ратичной функции в методе сопряженных градиентов занимает в работе всей программы более 90% времени. Определим причины этого факта. Размерность градиента равна dimW. Вычисление одной координаты градиента требует вычисления значений квадратичной функции в двух точках, что требует поряд- ка dimU*dimW операций. Получаем объем вычислений порядка dimW*dimU*dimW. Никакой другой фрагмент программной реализации не требует такого объема вычислений. В результате распараллеливания, именно этот путь при- вел к значительному ускорению времени расчета модели.

Схема распараллеливания По множителю Главная (master) задача запускает дочерние (slave) задачи, посылает им необходимые аргументы и множитель(-и), получает результаты и выбирает лучший вариант. Расчета градиента квадратичной функции Главная (master) задача запускает N_task дочерних (slave) задач, посылает им векторы u, w k, множество I k и индексы Start_k, Finish_k. Slave задача рассчитывает часть градиента, начиная со Start_k-ой координаты по Finish_k-ую. Результатом работы slave задачи являются (Finish_k -Start_k) координат искомого градиента. Во время работы slave задач master работает подобно им. Значение (Finish_k -Start_k) определяется числом запускаемых задач N_task, а именно, (Finish_k -Start_k) = [dimW / (N_task+1)] Так как объем вычислений для всех slave задач получается равным, то прием результатов осуществляется просто по порядку, а не по мере окончания вычислений в slave задачах.

Средства распараллеливания В течение 3-го, 4-го курсов учебы на математическом факультете УдГУ студенты кафедры вычислительной математики изучают курсы «Математическая экономика» и «Параллельные алгоритмы». В рамках первого курса была предложена сама задача, а в рамках второго – средства параллельного программирования, в частности PVM (Parallel Virtual Machine). Основная часть программы написана на языке C++ Параллельная часть программы реализована с помощью PVM Отладка и мониторинг производились с помощью XPVM Запуск программ осуществлялся на кластере PARC Кластер включает в себя 5 узлов на каждом из которых имеется 2 процессора Intel Pentium III 800 МГц

Результаты распараллеливания Вывод: Использование второго процессора на одном узле уменьшает время в 2 раза, что является максимально возможным. Использование двух узлов уменьшает время счета в 3.5 раза при максимально возможном в 4 раза. Использование 3-х, 4-х, 5-ти узлов дает примерно одинаковое ускорение в раз Результаты полученные при решении задачи с N=10, A=5, M=5. Приводится график временной зависимости выполнения одного объема вычислений при различном числе запускаемых задач для разного количества узлов кластера

Результаты распараллеливания Оптимальный вариант: master + 9 slave задач Неоптимальный вариант: master + 19 slave задач Вывод: Чрезмерное увеличение числа задач ведет к простою процессоров во время ожидания посылаемых данных Результаты полученные в XPVM при решении задачи с N=4, A=4, M=2. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится структура работы программы во времени

Результаты распараллеливания Оптимальный вариант: master + 9 slave задач Неоптимальный вариант: master + 19 slave задач Вывод: При оптимальном подборе числа запускаемых задач удается достичь более эффективной загрузки всех процессоров одновременно. То есть достигается равномерная загрузка процессоров. Результаты полученные в XPVM при решении задачи с N=4, A=4, M=2. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится характеристика работы запускаемых задач во времени

Результаты распараллеливания Оптимальный вариант: master + 9 slave задач Неоптимальный вариант: master + 19 slave задач Вывод: В оптимальном варианте число запускаемых задач равняется числу используемых процессоров кластера. Результаты полученные в XPVM при решении задачи с N=10, A=5, M=5. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится структура работы программы во времени

Результаты распараллеливания Оптимальный вариант: master + 9 slave задач Неоптимальный вариант: master + 19 slave задач Вывод: Данные результаты показывают эффективность распараллели- вания расчета градиента квадратичной функции. Видно, что работа остальной части программы занимает значительно меньше времени. Результаты полученные в XPVM при решении задачи с N=10, A=5, M=5. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится характеристика работы запускаемых задач во времени

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