🚀 go-pugleaf

On 2017-02-24 19:46, stchebel@gmail.com wrote:
> 1) Co nam dają na czasie te 2 maszyny działające podobno równolegle?
> Załóżmy, że cała tablica a[1..N] jest zapamiętana w obrębie jednej kostki
> (i faktycznie z reguły tak jest)

Niekoniecznie. Nie można, albo przynajmniej nie powinno się zakładać 
czegokolwiek o organizacji pamięci na tym poziomie.

>, więc nie ma fizycznej możliwości jednoczesnego odwołania się do adresu np. 1 i (N/2+1).

I zazwyczaj nie bedzie. Poza tym że CPU musi pobrać dane z pamięci to 
musi również je obrobić lokalnie (dodać). W tym momencie szyna jest 
wolna dla drugiego. Z grubsza jesli wiele rdzeni operuje na pamięci to 
są "magicznie" rozkładane pomiędzy nie cykle dostepu. Poza tym zakłada 
się że wiele danych leży w cache gdzie reguły dostepu mogą byc inne niż 
blokowanie się rdzeni. Inaczej będzie to w Core2Duo a inaczej w NUMA a 
inaczej we współczesnym i7. Trzeba też uwzględnić ze potokowość może 
miec pojęcie o innych potokach i np. przestawiać cykle dostepu do 
pamięci współpracując z innymi potokami.

> 2) Czy na maszynie 1-no rdzeniowej da się uruchomić więcej niż 1 wątek? Jeżeli tak, to o co tu chodzi?

Jest przerywany przez system. Wywłaszczanie. Ma to zalety, jesli wątek 
czeka na np. dane dysku to inny może coś liczyć w tym czasie. 
Implementacyjnie to przychodzi przerwanie z timera, system zamraża stan 
procesu wywalając dane ze stosu i rejestrów gdzieś do pamięci i odmraża 
inny wątek. Sprawa komplikuje się gdy mamy procesy a nie wątki, ale to 
raczej komplikacja związana z pamięcia wirtualną co sprawadza się do 
czasu przełączenia. Mała ilość rdzeni w CPU nie powoduje że wątki nie 
maja sensu - mają.

> 3) Co polecacie z literatury sieciodostępnej celem zapoznania się z tym tematem?
> Chodzi mi o jakieś praktyczne "etiudy" kilkuwątkowe.

Czytaj o wywłaszaczaniu, preemptive multitasking.

W dniu piątek, 24 lutego 2017 20:29:39 UTC+1 użytkownik Sebastian Biały napisał:
> On 2017-02-24 19:46, stchebel@gmail.com wrote:
> > 1) Co nam dają na czasie te 2 maszyny działające podobno równolegle?
> > Załóżmy, że cała tablica a[1..N] jest zapamiętana w obrębie jednej kostki
> > (i faktycznie z reguły tak jest)
> 
> Niekoniecznie. Nie można, albo przynajmniej nie powinno się zakładać 
> czegokolwiek o organizacji pamięci na tym poziomie.
> 

Niestety koniecznie. HW, który projektuję będzie wyposażony w jedną kostkę RAM'u. Można dyskutować dlaczego tak, a nie inaczej, ale to odrębny i dłuugi temat. Jest jedna kostka pamięci, i tyle.. Co prawda przykład, z tą rozdzieloną sumą podałem jako właśnie tylko i wyłącznie przykład.

> >, więc nie ma fizycznej możliwości jednoczesnego odwołania się do adresu np. 1 i (N/2+1).
> 
> I zazwyczaj nie bedzie. Poza tym że CPU musi pobrać dane z pamięci to 
> musi również je obrobić lokalnie (dodać). W tym momencie szyna jest 
> wolna dla drugiego. Z grubsza jesli wiele rdzeni operuje na pamięci to 
> są "magicznie" rozkładane pomiędzy nie cykle dostepu. Poza tym zakłada 
> się że wiele danych leży w cache gdzie reguły dostepu mogą byc inne niż 
> blokowanie się rdzeni. Inaczej będzie to w Core2Duo a inaczej w NUMA a 
> inaczej we współczesnym i7. Trzeba też uwzględnić ze potokowość może 
> miec pojęcie o innych potokach i np. przestawiać cykle dostepu do 
> pamięci współpracując z innymi potokami.

OK, dzięki, coś zaczynam jarzyć.. Chyba bez zmiany koncepcji mojego HW da się to jakoś czasowo poskładać. Jest późno, temat na odrębny wątek.. Jutro, pojutrze..

