Завдання

Відповідно до номера свого варіанта виконайте завдання обраного рівня складності.

Варіанти

Варіант 1. Інтегрування функцій

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка обчислює інтеграл ${\int }_0^2{x}^2{e}^{-x}\mathrm{d}x$ методом середніх прямокутників з ${10}^8$ кроків: ранг 0 розсилає кількість кроків операцією MPI_Bcast, кожен ранг підсумовує свою частину, MPI_Reduce збирає суму, а ранг 0 виводить результат і час MPI_Wtime.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка на ранзі 0 запитує номер функції ($\sin x$, $e^{-x^2}$, $\sqrt{1-x^2}$), межі інтегрування й кількість кроків, перевіряє введення (при помилці всі процеси завершуються з кодом 1), розсилає параметри одним повідомленням і виводить інтеграл, похибку відносно точного значення та час найповільнішого рангу.

3. Високий рівень. Створити проєкт CMake з програмою integrate мовою C++ з MPI, яка обчислює інтеграл функції, розподіляючи кроки між рангами, з опціями --func <назва>, --range <a>:<b>, --steps <n>, --rule rect|trap|simpson, --csv <файл> і --help. Програма обчислює інтеграл трьома правилами й записує в CSV кількість процесів, правило, час і похибку. Скрипт запускає програму для 1–8 процесів і виводить таблицю прискорення й ефективності; некоректні опції – повідомлення в stderr і код 1.

Варіант 2. Множення матриць

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка множить дві випадкові матриці $n\times n$ ($n=960$, фіксоване зерно): ранг 0 розсилає матрицю $B$ операцією MPI_Bcast, рядки $A$ – операцією MPI_Scatter, кожен ранг множить свої рядки, а MPI_Gather збирає $C$; ранг 0 перевіряє 10 випадкових елементів.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує розмір матриць $n$ (будь-який, не обов’язково кратний кількості процесів), розподіляє рядки операціями MPI_Scatterv і MPI_Gatherv, перевіряє результат послідовним множенням на ранзі 0 і виводить окремо час обчислень і час комунікацій та їх частки.

3. Високий рівень. Створити проєкт CMake з програмою matmul з опціями --size <n>, --algo rows|cannon, --repeat <k>, --csv <файл> і --help, яка реалізує розподіл рядків і алгоритм Кеннона на квадратній решітці процесів (MPI_Cart_create, MPI_Cart_shift, MPI_Sendrecv_replace), перевіряє, що кількість процесів – повний квадрат, і виводить таблицю «процеси – алгоритм – час – GFLOPS – частка комунікацій». Помилки параметрів – код 1.

Варіант 3. Парно-непарне сортування

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг генерує 100 000 випадкових цілих чисел (зерно дорівнює рангу), сортує їх std::sort, а потім виконує $p$ фаз парно-непарного обміну з сусідом (MPI_Sendrecv і злиття), після чого ранг 0 збирає масив і перевіряє впорядкованість.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує загальну кількість чисел (від ${10}^3$ до ${10}^8$), розподіляє їх між рангами з урахуванням залишку, сортує парно-непарним алгоритмом, перевіряє впорядкованість (кожен ранг порівнює свій максимум з мінімумом правого сусіда) і виводить час та кількість фаз, після яких обміни вже нічого не змінювали.

3. Високий рівень. Створити проєкт CMake з програмою oddeven з опціями --count <n>, --distribution uniform|sorted|reverse, --input <файл>, --output <файл> і --help, яка читає числа з двійкового файлу (кожен ранг – свою частину), сортує парно-непарним методом із раннім завершенням (MPI_Allreduce ознаки змін), записує результат і виводить таблицю часу для 1–8 процесів і трьох розподілів. Помилки файлів – код 2.

Варіант 4. Монте-Карло для числа π

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг генерує ${10}^7$ випадкових точок у квадраті генератором std::mt19937_64 із зерном $1000+\text{ранг}$, рахує точки всередині чверті кола, а ранг 0 після MPI_Reduce виводить оцінку $\pi$ і похибку.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує загальну кількість точок і базове зерно, ділить точки між рангами (залишок – першим рангам), виводить оцінку $\pi$, абсолютну похибку, стандартну похибку оцінки та кількість точок за секунду, і перевіряє, що результат не змінюється при повторному запуску з тим самим зерном.

