Без темы
<<  Параллельные алгоритмы решения геофизических задач на многопроцессорных вычислителях Плоскостное моделирование в развивающей игре ТАНГРАМ  >>
Параллельный алгоритм расчета неоклассической модели межотраслевого
Параллельный алгоритм расчета неоклассической модели межотраслевого
Описание модели
Описание модели
Описание модели
Описание модели
Основная задача модели
Основная задача модели
Описание функций, участвующих в задаче
Описание функций, участвующих в задаче
Метод решения
Метод решения
N=50 A=25 M=10 => u ~ 40Mb
N=50 A=25 M=10 => u ~ 40Mb
Средства реализации до этапа распараллеливания
Средства реализации до этапа распараллеливания
Идеи распараллеливания
Идеи распараллеливания
Реализация идей распараллеливания
Реализация идей распараллеливания
Схема распараллеливания
Схема распараллеливания
Средства распараллеливания
Средства распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Результаты распараллеливания
Выводы
Выводы

Презентация: «Параллельный алгоритм расчета неоклассической модели межотраслевого баланса». Автор: Мударисов Ильдар. Файл: «Параллельный алгоритм расчета неоклассической модели межотраслевого баланса.ppt». Размер zip-архива: 174 КБ.

Параллельный алгоритм расчета неоклассической модели межотраслевого баланса

содержание презентации «Параллельный алгоритм расчета неоклассической модели межотраслевого баланса.ppt»
СлайдТекст
1 Параллельный алгоритм расчета неоклассической модели межотраслевого

Параллельный алгоритм расчета неоклассической модели межотраслевого

баланса

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

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

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

– производственная функция, описывающая выпуск продукта j-й отраслью, принадлежащей ФПГ?, где – векторы продуктов и первичных ресурсов, затрачиваемых в ФПГ ? для выпуска j-го продукта

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

Рассматриваемая модель подробно описана в работе: Э.В. Автухович, С.М. Гуриев, Н.Н. Оленев, А.А. Петров, И.Г. Поспелов, А.А. Шананин, С.В. Чуканов «Математическая модель экономики переходного периода», вычислительный центр РАН, Москва 1999. Приведем краткое описание модели.

N – число чистых отраслей A – число финансово-промышленных групп (ФПГ) M – число видов первичных ресурсов

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

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

4 Основная задача модели

Основная задача модели

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

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

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

6 Метод решения

Метод решения

Метод одновременного решения пары двойственных задач [1]

Метод сопряженных градиентов [1]

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

7 N=50 A=25 M=10 => u ~ 40Mb

N=50 A=25 M=10 => u ~ 40Mb

Оценка размерности задачи

Число чистых отраслей N возьмем равным 50, финансово-промышленных групп (ФПГ) – 25, а первичных ресурсов – 10. Тогда dimU = 4765110 ~ 4.5x220, dimW = 6391385 ~ 6x220. Если каждая координата вектора u представляется одним числом типа double (8 bytes), то для хранения вектора u необходимо порядка 40 Mb.

Хранение такого объема информации в оперативной памяти вполне реально для современных ЭВМ. Если же мы захотим разместить в памяти градиенты всех функций ограничений, то потребуется матрица размером dimU x dimW. Ее объем оценивается в 2x105 Gb. Это совершенно нереальный для хранения объем информации.

8 Средства реализации до этапа распараллеливания

Средства реализации до этапа распараллеливания

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

9 Идеи распараллеливания

Идеи распараллеливания

Возможны следующие пути разработки параллельного алгоритма:

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

10 Реализация идей распараллеливания

Реализация идей распараллеливания

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

11 Схема распараллеливания

Схема распараллеливания

По множителю Главная (master) задача запускает дочерние (slave) задачи, посылает им необходимые аргументы и множитель(-и) , получает результаты и выбирает лучший вариант. Расчета градиента квадратичной функции Главная (master) задача запускает N_task дочерних (slave) задач, посылает им векторы u, wk, множество Ik и индексы 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 задачах.

12 Средства распараллеливания

Средства распараллеливания

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

13 Результаты распараллеливания

Результаты распараллеливания

Результаты полученные при решении задачи с N=10, A=5, M=5. Приводится график временной зависимости выполнения одного объема вычислений при различном числе запускаемых задач для разного количества узлов кластера

Вывод: Использование второго процессора на одном узле уменьшает время в 2 раза, что является максимально возможным. Использование двух узлов уменьшает время счета в 3.5 раза при максимально возможном в 4 раза. Использование 3-х, 4-х, 5-ти узлов дает примерно одинаковое ускорение в 5.5 - 6.5 раз

14 Результаты распараллеливания

Результаты распараллеливания

Результаты полученные в XPVM при решении задачи с N=4, A=4, M=2. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится структура работы программы во времени

Оптимальный вариант: master + 9 slave задач

Неоптимальный вариант: master + 19 slave задач

Вывод: Чрезмерное увеличение числа задач ведет к простою процессоров во время ожидания посылаемых данных

15 Результаты распараллеливания

Результаты распараллеливания

Результаты полученные в XPVM при решении задачи с N=4, A=4, M=2. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится характеристика работы запускаемых задач во времени

Оптимальный вариант: master + 9 slave задач

Неоптимальный вариант: master + 19 slave задач

Вывод: При оптимальном подборе числа запускаемых задач удается достичь более эффективной загрузки всех процессоров одновременно. То есть достигается равномерная загрузка процессоров.

16 Результаты распараллеливания

Результаты распараллеливания

Результаты полученные в XPVM при решении задачи с N=10, A=5, M=5. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится структура работы программы во времени

Оптимальный вариант: master + 9 slave задач

Неоптимальный вариант: master + 19 slave задач

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

17 Результаты распараллеливания

Результаты распараллеливания

Результаты полученные в XPVM при решении задачи с N=10, A=5, M=5. Запуск на 5 двухпроцессорных узлах кластера PARC. Приводится характеристика работы запускаемых задач во времени

Оптимальный вариант: master + 9 slave задач

Неоптимальный вариант: master + 19 slave задач

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

18 Выводы

Выводы

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

«Параллельный алгоритм расчета неоклассической модели межотраслевого баланса»
http://900igr.net/prezentacija/geometrija/parallelnyj-algoritm-rascheta-neoklassicheskoj-modeli-mezhotraslevogo-balansa-97387.html
cсылка на страницу

Без темы

105 презентаций
Урок

Геометрия

40 тем
Слайды
900igr.net > Презентации по геометрии > Без темы > Параллельный алгоритм расчета неоклассической модели межотраслевого баланса