> 
> > 2) Czy na maszynie 1-no rdzeniowej da się uruchomić więcej niż 1 wątek? Jeżeli tak, to o co tu chodzi?
> 
> Jest przerywany przez system. Wywłaszczanie. Ma to zalety, jesli wątek 
> czeka na np. dane dysku to inny może coś liczyć w tym czasie. 
> Implementacyjnie to przychodzi przerwanie z timera, system zamraża stan 
> procesu wywalając dane ze stosu i rejestrów gdzieś do pamięci i odmraża 
> inny wątek. Sprawa komplikuje się gdy mamy procesy a nie wątki, ale to 
> raczej komplikacja związana z pamięcia wirtualną co sprawadza się do 
> czasu przełączenia. Mała ilość rdzeni w CPU nie powoduje że wątki nie 
> maja sensu - mają.

Hmmm.. Lepiej się czuję w VHDL'u. Proces jest przeze mnie intuicyjnie zrozumiały w HW, no i takoż mi się wydawał wątek w SW. 

> 
> > 3) Co polecacie z literatury sieciodostępnej celem zapoznania się z tym tematem?
> > Chodzi mi o jakieś praktyczne "etiudy" kilkuwątkowe.
> 
> Czytaj o wywłaszaczaniu, preemptive multitasking.

To chyba załatwia OS(??). Chyba będę musiał bardziej precyzyjnie opisać swoje wątpliwości. Ale już nie dzisiaj :))

Dzięki za zainteresowanie tematem!!

W dniu 2017-02-24 o 19:46, stchebel@gmail.com pisze:
> Witam,
>
>  Nigdy nie miałem potrzeby programowania wielowątkowego, aż tu nagle
>  pojawia się pewna koncepcja w moim projekcie. Chodzi o to, żeby jak
>  gdyby 2-wie różne maszyny zajmowały się równolegle 2-ma różnymi sprawami,
>  ale trzeba ich działania w/g pewnych założeń zsynchronizować. No więc
>  na chłopski rozum potrzebna jest trzecia maszyna kontrolująca synchronizację
>  2-ch pozostałych. Przykład: mamy tablicę a[1..N] i chcemy jak najszybciej
>  obliczyć sumę wszystkich elementów a[i].
>
> Wątek 1:
>
> Suma1:=0;
> for i:=1 to N/2 do
>  Suma1:=Suma1+a[i];
>
> Wątek 2:
>
> Suma2:=0;
> for i:=N/2+1 to N do
>  Suma2:=Suma2+a[i];
>
> Wątek 3:
>
> Jak zakończone jest działanie Wątków 2 i 3 , to finalnie
>
> Suma:=Suma1+Suma2;
>
> =====
>
> No i teraz pytania:
>
> 1) Co nam dają na czasie te 2 maszyny działające podobno równolegle?

Maszyny, czyli osobne komputery? Osobne procesy na jednym komputerze? 
Czy osobne wątki w ramach jednego procesu?
To są spore różnice, choć rozwiązania są ramowo podobne.

A co dają? Że posłużę się analogią, dają to co więcej pracowników w 
firmie, kosztują tyle że ktoś musi tym zarządzać.


>
> 2) Czy na maszynie 1-no rdzeniowej da się uruchomić więcej niż
>  1 wątek?  Jeżeli tak, to o co tu chodzi?

Oczywiście. Każda aplikacja aktualnie uruchamia zazwyczaj więcej niż 
jeden wątek.
Jak wejdziesz w menadżera zadań Windows, to w karcie Procesy możesz 
pokazać kolumnę Watki i pokaże Ci ile wątków ma dany proces.

Ograniczeniem jest liczba jednocześnie obsługiwanych wątków przez CPU. 
Jeszcze kilka lat temu 1 CPU obsługiwał jeden wątek na raz, co oznaczało 
że inne w tym czasie spały. To właśnie robi funkcja Sleep() - oddaje 
czas procesora innym wątkom.

Większość OSów to systemy z wywłaszczaniem - oznacza to że OS może w 
każdej chwili zatrzymać dany wątek, i wznowić inny. OS stara się dać jak 
najwięcej czasu każdemu wątkowi, I jak już wykorzystanie wątka CPU 
zbliża się do 100% to przydziela wątkom programów czas CPU w/g 
priorytetu wątku (i paru innych ustawień).

Między innymi dlatego jest ważne żeby dać znać procesorowi ze się nic 
nie robi, jak np. funkcja Sleep(), WaitForSingleObject() i inne, czy 
typowa pętla komunikatów (wątek GUI tam czeka aż OS wyśle komunikat, nie 
zużywając czasu CPU).