3. Високий рівень. Створити проєкт CMake з програмою mcpi мовою C++ з MPI, яка оцінює $\pi$ методом Монте-Карло (частка випадкових точок у чверті кола, точки діляться між рангами) з опціями --points <n>, --seed <s>, --target <похибка> і --help. Програма подвоює кількість точок, доки стандартна похибка (обчислена через MPI_Allreduce сум і сум квадратів) не стане меншою за задану, і виводить таблицю ітерацій та ефективність для 1–16 процесів. Недосяжна точність за ${10}^{11}$ точок – код 3.

Варіант 5. Теплопровідність пластини 2D

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка моделює теплопровідність квадратної пластини $1200\times 1200$ вузлів (верхній край 100 °C, інші 0 °C, 1000 кроків явної схеми) з поділом на горизонтальні смуги й обміном рядками гало через MPI_Sendrecv і виводить середню температуру.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує розмір пластини й кількість кроків, використовує двовимірну декартову топологію (MPI_Dims_create, MPI_Cart_create, MPI_Cart_shift) і похідний тип для стовпців, перевіряє збіг середньої температури з результатом для одного процесу та виводить час і частку комунікацій.

3. Високий рівень. Створити проєкт CMake з програмою heat2d мовою C++ з MPI, яка моделює теплопровідність квадратної пластини явною схемою з поділом сітки між процесами й обміном гало, з опціями --size <n>, --steps <k>, --decomp strips|grid (смуги або декартова решітка), --weak, --csv <файл> і --help. Програма вимірює сильну й слабку масштабованість (у режимі --weak розмір на процес сталий) для 1–16 процесів і записує в CSV час, час обмінів і ефективність. Некоректна кількість процесів для решітки – код 1.

Варіант 6. Мандельброт «майстер–робітник»

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка обчислює множину Мандельброта 1200×800 (не більше 1000 ітерацій): ранг 0 роздає робітникам номери рядків по одному, збирає результати й записує зображення у файл mandel.pgm.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка обчислює множину Мандельброта й записує її у PGM. Програма запитує роздільність, максимальну кількість ітерацій і кількість рядків у завданні (1–64), реалізує статичний розподіл рядків і динамічний («майстер–робітник») та виводить для обох час, кількість рядків кожного робітника й відношення часу найшвидшого й найповільнішого робітника.

3. Високий рівень. Створити проєкт CMake з програмою mandelmw мовою C++ з MPI, яка обчислює множину Мандельброта за схемою «майстер–робітник» (майстер теж обчислює рядки між відповідями, MPI_Iprobe) з опціями --size <ш>x<в>, --iter <n>, --chunk <k>, --mode static|cyclic|dynamic, --image <файл.pgm>, --csv <файл> і --help. Програма записує зображення й виводить таблицю часу для всіх режимів і розмірів порції на 2–16 процесах.

Варіант 7. Розподілений k-means

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг генерує 200 000 випадкових точок площини навколо трьох центрів, а алгоритм k-means ($k=3$, 20 ітерацій) на кожній ітерації об’єднує суми координат і кількості точок кластерів операцією MPI_Allreduce; ранг 0 виводить знайдені центри.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка кластеризує точки площини алгоритмом k-means. Програма запитує кількість точок, $k$ і поріг зсуву центрів, генерує точки на ранзі 0 і розподіляє їх операцією MPI_Scatterv, виконує ітерації (суми кластерів об’єднуються MPI_Allreduce) до зсуву, меншого за поріг, і виводить центри, кількість точок у кластерах, кількість ітерацій і час на ітерацію.

3. Високий рівень. Створити проєкт CMake з програмою kmeans з опціями --input <файл.csv>, --k <k>, --max-iter <n>, --tol <e>, --output <файл.csv> і --help, яка читає точки з CSV (кожен ранг – свою частину рядків), записує мітки кластерів і виводить таблицю «процеси – ітерації – час на ітерацію – частка MPI_Allreduce». Помилки формату – номер рядка в stderr, код 2.

