(po tej taniej koli (cola marki cola dwa litry za 1zl)
co to ostatnio pije czuje sie jakos dziwnie)

chyba najfajniej o paralelizowaniu mozna pomyslec na
konkretnych przykladach (a nie mam tych przykladow za
wiele - umialby ktos podac jakies dobrze okreslone
uklady do sparalelizowania?) Podstawowym przykladem
ktory do mnie powraca jest przyklad wioski - 'wioska'
nazywam dla uproszczenia program (w c na pc)
skladajacy sie z postaci chodzacych po dwuwymiarowej
mapie (na ktorej poza postaciami moga byc jeszcze ew
jakies przeszkody, domki czy drzewka)

chodzi mi o postawienie kwestii czy wioske da sie
sparalelizowac ladnie w mtb (multithreadingu
bezkolizyjnym zob definicja w poscie 'mt - nazewnictwo')

jak ktos z grupowiczow zabieralby sie do parelelizowania
wioski?

(prof fir)




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

do góry

fir <f...@W...gazeta.pl> napisał(a):

> (po tej taniej koli (cola marki cola dwa litry za 1zl)
> co to ostatnio pije czuje sie jakos dziwnie)
>
> chyba najfajniej o paralelizowaniu mozna pomyslec na
> konkretnych przykladach (a nie mam tych przykladow za
> wiele - umialby ktos podac jakies dobrze okreslone
> uklady do sparalelizowania?) Podstawowym przykladem
> ktory do mnie powraca jest przyklad wioski - 'wioska'
> nazywam dla uproszczenia program (w c na pc)
> skladajacy sie z postaci chodzacych po dwuwymiarowej
> mapie (na ktorej poza postaciami moga byc jeszcze ew
> jakies przeszkody, domki czy drzewka)
>
> chodzi mi o postawienie kwestii czy wioske da sie
> sparalelizowac ladnie w mtb (multithreadingu
> bezkolizyjnym zob definicja w poscie 'mt - nazewnictwo')
>
> jak ktos z grupowiczow zabieralby sie do parelelizowania
> wioski?
>

realnie to poza samym wielkim movem (calej grupy)
to jest tam jeszcze grupowy draw a pozatym u mnie
przynajmniej jeszcze sam blit - i to ew mozna
by probowac rownoleglic

1. grupovy move //powiedzmy 20 ms (20 to sporo oczywiscie)
2. grupowy draw // nie wiem niestety ile ale powiedzmy 5 ms
3. blit // [pwoedzmy 3 ms

nie wiem ile zajmuje u mnie sumaryczny draw bo drawy sa
u mnie splecione z movami na poziomie pojedynczej jednostki

bigdrawa z blitem mozna oczywiscie bezkolizyjnie
rozbijac chocby i na tysiac kawalkow (tak sie przynajminej
mi wydaje), z tym ze jesli mialoby to byc jeszcze
paralelizowane z bigmovem to zeby nie bylo 'strzepienia'
(drawy tylko czytaja stan sceny i zmiany danych pod
drawem nie owocowaly by krytycznymi bledami ale ew
krotkotrwalymi bledami w obrazie)
trzebaby robic jakis doublebuffor dla samych movow -
a to jest mocno burdensome (dirty kode) - no ale costam
mozna zrobic (powiedzmy ze sciac paralelizacja caly
drawing do 1 ms)

pozostaje jeszcze 20 milisekundowy bigmove
ktorego trudno zrownoleglic ale warto pomyslec

(prof fir)



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

do góry

> pozostaje jeszcze 20 milisekundowy bigmove
> ktorego trudno zrownoleglic ale warto pomyslec
>

cos mozna zrobic dzielac postaci po 'polu potencjalnego
dzialania' na rozlaczne grupy ktore na pewno nie moga
kolidowac miedzy sobą i te grupy puscic w oddzielnych
watkach - tj to co moze kolidowac puszczac sekwencyjnie
a to co nie rownolegle