W dzisiejszych czasach większość procesorów ma przynajmniej dwa jądra, 
czyli obsługuje równocześnie dwa wątki, ale np Intel ma technologię 
HyperThreading gdzie jedno jadro jest w stanie obsłużyć dwa wątki na 
raz. Podobną technologię dodało AMD w swoich najnowszych procesorach, 
8-jądrowy procesor obsługuje jednocześnie 16 wątków.

Tego typu procesory są używane w serwerach, gdzie ilość wątków i 
wydajność energetyczna są ważniejsze niż prędkość pojedynczego wątku. 
Powoli także desktopy dostają obsługę większej ilości wątków na raz, i 
oprogramowanie desktopowe powoli się zmienia aby je wykorzystywać 
efektywnie.


> 3) Co polecacie z literatury sieciodostępnej celem zapoznania się z
>  tym tematem? Chodzi mi o jakieś praktyczne "etiudy" kilkuwątkowe.

Tematyka jest rozległa, radził bym najpierw poczytać jak to działa, co 
to są mutexy, semafory, operacje atomowe, bariery w pamięci, NUMA, i 
przede wszystkim dlaczego dostęp wielu wątków do tych samych danych musi 
być synchronizowany.

A kilka lat praktyki uczy jak nie używać tych rzeczy, uczy pokory, że 
łatwo coś zepsuć nie wiedząc nawet czemu ;-)

Generalnie najlepiej jest stosować gotowe obiekty przygotowane do pracy 
wielowątkowej (tu bieda w Delphi, jego RTLu i VCLu, poza TThreadList i 
chyba nic więcej). Najlepiej jest z góry rozdzielić pracę na wątki, tak 
aby nie współdzieliły danych, albo robiły to jak najkrócej.

Dobra jest też zasada że jakaś paczka danych należy tylko do jednego 
wątku - jak jest przesyłana do innego, to od tej chwili on jest za nią 
odpowiedzialny.


Jest też fajna rzecz, MapReduce, AFAIK opracowana w Google ponad 
dziesięć lat temu. Tu artykuł o tym: http://informatyka.wroc.pl/node/424
Google używa tego na petabajtach danych, tysiącach serwerów w klastrach, 
ale sama idea jest naprawdę prosta, wręcz genialnie prosta.

Np. Każde zapytanie do wyszukiwarki Google jest obsługiwane przez 
kilkanaście komputerów, które jednocześnie przetwarzają inne aspekty 
zapytania (szukanie w indeksach automatycznych, szukanie w indeksach 
ręcznych, reklamy, statystyki, etc), i dzięki podziałowi pracy robi to 
szybko.
Google pozwala sobie nawet zlecać tą samą pracę różnym komputerom (część 
Map z MapReduce), na wypadek gdyby któryś z nich nie był w stanie jej 
wykonać, lub wykonał ją zbyt powoli - wykorzystany zostanie wynik 
maszyny która skończyła pierwsza. Ich oprogramowanie nawet pamięta które 
komputery jak często się spóźniają, i może zgłaszać je do naprawy/wymiany.


Jak będziesz szukał informacji o wątkach, procesach i pracy równoległej, 
to nie skupiaj się na Delphi. To jest problem uniwersalny, a Delphi jest 
na tyle niszowe że dobrej literatury jest mało.

-- 
Arivald

On 2017-02-24 22:46, stchebel@gmail.com wrote:
> Niestety koniecznie. HW, który projektuję będzie wyposażony w jedną kostkę RAM'u.

To jest kompletnie nieistotne bez znajomosci architektury CPU i 
zagadnienia do rozwiązania. Może sie okazać że koszt wywłaszczania jest 
za duży i nalezy zastanowić sie nad cooperative multitaskingiem. 
Cooperative stosuje się czasem w systemach czasu rzeczywistego. Więc nie 
wiadomo bez szczegółów nic, a już na pewno nie wiadomo czy szyna pamięci 
będzie miala mierzalny wpływ na algorytm.

Na marginesie: pamięci są bardzo szybkie. Wysycenie całego pasma szyny 
pamięci to wcale nie jest trywialne zagadnienie nawet jeśli chcemy.