Варіант 8. Гістограма великих даних

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій ранг 0 генерує ${10}^7$ оцінок від 0 до 100, розподіляє їх операцією MPI_Scatter, кожен ранг будує гістограму з 10 інтервалів, а MPI_Reduce з MPI_SUM для масиву з 10 лічильників збирає загальну гістограму.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує кількість значень і кількість інтервалів, розподіляє дані операцією MPI_Scatterv, будує гістограму, перевіряє, що сума лічильників дорівнює кількості значень, і виводить гістограму текстовими стовпчиками та час для різної кількості процесів.

3. Високий рівень. Створити проєкт CMake з програмою histo з опціями --input <файл>, --bins <k>, --range <min>:<max>, --auto-range і --help, яка читає двійковий файл чисел double (кожен ранг – свою частину через зміщення у файлі), за --auto-range знаходить межі через MPI_Allreduce, виводить гістограму, квартилі й час. Відсутній файл – код 2.

Варіант 9. Гра «Життя» з неблокуючим обміном

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка моделює гру «Життя» на полі $1000\times 1000$ (тор) з поділом на горизонтальні смуги, обмінюється рядками гало через MPI_Sendrecv і виводить кількість живих клітин через 100 поколінь.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка моделює гру «Життя» Конвея на тороїдальному полі з поділом на горизонтальні смуги. Програма запитує розмір поля й кількість поколінь, обмінюється рядками гало неблокуючими MPI_Isend/MPI_Irecv, під час обміну обчислює внутрішні рядки, а після MPI_Waitall – крайові, і порівнює час із блокуючою версією (MPI_Sendrecv).

3. Високий рівень. Створити проєкт CMake з програмою lifempi мовою C++ з MPI, яка моделює гру «Життя» Конвея з поділом поля на смуги й обміном гало, з опціями --size <n>, --gens <k>, --exchange blocking|overlap, --pattern <файл.rle>, --snapshot <крок> і --help. Програма завантажує фігуру з файлу RLE, зберігає знімки поля у PGM (збирання на ранзі 0) і виводить таблицю часу обох способів обміну для 1–16 процесів.

Варіант 10. Прості числа в діапазоні

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка рахує прості числа від 2 до $5\cdot {10}^7$ перевіркою дільників: діапазон ділиться на рівні суміжні частини, а MPI_Reduce підсумовує кількості; ранг 0 виводить кількість і час кожного рангу (MPI_Gather).

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує межі діапазону, порівнює блоковий, циклічний (число $k$ отримує ранг $kmodp$) і динамічний («майстер–робітник» блоками по 10 000 чисел) розподіли та виводить для кожного кількість простих, час і відношення часу найшвидшого й найповільнішого рангу.

3. Високий рівень. Створити проєкт CMake з програмою primes з опціями --range <a>:<b>, --method trial|sieve, --split block|cyclic|dynamic, --list <файл> і --help, де метод sieve – сегментоване решето Ератосфена (базові прості розсилаються MPI_Bcast), а --list записує знайдені числа (збирання MPI_Gatherv). Вивести таблицю часу для всіх комбінацій.

Варіант 11. Sample sort

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг сортує 200 000 випадкових чисел, ранг 0 збирає по $p-1$ зразків від кожного, обирає $p-1$ роздільників і розсилає їх MPI_Bcast, після чого програма виводить, скільки чисел кожного рангу потрапляє в кожен кошик.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка сортує випадкові числа, згенеровані на кожному ранзі, повним алгоритмом sample sort: локальне сортування, вибір роздільників за зразками, обмін кількостями MPI_Alltoall, обмін кошиками MPI_Alltoallv, локальне злиття й перевірка впорядкованості на межах рангів. Програма виводить розміри кошиків, коефіцієнт дисбалансу й час.

3. Високий рівень. Створити проєкт CMake з програмою samplesort з опціями --count <n>, --distribution uniform|normal|zipf, --oversampling <s> і --help, яка порівнює sample sort із парно-непарним сортуванням і збиранням на ранзі 0 зі std::sort та виводить таблицю часу й дисбалансу для 1–16 процесів. Невдала перевірка впорядкованості – код 4.

