« 1 2 3 4 »
Autor Zpráva
Oxidián
Profil *
A kolik má kapacitu instrukční cache to je jako ta "přídavná" paměť v procesoru?

Chtěl jsem to zkusit jak se pracuje s obrázky v php.

V tom odkaze co si dal se píšou dvě věci:

"Optimizing compilers will sometimes perform the unrolling automatically, or upon request."
Takže bych vlastně mohl stejné věci dosáhnout v tom C/C++. Jestli to ale podporuje kompilátor.

"If the statements in the loop are independent of each other (i.e. where statements that occur earlier in the loop do not affect statements that follow them), the statements can potentially be executed in parallel."

To jde v PHP spustit ty věci paralelně? Jako že bych začal zpracovávat např. 3 vnořené smyčky za sebou (tedy např. řadu pixelů kde souřadnice má y=1, y=2 a y=3)?


myslím zpracovávat je souběžně
juriad
Profil
Oxidián:
Kapacita závisí na procesoru. Její hodnota ti stejně nic neřekne, protože nevíš, jak je implementováno PHP, které si také něco ukousne. Buď se to do ní vejde, a poběží to rychle, nebo ne.

"Optimizing compilers will sometimes perform the unrolling automatically, or upon request."
Takže bych vlastně mohl stejné věci dosáhnout v tom C/C++. Jestli to ale podporuje kompilátor.
Kompilátory právě zváží mnohem více aspektů a dokážou dost dobře odhadnout, kdy se to vyplatí. V připadě iterace přes obrázek se to může vyplatit.

"If the statements in the loop are independent of each other (i.e. where statements that occur earlier in the loop do not affect statements that follow them), the statements can potentially be executed in parallel."
>
To jde v PHP spustit ty věci paralelně? Jako že bych začal zpracovávat např. 3 vnořené smyčky za sebou (tedy např. řadu pixelů kde souřadnice má y=1, y=2 a y=3)?
Pokud kompilátor dokáže, že jsou jednotlivé instrukce nezávislé, může lépe rozvrhnout pořádí instrukcí. A procesor si je pak stejně ještě přeuspořádá. Procesor dnes typicky mají více než jednu aritmetickou/floatovou jednotku v každém jádru, je tedy možné, že spustí třeba dvě nezávislá násobení „najednou“.
Pozor, jedná se o paralelizaci na úrovni instrukcí v procesoru, nikoli na úrovni programovacího jazyka. Procesory dnes obsahují plánovače, které pozměňují a plánují pořadí instrukcí, tak aby co nejlépe využili své prostředky.

Lepší než tři řady pixelů je zpracovávat tři pixely za sebou a inkrementovat po třech (což je přesně to, co dělá rozbalování smyček). Důvodem k tomu je lepší predikce práce s pamětí. Nemusíš načítat tři nezávislé bloky, ale pracuješ jen s jedním. Pokud je třeba navíc velikost obrázku mocninou dvojky, může to při práci s více řádky dopadnut ošklivě kvůli cachovému aliasingu. Asi bych se měl zmínit, že jsem měl o této problematice pár semestrálních přednášek, kdy jsme si zkoušeli na reálném počítači, jak se chová a co pomáhá/škodí.

To, o čem se teď bavíme se týká vnitřní architektury a chování dnešních procesorů. Programování v PHP je tomu na míle vzdálené, tam tak jemné nástroje nemáš k dispozici.
Oxidián
Profil *
Chápu to tak, že moderní procesor chce využít multithreadingu a že když zpracovávám např. obr. 256x256 px a načetl bych blok o velikost 256 px s y=1 tak compilátor predikuje, že v další smyčce se bude dělat to samé ale pro y=2, takže dokáže to zkompilovat nebo prostě předat procesoru tak že předá jednu řadu jednomu jádru s y=1 a druhou řadu druhému jádru s y=2. Možná to říkám špatně, možná multithreading nezávisí na počtu jader.
Joker
Profil
1Pupik1989:
Joker má chybu hned v prvních větvích else, protože už neporovná $R s $G
No jasně, omlouvám se.

Ještě by to mohlo urychlit nahrazení jedné podmínky logickým operátorem:
$min = (($B < $G) && ($B < $R)) ? $B : (($R < $G) ? $R : $G);
$max = (($B > $G) && ($B > $R)) ? $B : (($R > $G) ? $R : $G);