>> Jest przerywany przez system. Wywłaszczanie. Ma to zalety, jesli wątek
>> czeka na np. dane dysku to inny może coś liczyć w tym czasie.
>> Implementacyjnie to przychodzi przerwanie z timera, system zamraża stan
>> procesu wywalając dane ze stosu i rejestrów gdzieś do pamięci i odmraża
>> inny wątek. Sprawa komplikuje się gdy mamy procesy a nie wątki, ale to
>> raczej komplikacja związana z pamięcia wirtualną co sprawadza się do
>> czasu przełączenia. Mała ilość rdzeni w CPU nie powoduje że wątki nie
>> maja sensu - mają.
> Hmmm.. Lepiej się czuję w VHDL'u. Proces jest przeze mnie intuicyjnie zrozumiały w HW, no i takoż mi się wydawał wątek w SW.

Są tak samo działające za wyjątkiem tego że ilość rdzeni jest mniejsza 
niż ilośc wątków i są co najmniej dwie popularne metody multiplesowania 
wątków na rdzenie. Z punktu widzenia programisty w zasadzie oznacza to 
że procesor ma tyle rdzeni ile wątkow pracuje a szczegóły są mało ważne.

>> Czytaj o wywłaszaczaniu, preemptive multitasking.
> To chyba załatwia OS(??).

Tak, ale niezrozumienie tematu wywłaszczania może się źle zakończyć dla 
wydajności. Wywłaszczanie wątku jest drogie i należy je ograniczać. 
Wbrew pozorom organizacja kodu watku może niejawnie wywłaszczyć ten 
watek przy choćby blokującym IO. Więc jakiś wpływ programisty na 
zachowanie wątków jest.

Obecnie pojawiło się bardzo dużo bardzo tanich komputerów w 
architekturze NUMA (głównie xeony wymieniane z serwerów). Sa bardzo 
wydajne obliczeniowo, ale mają pułapki dzięki którym od razu widać kto 
jest programistą a kto programatorem. Na nich martwiłbym się podziałem 
wątków. Na przecietnym pececie - nie ma się o co martwić.

W dniu 2017-02-25 o 12:26, Sebastian Biały pisze:

> Tak, ale niezrozumienie tematu wywłaszczania może się źle zakończyć dla
> wydajności. Wywłaszczanie wątku jest drogie i należy je ograniczać.
> Wbrew pozorom organizacja kodu watku może niejawnie wywłaszczyć ten
> watek przy choćby blokującym IO. Więc jakiś wpływ programisty na
> zachowanie wątków jest.
>
> Obecnie pojawiło się bardzo dużo bardzo tanich komputerów w
> architekturze NUMA (głównie xeony wymieniane z serwerów). Sa bardzo
> wydajne obliczeniowo, ale mają pułapki dzięki którym od razu widać kto
> jest programistą a kto programatorem. Na nich martwiłbym się podziałem
> wątków. Na przecietnym pececie - nie ma się o co martwić.
>

Czy wynika z tego że w niektórych sytuacjach mogą być one wolniejsze niż 
i7 analogicznej generacji i przy takim samym zegarze?

miab

On 2017-02-25 14:24, miab wrote:
>> Obecnie pojawiło się bardzo dużo bardzo tanich komputerów w
>> architekturze NUMA (głównie xeony wymieniane z serwerów). Sa bardzo
>> wydajne obliczeniowo, ale mają pułapki dzięki którym od razu widać kto
>> jest programistą a kto programatorem. Na nich martwiłbym się podziałem
>> wątków. Na przecietnym pececie - nie ma się o co martwić.
> Czy wynika z tego że w niektórych sytuacjach mogą być one wolniejsze niż
> i7 analogicznej generacji i przy takim samym zegarze?

Jesli napisałes kod który musi często sięgać do pamięci podpiętej 
fizycznie pod inny procesor to tak. Taki kod łatwo napisać jeśli się nie 
wie co robi, teoretycznie cała pamięc obu procesorow jest adresowalna 
wprost.

Po drugie częstotliwośc zegara obecnie jest kiepskim kreyterium oceny. 
Liczy się IPC, magistrale, cache, więc porównać można to tylko mając na 
względzie kilka rzeczy. Porównanie 3GHz i7 z 3GHz xeonem nie ma sensu 
jesli nie znamy dokładnych achitektur.

https://en.wikipedia.org/wiki/Instructions_per_cycle

Wieloprocesorowe maszyny serwerowe będa miały większą wydajność dla 
dwóch osobnych *procesów* niż jeden domowy ponieważ OS zaalokuje te 
procesy do osobnych pamięci z osobnymi magistralami. Natomiast jesli te 
procesy zaczną nagle nadmiernie gadać przez pamięć współdzieloną to 
pewno domowy cpu będzie szybszy.