Варіант 12. PageRank малого вебграфа

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка для заданого в програмі графа з 8 сторінок обчислює PageRank (коефіцієнт 0,85, 50 ітерацій): кожен ранг оновлює ранги своїх сторінок, MPI_Allgather збирає вектор на всіх процесах; вивести ранги сторінок.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка читає граф зі списку ребер (ім’я файлу вводить користувач), розподіляє вершини між рангами з урахуванням залишку (MPI_Allgatherv), виконує ітерації до зміни менше ${10}^{-8}$ (MPI_Allreduce норми) і виводить 10 сторінок з найбільшим рангом та кількість ітерацій.

3. Високий рівень. Створити проєкт CMake з програмою pagerank з опціями --edges <файл>, --damping <d>, --tol <e>, --top <k> і --help, яка генерує або читає граф (до ${10}^6$ вершин), обробляє «висячі» вершини, зберігає результат у CSV і виводить таблицю «процеси – ітерації – час – частка комунікацій». Помилки файлу – код 2.

Варіант 13. Задача n тіл кільцем

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг має 500 тіл із випадковими масами й координатами, блоки тіл передаються по кільцю (MPI_Sendrecv) $p-1$ разів, і кожен ранг обчислює сили від усіх тіл; ранг 0 виводить прискорення перших трьох тіл.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує кількість тіл і кроків і моделює рух тіл під дією взаємного тяжіння методом Ейлера: блоки тіл передаються по кільцю рангів. Програма перевіряє збереження імпульсу системи (MPI_Reduce) і виводить час на крок та порівняння з версією, де всі координати збираються MPI_Allgather.

3. Високий рівень. Створити проєкт CMake з програмою nbodyring мовою C++ з MPI, яка моделює рух тіл під дією взаємного тяжіння з опціями --bodies <n>, --steps <k>, --exchange ring|allgather, --overlap, --csv <файл> і --help. У режимі ring блоки тіл передаються по кільцю рангів, з --overlap – неблокуючими операціями під час обчислення сил поточного блоку. Програма записує траєкторії трьох тіл і виводить таблицю часу для 1–16 процесів.

Варіант 14. Лічильник слів у файлах

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка отримує в аргументах імена текстових файлів, розподіляє файли між рангами за номером ($imodp$), рахує слова в кожному файлі й збирає кількості на ранзі 0 (MPI_Reduce), виводячи загальну кількість слів.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка для файлів із заданої теки будує частотні словники на кожному ранзі, передає їх рангу 0 як рядки змінної довжини (MPI_Probe і MPI_Get_count), об’єднує й виводить 20 найчастіших слів та час.

3. Високий рівень. Створити проєкт CMake з програмою wordcount мовою C++ з MPI, яка будує частотний словник слів текстових файлів теки, розподіляючи файли між рангами, з опціями --dir <тека>, --top <k>, --min-length <n>, --balance files|bytes (за кількістю файлів або сумарним розміром) і --help. Словники рангів об’єднуються деревом попарних обмінів (${\log }_{2}p$ кроків); програма виводить $k$ найчастіших слів і записує результат у CSV. Відсутня тека – код 2.

Варіант 15. Результати виборів

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг імітує дільницю: генерує голоси 1000 виборців за 5 кандидатів (зерно дорівнює рангу), а MPI_Reduce масиву з 5 лічильників дає підсумок на ранзі 0 з відсотками.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг формує текстовий протокол дільниці змінної довжини (номер, кількість виборців, голоси), а ранг 0 збирає протоколи операцією MPI_Gatherv (довжини – MPI_Gather), перевіряє контрольні суми й виводить таблицю дільниць і підсумок.

3. Високий рівень. Створити проєкт CMake з програмою elections з опціями --input <тека протоколів>, --threshold <відсоток>, --report <файл.csv> і --help, яка розподіляє файли протоколів між рангами, виявляє протоколи з помилками (сума голосів більша за кількість виборців), виводить підсумок, кандидатів понад поріг і список помилкових протоколів у stderr; код 3, якщо помилки є.

Варіант 16. Гібридний метод Якобі

