1. Множество Мандельброта

Алгоритм

В программе используется многопоточный перебор точек в области ([-2; 2] \times [-1; 1]) для построения множества Мандельброта.
Определены глобальные переменные, общие для всех потоков:

static uint64_t       g_requested_points;   // сколько точек нужно найти
static uint64_t       g_collected_points;   // сколько точек уже найдено
static complex double *g_points_buffer;     // массив найденных точек

Каждый поток работает в своей подполосе по оси x. Для него заранее вычисляются x_start и x_end так, чтобы диапазоны потоков не пересекались:

args->x_start = -2.0 + x_segment_width * (double)i;
args->x_end   = args->x_start + x_segment_width;

Поток перебирает точки в своём диапазоне и для каждой проверяет, принадлежит ли она множеству Мандельброта. Если точка подходит, поток блокирует мьютекс, обновляет глобальные переменные (увеличивает счётчик и записывает точку в массив) и сразу освобождает мьютекс. Как только достигается требуемое количество точек (g_requested_points), потоки прекращают работу.

Выводы

Многопоточность значительно улучшает производительность при поиске множества Мандельброта, особенно на больших объёмах данных. Эксперименты показывают заметное ускорение при увеличении количества потоков, однако прирост производительности уменьшается после 4 потоков. На малых объёмах данных создание и управление потоками добавляет накладные расходы, поэтому ускорение при увеличении числа потоков может быть незначительным. Оптимальная эффективность достигается при использовании примерно 6–8 потоков, дальнейшее увеличение числа потоков не всегда оправдано из‑за накладных расходов на их управление.

Результаты

2. Read-write lock

Алгоритм (my rwlock)

Общая идея

• Вся структура защищена одним мьютексом mutex.
• Используются две условные переменные:
  • r_cv — ожидание читателей
  • w_cv — ожидание писателей
• Состояние:
  • r_locked_c — сколько читателей держат блокировку сейчас
  • w_locked — держит ли блокировку писатель (0/1)
  • rlock_wait_c, wlock_wait_c — сколько потоков ждут rdlock/wrlock
• Ожидание выполняется через while (...) pthread_cond_wait(...) (учитывает ложные пробуждения).
• Политика — writer-preference: если есть ожидающий писатель, новые читатели не заходят, чтобы не было голодания писателей.

wrlock()

• Захватываем mutex, увеличиваем wlock_wait_c.
• Ждём, пока нет активного писателя (w_locked == 0) и нет активных читателей (r_locked_c == 0).
• Уменьшаем wlock_wait_c, выставляем w_locked = 1.
• Освобождаем mutex.

rdlock()

• Захватываем mutex, увеличиваем rlock_wait_c.
• Ждём, пока нет активного писателя (w_locked == 0) и нет ожидающих писателей (wlock_wait_c == 0).
• Уменьшаем rlock_wait_c, увеличиваем r_locked_c.
• Освобождаем mutex.

unlock()

• Захватываем mutex.
• Если блокировку держал писатель: сбрасываем w_locked = 0.
• Если блокировку держал читатель: уменьшаем r_locked_c.
• Пробуждение:
  • если есть ожидающие писатели и блокировка полностью свободна — будим одного писателя (signal(w_cv)),
  • иначе будим всех читателей (broadcast(r_cv)).
• Освобождаем mutex.

Результаты

Тестирование: 80000 ключей, 1500 операций, коэффициенты 0.5 для поиска и вставки (удаление = 0), число потоков: 1, 4, 8.

1 поток (pthread)

Inserted 80000 keys in empty list
Rwlock implementation: pthread
Elapsed time = 6.793249e-01 seconds
Total ops = 1500
member ops = 800
insert ops = 700
delete ops = 0

1 поток (my)

Inserted 80000 keys in empty list
Rwlock implementation: my
[MY] Elapsed time = 7.462749e-01 seconds
[MY] Total ops = 1500
[MY] member ops = 800
[MY] insert ops = 700
[MY] delete ops = 0

4 потока (pthread)

Inserted 80000 keys in empty list
Rwlock implementation: pthread
Elapsed time = 5.294771e-01 seconds
Total ops = 1500
member ops = 767
insert ops = 733
delete ops = 0

4 потока (my)

Inserted 80000 keys in empty list
Rwlock implementation: my
[MY] Elapsed time = 4.557230e-01 seconds
[MY] Total ops = 1500
[MY] member ops = 767
[MY] insert ops = 733
[MY] delete ops = 0

