Setelah beberapa tulisan[1][2] mengenai OpenMP sebagai bahan kuliah saya jadi penasaran untuk membuat tiruannya dengan Delphi berhubung Delphi (saya pakai versi 7) memiliki kelas wrapper untuk menggunakan fasilitas threading di Win32. Sebetulnya Delphi versi 7 sudah lumayan tertinggal (mengingat sekarang sudah ada Delphi 200X) dalam hal pengembangan (tapi belum tahu juga untuk versi Turbo Delphi) dan untuk varian lainnya adalah FreePascal tetapi alternatif yang diajukan di FreePascal sepertinya tidak kompatibel secara bahasa dengan versi Object Pascal yang digunakan di Delphi 7 jadinya saya masih ragu-ragu. Akhirnya saya teruskan niat untuk mencoba membuat implementasi dari secuil fitur paralelisme OpenMP yaitu parallel for (untuk modifikasi sekumpulan data yang independen).
Pendahuluan
Langkah pertama adalah membuat algoritma sekuensial yang ingin diparalelkan (dibuat menjadi algoritma yang berjalan secara paralel). Algoritma yang saya pilih adalah seperti tulisan ini yaitu operasi terhadap seluruh elemen array 2 dimensi (misalnya citra) yang hanya melibatkan masing-masing elemen tersebut. Kodenya kira-kira seperti ini (yang dicetak miring adalah operasi elementernya)
for j := 0 to high(arr) do
for i := 0 to high(arr[j]) do begin
arr[j][i] := arr[j][i] + 10; { operasi elementer }
end;
Algoritma ini dipilih karena dianggap cukup sederhana karena jika diimplementasi secara paralel menggunakan thread maka antar thread tidak perlu melakukan komunikasi. Algoritma di atas cukup (bahkan mungkin terlalu) sederhana sehingga tidak bisa dibandingkan dengan algoritma paralel karena untuk membuat algoritma versi paralel ada overhead untuk penciptaan thread, penjadwalan, delegasi tugas, dan pembersihan. Oleh sebab itu yang dijadikan acuan untuk melakukan perbandingan performa adalah algoritma versi paralel yang hanya dikerjakan oleh satu buah thread saja. Waktu eksekusi untuk satu thread ini selanjutnya disebut sebagai t1 sedangkan waktu eksekusi algoritma versi paralel dengan n buah thread akan disebut sebagai tn sehingga pemercepatan (peningkatan kecepatan) akan dihitung sebagai perbandingan antara t1 dengan tn (t1/tn).
Pembuatan kelas Worker Thread
Penggunaan fasilitas threading di Delphi ada dua macam cara. Cara pertama adalah memanfaatkan fungsi-fungsi yang berkaitan dengan thread pada Win32 API dan cara kedua adalah membuat kelas turunan dari kelas TThread. Cara kedua dipilih secara subjektif dengan alasan kenyamanan pengelolaan. Pembuatan kelas turunan TThread dapat memanfaatkan wizard dari delphi dengan menggunakan menu File>New>Other>Thread Object. Fungsi yang ingin dijalankan pada thread ditempatkan sebagai fungsi execute yang menutup(override) implementasi dari kelas TThread. Sifat dari penggunaan kelas turunan TThread adalah objek tersebut akan dibebaskan dari memori setelah fungsi execute selesai dijalankan. Penciptaan dan Pembebasan ini tentunya akan menyebabkan redundansi proses yang tidak terlalu relevan dengan tujuan awal (mempercepat eksekusi). Oleh sebab itu perlu dibuat cara lain sedemikian rupa sehingga objek thread hanya perlu diciptakan sekali sebelum proses utama dilakukan dan hanya perlu sekali dibebaskan dari memori setelah seluruh pekerjaan selesai. Caranya adalah dengan membuat atribut status pada kelas thread dan membuat isi fungsi execute ini melakukan perulangan hingga tercapai status akhir (final state). Untuk itu kita perlu tiga buah keadaan yaitu Running, Idle, dan Done. Pada awalnya keadaan akan diinisialisasi sebagai Idle. Keadaan ini adalah keadaan yang menyatakan objek thread tidak sedang sibuk melakukan pekerjaan sehingga dapat didelegasikan. Jika objek thread sedang sibuk maka keadaannya adalah Running. Kode untuk kelas thread ditunjukkan dalam kode berikut :
unit Unit2;
interface
uses
Classes, Windows, SysUtils;
type
TThreadState = (tsRunning, tsIdle, tsDone);
TArrElmtModifier = class(TThread)
private
{ Private declarations }
FX, FY, FID: integer;
FState : TThreadState;
protected
procedure Execute; override;
procedure NotifyStart;
procedure NotifyDone;
public
constructor Create(AID:integer);
procedure Run;
procedure Done;
property X : integer read FX write FX;
property Y : integer read FY write FY;
property ID : integer read FID write FID;
property State : TThreadState read FState write FState;
end;
implementation
uses Unit1;
{ TArrElmtModifier }
constructor TArrElmtModifier.Create(AID:integer);
begin
inherited Create(false);
FID := AID;
X := 0;
Y := 0;
State := tsIdle;
self.FreeOnTerminate := false;
end;
procedure TArrElmtModifier.Done;
begin
FState := tsDone;
end;
procedure TArrElmtModifier.Execute;
begin
{ Place thread code here }
while (FState<>tsDone) do begin
if (FState=tsRunning) then begin
{ Do Thread Task here }
Form1.arr[Y][X] := Form1.arr[Y][X] + 10;
NotifyDone;
{ Notify when task done }
end;
sleep(1);
end;
end;
procedure TArrElmtModifier.NotifyDone;
begin
Form1.AcceptDone(FID);
State := tsIdle;
end;
procedure TArrElmtModifier.NotifyStart;
begin
Form1.Memo1.Lines.Add('Thread #'+inttostr(FID)+' started');
end;
procedure TArrElmtModifier.Run;
begin
State := tsRunning;
end;
end.
Implementasi Parallel for
Langkah selanjutnya adalah melakukan penjadwalan untuk alokasi pekerjaan dalam iterasi for agar dikerjakan oleh worker thread. Penyederhanaan (tanpa menggunakan antrian pekerjaan) dilakukan dengan penurunan tiap pekerjaan langsung diturunkan dari pola perulangan yang sama seperti pada algoritma sekuensial sehingga urutan pekerjaan menjadi terurut sesuai dengan eksekusi for. Selanjutnya dilakukan penjadwalan delegasi thread agar tiap thread mendapatkan proporsi beban pekerjaan yang cukup seimbang satu sama lain. Hal ini dilakukan dengan menggunakan antrian berbentuk cincin (ring queue) yang secara sederhana diimplementasi dengan memanfaatkan operator modulo pada struktur data kumpulan objek thread yang menggunakan array. Setelah semua pekerjaan didelegasikan perlu dibuat mekanisme barrier yang akan menunggu konfirmasi penyelesaian dari seluruh thread sebelum thread dibebaskan dari memori. Langkah terakhir adalah menampilkan perubahan. Hasil implementasi pada kode utama ditampilkan sebagai berikut :
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Unit2, StdCtrls, Spin;
type
TForm1 = class(TForm)
Memo1: TMemo;
SpinEdit1: TSpinEdit;
Button2: TButton;
Label1: TLabel;
Label2: TLabel;
SpinEdit2: TSpinEdit;
Button1: TButton;
procedure Button2Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
nthreads : integer;
threadflags : array of boolean;
threads : array of TArrElmtModifier;
arr : array of array of integer;
tq : integer;
procedure Prepare;
procedure DispatchThreads;
procedure AcceptDone(idx:integer);
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.AcceptDone(idx: integer);
begin
threadflags[idx] := false;
//memo1.lines.Add('done #'+inttostr(idx));
end;
procedure TForm1.DispatchThreads;
var
i, j, k : integer;
busy : boolean;
tmp : tstrings;
start, finish : longint;
begin
Memo1.Lines.Clear;
start := GetTickCount;
{ ordered scheduling }
for j := 0 to high(arr) do
for i := 0 to high(arr[j]) do begin
{ schedule iteration(i,j) }
busy := true;
repeat
k := tq; //GetNextAvailableThread
//if not threadflags[k] then begin
if threads[k].State = tsIdle then begin
threadflags[k] := true;
//memo1.lines.add(format('dispatch (%d,%d) to thread #%d', [i,j,k]));
threads[k].X := i;
threads[k].Y := j;
threads[k].Run;
busy := false;
break;
end;
tq := (tq + 1) mod length(threads);
Application.ProcessMessages;
until not busy;
end;
{ barrier, wait until all task finished }
repeat
busy := false;
for k := 0 to high(threads) do begin
if threadflags[k] then begin
busy := true;
break;
end;
end;
Application.ProcessMessages;
until not busy;
finish := GetTickCount;
{ clean up threads }
for i := 0 to high(threads) do
threads[i].State := tsDone;
{ display changes }
tmp := TStringlist.Create;
for j := 0 to high(arr) do begin
tmp.Clear;
for i := 0 to high(arr[j]) do begin
tmp.add(inttostr(arr[j][i]));
end;
memo1.Lines.add(tmp.CommaText);
end;
Memo1.Lines.Add('Done in '+inttostr(finish-start)+' ms');
tmp.Free;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
i : integer;
begin
Prepare;
nthreads := SpinEdit1.Value;
setlength(threadflags, nthreads);
setlength(threads, nthreads);
for i := 0 to high(threads) do begin
threadflags[i] := false;
threads[i] := TArrElmtModifier.Create(i);
end;
DispatchThreads;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i, j, k : integer;
start, finish : cardinal;
tmp : TStrings;
begin
Prepare;
Memo1.Lines.Clear;
start := GetTickCount;
{ ordered scheduling }
for j := 0 to high(arr) do
for i := 0 to high(arr[j]) do begin
arr[j][i] := arr[j][i] + 10;
end;
finish := GetTickCount;
{ display changes }
tmp := TStringlist.Create;
for j := 0 to high(arr) do begin
tmp.Clear;
for i := 0 to high(arr[j]) do begin
tmp.add(inttostr(arr[j][i]));
end;
memo1.Lines.add(tmp.CommaText);
end;
Memo1.Lines.Add('Done in '+inttostr(finish-start)+' ms');
tmp.Free;
end;
procedure TForm1.Prepare;
var
i,n : integer;
begin
n := SpinEdit2.Value;
if length(arr)>0 then
for i := 0 to high(arr) do
setlength(arr[i], 0);
setlength(arr, n);
for i := 0 to high(arr) do
setlength(arr[i], n);
tq := 0;
end;
end.
Tampilan Form (4K PNG)
Pengujian
Untuk menguji perubahan kecepatan pada penggunaan thread digunakan dimensi array 10×10 dan jumlah thread yang diuji antara lain 1 (kontrol), 2, 4, 8, 16 (diabaikan karena asimtotik). Hasil pengukuran ditunjukkan pada gambar berikut.
Grafik Speedup (4K PNG)
Penutup
Sepertinya bisa dinyatakan berhasil, walaupun sebelumnya saya coba justru bisa dibilang gagal karena penggunaan multithread justru memperlambat (mungkin karena saya menjalankan langsung dari IDE). Selanjutnya mungkin saya akan mencoba bagaimana mengimplementasi pola eksekusi berbentuk pohon, analisis statik independensi antar operasi, dan komunikasi (sinkronisasi) antar thread yang pada tujuan akhirnya adalah mewujudkan salah satu mimpi saya terdahulu yaitu membuat bahasa pemrograman (next generation programming language) paralel (akhirnya tujuan perancangannya bisa lebih spesifik) yang memanfaatkan threading secara implisit (tidak perlu menyatakan pembuatan dan pembersihan objek thread secara eksplisit dalam kode program) dan sebisa mungkin makin meng-eksplisitkan independensi antar data/task pada kode program dan penulisan yang bersih dan nyaman untuk dibaca (yang terakhir agak subjektif dan kurang terdefinisi, hehehe). Perwujudan ini (mungkin) dilakukan dalam beberapa tahap yaitu pengembangan abstract machine (sebagai testbed komputer paralel), interpreter, dan pada akhirnya implementasi compiler dan IDE untuk bahasa baru ini yang untuk sementara saya namakan sebagai ‘project pi’ (akhirnya ada juga namanya).
GAIBlog 