Каждый сдает 3 лабораторные работы.

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

ЛАБОРАТОРНЫЕ РАБОТЫ

ПО КУРСУ «ПАРАЛЛЕЛЬНОЕ И РАСПРЕДЕЛЕННОЕ ПРОГРАММИРОВАНИЕ»

1.  СИНХРОНИЗАЦИЯ ПОТОКОВ 

ЯЗЫКИ: С++, С#

1.1.  Задача обедающих философов.

За круглым столом сидят N философов. Между соседями лежит по вилке (всего N штук). Философ – это поток, который поочередно делает 2 действия: думает (функция think()) и ест (eat()). Чтобы поесть необходимо ложки (одна слева, одна справа).

Необходимо запрограммировать поведение потоков-философов так, чтобы они работали по возможности параллельно, не возникало тупиков, не возникало дискриминации (кто-то не может поесть очень долгое время). Функции think(), eat() могут занимать существенно разное время (для простоты, можно сделать там сортировку массива с случайной – каждый раз заново вычисляемой длиной).

1.2.  Задача «читатели-писатели»

N потоков «писателей» и M потоков-«читателей» обмениваются данными (сообщениями – фиксированной длины) через сравнительно небольшой буфер размером K сообщений. Для простоты – сообщение может быть одним целым числом.

int prepare_data() – подготовка данных «писателем» - возвращает сообщение (целое число).

void process_data(int data) – обработка данных «читателем».

Предполагается, что Prepare_data() и process_data() занимает значительное время, а процесс записи-чтения в буфер – сравнитеьлно небольшое.

Необходимо запрограммировать поведение потоков читателей-писателей, так чтобы они работали максимально параллельно (чтобы несколько читателей и писателей параллельно подготавливали и обрабатывали данные).

1.3.  Задача «спящий парикмахер»

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

Запрограммировать повдение такой системы (поток парикмахер, N-потоков клиентов, которые «приходят» в парикмахерскую время от времени).

1.4.Команда потоков

Реализовать управление команды из N «рабочих» потоков и одного управляющего потока. Каждый рабочий поток может выполнять два задания taskOne(int x), taskTwo(int x). Выполнение каждого задания может занять существенно различное время, в зависимости от параметра x.

Управляющий поток генерирует набор независимых заданий размером K (состоящих из заданий taskOne(), taskTwo() со случайными параметрами) и выполняет их с помощью команды рабочих потоков за минимальное время.

2. OpenMP

ЯЗЫКИ: С/С++

2.1. Найти максимальный и минимальный элемент в массиве

2.2. Найти сумму элементов в массиве

2.3. Найти скалярное произведение двух векторов a и b длины N.

X = a[0]*b[0]+a[1]*b[1]+…+a[N]*b[N]

2.4.Линейный фильтр «размытие».

Дан исходный вектор a. На выходе получаем вектор b. b[i] = (a[i] + a[i+1] + … a[i+k])/k. Здесь k – параметр фильтра.

3. MPI

ЯЗЫКИ: С/C++

Сдается на кластере Cyberia.

Для удобства разработки и отладки дома можно использовать реализацию MPI в виде библиотеки MPICH2.

3.1. Сортировка массива

3.2. Умножение матрицы на вектор

3.3. Умножение матрицы на матрицу

3.4. Задача коммивояжера (полный перебор).