Použití SSE instrukcí
Pro zrychlení výpočtu se nabízí využití instrukcí ze sady SSE, resp. SSE2. Konkrétně instrukce PSADBW. Kód lze zapisovat buď přímo pomocí assembleru nebo s pomocí tzv. intrinsics funkcí, které kompilátor přímo zamění za instrukce v assembleru:
__m128i _mm_sad_epu8 (__m128i a, __m128i b);
Tato funkce umožňuje vezme dvě 128-bitové proměnné (tj. 16 bytů) a provede součet absolutních hodnot rozdílů jednotlivých bytů (viz dokumentace).
Použití této instrukce ovšem znamená, že rozdíl mezi jednotlivými barevnými složkami již nelze brát jako kvadrát součtů jejich rozdílů, ale pouze jako součet absolutních hodnot těchto rozdílů. Při testech jsem ovšem nepozoroval nějaké významné zhoršení (pouze při některých konfiguracích).
Velkým problémem znemožňujícím efektivnější použití SSE instrukcí se bohužel ukázala nutnost pro každé porovnání (resp. pro každých X porovnání) přesunovat data do vyhrazené paměti. Nalézt efektivní způsob tohoto přesunu, resp. nějaký obecný vzorec, který by umožnil některá data pro pixely v pozicích posunujícího se klouzavého okna zachovat a nenačítat opakovaně (byť na jiných pozicích), se mi zatím bohužel nepodařilo.
Algoritmus s implementovanými SSE instrukcemi probíhá takto:
- Do (zarovnané) paměti jsou načteny validní pixely v kontextovém okně okolo právě řešeného pixelu.
- Do paměti je načteno okolí X (specifikováno uživatelem) pixelů pro X validních pozic klouzavého okna.
- Těchto X pozic je porovnáno a vybrán pixel (střed) s nejmenší chybou.
- Kroky 2 a 3 se opakují, dokud ještě existují nepoužité validní pozice (
počet pozic / X). - Pokud ještě existují maskované pixely, znovu ke kroku 1; jinak konec.
Výsledky běhu algoritmu s a bez implementovaných SSE instrukcí (testovacím obrázkem byl obrázek Krajina – viz článek Non Parametric Sampling - první verze). Levý sloupec označuje velikost kontextových oken:
| solveScalar() | solveWithSse() | solveWithSseSingleChunk() | ||||
|---|---|---|---|---|---|---|
| powDiff | absDiff | 32 chunks | 256 chunks | 2048 chunks | ||
| 7 px | 49 s | 49 s | 40 s | 41 s | 42 s | 41 s |
| 13 px | 172 s | 174 s | 137 s | 139 s | 143 s | 138 s |
| 19 px | 327 s | 374 s | 297 s | 299 s | 311 s | 294 s |
Pozn.: solveWithSseSingleChunk() řeší speciální případ, kdy je do paměti načten vždy jen jedno klouzavé okno.
Z tabulky je patrné, že při "skalárním" zpracování není velký rozdíl v době výpočtu rozdílu barev mezi použitím absolutní hodnoty a mocněním. V případě SSE instrukcí pak nehraje příliš roli počet najednou nahrávaných klouzavých oken ("chunků"). Přibližné zrychlení oproti "skalárnímu" zpracování je cca. 20%.
Bohužel se tedy zdá, že tento druh paralelismu při stávající implementaci velké zlepšení nepřináší.
Eventuálním řešením by možná mohlo být rozdělit prohledávány prostor na cca. čtyři menší a jednotlivé prostory prohledávat samostatnými vlákny. Výsledné 4 nejlepší pixely pro konkrétní hledaný maskovaný pixel by pak už jen stačilo porovnat mezi sebou. Výhodou by také byl fakt, že by již nebylo třeba nijak přesouvat data v paměti.
EDIT: Projekt je nyní dostupný na githubu (pouze zdrojové kódy).