PROCEEDINGS ITB, Vol.25, No. 1, 1992
I
EKSEKUSI PARALEL OPERATOR REI.ASI DARI TRANSAKSI PADA BASIS DATA MODEL REI.ASI
Dr. lng. lr. Benhard Sitohang*
SARI Waktu tanggap SMBDR dicoba diperbaiki dengan mengantisipasi eksekusi seluruh operator relasi dari transaksi secara paralel. Pada makalah ini, drjelaskan pendekatanyang memungkinkan eksekusi secara paralel (berupa usulan pendefinisian operator bebas), ujicoba, serta analisis untuk mengetahuisejauhmana perbaikantersebutdapat dicapai. Hasil uji-coba pada sistem komputer PDP-lll44, sistem operasi Xenix, digunakan mengidentifikasikendala-kendalayang berperandalam menentukanperbaikan termaksud. Waktu tanggapbeberapatransaksiuji-cobayang dieksekusisecaraparalelternyatalebih baik daripadaeksekusisecarasekuensial(reduksi : 11,36 %).Beberapatransaksiuji coba lainnya kurang memberikanhasil yang mendukunghipotesa(reduksi: -60,87%).
ABSTRACT Improvement of RDBMS response-timewas tried by anticipating to execute all relational operators of the transaction as a parallel process. This paper explains an approach which enables parallel execution (by defining "free operators"), te,st-caseand analysis to know how far the improvementcan be attained.Test-caseresult on PDP-IIl44, underXenix, was used to identify others constraintswhich plays role to the improvement. Response-time of test-casewich parallel-execution performed better then sequential-execution(reduction : 11.,36Vo).Others test-casetransactionsdon't present satisfying result to the hypotheses(reduction : -6O,87Vo).
I-ABORATORIUMBASISDATA & SISTEMMANAJEMENINFORMASI Jurusan TeknikInformatika, FTIJTB,Jl. Ganesa No.l0 - Bandune 40132
2
pnocenorNcsITB,vol.2s, No.i, i992
I.
PENDAHULUAN
I.I.
WAKTU TANGGAP SMBDR
Waktu tanggap (time response) dari Sistem Manajemen Basis Data Relasional [SMBDR] relatif lambat. Bahkan lebih lambat lagi, bila SMBDR digunakanoleh beberapa pcmakai sekaligus (multi-usen). Degradasi waktu tanggap tersebut,sebagai akibat dari ketidak sesuaian antara karakteristik SMIIDR dcngan sistem komputer yang umum digunakan. Beberapaprerbcdaankarakteristik tersebut,adalah : l.
Konsep proses pada prosesor (termasuk mikro komputcr) didasarkan pada operasi numerik, yang biasa discbut sebagai"Numerical Processor".Pada sisi lain, SMBDR melakukan operasi teks, dapat disebut sebagai"Text Processor".Sebagaiakibat dari pcrbedzranini, operasi pada SMBDR tidak dikenal scbagai operasi primitif. Dengan dcmikian operasiteks harusterlebihdahuluditransformasimenjadioperasinumerik.
2.
Metoda akses (pencarian)memori sekunderdan memori utama tidak didasarkanatas semantik dari data, tetapi dilakukan dengan menggunakanalamat llsik data. Hal ini menimbulkankesulitanpada aksesdata pada memori, yang selanjutnyaberakibatpada opcrasiMasukan/ Keluaranyangrelatifdominan.
1.2. USAIIA UNTUK MEMPERBAIKI
WAKTU TANGGAP SMBDR
Beberapa penelitian yang sedang dilaksanakan (merupakan topik penelitian yang dominan saatini dalam mpek Basis Data, disampingSistemManajemenBasis Data Terdistribusi), dimaksudkanuntuk memperbaikikedua kelemahantersebutdiatin. Beberapaalternatif pendekatanyang sedangdilakukanadalahpenerapanISTA 88] : 1.
IntelLigentSecondaryStorageDevice Contoh: CASSM, RAP, RARES
2.
Data lJaseFilter on VO channel Contoh.' CAPS, SURE, VERSO
3.
Multi procassorData Basc Computer Contoh; MICRONET. XDMS. EDC
4.
Tcxt Proce.ssors Contoh ; GESCAN, EURITKA
-5. AssociativeMemory System Contoh: LOGIC MEMORY. ASP. STARAN
PROCEEDINGS ITB, Vol. 25, No. 1, 1992
I3.
3
IIIPOTESA DASAR
Sesuai dengan prinsip dan konsep basis data model relasi, pemrosesan transaksi dalambentuk deretan(strukturpohon) dilaksanakandenganterlebihdahulu menjabarkannya produk kartasian,join, quotient, projection, selection, dan binary: oi)erratorrelasi (unary : join, adanya beberapaoperatoryang tidak pengurangan, interseksi). Dengan union, natural pada operator relasi daun struktur pohon),dibuat langsung (mis.: saling bergantungansecara berikut : satu hipotesasebagai operator relasi dari traksaksi dapat dieksekusi secara paralel (paralel processing), jika setiap operator relasi dari transaksi didefinisikan sebagaisatu proses.Dampak positif yang dapat diharapkan,adalah perbaikanwaktu tanggap (time response)dari eksekusi transaksi termaksud[SIT 85]. Tergantungdari struktur transaksi,beberapa operator(sebagaiterjemahandari transaksi)dapatdieksekusisecaratidak bergantungan. Dida;arkan pada hipotesaini, semua operatordari satu transaksi(khususnyaoperator yang tidak saling bergantungan)dapat dicksckusi secara paralel dengan memanfaatkan sistem operasi multi-programming, atau lebih baik lagi, dengan sistem komputer yang dibangundenganpemrosesbanyak(multi processor). I.4,
ALTERNATIF
PERBAIKAN & KRITERIA
I.AIN
Uji-coba dan analisistelah dilaksanakan,yang dimaksudkanuntuk lebih memperbaiki waktu tanggap (sebagai objektif akhir), yang didasarkanatas hipotesa tersebut diatas. Aktifitas awal yang telah dilakukan,adalahmendefinisikanketidak tergantunganantaraoperator relasi pada transaksi (untuk itu, didefinisikan operator bebas, kelompok operator bebas dan derajat kebetrasan),dan kemudian mencoba(dengan implementasi)eksekusi secara paralel semua operator yang tidak bergantungan (operator bebas), dengan memanfaatkansistem operasi multi programming. Hasil dari penelitian tersebut adalah merupakanpokok bahasanpadatulisanini. Dengan hasil positif yang didapatkan dari penelitian tersebut diatas, maka prinsip eksekusiparalelyang dimaksudkanjuga diperluas,denganmenerapkankonsepmulti processor yang dibangun dari mikro komputer (penelitian lanjutan, yang tidak dibahas dalam tulisan ini). Untuk pendekatanterakhir ini, dilakukan dengan mengantisipasikriteria tambahanyang dititik beratkandari faktor biaya, yaitu : Menggunakan perangkat keras yang sudah umum dikenal, dan dapat digunakan dengan investasiyang relatif murah. Sebagai kesimpulan, akan dijelaskan hasil dan kendala yang dihadapi, beserta evaluasi lebih lanjut. untuk pengembangan
4
II.
pnocanowcslTB, vol.25,No.I, 192
TRANSAKSI
PADA BASIS DATA
Transaksipada ba;is data adalahmerupakanpcnjabarandari kebutuhanakan pengakscsan basis data. Transaksi bia;anya dijabarkan dalam sintaks tertentu (tcrgantung dari SMBD), dan diaktifkan secarasendiri,ataudiintcgrasikandalam bahasapemrograman(host language). Beberapasintakstransaksipada SMBDR yang sudahdikenal [ULI- 88], antaralain A1gcbric languagc,Structurc Qucry l-anguagci SQL (pada saatini seqrra dc-facto dianggap sebagaistandarduntuk klassifikaii non-procedurallanguage),Query By Lxample IQBEI, QUEry l-anguage(QUEL), dll. Kescluruhansintaksyang discbutkandiatas,sccaraprinsip menekankankarakteristik"user-friendly",dan sccarakcseluruhandapatdianggapsama,,jika dilihat dari sisi pemrosesan s€caraintemal padaSMBDR yang dimaksudkan. Sebagaimanadisebutkandiatis, perbedaanhanyaterletakpadasintaks,kata kunci yang digunakan,cara penjabaranketrutuhan(SQL, QUEL, dil. rlengankalimat, scdangkanQIJI: dengantabel, dan Algebric l-anguagedenganmengunakansimbol operatorrclasi),dan lainlain perbedaan,yang pada dasamyadimaksudkanuntuk lebih memberikankemudahanbagi pemakai.Scluruhsintaksyang disebutkandiatastermasukdalam kelompoknon procedural.
III. PENJAI}ARANTRANSAKSIDENGAN OPERATORITEI.ASI Pada pemmsesannya,seluruh sintaks yang disebutkan terdahulu [sccara intcmal] dijabarkan dalam bentuk struktur pohon dari operator relasi untuk transaksi, dengan kodifikasi yang disesuikandengankebutuhanproses. Berikut ini adalah contoh penjabarannya,sedangkanuntuk mendukung pemahaman terhadapstruturpohon,maka deskripsibasisdatayang digunakansebagaicontoh,dijelaskan padal.ampiran-1. Contoh-l: SQL :
SELECT SNAME, ITEM, PRICE FROM SUPPLIERS,ORDERS WHERE NAME ='Ali Baba'AND SUPPLIERS.ITEM= ORDERS.I.|LM
Arti :
Tuliskan semuaSNAME, ITEM & PRICE dari setiap produk yang dipesanoleh pemesanbemama'Ali Baba'.
PenjabarandenganstrukturpohonoperatorrelasiadalahsepertipadaGambar-l. Contoh-2: SQL :
SELECT MEMBER_CODE, NAME FROM MEMBERS WIfiRE 10 <= SELECT SUM(QUANNTD FROM ORDERS WHERE MEMBER CODE = MEMBERS
PROCEEDINGS ITB, Vol.25, No. 1, 1992
5
Tuliskan semua MEMBER_CODE dan NAME dari pemesan,yang mempunyai pesananlebih besaratausamadengan10 unit.
Arti:
PenjabarandenganstrukturpohonoperatorrelasiadalahsepertipadaGambar-2.
S N A M E ,I T E M ,P R I C E
Atributhasil
projeksi
op. relasi
equtlotn ITEM = ITEM
+-------+
I
op. relasi
------+
I
seleksi N A M E= ' A l i B a b a '
ORDERS
SUPPLIERS
op. relasi
relasi
Gambar-1 StrukturPohonTransaksiContoh-1
IV. OPERATORBEBAS,KELOMPOK OPERATORBEBASSERTA DER,dIAT KEBEBASAN Iv.l. OPERATORBEBAS[SrT85] -
Operator bebas (pengertian bebas adalah relatif terhadap operator relasi lainnya dalam satu transaksi)adalah operator relasi, dimana hasil (output) dan masukan (input) dari operatortermaksudtidak menentukaneksekusidari operatorlainnya.
Pada Gambar-2, operator projeksi 03 disebut sebagai operator bebas, relatif terhadap 04 maupun05.
6
pnocnnolNcs ITB, vot.25,No.1, 1992
IV.2. KELOMPOK OPERATORtsEBAStItUT 871 operator - Kelompok operator trebasadalahmerupakan kumpulandari beberapa sesama oleh dipenuhi dimanadefinisiOperator bebas relasipadasatutransaksi, rclasitersebut. oDerator
M E M B E R - C O D EN, A M E
(olj
ievel - 1
pro.jeksi
level - 2
(04 equi-join M E M B E R _ C O D=EM E M B E R _ C O D E
(03) projeksi C O D EN, A M E MEMBER
(04) Projeksi M E M B E RC O D E
level- 3
(05) seleksi
level- 4
>= 10 suM (QUANTITY)
l e v e-l 5 . . .
SUM
fungsi
OUANTIry
MEMBER
ORDERS
Gambar-2 StrukturPohonTransaksiContoh-2
relasi
PROCEEDINGS ITB, Vot.25, No. 1, 1992
7
PadaGambar-2,maka kumpulanoperatorrelasi03 dan 04 adalahsatukelompok operator bebas.Sedangkan03 dan 05 adalahkelompok operatorbebaslain. Dengan demikian, pada Contoh-2, terdapatdua kelompok operatorbebas.Untuk lebih mempermudahpemah:riran, akan digunakan contoh transaksi teoritis, dengan struktur pohon seperti pada Gambar-3. Pada Gambar-3, terdapat beberapa kelompok operator bebas (untuk mempermudah representasi, maka kelompokoperatorbebasdinyatakandengan"panahdua arah"),yaitu : hasil akhir
level 1
01 I
I
02
R1
05
06
Re
R9
Gambar-3 StruktwPohonTransaksi
1 . 03dan01(01 .-
g0
2 . 04dan0L (01 .-
0I)
-). 03,06 dan 07 atau: 3.1.03 dan0q^(01 .3.2.o3 dan0Z (01 .---=.-_ 3.3.0q dan07 (W -
0O, 0D, oD,
07
R4
t
pnocntorNcsITB,vor.25,No.I, 1992
4. 04 dan05.(0{. .=--_* 5
0O
0_10f dan07 atau: 5.1. 05 dan0q.(0I 5.2. 05 dan0Z(0q.5.3. 06dan0Z(0q.-
09 0D 0D
Jikadilakukanoptimasi,makaakandidapatkan kelompokoperatorbebasberikut: + 1. 01,5. 06 U Ql 2. 04-05 6. 0I.+Q{ -_OO 3.01. 7.0I-02
4. o1 - o Z rv.3. DERAJATKEBEBASANIBUTE7I -
Derajat kebebasan dari operator bebas adalah tingkat prioritas eksekusi operator bebas,relatifterhadap semuaoperator relasi pada transaksi.
-
Derajat kebebasan suatu operator bebas ditentukanberdasarkantingkatan (level) operator bebastersebutpadastruktur pohon operatorrelasi.
PadaGambar-3,maka : O_101
: mempunyai derajat kebebasan3
O_1Oq, 07 : mempunyai derajat kebebasan4
V.
EKSEKUSI OPERATORBEBAS& KELOMPOK OPERATORBEI]AS
v.1. EKSEKUSISECARABERURUTAN(SEKUENSTAL) Prinsip eksekusi kumpulan operator relasi yang merupakanpenjabarandari transaksi pada SMBDR dilakukan secara trerumtan (sequential),meskipun SMBDR termaksud dioperasikan pada sistem operasr yang mendukung proses paralel (s€pcrti muiti-task.;. Dengan demikian, waktu eksekusi (waktu tanggap) untuk satu transaksitertentu, adalah merupakan akkumulasi waktu tanggap eksekusi setiap operator relasi yang dimaksudkan sebagaipenjabarantransaksi.Untuk Gambar-3,s(rcarateoritis waktu tanggaptransaksi(ts) adalah: 7 .sr tS=
u) i-l
to;
dimana : tei : waktu eksekusiuntuk operatorrelasi Oi
PROCEEDINGSITB, Vot.25, No. 1, 1992
9
V.2. EKSEKUSI SECARA PARALEL Dengan menerapkan definisi operator bebas dan kelompok operator bebas, maka eksekusi operator relasi secaraparalel akan dapat diterapkan,denganprinsip sebagaiberikut: - Seluruh operator relasi yang didefinisikan dalam satu kelompok operator bebas (misalnya : Of, dengan 04 dari Gambar-3) dapat dieksekusi secarabersama(paralel) dan tidak saling bergantungansatu samalainnya. -
Prioritas pemilihan operator bebas yang akan dieksekusi, ditentukan berdasarkan derajat kebebasan dari setiap operator bebas. Operator bebas dengan derajat kebebasanpaling besar akan mendapat prioritas pertama (hal ini adalah merupakan pcnjabaranprinsip urutan(sequence)dari strukturpohon.
-
Eksekusi operator relasi dimulai dari level (tingkatan) yang paling tinggi (untuk Gambar-3,maka dimulai dari level 4, level 3 dan seterusnyasampaidenganlevel 1).
-
Setiapoperatorrelasidianggapsebagaisatuproses.Padaeksekusisekuensial,seluruh operator reiasi dari transaksidianggapsebagaisatu proses.
Berdasarkanprinsip ini, maka waktu eksekusi transaksi untuk Gambar-3 secaraparalel (tD secarateoritis akan lebih kecildari tg atau tp < tq. Secarateorjtis, besamyatp akan ditentukan oleh beberapahal berikut : 1.
Jumlah proses yang dapat aktif secara bersama (paralel). Hal ini ditentukan oleh kapasitassistemkomputeryang digunakan.
2.
Jumlaboperatorbebaspadasetiapsaat.
3.
Waktu eksekusi terbesar dari setiap operator bebas yang terdapat pada satu kelompok operator bebas.
4.
Waktu tanggap adalah sama denganwaktu untuk eksekusi seluruh operator relasi yang berada pada jalur terpanjang (alur pada pohon transaksi adalah mulai dari akar pohon transaksi,sampai dengandaun pohon transaksi).
Secarapraktis, hal tenebut diatas masih perlu dikoreksi, denganbeberapabeban (overhead) berikut : 1.
Waktu yang dibutuhkan untuk pengendalian (sinkronisasi) prcses yang paralel (manajemenuntuk prosesyang paralel).
2.
Karena transaksi pada SMBDR biasanya melibatkan data dengan volume yang relatif besag maka ada kecenderungan bahwa pemrosesan secara paralel akan menuntut penggunaan memod sekunder (untuk penyimpanansementara)relatif lebih besar daripada eksekusi secara berurutan. Hal ini akan mengakibatkan naiknya beban (overhead)dari aktifitas Masukan / Keluaran.
t0
PROCEEDINGS ITB' Vol.25, No. 1, 1992
V3. AI{;ORITMA
PENGENDALIAN
EKSEKUSI PARALEL
Algoritma pengendalian eksekusi secara paralel dimaksudkan untuk mengendalikan pengaktifanproses untuk setiap opcrator relasi, agar terdapatsinkronisasi,scsuai dengan urutannyapadapohontransaksi. Llcberapastrategi yang mungkin ditcmpkan scbagai prinsip algiiritrna pcngcndalr satu variahe! eksekusiparalel telah dibahasdan
PIIOSRS :
Prtxqs yangdimaksudkan
-
DERAJAT :
Derajat kebebasan proses, rclatif terhadap struktur pohon "'ang sebagaitingkat (level) opcradimaksudkan.Hal ini dapatdiinterpretasikan pada pohon transak.si tor relasiyang dimaksudkan
-
POINTER :
Pointeryang menujuke prosesyang menunggu.
Untuk Gambar-3,tabelyang sesuaiadalahsebagaiberikut : No.
K
I z
0 0 0 1 2 2 1
J A
5 6 7
5 6 7 3 4 2 1
D
PN
A
A
t\:
A
5 5 6 6 ,|
p: D PN:
4 J J
2 1
kondisi proses (operator) derajatkebebasan poinler
PROCEEDINGS ITB,Vot.25,No. 1, 1992
t.
11,
Algoritma pengaktifan proses(AKTIF) : PROSEDIIR AKTIF (aktif secarapermanen) BILA processortersediaMAKA Cari prosesPx denganK = 0 dan D paling besar Untuk Px, maka I( = * (identifikasi bahwa prosessudahaktif; Akti{kan prosesPx SELESAI AKHIR PROSEDUR AKTIF:
2.
Algoritma modifikasi tabel (MOD_TABEL) : PROSEDUR MOD_TABEL (Untuk optimasi processor,maka prosedurtersebuthanya aktif, jika ada prosesyang sudahselesai). BILA ada prosesPx sudahselesaiMAKA m = PN dari Px PN dari Px = 0 K dari baris ke-m dikurangisatu (Km = Klq- 1) SELESAI AKHIR PROSEDUR MOD TABEL:
VI.
IIASIL
IMPLEMENTASI
PADA SISTEM OPERASI
MULTI.PROGRAMMING Implementasi dari prinsip yang telah dijelaskan sebelumnya (eksekusi operator relasi secaraparalel) telah dilakukan, dan telah diuji-coba denganberbagaiketerbatasanyang ada. Uji-coba dilakukan dengan dua cara, yaitu eksekusi secara sekuensial dan eksekusi secaraparalel, denganmenggunakandata dan metodaeksekusimasing-masingoperator yang sama untuk kedua cara eksekusi. Dengan demikian, secara garis besar bahwa perbedaan waktu tanggapuntuk transaksiyang sama,hanya akan timbul sebagaiakibat dari : 1.
Beban (overhead)pengendalianeksekusiparalel (hanya untuk eksekusisecaraparalel)
2.
Beban (overhead)aktifitas Masukan / Keluaran yang timbul sebagaiakjbat keterbatasan memon uuma.
3.
Jumlah kanal Masukan / Keluaran yang tersediauntuk eksekusisecaraparalel.
12
hR}0EEDINGS ITB, vor. 2s, No.r, 1992
VI.I.
FASILTTAS KOMPUTER
Sistem komputer yang digunakanadalah : - Processor :PDP lll44 -
SistemOperasi: XEND(
-
Pemrograman : C-language
-
Kanal VO
: 2 unit
-
Disk
:2 unit
VI.2. BASIS DATA & TRANSAKSI Basis Data yang digunakan sebagaicontoh dalam pelaksanaanuji-coba adalahbasis data PERSONALIA yang terdiri dari 10 relasi. Struktur dan contoh data disertakan pada I-ampiran-1. Transaksi untuk basis data termaksuddidefinisikan secarakhusrs (dengankode). Hal ini dilakukan untuk menghindari semaksimal mungkin adanya beban (overhead) kompilasi transaksi.Padalampiran-2,disertakan6 transaksiyangdigunakanpadauji-coba. VI3.
HASIL UJI.COBA
Dalam pelaksanaanuji-coba, kondisi yang diterapkanadalahsebagaiberikut : 1.
Padasaat percobaan,sistem komputer tidak digunakanuntuk prosesyang lain.
2.
Jumlah tupple yang digunakan dalam uji-coba adalah 1000 dan 10.000.Hal ini dipenuhi dengandatadummy.
3.
Pengamatandilakukan terhadapwaktu : waktu mulai eksekusi serta saat hasil akhir eksekusi didapatkan. Dengan demikian, dalam waktu yang diamati telah tcrqakup seluruhbeban(overhead)nyatayang digunakandalam rangkaeksekusitransaksi.
Untuk kondisi tersebut,didapatkanhasil sesuaidenganisi tabel- 1 (untuk lfiX) tupple) dan tabel-Z(untuk 10.m0 tupple).Untuk informasilebih rinci, lihat IBUT 87].
PROCEEDINGSITB,VoI.25,No. t, 1992
13
(delik)untuk1000lupple: Tabel-l : Wakt,-,langgap
TRANSAKSI
T1 T2 T3
EKSEKUSIPARALEL
LKSEKUSI SEKUENSIAL 9,20 28,00 15,33
l disk
2 disk
waktu
reduksi
waktu
reduksi
14,80 36,33 17,38
40,87 Vo -29,75 Vo -13,37Vo
15,60
-L,76 Vo
Tabel-2: Waktutanggap(detik)untuk10.000tupple: TRANSAKSI
T1 't2 13 T4 T5 T6
EKSEKUSIPARALEL
EKSEKUSI SEKUENSIAL 10,33 306,00 r92,50 254,50 1967,50 538,00
l disk waktu
reduksi
68,80 328,00 181,50 241,50 1818,0
+0,75 Vo -7,I9 Vo +5,7L Vo +5,1,1Vo +7,6O%
2 disk waktu
355,00 l7'7,55 234,m l744,OO 529,00
reduksi -t6,o1.70 + 7,19 Vo + 8,06 Vo +11,36Vo + 1,67Vo
VI.4. EVALUASI IIASIL UJI.COI}A Dari hasil uji-coba (disertakanpada Tabel-l dan Tabel-2) terlihat bcberapahal yang penting,dan beberapakeanehan: 1.
2.
Waktu tanggap eksekusi paralel dengan 1000 tuppie ternyata lebih bcsar dari waktu tanggap eksekusi sekuensial.Sebaliknya, untuk 10.000 tupple, maka keadaan akan terbalik.Dari uji-coba ini dapatdinyatakanbahwa : -
Padaprinsipnya,perbaikanwaktu tanggapdapatterjadidenganmelakukaneksekusi paralel, meskipun secara nyata hal ini tidak terlihat pada uji-coba dengan 1000 tupple.
-
beban (overhead)pengendalianeksekusiparalel adalahlebih besar dari perbaikan waktu tanggapuntuk 1000tupple.
Reduksi waktu tanggapternyatalebih baik jika menggunakandua disk dan dua kanal. Dengan demikian dapatdinyatakanbahwa,jika jumlah kanal dan disk membesar,maka waktu tanggap akan makin membaik (tentunya ini berlaku, jika transaksi yang dimaksudkanmenggunakanbanyakrelasi).
14
J.
4.
zR)oEEDINGS ITB, vo!.2s, No.1, 1992
Waktu eksekusi T4 secaraparalel temyata lebih baik dari eksekusi sekuensial.Hal ini tidak mungkin, karena pada T4 tidak terdapat operator bebas. Seharusnya, waktu eksekusi secaraparalel akan lebih besar dari waktu eksekusi secarasekuensial, karena adanyabeban (overhead)pengendalianeksekusiparalel. Sesuai'dengan transaksi dan lingkungan uji-coba, maka reduksi waktu tanggap maksimum yang dapat dicapai adalah 11,36 %. Hal ini dapat diamati dari eksekusi paralel untuk transaksi T5 (menggunakan 2 disk). Dengan reduksi hanya II,36 Vo, berarti beban (overhead) untuk pengendalianeksekusi paralel relatif cukup dominan di dalam waktu tanggap.
5. Mengingat keterbatasan fasilitas yang dapat digunakan, khususnya yang berkaitan dengan sistem operasi, beberapa hasil uji-coba tidak dapat dijelaskan (misalnya hasil uji-coba dari transaksi T2). Kemungkinan, hal ini terjadi sebagai akibat dari tidak idealnya kondisi percobaan.Jika akan dianalisa, seharusnyahal ini akan dapat dijawab dengan mempertimbangkanbeberapaaspekdari sisi sistem operasi,yaitu : -
strategi pengelolaansumber (resource)oleh sistem operasi
-
operasimasukan/keluaran(I/O) memori primer dan strategi pengalokasianuntuk setiap prosespada eksekusi paralel.
Reduksi waktu tanggap akan membaik, jika struktur pohon dari transaksi memiliki banyak cabangdan seimbang.Hal ini didukung oleh makin banyaknyajumlah operator bebas.
VII. KESIMPUI,AN Masalah yang dibahasdalam tulisan ini berangkatdari suatu hipotesa.Dari analisa teoiitis terhadap ide yang dimaksudkan pada hipotesa, telah dijelaskan bahwa hipotesa tersebut benar, dengan dikembangkannya definisi operator bebas, kelompok operator bebas dan derajat kebebasan. Berbagai aspek yang mengakibatkanmeningkatnya kompleksita; persoalan dalam rangka implementasi (uji-coba) juga telah dibahas, walaupun belum mencakup seluruh aspek, khrsusnya dari sisi sistem operasi (pengelolaaneksekusiparalel). Sebagaidampak langsungdari kompleksitastersebut,adanyabeberapahasil pengamatanyang belum dapat dijelaskansecaratuntas. Dengan keterbatasanyang disebutkan diatas, hasil uji-coba sctidak-tidaknyasecar-a global sudah dapat digunakan sebagaidasar untuk menyatakankebcnaranhipotesa y:,,rig disebutkandi awal tulisanini. yaitu :
PROCEEDINGS ITB, Vol.25, No. 1, 1992
t5
:
l:, dari transaksi pada basis data model relasi dapat dieksekusi secara Operatr. paralei, or'1F;ii ir'snganggapbahwa setiapoperatorrelasi adalahsatu proses.
.
Eksekusiuiajrirlr relasidari transaksisecaraparalelakanmemperbaikiwaktu tanggap.
Berbagaiha.irri.rsir dianggapmenjadi grnghalangdari kcberhasilanuji-coba (minimal, belum memberikanrcrJuksiwaktrl tanp.g:ii) vang relatif baik, ktrususnyapadaeksekusiuntuk jumlah lupple yarriil*rnata.;).iiai ini ter-.jl
Mcningkatkan deru_;ai iraf:lelisme pada proccssor.IIal ini mungkin dilakukan dengi,r pengembangannrErixlaoptimasitransaksi,sehinggastrukturpohon opcratorrelasidapai diusahakanagar semal$imal mungkin bercabangbanyakdan seimbang.Struktur pohon oflerator relasi seperti ini akan berarti memperpendekjalur operator relasi dan sekaligus meningkatkanjumlah op€ratorbebas.
2.
Meningkatkanderajatparalclismepadaaktifitas(opcrasi)Masukan,'Keluaran.
Reduksj waktu tanggap maksimum (teoritis) yang dapat dicapai dcngan peningkal.an pada dua hal terscbutdiao.as, adalahmendekatiprosentasebebanMasukan/ Keluaran pada SMBIIR padaumumnya,yang berkisarantara60 - 80 % IDON 8,5j. Untuk tujuan peningkatanreduksi waktu tanggapyang dimaksudkandiata;, beberapa hal yang rnasihperlu dikembangkanlebih lanjut,antaralain : 1,. Optimrsi algoritma yang digunakan,yang berkaitandengan eksekusisetiap operaior relasi,khususnyayang menyangkutpengendalianeksekusisecaraparalel. 2. Pengembangan metodaoptimasitransaksi,sehinggastrukturpohonoperatorrelasrdapat diusahakanagarsemaksimalmungkin bercabangbanyakdan seimbang. 3. Melaksanakanuji coba padasistemkomputeryang memberikankelcluasaanlebih besar dalam bal kemungkinan konfigurasi perangkatkeras dan sistem operasi yang dapat digunakan.
UCAPAN
TERIMA
KASIII
Keberhasilan uji-coba eksekusi paralel operator relasi yang dijelaskan pada tulisan ini tidak lepas dari ketersediaan komputer yang dimiliki oleh PT.INTI, dan peran Sdr.Ir.Manonton Butafuutar dalam pengembanganberbagai program yang digunakan untuk uji-coba.Untuk jtu, penulismengucapkanterimakasihatasdukungann;'a.
16
zRI:EEDINGS ITB, vot. 25,No. 1, 1992
DAI-IAR PUSTAKA [BLr-T87]
Butarbutar, M., EKSEKUSI PARALEL OPERA1OR REIASI SMBDll, Tugas akhir program S-1, Jurusan Teknik Informatika ITB, Bandung, Pebruari1987.
[DON85]
Donovan, J.J. & Stuart, E.M., OPERATING SYSTEM, Mc.Graw-Hill, Tokyo, 1985.
lSIT85l
Sitohang,B.,EKSEKUSI OPERATOR RELASI RDBMS PADA SISTEM OPERASI MULTI-PROGRAMMING, KKN - IPKIN, Jakarta, September 1985.
[STA 88]
Stanley, Y.W. Su, DATABASE COMPUTERS : Principles, Architectures & Techniques,Mc.Graw-Hill, 1988.
[ULL82]
Ullman, J.D., PRINCIPLES OFDATABASE SYSTEMS, Computer Science Press,Maryland, L982. Ullman, J.D., DATABASE AND KNOWLEDGE - BASE SYSTEM, Volume I, Computer SciencePress,Maryland, 1988.
[ULL 88]
PROCEEDINGS ITB. Vo!.25,No.I, 1992
Lamplran-|
BASIS DATA STRUKTUR l. Model E-R
2. Skema loglk : PEG(N!P. NAI1A,UtlUR) JEN( KJEN, I,L,EN) JUR( KJUR, NJUR) BHS(KBHS.NEHS) I S T R I( N I T , P E K ) KANTOR(KTOR. NTOR) PEND(NIP. KJEN-KJUR) PEGBI.IS( NIP- KBHS,KET) P E T R I (N I P - N I T ) PETOR(NIP. KTOR-T6L)
17
18
zRj1EEDINGS ITB, vot. 25, No.t, 1992
Lamplran-I f - C o n t o hD a t a : PEG
JTN
NIP
8 7 0l 8702 6703 8704 8705
MIlA
Ali Budi Chorles Daniel Efendi
JMUR 40 30 27 25 29
BH5 KBHS NBHS t0 Inggrls PR Peroncls JR Jermon JP .Jspar{ BL Belanda
PIND
KJEN
JUR KJUR
Kursus
IF
I nformatika
s0
Diploma SorJono llaster Doktor
TL
Elektro
sl 52
NII
Ani Tutl Betty Atl Susl Nelly Totl
KJEN
870| 870| 870r 8702 8702 8703 8703 8704 8705
sl
s2 s3 sl
s2 sr s2 5l sl
KJUR BI f1A IF EL IF TA IF IF IF
NIP
flA
flatomotlka
8l TA
Elologl Tsmb8ng
KANTOR
ISTRI PEK
PT.Oanesho PT.Gsnesho lkutSuoml PT.Gonesha PT.Dw lkutSuomi PT.D@
KTOR
NTOR
JK BD f1D
JakortE Bondurq me(hn Surobqlo Semarong
s8 SH
PETRI
PEOEHS
NIP
t'uuR
KJEN
KR
KEHS
IG
KET A A P P A P A A
IG
P
670
IU
870|
PR
870r
JR
8702 8702 8703 8705 8704 8705
t0 PR IG PR
NIP
NIT
8 7 0| 8742 8702 8702 8703 8704 8705
Teti Anl Tuti Betty Susi Ati Nelly
PROCEEDINGSITB,VoI.25,No. 1, t992
19
I-AMPIRAN.2 .T'RANSAKSI UJI-COBA
1.
Transaksi Tl lv{akna: Dapatkand;rtapnbadi pegawaidcnganMP adalah8701.
2.
Transaksi T2 Makna : DapatkanNII'darr Nz\MA pegawaiyang memenuhisyaratberikut : kodejurusanadalahili. kodejenjang51, dan umur lebih kecil dari 30.
3.
Transaksi'f3 Makna : DapatkanNIP pcgawaiyang memenuhisyaratberikut : namajurusanadalahInformatika,denganjenjangS1, dan pemahbekeqadi Bandung.
4.
Transaksi T4 Makna : Dapatkandata pribadi,pendidikan,penguasaan bahasa,istri, kantordanjcnjnag pendidikandari pegawaidenganNIP adalah8704.
5.
TransaksiT5 Makna : Siapa saja pegawai (NIP) yang tercatat pada relasi PEG, PEND, PEGBHS, PETRI, dan PETOR. Daftarkankode kantor,bahasadanjenjang pendidikannya.
6.
TransaksiT6 Makna : Dapatkandatapnbadi dan pendidikandari pegawaibernamaALI.
20
zRqcEEDINGSITB, vol.25, No. 1, 1992
(;Ec(
I rooo lrl ' rool =ezorI | rure
-T'
F-;--zl I N r P= 8 7 0 r I
-l'
r-;--z -l' I N r p= 8 7 0 r I
@ plpa = 7 flle = 2 d e s k r l D t of lrl e = l 6
Keterangan : dari/ke f i le nlasukan/keluaran --+ darl/ke plpa masukan/keluaran
xAngkadl samplng menyatakan Jumlahrecordflle xAngkadl samplng menyatakan Jumlahrecordmelalulplpa {> xAngkadl klrl atas kotakmenyatat(an n0m0roperator xAngkadikananatas kotakmenyatakan jumlahoperasiI1lK. Struktur PohonTransaksl Tl
PROCEEDINGSITB, Vol.25,No. 1, 1992
)
o
2000
utluR ( l0
P l P a= 3 file = 4 d e s k r l p t of rl l e = l 0 Keterangan : ----{> masukan/keluaran darl/ke f i le masukan/keluaran dafilke pipa +
xAngkadl samping-----+ menyatakan Jumlahrecordf lle xAngt(adi samping--; jumlahrecordmelalulplpa menyatakan *Angkad1klrl ataskotakmenyatakan nomoroperator xAngkadlKanan ataskotakmenyatakan JumlahoperaslM/K. Struktur PohonTransaksl T2
21
22
PR1.EEDINGSITB,vol.25,No' 1, 1992
o l00l NJUR= "lnformatlka' l)
o 1006
D
lxl KJUR
o l00l NTOR "Bandung'
3)
GENDT tooo\-___-\
s)
467 '5I " KJEN=
PlPa= 5 file =6 file = l6 deskriPtor Struktur PohonTransaksl T3
lxl
1006
1, 1992 23 PROCEEDINGSITB,VoI.25,No.
1)
o lO0l
N r P= 8 7 0 4
2)
1002
txl
H
r 000
NIP
to o 2
4 lxl
H
NIP
r 000
1002
5)
lxl NIP
ff
1002
6)
lxl Nlp
ff
ffi .
P i P a= 5 file =7 l7 destcrlPtorfiie=
Struxtur PohonTransaksi T4
24
No. 1, 1992 PR)CEEDINGSITB,vol.25,
l,oooo
lnl I
ll
l o o oIe
NrP
lr) thl
-r|
I
rurp I
l''
-l--
lurnl
I
li, I l l6 Y
lo Y
I
Y
C(
@
@
@
@
@
@
q
oooo l, Y, lr, lr(l
r000e I
-rI
l,oooo l,oooo .-t_-.____r_ roooe loooe lo) I I ;ooon
l,oooo
I
____l__
lr)
@
@
@
@
NIP
I
C(
I
-l16)
lnl I
I'oooo I'oooo ___r-_ roooe 1000e I
Nrp
I
C<
I
17)
lJ, I arr r-T \__:_\
Struktur PohonTransaksl T5
I
l
l,oooo
____l_
18) r000e I lnl ruro I |
-T__ q
PROCEEDINGS ITB, Vol. 25, No. 1, 1992
|)
6 20000 NAMA <=
"zzzzz'
D
o20000 NAIIA <= "zzzzz"
3)
o 20000 NAMA<= "ALI"
5)
|)
o
20010
lxl NIP
Struktur PohonTransaksl T6
o 20000 KJEN<= 'zz'
25