np jesli mapa zawieralaby samych teleporterow to
potencjalnie wszystko moze kolidowac ze soba w ramce wiec
trudno podzielic, ale jesli mapa zawiara lokalnie jedynie
przemieszczajace sie postaci to na pewno np 1/3 lewa czesc
postaci z ekranu mozna puscic w jednym watku, prawa 1/3
w drugim rownolegle - a srodek zastopowac i puscic na koncu
- przyspieszenie 33%, z tym ze sa pewne koszty przygotowywania
czy wyrozniania tych zbiorow - ale dla przynajmniej dla 'ciezkich'
postaci byloby/[pwinno byc) oplacalne - przy drobniejszym
podziale np dla wielkich ukladow z ciezkimi i lokalnymi
postaciami mozna by (przy wielu prockach) przyspieszac
znacznie - odwrotnie dla lekkich mniej lokalnych postaci
slabiej by to dzialalo

przy tym przychodzi mi do glowy jeszce jedno zastrzezenie
- nie wiem czy nie wprowdzilby sie pewien dodatkowy stopien
swobody w postaci ew dosyc losowego charakteru porzadku
w jakich te postaci by sie ruszaly (chodzi o wzajemna
kolejnosc) - wszystko byloby zgodnie z zalozeniami w tym
sensie ze kazda postac poruszylany sie zgodnie z przepisem
raz w danej ramce ale nie konta teraz jawnie kontroluje sie
to ktora poruszylaby sie wczesniej a ktora pozniej
(to mogloby zalezec od 'brudnego zrodla' zaleznego od
technicznych detali architektury - np tu te z lewej i
z prawej poruszylyby sie zawsze wczesniej niz te na srodku
(w ramach lewej i prawej normalnie zgodnie z indeksami w
tablicy) - nie wiem czy nie obfitowaloby to jakimis
specyfikami w gameplayu

tak czy owak jest to jedna z form mt bezkolizyjnego
(w pewnym przynajmniej sensie) - nie ma ani lockow ani
flagowania

(prof fir)











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

do góry

genaralnie jesli da sie podzielic na kilkaset kawalkow
(w cos w rodzaju kratki na ubraniu) to mozna wykonac
je rownolegle w trzech przebiegach (najpierw laty
pozniej 'ulice' miedzy latami a pozniej 'skrzyzowania')
(powiedzmy ze w sumie kilkaset rozlacznych kawalkow)

dodatkowym kosztem jest ten koszt podzialu na te zbiory
ale to sie robi prostymi warunkami na wsp x i y
- to mozna ew tez zrownoleglic (o ile dorzuci sie troche
dodatkowego ramu na brudne (cachowe) listy)
[pewien problem tutaj co prawda bo albo trzeba trzymac
te listy w spacjali albo samo budownie list byloby
kolizyjne) - albo mozna nie budowac chache i jechac
na zywca np kilkuset watkami po jednej tablicy
- tu sie dochodzi do pojecia stalych kosztow O(1)
- wersja ze spacjala wydaje sie ew najlepsza i to
peowadzi do wogole nowego pomyslu by ew robic to z
wywaleniem ujecia 'lagrangeowskiego' (.x .y) i przelaczenia sie
na eulerowskie ([y][x]) tj z creepowatymi watkami skanujacymi nie postaci
po x y a mape po polach (szukajacych postaci lokalnie w
obslugiwanych obszarach mapy) - ciekawe ale bedzie trzeba
przemyslec to chyba innym razem (bo cos sie glodny zrobilem)

widac w kazdym razie ze kluczowym czynnikiem jest loalnosc
pol oddzialywania postaci - lokalne powolne postaci
zrownoleglaja sie w ten sposob dobrze a 'teleporterzy'
nie bardzo





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

do góry

Dnia Fri, 30 Dec 2011 15:25:21 +0000 (UTC), f...@N...gazeta.pl napisał(a):

> widac w kazdym razie ze kluczowym czynnikiem jest loalnosc
> pol oddzialywania postaci - lokalne powolne postaci
> zrownoleglaja sie w ten sposob dobrze a 'teleporterzy'
> nie bardzo

Wycielo mi chyba polowe watku, z kim gadasz? :>

--
pozdro
R.e.m.e.K

do góry

R.e.m.e.K <g...@d...null> napisał(a):

> Dnia Fri, 30 Dec 2011 15:25:21 +0000 (UTC), f...@N...gazeta.pl napisał
(a):
>
> > widac w kazdym razie ze kluczowym czynnikiem jest loalnosc
> > pol oddzialywania postaci - lokalne powolne postaci
> > zrownoleglaja sie w ten sposob dobrze a 'teleporterzy'
> > nie bardzo
>
> Wycielo mi chyba polowe watku, z kim gadasz? :>
>

uzupelniam wypowiedzi - nie moja wina ze nikt nic nie
pisze, a jak mam jakies nowe rzeczy do uzupelnienia to
uzupelniam;

akurat jestem zadowolony dosyc z powyzszego wywodu,
(zwlaszcza np z tej koncowki z creepujacymi po mapie
niezatrudnionymi watkami)

dorobilem sie juz na przestrzeni kilku lat mentalnej
(co prawda troche przymulastej) pracy paru pojec,

poukladalem pojeciow pare rzeczy tak ze teraz
czasem ta tematyczna robota jakby lepiej idzie

(zreszta temat mt mz jest raczej znacznie
latwiejszy niz temat c)






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

do góry

>
> jak ktos z grupowiczow zabieralby sie do parelelizowania
> wioski?
>

czyli zeby jeszcze podsumowac dla konkretnego przypadku

- powiedzmy ze mam mape tysiac pol na tysiac i 50 tys
postaci na mapie
- 4 albo 6 rdzeniowy procek

dzielenie lagranzowskiej petli 50tys malych move'ow
np na 6 rownloeglych niesynchronizzowanych kawalkow
powodowac bedzie losowo wypadki

sposoby kolizyjne (z lockami)

-mozna lokowac cala mape ale to raczej zupelnie do niczego,
-mozna lokowac mape w drobniejszej skali np na poziomie
pojedynczych pol mapy - jest to jeden ze sposobow ale nie
umiem ocenic jego praktycznych plusow czy minusow - mozna
tylko byc pewnym ze tych lokow byloby od cholery (chyba co
najmniej 50tys na ramke) tak ze nie wiem jak by to dzialalo

sposob bezkolizyjny:

dzielimy mape np na 6 poziomych pasow odleglych od siebie
o kilka pol np (y: 0-150, 160-310, 320-470, itd)

olewamy lagrangea i iterujemy eulerowsko w 6ciu watkach
po tych pasach rownolegle, - jest zrownoleglenie, -
wyszukojemy postaci na mapiei wywolujemy im update;
czekamy az pasy sie wykonaja po czym w drugim przebiegu
wykonujemy piec paskow dzielacych tamte duze pasy

wada:
jest 200 kilo/na watek prostych ale stratnych iteracji
po mapie w poszukiwaniu postaci (200 kilo takich prostych
iteracji to jednak raczej nie powinno mam nadziej dobic
kosztu milisekundy)

zaleta:
jest bezkolizyjne bez lockow i waitow - raczej by sie chyba
oplacalo - no ale dokladnie trudno powiedziec, trzebaby zbadac,
ew zastanowic sie czy nie ma jeszcze jakiegos innego pomyslu)
- im wiecej rdzeni tym raczej bardziej by sie oplacalo










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

