работа (стр. 1 из 7)
| Белорусский Государственный Университет | ||
| Факультет радиофизики и электроники | ||
| Кафедра информатики | ||
| Разработка и анализ эффективности программы | ||
| нахождения интегралов методом Монте-Карло | ||
| на кластере MPI | ||
| Курсовая работа | ||
| Выполнил: | ||
| студент 4 группы 3 курса | ||
| Строев В.Г. | ||
| Научный руководитель: | ||
| доцент Шпаковский Г.И. | ||
| г. Минск, 2004 | ||
ОГЛАВЛЕНИЕ
| ВВЕДЕНИЕ……………………………………………………………... | 3 |
| Раздел 1. Многопроцессорные системы. cтандарт MPI………………………………………... | 4 – 11 |
| 1.1. Организация и эффективность параллельных ЭВМ………. | 4 – 6 |
| 1.2. Разновидности многопроцессорных систем……………...... | 6 – 8 |
| 1.3. Техническая реализация параллельных ЭВМ……….……... | 8 – 9 |
| 1.4. Системы программирования для многопроцессорных систем. Стандарт MPI………………………………………... | 9 – 11 |
| Раздел 2. Метод Монте-Карло……………………………... | 12 – 15 |
| 2.1. Применение метода статистического моделирования…….. | 12 – 13 |
| 2.3. Способы получения случайных чисел……………………… | 13 – 14 |
| 2.4. Идея и суть метода Монте-Карло........................................... | 14 – 15 |
| Раздел 3. Алгоритмы вычисления интегралов методом Монте-Карло……………………........ | 16 – 27 |
| 3.1. Определенный интеграл……………………………………... | 16 – 18 |
| 3.2. Параллельные алгоритмы вычисления...…………………… | 18 – 25 |
| 3.3. Эксперимент. Анализ эффективности некоторых из реализованных алгоритмов………………………………….. | 25 – 27 |
| Заключение………………………………………………………… | 28 |
| Литература………………………………………………………….. | 29 |
| ПриложениЯ………………………………………………………... | 30 – 41 |
ВВЕДЕНИЕ
Классическое понимание алгоритма включает в себя в неявном виде утверждение о том, что процедура, которая может быть названа алгоритмом, имеет последовательный пошаговый характер. Поскольку человек, который решает задачу, и ЭВМ, построенная по классической схеме, выполняют программы вычислений последовательно, то и в информатике на первых порах рассматривались только последовательные методы вычислений.
Однако развитие архитектуры ЭВМ привело к появлению структур, в которых вычислительный процесс может протекать по нескольким ветвям параллельно. Параллелизм возник естественным образом, как средство увеличения производительности вычислительных машин. Идея параллелизма была технически реализована в многопроцессорных системах, однородных средах, локальных вычислительных сетях и в ряде других аппаратных решений.
Появление технических средств, способных организовать параллельное протекание вычислительного процесса, поставило две задачи. Одна из них – создание специальных программных средств для записи параллельных процессов в форме, которую может использовать операционная система вычислительной машины, системы или сети, чтобы фактически организовать параллельный процесс. Появление этой задачи породило новое направление в программировании – параллельное программирование.
Другая задача была связана с созданием специальных методов решения задач, ориентированных на параллельную реализацию, поиском численных методов, которые допускали бы распараллеливание вычислительных процедур.
Прежде всего, специалистов привлекли методы, опирающиеся на идею независимых статистических испытаний. Их еще называют методами Монте-Карло. Главное преимущество применения метода Монте-Карло в параллельных вычислениях состоит в том, что вычислительные процессы не зависят друг от друга, обеспечивая наибольший выигрыш во времени по сравнению с другими методами [5].
Цель данной работы – нахождение алгоритмов вычисления интегралов методом Монте-Карло, без обменов сообщениями между процессами на этапе накопления статистического материала.
Раздел 1. Многопроцессорные системы.
Стандарт MPI
1.1. Организация и эффективность параллельных ЭВМ
Под параллельной ЭВМ понимают ЭВМ, состоящую из множества связанных определенным образом вычислительных блоков, которые способны функционировать совместно и одновременно выполнять множество арифметико-логических операций, принадлежащих одной задаче (программе) [8].
Классифицировать параллельные ЭВМ можно по различным критериям: виду соединения процессоров, способу функционирования процессорного поля, области применения и т.п.
Однако наиболее употребительная классификация параллельных ЭВМ была предложена Флинном [8, 9] и отражает форму реализуемого ЭВМ параллелизма. Основными понятиями классификации являются «поток команд» и «поток данных». Под потоком команд упрощенно понимают последовательность команд одной программы. Поток данных – это последовательность данных, обрабатываемых одной программой.
Согласно классификации Флинна имеется четыре больших класса ЭВМ:
1) ОКОД – Одиночный поток Команд – Одиночный поток Данных (SISD – Single Instruction – Single Data). Это последовательные ЭВМ, в которых выполняется единственная программа, т.е. имеется только один счетчик команд и одно арифметико-логическое устройство;
2) ОКМД – Одиночный поток Команд – Множественный поток Данных (SIMD – Single Instruction – Multiple Data). В таких ЭВМ выполняется единственная программа, но каждая ее команда обрабатывает много чисел. Это соответствует векторной форме параллелизма;
3) МКОД – Множественный поток Команд – Одиночный поток Данных (MISD – Multiple Instruction – Single Data). Подразумевается, что в данном классе несколько команд одновременно работает с одним элементом данных, однако эта позиция классификации Флинна на практике не нашла применения;
4) МКМД – Множественный поток Команд – Множественный поток Данных (MIMD – Multiple Instruction – Multiple Data). В таких ЭВМ одновременно и независимо друг от друга выполняется несколько программных ветвей, в определенные промежутки времени обменивающихся данными. Такие системы обычно называют многопроцессорными. Далее, в работе будут рассматриваться только многопроцессорные ЭВМ.
Вопрос об эффективности параллельных ЭВМ возникает на разных стадиях исследования и разработки ЭВМ. Следует различать эффективность параллельных ЭВМ в процессе их функционирования и эффективность параллельных алгоритмов [8].
В зависимости от стадии разработки полезными оказываются различные характеристики эффективности ЭВМ. Одной из главных является ускорение r параллельной системы, которое определяется выражением:
 | (1.1.1) |
