On Thursday, April 18, 2013 12:43:14 PM UTC+2, Edek wrote:
[...]
> Wersja ze strony Intela wyrabiała się w 1.5s (rozsądna była 2.5s)
> czyli 60% czasu, ja dodatkowo zrównolegliłem a gcc wykonało jeszcze
> jakieś voodoo i jest 30% czasu rozsądnej:
Czyli bardzo duży zysk.


> Wynik jest prawdopodobnie ok, ale nie jest idealnie taki sam. Przez dobre
> 10 minut szukałem błędu i mam nauczkę, żeby z assemblerem się
> ostrożnie obchodzić, bo nie wiem czy jest błąd czy nie. A jak w czymś
> tak prostym nie potrafię znaleźć błędu przez 10 minut to oznacza
> tylko jedno: system error, wrong language.
W ogóle w dowolnym języku testy pisane na kolanie to kontrowersyjna sprawa,
ale mamy na to tyle czasu ile mamy a nie więcej. W tym moim kodzie który
dałem na początku też jest fatalny błąd.


> Dodatkowo okazało się, że jakakolwiek logika branchy w pętli
> wewnętrznej strasznie "boli". Przypuszczam, że wektoryzacja gcc
> o ile dobrze potrafi radzić sobie ze zrównoleglanymi danymi,
> to nawet tak proste ify jak w mandalbrocie już te algorytmy
> analizujące przerastają.
Czy można podsumować ten wątek tak, że kompilatory jednak
rewelacyjnego kodu nie generują? Okazuje się, że tę prostą
procedurę można przyspieszyć wielokrotnie. Więc co się
dzieje na procedurach dużych i naprawdę skomplikowanych?
Duże skomplikowane procedury można przyspieszyć 30 razy
względem rozsądnej implementacji?


Pozdrawiam

do góry

W dniu 2013-04-17 19:48, AK pisze:
> Użytkownik "Miroslaw Kwasniak" <m...@i...zind.ikem.pwr.wroc.pl>
> napisał:
>
>> Ale długo to trwało, bo Cooley&Tukey nie byli piewszymi, którzy
>> wynaleźli FFT
>> ;)
>
> O ! A to ciekawostka. Bylem przekonany, ze to oni.
> Mozesz rozwinac termat ?
> Czyzby "zerzneli" ?

Ojtam zerznęli. Tak samo jak lemat Zorna udowodnił Kuratowski
10 czy 20 lat przed Zornem;-)

This method (and the general idea of an FFT) was popularized by a
publication of J. W. Cooley and J. W. Tukey in 1965,[2] but it was later
discovered (Heideman & Burrus, 1984) that those two authors had
independently re-invented an algorithm known to Carl Friedrich Gauss
around 1805 (and subsequently rediscovered several times in limited forms).

The most well-known use of the Cooley-Tukey algorithm is to divide the
transform into two pieces of size N/2 at each step, and is therefore
limited to power-of-two sizes, but any factorization can be used in
general (***as was known to both Gauss and Cooley/Tukey***).

pzdr
bartekltg

do góry

Dnia Thu, 18 Apr 2013 10:43:14 +0000 po głębokim namyśle Edek rzekł:

> Dnia Thu, 18 Apr 2013 02:04:18 -0700 po głębokim namyśle M.M. rzekł:
>
>> Ja raczej nie napiszę w ASM, większość dawno temu zapomniałem :) Czy
>> mógłbyś podrzuć mi wersję tej procedury w asmie, tak żebym mógł ją
>> skompilować GCC64 bity? Czyli musiałby to być jakiś asembler osadzony.
>
> Napisałem wersję AVX, powinna działać na i3:

Oops, korekta. Chyba jednak nie będzie działać, zerknąłem do cpuinfo.

Ale może ktoś albo sprawdzi albo uwierzy na słowo tudzież
wynik "time". Można też w prosty sposób zamienić instrinsici
na krótsze niż 256bit.

--
Edek

do góry

>
>
> http://pastebin.com/PEDVihPP
>

