On Sunday, March 4, 2012 11:13:42 AM UTC, wrote:
> Roman W <b...@g...pl> napisał(a):
>
> > On Sunday, March 4, 2012 5:46:00 AM UTC, M.M. wrote:
> > > Zawsze narzut na utworzenie watkow jest duzy, to nie wina OpenMP.
> >
> > Jezeli tworzysz watki recznie, narzut jest znacznie mniejszy.
>
> Mozesz to jakos uzasadnic i opisac jak uzywasz slowa "recznie"?
> Pozdrawiam

A kto pyta? ;-)

Mialem na mysli np. cos takiego:

#include <boost/thread.hpp>
#include <boost/timer.hpp>
#include <iostream>
#include <sstream>
#include <cmath>

template <class T> class global_data
{
public:
global_data(const T& data = T())
: m_data(data)
{
}

T& get() { return m_data; }
const T& get() const { return m_data; }
boost::mutex& mutex() { return m_mutex; }
private:
boost::mutex m_mutex;
T m_data;
};

template <class T> struct summator
{
summator(global_data<T>* d, T b, T e)
: begin(b), end(e), data(d)
{
}

void operator()()
{
T sum = T();
for (T i = begin; i < end; ++i)
sum += cos(i);
{
boost::lock_guard<boost::mutex> total_sum_lock(data->mutex());
data->get() += sum;
}
}

T begin;
T end;
global_data<T>* data;
};

template <class T> summator<T> make_summator(global_data<T>* d, T b, T e)
{
return summator<T>(d, b, e);
}

int main(int argc, char* argv[])
{
size_t n;
size_t d;
if (argc < 3) {
std::cerr << "Usage: " << argv[0] << " array-size number-of-threads" << std::endl;
return -1;
} else {
std::stringstream ss;
ss << argv[1];
ss >> n;
ss.clear();
ss << argv[2];
ss >> d;
}
if (n % d != 0) {
std::cerr << "array-size not exactly divisible by number-of-threads: " << n << "
and " << d << std::endl;
return -1;
}
const size_t s = n / d;
boost::thread_group tg;
global_data<double> total_sum(0.0);
for (size_t i = 0; i < d; ++i) {
tg.create_thread(make_summator(&total_sum, static_cast<double>(i*s), (i + 1.0)*s));
}
tg.join_all();
std::cout << "Total sum == " << total_sum.get() << std::endl;
}


Nawet dla parametrow przy ktorych program dziala tylko kilkanascie sekund (array-size
= 1000000) 2 watki wykonuja sie znacznie szybciej niz 1, a 4 to juz ho-ho.

RW

do góry

Roman W <b...@g...pl> napisał(a):

> Mialem na mysli np. cos takiego:
[ciach]
> Nawet dla parametrow przy ktorych program dziala tylko kilkanascie sekund (=
> array-size =3D 1000000) 2 watki wykonuja sie znacznie szybciej niz 1, a 4 t=
> o juz ho-ho.

Czyli stawiasz teze ze watki z boosta sa szybsze niz z OpenMP.
Nie mam wprawy w poslugiwaniu sie watkami boostowymi, na kolanie nie
napisze i nie sprawdze. Waskim gardlem w tworzeniu watkow jest wywolanie
systemowe i byc moze wykonanie specyficznych instrukcji procesora
plus przerzucanie/konflikty cache - zaleznie jak to jest zaimplementowane
na danym modelu procesora. Takie problemy ma kazda biblioteka, kazda
musi tworzyc watek za posrednictwem systemu. Mysle ze nie masz racji,
mysle ze OpenMP jest bardzo podobna pod wzgledem wydajnosci jak
kazda inna dobra(!) biblioteka, czy inny standard.

Zobacz ten program:
http://pastebin.com/Kw6pREMG

