Содержание
ВВЕДЕНИЕ 3
ГЛАВА 1. МЕТОД ФЛОЙДА И СРЕДСТВА ДЛЯ ЕГО ОПТИМИЗАЦИИ 5
1.1 Технология программирования OpenMP 5
1.2 Технология MPI 6
1.3 Алгоритм Флойда для решения задачи поиска кратчайшего пути в графе 8
ГЛАВА 2. РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПОИСКА КРАТЧАЙШЕГО ПУТИ МЕТОДОМ ФЛОЙДА 11
2.1 Последовательный алгоритм Флойда 11
2.2 Распараллеливание алгоритма Флойда 12
ГЛАВА 3. РАЗРАБОТКА ПРОГРАММЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИЙ OPENMP И MPI 14
3.1 Реализация последовательного алгоритма Флойда 14
3.2 Реализация метода Флойда для OpenMP 15
3.3 Реализация метода Флойда для MPI 15
ГЛАВА 4. АПРОБАЦИЯ ПРОГРАММЫ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ. ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ 17
Рис.4. Компиляция программы на MPI 18
4.1 Результаты вычислительных экспериментов 19
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 22
ПРИЛОЖЕНИЕ 23
Выдержка из текста
Параллельные вычисления – современная многогранная область вычислительных наук, бурно развивающаяся и являющаяся наиболее актуальной в ближайшие десятилетия. Актуальность данной области складывается из множества факторов, и в первую очередь, исходя из потребности в больших вычислительных ресурсах для решения прикладных задач моделирования процессов в физике, биофизике, химии и других науках. К тому же, традиционные последовательные архитектуры вычислителей и схем вычислений в преддверии технологического предела. В то же время технологический прорыв в области создания средств межпроцессорных и межкомпьютерных коммуникаций позволяет реализовать одно из ключевых звеньев параллелизма – эффективное управление в распределении вычислений по различным компонентам интегрированной вычислительной установки.
Существуют различные способы реализации параллельных вычислений. Например, каждый вычислительный процесс может быть реализован в виде процесса операционной системы, либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса ОС.
Параллельные программы могут физически исполняться либо последовательно на единственном процессоре — перемежая по очереди шаги выполнения каждого вычислительного процесса, либо параллельно — выделяя каждому вычислительному процессу один или несколько процессоров (находящихся рядом или распределённых в компьютерную сеть).
Список использованной литературы
1. Белов В.В. Теория графов. — М.: Высшая школа, 1976- 268 с.
2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. // СПб.: БХВ-Петербург, 2002. — 608 с.
3. Гергель В.П. Теория и практика параллельных вычислений. // Интуит Бином. Лаборатория знаний. 2007. — 424 с.
4. Grama, A., Gupta, A., Kumar V. Introduction to Parallel Computing. // Harlow, England: Addison-Wesley, 2003, 2nd edn. — 656 p.
5. Quinn M.J Parallel Programming in C with MPI and OpenMP // New York, NY: McGraw-Hill, 2004. — 480 p.