Параллельное программирование

А.Ю. Сыщиков, Ю.Е. Шейнин

Методические указания к выполнению курсовых работ.

Санкт-Петебург

2010

1 Введение

Курсовая работа по дисциплине «Параллельное программирование» («Системы с параллельной обработкой информации») является завершающим этапом изучения данной дисциплины.

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

2 Общее описание задания на курсовую работу

2.1 Содержание курсовой работы

Задание на курсовую работу состоит из следующих частей:

1. Изучение задачи своего варианта, разработка и описание общего алгоритма ее решения;

2. Разработка и отладка параллельной программы решения данной задачи в рамках одного из двух изученных стандартов разработки параллельных программ: MPI или OpenMP;

3. Промежуточное представление результатов работы;

4. Подготовка отчета по курсовой работе;

5. Защита курсовой работы.

2.2 Выбор варианта задания

Выбор варианта задания и стандарта параллельного программирования для разработки программы осуществляется студентом при личном присутствии из списка заданий на курсовые работы, которые еще не были заняты другими студентами.

2.3 Метод решения и используемые средства

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

2.4 Требования к курсовой работе

1. Разработанные программы должны содержать достаточное количество распараллеленных вычислений и/или их частей.

2. Количество параллельных процессов должно быть произвольным.
Допускается пожелание студента, чтобы задаваемое число параллельных процессов было кратно некоторому требуемому числу.

3. В программе должно засекаться время ее выполнения (с точностью до миллисекунд) и выводиться на экран по итогам работы программы.

4. Программа на большем количестве процессов должна работать быстрее, чем на меньшем количестве процессов. В случае если это не так необходимо веско аргументировать, почему это не так.

5. Если программе требуется больше одной-двух цифр входных данных – такие данные должны задаваться в файле(ах) и читаться оттуда.

6. Размерность задачи для тестового примера должна быть такой, чтобы ее вычисление занимало не меньше 10 секунд (можно больше в разумных пределах).

2.5 Содержание отчета

1. Титульный лист

2. Текст задания с вариантом

3. Теоретическая часть

a. Краткий обзор по теме задания

b. Общее описание выбранного метода решения

c. Описание применения выбранного метода распараллеливания к выбранному методу решения

4. Практическая часть

a. Схема алгоритма программы

b. Текст существенных (относительно изучаемого предмета и выбранного задания) частей программного кода

c. Примеры работы программы с пояснением выводимых результатов

5. Заключительная часть

a. Описание результатов относительно выбранного задания

i. ограничения на входные данные

ii. качество получаемых результатов

iii. другие характеристики (если есть)

b. Описание результатов распараллеливания решения задания

i. изменение времени работы при использовании одного процессора/ядра

ii. изменение времени работы при использовании двух процессоров/ядер

iii. оценка изменения времени работы при использовании N процессоров/ядер (N>2)

6. Выводы

2.6 Оценка курсовой работы

Оценка за курсовую работу может быть снижена:

1. По формальным признакам:

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

b. За несоответствие отчета требованиям к содержанию отчета

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

d. При сдаче курсовой на дополнительных занятиях после окончании сессии независимо от предъявления промежуточных результатов

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

2. По результатам работы:

a. За неполное соответствие проделанной работы выбранному заданию

b. За малоэффективное применение методов и средств распараллеливания

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

d. Если студент в течение пары не смог ответить на поставленные преподавателем вопросы.

3 Варианты заданий на курсовую работу

№ вар.	Задача	Стан- дарт
1	Игра «Судоку»: генератор поля	MPI
2	Игра «Судоку»: генератор поля	OpenMP
3	Игра «Судоку»: решатель задач	MPI
4	Игра «Судоку»: решатель задач	OpenMP
5	Японский кроссворд	MPI
6	Японский кроссворд	OpenMP
7	«Расстановка ферзей»	MPI
8	«Расстановка ферзей»	OpenMP
9	«Путешествие коня»	MPI
10	«Путешествие коня»	OpenMP
11	«Агрессивные ладьи»	MPI
12	«Агрессивные ладьи»	OpenMP
13	«Задача о красных и синих точках»	MPI
14	«Задача о красных и синих точках»	OpenMP
15	«Задача об окружностях»	MPI
16	«Задача об окружностях»	OpenMP
17	Построение крaтчaйшего мaршрутa	MPI
18	Построение крaтчaйшего мaршрутa	OpenMP
19	«Минимальное количество монет»	MPI
20	«Минимальное количество монет»	OpenMP
21	«А у вас будет без сдачи?»	MPI
22	«А у вас будет без сдачи?»	OpenMP
23	«Фермер и сарай»	MPI
24	«Фермер и сарай»	OpenMP
25
26

4 Пояснения к задачам

4.1 «Игра «Судоку»: генератор поля»

Судоку - логическая головоломка, квадрат 9x9, который нужно заполнить цифрами по следующим правилам: в свободных клетках надо расставить цифры от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.

Необходимо сгенерировать полное поле цифр для игры Судоку, удовлетворяющее правилам игры.