Uruchamiam go z parametrami:
13 1000000 3000
Czyli procedura wykonuje 1 milion petli i jest wywolywana 3tys
razy. Czas sumaryczny na i3 (dwa fizyczne prcesory, cztery z hyperthreading)
Dla 1 watku mam czas 13s.
Dla 2 .............. 7s
Dla 3 .............. 7s
Dla 4 .............. 6s
dla 20 .............. 7s

Oznacza to ze na jedno utworzenie watku przypada 13s / 3000 ~= 4ms
obliczen. A pomimo to OpenMP uzyskuje liniowe przyspieszenie. Nie widac
zadnego narzutu na tworzenie watkow. Nie mam pojecia i nie chce miec
pojecia (bo do czego mi to potrzebne?) czy OpenMP raz utworzylo watki i
sprytnie im przydziela zadania, czy moze tworzy je za kazdym razem od nowa
gdy to jest potrzebne. Po prostu cala ta robote zrobil za mnie kompilator i
OpenMP, ja raptem dopisalem jedna jedyna linijke kodu i mam ponad dwukrotne
przyspieszenie na czasie obliczen 4 ms.

Eksperymentowalem dalej, dodalem schedlule(static,1), czyli kazdy watek
bierze po JEDNEJ! petli.
#pragma omp parallel for reduction(+:res) schedule(static,1)
Jaki czas? Dla dwoch watkow na tym procesorze 11s, czyli pomimo ze jeden
watek otrzymuje okolo 20 taktow procesora do wykonania, to nadal widac
przyspieszenie.

Gdy dalem chunk=20
#pragma omp parallel for reduction(+:res) schedule(static,20)
To mam czas 10s dla dwoch watkow.

Czego mozna chciec wiecej? Wszystko wskazuje na to, ze OpenMP nawet nie
tworzy watkow, ale umie je sprytnie przytrzymac i dac im zadania zgodnie
z zaleceniami synchronizacji. No i do tego prostota, jeden wiersz aby
uzyskac zrwonoleglenie. Poza tym OpenMP umie sie komunikowac z innymi
programami uruchomionymi w systemi. Jesli inny proces przydzieli sobie np.
6 watkow, a system dysponuje 8 procesorami, to aplikacja otrzyma
tylko 2 watki - w aplikacjach obliczeniowych najczesciej wlasnie tak jest
optymalnie.

Ah, bym zapomnial, kompiluja to wszystkie popularne kompiltory C++ pod
wszystkie popularne systemy, niektore tylko sa troszke do tylu i nie
obsluguja najnowszej wersji. Pomysl ma potencjal, byc moze jeszcze inne
jezyki niz C++ i Fortan go zaadoptuja (a moze juz zaadoptowaly, a ja nie wiem)

Pozdrawiam



#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <omp.h>

typedef double T;

T* Inits( const int table_size ) {
T *table = new T[table_size];
for( int i=0 ; i<table_size ; i++ )
table[i] = (T)(rand()%1024 - rand()%1024);
return table;
}


T Compute( T table[] , const int table_size ) {
T res = 0;
#pragma omp parallel for reduction(+:res)
for( int i=0 ; i<table_size ; i++ ) {
res += table[i];
if( table[i] > +10 ) table[i] -= 1;
else if( table[i] < -10 ) table[i] += 1;
else if( i%2 ) table[i] -= 13;
else table[i] += 14;
}
return res;
}


int main(int argc, char *argv[]) {
srand( atoi(argv[1]) );
const int table_size = atoi(argv[2]);
const int iterations = atoi(argv[3]);
T *table = Inits( table_size );
const time_t start = time(NULL);
T res = 0;

omp_set_num_threads( 3 );

for( int i=0 ; i<iterations ; i++ )
res += Compute( table , table_size );


printf("result = %lf\n" ,(double)res );
printf("all time = %ds\n", (int)(time(NULL)-start) );

delete[] table;
return 0;
}

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Użytkownik " M.M." <m...@N...gazeta.pl> napisał w wiadomości grup
dyskusyjnych:jiuvio$ea6$...@i...gazeta.pl...
> Co Ty za podreczniki czytasz? :) To okolo 3% mozliwosci
> OpenMP :)