no spoko, w sumie nawet ciekawe
(sam kod avx wlasciwie taki sam
jak ta wersja softlab testowana
przeze mnie - skad pomysl by to
tak rozwinac na 12 pikseli ?
12 pikseli dziala najszybciej ?

do góry

Dnia Thu, 18 Apr 2013 04:41:51 -0700 po głębokim namyśle M.M. rzekł:

> On Thursday, April 18, 2013 12:43:14 PM UTC+2, Edek wrote:

> ale mamy na to tyle czasu ile mamy a nie więcej. W tym moim kodzie który
> dałem na początku też jest fatalny błąd.

Pierwsza zasada benchmarka: nie zmienia się benchmarkowanej metody.
Druga: zaczyna się od poprawnej (czego nie można się spodziewać
po tym baranie - mam dosyć konkursu)

>> Dodatkowo okazało się, że jakakolwiek logika branchy w pętli
>> wewnętrznej strasznie "boli". Przypuszczam, że wektoryzacja gcc o ile
>> dobrze potrafi radzić sobie ze zrównoleglanymi danymi,
>> to nawet tak proste ify jak w mandalbrocie już te algorytmy analizujące
>> przerastają.
> Czy można podsumować ten wątek tak, że kompilatory jednak rewelacyjnego
> kodu nie generują? Okazuje się, że tę prostą procedurę można
> przyspieszyć wielokrotnie. Więc co się dzieje na procedurach dużych i
> naprawdę skomplikowanych?
> Duże skomplikowane procedury można przyspieszyć 30 razy względem
> rozsądnej implementacji?

No ale ja użyłem gcc i wynik jest lepszy 2x od flagowej strony Intela
o AVX. Poza tym algorytmy mają swoje znane właściwości. No, chyba
że twierdzisz, że do każdego algorytmu grafowego zastosujesz OpenMP -
pokaż wynik "time". Możemy zostać ze swoimi wnioskami.

--
Edek

do góry

On Thursday, April 18, 2013 1:46:18 PM UTC+2, Edek wrote:

> Oops, korekta. Chyba jednak nie b�dzie dzia�a�, zerkn��em do cpuinfo.
> Ale mo�e kto� albo sprawdzi albo uwierzy na s�owo tudzie�
> wynik "time". Mo�na te� w prosty spos�b zamieni� instrinsici
> na kr�tsze ni� 256bit.

Nawet nie chce się u mnie to skompilować. Ale oczywiście wierzę.

Najważniejsze pytanie w tym wątku, czy można generalizować te wyniki na inne
programy?

Pozdrawiam

do góry

W dniu czwartek, 18 kwietnia 2013 13:35:34 UTC+2 użytkownik Edek napisał:
> Dnia Thu, 18 Apr 2013 04:17:29 -0700 po g��bokim namy�le firr kenobi
>
> rzekďż˝:
>
>
>
> > z kt�rej stronki? troche g�upio jest odnosic to co sie pisze do stronki
>
> > bez podania dokladnie o jakďż˝ chodzi , nie ;)
>
>
>
> Przepraszam Wodza... niech w�dz poszuka Intela w necie.
>
>
hehe - spox ale nie dziw
sie ze nie chce rozmawiac z osobami proponujacymi rozmaowa na tego typu poziomie
(wiecej meki w brnieciu przez glupote
rozmowcy niz pożytku)

do góry

fakt nie zauazylem ze tam moze byc || - to dobre wiesci bo
czasem test dzialalby juz po jednym ifie c:

do góry

On 2013-04-14 10:52, Borneq wrote:
> Jaki jest schemat podpisywania cyfrowego dokumentu przez większą ilość
> osób/programów?
> Nie można tego znależć w Google.

A jednak:
http://lmgtfy.com/?q=multi+party+digital+signature

--
Michal

do góry

W dniu 2013-04-18 10:28, M.M. pisze:
> On Thursday, April 18, 2013 9:44:56 AM UTC+2, firr kenobi wrote:
>> a czemu taka dziwna petla
> Nie wiem... znam akurat taką implementację rysowania
> tego fraktala. Co jest w niej dziwne? Jaka jest lepsza?

Była w wątku;)

>> czy dwa warunki na fabsa sa szybsze
>> niz jeden na x*x+y*y>4. ? moze
>> cztery x<-2, x>2 y<-2, y>2 bylyby szybsze
>
> Jak dwa warunki, jak cztery? Nie kumam :)

const double tmp = x*x - y*y + _x;
if( std::fabs(tmp) > 2.0 ) break; //pierwszy
y = 2.0 * x * y + _y;
if( std::fabs(y) > 2.0 ) break; //drugi
x = tmp;


Wersja, o której myśli fir wygląda tak:

double x=0, y=0, xx=0,yy=0;

for( i=0 ; i<inf ; i++ )
{
y = 2.0 * x * y + _y;
x = xx - yy + _x;
xx = x*x;
yy = y*y;
if (xx+yy>4.0) break;
}

Idea jest taka, że skoro i tak kwadratujemy wspolrzedne
by obliczyć cześć rzeczywistą, to możemy je wykorzystać
do normy. Żadnych abs i tylko jeden warunek.
Trzeba tylko pamiętać, żeby przed pętlą inicjować
nie tylko x i y, ale też ich kwadraty, xx,yy.

To jest zresztą jedna z optymalizacji, przy której
nie wierzę, by komputer na nią wpadł na podstawie
kodu zapisanego elegancko na zmiennych zespolonych;)

BTW, jakiś kompilator wpada choćby na to, że
if ( liczba.abs()< stala )
to to samo co
if ( liczba.norm()< stala*stala )
?

A tego speca, co nazwał kwadrat normy normą to...


> Na takim obszarze przy większej wartości inf mam wszystko czarne:
> https://thumbs.rapidshare.com/thumbs/1024/F28/9A4A63
B42170BFFB707E1970E39E1.jpg

Zrób lepszą paletę;)

To jakie masz to inf. Zmieniając je wyniki nie będą się
tak do końca liniowo skalować.


> Robię na takim:
> x1 = -1.40105941;
> y1 = -0.00005182;
> x2 = -1.40116832;
> y2 = 0.00004030;
> inf = 60000;

Łojej! 60 tysięcy? ładne obrazki na [-1,1]^2 to dla 30 wychodzą;)

pzdr
bartekltg

do góry