1. Початковий рівень. Створити консольну програму мовою C++ з MPI і OpenMP, яка розв’язує методом Якобі систему $(2+\sigma )u_i-u_{i-1}-u_{i+1}=b_i$ для ${10}^6$ невідомих з поділом на блоки між рангами й обміном гало, а цикл оновлення в межах блоку розпаралелює #pragma omp parallel for; використати MPI_Init_thread з MPI_THREAD_FUNNELED.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI і OpenMP, яка розв’язує методом Якобі систему $(2+\sigma )u_i-u_{i-1}-u_{i+1}=b_i$ з поділом невідомих на блоки між рангами й обміном гало та паралельним оновленням блоку потоками. Програма запитує кількість невідомих, ітерацій і $\sigma$, виконує ітерації до норми нев’язки менше ${10}^{-10}$ (MPI_Allreduce кожні 10 ітерацій), перевіряє наданий рівень підтримки потоків і виводить кількість рангів, потоків, ітерацій, час і похибку.

3. Високий рівень. Створити проєкт CMake з програмою hybridjacobi мовою C++ з MPI і OpenMP, яка розв’язує методом Якобі систему $(2+\sigma )u_i-u_{i-1}-u_{i+1}=b_i$ (блоки між рангами з обміном гало, оновлення блоку потоками) з опціями --size, --iters, --csv і --help. Скрипт запускає програму в конфігураціях «ранги × потоки» 8×1, 4×2, 2×4, 1×8 з --map-by slot:PE=<t> і --report-bindings, перевіряє прив’язку й записує в CSV час, час обмінів і прискорення.

Варіант 17. Пошук у ширину в графі

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка для заданого в програмі графа-решітки $100\times 100$ з вершинами, розподіленими блоками між рангами, виконує рівневий пошук у ширину від вершини 0: після кожного рівня фронт об’єднується MPI_Allgather; вивести кількість рівнів і вершин на кожному рівні.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка генерує випадковий граф (кількість вершин і середній степінь вводить користувач), виконує BFS, пересилаючи власникам вершин запити через MPI_Alltoall кількостей і MPI_Alltoallv вершин, і виводить відстані до 10 випадкових вершин та час.

3. Високий рівень. Створити проєкт CMake з програмою bfsmpi з опціями --graph <файл>, --source <v>, --distances <файл> і --help, яка читає граф списком ребер, перевіряє результат послідовним BFS на ранзі 0 для графів до ${10}^6$ вершин, виводить таблицю рівнів і розмірів фронту та час для 1–16 процесів. Недосяжні вершини мають відстань $-1$.

Варіант 18. Метод Гаусса

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка розв’язує систему $n\times n$ ($n=500$, випадкова матриця з діагональною перевагою) методом Гаусса з циклічним розподілом рядків: на кожному кроці власник ведучого рядка розсилає його MPI_Bcast; вивести найбільшу нев’язку.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує $n$, виконує метод Гаусса з вибором головного елемента в стовпці (MPI_Allreduce з MPI_MAXLOC), зворотний хід і виводить нев’язку, час та порівняння блокового й циклічного розподілу рядків.

3. Високий рівень. Створити проєкт CMake з програмою gaussmpi з опціями --input <файл>, --size <n>, --distribution block|cyclic, --output <файл> і --help, яка читає систему з текстового файлу, виявляє вироджену матрицю (код 3), записує розв’язок і виводить таблицю часу й нев’язки для 1–16 процесів.

Варіант 19. Хвильове рівняння 1D

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка моделює коливання струни (явна схема для хвильового рівняння, ${10}^6$ вузлів, 2000 кроків) з поділом на блоки й обміном гало MPI_Sendrecv і виводить енергію струни на початку й наприкінці.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка моделює коливання струни (явна схема для хвильового рівняння) з поділом на блоки між рангами й обміном гало. Програма запитує кількість вузлів на процес, кроків і число Куранта (перевірка стійкості), вимірює слабку масштабованість для 1–16 процесів і виводить час, ефективність і зміну енергії струни.

