Генерация фракталов с помощью SSE/SSE2 - CvtTss2si м макрос FASM

ОГЛАВЛЕНИЕ

CvtTss2si

После окончания расчета программа должна перевести результаты в значения цветов. Одна строка кода (*b++ = a[i];) может произвести перевод в C, но на языке ассемблера придется сделать больше работы.

Программа устанавливает xmm6 в ноль и прибавляет к нему 4.0 на каждой итерации (смотрите код любого метода выше). Если внутренний цикл не прерывается, он повторяется ITER раз. При завершении цикла число полных итераций умножается на 4 в регистре xmm6 при условии, что точка не принадлежит набору Мандельброта, и там есть значение ITER * 4 в противном случае. Можно провернуть такой же трюк с последним элементом массива: добавить один элемент к массиву и приравнять его значение к черному. С помощью такого приема можно использовать один код окраски для обработки точек, входящих в набор Мандельброта, и точек, не входящих в него. FFFF v3.2.2 по-разному обрабатывает эти типы точек, используя условную пересылку (это более медленный путь, и команду CMOV не поддерживают некоторые старые процессоры AMD).

Заметьте, что регистр xmm6 хранит число полных итераций, умноженное на 4. FFFF делит его, чтобы получить индекс в палитре. Для деления он использует команду shr, медленно работающую на процессорах Pentium IV с номером модели меньше 3. Но один элемент палитры занимает 4 байта в памяти. Таким образом, FFFF делит число на 4, а затем умножает его на 4, чтобы получить сдвиг в памяти. Какая ужасная потеря времени! Это делается гораздо проще:

CVTTSS2SI eax, xmm6
; xmm6 содержит сдвиг в палитре, т.е. 4*число итераций
mov eax, [esi + eax]  ; палитра начинается в [esi]
mov [edi], eax        ; текущий пиксель битовой карты находится в [edi]

Команда CvtTss2si преобразует, с усечением, значение с плавающей точкой с одинарной точностью в целое значение в регистре eax. Количество итераций, разумеется, целое число. Оно преобразуется без округления, поэтому режим округления тут не важен. Следующая команда извлекает цвет из палитры, а последняя команда записывает цвет в битовую карту. Битовая карта может находиться в видеопамяти или в ОЗУ (пока не беспокойтесь об этом).
Есть другие команды для преобразования чисел с плавающей точкой (а именно, CvtPs2Pi и CvtPs2Dq), но ни одна из них не записывает результат в регистры общего назначения. Приходится сохранять число в памяти и сразу читать его из того же самого места, что вызывает дополнительные задержки в Pentium IV. Тестирование кода с CvtPs2Dq показало, что он не быстрее кода, использующего CvtTss2si.

Мощь макроса FASM

Написание нескольких вариантов одного и того же кода для набора Мандельброта и для набора Джулии, для чёрно-белого изображения и для цветного изображения, для SSE и для SSE2, требует много рутинной работы. К счастью, большинство ассемблеров имеет специальные инструменты, способные сделать эту работу за вас. Инструменты - макрокоманды и условная компоновка. Макросы позволяют повторять последовательность команд с разными параметрами, а условная компоновка позволяет вставлять команды в зависимости от этих параметров.

Был выбран FASM 1.62 из нескольких ассемблеров, потому что он маленький, быстрый и имеет богатый синтаксис макросов. Руководство по FASM подробно описывает синтаксис. Ниже приведен маленький кусок из метода Vodnaya для иллюстрации использования макросов в программе:

macro JuliaMandelPaint color, type {
; ...
   ADDPS  xmm1, xmm1
   SUBPS  xmm0, xmm3
if type = Julia
   ADDPS  xmm1, dqword[cy1]
   ADDPS  xmm0, dqword[cx1]
else if type = Mandel
   ADDPS  xmm1, xmm5
   ADDPS  xmm0, xmm4
end if
; ...
}

Если аргумент type равен Julia, FASM сгенерирует код, добавляющий cx1 к xmm0 и cy1 к xmm1, иначе он будет использовать значения из регистров xmm4-xmm5. Оба варианта кода будут сгенерированы: первый с меткой JULIA и второй с MANDELBROT. Вы лишь проверяете переменную fractaltype и решаете, какой вариант использовать.
Можно сказать, что есть более легкий способ сделать это:

   mov eax, [fractaltype]
   test eax, eax
   jz MANDELBROT
   ADDPS  xmm1, dqword[cy1]
   ADDPS  xmm0, dqword[cx1]
   jmp NEXT
MANDELBROT:
   ADDPS  xmm1, xmm5
   ADDPS  xmm0, xmm4