Oczywiście. Ale po co mi więcej - skoro program jest niczym innym tylko taką
pętlą po i wywoływaną w pętli po j ?

Przy tym tej po j nie da się z oczywistych powodów.

> Zawsze narzut na utworzenie watkow jest duzy, to nie wina OpenMP.

I tak. I nie. Np. mogę sobie wyobrazić rozwiązanie, w którym jest "czekająca
pula wątków" - i zamiast tworzyć nowy, jest aktywowany "stary". Ile wymaga
to wysiłku? Tzn. ile wymaga, jeżeli każdy wątek dostaje a priori własny
rdzeń, a zawiaduje tym wszystkim oddzielny CPU? Moim zdaniem tyle co nic -
ba! - to może być nawet realizowane hardware'owo.

> Nie milcza, pelno w sieci materialow.

I tak. I nie.

> Zrownoleglaj obliczenia ktore trwaja przynajmniej 60s na jednym
> watku, wtedy pisz ze dziwne jesli spowolni :)

One trwają... około tygodnia. ;) Ale przecież dla testów nie będę dawał
docelowych wielkości pętli itd. ;)

> No kurde jest. Bez OpenMP taki sam efekt uzyskujesz piszac 5-20 razy
> wiecej kodu. OpenMP robi to samo co bys zrobil sam bez OpenMP -

Niekoniecznie. Np. obsługa wątków w MS Windows jest trywialnie prosta
(jeżeli nie potrzeba niczego, lub prawie niczego, synchronizować). Problemy
są z synchronizacją i dostępem do rozmaicie pojmowanych zasobów. Akurat w
moim programie "część równoległa" jest naprawdę równoległa.

> Nie spada, po prostu uzywasz tira do przewozenia jednego pudelka zapalek.

Raczej wysłałem kierowcę TiR-em po jedno pudełko zapałek i sprawdzam, ile
czasu mu zajmie jazda w mieście. I okazuje się, że nie jest słodko - a to
nie przejedzie pod wiaduktem, a to zakręt nie do zrobienia z tak długą
naczepą itd. itp. Więc zastanawiam się, czy da radę się robić tym i czterama
kolejnymi TiR-em w tym mieście 50 kursów dziennie. ;)

do góry