3. Високий рівень. Створити проєкт CMake з програмою wave1d мовою C++ з MPI, яка моделює коливання струни явною схемою для хвильового рівняння з блоками вузлів на рангах і обміном гало, з опціями --nodes <n>, --steps <k>, --courant <c>, --mode strong|weak, --snapshots <тека> і --help. Програма записує профілі струни в CSV (збирання MPI_Gatherv), перевіряє збереження енергії з допуском і виводить таблицю масштабованості. Нестійка схема – код 1.

Варіант 20. Статистика продажів мережі

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій ранг 0 створює 100 000 записів продажів (структура: магазин, сума, дата), описує їх похідним типом MPI_Type_create_struct, розподіляє операцією MPI_Scatter, а MPI_Reduce підсумовує виручку за 10 магазинами.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка читає записи продажів із CSV на ранзі 0 (ім’я файлу вводить користувач), розподіляє їх MPI_Scatterv похідним типом, обчислює виручку, кількість чеків і середній чек за магазинами й місяцями та виводить таблицю.

3. Високий рівень. Створити проєкт CMake з програмою salesmpi з опціями --input <файл.csv>, --group shop|month|both, --top <k>, --report <файл> і --help, яка власною операцією редукції (MPI_Op_create) знаходить найбільший чек із номером магазину, пропускає некоректні рядки з повідомленням у stderr і виводить звіт. Відсутній файл – код 2.

Варіант 21. Трасування променів

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка рендерить сцену з трьох сфер (зображення 800×600, один промінь на піксель) з розподілом рядків між рангами й збиранням MPI_Gather на ранзі 0 у файл scene.ppm.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка рендерить сцену зі сфер трасуванням променів. Програма запитує роздільність і кількість променів на піксель, розподіляє між робітниками тайли 32×32 за схемою «майстер–робітник», збирає зображення у файл PPM і виводить час та кількість тайлів кожного робітника.

3. Високий рівень. Створити проєкт CMake з програмою raympi мовою C++ з MPI, яка рендерить трасуванням променів (з тінями й відбиттями) сцену, описану в текстовому файлі, розподіляючи тайли зображення між процесами. Опції: --scene <файл>, --size <ш>x<в>, --spp <n>, --tile <k>, --output <файл.ppm>, --help. Програма зберігає зображення й виводить таблицю часу для статичного й динамічного розподілу тайлів на 2–16 процесах.

Варіант 22. Лісові пожежі

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка моделює клітинний автомат лісової пожежі (дерево, вогонь, попіл) на сітці $600\times 600$ з декартовою топологією 2D і обміном гало, починаючи з вогню в центрі, і виводить кількість згорілих дерев.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка моделює клітинний автомат лісової пожежі (дерево, вогонь, попіл) на сітці з декартовою топологією 2D і обміном гало. Програма запитує розмір сітки, щільність лісу й імовірність займання, використовує незалежні генератори з урахуванням глобальних координат (результат не залежить від кількості процесів) і виводить частку згорілих дерев та кількість кроків до згасання.

3. Високий рівень. Створити проєкт CMake з програмою fire мовою C++ з MPI, яка моделює клітинний автомат лісової пожежі на сітці, розподіленій між процесами, з опціями --size <n>, --density <d1,d2,…>, --runs <k>, --wind <напрям>, --csv <файл> і --help. Для кожної щільності лісу програма виконує $k$ моделювань, записує середню частку згорілих дерев і час, виводить таблицю й щільність, за якої частка перевищує 50 %.

Варіант 23. Пошук підрядка в геномі

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій ранг 0 генерує послідовність ДНК з ${10}^8$ символів ACGT, розсилає частини MPI_Scatter, кожен ранг рахує входження заданого шаблону довжиною 12 у своїй частині, а MPI_Reduce дає загальну кількість.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка шукає всі входження шаблону довжиною $m$ у згенерованій послідовності ДНК: ранг 0 розсилає частини послідовності, кожен ранг отримує від правого сусіда $m-1$ символів (MPI_Sendrecv), щоб врахувати входження на межах частин. Позиції входжень збираються MPI_Gatherv на ранзі 0 і перевіряються послідовним пошуком.

