2 лабораторных по Параллельным алгоритмам и системам на C++

2 Лабораторные работы на тему Параллельные алгоритмы и системы. Пример выполненной работы имеется

Первая лаба - Решение СЛАУ методом Гаусса. Вторую работу можно взять любую из списка.

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

Задача стационарного распределения тепла (двумерная или трехмерная)

Задача моделирования вибрации струны

Задача N-тел (NBODY).

Алгоритм поиска кратчайших путей (Флойда, Дейкстра)

Хеш-таблица с закрытой адресацией

Хеш-таблица с открытой адресацией (напр. hopscotch)

Сбалансированное бинарное дерево (RB, AVL)

Очередь с приоритетом

Быстрые методы сортировки (подсчетом, Шелла, BucketSort, сортировка быстрыми выборами)

Очередь с приоритетами (любая)

Примерное содержание отчёта:

1. Исходный код (можно взять где угодно, в т.ч. спросить у ChatGPT)

2. Проблемные места (hotspots), подтвержденные анализом (perf, intel vtune или что-то другое), измерить среднее время работы и другие метрики. Возможные метрики (выбрать как минимум несколько): кэш-миссы, предсказания переходов, время выполнения программы, CPI, IPC, кол-во инструкций и т. п. Показатель эффективности вашей оптимизации кода, как раз и будет оцениваться с помощью метрик.

3. Серия оптимизаций кода

Привести код после оптимизации

После каждой оптимизации повторный анализ из п. 2.

Оптимизация параметров оптимизации, если применимо (напр. фактор раскрутки цикла, ширина векторизации)

Выводы

4. Для итоговой программы

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

Сравнить с исходной программой, скомпилированной компилятором с ключами О1, О2, О3 и т.д.

5. Общие выводы

Требования к программе

1. Компиляцию выполнять с ключем О0 (кроме п. 4)

2. Рекомендуемые языки С, С++, LLVM IR, Ассемблер

3 .Среда: GNU/Linux, MacOS, WSL

4. Компиляторы: Clang/LLVM, GCC, ICC (желательно провести эксперименты на обоих)