Входные данные для программы не требуются.

Выходными данными будет сгенерированное поле в виде матрицы 9х9.

4.2 «Игра «Судоку»: решатель задач»

Необходимо найти решения задаваемой головоломки: одно, если оно однозначно, несколько, если возможны различные корректные решения или сделать вывод, что конкретная задача не имеет решений.

Входными данными будет начальное поле размером 9х9, в котором 0 обозначаются пустые клетки, цифрами от 1 до 9 открытые клетки.

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

4.3 «Японский кроссворд»

В клетках японского кроссворда скрываются не слова, а картинки. Задача - нарисовать картинку по числам, которые проставлены слева от строк и над колонками. Числа показывают, сколько групп закрашенных клеток находится в соответствующей линии и сколько закрашенных клеток содержит каждая группа. Например (рис. 1), числа 2, 1 и 1 во второй строке означают, что в этой строке есть три группы, состоящие: первая - из двух, вторая - из одной, третья - также из одной закрашенной клетки. Группы разделены, как минимум, одной пустой клеткой. Пустые клетки могут быть и по краям рядов.

Необходимо найти решения задаваемого кроссворда: одно, если оно однозначно, несколько, если возможны различные корректные решения или сделать вывод, что конкретный кроссворд не имеет решений.

Входными данными будут размеры поля M и N, а также наборы длин закрашенных групп по координатам X и Y.

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

4.4 «Расстановка ферзей»

Разработать программу поиска всех возможных способов расстановки восьми шахматных ферзей на пустой доске размером x*y таким образом, чтобы ни один из них не "бил" другого. Т.е. так, чтобы ни какие два ферзя не стояли на одном и том же столбце, или на одной и той же строке, или на одной и той же диагонали шахматной доски.

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

Выходными данными будут количество найденных расстановок и сами расстановки.

4.5 «Путешествие коня»

Разработать программу для обхода шахматным конем, находящимся на произвольной клетке доски размером x*y, всех остальные клеток доски. При этом на одну клетку можно походить только один раз.

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

Выходными данными будет последовательность обхода доски.

4.6 «Агрессивные ладьи»

Разработать программу поиска максимального количества ладей, которые можно расставить на доске размером x*y так, чтобы ни одна из них не «била» другую. Т.е. так, чтобы ни какие две ладьи не стояли на одном и том де столбце или строке.

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

Выходными данными будут количество расставленных ладей и сама расстановка.

4.7 «Задача о красных и синих точках»

Дано некоторое количество красных и столько же синих точек. Разработать программу, которая соединить их попарно (красная-синяя) так, чтобы суммарная длина отрезков была минимальна.

Входными данными для программы будут наборы координат красных и синих точек.

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

4.8 «Задача об окружностях»

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

Входными данными для программы будет набор координат точек.

Выходными данными будут минимальное количество окружностей и сами окружности с их параметрами и списком точек, которые лежат на конкретной окружности.

4.9 Построение крaтчaйшего мaршрутa

Имеется поле x*y. Кaждaя клеткa поля может быть проходима или не проходима. На поле имеются точки А и В. Перемещение возможно только по вертикали и горизонтали. Hеобходимо найти кратчайший маршрут из точки А в точку В, если он существует.

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

Выходными данными будут последовательность и координаты точек кратчайшего маршрута.

4.10 «Минимальное количество монет»

У продавца и покупателя имеется неограниченное количество монет/купюр достоинством 1, 2, 5, 10, 50, 100 и 500 рублей. Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет/купюр, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец.

Входными данными для программы будет являться сумма покупки.

Выходными данными будут наборы монет/купюр, переданных со стороны покупателя и продавца.

4.11 «А у вас будет без сдачи?»

У покупателя имеется некоторое количество монет/купюр достоинством 1, 2, 5, 10, 50, 100 и 500 рублей. Необходимо найти максимальную стоимость товара Р, который покупатель не сможет купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара достаточно.

Входными данными для программы будут являться количество монет/купюр каждого номинала.

Выходными данными будет максимальная стоимость покупки, на которую хватает денег, но за которую не рассчитаться.

4.12 «Фермер и сарай»

Фермер хочет построить на своей земле как можно больший по площади прямоугольный сарай. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Можно представить ферму полем размером MxN. Каждое дерево или постройка занимает одну или несколько «клеток». Прямоугольный сарай не должен ни с чем соприкасаться (т.е. соседних с ним «клетках» ничего не должно быть).

Найти максимально возможную площадь сарая и где он может размещаться.

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

Выходными данными будут максимальная площадь сарая и координаты его размещения.

5 Список литературы

MPI: A Message-Passing Interface Standard.

http://parallel.ru/docs/Parallel/mpi1.1/mpi-report.html

MPICH-A Portable Implementation of MPI.

http://www-unix.mcs.anl.gov/mpi/mpich

Воеводин Вл.В. Курс лекций "Параллельная обработка данных".

http://parallel.ru/vvv/index.html

http://parallel.ru/tech/tech_dev/openmp.html

http://www.openmp.org