3. Високий рівень. Створити проєкт CMake з програмою dnasearch з опціями --genome <файл.fasta>, --patterns <файл>, --mismatches <k> і --help, яка шукає кілька шаблонів з допуском $k$ замін, виводить таблицю «шаблон – кількість – перші позиції» та час для 1–16 процесів. Помилки формату FASTA – код 2.

Варіант 24. Інтегрування Сімпсона із заданою точністю

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка обчислює ${\int }_0^{1}4/(1+x^2)\mathrm{d}x$ методом Сімпсона з ${10}^6$ відрізків, розподілених між рангами, і виводить результат та похибку.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка обчислює інтеграл методом Сімпсона з відрізками, розподіленими між рангами. Програма запитує функцію, межі й точність, подвоює кількість відрізків, доки різниця двох наближень (однакова на всіх рангах завдяки MPI_Allreduce) не стане меншою за точність, і виводить таблицю подвоєнь.

3. Високий рівень. Створити проєкт CMake з програмою simpson з опціями --func <назва>, --range <a>:<b>, --eps <e>, --adaptive і --help, де режим --adaptive розподіляє підінтервали за схемою «майстер–робітник» з рекурсивним поділом, і вивести порівняння рівномірного й адаптивного методів за кількістю обчислень функції та часом.

Варіант 25. Кластеризація документів групами

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, яка ділить процеси на дві групи MPI_Comm_split (парні й непарні ранги); кожна група обчислює суму своїх рангів MPI_Allreduce у власному комунікаторі, а кожен процес виводить свій ранг у світі й у групі.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, у якій документи (вектори частот 100 слів) розподілено між рангами, процеси діляться на $g$ груп (вводить користувач), кожна група виконує k-means з власним $k$ у своєму комунікаторі, а ранг 0 збирає якість кластеризації груп і виводить найкраще $k$.

3. Високий рівень. Створити проєкт CMake з програмою docclust з опціями --input <тека>, --k-list 2,4,8, --groups <g> і --help, яка будує вектори TF-IDF текстових файлів, запускає k-means для різних $k$ паралельно в групах процесів і виводить таблицю «$k$ – сума квадратів відстаней – час».

Варіант 26. Моделювання ризиків банку

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг моделює ${10}^6$ сценаріїв річної зміни вартості портфеля (нормальний розподіл дохідності, зерно дорівнює рангу), а ранг 0 після MPI_Reduce виводить середній збиток.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, у якій ранги моделюють методом Монте-Карло сценарії річної зміни вартості портфеля. Програма запитує кількість сценаріїв, склад портфеля (3 активи з дохідністю й волатильністю) і рівень довіри, збирає збитки на ранзі 0 (MPI_Gatherv) і виводить VaR, очікуваний збиток і 95 % довірчий інтервал середнього.

3. Високий рівень. Створити проєкт CMake з програмою varsim з опціями --portfolio <файл.csv>, --scenarios <n>, --confidence 0.95,0.99, --seed <s> і --help, яка обчислює VaR без збирання всіх сценаріїв (гістограма збитків MPI_Reduce і пошук квантиля), порівнює з точним методом для малих $n$ і виводить таблицю. Помилки файлу – код 2.

Варіант 27. Блокуючі й неблокуючі обміни

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій ранги утворюють кільце й передають блок з 1000 чисел double правому сусідові 100 разів трьома способами (MPI_Sendrecv, MPI_Isend/MPI_Irecv з MPI_Waitall, парні/непарні з MPI_Send/MPI_Recv) і виводить час кожного.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка запитує розмір блоку, демонструє взаємоблокування з MPI_Ssend (після тайм-ауту MPI_Test виводить попередження й завершує програму MPI_Abort) і вимірює, для якого розміру MPI_Send перестає завершуватися без отримувача.

3. Високий рівень. Створити проєкт CMake з програмою overlap з опціями --sizes 1e3,1e5,1e7, --work <мкс>, --mode block|nonblock|test і --help, яка вимірює, яку частку часу обміну вдається сховати за обчисленнями неблокуючими операціями (з періодичним MPI_Test і без нього), і виводить таблицю для всіх розмірів.

Варіант 28. Гібридна множина Жюліа

