Теми лабораторних занять.

Завдання до лабораторної роботи на тему «Технологія MPI»

1. Дано матрицю дійсних чисел . Кожний із процесів містить її рядків. Написати процедуру множення цієї матриці на довільний вектор. Використати колективні комунікації.
2. Дано матрицю дійсних чисел . Кожний із процесів містить її стовпців. Написати процедуру множення цієї матриці на довільний вектор. Використати колективні комунікації.
3. Дано матрицю дійсних чисел . Кожний із процесів містить її рядків. Написати процедуру множення цієї матриці на довільний вектор. Використати колективні функції.
4. Дано матрицю дійсних чисел . Кожний із процесів містить її стовпців. Написати процедуру множення цієї матриці на довільний вектор. Використати розподілені операції.
5. Створити розподілену операцію для знаходження максимального за модулем комплексного числа. Кожен паралельний процес читає зі свого файлу масив комплексних чисел. Розміри всіх масивів однакові. Знайти найбільше за модулем комплексне число із цих масивів.
6. Поле клітинного автомата (КА) являє собою двовимірний масив кліток. Кожна внутрішня клітка (у випадку періодичного КА й гранична) має 8 сусідів: , , , , , , , . Клітка КА може перебуває в одному із двох станів: клітка вільна (0), клітка зайнята (1). Робота КА визначається наступними правилами:

• Якщо в зайнятий клітки більше трьох сусідніх кліток зайняті, клітка звільняється.
• Якщо у вільної клітки хоча б дві сусідні клітки зайняті, клітка стає зайнятою.

Для моделювання роботи КА використати наступну топологію процесів:

1. Двовимірний масив процесорів.
2. Двовимірний масив процесорів, періодичний по одній координаті.
3. Двовимірний масив процесорів, періодичний по обох координатах.
4. Кільце із процесорів.
1. Цілочисловий масив розподілений між паралельними процесами. Процеси утворять топологію гіперкуб. Спочатку всі процеси сортують свої частини масиву. Потім деякі з них передають відсортовані частини іншим процесам і завершують роботу. Процес, що одержав відсортований масив, поєднує його зі своїм локальним масивом, зберігаючи впорядкованість. Наприкінці роботи який-небудь один процес одержує повністю відсортований масив.
2. Для обчислення визначеного інтеграла від заданої функції по формулі середніх прямокутників використати паралельних процесів.
3. Дійсна матриця розміру розподілена по стовпцях між паралельними процесами. Знайти -розкладання матриці , використовуючи обертання Якобі.
4. Матриця розмірності розподілена по рядках між паралельними процесами ( – ціле). Кожен процес зчитує свою частину матриці зі свого файлу.
1. Знайти найбільший елемент у матриці, використовуючи розподілені операції.
2. Знайти номери нульових стовпців матриці.
3. Знайти найбільший елемент у кожному стовпці матриці.
4. Матриця комплексна. Створити розподілену операцію знаходження максимального за модулем комплексного числа. Використовуючи створену розподілену операцію, знайти максимальне за модулем комплексне число матриці.

Завдання до лабораторної роботи на тему «Взаємодія між процесами ОС Unix»

1. Створити клас, що дозволяє використати «множинні семафори». Використовуючи цей клас, написати наступний програмний додаток мовою С++. Файли f1, f2, f3, f4, f5 містять цілі числа. П'ять однакових процесів обробляють ці файли. Кожному процесу для роботи необхідно два файли. Результат роботи процес записує у файл out_i.

Процес виконує одне з наступних дій (визначається варіантом завдання):

a. Знаходить у файлах будь-яку пару парних чисел (по одному числу у файлі), заміняє їхніми нулями. Знайдені числа виводить у файл out_i. Якщо хоча б в одному файлі потрібних чисел немає - закінчує роботу.

b. Знаходить у файлах будь-яку пару непарних чисел (по одному числу у файлі), заміняє їхніми нулями. Знайдені числа виводить у файл out_i. Якщо хоча б в одному файлі потрібних чисел немає - закінчує роботу.

c. Знаходить у файлах будь-яку пару натуральних чисел (по одному числу у файлі), заміняє їхніми нулями. Знайдені числа виводить у файл out_i. Якщо хоча б в одному файлі потрібних чисел немає - закінчує роботу.

d. Знаходить у файлах будь-яку пару простих чисел (по одному числу у файлі), заміняє їхніми нулями. Знайдені числа виводить у файл out_i. Якщо хоча б в одному файлі потрібних чисел немає - закінчує роботу.

2. Для рішення задачі спроектувати монітор Хоара. Описати алгоритм рішення задачі з використанням цього монітора. Написати програму мовою С++, що реалізує цей алгоритм (монітор реалізувати з використанням класу семафора).