V benchmarku mi to možná vyšlo rychlejší, ale dělal jsem to na počítači, kde je velký rozptyl mezi testy.
1Pupik1989
Profil
Joker: Možná zkusit ještě klasické podmínky, tak by se to ještě o milisekundu zrychlilo. Pokud první podmínka splněna, tak nemusíš hledat minimální hodnotu. Pokud není splněna, tak zase není třeba hledat maximální.
juriad
Profil
Oxidián:
Netýká se jader, vše běží na jednom. Aby to běželo na více, musel bys explicitně naprogramovat vícevláknovou aplikaci. To, co popisuji se týká výpočetních jednotek uvnitř jednoho jádra. Jeden řádek cache na úrovni L1 obsahuje (v Pentiu 4, podle Wikipedie) 64 bytů, dnes to bude trochu víc. Tedy z hlavní paměti se do nejrychlejší cache přenese najednou souvislý blok 16 pixelů (jeden má obvykle 4B). Tedy na základě tohoto výpočtu bude procesor provádět operaci s každými 16 pixely docela rychle. Má tedy smysl rozvinout smyčku 16x a na jejím začátku zadat prefetch dalšího bloku paměti, mezitím zpracovat pixely aktuálního bloku. Změnou pořadí operací můžeš dojít k tomu, že se zároveň bude třeba sčítat a násobit. Pokud by jedna operace s pixelem byla třeba $val = $val * 0.2 + 0.1; (*), může se to vykonat takto:
load($val);
$val *= 0.2;
$val += 0.1;
store($val);
Při rozvinutí se z toho stane:
prefetch(next block);
load($val1);
$val1 *= 0.2;
$val1 += 0.1;
store($val1);
load($val2);
$val2 *= 0.2;
$val2 += 0.1;
store($val2);
load($val3);
$val3 *= 0.2;
$val3 += 0.1;
store($val3);
...
A z nezávislosti může procesor provést toto na jediném jádře v různých výpočetních jednotkách:
prefetch(next block);
load($val1);
$val1 *= 0.2; load($val2);
$val1 += 0.1; $val2 *= 0.2; load($val3);
$val2 += 0.1; $val3 *= 0.2; store($val1); load($val4);
$val3 += 0.1; $val2 *= 0.2; store($val2); load($val5);
...

Znovu opakuji, zápis v PHP na to nemá žádný velký vliv. Jaké konkrétně instrukce se vykonají při výpočtu (*), to závisí na implementaci PHP. Mluvit do toho také můžou akcelerátory. Zkus nějaký použít, třeba tak dosáhneš nějakého zajímavého zrychlení „bez práce“.
Oxidián
Profil *
Co myslíš tím "prefetch"?
juriad
Profil
Vyžádání dat z hlavní paměti dopředu (optimisticky), aby byla dostupná v cachi v okamžiku, kdy jsou skutečně potřeba.
http://en.wikipedia.org/wiki/Instruction_prefetch, nebo přimo od intelu
Joker
Profil
1Pupik1989:
Možná zkusit ještě klasické podmínky, tak by se to ještě o milisekundu zrychlilo.
Sice to podle mě bude o něco méně přehledné, ale rychlejší to bude:
if ($B < $G) {
  $min = ($R < $B) ? $R : $B;
  $max = ($R > $G) ? $R : $G;
}
else {
  $min = ($R < $G) ? $R : $G;
  $max = ($R > $B) ? $R : $B;
}

Benchmark mi potvrdil očekávání: Tahle varianta je nejrychlejší, ale rozdíly nejsou dramatické (počítač na kterém jsem to testoval má příliš kolísající zátěž než abych to uměl říct konkrétněji).

V každém případě kdyby i takové rozdíly byly kritické, bylo by lepší tu aplikaci programovat přímo v C a ne v PHP.
1Pupik1989
Profil
Joker:
Já to myslel takto:

if(($B < $G) && ($B < $R)){
  $min = $B;
  
  if($G < $R){
    $max = $R;
  }else{
    $max = $G;
  } 
}else{
  $max = $B;
  
  if($G < $R){
    $min = $G;
  }else{
    $min = $R;
  }
}

Nicméně mi stejně nejrychleji vychází:

if ($R < $G ){
  if($R < $B ){
    $min = $R;

    if($G < $B){
      $max = $B;
    }else{
      $max = $G;
    } 
    
  }else{
    $min = $B; 
    $max = $G;
  }
    
}else{
  if($G < $B){
    $min = $G;
    
    if($R < $B){
      $max = $B;
    }else{
      $max = $R;
    } 
     
  }else{
    $min = $B;
    $max = $R;    
  }
}

Je to ale podle vstupních hodnot. Pokud první podmínka bude splněna a vnořená podmínka ne, tak je to vlastně o jednu vnořenou podmínku ještě kratší. Pokud bude platit $R < $G < $B, tak bude nejrychlejší ten vrchní příklad z tohoto příspěvku. To už jsou ale takové zanedbatelné rozdíly, že to nemá cenu řešit. To by muselo být předem jasno který barevný kanál bude mít nejčastější nejnižší hodnotu.
Oxidián
Profil *
juriad:
Takže tím prefetch(next block); si myslel ne instrukci kterou píšu já, ale požadavek CPU do pěměti... Jestli to teda už chápu.

S tou L1 se mi zdá málo že by měla jen 64 bytů, tady jsem se díval:
http://www.tomshardware.co.uk/forum/263313-28-pentium-cache
a tam je zmínka o "8-KB Level 1 data cache" a "Level 1 Execution Trace Cache stores 12-K"
Dále tam někdo píše: "So, total L1 cache is 158KB for Northwoods and Williamettes, and 164KB thereafter."


Předpokládám, že když bych chtěl pracovat s maticema, např. na rozmazání obrázku nebo na nalezení okrajů masky, tak phpčku by to trvalo příliš dlouho. Ale přesto by mě tedy zajímalo jak bych to mohl realizovat z hlediska rozvržení, abych to urychlil, když bych pracoval s maticema jako tady.

http://www.phpied.com/canvas-pixels-2-convolution-matrix/
Hádám, že bych v tomto případě musel odkazovat na pixely nějak takto (pro devět pixelů):

$image[$y][$x+256]
$image[$y][$x+256+1]
$image[$y][$x+256+2]
$image[$y+1][$x+256]
$image[$y+1][$x+256+1]
$image[$y+1][$x+256+2]
$image[$y+2][$x+256]
$image[$y+2][$x+256+1]
$image[$y+2][$x+256+2]