8 потоков (pthread)

Inserted 80000 keys in empty list
Rwlock implementation: pthread
Elapsed time = 5.615220e-01 seconds
Total ops = 1500
member ops = 752
insert ops = 744
delete ops = 0

8 потоков (my)

Inserted 80000 keys in empty list
Rwlock implementation: my
[MY] Elapsed time = 4.871681e-01 seconds
[MY] Total ops = 1500
[MY] member ops = 752
[MY] insert ops = 744
[MY] delete ops = 0

Выводы

• В однопоточном режиме библиотечный pthread_rwlock_t оказался быстрее (0.679 c против 0.746 c), что ожидаемо из‑за меньших накладных расходов.
• В многопоточном режиме собственная реализация показывает лучшую производительность:
  • 4 потока: 0.529 c → 0.456 c (примерно −14%)
  • 8 потоков: 0.562 c → 0.487 c (примерно −13%)
• Итог: my_rwlock_t в этих тестах лучше масштабируется при росте числа потоков и использует приоритет писателей, снижая риск голодания писателей при большом числе читателей.

---

3 Задача N тел

1. Формулирова задачи

Дано N материальных точек с массами m_k, положения которых в начальный момент времени заданы радиус-векторами r_k, а скорости векторами v_k (k = 1, N). Требуется определить траектории всех частиц для времени от 0 до t_end.

Физическая модель

Задача основана на законе всемирного тяготения Ньютона:

2. Реализация

2.1 OpenMP версия

Файл: nbody_minimal.cpp

Параллелизация:

• Директива #pragma omp parallel for для вычисления ускорений
• Динамическое планирование задач: schedule(dynamic)
• Параллельное обновление позиций и скоростей

Ключевые особенности:

#pragma omp parallel for schedule(dynamic)
for (int i = 0; i < n; i++) {
    // Вычисление ускорений для частицы i
    for (int j = 0; j < n; j++) {
        if (i == j) continue;
        double dx = particles[j].x - particles[i].x;
        // ... расчет силы тяготения
    }
}

2.2 CUDA версия

Файл: nbody_cuda_minimal.cu

Параллелизация:

• Один CUDA поток на каждую частицу
• Размер блока: 256 потоков
• Архитектура GPU: sm_89 (Ada Lovelace)

Ключевые особенности:

__global__ void computeAccelerationsKernel(
    const double* x, const double* y, const double* z,
    const double* mass, double* ax, double* ay, double* az, int n)
{
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i >= n) return;
    
    // Каждый поток вычисляет ускорение для своей частицы
    for (int j = 0; j < n; j++) {
        // ... расчет силы тяготения
    }
}

3. Тестовая конфигурация

Входные данные

Файл: input.txt

3
0.0 0.0 0.0 0.0 0.0 0.0
1.496e11 0.0 0.0 0.0 2.978e4 0.0
1.500e11 0.0 0.0 0.0 3.001e4 0.0

Описание системы:

• Частица 1 (Солнце): масса 10²⁴ кг, в центре координат, без начальной скорости
• Частица 2 (Земля): на расстоянии 1.496×10¹¹ м (1 а.е.), орбитальная скорость 29.78 км/с
• Частица 3 (Луна): на расстоянии 1.5×10¹¹ м, скорость 30.01 км/с

Параметры симуляции:

• Время симуляции: 100 секунд
• Количество шагов: 10,000
• Количество точек вывода: 1,000

4. Результаты экспериментов

4.1 Производительность

Реализация	Время выполнения	Ускорение
OpenMP (12 потоков)	3.939 сек	1.0× (базовая)
CUDA (RTX 4070)	0.375 сек	10.5×

Вывод: CUDA версия в 10.5 раз быстрее OpenMP версии благодаря массивному параллелизму GPU.

4.2 Вывод программ

CUDA версия:

OpenMP версия:

5. Формат выходных данных

Файл: output.csv

Формат:

t x1 y1 x2 y2 x3 y3
0.0 0.0 0.0 1.496e+11 0.0 1.5e+11 0.0
0.1 ... ... ... ... ... ...

Где:

• t — время (секунды)
• x1, y1 — координаты первой частицы (Солнце)
• x2, y2 — координаты второй частицы (Земля)
• x3, y3 — координаты третьей частицы (Луна)

Количество строк: 1,001 (начальное состояние + 1,000 промежуточных)