Powitać

Jest dana tabela liczb całkowitych:
int tab[SIZE][N];

I jest dany wektor liczb całkowitych:
int vec[SIZE];

I jest program który oblicza sumę warunkową:

int suma = 0;
for( int i=0 ; i<SIZE ; i++ )
if( tab[i][COL1] <= VAL1 AND tab[i][COL2] <= VAL2 AND tab[i][COL3]
<= VAL3 )
suma += vec[i];

Zadanie polega na tym, aby tak dobrać stałe COL1,COL2,COL3 i VAL1,
VAL2, VAL3; żeby
uzyskać maksymalną sumę.

Załóżmy że używamy algorytmu brut force, czyli sprawdzamy wszystkie
możliwości.

I teraz moje pytanie: Jakie przyspieszenie można uzyskać w takim
algorytmie
jeśli go się zaimplementuje w jakiejś technologii jak w temacie na
najnowszych
kartach graficznych? Przyspieszenie względem nowych procesorów
głównych.

Z góry dziękuję
Pozdrawiam

do góry

Mariusz Marszałkowski pisze:
> Zadanie polega na tym, aby tak dobrać stałe COL1,COL2,COL3 i VAL1,
> VAL2, VAL3; żeby
> uzyskać maksymalną sumę.
>
> Załóżmy że używamy algorytmu brut force, czyli sprawdzamy wszystkie
> możliwości.
>
> I teraz moje pytanie: Jakie przyspieszenie można uzyskać w takim
> algorytmie
> jeśli go się zaimplementuje w jakiejś technologii jak w temacie na
> najnowszych
> kartach graficznych? Przyspieszenie względem nowych procesorów
> głównych.