abych mohl provést rozostření jen do vzdálenosti jednoho pixelu. Takže "jen" devět pixelů a to by se do 64 bytové chache nevešlo ani náhodou. Co teprve když bych chtěl načíst do vzdálenosti 5px... a k tomu aby si CPU mohl provést ten prefetch pro vedlejší pixel při dalším cyklu/kroku $x++; Ale jedno mi z toho je jasné, určitě, tady by se dalo tím rozbalením ušetřit hodně. Rozhodně lepší než provádět další dvě smyčky o řekněme n:=0;n<3;n++ a m:=0;m<3;m++ ... to by byla sebevražda. Jenže když to člověk chce udělat dynamicky a ty nevíš jak velký diametr uživatel zadá při spuštění programu, tak tím pádem to je třeba rozvětvit a už druhá větev dá 5x5 pixelů, třetí větev pak 7x7 pixelů a čtvrtá 9x9 a můžeme takhle pokračovat celkem 8 větví (takže tři podmínky se vyhodnocují celkem - rozhodnuto pomocí podobné zkrácené podmínky jako jsme použili v algoritmu pro nález minimální a maximální hodnoty).
Alphard
Profil
Oxidián [#11]:
Nečetl jsem detailně začátek diskuse, ale viděl jsem různé rady napsat to v něčem jiném. Určitě by to bylo rozumnější.

Ale přesto by mě tedy zajímalo jak bych to mohl realizovat z hlediska rozvržení, abych to urychlil, když bych pracoval s maticema jako tady.
Pro větší masky (tak od 10x10 výše) je lepší nejdříve převést do frekvenční oblasti a pak násobit po složkách než provádět přímou konvoluci.
juriad
Profil
Oxidián:
Ano, prefetch je instrukce, kterou vygeneruje kompilátor.
64B je jeden řádek cache, je to souvislý úsek hlavní paměti. Cache obsahuje těch cachových řádků 128 při celkové velikosti 8KB.

K těm maticím se vyjádřím později, musím letět na vlak. Je to mnohem složitější problematika a nevím, zda chci vysvětlovat něco, co stejně v PHP nedokážeš ovlivnit.
Oxidián
Profil *
juriad:
Napsal bych to v C++, možná bychom to mohli probrat tady:
Nezařaditelné dotazy o webu
Alphard
Profil
Oxidián:
Pokračujte v tomto vlákně, klidně i v jiném jazyce, ale nezakládejte duplicity.

Jestli to budete dělat v C++, existují efektivní knihovny, nemusíte to psát sám.
Oxidián
Profil *
Alphard:
A můžete dát tip? Mám na pc nainstalovanou knihovnu Boost, ale ještě jsem v tom nic nezkoušel dělat, takže nevím co všechno to umí.
Alphard
Profil
Netroufám si doporučit nějakou jednoduchou jednoúčelovou knihovnu, protože s nimi nemám moc zkušenosti. Aktuálně pracuji na jednom projektu s aplikací v medicíně, kde používáme ITK, takže bych jako první zkusil www.itk.org/Doxygen40/html/classitk_1_1ConvolutionImageFilter.html, trochu přehlednější příklad je na www.itk.org/Wiki/ITK/Examples/ImageProcessing/ConvolutionImageFilter.
Oxidián
Profil *
Alphard:
Ok dík za info.


Jinak mě napadlo, že když bych už nějakej ten filtr měl (nevím jak se tomu maticovému filtru říká česky), že bych mohl zkusit takovou optimalizaci. Jelikož většinou chci pracovat s černobílíma maskama, které chci rozostřit a v nich je spousta černého místa, kde by ten filtr běžel naprosto zbytečně.

Tady je to na tom obrázku. Jednotlivé čtverečky jsou pixely u hodně přiblíženého obrázku. To co jsem vyznačil šedýma čtverečkama je domnělá oblast, kterou by mohl filtr procházet.
http://oi61.tinypic.com/o7oq3r.jpg
Představa je taková, že před spuštěním filtru bych provedl detekci jestli ve světle šedých čtvercích je černá barva (ještě jednou: šedé čtverce jen vyznačují oblast na černobílé masce, kde jsou hodnoty B/W nic mezi tím). Mám tam 12 pixelů po obvodu čtverce. Když zjistím, že všechny jsou černé, tak si uchovám informaci že tento čtverec obsahuje černou barvu a tudíž ho nebudu muset zpracovávat filtrem. Toto by mohlo řekněme 14x urychlit zpracování obrazu. Jakmile budu mít pole či objekt s informacema, pak se při zpracovávání smyčky filtru podívám jestli dotyčný pixel neleží někde uvnitř toho objektu. Ovšem je otázka jestli by tento úkon vůbec mohl být proveden dostatečně rychle. S tím že by si uživatel mohl navolit velikost čtverce ....
1Pupik1989
Profil
Oxidián:
Tak to bych řešil ještě trochu jinak. Projel bych cyklem obrázek po 8 řádcích, kde na každém řádku bych detekoval, jestli barva není jiná než černá. Pokud taková situace nastane, pak bych aplikoval filtr. Jinak cyklus pojede dál a na konci řádku poskočí o 8 řádků níž, dokud neskončí na finálním pixelu v obrázku.
Oxidián
Profil *
1Pupik1989:
To by sice bylo jednodušší, ale má to několik nevýhod. Hlavní problém je v tom, že když například přez obrázek povede napříč bílá čára zezdola nahoru, tak se filtr bude aplikovat vždy a přesto bude většina polí černá... Moje představa je detekovat celý obrázek po čtvercích. Přitom bych potřeboval zapsat že daný čtverec, pojmenujme ho pro jednoduchost A1 neobsahuje bílou barvu (říkejme mu tedy "black" ). Takže A1 je black. Mám zapsáno. Zpracovávám sousední čtverec. A2 je black, zapíšu a pokračuju do dokončení první řady čtverců. Druhá řada (B): B1 je black, B2 je black, B3 je black, B4 je white, protože jsem narazil na bílý pixel. atd. C1 je black, C2 je black, C3 je black, C4 je black, C5 je white. Atd. Skončím někde u E6. Pak projdu ten objekt co shromažďuje tyto informace a porovnám sousední čtverce. U A1 se ptám: je A2 black? B1 je black? B2 je black? Pokud ano, pak A1 nastavím mu stav empty=true. Což znamená, že A1 nemusím filtrovat. Toto provedu s každým čtvercem. Např. u B2 zkontroluju: A1,A2,A3,B1,B3,C1,C2,C3. B2 nastavím empty=true. Ale B3 ani A3 ani C3 nebudou empty=true protože sousedí se čtvercem C5 white. Tyto čtverce sice jsou prázdné, ale sousedí s bílím čtvercem a já potřebuju aplikovat rozmazávací filtr i na ten černý čtverec, protože sousedí s bílou buňkou.

Mohl bych ještě analyzovat ještě další čtyři čtverce uvnitř kvůli přesnosti. Takže když vím, že A3, B3 a C3 mají stav empty=false, mohu zkontrolovat čtverce uvnitř a takže A3 se bude dělit na čtverce AA1,AA2,AB1 a AB2, ztoho první všechny jsou black, ale jen první tři budou mít stav empty=true. Tím pádem aplikuju filtr jen na AB2.
1Pupik1989
Profil
Kdyby byla bílá čára na uhlopříčku, tak se právě neaplikuje vždy. Pouze pokud narazí na bílý pixel. Takže když rozdělím obrázek na 4 čtverce/obdélníky a bílá čára by vedla z levého horního rohu do pravého dolního, tak se v levém dolním a pravém horním segmentu neaplikuje nic. Pokud narazí na bílou, tak jí musíš stejně zpracovat.

Nevím jestli si mě pochopil. Představa byla linka osmi bodů pod sebou.
Oxidián
Profil *
Já bych to nechal na uživateli, ať si zadá sám jaký chce mít tvar toho čtverce/obdelníku. Třeba bude chtít výšku nebo šířku obrázku a třeba bude chtít testovat jen každý druhý pixel/řádek.


Napadlo mě, že když jde o B/W masku, tak vlastně je zbytečné provádět rozostření pokud máš před sebou velkou bílou polochu, která neobsahuje žádný černý okraj. To je vlastně to samé. Jen by se musely zvlášť porovnávat čtverce bílé barvy nebo černé barvy. Nakonec i kdyby tam bylo těch barev více (například maska, která používá 3 nebo 4 barvy), tak vždy lze aplikovat stejný princip.
1Pupik1989
Profil
Co vlastně ve výsledku ze všech těch kódů má být? Aplikace uživatelsky definovaných filtrů na obrázek?

Jinak jsem v PHP zkoušel metodu rgb2hsv a rychleji mi vyjde můj první příklad.

Testováno na 1000000 iteracích.

Tvoje vyjde 2.3109719753265.
Moje vyjde 1.5082588195801.

Pokud nepoužiji pole, tak je ještě rychlejší.

Výsledek: 1.2833871841431
Oxidián
Profil *
1Pupik1989:
Jinak jsem v PHP zkoušel metodu rgb2hsv a rychleji mi vyjde můj první příklad.
Teď už nevím který kód myslíš. Já teď používám ten zkrácený kód, případně tu delší verzi, tj. ty u kterých jsem naměřil nejrychlejší čas. Takže nevím o jakých verzích teď mluvíš. Ten kód který jsem napsal já a jeho opravenou verzi už nepoužívám.

Jo, měla by to být aplikace ve které můžeš použít nějaké grafické filtry, hlavně ty maticové.

Dnes jsem si uvědomil, že existuje mnohem jednodušší a rychlejší i účinnější cesta jak naprogramovat tu detekci sousedících čtverců - říkejme tomu ale pro jednoduchost grid system. Teda zatím jsem to nezrealizoval, takže jsem čas ještě neměřil. Jaký je nejjednodušší grid systém v grafice? Zmenšíš obrázek na potřebnou velikost a dostaneš čtverce (pixely) o určité velikosti --> tedy když to porovnáš s původní velikostí tak víš jestli ted pixel v původní velikosti leží v té oblasti zmenšené velikosti. Při zmenšení obrázku dochází k rozmazání pixelů. Pokud máš velký bílý flek uprostřed obrázků, a ty si vybereš čtverec uprostřed, který je daleko od okrajů bílé plochy, tak se jeho barva nezmění ani po zmenšení rozmazání okolních čtverců. Z toho vyplývá že na tuto oblast nemusím aplikovat filtr.

Navíc u těch čtverců, jejich barva je rozmazaná a obsahují například pouze 20% černé, se dá vypočítat v jaké vzdálenosti se nachází bílá plocha. Tudíž mohu rovnou vytvořit ještě jeden zmenšený obrázek, jehož délka a šířka bude dělena 4 oproti původnímu obrázku. Tím pádem mohu detekovat tyto rozmazaná místa a prověřit, které podčtverce nepotřebují aplikovat filtr, protože nesousedí s černou plochou. Je to geniální. Pouze z toho kolik obrázek obsahuje dotyčné barvy nebo světla zjistíš jak daleko je okraj...

Dejme tomu že mám obrázek o velikosti 1024. Zmenším to na 0.5% (5x5px), 1% (10x10),2%(20x20),4%(41x41),8%(82x82),16%(164x164),32%(328x328). Pro představu těch dvou posledních velikostí: v původním obraze mám obdélník 15x6px. 16% zmenšení z nich udělalo 2x1px obdélník a 32% z nich udělalo černý obdélník 4x2 (o barvovém rozsahu HSV 0,0,2-4%). Z toho lze dedukovat že daná oblast sousedí z bílými pixely, i když převážná část je černá. Okraje pak jsou 4x6px o rozsahu HSV 0,0,45-94%. Z toho už budu vědět, že tuto plochu je třeba zahrnout do filtru. Jelikož celkem bílý obraz zabírá asi 40% plochy tak by se dalo dost času ušetřit, aniž bych prováděl detailní ověřování.
1Pupik1989
Profil
Myslel jsem kód z 18. příspěvku na předchozí straně. Konkrétně funkci rgb2hsv. Pokud použiji třídění z 3. příspěvku na předešlé stránce, tak se to zrychlí skoro o polovinu. Nejsem pak nucen používat podmínky pro porovnání kanálů s největší hodnotou typu if( $R == $max ), protože vím která ta maximální hodnota je. Navíc to zkrátí kód na polovinu. Inspiroval jsem se zde.

Taky zkusím napsat aplikaci maticových filtrů na obrázek, později se třeba hodí v javascriptu na textury.
Oxidián
Profil *
1Pupik1989:
V jakém jazyce to chceš psát? V php nebo C/C++? Nějaké matice jsou na té stránce, kterou jsem tu odkázal v #11, ale tam je to jen do nějaké omezené vzdálenosti. Bylo by fajn na ty matice udělat nějaký roztříděný objekt. Já přišel s nápadem třídit ty matice takto: když zadá uživatel že chce použít "brush" tak dostane kulatý tvar matice. Když zadá, že chce kernel, tak bude použita čtvercová matice. Jen zvolit správný typ, velikost čtverce a zesilovací faktor.
1Pupik1989
Profil
Oxidián:
Zatím to píšu v PHP, přepsat už to nebude problém. Inspiraci jsem našel na Lodev. Mám pouze čtvercové matice. Čtvercové nechám pořád, akorát budu vynechávat indexy, které se nemají použít. Takže jediné co mi přibude je typ použití.
Oxidián
Profil *
Fajn stránka. Na to bych mohl taky mrknout když je to v céčku
1Pupik1989
Profil
Tak při použití matice 3x3 na obrázek kytky z lodevu to trvá 0.535 sekundy. To je hodně pomalé. Pokud se to nebude používat často, tak by asi i PHP stačilo. Násobím zatím i nulové hodnoty, jelikož mě ještě nenapadlo jak upravit násobení hodnoty s rgb. Možná floaty z matice převedu na celá čísla a nakonec vydělím.
Oxidián
Profil *
1Pupik1989:
Zapomněl jsem se podívat na tu stránku co si posílal link:
http://lolengine.net/blog/2013/01/13/fast-rgb-to-hsv
Tak ta je hodně dobrá. Budu to muset zkusit až bude čas. Supr!

Zatím jsem blur v php nezkoušel, takže nemohu porovnat.
« 1 2 3 4 »

Vaše odpověď

Mohlo by se hodit

Odkud se sem odkazuje


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0