1
76
IMPLEMENTASI ALGORITME PARALEL SVD DENGAN MENGGUNAKAN METODE BLOCK-JACOBI DAN PENENTUAN SUBPROBLEM DINAMIS PADA LINGKUNGAN KLUSTER KOMPUTER T. Basaruddin* dan Rifki Sadikin** ABSTRAK Algoritme paralel untuk menghitune SVD sebuah matrik A <= D™">
dX itu, dllakukan penentuan
ftu
n a n
m
a
X
m
U
m
m a t C h m g
U
W
/
f
l
P
3
d
a
S 6 b U a h
yang lebih sederhana
2 ' 7 , memperoleh perband.ngan unjuk C
e
d
a
n
d
a
l
a
m
^
b u k a
A
"
« « « * -
yaitu dengan algoritme greedy
m ^ fwSnS re t o /a
Aieoritm,
Nfrungan kluster komputer. Percobaan dilakukan untuk speed
kerja antara algoritme dinamis dan algoritme statis, profiling,
tamik d i i Z TenHUnJUkka" b3hWa ^ " ° ^ ' d e n g a n m^eTacob dinamik didapatkan, speed up dengan pemadwalan dinamis lebih tinggi daripada algoritme statis speed up algontme dinamik pada matrik rampat lebih tinggi daripada matrik jarang. a
P
a l 8
r i t m e
P
a
r
a
l
d
P
Kata kunci: algoritme paralel SVD, metode Jacobi, algoritme greedy, passing interface
lingkungan kluster komputer,
?
message
ABSTRACT SVD
(Singular Value Decomposition) paralel algorithm for a Matrix A e R
m x n
with dynamic OFdeFifig i§
presented. The difference between static ordering and dynamic ordering is in subproblem ordering. Dynamic ordering uses the actual status of matrix A for choosing subproblems. The subproblems that dynamic ordering choosed have the highest norm totally. The solution of this task is equivalent to the solution of maximum
weight perfect matching problem in a graph. The solution of maximum weight perfect matching is
not cheap Therefore, the greedy algorithm for efficient solution is presented. The algorithm is implemented in
MPI (Message Passing Interface) and paralel computer cluster environment. The computational
experiments both type ordering. Speed Up, profiling and accuration were taken. The results confirm that speed up is obtained in dynamic ordering. Speed up with dynamic algorithm is higher than static algorithm, and speed up with dynamic algorithm for dense matrix is higher than speed up in sparse matnx. Keywords: SVD paralel algorithm, dynamic ordering algorithm, greedy algorithm, paralel computer cluster environment, message passing interface m xn
1. PENDAHULUAN
(Golub dan Loan
1989). Oleh karena i
teknik paralel untuk menyelesaikan S V D diharapk Komputasi S V D (Singular merupakan
komputasi
Value yang
Decomposition)
penting
dan
mengurangi waktu yang dibutuhkan.
sering
SVD
dijumpai dalam persoalan aljabar linear. M i s a l n y a untuk
penyelesaian
permasalah
pencarian
rank
sebuah matrik A e R
m x n
adalah: ..(
r
dengan
matrik, penyelesaian permasalahan least
komputasi
SVD
dan
UZV
orthogonal. I merupakan matrik diagonal. Elem
proyeksi ortogonal (Heath 2002). Algoritme serial melakukan
square,
A =
pada matrik diagonal E adalah nilai singular mat
memiliki
untuk
kompleksitas Q(m xn) * **
untuk matrik dengan ukuran
Fakultas I l m u Komputer, Pasca S a r j a n a , Fakultas
Majalah I P T E K - V o l .
UI limit Komputer,
U e
dan
R
V e R
adalah
mat
(Golub dan Loan 1989).
UI
15, N o . 2, M e i 2004
77
5 * _
ilgoritme S V D dapat digolongkan algoritme langsung dan algoritme tidak Algoritme S V D langsung menggunakan misalnya dengan iterasi QR. algoritme S V D tidak langsung adalah S V D didapatkan secara iteratif diantaranya algoritme Jacobi. Untuk matrik jarang bidiagonalisasi menjadi pilihan, misalnya Lanczos (Heath 2002).
dengan
paralel S V D lebih mudah didapatkan menggunakan algoritme tidak langsung dan Loan 1989). Algoritme paralel S V D matrik rampat lebih banyak menggunakan Jacobi, sedangkan untuk matrik jarang dan iggunakan metode Lanczos, Davidson atau ividson. Algoritme paralel S V D dengan Jacobi telah diterapkan dan diusulkan (Luk dan Park 1989) melakukan i S V D dengan metode Jacobi dengan ;n statis namun dengan berbagai skenario. (Becka dan Vajtersic 2002) -melakukan i metode Jacobi dengan penjadwalan (Becka dan Vajtersic 2002) rmasikan bahwa algoritme dengan dinamis memiliki kinerja lebih baik penjadwalan statis dilihat dari jumlah yang dibutuhkan untuk mendapatkan bentuk (Becka dan Vajtersic 2002)melakukan itasi algoritme S V D dengan metode pada lingkungan yang berparalel tinggi.
2. A L G O R I T M E S E R I A L
itasi algoritme SVD dengan metode Jacobi pd^alan dinamik seperti pada (Becka dan 2002) dilakukan. Perbedaan dengan dan Vajtersic 2002) adalah implementasi dalam lingkungan kluster komputer. itu, dilakukan juga pengukuran speed up bobagai macam bentuk matrik yaitu bentuk nmpat, matrik jarang dan matrik tridiagonal. ini diorganisasikan sebagai berikut: bagian 1 pendahuluan,
bagian
2
menceritakan
pemilihan
algoritme
paralel
dinamis metode
berisi Jacobi
penjabaran dan
strategi
pemilihan indek dinamis dengan algoritme
greedy,
bagian 5 berisi data hasil percobaan dan pembahasan hasil percobaan, percobaan yang dilakukan adalah pengukuran speed perbandingan
up, melakukan profiling
presisi,
dan
bagian
6
dan berisi
kesimpulan.
Ide dasar algoritme Jacobi adalah meminimalkan nilai elemen non-diagonal pada matrik A . Jika didefinisikan F(A,l)
sebagai (2)
Z V
F(A,l)=f.
/=i
j=\,i*j
Metode Jacobi secara terus menerus mengecilkan nilai F(A,l)
sehingga A menjadi diagonal.
Metode Jacobi dapat diterapkan dcugan operdSl ulOK mxn
dibuat menjadi blok matrik
matrik. A e R berukuran / x I. Ditentukan 2 indek yaitu i dan dengan i * j dan i j =0,1,...,/ sehingga didapatkan gabungan 4 blok matrik yaitu: (A Sir
A'J
.(3)
Perhitungan S V D dilakukan pada matrik Sij apabila nilai F(Sij,l) melebihi suatu konstanta 8. Perhitungan SVD dilakukan untuk matrik Sij, sehingga didapatkan matrik X dan Y yang persamaan:
memenuhi
4
SY,,=D„
•(4)
dan matrik D adalah dalam bentuk blok diagonal. ..(5) n)
Perhitungan apabila,
S V D dilakukan
pada
matrik Sij
ie serial untuk metode Jacobi, bagian 3 Bntakan tentang pemilihan dinamis yaitu apa *auksud dengan pemilihan dinamis dan apa
F ( S i J M = p i
+
\ A l > S
..(6)
dengan 6 = e / L
•afan pemilihan dinamis dibanding dengan ham statis, bagian 4 adalah algoritme paralel
Vol. 15, No. 2, Mei 2004 - Majalah IPTEK
78
Pemilihan indek / dan j , serta perhitungan S V D untuk matrik Sij dilakukan secara berulang sehingga nilai F ( A , l ) menjadi kecil. Pemilihan indek i dan j dapat dilakukan dengan memilih pasangan i dan j secara statis atau dinamis. Misalnya pasangan-pasangan indek i dan j diberikan
W\J\\\hJi)>
»(W/)}
maka algoritme serial
Kompleksitas berdasarkan
Algoritme kompleksitas
1
dapat
perhitungan
dihitun SV
perkalian matrik dan jumlah sweep Gumlah itera while). Apabila m = n (matrik bujur sangkar) da ditentukan jumlah faktor blok / diperoleh (Bec dan Vajtersic 2002). I |=nsw. — 2 2
TIME
seria
untuk menghitung SVD dengan metode Jacobi dapat ditulis seperti Algoritme 1 (Becka dan Vajtersic 2002).
Algoritme 1 { A l g o r i t m e SVD b l o k - J a c o b i 2 Sisi Serial) U = Im,V = In while F ( A , l ) > e do for k = 1 to L do (ij) -
—" 2
3
+ A4c /j
2,r
2
+0(nsw.« ) 2
( Konstanta c, tergantung dari algoritme S V D ya digunakan, sedangkan konstanta c berasal d perkalian matrik. nsw adalah banyaknya iterasi pa Algoritme 1. 2
3 P E M I L I H A N DINAMIS (ikjk)
5then
Kecepatan algoritme pencarian SVD dengan meto semakin cepat proses pengenolan nilai Norm no
• Komputasi SVD pada subproblem Sy
Jacobi tergantung pada jumlah iterasi. Artin
UF(Sy,l)2:
diagonal matrik maka semakin cepat waktu ya • menghasilkan Xy dan Yy
dibutuhkan. Pada satu iterasi yang dilakukan ada
SVEKSyi-^Xy.Yy
membuat norm blok matrik A y dan A j i menjadi n Jadi setiap iterasi nilai F (A, I) berkurang seban
• Perbaharui Blok Kolom
lAy\
+ \ d ^ F . Oleh karena pengurangan F ( H
for t = 1 to / do tergantung pada besaf iiorm 2 blok yang dipi (A j,A j ) = (A i,A j ). Yjj t
t
t
t
(U ,U ) = (U«,U ).Xy ti
U
tj
(V,i,V ) = (V, ,V ).Y tj
i
tJ
ij
maka pemilihan blok matrik yang dilakukan ope SVD sangat penting. Apabila setiap iterasi dilaku untuk
2
I^IJF +
end for
blok
matrik
dengan
jum
| | ; 4 , | | F maksimum maka dapat diharap /
nilai F (A, I) lebih cepat menuju nol.
• Perbaharui Blok Baris
Pemilihan Dinamis adalah pemilihan indek y f
A
\
for t = 1 to / do \)> )
= xl \ j > j
end for
tidak ditetapkan
secara
buta, namun dilaku
dengan mengambil i dan j yang memiliki
lUjF + l^lr
7,
maksimum. Biaya tambahan da
melakukan S V D dengan pemilihan Dinamis ad
end if end for
pengurutan
dan
norm dan
perhitungan norm
pengurutan. dalam
Perhitu
kasus ^terb
dibandingkan dengan biaya untuk perhitungan
end
membutuhkan
end while
waktu
sebanyak
0(/),
memiliki norm optimal memiliki biaya lebih ren
matrik Sy . Dalam percobaan prosedur SVD(S„ ,1)
matrik 0 ( n /I) yaitu pencarian
yang melakukan dekomposisi S V D terhadap sub
dengan metode Jacobi yang melibatkan perk
Prosedur SVD(S
,1) merupakan prosedur kernel
V
adalah
fungsi
dgesvd
pada
paket
indek ( i j )
LAPACK
(Anderson dan Dimmel 1999).
Majalah IPTEK - Vol. 15, No. 2, Mei 2004
79
DENGAN
4. ALGORITME PARALEL PEMILIHAN DINAMIS
Sebuah graf G(\fi,0
dapat dibentuk berdasarkan
informasi norm pada tiap blok pada matrik yang dalam
hendak didekomposisi singular. Simpul-simpul graf
mudah
adalah indek blok yang diberi label 1 sampai dengan
elkan. Apabila terdapat p prosessor maka
/, busur graf menghubungkan simpul dengan label /
i p iterasi dapat dilakukan secara bersamaan
dan label j dengan syarat /' < j dan tiap busur diberi
subproblem yang dilakukan tiap prosessor
bobot
wij
Perfect
M a t c h i n g dapat dilakukan pada graf G(\|/,£)
satu KWaikan
kelebihan
metode
perhitungan . SVD
Jacobi adalah
n i ^ n l in subproblem yang berbeda. lie S V D paralel dilakukan dengan strategi > {Single I n s t r u c t i o n Multiple D a t a ) . Algoritme sama dijalankan pada tiap prosessor yaitu yang melakukan perhitungan SVD, untuk em A y dan A / i . Tiap prosessor melakukan gan untuk matrik U, V dan memperharui ' pada matrik A untuk kolom ke-j dan kolom keir mendistribusi hasil yang diperoleh ke lain.
=jA
u
F + \\A \\F.
Maximum-weight
J I
dalam waktu 0(p ), dengan p adalah 1/2. Permasalahan
pemilihan pasangan
disederhanakan Matching
dari
menjadi
Algoritme greedy subset
maksimum
indek dapat
Maximum-weight pencarian
mengurangi dengan
secara
greedy.
biaya pencarian
harapan
maksimum. Algoritme greedy
Perfect
mendekati
dalam pencarian
subset adalah dengan cara mengurutkan semua kemungkinan pasangan indek / dan j dengan i<j
pada serial, di lingkungan paralel strategi menetapkan pasangan indek dapat dilakukan statik atau secara Dinamis. Pemilihan pada lingkungan paralel lebih sulit n serial. Beberapa pasang indek harus sehinga pasangan-pasangan indek itu nilai paling optimal daripada kemungkinan indek lainnya. Permasalahan pemilihan pasangan indek optimal dapat dianalogikan permasalahan maximum-weight perfect •problems padateori graf. M a t c h i n g pada sebuah graf G(y/,%), dengan y/ sehimpunan simpul dan { adalah sehimpunan
berdasarkan nilai ||^,. ||F + ^ A ||F j t
dalam urutan
tidak menaik. Kemudian, dilakukan p » m i n d a i a n dari nilai yang paling tinggi ke paling rendah. Pasangan indek ditambahkan ke subset yang dicari apabila indek-indek dari pasangan
indek yang sedang
dipindai belum menjadi anggota subset. Algoritme greedy
ini memiliki kompleksitas 0(p log(p))
akibat
pemindaian dan pengurutan. Berdasarkan pemilihan subproblem Dinamis, algoritme S V D paralel pada sejumlah p , dan tiap prosessor diberi label me = 0,1, ....,/-! p r e s s o r dapat dilakukan secara SIMD dengan menjalankan Algoritme 2 pada masing-masing prosessor (Becka dan Vajtersic 2002).
Vol. 15, No. 2, Mei 2004 - Majalah IPTEK
80
Algoritme 2 {Algoritme SVD blok-Jacobi P a r a l e l dengan P e m i l i h a n D i n a m i s )
2 Sisi
Algoritme 2 dijalankan pada tiap-tiap prosessor. Tiap prosessor mengerjakan 2 blok kolom yang berbeda
(i,j)=(2.me + \ + 2 )
berbeda. Blok kolom yang dikerjakan prosessor
U=I , V = L m
iJt
blok
Prosedur A l l G a t h e r ,
/;>5then
9
kolom
yang dikerjakan
dalam MPI adalah fungs
(PACS
2001),
melakuka
pengiriman hasil matrik X (bagian dari matrik U yang dikerjakan ke prosessor ke semua prosesso
tJ
lain. Tiap prosessor menerima matrik X dari semu prosessor lain disimpan di matrik sementara X Matrik XX digunakan untuk memperbaharui matri
u
lh
tt
X,j = I,m
dengan
prosessor lain.
While F(A, I) > € do if F ( S
MPI_Allgather
• Komputasi SVD pada subproblem Sy • menghasilkan Xydan Yy $VD(SJ-+X , Y • Perbaharui Blok Kolom forr=l t o / d o
A ketika memperbaharui blok baris.
(A , A , ) = (A„, A,).Y„ ({],,. UJ = f U , V„>.X„ (V Vtj) = (V„, V,j).Y end for else
p
end if • Kirim matrik A",, ke semua prosessor • dan terima sekumpulan matrik X ,„ pada array X X r
AllGatherGVj) -> XX(0 = ( X , r , s ) , t * 0 , \ , . . . , p - 1 rx
• Perbaharui Blok Baris A
\
for t = 1 to p do
Norm tiap subproblem disimpan pada array setiap usai perhitungan S V D subproblem nilai diperharui. Berdasarkan array W ditentukan su problem yang akan dikerjakan oleh masingmasi prosessor. Setelah itu, blok kolom yang dikerjak oleh prosessor dikirim ke prosessor lain sesu dengan reordering dan menerima blok kolom da prosessor lain yang merupakan blok kolom itera berikutnya. Proses pengiriman dan penerimaan ha dilakukan secara nonbloking agar menghind deadlock.
V J
end for update(W) ReOrderingComp(/J, FF, me) -> destl, dest2, tagl, tag2 • Copy blok yang akan dikirim • agar tidak mengganggu proses kirim dan terima
Kompleksitas Algoritme 2 dapat dihitu berdasarkan proses perkalian matrik, perhitung SVD pada subproblem dan ongkos unt reordering. Apabila matrik A merupakan mat bujur sangkar berukuran n dan dibuat matrik b berukuran / x I dengan / =2.p maka kompleksi komputasi dengan greedy dynamic reord adalah (Becka dan Vajtersic 2002):
copy (A„ U„ V„ i) A , U V r copy(^, Uj, V j , j ) ^ A j , Uj,Vj,j r
n
n
(
x
s
n
n
2
}
n — +P I P J 3
• Kirim blok row ke prosessor dest 1 dan dest 2 send { A U V r, destl, send (A , U , V , s, dest2,
TIME%%=npil
tagl) tagl)
n
s
• Terima blok row dari prosessor manapun recv (A„ U„ V„ i, 1) recv ( A U„ V„ i, I)
Dengan p adalah jumlah prosessor, n adalah dim matrik dan npil adalah banyaknya iterasi pada s prosessor.
h
end while end
Majalah IPTEK - Vol. 15, No. 2, Mei 2004
81
I E R C O B A A N D A N HASIL
tridiagonal adalah dalam rentang 0.94-1.40 (rata-rata
PERCOBAAN
1.40). Jika dilihat dari jenis matrik maka nilai rasio
2 diimplementasikan dengan MPI pada paralel kluster dengan spesifikasi tiap r adalah: prosessor intel pentium 450 MHz, sebesar 512 M H z dan jaringan menggunakan Ethernet yang dihubungkan dalam L A N . Ihan ihn dgemm di B L A S digunakan untuk pnalian matrik. Sedangkan, untuk melakukan S V D - . • : : :lem digunakan prosedur dgesvd.
ifltertinggi diperoleh untuk matrik tolosa, kemudian td matrik tridiagonal dan terakhir matrik random. Penurunan nilai off yang dihitung dengan persamaan (2) untuk per langkah iterasi pada masing-masing matrik dapat dilihat dalam Gambar 1. Gambar 2 menunjukkan trend kenaikan rasio seiring dengan
jumlah
prosessor
yang
dipakai
dalam
paralel. Hal ini disebabkan jumlah kemungki nan ftrcobaan dilakukan pada 3 jenis matrik yaitu rampat, matrik jarang dan matrik tridiagonal Matrik rampat dibangkitkan dari prosedur ada di L A P A C K yaitu d l a t m r . Matrik jarang matrik tolosa yang merupakan data dari yaitu Harwell-Boeing. Matrik tridiagonal diperoleh dari dikritisasi persamaan 2 2 al d fdx + x . dilakukan dengan dimensi matrik 200, » . 8 0 0 , 1000, 1200, 1400, 1600, -1800, dan Jnmlah prosessor untuk percbbaan algoritme adalah 2,3, dan 4. Toleransi yang digunakan untuk menetapkan e dan 8. Seluruh -i dilakukan dengan akurasi presisi double dkagan presisi mesin e ~ 1.11 x l O .
pasangan indek sebanding dengan jumlah prosessor yang dipakai. Oleh karena itu, pemilihan pasangan indek oleh algoritme
dinamis cenderung
lebih
menguntungkan dibanding dengan pasangan indek yang dipilih oleh algoritme statis pada jumlah prosessor yang banyak.
f
— Pina-iki Sis*:;
|
fc 21
0
M
i
< > it - i
3 1
3
, „ „
„ „
a
u
M
ktraci
(a)
- 1 6
Fterbandingan antara Algoritme Statis dan Algoritme Dinamis percobaan dengan menggunakan algoritme *ajikan pada Tabel 1. Sedangkan, hasil _ dtngan menggunakan algoritme dinamis pada Tabel 2. Algoritme statis pengurutan yang disebut chess (Golub dan Loan 1989). unjuk kerja antara algoritme Dinamis dapat ditunjukkan dengan rasio antara fcomputasi yang dibutuhkan oleh algoritme ) dan waktu komputasi yang dibutuhkan ! dinamis (td).
M
\ '
IS
I!
17
I?
}|
"
«
?r
Ki
ti
j>
r*
IT
M
Iterasi
(b)
a
0
t
- dengan matrik tolosa adalah dalam rentang
» !l
3
I'
»
19 21 » Derail
it 2;
2i 31
J3
(C)
(rata-rata 1.83), matrik random adalah lang 0.88-1.18 (rata-rata 1.03), dan matrik
Gambar l . Penurunan F(^,/) per langkah iterasi pada matrik tolosa (a), matrik random (b) dan matrik tridiagonal (c).
Vol. 15, No. 2, Mei 2004 - Majalah IPTEK
Tabel 1. Tabel konsumsi waktu dan banyak iterasi SVD-Jacobi Paralel menggunakan Algoritme Statis. Jumlah Prosessor 2
3
4
39
432.33
25
674.19
57
508.33
29
584.79
11
33
213.46
21
283.35
10
392.09
39
249.99
26
343.41
12
522.5
Dlatmr
58
302.09
30
305.16
11
379.57
Tolosa
33
101.47
21
135.82
10
209.03
Tridia
39
121.31
26
171.39
12
256.89
Dlatmr
43
111.48
28
141.77
11
172.93
Tolosa
33
42.42
21
52.7
10
72.62
Tridia
39
52.24
26
66.54
12
88.29
Dlatmr
58
67.37
28
58.26
11
60.11
Tolosa
33
13.55
21
16.12
10
19.68
Tridia
16.84
26
19.54
12
23.82
Dlatmr
22.2
28
17.9
11
17.25
Tolosa
33
1.89
21
2.05
10
2.56
Tridia
26
2.64
28
2.79
12
3.03
Dlatmr
52
2.-66
28
2.45
11
2.26
Tolosa
200
iterasi
t (detik)
iterasi
t (detik)
iterasi
t (detik)
Matrik
Dim
400
600
800
1000
1200
1400
1600
1800
2000
1242.39
Tolosa
899.64
Tridia
12
1101.32
Dlatmr
773.33
Tolosa
Tridia
1601.42
Tolosa
1444.64
Tridia
1592.05
Dlatmr
2289.24
Tolosa
2093.14
Tridia
2571.54
Dlatmr
3064.17
Tolosa
3040.56
Tridia
3709.62
Dlatmr
4090.74
Tridia
5010.52
Dlatmr
10 11 11 10 10 11 10 10 12 10 10 12 10
21
558.4
30
944.68 1017.46
25 21
856.37
30
1680.68
25
1830.48
21
1513.05
29
2820.95
24
2899.81
21
2517.78
29
3913.53
24
4036.48
21
3517.89
60 41
350.26 785.44 728.23
33 53 39 32
584.62
53
1328.13
39
1228.24
32
1006.72 1855.75
57 37
1550.67
32
1340.08 2704.45
57 38
2235
32
1920.03
Majalah IPTEK - Vol. 15, No. 2 , Mei 2 0 0 4
83
Tabel2. Tabel Konsumsi Waktu dan Banyak Iterasi SVD-Jacobi Paralel menggunakan Algoritme Dinamis. Jumlah Prosessor
Dim 200
400
600
800
1000
1200
1400
1600
1800
2000
Matrik
t (detik)
4
3
2
-
t (detik)
Iterasi
Iterasi
t (detik)
Iterasi
Tolosa
2.06
10
1.43
17
1.55
31
Dlatmr
3.11
12
2.64
26
2.22
38
Tridia
2.46
10
1.88
19
1.67
27
Tolosa
14.81
10
10.82
17
9.81
27
Dlatmr
24.18
12
20.98
27
15.55
37
Tridia
19.40
10.
15.85
21
10.52
25
Tolosa
46.5
9
34.91
17
29.63
26
Dlatmr
91.82
12
69.69
27
48.64
36
Tridia
74.77
10
50.56
20
30.74
24
Tolosa
132.18
9
80.92
16
59.85
23
Dlatmr
2-68.75
12
170.01
26
117.44
38
Tridia
222.98
10
129.31
20
74.56
24
Tolosa
249.10
9
149.19
15
117.9
23
Dlatmr
462.27
11
318.24
23
221.11
35
Tridia
405.23
10
248.53
18
152.94
24
Tolosa
604.31
9
271.69
14
174.65
20
Dlatmr
1126.64
12
673.25
25
366.48
33
Tridia
946.56
10
553.93
21
262.66
24
Tolosa
969.28
9
491.85
16
349.07
24
Diatmr
1802.81
12
995.95
24
644.62
35
Tridia
1499.16
10
847.18
25
447.44
24
Tolosa
1408.46
9
936.15
17
535.25
22
Dlatmr
2621.43
12
1810.38
25
1153.84
37
Tridia
2185.84
10
1430.89
20
812.40
25
Tolosa
2039.99
9
1229.42
13
738,09
23
Dlatmr
3877.19
12
3184.36
26
1501.73
35
Tridia
3100.02
10
2412.68
20
969.76
23
Tolosa
2766.34
9
2009.08
15
916.81
20
Dlatmr
5118.52
12
4236.61
25
1889.06
32
Tridia
4121.15
10
3310.71
20
1385.63
23
Vol. 15, No. 2, Mei 2004 - Majalah IPTEK
84
2.50
T
waktu yang digunakan untuk menunggu prosessor lain mengirim hasil SVD untuk memperbaharui blok
2.00
baris yaitu pemanggilan fungsi M P I A U g a t h e r . Re1 CO
-•-Tolosa - » - Random
1 CO
Tridiignral
n«n • o.co
2 Jurrlah
ts
Gambar 2. Rasio —
3
4
Proituor
berbanding dengan jumlah
prosessor.
5.2 Profiling Proses yang dilakukan oleh algoritme Blok S V D Jacobi paralel dengan pengurutan Dinamis dapat dibedakan menjadi 5 macam yaitu perkalian matrik (MM),
perhitungan
S V D (SVD),
komunikasi
(Comm), menunggu (Wait) dan pengurutan ulang (Reordering). M M adalah waktu yang digunakan untuk melakukan perkalian matrik yaitu pada saat memperbaharui
blok
matrik
A , U , dan V .
Perhitungan S V D adalah waktu yang digunakan lintuk mplnlrukan komputas'i SVD yaitu pemanggilan fungsi dgesvd adalah
waktu
pertukaran
yang
pada matrik Sij . Comm
dipakai
untuk
hasil S V D pada
melakukan
subproblem
antar
prosessor pada tiap langkah iterasi. Wait adalah
ordering adalah menjalani
waktu yang digunakan
algoritme
greedy
dalam
untuk
pemilihan
pasangan indek berikut. Tabel 3 adalah porsi waktu yang digunakan untuk menghitung S V D matrik Tolosa, Random dan Tridiagonal dengan dimensi matrik 1000 x 1000. Hasil pada Tabel 3 merupakan rata-rata semua prosessor untuk semua ukuran matrik. Perkalian matrik, S V D , komunikasi dan waktu tunggu tergantung dengan jumlah iterasi dan dimensi blok matrik. Jumlah iterasi semakin banyak sebanding dengan jumlah prosessor dan dimensi blok matrik berbanding terbalik dengan jumlah prosessor. Oleh karena jumlah prosessor yang digunakan hanya 2,3 dan 4 trend perkalian matrik, SVD, komunikasi dan waktu tunggu tidak berubah yaitu trend untuk perkalian matrik, komunikasi dan waktu tunggu adalah menaik. Sedangkan, S V D menurun. Pada prosessor 2,3 dan 4 belum ditemukan titik seimbang antara ukuran matrik dan jumlah iterasi sehingga mengakibatkan trend alokasi waktu tidak berubah.
5.3 Speed Up Speed Up dihitung berdasarkan perbandingan antara waktu terbaik algoritme sekuensial dan waktu yang dibutuhkan dengan algoritme paralel. Algoritme SVD Blok-Jacobi 2 sisi dengan penjadwalan
Tabel 3. Tabel Alokasi Waktu pada Algoritme Blok SVD-Jacobi Dinamis dengan dimensi matrik 1000 x 1000.
2
Tolosa
n Proc
Matrik
Random
Comm
SVD
MM 52.25%
46.24% 39.28%
36.00%
2
65.49%
4
57.29%
3
35.92%
2
54.64%
4
44.34%
3
Tridiagonal
54.12%
4
43.92%
3
28.97% 62.82% 53.25% 41.48% 62.94% 53.54% 41.94%
0.93% 2.16% 3.58% 0.74% 1.59% 2.60% 0.71% 1.63% 3.04%
Wait 0.18% 0.47% 0.77% 0.14% 0.35% 0.61% 0.14% 0.37% 0.58%
Reordering 0.08%
Sisa 0.32% 0.60%
0.20%
0.84%
0.35% 0.06%
0.23%
0.15% 0.25% 0.06% 0.15% 0.26%
0.32% 0.43% • 0.23% 0.40% 0.58%
Majalah IPTEK - Vol. 15, No. 2, Mei 2004
85
dinamis dijalankan pada prosessor tunggal dengan b l o c k i n g f a c t o r . 4,6, dan 8. Waktu yang dibutuhkan untuk B l o c k i n g f a c t o r 4 digunakan untuk pembanding dengan jumlah prosessor 2, 6 untuk jumlah prosessor 3 dan 8 untuk jumlah prosessor 4. Gambar 3 menunjukkan speed up matrik Tolosa tidak bertambah secara signifikan seiring dengan jumlah prosessor yang dipakai. Rinciannya adalah sebagai berikut: Pada jumlah prosessor 2 rata-rata speed up adalah 1.87, dengan rentang speed up antara 1.54 sampai dengan 1.95. Speed up cenderung stabil untuk dimensi matrik > 600. Trend berbeda ditunjukkan oleh jumlah prosessor 3. Ratarata speed up pada jumlah prosessor 3 adalah 1.99 dan dalam rentang antara 1.69 sampai dengan.2.45. Speed up pada jumlah prosessor 3 menurun seiring dengan dimensi matrik dan stabil pada kisaran 2.00. Hal yang sama terjadi pada jumlah prosessor 4 dengan ratarata 2.11 dan dalam rentang 1.94 2.72. Speed up cenderung menurun seiring dengan dimensi matrik dan stabil untuk d i m e n s i matrik > 1400. Speed up pada matrik Tolosa tidak bertambah secara signifikan dibandingkan jumlah prosessor disebabkan oleh nilai norm blok matrik Tolosa. Norm blok matrik yang terbesar jauh lebih besar dibandingkan dengan norm blok matrik lainnya.
dan dalam rentang 2.08-2.29. Pada jumlah prosessor 3 diperoleh speed
up yang lebih tinggi daripada
dengan 2 prosessor yaitu 2.88 dan dalam rentang 2.60-3.32. Rata-rata speed
up pada jumlah prosessor
4 adalah tertinggi yaitu: 4.11 dan dalam rentang 3.65-4.50. E CD •
4.E0 400 3.60
-•-2
§3.03 2.60
.......3
1 CO
-*-4
1.60 1.00 0.60 ceo 230 (03 600 600 10X 1203 I 4X
1603 '800 2X3
Dimtnsi Matrik
Gambar 4. Speed
Up Algoritme Blok SVD-Jacobi
Paralel dinamis untuk Matrik Random. Gambar 5 menunjukkan Speed Tridiagonal. Trend speed
Up untuk matrik
up matrik tridiagonal
cenderung sama dengan trend, speed up matrik random. Speed
up bertambah seiring dengan jumlah
prosessor yang digunakan. Pada jumlah prosessor 2 rata-rata speed 2.07.
up adalah 1.97, dalam rentang 1.94-
Pada jumlah prosessor 3 rata-rata speed
up
adalah 2.51, dalam rentang 2.32-2.77. Speed
up
tertinggi diperoleh pada jumlah prosessor 4 yaitu dengan rata-rata 3.97, dalam rentang 3.41-4.50.
200 400
SCO
800 1X0 12X 1403 1600 18X 2X0
Dimensi Matrik
Gambar 3. Speed
Up Algoritme Blok SVD-Jacobi
Paralel dinamis untuk Matrik tolosa. Gambar 4 menunjukkan Speed
Up untuk matrik
Random bertambah sebanding dengan pertambahan 3TO$e§§GF. Speed
Up telah diperoleh pada jumlah
ICC
400
600
800 1000 1200 MI
15C0 18X 2X0
Dimensi Matrix
Gambar 5. Speed Up Algoritme Blok SVD-Jacobi Paralel dinamis untuk Matrik Tridiagonal.
prosessor 2,3 dan 4 dan pada dimensi matrik > 200. lata-rata speed
up dengan 2 prosessor adalah 2.14
Vol. 15, No. 2, Mei 2004 - Majalah IPTEK
86
5.4 Akurasi Akurasi algoritme Blok SVD-Jacobi Dinamis dinilai dan perbedaan antara nilai singular yang ditemukan oleh algoritme Blok SVD-Jacobi Dinamis dan nilai singular yang ditemukan oleh dgesvd pada paket L A P A C K dan perbedaan antara matrik A dan matrik yang ditemukan oleh U I V , matrik U , V dan I merupakan matrik-matrik yang diperoleh dari S V D dengan algoritme Blok-Jacobi dengan pengurutan dinamis. T
Selisih nilai singular antara nilai yang ditemukan oleh algoritme Blok-Jacobi dengan
penjadwalan
dinamis dan nilai yang ditemukan oleh prosedur disajikan
dalam
Tabel
4. Tabel
4
didapatkan matrik A
maka dapat dihitung nor A
selisih matrik A (matrik asli) dengan matrik A yait ^-^|| . F
Tabel 5 menunjukan
nilai
J|y4-y4J|
sangat kecil sehingga akurasi algoritme blok-Jacob dengan
penjadwalan
dinamik mendekati
mesin yaitu akurasi double floating
akuras
point.
6. SIMPULAN Algoritme
SVD
penjadwalan
blok-Jacobi
dinamik
dapat
2
sisi
denga
diimplementasika
lingkungan klusteF keffipiitef.
dalam
Percobaa
penjadwalan dinamis lebih tinggi daripada speed
ke-10. Untuk matrik random sampai dengan digit
bahwa secara umum speed
matrik tolosa identik sampai dengan digit desimal
statis.
algoritme Blok-Jacobi dinamik dan L A P A C K untuk
algoritme paralel dengan penjadwalan dinamis da
menunjukkan nilai singular yang ditemukan oleh
menunjukkan bahwa speed
agesva
up diperoleh denga
Selain itu percobaan
juga
menunjukka
up algoritme deng
algoritme dengan penjadwalan statis.
ke-15. Untuk matrik tridiagonal sampai dengan digit kel2. Hal ini menunjukkan akurasi nilai singular yang ditemukan
algoritme
Blok-Jacobi
dengan
penjadwalan dinamis relatif sama dengan akurasi yang dimiliki oleh prosedur dgesvd A
Riln matrik orthogonal
di L A P A C K .
A
U, V dan matrik diagonal
A
dinamik dikalikan sehingga
dengan penjadwalan
oleh
Zyang
Tabel 4
ditemukan
algoritme
blok-Jacobi
Speed up dan perbandingan unjuk kerja algorit dinamis dan algoritme statis tergantung dari kondi norm blok matrik. Hal ini ditunjukkan oleh mat tolosa yang memiliki norm blok matrik sangat tid merata. Matrik Tolosa memiliki speed
up yang tid
tergantung dengan jumlah prosessor dan kine algoritme dinamis jauh lebih baik daripada kine algoritme statis. Hal yang sebaliknya ditunjukk oleh matrik Random dan matrik Tridiagonal.
Rata-rata Selisih antara nilai singular yang ditemukan algoritme Blok-Jacobi dinamis dan j J u: „: i n n r w innn
2 2.58 x 10-'" 7.25 x 10"" 1.61 x l O "
Matrik Tolosa Random Tridiagonal
2
Tabel 5. Nilai Li - A ^
F
lumlah Prnsessor 3 3.18x10-"' 9.11 x 1 0 " 1.80x10-"
4 4.31 x 10-'" 9.60 x 1 0 " 2.19 x 10" 2
untuk dimensi matrik 1000 x 1000. lumlah Prosessor 3 1.11 xlO"' 1.65 x 10" 3.53 x 10""
2 9.11 x 10"'" 1.32x10" 3.09x10'"
Matrik Tolosa Random Tridiagonal
4 1.28 x 10"" 1.75 x 10" 3.58 x 10""
7
2
2
Majalah 1PTEK - Vol. 15, No. 2, Mei 2004
87
DAFTAR ACUAN
Heath, M.T. (2002), Scientific Computing : A n Introductory Survey, McGraw Hill, New
Anderson, J.D.E. dan Dimmel, J. (1999), L A P A C K User Guide, SIAM Publishing. Becka, G.O.M. dan Vajtersic, M . (2002), D y n a m i c O r d e r i n g for a P a r a l l e l Block-Jacobi SVD A l g o r i t h m , Parallel Computing, 28, pp. 243-262. Golub,
G . H . dan
Loan, C.F. (1989),
Matrix
York, USA, 2 edition. nd
Luk,
F. dan Park, H . (1989), O n E q u i v a l a n c e and Convergence of P a r a l l e l Jacobi SVD A l g o r i t h m , I E E E Trans on Computation, 38, pp. 806-811.
PACS (2001), Introduction to MPI,
NCSA.
Computation, The Jhon Hopkins University Press, Baltimore, Maryland USA.
Vol. 15, No. 2, Mei 2004 - Majalah IPTEK