NEXT:

Почему бы не использовать этот код? Потому что проверка находится в глубоко вложенных циклах, и сравнение повторится несколько миллионов раз, тогда как его надо делать всего один раз. Нечего и говорить о задержках, возникающих при не предсказании условного перехода. Поэтому выгодно вынести сравнение за пределы цикла. Макросы помогают кратко записать это.

Следующая интересная задача – адаптация методов под SSE2. Команды SSE2 параллельно работают над двумя значениями двойной точности. В иных аспектах они не отличаются от SSE. Даже задержки и производительности для SSE2 те же, что и для SSE.

Надо провести массовый поиск с заменой, чтобы изменить ADDPS на ADDPD, MULPS на MULPD, MOVAPS на MOVAPD, и т.д. Затем надо поправить увеличения указателей и получить две функции: одну – для SSE и одну – для SSE2. Такой подход применяется в FFFF и нескольких других программах. У него есть один серьезный недостаток. При обновлении программы приходится менять один и тот же код в обеих функциях. Это нудно и неприятно. Иногда исправляют одну функцию, но забывают изменить другую.

Идея такова – создать макрос по имени MOVAP, заменяемый на MOVAPS для SSE и на MOVAPD для SSE2. Теперь вместо двух функций пишется только одна, и в ней используются макросы MOVAP, MULP и ADDP. Во время компиляции реальные команды SSE или SSE2 используются вместо этих макросов:

macro MOVAP a, b {
   if ssewidth = 4
      MOVAPS a, b
   else
      MOVAPD a, b
   end if
}

Не спешите писать этот код! Есть более элегантное решение:

macro defineinstr instr, [args] {
   common
   if ssewidth = 4
      instr#S args
   else
      instr#D args
   end if
}

Макрос defineinstr принимает переменное число аргументов. Например, он может использоваться для SHUFPS с 3 аргументами и для ADDPS с 2 аргументами. Макрос выдает команду с суффиксом S, если ssewidth = 4, или ту же самую команду с суффиксом D в противном случае. Оператор # соединяет имена; common означает, что команда повторится всего один раз.

Можно еще сократить этот код:

macro defineinstr instr {
   macro instr [args] \{
   \common
      if ssewidth = 4
    instr#S args
      else
    instr#D args
      end if
   \}

Тут есть два вложенных макроса. Внешний макрос defineinstr определяет внутренний макрос instr. Заметьте, что instr также является аргументом defineinstr, поэтому при написании defineinstr MOVAP будет определен макрос по имени MOVAP. Это как раз то, что надо. Фигурные скобки и директиву common надо экранировать обратным слешем из-за каких-то странных проблем парсинга внутри FASM. Теперь определение новой команды SSE/SSE2 очень краткое и простое: пишется defineinstr и имя команды. Число аргументов не имеет значения.
Теперь вы убедились, что макросы FASM очень мощные и изящные. Если нет, попробуйте сделать макрос препроцессора C с переменным числом аргументов, и сравните его с эквивалентом FASM!

Копирование битовых карт с помощью GDI и DirectDraw

Функция SetPixel кажется самым медленным из возможных способов вывода пикселей на экран:

case WM_PAINT: {
   PAINTSTRUCT ps;
   HDC hdc = BeginPaint(hWnd, &ps);
   for(x = 0; x < w; ++x)
      for(y = 0; y < h; ++y)
          SetPixel(hdc, x,y, b[i]);
   EndPaint(hWnd, &ps);
}

Используйте эту функцию только для установки 1 или 2 пикселей; она слишком медленная для больших изображений. Ниже приведена более быстрая упрощенная версия программы:

int w, h; HBITMAP hBMP = 0, holdBMP; HDC hmem;
BITMAPINFOHEADER bi = {sizeof(BITMAPINFOHEADER), 0, 0, 1, 32, BI_RGB};
void ReDraw() {
   PaintJuliaSSE(b, ceil(w, 4), h);
   SetDIBits(hmem, hBMP, 0, h, b,
            (BITMAPINFO*)&bi, DIB_RGB_COLORS);
            // Копировать битовую карту в hmem
}
LRESULT CALLBACK WndProc(HWND hWnd,UINT msg,WPARAM wParam,LPARAM lParam) {
   switch(msg) {
      case WM_SIZE: {
         HDC hdc = GetDC(hWnd);
         if(hBMP) { DeleteObject(SelectObject(hmem, holdBMP)); DeleteDC(hmem); }
         w = LOWORD(lParam), bi.biWidth = ceil(w, 4),
         h = HIWORD(lParam), bi.biHeight = h;
         bi.biSizeImage = bi.biWidth * h * 4;
         b = (long*)realloc(b, bi.biSizeImage);
         hBMP = CreateCompatibleBitmap(hdc, ceil(w, 4), h);
         hmem = CreateCompatibleDC(hdc);
         holdBMP = (HBITMAP)SelectObject(hmem, hBMP);
         ReleaseDC(hWnd, hdc);
         ReDraw();
         return 0;  }
      case WM_PAINT: {
         PAINTSTRUCT ps; HDC hdc = BeginPaint(hWnd, &ps);
         BitBlt(hdc, 0, 0, w, h, hmem, 0, 0, SRCCOPY);  // Копировать hmem на экран
         DrawPolyline(hdc);
         EndPaint(hWnd, &ps);
         return 0;   }
      case WM_DESTROY:
         DeleteObject(SelectObject(hmem, holdBMP)); DeleteDC(hmem);
         PostQuitMessage(0); return 0;
      default:
         return DefWindowProc(hWnd,msg,wParam,lParam);
   }
}

Функция ReDraw вызывается при каждом полном обновлении изображения, т.е. при его увеличении или уменьшении. Она использует PaintJuliaSSE для генерации битовой карты фрактала в b. Затем вызывается функция SetDIBits. Она копирует весь массив b в контекст устройства памяти hmem.

В ответ на WM_SIZE программа устанавливает новый размер битовой карты и заново создает ее. Также память для битовой карты перераспределяется, и фрактал полностью перерисовывается. Обработчик для WM_PAINT просто копирует контекст устройства памяти на экран и добавляет ломаную линию, показывающую орбиту функции.

Изображение фрактала хранится в контексте устройства памяти, существующем на протяжении всего времени работы программы. Имея это изображение, можно быстро нарисовать движущуюся ломаную путем копирования сохраненного изображения и рисования нового положения вышеназванной ломаной. Это вызовет небольшое мерцание ломаной, что допустимо. Добавление второго контекста устройства памяти и второй битовой карты может полностью убрать мерцание, но тогда программа будет тормозить и потреблять много памяти.
Команды SSE работают над 4 значениями параллельно, и все вышеприведенные методы SSE требуют, чтобы число пикселей в линии было кратно 4. Поэтому  ширина (w) округляется в большую сторону функцией ceil(w). Битовая карта становится немного больше чем надо, и в обработчике WM_PAINT из нее копируется только прямоугольник w * h.

Кроме GDI, программа также поддерживает DirectDraw. Код здесь не показан, потому что он очень длинный и скучный (обработка ошибок занимает много места). По сути, он сходен с кодом GDI. Создается скрытая поверхность; фрактал отрисовывается на нее. В WM_PAINT скрытая поверхность копируется на главную поверхность (на экран) и рисуется ломаная. Современные видеоплаты хранят обе поверхности в видеопамяти, следовательно, копирование с помощью DirectDraw может быть быстрее в 50 раз, чем копирование через GDI (данный результат был получен на ноутбуке с простой встроенной видеоплатой Intel 915 GM). DirectDraw повышает общее быстроту действия на 5-6% по сравнению с GDI.

DirectDraw поддерживается для Windows 98 и выше. Для поклонников Windows 95 было написано несколько строк кода, поэтому программа изящно перейдет на GDI, если DirectDraw отсутствует.

Заключение

Созданная программа является очень быстрым генератором набора Мандельброта и Джулии, использующим SSE/SSE2 и DirectDraw. Она не называется "быстрейшим генератором фракталов для Win32", как сделал автор FFFF, но программа очень быстрая и удобная. Некоторые пункты все еще требуют доработки, например:

•    есть  более быстрые алгоритмы, "угадывающие" значения соседних пикселей;
•    можно дополнительно оптимизировать методы MOV-ADD и Vodnaya, чтобы получить максимальную производительность на 64-битных процессорах;
•    может быть, существует какой-то хитрый подход к оптимизации предсказания ветвлений, но его не нашли;
•    программа не может сохранить текущее положение и параметр C, чтобы позволить вернуться к ним впредь (следующая версия будет делать это);
•    изменение палитры не поддерживается, но такой цели и не было.

Итак, код хороший, но не идеальный.

Можно использовать представленные в данной статье методы во множестве разных графических приложений. Анализ задержек и производительности помогает найти узкие места. Затем можно убрать операции с длинными задержками с критического пути, сделать несколько независимых цепей в коде и увеличить параллелизм на уровне команд путем переупорядочивания команд. Наконец, макросы ассемблера освобождают от такой скучной работы, как переписывание того же самого кода для SSE2.