Mandelbrot Set

Суть проекта

Основная идея этого проекта - на примере построения множества Мандельброта изучить различные методы аппаратно-ориентированной оптимизации.

Математическое определение множества Мандельброта

Множество Мандельброта ℳ определяется как множество комплексных чисел c ∈ ℂ, для которых рекуррентная последовательность:

$Z_n = Z_{n-1}^2 + Z_0$

остается ограниченной при n → ∞. $Z_0$ - фиксированная точка на комплексной плоскости.

Выражение в координатах выглядит следующим образом:

$x_{n+1} = x_n^2 - y_n^2 + x_0$
$y_{n+1} = 2x_ny_n ~~~ + y_0$

Критерий принадлежности

Точка c принадлежит ℳ тогда и только тогда, когда для всех n ∈ ℕ: $|Z_n| ≤ R$

На практике вычисляется до конечного числа итераций N.

В работе принято N = 256 и R = 10.

Рассмотренные в работе варианты оптимизаций

1. Отсутствие оптимизации.

Функция для вычисления принадледности точки множеству Мандельброта написана каких-либо оптимизаций, обрабатываем по одной точке за раз.

2. Использование флагов компилятора.

Я использую компилятор g++ с флагом:

-O3

3. Автоматическая векторизация компилятором.

В функции для вычисления принадледности точки множеству Мандельброта вместо обработки по одной точке, начинаем обрабатывать сразу по 8 точек плоскости, в результате чего компилятор оптимизирует код.

4. Ручная векторизация при помощи intrinsic-ов.

В функции для вычисления принадледности точки множеству Мандельброта также обрабатываем по 8 точек за раз, но теперь оптимизируем код вручную, используя intrinsic-и.

Сборка на Linux x86-64

Для сборки необходимо написать в коммандной строке:

make

Запуск

Для запуска программы необходимо написать в командной строке имя исполняемого файла:

./do

Взаимодействие с программой

После запуска программы будет открыто окно с изображением множества Мандельброта. Предусмотрена возможность взаимодействия:

• Перемещение по графику:

  • W - Вверх
  • A - Влево
  • S - Вниз
  • D - Вправо

• Zoom графика:

  • Z - Увеличение
  • X - Уменьшение

• Режимы работы.

  В зависимости от режима работы будет вызываться функция с той или иной оптимизацией.

  • 1 - Без ручных оптимизаций
  • 2 - Векторизация компилятором
  • 3 - Векторизация intrinsic-ами

• Завершение программы:

  • Q

Результаты оптимизаций

Для оценки эффективности оптимизаций будем использовать значение fps, полученное встроенной функцией.

Измерения проводились на ноутбуке Thunderobot 911S Core D

Измерения проводились на начальном положении рисунка (при перемещении по рисунку fps может значительно меняться). Для более точных результатов также была ограничена частота процессора до 2Ghz.

-	Без использования флага -O3	С использованием флага -O3
Без ручных оптимизаций	5	11
Векторизация компилятором	5	26
Векторизация intrinsic-ами	12	48

Источники

• Wikipedia