где T1 – время решения задачи на однопроцессорной системе, а Tn – время решения той же задачи на n-процессорной системе.
Если обозначить W = Wск + Wпр, где W – общее число операций в задаче, Wпр – число операций, которые можно выполнять параллельно, а Wск – число скалярных (нераспараллеливаемых) операций; t – время выполнения одной операции, то закон Амдала будет иметь вид [8, 9]:
 | (1.1.2) |
где a = Wск / W – удельный вес скалярных операций.
Закон Амдала определяет принципиально важные для параллельных вычислений положения:
1. Ускорение вычислений зависит как от потенциального параллелизма задачи (величина 1-a), так и от параметров аппаратуры (число процессоров n).
2. Предельное ускорение вычислений определяется свойствами задачи и не может превосходить 1/a при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи и весьма чувствительно к изменению величины a.
Тем не менее закон Амдала не учитывает временных затрат на обмен сообщениями между процессорами. А ведь во многих случаях эти потери могут не только снизить ускорение вычислений, но и замедлить вычисления по сравнению с однопроцессорным вариантом.
Поэтому, необходимо ввести величины Wс – количество передач данных и tc – время одной передачи данных. Тогда модернизированный закон Амдала, называемый сетевым законом Амдала, будет выглядеть следующим образом: | (1.1.3) |
где с = Wc·tc / W·t = cA·cT – коэффициент сетевой деградации вычислений определяет объем вычислений, приходящийся на одну передачу данных (по затратам времени). При этом cA определяет алгоритмическую составляющую коэффициента деградации, обусловленную свойствами алгоритма, а cT – техническую составляющую, которая зависит от соотношения технического быстродействия процессора и аппаратуры сети.