1. Початковий рівень. Створити консольну програму мовою C++ з MPI і OpenMP, яка обчислює множину Жюліа ($c=-0,8+0,156i$, 1600×1200, 1000 ітерацій): рядки діляться між рангами циклічно, а в межах рангу – потоками schedule(dynamic); ранг 0 збирає кількість ітерацій.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI і OpenMP, яка обчислює множину Жюліа (рядки між рангами, у межах рангу – потоками). Програма запитує $c$, роздільність і кількість ітерацій, збирає зображення на ранзі 0 (MPI_Gatherv) у файл PGM і виводить кількість рангів, потоків, рівень підтримки потоків і час.

3. Високий рівень. Створити проєкт CMake з програмою juliahybrid мовою C++ з MPI і OpenMP, яка обчислює множину Жюліа (рядки між рангами, у межах рангу – потоками) з опціями --c, --size, --iter і --help, та скрипт, який порівнює конфігурації «ранги × потоки» з різними --map-by і --bind-to (зокрема --bind-to none і один ранг з 8 потоками без PE), записує в CSV час і прив’язку з --report-bindings та виводить найкращу конфігурацію.

Варіант 29. Префіксна сума

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій кожен ранг має 1000 випадкових чисел, обчислює локальну префіксну суму, а зміщення рангу отримує операцією MPI_Exscan; ранг 0 збирає масив і перевіряє його послідовним обчисленням.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка реалізує префіксну суму сум рангів алгоритмом рекурсивного подвоєння (${\log }_{2}p$ кроків MPI_Sendrecv з рангом $r\pm 2^k$), порівнює результат і час з MPI_Scan та виводить таблицю.

3. Високий рівень. Створити проєкт CMake з програмою prefix з опціями --count <n>, --method scan|doubling|gather, --op sum|max і --help, яка підтримує довільну (не лише степінь двійки) кількість процесів, перевіряє результат і виводить таблицю часу методів для 1–16 процесів. Невдала перевірка – код 4.

Варіант 30. Модель α–β

1. Початковий рівень. Створити консольну програму мовою C++ з MPI, у якій ранги 0 і 1 виконують «пінг-понг» повідомленнями від 1 байта до 1 МБ (кратно 4) і ранг 0 виводить таблицю часу передавання в один бік і пропускної здатності.

2. Базовий рівень. Створити консольну програму мовою C++ з MPI, яка вимірює «пінг-понг» для розмірів з файлу або клавіатури, методом найменших квадратів знаходить $\alpha$ і $\beta$ моделі $T(m)=\alpha +\beta m$ і виводить виміряний та прогнозований час з відносною похибкою.

3. Високий рівень. Створити проєкт CMake з програмою alphabeta з опціями --sizes <список>, --reps <k>, --pairs same-node|any, --csv <файл> і --help, яка вимірює параметри для пар рангів на одному вузлі й на різних вузлах (файл вузлів), прогнозує час обміну гало для заданої сітки й процесів і порівнює з виміряним.

Порядок виконання та захисту роботи

1. Опрацювати теоретичні відомості та приклади розв’язання завдань.
2. Встановити Open MPI в Ubuntu 26.04 (WSL2 або віртуальна машина), перевірити версію командою ompi_info --version і запустити приклад «Привіт, MPI» для 4 процесів.
3. Створити проєкт CMake з find_package(MPI REQUIRED) (і OpenMP для гібридних завдань), реалізувати послідовну версію завдання й перевірити результат паралельної версії для різної кількості процесів, зокрема такої, на яку розмір задачі не ділиться.
4. Переконатися у відсутності взаємоблокувань: запустити програму з великими повідомленнями, а за потреби замінити MPI_Send на MPI_Ssend для перевірки.
5. Виміряти час для 1, 2, 4, 8 і 16 процесів (медіана щонайменше 5 запусків, MPI_Wtime, час найповільнішого рангу), частку комунікацій, для гібридних завдань – різні конфігурації «ранги × потоки» з --report-bindings; побудувати таблицю й графік прискорення та пояснити результати. За наявності кількох ВМ повторити вимірювання з файлом вузлів.
6. Продемонструвати роботу програми, пояснити код і результати вимірювань, відповісти на контрольні питання.