do góry

<f...@N...gazeta.pl> napisał(a):

> >
> > jak ktos z grupowiczow zabieralby sie do parelelizowania
> > wioski?
> >
>
> czyli zeby jeszcze podsumowac dla konkretnego przypadku
>
> - powiedzmy ze mam mape tysiac pol na tysiac i 50 tys
> postaci na mapie
> - 4 albo 6 rdzeniowy procek
>
> dzielenie lagranzowskiej petli 50tys malych move'ow
> np na 6 rownloeglych niesynchronizzowanych kawalkow
> powodowac bedzie losowo wypadki
>
> sposoby kolizyjne (z lockami)
>
> -mozna lokowac cala mape ale to raczej zupelnie do niczego,
> -mozna lokowac mape w drobniejszej skali np na poziomie
> pojedynczych pol mapy - jest to jeden ze sposobow ale nie
> umiem ocenic jego praktycznych plusow czy minusow - mozna
> tylko byc pewnym ze tych lokow byloby od cholery (chyba co
> najmniej 50tys na ramke) tak ze nie wiem jak by to dzialalo
>
> sposob bezkolizyjny:
>
> dzielimy mape np na 6 poziomych pasow odleglych od siebie
> o kilka pol np (y: 0-150, 160-310, 320-470, itd)
>
> olewamy lagrangea i iterujemy eulerowsko w 6ciu watkach
> po tych pasach rownolegle, - jest zrownoleglenie, -
> wyszukojemy postaci na mapiei wywolujemy im update;
> czekamy az pasy sie wykonaja po czym w drugim przebiegu
> wykonujemy piec paskow dzielacych tamte duze pasy
>
> wada:
> jest 200 kilo/na watek prostych ale stratnych iteracji
> po mapie w poszukiwaniu postaci (200 kilo takich prostych
> iteracji to jednak raczej nie powinno mam nadziej dobic
> kosztu milisekundy)
>
> zaleta:
> jest bezkolizyjne bez lockow i waitow - raczej by sie chyba
> oplacalo - no ale dokladnie trudno powiedziec, trzebaby zbadac,
> ew zastanowic sie czy nie ma jeszcze jakiegos innego pomyslu)
> - im wiecej rdzeni tym raczej bardziej by sie oplacalo
>