a) Процеси PW, PR1 й PR2 спільно обробляють файл f.pub. PW читає з файлу f.in довільні натуральні числа й записує їх у файл f.pub. PR1 читає з файлу f.pub парні числа й записує у файл f1.out їхні прості дільники. PR2 читає з файлу f.pub непарні числа, перевіряє їх на простоту. Результат записує у файл f2.out. PW пише числа у файл, якщо файл порожній або число прочитано. Процеси PR1, PR2 читають числа по одному разі.

b) Процеси PW, PR1 й PR2 взаємодіють через загальну пам'ять. PW читає з файлу f.in і записує загальну пам'ять довільні натуральні числа. PR1 читає із загальної пам'яті парні числа й записує у файл f1.out їхні прості дільники. PR2 читає із загальної пам'яті непарні числа, перевіряє їх на простоту. Результат записує у файл f2.out. PW пише числа в загальну пам'ять, якщо загальна пам'ять порожня або число прочитане. Процеси PR1, PR2 читають числа по одному разі.

3. Процес P1 читає з файлу f1.in цілі числа й записує їх у файл f.pub. Процес P2 читає числа з файлу f.pub і записує їхні прості дільники у файл f2.out. Процеси звертаються до файлу f.pub по черзі.

4. Процес P1 читає з файлу f1.in цілі числа й записує їх у загальну пам'ять. Процес P2 читає числа із загальної пам'яті й записує їхні прості дільники у файл f2.out. Процеси звертаються до загальної пам'яті по черзі.

5. Процес P1 читає з файлу f1.in рядок символів, шифрує її й записує у файл f.pub. Процес P2 читає зашифрований рядок з файлу f.pub, розшифровує її й записує у файл f2.out. Процеси звертаються до файлу f.pub по черзі. Рядки шифруються алгоритмом Цезаря.

6. Процес P1 читає з файлу f1.in рядок символів, шифрує її й записує в загальну пам'ять. Процес P2 читає зашифрований рядок із загальної пам'яті, розшифровує її й записує у файл f2.out. Процеси звертаються до загальної пам'яті по черзі. Рядки шифруються алгоритмом Цезаря.

7. Описати клас «рахункові семафори» і вирішити наступну задачу («читачі-письменники»). Процес-письменник PW читає з файлу f1.in цілі числа й записує у файл f.pub (якщо лічено 0 – додаток завершує роботу). Процеси-читачі виконують наступне: PR1 читає з файлу f.pub парні числа й знаходить його найбільший простий дільник. Результат записує у файл f1.out. PR2 читає з файлу f.pub непарні числа, перевіряє їх на простоту й результат виводить у файл f2.out. PR3 читає з файлу f.pub негативні числа й виводить у файл f3.out.

8. Додаток-сервер створює черга повідомлень. Потім, читаючи із черги повідомлення записує у файл f1.out повідомлення типу 1, а у файл f2.out – повідомлення типу 2. Одержавши повідомлення типу 3, додаток-сервер видаляє чергу й завершує роботу. Додаток-клієнт читає з файлу f1.in числа (тип повідомлення) і рядка символів і записує цю інформацію в чергу повідомлень. Продемонструвати роботу додатка-сервера й мінімум двох клієнтів, що працюють одночасно.

9. Створити конвеєр із трьох процесів P1, P2, P3. Процес P1 читає з файлу f1.in рядок з латинських символів і пробілів і заміняє в ній всі малі літери прописними. Процес P2 видаляє з рядка зайві пробіли. Процес P3 заміняє пробіли символом ‘_’ і виводить рядок у файл f1.out. Використати семафори Unix System Y, описавши на їхній основі клас семафорів. Для взаємодії між собою процеси використають FIFO.

10. Створити конвеєр із трьох процесів P1, P2, P3. Процес P1 читає з файлу f1.in рядок з латинських символів і пробілів і заміняє в ній всі малі літери прописними. Процес P2 видаляє з рядка зайві пробіли. Процес P3 заміняє пробіли символом ‘_’ і виводить рядок у файл f1.out. Використати семафори Unix System Y, описавши на їхній основі клас семафорів. Для взаємодії між собою процеси використають загальну пам'ять.

11. Створити конвеєр із трьох процесів P1, P2, P3. Процес P1 читає з файлу f1.in рядок з латинських символів і пробілів і заміняє в ній всі малі літери прописними. Процес P2 видаляє з рядка зайві пробіли. Процес P3 заміняє пробіли символом ‘_’ і виводить рядок у файл f1.out. Використати семафори Unix System Y, описавши на їхній основі клас семафорів. Для взаємодії між собою процеси використають чергу повідомлень.