Sporo zależy od tego jaki procesor i jaka karta, ale ogólnie o ile
tablica zmieści się w szybkiej pamięci to myślę, że około
80% ze stosunku MHz (czyli np (512 rdzeni * 950MHz) / (4 rdzenie *
3000MHz). Jak masz te tablice duże to w sumie nie wiem - pewnie trzeba
by liczyć wiele sum równolegle 'porcjami' na jednym rdzeniu tak aby
optymalnie wykorzystać pamięć.

--
Pozdrawiam
Michoo

do góry

Mariusz Marszałkowski <m...@g...com> wrote:

> Załóżmy że używamy algorytmu brut force, czyli sprawdzamy wszystkie
> możliwości.
>
> I teraz moje pytanie: Jakie przyspieszenie można uzyskać w takim
> algorytmie
> jeśli go się zaimplementuje w jakiejś technologii jak w temacie na
> najnowszych
> kartach graficznych? Przyspieszenie względem nowych procesorów
> głównych.

Nie wiem, jak na kartach graficznych, ale na zwykłym CPU z rozkazami
SSE2 mógłbyś uzyskać ok. 4-krotne przyspieszenie (jeśli sizeof(int)=4).

w.

do góry

On 30/07/2010 15:53, Mariusz Marszałkowski wrote:
> int suma = 0;
> for( int i=0 ; i<SIZE ; i++ )
> if( tab[i][COL1]<= VAL1 AND tab[i][COL2]<= VAL2 AND tab[i][COL3]
> <= VAL3 )
> suma += vec[i];
>
> Zadanie polega na tym, aby tak dobrać stałe COL1,COL2,COL3 i VAL1,
> VAL2, VAL3; żeby uzyskać maksymalną sumę.

masz jakieś dodatkowe ograniczenia odnośnie VAL1 VAL2 VAL3 ? Bo jeżeli
nie, to najprostszym "algorytmem" będzie
VAL1 = MAXINT;
VAL2 = MAXINT;
VAL3 = MAXINT;
COL1 = 0; COL2 = 1; COL3 = 2;



B.

do góry

On 30 Lip, 21:26, Bronek Kozicki <b...@s...net> wrote:
> On 30/07/2010 15:53, Mariusz Marszałkowski wrote:
>
> > int suma = 0;
> > for( int i=0 ; i<SIZE ; i++ )
> >    if( tab[i][COL1]<= VAL1 AND tab[i][COL2]<= VAL2 AND tab[i][COL3]
> > <= VAL3 )
> >       suma += vec[i];
>
> > Zadanie polega na tym, aby tak dobrać stałe COL1,COL2,COL3 i VAL1,
> > VAL2, VAL3; żeby  uzyskać maksymalną sumę.
>
> masz jakieś dodatkowe ograniczenia odnośnie VAL1 VAL2 VAL3 ? Bo jeżeli
> nie, to najprostszym "algorytmem" będzie
> VAL1 = MAXINT;
> VAL2 = MAXINT;
> VAL3 = MAXINT;
> COL1 = 0; COL2 = 1; COL3 = 2;

W sumowanym wektorze są też liczby ujemne, nie można wybrać po
prostu całego zakresu.

Pozdrawiam


.

do góry

On 30 Lip, 18:04, Michoo <m...@v...pl> wrote:
> Mariusz Marszałkowski pisze:
>
> > Zadanie polega na tym, aby tak dobrać stałe COL1,COL2,COL3 i VAL1,
> > VAL2, VAL3; żeby
> > uzyskać maksymalną sumę.
>
> > Załóżmy że używamy algorytmu brut force, czyli sprawdzamy wszystkie
> > możliwości.
>
> > I teraz moje pytanie: Jakie przyspieszenie można uzyskać w takim
> > algorytmie
> > jeśli go się zaimplementuje w jakiejś technologii jak w temacie na
> > najnowszych
> > kartach graficznych? Przyspieszenie względem nowych procesorów
> > głównych.
>
> Sporo zależy od tego jaki procesor i jaka karta, ale ogólnie o ile
> tablica zmieści się w szybkiej pamięci to myślę, że około
> 80% ze stosunku MHz (czyli np (512 rdzeni * 950MHz) / (4 rdzenie *
> 3000MHz). Jak masz te tablice duże to w sumie nie wiem - pewnie trzeba
> by liczyć wiele sum równolegle 'porcjami' na jednym rdzeniu tak aby
> optymalnie wykorzystać pamięć.

A tak można policzyć?
- procesor ma 80GFLOPS
- karta ma 5000GFLOPS
więc należy spodziewać się że na karcie wykona się 62 razy szybciej?

Dane zmieszczą się w pamięci karty grafiki.
Karta np. Redeon 5970.

Pozdrawiam

do góry

On 30 Lip, 18:25, Wojciech Muła
<w...@p...null.onet.pl.invalid> wrote:
> Mariusz Marszałkowski <m...@g...com> wrote:
> > Załóżmy że używamy algorytmu brut force, czyli sprawdzamy wszystkie
> > możliwości.
>
> > I teraz moje pytanie: Jakie przyspieszenie można uzyskać w takim
> > algorytmie
> > jeśli go się zaimplementuje w jakiejś technologii jak w temacie na
> > najnowszych
> > kartach graficznych? Przyspieszenie względem nowych procesorów
> > głównych.
>
> Nie wiem, jak na kartach graficznych, ale na zwykłym CPU z rozkazami
> SSE2 mógłbyś uzyskać ok. 4-krotne przyspieszenie (jeśli sizeof(int)=4).

Tak, typem podstawowym może być int32, albo float32.

Pozdrawiam

do góry

On Fri, 30 Jul 2010 17:18:42 -0700 (PDT)
Mariusz Marszałkowski <m...@g...com> wrote:

> A tak można policzyć?
> - procesor ma 80GFLOPS
> - karta ma 5000GFLOPS
> więc należy spodziewać się że na karcie wykona się 62 razy szybciej?

To sa wartosci teoretyczne i tak naprawde ciezko powiedziec ile maja wspolnego z
rzeczywistoscia. Jezeli bedziesz to robil na floatach to na karcie bedzie szybciej,
jezeli bedziesz mial liczby calkowite to one na procesorze sa sumowanie szybciej
niz float(na procesorze). Karta graficzna z kolei zawsze musi wykonywac dzialania na
floatach. Wniosek, wiec jest taki ze jezeli dodawanie(na intach, jezeli robisz na
intach)
i operacja warunkowa jest szybsza na procu niz tylko dodawania na floatach na
karcie(bo
podobno if na karcie jest za darmo) to na procu bedzie szybciej.


--
Michal

do góry

On 31/07/2010 01:09, Mariusz Marszałkowski wrote:
> W sumowanym wektorze są też liczby ujemne, nie można wybrać po
> prostu całego zakresu.


ok, więc nieco poważniejsze rozważania. Trzymanie w pamięci jednej
zmiennej suma do której wszystkie wątki zapisują, zupełnie się nie
skaluje. Musisz wymyśleć lepszy algorytm.

Np - w każdym wątku pętla od 0 do SIZE, wątków tyle ile kolumn. Każda
pętla tworzy histogram elementów w kolumnie. Dodatkowo (jeszcze jeden
niezależny wątek) pętla tworząca historam wektora. Na podstawie
ostatniego będziesz widział z których wierszy możesz zrezygnować z
najmniejszą stratą, na podstawie histogramów kolumn będziesz wiedział
które kolumny maję najmniejszy maksymalny element, drugi od końca itd. i
w ten sposób sobie dobierzesz minimalne wartości N i pasujący wybór
kolumn. Z perspektywy przetwarzania wielowątkowego ważne jest że w ten
sposób rozbiłeś część zadania na wiele (liczba kolumn + jeden na wektor)
niezależnych wątków wykonania z których każdy zapisuje swoje własne dane
do pamięci. Co więcej, każdy wątek bedzie później mógł niezależnie te
histogramy analizować ze stosunkowo niewielką wymianą danych między
wątkami (preferowane wiersze do utraty, przesłane z histogramu wektora
do histogramów kolumn).

Jak to się ma do CUDA? Nie wiem, bo w tym nie programuję. Ale,
skalowalność na wiele wątków (sprzętowych czy programowych) działa tylko
wtedy, jeżeli nie musisz dostępu do danych synchronizować w każdym kroku.


B.

do góry

On 31 Lip, 15:29, Bronek Kozicki <b...@s...net> wrote:
> On 31/07/2010 01:09, Mariusz Marszałkowski wrote:
>
> > W sumowanym wektorze są też liczby ujemne, nie można wybrać po
> > prostu całego zakresu.
>
> Jak to się ma do CUDA? Nie wiem, bo w tym nie programuję. Ale,
> skalowalność na wiele wątków (sprzętowych czy programowych) działa tylko
> wtedy, jeżeli nie musisz dostępu do danych synchronizować w każdym kroku.
>
Właśnie tego nie wiem jak to szybko się wykona na GPU. Czy jest
możliwe zwiększenie wydajności o teoretyczny współczynnik 60 razy?

Pozdrawiam

do góry