choc dla kilku rdzeni to moze i lepiej lagrangem (z grubsza
eulerem lepiej gdy rozmiar tablicy postaci << rozmiar bloku na
mapie, tutaj jest 50k vs ok 200k czyli wychodzi jakby z grubsza
to samo

czyli w sumie mz paralelizacja tego

update_boty_by_one_thrad()
{
for(int i=0; i<postac_max;i++)
postac[i].update();

}

wygladalaby jakos tak (lagrange):


update_part(int map_y_begin, int map_y_end)
{
for(int i=0; i<postac_max;i++)
if(postac[i].y>=map_y_begin &&
postac[i].y<map_y_end &&
!postac[i].done) // flaga potrzebna dla tych co z
szerokiego pasa przeszly do waskiego i tam juz nie powinny sie ruszac jako
przerobione
{
postac[i].update();
postac[i].done = true;
}
}


update_boty_mt()
{
int threads = get_optimal_no_of_threads_for_mt();

// obliczanie szerokosci 'pasow' podzialu mapy

int caly = map_y/threads;
int waski = 5;
int szeroki = caly - waski;


for(int i=0; i<threads;i++)
new thread update_part(i*caly, i*caly+szeroki);

wait threads;

for(int i=0; i<threads;i++)
new thread update_part(i*caly+szeroki, (i+1)*caly);

wait threads;

}

kod nie taki za przyjemny, (mam nadzieje ze to by dzialalo
bo moze sa jednak jakies bugi w kodzie czy rozumowaniu)
ale rozwazanie jakie za tym stoi mz w miare przydatne




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

do góry

>
> update_boty_mt()
> {
> int threads = get_optimal_no_of_threads_for_mt();
>
> // obliczanie szerokosci 'pasow' podzialu mapy
>
> int caly = map_y/threads;
> int waski = 5;
> int szeroki = caly - waski;
>
>
> for(int i=0; i<threads;i++)
> new thread update_part(i*caly, i*caly+szeroki);
>
> wait threads;
>
> for(int i=0; i<threads;i++)
> new thread update_part(i*caly+szeroki, (i+1)*caly);
>
> wait threads;
>
> }
>

albo w wersji gdzie przecinek oznacza zrownoleglenie
wykonania a srednik synca

update_boty_mt()
{
int threads = get_optimal_no_of_threads_for_mt();
int caly = map_y/threads, int waski = 5;
int szeroki = caly - waski;

for(int i=0; i<threads;i++)
update_part(i*caly, i*caly+szeroki), ;
for(int i=0; i<threads;i++)
update_part(i*caly+szeroki, (i+1)*caly), ;
}

troche dziwnie ale jestem sklonny jednak pobadac ta skladnie


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

do góry

fir <f...@W...gazeta.pl> napisał(a):

> chyba najfajniej o paralelizowaniu mozna pomyslec na
> konkretnych przykladach (a nie mam tych przykladow za
> wiele - umialby ktos podac jakies dobrze okreslone
> uklady do sparalelizowania?)
Jakiekolwiek? To chyba nie sztuka? Moze mnozenie macierzy?

> chodzi mi o postawienie kwestii czy wioske da sie
> sparalelizowac ladnie w mtb (multithreadingu
> bezkolizyjnym zob definicja w poscie 'mt - nazewnictwo')
Jakie to jest bezkolizyjne zrownoleglenie? Czy chodzi o cos takiego:
1) znamy szybkosc wykonywania instrukcji
2) znamy zasady komunkacji procesor <=> cache <=> ram
3) na kazdym procesorze odpalamy program
4) programy chodz pracuja na wspolnej pamieci, to sa tak napisane,
ze nigdy w tej samej chwili nie dojdzie do operacji odczytu/zapisu
tych samych danych przez dwa procesory?
Pozdrawiam


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

do góry