Znacznie ciekawsze rzeczy pojawiają sie jak ktoś zapyta jak szybko 
zmiana w jednej z pamięci pierwszego cpu będzie widoczna w drugim cpu i 
czy aby na pewno we właściwej kolejności jaką zakładał programator :D

Nie zmienia to faktu że obecnie serwerowe xeony to chyba najtańsza moc 
obliczeniowa jaka może kupić hobbysta bo procesory są w cenie kilkunastu 
zł. Niestety płyty drogie, ale znowuy pamięci tańsze (bo z ecc i nie ma 
komu sprzedać).

W dniu 2017-02-24 o 19:46, stchebel@gmail.com pisze:

> 1) Co nam dają na czasie te 2 maszyny działające podobno równolegle? Załóżmy, że cała tablica a[1..N] jest zapamiętana w obrębie jednej kostki (i faktycznie z reguły tak jest), więc nie ma fizycznej możliwości jednoczesnego odwołania się do adresu np. 1 i (N/2+1).

Wątki nie mają na celu przyśpieszenia wydajności ale na uproszczeniu 
obsługi procesu. W przypadku wątku w którym masz blokujące wywolania 
metod, stan procesu jest dokładnie określony przez aktualnie wykonywaną 
linię kodu.
W przypadku tworzenia kodu typu event-driven programming" stan procesu 
musisz przechowywać w jakimś innym miejscu.


-- 
pozdrawiam
Piotr
XLR250&bmw_f650_dakar

On Sat, 25 Feb 2017 14:39:19 +0100, Sebastian Biały wrote:

> Wieloprocesorowe maszyny serwerowe będa miały większą wydajność dla 
> dwóch osobnych *procesów* niż jeden domowy ponieważ OS zaalokuje te 
> procesy do osobnych pamięci z osobnymi magistralami. Natomiast jesli te 
> procesy zaczną nagle nadmiernie gadać przez pamięć współdzieloną to 
> pewno domowy cpu będzie szybszy.
> 
> Znacznie ciekawsze rzeczy pojawiają sie jak ktoś zapyta jak szybko 
> zmiana w jednej z pamięci pierwszego cpu będzie widoczna w drugim cpu i 
> czy aby na pewno we właściwej kolejności jaką zakładał programator :D


A możesz podać jaki prosty przykład takiej błędnej sytuacji oraz jak temu
zaradzić?

-- 
pozdrawiam
Roman Tyczka

On 2017-03-06 20:08, Roman Tyczka wrote:
>> Znacznie ciekawsze rzeczy pojawiają sie jak ktoś zapyta jak szybko
>> zmiana w jednej z pamięci pierwszego cpu będzie widoczna w drugim cpu i
>> czy aby na pewno we właściwej kolejności jaką zakładał programator :D

> A możesz podać jaki prosty przykład takiej błędnej sytuacji

Wątek a) ustawia zmienną X a *potem* zmienną Y.
Wątek b) widzi najpierw zmienioną Y a potem X

Jeśli masz do czynienia z typowym hackerem, to znajdziesz takie kfiatki 
jak busy loop na zmiennych w pamięci dzielonej zamiast poprawnej 
synchronizacji międzywątkowej/miedzyprocesowej. Stąd łatwa droga do np. 
deadlocka. Oczywiście wszystko zależy od tego jak cpu sychronizują 
zmiany pomiędzy sobą. Prawidlowo programista powinien zakładać że 
dowolnie pomiedzy barierami.

> oraz jak temu
> zaradzić?

Dla jednoprocesorowego systemu opartego na x86 Intel był bardzo 
wyrozumiały. Dla innych systemów tego typu problemy mogą wystąpić nawet 
bez NUMA, z jednym cpu:

https://en.wikipedia.org/wiki/Memory_ordering

Jak zaradzić? Przeczytać dokumentacje do systemu. Najprościej i 
najogólniej używać prymitywów dostepnych na poziomie cpu ewentualnie 
używać memory barrier w bardziej skomplikowanych sytuacjach nawet jesli 
pozornie wydaje się to bez sensu (w skrajnym przypadku stawia się "dużo 
muteksów" co może nie jest sensowne, ale działa).

CPU wymieniają między soba informacje o zmianach w prywatnych pamięciach 
i cache:

https://en.wikipedia.org/wiki/Cache_coherence

Nie ma innej drogi jak używać gotowcow dostarczonych przez kompilator 
albo OS do tego żeby być choć troche przenośnym.

Troche szkoda że teraz wszystko jest x86. Kiedy był Sparc ludzie jeszcze 
zastanawiali się "a co jeśli". Obecnie już nie :/