Дополнительные вопросы и задания

1.     Запрограммируйте параллельную программу, реализующую задачу “об обедающих философах”. Для реализации потребуется пять процессоров. Суть задачи следующая: пять философов сидят за круглым столом. Они проводят жизнь, чередуя приемы пищи и размышления. В центре стола находится большое блюдо спагетти. Философам, чтобы съесть порцию спагетти, требуется две вилки. Вилок всего пять: между каждой парой философов лежит по одной вилке. Каждому философу дозволительно пользоваться только вилками, которые лежат рядом с ним (слева и справа). Задача – написать программу, моделирующую поведение философов. Программа должна избегать ситуации, в которой все философы голодны, то есть ни один из них не может взять себе две вилки (например, когда каждый философ держит по одной вилке и не хочет отдавать ее). Раз вилок всего пять, то одновременно могут есть не более, чем двое философов. Два сидящих рядом философа не могут есть одновременно. Предположим, что периоды раздумий и приемов пищи различны – для их имитации в программе можно использовать генератор случайных чисел. Имитация поведения каждого философа может быть разбита на следующие блоки: поразмыслить, взять вилки, поесть, отдать вилки. Вилки являются разделяемым ресурсом. Запрограммируйте остановку алгоритма по достижении контрольного времени. Выведите в файл результатов общее время реализации параллельного алгоритма, количество приемов пищи для каждого философа, постройте схему работы алгоритма. Например:

2.     Запрограммируйте параллельную программу, реализующую задачу “о восьми ферзях”. Нужно расставить на шахматной доске восемь ферзей так, чтобы они не атаковали друг друга. разработайте программу, которая строит все 92 решения этой задачи. Для реализации используйте модель “управляющий-рабочие”. Пусть управляющий процессор распределяет по другим процессорам варианты восьми начальных позиций ферзей, какие те должны проверить. Обнаружив частичное решение, рабочий процесс должен передать его управляющему. Программа должна найти все решения и завершить работу. Управляющий процесс должен все решения записать в файл результатов.

3.     Запрограммируйте параллельную программу, реализующую задачу о расстановке пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них. Для реализации используйте модель “управляющий-рабочие”.

4.     Запрограммируйте параллельную программу, реализующую задачу “о коммивояжере”. Эта классическая задача имеет практическое применение, например, при планировании обслуживания населения городским общественным транспортом. Дано городов и симметричная матрица . Значением элемента является расстояние между городами и . Коммивояжер начинает путь в городе 1 и должен посетить по одному разу каждый город, закончив свой путь снова в городе 1. Требуется найти путь, минимизирующий расстояние, которое придется проехать коммивояжеру, а результат сохранить в векторе . Значением вектора должна быть перестановка целых чисел от 1 до , соответствующая порядку посещения городов коммивояжером. Разработайте параллельную программу для решения поставленной задачи, используя модель “управляющий-рабочие”.

5.     Запрограммируйте параллельную программу, реализующую задачу клеточный автомат “игра в жизнь”. Многие биологические и физические системы можно смоделировать в виде набора объектов, которые с течением времени циклически взаимодействуют и развиваются. Некоторые простейшие системы можно моделировать с помощью клеточных автоматов. Основная идея разделить пространство физической или биологической задачи на отдельные клетки. каждая клетка – это конечный автомат. После инициализации все клетки сначала совершают один переход в новое состояние, затем второй переход и т.д. Результат каждого перехода зависит от текущего состояния клетки и ее соседей. Дано двухмерное поле клеток. Каждая клетка либо содержит организм (жива), либо пуста (мертва). Каждая клетка имеет восемь соседей, которые расположены сверху, снизу, слева, справа и по четырем диагоналям от нее. Игра “жизнь” происходит следующим образом. Сначала поле инициализируется: определяются мертвые и живые клетки (для этой цели в программе можно использовать генератор случайных чисел). Затем каждая клетка проверяет состояние свое и своих соседей и изменяет свое состояние в соответствии со следующими правилами:

a.       живая клетка, возле которой меньше двух живых клеток, умирает от одиночества;

b.       живая клетка, возле которой есть две или три живые клетки, выживает еще на одно поколение;

c.       живая клетка, возле которой находится больше трех живых клеток, умирает от перенаселения;

d.       мертвая клетка, рядом с которой есть ровно три живых соседа, оживает.

Этот процесс повторяется заданное число шагов (поколений). Поле требуется разделить на полосы или блоки клеток, при этом каждая полоса или блок клеток обрабатываются отдельным процессором. Для реализации алгоритма потребуется организовать передачу данных о состоянии пограничных клеток.

6.     Запрограммируйте параллельную программу, реализующую алгоритм “решето Эратосфена” для нахождения всех простых чисел меньше . Решетом Эратосфена называют следующий способ. Выпишем подряд все целые числа от 2 до . Первое простое число 2. Запомним его, а все большие числа, кратные 2, вычеркнем. Первое из оставшихся чисел 3. запомним его, а все большие числа, кратные 3, вычеркнем. Первое из оставшихся чисел 5 (4 уже вычеркнуто как кратное 2), запомним его, а все большие числа кратные 5, вычеркнем и т.д.

7.     Запрограммируйте параллельную программу, реализующую алгоритм метода Монте-Карло [16] для вычисления площади круга . Методы Монте-Карло – это общее название группы методов для решения различных задач с помощью случайных последовательностей. Эти методы (как и вся теория вероятностей) выросли из попыток людей улучшить свои шансы в азартных играх. Этим объясняется и тот факт, что название этой группе методов дал город Монте-Карло – столица европейского игорного бизнеса. Суть метода Монте-Карло для приближенного вычисления значения кратного интеграла , где - область интегрирования, вписанная в прямоугольник , сводится к следующему: выбирается случайным образом точек , расположенных в прямоугольнике ; вычисляется приближенное значение интеграла по формуле - , где - количество точек, попавших внутрь . Для подсчета площади круга требуется найти интеграл: . При реализации параллельного алгоритма каждый процессор генерирует свое пространство случайных чисел и их обрабатывает. Запишите в файл результат выполнения параллельной программы, содержащий общее количество сгенерированных случайным образом точек , количество попавших в заданную область точек , приближенное вычисленное значение площади круга, погрешность вычисления.

8.     Реализуйте параллельный алгоритм решения задачи Дирихле для двумерного уравнения Лапласа. Требуется найти функцию , удовлетворяющую уравнению Лапласа:

в области и граничным условиям:

, ,

, .

Для численного решения данной задачи требуется построить равномерную сетку в области . Систему линейных уравнений, полученных после аппроксимации дифференциальной задачи конечно-разностной, можно решать итерационным методом Якоби, который имеет максимальную степень параллелизма, либо методом Гаусса-Зейделя или верхней релаксации [44].

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

,

где , - параметр верхней релаксации (при получаем метод Гаусса-Зейделя).

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

Рис. 80. Шаблон красно-черного разбиения

Заметим, что метод верхней релаксации представляет собой рекуррентные вычислительные формулы, затрудняющие его распараллеливание. Тем не менее, метод все же удается распараллелить. Для этого разобьем все узлы в шахматном порядке на красные и черные, как показано на рис. 80 (в литературе эта процедура носит название красно-черного упорядочения [45, 46]). Нетрудно заметить, что для каждого цвета узлов расчеты будут проводиться независимо. На первом этапе будем вычислять значения сеточной функции в красных узлах, используя значения в черных узлах на предыдущей итерации:

.

На втором этапе вычисляются значения в черных узлах, используя значения в красных узлах, но уже новые, вычисленные на первом этапе:

.

Запишите в файл результат выполнения параллельной программы, содержащий количество точек разбиения, число задействованных процессоров, погрешность полученного численного решения (аналитическое решение поставленной задачи ). Вычислить ускорение и эффективность параллельного алгоритма по сравнению с последовательным в зависимости от количества точек разбиения области.