12. Створити конвеєр із трьох родинних процесів. Перший процес читає з файлу f1.in рядок з латинських символів і пробілів і заміняє в ній всі малі літери прописними. Другий процес видаляє з рядка зайві пробіли. Третій заміняє пробіли символом ‘_’ і виводить рядок у файл f.out. Використати семафори Unix System Y, описавши на їхній основі клас семафорів. Для взаємодії між собою процеси використають анонімні канали.

Завдання до лабораторної роботи на тему «Потоки ОС Unix стандарту POSIX»

А. Додаток клієнт посилає додатку сервер запит, використовуючи один з механізмів межпроцессного взаємодії. Головний потік додатка сервер приймає запити від клієнта (клієнтів) і поміщає їх у чергу запитів. Деяка кількість потоків сервера одночасно обробляють ці запити, витягаючи їх із черги. Сервер завершує роботу, одержавши запит певного зразка. Результати обробки запитів потоки поміщають у файл. Для синхронізації роботи потоків використати мютексы й POSIX-семафори.

Б. Додаток клієнт посилає додатку сервер запити двох типів, використовуючи один з механізмів межпроцессного взаємодії. Клієнт читає запити з файлу. Головний потік сервера приймає запити від клієнта (клієнтів) і поміщає їх у чергу запитів. Деяка кількість потоків (двох типів) сервера одночасно обробляють ці запити, витягаючи їх із черги. Сервер завершує роботу, одержавши запит певного зразка. Результати обробки запитів потоки поміщають у різні файли залежно від типу запиту. Для синхронізації роботи потоків використати мютексы, POSIX-семафори й умовні змінні.

В. Головний потік програми формує черга завдань із вхідного файлу. Для обробки завдань із цієї черги використається конвеєр із трьох потоків. Перший потік витягає завдання із черги, обробляє й передає другому. Другий потік обробляє завдання й передає третьому. Третій потік обробляє завдання й виводить результат у файл. Потоки виконуються одночасно. Для синхронізації роботи потоків використати мютексы й POSIX-семафори.

Вимоги до звіту: 1. Постановка задачі. 2. Алгоритм рішення задачі. 3. Текст програми. 4. Тестовий приклад. 5. Результати роботи програми на тестовому прикладі.

Завдання до лабораторної роботи на тему «Технологія OpenMP»

На языке С/С++ написать последовательную программу решения поставленной задачи. Программа должна определять время, потраченное потоком процесса на решение задачи. Преобразовать последовательную программу в параллельную для 2-процессорной SMP-системы. Программа должна выводить время, потраченное каждым потоком программы на решение задачи.

1. Вычислить A^m, где A – вещественная матрица размера n´ n.
2. Найти m-е простое число.
3. Даны матрицы A и B неотрицательных целых чисел размера m´ m. Найти наибольшие общие делители элементов a(i, j) и b(i, j) (1£ i, j£ m). Результаты записать в матрицу C. Наибольший общий делитель двух v1 и v2чисел можно найти по алгоритму:
   while (v1! =v2) if (v1> v2)v1-=v2; else v2-=v1;
4. Дана матрица A неотрицательных целых чисел размера m´ m. Найти наибольший общий делитель ее элементов. Наибольший общий делитель двух v1 и v2чисел можно найти по алгоритму:
   while (v1! =v2) if (v1> v2)v1-=v2; else v2-=v1;
5. Дана матрица A неотрицательных целых чисел размера m´ m. Найти количество простых чисел среди ее элементов.
6. Дана матрица A неотрицательных целых чисел размера m´ m. Построить матрицу B следующим образом. b(i, j) – это a(i, j)-е простое число.
7. Дана матрица A неотрицательных целых чисел размера m´ m и простое число p. Построить матрицу B следующим образом. b(i, j) =(log₂ a(i, j)) mod p (или 0).
8. Дана матрица A неотрицательных целых чисел размера m´ m и простое число p. Построить матрицу B следующим образом. b(i, j) =(log₃ a(i, j)) mod p (или 0).
9. Дана матрица A неотрицательных целых чисел размера m´ m и простое число p. Построить матрицу B следующим образом. b(i, j) =(log₄ a(i, j)) mod p (или 0).
10. Дана матрица A неотрицательных целых чисел размера m´ m и простое число p. Построить матрицу B следующим образом. b(i, j) =(log5 a(i, j)) mod p (или 0).

Отчет должен состоять из следующих пунктов:

1. Постановка задачи.
2. Алгоритм решения задачи.
3. Тексты последовательной и параллельной программ.
4. Тестовый пример.
5. Результаты работы программ на тестовом примере.

9. Індивідуальне навчально-дослідне завдання

Не передбачено