co do tego pytania czy program dwa procesory moglby byc
wiecej niz dwa razy szybszy to przychodzą mo do glowy dwa
(moze jest wiecej) moze mozna powiedziec troche 'oszukancze'
przypadki - w przypadkach kiedy liniowy wzrost mocy procka
przekladalby sie na ponadliniowy wzrost programu wogole
- kiedy czesc mozy pierwszego proca musialaby byc oddelegowana
na stale do innych zadan wiec nie moglaby uczestniczyc
(np jesli 80% pierwszego proca szloby zawsze na obsluge
systemu 9albo jakiegos sterowania w aplikacji) to dorzucenie
drugiego zwiekszylo by proga 6x - ale mozna powiedziec ze
to troche oszukancze rozwiazania ("i ve got a poison I ve got
a remedy")



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Użytkownik " M.M." <m...@N...gazeta.pl> napisał w wiadomości grup
dyskusyjnych:jj2l7u$clb$...@i...gazeta.pl...
> napisze i nie sprawdze. Waskim gardlem w tworzeniu watkow jest wywolanie
> systemowe i byc moze wykonanie specyficznych instrukcji procesora
> plus przerzucanie/konflikty cache - zaleznie jak to jest zaimplementowane

Ok. Ale są dwa zupełnie różne zagadnienia:

Problem A.: Program ma używać dwóch wątków, aby wydajniej wykorzystać moc
komputera i wcale nie jest ważne, jak długo będzie się coś liczyło - jeżeli
tylko procesory będą sensownie wykorzystywane. (Akceptowalne jest np. aby
były obciążone tylko w 5% każdy, bo pozostałe 95% też się komuś do czegoś
przyda.)

Problem B.: Program ma używać wszystkich wątków, aby jak najszybciej
ukończyć obliczenia, nawet za cenę nieefektywności (np. kilka wątków powiela
obliczenia już wykonane). Przynajmniej jeden procesor MUSI być obciążony w
100%, a dobrze byłoby gdyby i pozostałe liczyły pełną mocą.

> na danym modelu procesora. Takie problemy ma kazda biblioteka, kazda
> musi tworzyc watek za posrednictwem systemu. Mysle ze nie masz racji,

Niekoniecznie. Zawsze można np. próbować ominąć system pisząc własny.

> mysle ze OpenMP jest bardzo podobna pod wzgledem wydajnosci jak
> kazda inna dobra(!) biblioteka, czy inny standard.

I tak. I nie. Jak pisałem - "open" OpenMP z GCC okazała się znacznie mniej
wydajna niż ta z MSVC. Więc nawet OpenMP może być bardzo różne... a co
dopiero w porównaniu z innymi rozwiązaniami.

> Czego mozna chciec wiecej? Wszystko wskazuje na to, ze OpenMP nawet nie
> tworzy watkow, ale umie je sprytnie przytrzymac i dac im zadania zgodnie

Zależy od implementacji. Windowsiane OpenMP z GCC (i to jeszcze wersja jaką
mam) być może jest mało sprytne.

do góry

Użytkownik " fir kenobi " <f...@N...gazeta.pl> napisał w wiadomości grup
dyskusyjnych:jj31fb$n8o$...@i...gazeta.pl...
> (np jesli 80% pierwszego proca szloby zawsze na obsluge
> systemu 9albo jakiegos sterowania w aplikacji) to dorzucenie

To i tak trochę kicha: bo na pewnym etapie ten szybki 2-gi CPU czekałby na
ten wolny (tj. zajęty wysługiwaniem się systemowi) 1-szy CPU.

Nawet trochę podejrzewałem, że może tak być w konkretnym przypadku. Tj. że
zamiast system być 1-szym CPU i a na 2-gim CPU "na full" chodzi program - to
jest tak, że program chodzi na 1-szym CPU biorąc z niego 10% i wtedy
równolegle dokłada sobie 10% z 2-giego CPU. Czyli jest zaledwie 20%
wydajności pojedynczego rdzenia CPU, zamiast - jak to było dla 1-wątkowca -
100%. Czyli spadek wydajności 5x zamiast wzrostu 2x. Czyli efekt równy 1/10
tego oczekiwanego.

Zasada najsłabszego ogniwa czy jakoś tak. No, ale OpenMP powinno puszczać
obliczenia na "pierwszy lepszy wolny" - więc raczej nie fifty-fifty, tzn.
10%-10%, ale raczej 10%-(10%+(10%+10%)+...) czyli łącznie 110%. Ale jeżeli
tego nie potrafi (dana implementacja)...

do góry

On 02.03.2012 20:11, slawek wrote:
[...]
> /***************************************************
****************************************************
************************
>
> !
> ! Program test-omp
> !
> ! /openmp
> !
Zacytuję ioccc:
You can hide a semi truck in 300 lines of C.

Tu jest w 88 liniach C ukryty fiat 126p z 4 przyczepami - nic dziwnego,
że jedzie tak wolno.


Wyniki z mojego komputera (core i5) i gcc-4.6:
(wywaliłem niepotrzebną linijkę z getchar() na końcu)
$ gcc-4.6 -O3 kot.c
$ time ./a.out
CPU time = 8.100000
just for fun 91.999668
./a.out 8,12s user 0,01s system 99% cpu 8,128 total

$ gcc-4.6 -O3 --fast-math kot.c
$ time ./a.out
CPU time = 0.700000
just for fun 91.999668
./a.out 0,71s user 0,00s system 99% cpu 0,716 total

Ciekawi mogą zajrzeć do assemblera i zobaczyć, że gcc zastąpiło
dzielenie i 2 dodawania przez mnożenie i dodawanie. Psuje to pełną
zgodność ze standardem, ale generuje kod 11 razy szybszy.

$ gcc-4.6 -O3 --fast-math -fopenmp kot.c
$ time ./a.out
CPU time = 7.540000
just for fun 91.999668
./a.out 7,18s user 0,39s system 394% cpu 1,917 total

Interesujące - wszystkie rdzenie obciążone, dużo czasu w kernel mode a
czas wykonania ponad 2 razy dłuższy nie mówiąc o czasie procesora, który
jest 10 razy dłuższy.

Pora pobieżnie przejrzeć kod i zaaplikować patch:

- #pragma omp parallel
{

- #pragma omp for schedule(static,100)
for(i = 0; i < n; i++)
v2[i] = v1[i]/(c*c) + epsilon0 + pi;


setup(vec[i1]);
+ #pragma omp parallel for schedule(static,4096)
for(j = 0; j < m; j++)
{


$ gcc-4.6 -O3 --fast-math -fopenmp kod.c
$ time ./a.out
CPU time = 1.960000
just for fun 91.999668
./a.out 1,97s user 0,00s system 389% cpu 0,507 total

I mamy wykonanie 40% szybciej na 2 rdzeniach z HT (z narzutem na
zrównoleglenie 180%).

Magia polega na dwóch zmianach:
1. NIE wykonywaniu TEGO SAMEGO kodu wielokrotnie (naprawdę się
zastanawiam, czy slawek nie umie czytać, czy zrobił to specjalnie(co
będzie pewnie utrzymywać)).
2. sensowny przydział bloków obliczeń

--
Pozdrawiam
Michoo

do góry

> I mamy wykonanie 40% szybciej na 2 rdzeniach z HT (z narzutem na
> zrównoleglenie 180%).

I mamy rozwiązanie.

> Magia polega na dwóch zmianach:
> 1. NIE wykonywaniu TEGO SAMEGO kodu wielokrotnie (naprawdę się
> zastanawiam, czy slawek nie umie czytać, czy zrobił to specjalnie(co
> będzie pewnie utrzymywać)).
> 2. sensowny przydział bloków obliczeń

To tak jak jakiś czas temu wrzało, że w kompilatorze C# jest błąd, bo
mnóstwo ludzi błędnie rozumiało działanie wyrażeń lambda w połączaniu z
closures.

--
Mateusz Bogusz

do góry

Użytkownik "Michoo" <m...@v...pl> napisał w wiadomości grup
dyskusyjnych:jj3soa$jrf$...@m...internetia.pl...
> ./a.out 1,97s user 0,00s system 389% cpu 0,507 total
>
> I mamy wykonanie 40% szybciej na 2 rdzeniach z HT (z narzutem na
> zrównoleglenie 180%).
>
> Magia polega na dwóch zmianach:

Przypadkiem zauważyłeś, że MSVC to Windows - natomiast ty uruchamiasz i
testujesz pod Linuksem?

Połowa (większa) problemu to narzuty "wewnętrzne" - widać po twoim teście
jedynie to, że Linuks sprawdza się lepiej (czyli jak trzeba).

> 1. NIE wykonywaniu TEGO SAMEGO kodu wielokrotnie (naprawdę się

do for paralell jest równoważne parze linijek parallel/do for --
przynajmniej to wyczytałem w opisie OpenMP

> 2. sensowny przydział bloków obliczeń

Sensowny dla MS Windows oznacza w tym przypadku kawałki liczące się około
milisekund. A w programie są mikrosekundowe.

do góry

On Tuesday, March 6, 2012 9:43:31 AM UTC, slawek wrote:

> Sensowny dla MS Windows oznacza w tym przypadku kawałki liczące się około
> milisekund. A w programie są mikrosekundowe.

No to przeciez 1ms to jest rzad wielkosci rozdzielczosci zegara systemowego. Nic
dziwnego, ze masz duzy narzut. Czemu sie upierasz, zeby operowac na tak malych
kawalkach?

RW

do góry