Analisa Probabilistik Algoritma Routing pada Jaringan Hypercube Zuherman Rustam JurusanMatematika Universitas Indonesia Depok 16424. id E-mail :
[email protected].
Abstrak Algoritma routing pada suatu jaringan interkoneksi adalah suatu mekanisme untuk menentukan rute yang harus dilalui oleh suatu packet yang berasal dari suatu node sumber ke node destinasi pada jaringan tersebut.Tujuanutama dari algoritma routing adalah memilih rute , yang yang menghubungknn node origin dengan node destination, dengan total delay setiap packet minimal. Makalah ini membahashasil analisa probabilistic tentang dua buah algoritma routing yaitu Algoritma Deterministik Bit Fixing dan Algoritma Randomized Routing. Dengan menggunaknn teorema Chernolf dapat diketahui probabilitas suatu packet mencapai node tujuan. 1.
Pendahuluan
Komputer paralel terdiri dari sejumlah prosesyang saling berinteraksi. Komunikasi antara prossesordilakukan melalui interconnection network, sedangkaninformasi yang dikirimkan antar prosessor dapat berupa sekumpulan data binary , yan9 dinamakan dengan packet. Untuk merepresentasikaninteraksi antar prosessordigunakan suatu graph atau topology. Node dari graph tersebut menunjukkan prosessor sedangkan edge yang menghubungkan sepasang node menunjukkan adanya jalur komunikasi antara kedua prosessor.Topologi atau Graph yang biasa digunakan antara lain : Linear Array , Hypercube , Mesh dan Fat Tree. Topologi Linear Array merupakantopologi yang sederhanadan banyak digunakan untuk komputer paralel denganjumlah prosesoryang sedikit. Generasipertama komputer paralel ( Intel iPSC dan CM2 ) menggunakan topologi hypercube.Generasiberikutnya seperti Intel Paragon dan iWrap menggunakantopologi mesh.lBertsekas,I 989] Jaringan Linear Array , Hypercube , Mesh dan Fat Tree digolongkan kedalam static interconnextion nehvorl<s,hal ini disebabkankarena prosessor dihubungkan satu samalain dengan menggunakanfixed connection. Algoritma Routing unfuk suatu Jaringan Interkoneksi adalah suatu mekanisme untuk menentukan rute / lintasan yang harus dilalui oleh suat: packel dari suatu node sumber ke node destinasi.Tujuan utama algoritma routing adalah memilih rute pada jaringan sedemikian sehingga total delay untuk setiap paket minimum. Dalam makalah ini akan dibahas dua algoritma routing yaitu Bit-Fixing Routing dan RandomizedRouting pada jaringan Hypercube. Sistimatika makalah ini sebagai berikut : bagian kedua membahasdefinisi dan teorema dasar yang berkaitan dengan Topologi Hypercube , bagian ketiga membahastentang algoritma Bit-Fixing, bagian terakhir dari makalah ini membahasalgoritma RandomizedRouting. 2.
Topologi Hypercube Suatu jaringan hypercube berdemensi n ( disebut juga dengan n
cuhe), terdiri dari
N =2n node. Setiap nodeber-degree n , denganperkataan lain setiap node terhubung dengan n buah node lainnya. . Setiap node mempunyai n bit address . Address dari node ke f dinyatakan dalambentuk (i1,i2,...,in1 {0,1}n . Edge e menghubungkansepasangnodei dan i jika jarak Hamming antara(i1,i2,...,irldan(j1, j2,..., jnl bernilai I . Topologi hypercubeditinjau berdasarkankomputasi lebih baik dibandingkan denganmesh, hal ini ditandai dengan fakta bahwa komputasi yang dikerjakan dengan satu langkah di mesh dapat dikerjakandengansatu langkahpadahypercube,sedangkankebalikannya tidak berlaku.
Proceedings Komputer dan sistem Auditorium Universitas Gunadarma" Jakart4 2l -22
A-106
Definisi I : Misalkan diberikan suatujaringan dengan IV node , dimana setiap node memuatil pdcket yang harus dikirimkan ke suatunodedestinasi, jika node destinasi membcfl stratupermutasi rr:JV -lV , dari ffnode maka masalahrouting dinamakaamaseff Permutasi Routing. Algoritma yang digunakan untuk menyclesaikan masalah I dinamakanalgortimaPermutasiRouting. Definisi2 : Setiap algoritma routing , dimanarute setiappacket ditentukanberdasarkanhanyapa& address dari node destinasi , dinamakanalgorinna oblivious-routing. Algorituia iti menggunakannrte tetapuntuk setiappasangnodesumberdan destinasi.Padanodeantan, keputusanyang harus dilakukan adalah memilih rute yang harus dilalui snatrrtpackct, berdasarkan address node destinasi. Teorema 3 : [Motwani et all "I997I Kompleksitas algortima PermutasiRouting pada jaringan dengan IV node oberdegree n,
tN adalaho(i;). 3.
Algoritma
Bit-Fking
Routing
Algoritma Bit-Fixing merupakan algoritma oblivious-routing deterministik. Pada node intermediate, keputusan routing untuk suatupacket, hanya didasarkan pada adrress dari node destinasi.Misalkan suatu packet akan dikirimkan dari node sumber bepaddress rr(i) ke node destinasi ber-address q(i) melalui node intermediate ber-address o(i). Fertama sekali harus dibandingkan address n(i) dengan o(i),dimulai dari kiri ke kanan, dan ditentukan di posisi mana kedua address tersebut berbeda. Selanjutnya packet dikirimkan ke node beraddress q(i) dimana 4{i) dengan o(i) hanya berbedapadaposisi tersebut. Misalkan diberikan jaringan Hypercube berdimensi n , terdiri dari IV=2n
node dan
au"operator . I merupakan operator konkatenasi. Dan dimisalkan setiap node di hypercube tersebut dinyatakan dalam bentuk (i.l) dan setiap node merupakan elemen berbeda dari matriks A , berukuran setiap node berdegree n ( genap).Misalkan i dan j bit-string dengan panjang
nn
22 x22 . Berdasarkan data-data tersebut maka menghitung ftanspose dari matriks I sama artinya dengan proses routing setiap element ke node destinasi yang berbeda sedemikian sehingggaelement yang disimpan di node (t. j) di kirimkan ke node (j. il. Karena node destinasi membentuk suatu permutasi maka masalah ini dinamakan masalah permutasi routing , atau transposepermutasi. Permutasi diatas diperlukan untuk membahas kompleksitas dari algorihna bit-fixing algorithm untuk Hypercube. Dengan menggunakan teorema 3 akan menghasilkan corollary berikut ini : Corallarv 4 : Kompleksitas dari algortima Bit-Fixing-routing pada jaringan hypercube dengan N node , 1,
berdegreen adalah O(i;)
.
Bukti : n
t, i
routing elememtyang disimpanpadanode memerlukan 10,1,...,2, 1) permutasitranspose
A-t07
Analisa Probabilistik Algoritma Routing pada Jaringan Hyperabe
n
surrber(i' j) ke nodedestinasi U'il .Misalkanuntuk j = 0 , ( terdapate z buah node dengan j = 0 ) , I 10,1,...2; 1) dilakukan routing untuk elementyang disimpanpada node sumber (i.0) ke nodedestinasi (0.f) denganmenggunakan algoritrnaBit-Fixing. Setiapelement harus n t2n
bilanganganjil terdapur melaluinode (0.0). Jika f merupakan T
node dari 22node yang n
Eniliki
transposepermutasiterdapat address(1.0). Sehinggaberdasarkan
2V 2
element yang
node (1o 0) dan (0 o 0). ekan melintasiedge, yangmenghubungkan Karena hanya ada sebuah elemen pada saat yang bersamaanyang dapat menggunakan edge yang cZ liarna , maka hal ini memrlukan
]-
langkah
tr
ablzn ) langkah. 4.
Algoritma
Sehinggapermutasi transposememerlukan
Randomized-Routing
Untuk menylesaikan masalahpermutasirouting pada hypercube ,Les Valiant membentuk algoritma randomized routing , untuk mengirimkan suatv packer . Algoritma Valiant tersebut terdiri dari dua phase yaitu:I Valliant ,1982] Padasetiapdipilih secararandom , node intermediateo(f) dari {1,2,...,NI dan kirimkan packet v; dari i ke o(i) denganmenggunakanBit-Fixing Routing 2. Ilka packet telah sampai di node antara o(i) , kirimkan packet tersebut dari node intermediate o(i) ke node destinasi n(i) denganmenggunakanBit-Fixing Routing l.
Lemma 5 : Jika algoritma Bit-Fixing digunakan untuk mengirimkan packet vi dari i ke o(i) dan mengirimkan packet v i dari j ke offl maka rute keduanya tidak akan melintasi rute yang samajika akan keduanya sudahberpisah. Bukti : Misalkan k dan / masing-masing menunjukkan node dimana kedua path berpisah dan bergabung. Karena rute pada bitfixing untuk masing-masingpacket vi danpacket vi tergantung hanya padaaddress dari node k dan nodel makakedua packet tersbut harus melaui rute yang sama.E Selanjutnya akan dibahas tentang kompleksitas algoritma Randomized-Routing.Misalkan pi = (er ,e2t...te1) lintasanyang dilalui oleh packet v1 dan didefinisikan himpunan S sebgai berikut: S = {v; I i j,v i melintasi paling sedikit sebuahedgedi p1 = (e1,e2,...,ep1). Untuk suatupacket v , keterlambatan(lag\ daipacket v relatif terhadap p1 dinyatakan sebagai f - j . Keterlambatan terjadi jika pada saat t , packet tersebutsudah siap untuk melintasi edge er-. Lemma 6: Batas atas keterlambatanpacket v; adalah
ProceedingsKomputer dan sistem Intelejen(KOMMIT2002) Auditorium Univsrsitas Gunadarma,Jakarta,2l -zzAgustus 2002
A - 10 8
Bukti : Setiappacket yangmeninggalkanlintasan p, = (e1,e2,...,er) denganlag sebesarl, akan lag dari packet tersebut akan dikenakan penalti sebesar satu satuan , sehingga lag dari packet f/saatterakhir suafiipacketberadadihimpunan S dengan tersebutmenjadil+l.Misalkan jumlah sebesar I. Karena keterlambatan langkah hingga maka adr packet yang akan menggunakan errpadasaatf/sedemikainsehinggat' - j':/. Karenapaclcetv akanmenggunakanedge ert dan pada saat yang bersamaansuatttpacket w sedangberada di edge €rr, maka dua terdapat dua pilihan untukpacket w yaituharus meninggalkan p, pada saat tt atau w menunggu untuk melintasi edge e *, pada saat tl + 1 . Hal ini akan mengakibatkan beberapapac,tel harus melintasi ,t 5, v ert*,rpadasaatf/ +1.Hal inibertentangandenganmaksimalitasdariL Berdasarkan,lemma tidak akan pernah kembali ke lintasan p; . Sehingga setiappacket yang berada di S paling sedikit tr mengalamipenalti paling sedikit safu kali. Selanjutnyaakan dibahas ekspekati waktu untuk mentransferseluruhpacket padajaringan Hypercube. ll Misalkan didefinisikan variabel random H,,t = 1 ^
,jlkaeep,Api
' LO , jika tidakdemikian
dan
d; menunjukkan total delay yang dialami oleh peicket v;. Berdasarkan lemma 6, akm
-r-nn bertaku d,
Misalkanf(e) variabelrandomyangmenunjukkanbanyaknyaruteyangmelintasiedgee . Jika pi=(e1te2,...,€k) **u
ia j =t
Karenasetiaprute harusmelaluipaling
r
sedikit sebuahedge di pi =(et1e21...re1), misalkanedge tersebutadalah el.Karena edge e; adalahedge yang dilintasi oleh setiap rute tersebutuntuk membawa suafttpackel anggota S maka k'k
El>H uJ
(1 )
j =l
Karena edge pada Hypercube adalah simetris EIT(e,)l=
e1 dan
em berlabq
E[T(e^)]. Jumlahedge pada digraphadalah lVn maka ekspektasipanjang suatun&
nNn dan ekspektasipanjang total rute adalah . Denean perkataanlain , , p . Denganmenggunakanpersamaan(1) , maka akan berlaku :
adalah b
, maka untuk
nrtn,t=+ =:
1 E[I(e)]=7 "
(2)
i=t22 Karena rute untuk statu packer dipilih bebas secararandom.Untuk suatu nilai i , i JH4 merupakan percobaan Poison sehingga untuk menghitung batas-batasprobabilistik dari Hil dapatdigunankanTeorema Chernoff , yaitu TeoremaChernoff :
JikaX =2,X,
dimanaX, suatumenunjukkan outcomedaripercobaan bebasPoissm,
A-109
Analisa Probabilistik Algoritma Routing pada JaringanHypercube
, dimana5
maka berlakuPr[X> (l+6)p).[*fu)"
konstantadan
p = E[x]=L,P, Selanjutnyajika d >2e-l
maka akanberlaku:
j.,rr]' < pr[x > (r+ 5)p)=( \zr - 11;rtr*ar .. "' -=[|.rr ( r * "'-i,rrlett+ar '[(r* 5 ) " 0 il" u ) ) (I+ 6)p = 6n maka Vt1fn, Denganmenetapkan
> 6n)< 2*6' -
j=l
Karena total banyaknya packet adalah 2n maka probabilitas , bahwa suatu delay yang 6n. Berdasarkan analisa diatas maka akan terjadi lebih besar 6n , adalah lebih kecil dari 2n x2 dihasilkanproposisiberikut ini : Proposisi7 : Dengan probabilitas kurang dari 1-2-5n , suatu packet vi dalam 7n langkah atau kurang dari itu.
akan mencapai node o(i)
Phasekedua pada algoritma Randomized-RoutingValliant identik dengan phasepertama jika node sumber dan node destinasidipertukarkan. Sehinggaanalisadiatasjuga berlaku untuk phasekedua. Dengan dilakukan pertukaranperan dari node source dan node destinasi maka dengan probabilitas L lebih kecil dari 2-' ==-l-, suatu paket gagal untuk mencapainode destinasi pada salah satu phase tersebut, kurang dari 2-so*1.Atau dapat dinyatakan dinyatakandalam proposisi dibawah ini : Proposisi8: Dengan probabilitas lebih kecil dari I - { , ,uutu p acket tidakakan mencapai destinasinya N. itu. dari kurang langkah atau dalam 14n 5. tll. l2l. l3l.
Daftar Pustaka D.P. Bertsekasand J.N. Tsitsiklis , Parallel and Distributed Computation, PrenticeHall Inc, 1989. R.J Motwani et all , RandomizedApproximation Algorithms in Combinatorial Optimizatiott , PWS, 1997 L.G. Valliant , A Schemefor Fast Parallel Communication, SIAM J. Computations, Vol I l:350-361,1982
