Obliczenia współbieżne na wątkach
Program pokazuje jak zrealizować obliczenia współbieżne na wątkach.
Kiedy można stosować obliczenia współbieżne?
Aby obliczenia współbieżne były możliwe do zastosowania, musi istnieć możliwość podzielenia zadania
obliczeniowego na niezależne części.
Mój przykład
W moim przykładzie używam czterech wątków do obliczenia silni. Obliczanie silni w ten sposób nie ma
większego sensu i służy tu prostemu zobrazowaniu, na czym rzecz polega.
Omówię to na przykładzie silni z 12.
Silnia z N to iloczyn liczb od 1 do N. (Silnia z 0 jest 1.)
Dla 12 jest to 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 10 * 11 * 12.
Łatwo zauważyć, że taki iloczyn można podzielić na iloczyny częściowe np.:
(1 * 2 * 3) * (4 * 5 * 6) * (7 * 8 * 9) * (10 * 11 * 12).
Celowo utworzyłem 4 iloczyny częściowe, oddzielone nawiasami, bo mam zamiar przydzielić każdy z nich
jednemu z czterech wątków, którymi się posługuję w przykładzie.
Na koniec pomnożę iloczyny częściowe przez siebie i otrzymam wynik.
Synchronizacja różnych wątków
Warto zauważyć, że to końcowe mnożenie zostanie również wykonane przy użyciu wątków.
Ponieważ nie wiadomo, w jakim momencie poszczególne wątki wyliczą iloczyny częściowe, należy
wprowadzić synchronizację wątków. Wygląda to tak:
Pierwszy wątek pobiera własny, już obliczony iloczyn częściowy i ustawia flagę gotowości tego
iloczynu do pobrania przez inny wątek.
Drugi wątek po obliczeniu własnego iloczynu czeka na pojawienie się flagi gotowości pierwszego wątku
i mnoży własny iloczyn przez iloczyn z pierwszego wątku, po czym również ustawia flagę gotowości do
pobrania iloczynu przez trzeci wątek. Itd., co można zapisać jako:
Wątek 1: iloczyn_końcowy_1 = iloczyn_częściowy_1
Wątek 2: iloczyn_końcowy_2 = iloczyn_końcowy_1 * iloczyn_częściowy_2
Wątek 3: iloczyn_końcowy_3 = iloczyn_końcowy_2 * iloczyn_częściowy_3
Wątek 4: iloczyn_końcowy_4 = iloczyn_końcowy_3 * iloczyn_częściowy_4
Dzięki synchronizacji przez flagi odbędzie się to w takiej, a nie innej kolejności.
Wynikiem obliczeń jest iloczyn_końcowy_4.
Losowość
Abyś mógł się przekonać, że kolejność zadań wykonywanych przez wątki jest losowa (za wyjątkiem
przypadku synchronizacji) dodałem przycisk ‘Kolejność’.
Praktycznie za każdym razem jest inna.
Przypadek ogólny
Dla liczb, które nie dzielą się przez 4 (ilość wątków) np. 13, ostatni iloczyn jest rozszerzany.
Dla 13 będzie on wyglądał (10 * 11 * 12 * 13). Jest to prosta metoda, ale można się pokusić o
przerobienie programu tak, aby np. dla 14 utworzył iloczyny:
(1 * 2 * 3 * 13) * (4 * 5 * 6 * 14) * (7 * 8 * 9) * (10 * 11 * 12),
aby możliwie równomiernie obciążyć wątki.
Dla liczb zbyt małych, aby „obsadzić” wszystkie wątki, należy przyjąć iloczyny częściowe równe 1.
(Gdybyśmy dodawali wyrazy a nie mnożyli, byłoby to 0).
Uruchomienie programu
Aby uruchomić program, należy utworzyć nowy projekt z Form1, Unit1 i wkleić całą zawartość mojego
Unit1 oraz powiązać w zdarzenia OnCreate i OnClose w kodzie z formą.
Wszystkie kontrolki zostaną utworzone automatycznie po uruchomieniu.
Wykonanie obliczeń
W żółte pole należy wpisać liczbę od 0 do 20, której silnię chcemy obliczyć.
Wynik po kliknięciu Oblicz pojawi się w zielonym polu.
Kiedy można stosować obliczenia współbieżne?
Aby obliczenia współbieżne były możliwe do zastosowania, musi istnieć możliwość podzielenia zadania
obliczeniowego na niezależne części.
Mój przykład
W moim przykładzie używam czterech wątków do obliczenia silni. Obliczanie silni w ten sposób nie ma
większego sensu i służy tu prostemu zobrazowaniu, na czym rzecz polega.
Omówię to na przykładzie silni z 12.
Silnia z N to iloczyn liczb od 1 do N. (Silnia z 0 jest 1.)
Dla 12 jest to 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 10 * 11 * 12.
Łatwo zauważyć, że taki iloczyn można podzielić na iloczyny częściowe np.:
(1 * 2 * 3) * (4 * 5 * 6) * (7 * 8 * 9) * (10 * 11 * 12).
Celowo utworzyłem 4 iloczyny częściowe, oddzielone nawiasami, bo mam zamiar przydzielić każdy z nich
jednemu z czterech wątków, którymi się posługuję w przykładzie.
Na koniec pomnożę iloczyny częściowe przez siebie i otrzymam wynik.
Synchronizacja różnych wątków
Warto zauważyć, że to końcowe mnożenie zostanie również wykonane przy użyciu wątków.
Ponieważ nie wiadomo, w jakim momencie poszczególne wątki wyliczą iloczyny częściowe, należy
wprowadzić synchronizację wątków. Wygląda to tak:
Pierwszy wątek pobiera własny, już obliczony iloczyn częściowy i ustawia flagę gotowości tego
iloczynu do pobrania przez inny wątek.
Drugi wątek po obliczeniu własnego iloczynu czeka na pojawienie się flagi gotowości pierwszego wątku
i mnoży własny iloczyn przez iloczyn z pierwszego wątku, po czym również ustawia flagę gotowości do
pobrania iloczynu przez trzeci wątek. Itd., co można zapisać jako:
Wątek 1: iloczyn_końcowy_1 = iloczyn_częściowy_1
Wątek 2: iloczyn_końcowy_2 = iloczyn_końcowy_1 * iloczyn_częściowy_2
Wątek 3: iloczyn_końcowy_3 = iloczyn_końcowy_2 * iloczyn_częściowy_3
Wątek 4: iloczyn_końcowy_4 = iloczyn_końcowy_3 * iloczyn_częściowy_4
Dzięki synchronizacji przez flagi odbędzie się to w takiej, a nie innej kolejności.
Wynikiem obliczeń jest iloczyn_końcowy_4.
Losowość
Abyś mógł się przekonać, że kolejność zadań wykonywanych przez wątki jest losowa (za wyjątkiem
przypadku synchronizacji) dodałem przycisk ‘Kolejność’.
Praktycznie za każdym razem jest inna.
Przypadek ogólny
Dla liczb, które nie dzielą się przez 4 (ilość wątków) np. 13, ostatni iloczyn jest rozszerzany.
Dla 13 będzie on wyglądał (10 * 11 * 12 * 13). Jest to prosta metoda, ale można się pokusić o
przerobienie programu tak, aby np. dla 14 utworzył iloczyny:
(1 * 2 * 3 * 13) * (4 * 5 * 6 * 14) * (7 * 8 * 9) * (10 * 11 * 12),
aby możliwie równomiernie obciążyć wątki.
Dla liczb zbyt małych, aby „obsadzić” wszystkie wątki, należy przyjąć iloczyny częściowe równe 1.
(Gdybyśmy dodawali wyrazy a nie mnożyli, byłoby to 0).
Uruchomienie programu
Aby uruchomić program, należy utworzyć nowy projekt z Form1, Unit1 i wkleić całą zawartość mojego
Unit1 oraz powiązać w zdarzenia OnCreate i OnClose w kodzie z formą.
Wszystkie kontrolki zostaną utworzone automatycznie po uruchomieniu.
Wykonanie obliczeń
W żółte pole należy wpisać liczbę od 0 do 20, której silnię chcemy obliczyć.
Wynik po kliknięciu Oblicz pojawi się w zielonym polu.
unit Unit1; interface uses Windows, SysUtils, Classes, Forms, Graphics, StdCtrls, ExtCtrls, Controls; const ThreadCount = 4; //ilość wątków JobCount = 4; //ilość zadań w wątku type TThreadCalc = class(TThread) private Tag: integer; //numer wątku Job: integer; //numer zadania Succ: array [0..JobCount - 1] of integer; //kolejność wykonywania zadań //przez wszystkie wątki FGetSucc: boolean; //jeśli true, badana jest kolejność protected procedure Execute; override; procedure GetData; //pobranie danej do obliczenia silni procedure PutData; //wyświtlenie rezultatu procedure CalcProc; //procedura obliczeniowa procedure GetSucc; //bada kolejność public constructor CreateWithPar(aTag: integer; aFGetSucc: boolean = false); //konstruktor z parametrami end; type TForm1 = class(TForm) procedure FormCreate(Sender: TObject); procedure Calc(Sender: TObject); procedure TimerTimer(Sender: TObject); procedure FormClose(Sender: TObject; var Action: TCloseAction); public Threads: array [0..ThreadCount - 1] of TThreadCalc; //tablica wątków Edits : array [0..JobCount - 1, 0..ThreadCount - 1] of TEdit; //edity do wyświetlenia wyników pośrednich //lub kolejności Timer: TTimer; //warto umieścić na wypadek niepowodzeń procedure ClearEdits(Sender: TObject); procedure RunThreads(aFGetSucc: boolean = false); //uruchamia wszystkie wątki end; type TValue = record IntValue: int64; StrValue: string; IsInt : boolean; //flaga gotowości wartości int64 do dalszych obliczeń IsStr : boolean; //flaga gotowości wartości string do dalszych obliczeń end; var Form1: TForm1; Value: array [0..JobCount - 1, 0..ThreadCount - 1] of TValue; //tablica wyników pośrednich //służy także do synchronizacji obliczeń SuccCtr: integer; //licznik do badania kolejności wykonywania zadań //przez wszystkie wątki implementation {$R *.dfm} constructor TThreadCalc.CreateWithPar(aTag: integer; aFGetSucc: boolean = false); //tworzy wątek //jeśli aFGetSucc = true zbiera informacje o kolejności var iJob: integer; begin Tag := aTag; FGetSucc := aFGetSucc; for iJob := 0 to JobCount - 1 do //ustawienie flag wartości //na brak gotowości do dalszych obliczeń begin Value[iJob, Tag].IsInt := false; Value[iJob, Tag].IsStr := false; end; Self := Create(false); end; procedure TThreadCalc.GetData; //pobranie danej do obliczenia silni begin Value[Job, Tag].IntValue := StrToInt(Form1.Edits[Job, 0].Text); Value[Job, Tag].IsInt := true; end; procedure TThreadCalc.PutData; //wyświetlenie wyników pośrednich //lub kolejności var iJob: integer; begin if not FGetSucc then begin for iJob := 1 to JobCount - 1 do if Value[iJob, Tag].IsInt then Form1.Edits[iJob, Tag].Text := IntToStr(Value[iJob, Tag].IntValue) else if Value[iJob, Tag].IsStr then Form1.Edits[iJob, Tag].Text := Value[iJob, Tag].StrValue else Form1.Edits[iJob, Tag].Text := ''; end else for iJob := 0 to JobCount - 1 do Form1.Edits[iJob, Tag].Text := IntToStr(Succ[iJob]); if Tag = 0 then Form1.Edits[0, Tag].ReadOnly := false; end; procedure TThreadCalc.CalcProc; //procedura obliczeniowa procedure Job0; begin Job := 0; Synchronize(GetData); //używamy Synchronize po pobieramy daną z Form1 //tj. wątku głównego GetSucc; end; procedure Job1; //zadanie przygotowuje iloczyn częściowy //np. dla 12! i Tag = 1 jest to 4 * 5 * 6 var s: string; v: int64; i: integer; Max, Min: int64; begin Job := 1; v := Value[Job - 1, Tag].IntValue; Min := Tag + Tag * (v div (ThreadCount + 1)) + 1; Max := Tag + (Tag + 1) * (v div (ThreadCount + 1)) + 1; if Tag = ThreadCount - 1 then Max := v; if Max > v then Max := v; for i := Min to Max do if i = Min then s := IntToStr(i) else s := s + '*' + IntToStr(i); if s = '' then s := '1'; Value[Job, Tag].StrValue := s; Value[Job, Tag].IsStr := true; GetSucc; end; procedure Job2; //zadanie wylicza wartość iloczynu częściowego var v: int64; s: string; begin Job := 2; s := Value[Job - 1, Tag].StrValue; v := 1; s := s + '*'; while Pos('*', s) > 0 do begin v := v * StrToInt(Copy(s, 1, Pos('*', s) - 1)); s := Copy(s, Pos('*', s) + 1, Length(s)); end; Value[Job, Tag].IntValue := v; Value[Job, Tag].IsInt := true; GetSucc; end; procedure Job3; //zadanie mnoży iloczyny częściowe //np. dla Tag = 1 jest to //iloczyn_częściowy(Tag = 0) * iloczyn_częściowy(Tag = 1) //w zadaniu występuje synchronizacja wątków begin Job := 3; if Tag = 0 then begin Value[Job, Tag].IntValue := Value[Job - 1, Tag].IntValue; Value[Job, Tag].IsInt := true; end else begin while not Value[Job, Tag - 1].IsInt do //synchronizacja wątków ; //tu: oczekiwanie na zakończenie //obliczeń przez wątek (Tag - 1) Value[Job, Tag].IntValue := Value[Job - 1, Tag].IntValue * Value[Job, Tag - 1].IntValue; Value[Job, Tag].IsInt := true; end; GetSucc; Synchronize(PutData); //używamy Synchronize bo wpisujemy dane do Form1 //tj. wątku głównego Terminate; //jest to ostatnie zadanie i kończy wątek end; begin Job0; Job1; Job2; Job3; end; procedure TThreadCalc.GetSucc; begin if not FGetSucc then Exit; Inc(SuccCtr); Succ[Job] := SuccCtr; end; procedure TThreadCalc.Execute; begin FreeOnTerminate := true; Priority := tpNormal; CalcProc; end; procedure TForm1.Calc(Sender: TObject); //uruchamia obliczenia begin try if StrToInt(Edits[0, 0].Text) in [0..20] then begin Edits[0, 0].ReadOnly := true; if (Sender as TButton).Tag = 0 then RunThreads else if (Sender as TButton).Tag = 1 then RunThreads(true); end; except end; end; procedure TForm1.RunThreads(aFGetSucc: boolean = false); //uruchamia wszystkie wątki var iThread: integer; begin ClearEdits(nil); SuccCtr := 0; for iThread := 0 to ThreadCount - 1 do Threads[iThread] := TThreadCalc.CreateWithPar(iThread, aFGetSucc); end; procedure TForm1.TimerTimer(Sender: TObject); begin Application.ProcessMessages; end; procedure TForm1.ClearEdits(Sender: TObject); //czyści edity var iJob, iThread: integer; begin for iJob := 0 to JobCount - 1 do for iThread := 0 to ThreadCount - 1 do if not ((iJob = 0) and (iThread = 0)) then Edits[iJob, iThread].Text := ''; end; procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction); //należy powiązać z OnClose w ObjectInspectorze var iThread: integer; begin for iThread := 0 to ThreadCount - 1 do try Threads[iThread].Terminate; except end; end; procedure TForm1.FormCreate(Sender: TObject); //tworzy wszystko co jest potrzebne do sprawdzenia jak to działa //należy powiązać z OnCreate w ObjectInspectorze const constWidth = 240; constHeight = 21; var iJob, iThread: integer; l: TLabel; b: TButton; begin Width := 1000; Height := 600; Position := poScreenCenter; Font.Name := 'Tahoma'; Font.Size := 8; Caption := 'Obliczanie silni na 4 wątkach, podaj wartość od 0 do 20'; for iJob := 0 to JobCount - 1 do begin l := TLabel.Create(Self); l.Left := 10 + iJob * constWidth; l.Top := 14; case iJob of 0 : l.Caption := 'Zadanie ' + IntToStr(iJob) + ', wejście'; 1, 2: l.Caption := 'Zadanie ' + IntToStr(iJob); 3 : l.Caption := 'Zadanie ' + IntToStr(iJob) + ', wyjście'; end; InsertControl(l); for iThread := 0 to ThreadCount - 1 do begin Edits[iJob, iThread] := TEdit.Create(Self); Edits[iJob, iThread].Width := constWidth; Edits[iJob, iThread].Left := 10 + iJob * constWidth; Edits[iJob, iThread].Top := 30 + iThread * constHeight; if not ((iJob = 0) and (iThread = 0)) then Edits[iJob, iThread].ReadOnly := true; InsertControl(Edits[iJob, iThread]); end; end; Edits[0, 0].OnChange := ClearEdits; Edits[0, 0].Color := clYellow; Edits[JobCount - 1, ThreadCount - 1].Color := clLime; b := TButton.Create(Self); b.Left := Edits[0, 0].Left; b.Top := 30 + ThreadCount * constHeight; b.Width := constWidth; b.Tag := 0; b.Caption := 'Oblicz'; b.OnClick := Calc; InsertControl(b); b := TButton.Create(Self); b.Left := Edits[1, 0].Left; b.Top := 30 + ThreadCount * constHeight; b.Width := constWidth; b.Tag := 1; b.Caption := 'Kolejność'; b.OnClick := Calc; InsertControl(b); Timer := TTimer.Create(Self); Timer.Interval := 100; Timer.OnTimer := TimerTimer; Timer.Enabled := true; end; end.
4 komentarze
Używam Synchronize ponieważ modyfikuję zawartość editów na formie głównej, a w takiej sytuacji (akurat na przykładzie UpdateCaption) Borland zaleca takie postępowanie. Wystarczy wyklikać File/New/...ThreadObject i samo się to wpisuje do unitu. Chciałem w tych editach pokazać obliczenia cząskowe, których nikt by nie wypisywał w postaci stringa np. '1 * 2 * 3', gdyby chodziło tylko o szybkość obliczeń, a tu chodzi także o prezentację podziału na obliczenia cząstkowe.
Jeśli chodzi o Sleep(1ms) to jest to czas strasznie długi w porównaniu do większości obliczeń.
Tak czy inaczej trzeba by dobrać odpowiednią proporcję między czasem trwania zadań (Job0, Job1,...), wynikającym z ich złożoności, a czasem trwania Sleep, żeby maksymalnie wykorzystać procesor. Można jeszcze skorzystać z GetTickCount.
Trochę się boję prowadzić dalsze testy, skoro Azarien mnie ostrzega o poważnym problemie jaki mam z chłodzeniem procesora. Niby w Bios-ie mam ustawione zabezpieczenie przed przegrzaniem procesora i do tej pory zwalniał pracę, ale rzeczywiście nigdy nie było pisku. Muszę to sprawdzić.
Ten cały artykuł powstał na bazie eksperymentu. Zanim przeczytałem wasze komentarze miałem zamiar dopisać, że ten eksperyment może być niebezpieczny dla procesora - jak się okazuje dla mojego.
Jeżeli przy obciążeniu 100% zaczyna ci piszczeć, to masz poważny problem z chłodzeniem procesora.
Jaki sens ma dzielenie tego na wątki skoro i tak wszystko wykonujesz w kontekście wątku głównego przez Synchronize?
I zamiast Synchronize(ProcessMessages); można było dać Sleep(ilosc ms)
kod raczej nie zabija procesorów :) jeżeli temperatura ci rośnie tak że włącza się piszczek to znaczy że chłodzenie się nie wyrabia. Choćby dlatego że może radiator niedokładnie przylega do procesora, czy nawet dlatego że jest już mocno zakurzony. W normalnych warunkach temperatura nie powinna przekraczać 70 stopni (przynajmniej jak dla mnie), nieważne jakie obciążenie.