работа (стр. 5 из 7)
- Инициализация генератора псевдослучайных чисел номером процесса и текущим временем.
- Вычисление шага, с которым ведется генерация чисел.
- Параллельный внутренний цикл, в котором вычисляется случайная точка, значение функции в этой точке и накапливается частичная сумма. В цикле каждый процесс совершает, в среднем, totpt / totproc итераций (totproc – количество запущенных процессов, totpt – количество генерируемых точек). В таблице 3.2.1 показан пример распределения итераций цикла по процессам для 6-ти процессорной группы (totproc = 6) и totpt = 20:
Таблица 3.2.1.
| Процессы | ||||||
| 0 | 1 | 2 | 3 | 4 | 5 | |
| Итерации | 1 | 2 | 3 | 4 | 5 | 6 |
| 7 | 8 | 9 | 10 | 11 | 12 | |
| 13 | 14 | 15 | 16 | 17 | 18 | |
| 19 | 20 | - | - | - | - | |
- Синхронизация всех процессов.
- Объединение частичных сумм всех процессов.
- Вычисление корневым процессом значения интеграла.
- Синхронизация процессов.
- Широковещание всем процессам из корневого процесса значения интеграла.
- Увеличение числа генерируемых точек для следующего прохода внешнего цикла.
- Проверка условия выхода. Если ложь – прервать внешний цикл, если истина – продолжить внешний цикл с увеличенных количеством генерируемых точек.
- Возвращение функцией полученного значения интеграла.
2. Алгоритм, в основе которого лежит идея сужения интервала интегрирования для каждого процесса (процессорный интервал), реализован в функции Integral1DMK_par1(…). В этом алгоритме, как и в предыдущем, генерация чисел осуществляется с некоторым шагом равным отношению интервала интегрирования L к количеству генерируемых точек. Здесь каждый процесс вычисляет интеграл на своем участке (частичный интеграл), а затем эти значения объединяются операцией редукции. Это позволяет, как и в предыдущем алгоритме, по мере уменьшения шага, добиваться равномерного распределения чисел по оси координат, а также точнее изучить поведение функции на узком интервале. Как следствие – увеличение сходимости метода, а также повышение точности вычислений.
В этом алгоритме каждый процесс выполняет следующие основные шаги:
- Получение количества запущенных процессов, получение процессом своего номера.
- Вычисление переменных, определяющих рабочие интервалы каждого процесса.
- Начало внешнего цикла.
- Инициализация переменных, содержащих значение интеграла на двух соседних итерациях (для проверки условия выхода).
- Инициализация генератора псевдослучайных чисел номером процесса и текущим временем.
- Вычисление шага, с которым ведется генерация чисел.
- Внутренний цикл, в котором вычисляется случайная точка, значение функции в этой точке и накапливается частичная сумма.
- Вычисление процессом частичного интеграла на узком промежутке.
- Увеличение числа генерируемых точек для следующего прохода внешнего цикла.
- Синхронизация всех процессов.
- Объединение частичных интегралов всех процессов.
- Синхронизация процессов.
- Широковещание из корневого процесса интеграла на L всем процессам.
- Проверка условия выхода. Если ложь – прервать внешний цикл, если истина – продолжить внешний цикл с увеличенных количеством генерируемых точек.
- Возвращение функцией полученного значения интеграла.
3. Алгоритм, в основе которого лежит идея сужения интервала интегрирования для каждого процесса и вычисление полного интеграла на этом участке, реализован в функции Integral1DMK_par2(…). В этом алгоритме, как и в предыдущих, генерация чисел осуществляется с некоторым шагом равным отношению интервала интегрирования L к количеству генерируемых точек. Здесь каждый процесс вычисляет интеграл на своем участке до тех пор, пока не получит значения с заданной точностью, а затем эти значения объединяются операцией редукции после завершения внешнего цикла. Это позволяет, как и в предыдущих алгоритмах по мере уменьшения шага, добиваться равномерного распределения чисел по оси координат, а также точнее изучить поведение функции на узком интервале. Кроме того, обмен сообщениями осуществляется только один раз. Как следствие – увеличение сходимости метода, повышение точности вычислений и уменьшение времени вычислений на некоторых классах функций.
В этом алгоритме каждый процесс выполняет следующие основные шаги:
- Получение количества запущенных процессов, получение процессом своего номера.
- Вычисление переменных, определяющих рабочие интервалы каждого процесса.
- Начало внешнего цикла.
- Инициализация переменных, содержащих значение интеграла на двух соседних итерациях (для проверки условия выхода).
- Инициализация генератора псевдослучайных чисел номером процесса и текущим временем.
- Вычисление шага, с которым ведется генерация чисел.
- Внутренний цикл, в котором вычисляется случайная точка, значение функции в этой точке и накапливается частичная сумма.
- Вычисление процессом частичного интеграла на узком промежутке.
- Увеличение числа генерируемых точек для следующего прохода внешнего цикла.
- Проверка условия выхода. Если ложь – прервать внешний цикл, если истина – продолжить внешний цикл с увеличенных количеством генерируемых точек.
- Синхронизация процессов.
- Редукция полных интегралов на всех процессорных интервалах.
- Возвращение функцией полученного значения интеграла.
Временные диаграммы синхронных вычислительных процессов с независимыми ветвями приведены на рис. 3.2.3.
Еще раз подчеркнем, что для увеличения сходимости метода существенную роль играет, состав последовательности псевдослучайных чисел или, иными словами, ее качество.
| Рис. 3.2.3 |
3.3. Эксперимент. Анализ эффективности
некоторых из реализованных алгоритмов
Были проведены исследования эффективности разработанных алгоритмов на кластере MPI, с компонентами: процессор – Pentium 1 Ггц, ОЗУ – 128 Мб, сеть – Fast Ethernet.
В экспериментах тестировалась подынтегральная функция . Пределы интегрирования составляли a = 0, b = 1e6. По результатам тестирования были получены кривые 3.3.1 и 3.3.2.В таблице 3.3.1 приведены результаты тестирования алгоритмов на различных функциях. Сравнивались результаты вычисления на 1 и 5 процессорных системах
Таблица 3.3.1
| Функция | a | b | t, с (1 проц.) | t, с (5 проц.) |
 | 2 | 4 | 0,001784 | 0,007947 |
| sinx/x | 0,0000001 | 1 | 0,000555 | 0,002694 |
| x3 | -100 | 100 | 75,140435 | 7,556625 |
 | 0 | 3 | 39,392135 | 15,766564 |
 | 0 | 100000 | 6,454987 | 2,638202 |
| 100 | -0,0010000 | 1000 | 0,004833 | 0,00334 |
| | 0 | 1000000 | 131,795787 | 20,773000 |
По результатам экспериментов были сделаны следующие выводы:
1. Алгоритм 1 работает наиболее эффективно со сложными функциями в широком диапазоне L. В то время как остальные заметно уступают ему в работе с такими функциями.
2. Для небольших функций в небольших пределах L 3-ий алгоритм работают быстрее других, т.к. содержит только одну операцию обмена данными. Для того же класса функций 1-ый алгоритм проигрывает, т.к. время, затраченное на обмен данными оказывается больше времени вычислений.
Таким образом, для вычислений интегралов могут быть использованы все три алгоритма – в зависимости от класса функции и пределов интегрирования.
ЗАКЛЮЧЕНИЕ
В заключении хотим отметить следующее.