Kembali Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
PERANCANGAN DAN ANALISIS JUMLAH PROSESOR MENGGUNAKAN MODEL CUBE-CONNECTED DAN TREE-CONNECTED DALAM ALGORITMA PARALEL Mike Susmikanti*
ABSTRAK PERANCANGAN DAN ANALISIS JUMLAH PROSESOR MENGGUNAKAN MODEL CUBE-CONNECTED DAN TREE-CONNECTED DALAM ALGORITMA PARALEL. Komputasi paralel dirancang untuk menurunkan biaya, mengefisienkan ruang memori dan mempecepat perhitungan. Arsitektur sistem paralel diklasifikasikan dalam beberapa bentuk diantaranya multi-processor. Multiprocessor mengijinkan pemrosesan dengan alur instruksi yang terpisah. Algoritma paralel merupakan suatu metode solusi bagi permasalahan tertentu yang dirancang untuk komputer paralel. Dalam hal ini akan dibahas rancangan dan analisis jumlah prosesor yang digunakan serta alur instruksi dan data yang diproses oleh masing-masing prosesor. Simulasi diaplikasikan dalam operasi perkalian matriks dengan matriks dan matriks dengan vektor dalam algoritma paralel dan prosedur PASCAL. Model yang dipilih adalah komputer SIMD cube-connected dan tree-connected. Sistem komputer yang digunakan saat ini masih satu personil komputer dengan asumsi memori yang dipakai adalah virtual memory dengan beberapa address. Kata-kata kunci: Pemrosesan Paralel, Multiprocessor
ABSTRACT THE DESIGN AND ANALYSIS OF THE NUMBER PROCESSOR USED THE CUBECONNECTED AND TREE-CONNECTED MODEL IN PARALLEL ALGORITHMS . Parallel computing has been made breakthroughs that have decreased costs and increased memory space and computing power. The parallel architectures are classified into some system. The one is multiprocessor. Multiprocessors allow processing elements to execute separate instruction streams. A parallel algorithm is a solution method for a given problem destined to be performed on a parallel computer. The number of processor is design to process the data. The simulation is applied to matrix-by-matrix and matrix-byvector multiplication in the algorithms parallel and procedure PASCAL. The model are used is the SIMD computer Cube-Connected and Tree-Connected. The computer system now is still used one the personnel computer with assumption the memory are used is the virtual memory with some address. Keywords: Parallel Processing, Multiprocessor
*
Pusat Pengembangan Informatika Nuklir - BATAN
417
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
PENDAHULUAN Beraneka ragam persoalan teknik dan ilmu pengetahuan berskala besar memerlukan sejumlah besar perhitungan. Persoalan yang dihadapi umumnya berkaitan dengan perkiraan pengaruh perubahan parameter pada energi. Sebagai contoh dalam perhitungan dinamik fluida yaitu rancangan reaktor nuklir dan dinamik plasma untuk aplikasi energi fusi nuklir. Data dan perhitungan perkiraan parameter membentuk sistem persamaan yang dinyatakan dalam bentuk matriks berikut operasinya. Pemrosesan paralel merupakan cara untuk mencapai kecepatan komputasi yang diinginkan dengan meningkatkan atau mengefisienkan ruang memori serta dirancang dengan tujuan melakukan penurunan biaya. Algoritma paralel merupakan suatu metode penyelesaian bagi permasalahan tertentu yang dirancang untuk komputer paralel [1]. Pembahasan meliputi rancangan dan analisis jumlah prosesor yang digunakan serta alur instruksi dan data yang diproses oleh masing-masing prosesor. Simulasi diaplikasikan dalam operasi perkalian matriks dengan matriks dan matriks dengan vektor dalam algoritma dan prosedur PASCAL. Algoritma paralel ini dirancang untuk diproses pada komputer SM SIMD (Shared Memory, Single Instruction stream - Single Data stream) dengan model kubus-terhubung dan pohon-terhubung. Difokuskan sistem komputer yang digunakan saat ini masih satu personil komputer dengan asumsi memori yang dipakai adalah virtual memory dengan beberapa address.
KOMPUTER SIMD Salah satu model komputasi paralel pada komputer adalah model dengan instruksi yang sama dapat memproses data yang berbeda (SIMD) [1]. Pada model komputer paralel terdiri dari N prosesor yang sama (gambar-1). Masing-masing N prosesor mempunyai memori lokal yang dapat menyimpan data maupun program. Semua prosesor beroperasi berdasarkan kontrol sebuah aliran perintah tunggal yang dikeluarkan oleh sebuah unit kontrol pusat. Sejumlah N prosesor diasumsikan menyimpan hal yang sama dari sebuah program, masing-masing nilai prosesor disimpan di dalam memori lokal. Terdapat sejumlah aliran data yang dibagi per prosesor. Dalam penyelesaian beberapa masalah pada komputer SIMD, dimungkinkan prosesor mampu berkomunikasi guna melakukan pertukaran data atau hasil. Hal ini dapat dilakukan dengan dua cara yaitu dengan komunikasi melalui memori bersama dan jaringan interkoneksi.
418
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Memori Bersama/ Jaringan Interkoneksi Aliran data 1
Aliran data 2 Prosesor 1
Aliran data n Prosesor 2
.…
Prosesor n
Aliran intruksi Kontrol Gambar-1 : Model Komputer SIMD
Komputer SIMD Memori Bersama (Shared Memory) Jenis komputer ini dikenal sebagai model Parallel Random Access Memory (PRAM) [5]. Dalam hal ini, N prosesor berbagi memori bersama. Selama pelaksanaan algoritma parallel, N prosesor mengakses memori bersama untuk membaca input data, membaca atau menulis hasil-hasil antara dan menulis hasil akhir. Model dasar ini memungkinkan semua prosesor untuk mengakses ke memori bersama secara simultan apabila lokasi memori yang ingin dibaca atau ditulis adalah berbeda. Model memori bersama meliputi memori bersama secara fisik ( physical) dan bayangan (virtual) [3]. Dalam hal ini digunakan model memori bersama secara virtual.
Komputer SIMD Jaringan-Terhubung (Interconection Network) Model SIMD SM dapat dibuat menjadi layak dengan membagi memori menjadi blok-blok dan menjadikannya akses ke blok-blok ini secara eksklusif (dua prosesor tidak mungkin secara simultan membaca dari/atau menulis ke lokasi memori). Pada jaringan-interkoneksi, M lokasi dari memori bersama didistribusikan diantara N prosesor, masing-masing menerima M/N lokasi memori. Disamping itu setiap pasang prosesor dihubungkan oleh sebuah jalur dua arah. Algoritma pada jaringaninterkoneksi dapat disimulasikan pada model memori bersama dengan langkah antara
419
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
lain jajaran satu dimensi (linear), jajaran dua dimensi (Mesh), hubungan-pohon (TreeConnection), hubungan-kubus (Cube Connection) dan hubungan-campuran (Perfect Shuffle Connection) [1,4] . Dalam hal ini akan disimulasikan langkah-langkah dalam pohon-terhubung (gambar-2) dan kubus-terhubung (gambar-3) pada operasi matriks khususnya perkalian matriks dengan vektor dan perkalian matriks dengan matriks, yang berperan salah satunya pada penyelesaian sistim persamaan serta permasalahan graf. Akan dianalisis jumlah prosesor yang diperlukan atau dirancang, waktu yang diperlukan dan biaya yang mempunyai keterkaitan dengan jumlah prosesor. P7
Akar
Tingkat-3
P5
P6
Tingkat-2
Tingkat-1 Daun
P1
P2
P3
P4
Gambar-2 : Pohon-terhubung dengan tujuh prosesor P1
P9
P5
P3
P13
P11
P7
P15
P2
P14
P6
P10
P4 P8
P12 P16
Gambar-3 : Kubus-terhubung dengan enam belas prosesor
420
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
RANCANGAN DAN ANALISIS ALGORITMA PARALEL Sejumlah teknik rancangan algoritma digambarkan dalam hubungan berbagai model komputasi paralel yang dibahas sebelumnya diatas. Contoh kasus yang dibahas berhubungan dengan permasalahan analisis algoritma yaitu waktu yang diperlukan, biaya untuk memproses dan efisiensi penggunaan sumber daya. Suatu algoritma yang dirancang, dievaluasi menggunakan beberapa kriteria antara lain waktu yang diperlukan untuk menjalankannya (running time), jumlah prosesor yang digunakan dan biaya [1]. Disamping itu perlu dipertimbangkan sejumlah ukuran yang berkaitan dengan teknologi tertentu misalnya komputer yang digunakan ataupun penggunaan sistem jaringan. Alasan utama terhadap pembuatan komputer paralel adalah mempercepat komputasi. Sehingga ukuran yang terpenting didalam mengevaluasi algoritma paralel adalah running time-nya serta kebenaran program juga harus dipertahankan. Running time didefinisikan sebagai waktu yang diperlukan mulai dari awal algoritma dilaksanakan sampai saat berakhir. Apabila berbagai prosesor tidak memulai dan mengakhiri komputasinya secara bersama, maka running timenya adalah sama dengan waktu antara saat prosesor pertama mulai melakukan komputasi dan saat prosesor terakhir mengakhiri komputasi. Misalnya suatu permasalahan yang besarnya n, running time pada kasus terburuk dari suatu algoritma adalah suatu fungsi n yang disimbolkan dengan t(n) [6]. Kriteria kedua yang paling penting didalam mengevaluasi algoritma paralel adalah jumlah prosesor yang diperlukan untuk memecahkan permasalahan dan komunikasi antar prosesor. Disisi lain perlu dipertimbangkan permasalahan faktor perawatan khususnya yang akan meningkat, dan harga yang harus dibayar untuk menjamin tingkat kehandalannya yang tinggi. Semakin besar jumlah prosesor yang digunakan oleh algoritma untuk memecahkan permasalahan, semakin mahal pula biayanya yang harus dikeluarkan. Untuk permasalahan yang berukuran n, maka jumlah prosesor yang diperlukan oleh suatu algoritma, sebagai fungsi n yang ditunjukkan dengan p(n). Kriteria berikutnya adalah biaya dari suatu algoritma paralel yang didefinisikan sebagai hasil kali dua ukuran sebelumnya, dinyatakan sebagai: Biaya = running time paralel x jumlah prosesor yang digunakan Biaya sama dengan jumlah langkah yang dilaksanakan secara bersama oleh semua prosesor dalam memecahkan masalah dengan kasus terburuk (worst case) pada algoritma. Diasumsikan sejumlah prosesor melaksanakan sejumlah langkah yang sama. Apabila tidak demikian, maka biayanya adalah batas atas jumlah langkah yang dilaksanakan. Untuk permasalahan berukuran n prosesor maka biaya diperkirakan sebagai fungsi dari n yaitu c(n) = p(n) x t(n), walaupun demikian tergantung pula dari masing-masing persoalan yang dibahas. 421
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
PERKALIAN MATRIKS DAN VEKTOR DENGAN POHON-TERHUBUNG Perkalian matriks dan vektor dengan pohon-terhubung diperoleh m-1+log(n) langkah atau tahap. Langkah tersebut terlihat pada gambar-4, yaitu sejumlah tiga tahap untuk m = 3 dan n = 4. Secara umum diagram pohon mempunyai n buah prosesor ”daun” P1, P2, ..., Pn, dan n-2 prosesor ”menengah” Pn+1, Pn+2, ...., P2n-2, serta prosesor ”akar” P2n-1. Algoritma dari proses diatas [1], dinyatakan dalam prosedur MVTREE (lampiran-1), khusus untuk matriks order m x 2 dan vektor order 2 x 1 : (i) Prosesor daun Pi menyimpan ui selama pelaksanaan algoritma. (ii) Matriks A dimasukkan ke dalam diagram pohon baris demi baris, satu unsur per “daun”. Prosesor Pi menerima aji, maka akan dihitung ui x aji dan mengirimkan hasil perkalian ke induknya. (iii) Proses menengah atau prosesor akar Pk akan menerima dua masukan dari anakanaknya, menambahkan dan mengirimkan hasilnya kepada induknya. Akhirnya vj akan muncul dari prosesor ”akar”.
500 50
60
10 30
20 40
(a)
1200 50
30
50
(c)
40
(b) 1700 3900
1700
1500
60
2400 60
50
60
(d) Gambar-4. Perkalian matriks dan vektor menggunakan prosedur MVTREE untuk n = 2
422
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Berikut hasil program untuk perkalian matriks khusus order 2 x 2 dengan vektor order 2 x 1 untuk persoalan tersebut diatas; Output program: order of Matrix & Vector 221 Matrix Input 10 20 30 40 Vector Input 50 60 Process Tree Multiplication of Matrix & Vector : P(1) : 500 P(2) : 1200 P(1) : 1500 P(2) : 2400 Processor(3) :1700 Root(1) :1700 Processor(3) :3900 Root(2) :3900 Output Matrix 1700 3900 Prosedur matriks order m x n dan vektor order n x 1 untuk perkalian matriks khususnya n > 2 ditunjukkan dalam prosedur MULTITREE (Lampiran-2). Berikut ini hasil program untuk perkalian matriks order 3 x 4 dengan vektor 4 x 1. Output Program: order of Matrix & Vector 341 Matrix Input 1234 1234 1234 Vector Input 10 20 30 40
423
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Process Tree Multiplication of Matrix & Vector : Processor(1) : 10 Processor(2) : 40 Processor(3) : 90 Processor(4) : 160 Processor(1) : 10 Processor(2) : 40 Processor(3) : 90 Processor(4) : 160 Processor(1) : 10 Processor(2) : 40 Processor(3) : 90 Processor(4) : 160 Processor(5) :50 Processor(6) :250 Root(1) :300 Processor(5) :50 Processor(6) :250 Root(2) :300 Processor(5) :50 Processor(6) :250 Root(3) :300 Output Matrix V(1) : 300 V(2) : 300 V(3) : 300
424
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Diagram pohon untuk proses diatas dapat digambarkan sebagai berikut : V1 V2 V3
P7
P5
P1
10
1 1 1
P6
P2
20
2 2 2
P3
30
P4
3 3 3
40
4 4 4
Gambar-5 : Perkalian matriks dan vektor untuk order n > 2
ANALISIS Diperlukan log n langkah setelah baris pertama matriks A dimasukkan pada prosesor “daun” agar v1 muncul dari prosesor “akar”. Kemudian diperlukan m-1 langkah hingga vm muncul dari ”akar”. Berarti prosedur MVTREE/ MULTITREE membutuhkan m–1+log(n) langkah. Karena digunakan 2n-1 prosesor, maka akan berjalan dalam waktu t(n) = O(n) ketika m ≤ n dan prosedur akan memiliki biaya O(n2). Dalam hal ini biaya adalah optimal jika dibandingkan dengan Ω(n 2 ) yaitu waktu yang dibutuhkan jika diproses secara berurutan [6].
425
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
PERKALIAN MATRIKS DENGAN MATRIKS MENGGUNAKAN KUBUS-TERHUBUNG Kubus didefinisikan sebagai kumpulan n prosesor, dimana n = 2q. Algoritma dirancang mengikuti arsitektur kubus-biner. Masing-masing n simpul mempunyai log n hubungan dengan simpul tetangganya [2]. Algoritma meliputi tiga tahap : 1. Unsur-unsur matriks A dan B didistribusikan ke seluruh n3 prosesor. Dilakukan penyimpanan elemen a dan b yang menghasilkan, A(i,j,k) = aji dan B(i,j,k) = bik 2. Hasil dari C(i,j,k) = A(i,j,k) x B(i,j,k) dihitung n
3. Jumlah
∑ C (i, j, k ) dihitung i =1
Algoritma diatas dinyatakan dalam prosedur PRODCUB (Lampiran-3). Berikut hasil program dari prosedur PRODCUB Output Program : Matrix Order 4x4 4x4 Matrik Input I 17 23 27 3 9 1 14 16 31 26 22 8 15 4 10 29 Matrix Input II -7 -25 -19 -5 -18 -30 -28 -12 -13 -21 -11 -32 -20 -2 -6 -24 The content of Proccessor for elemen A & B P(1)17 & -7 P(2)17 & -25 P(3)17 & -19 P(4)17 & -5 P(5)9 & -7 P(6)9 & -25 P(7)9 & -19 P(8)9 & -5 P(9)31 & -7
426
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
P(10)31 & -25 P(11)31 & -19 P(12)31 & -5 P(13)15 & -7 P(14)15 & -25 P(15)15 & -19 P(16)15 & -5 P(17)23 & -18 P(18)23 & -30 P(19)23 & -28 P(20)23 & -12 P(21)1 & -18 P(22)1 & -30 P(23)1 & -28 P(24)1 & -12 P(25)26 & -18 P(26)26 & -30 P(27)26 & -28 P(28)26 & -12 P(29)4 & -18 P(30)4 & -30 P(31)4 & -28 P(32)4 & -12 P(33)27 & -13 P(34)27 & -21 P(35)27 & -11 P(36)27 & -32 P(37)14 & -13 P(38)14 & -21 P(39)14 & -11 P(40)14 & -32 P(41)22 & -13 P(42)22 & -21 P(43)22 & -11 P(44)22 & -32 P(45)10 & -13 P(46)10 & -21 P(47)10 & -11 P(48)10 & -32 P(49)3 & -20 P(50)3 & -2
427
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
P(51)3 & -6 P(52)3 & -24 P(53)16 & -20 P(54)16 & -2 P(55)16 & -6 P(56)16 & -24 P(57)8 & -20 P(58)8 & -2 P(59)8 & -6 P(60)8 & -24 P(61)29 & -20 P(62)29 & -2 P(63)29 & -6 P(64)29 & -24 Matrix or Processor Ouput -944 -1688 -1282 -1297 -583 -581 -449 -889 -1131 -2033 -1607 -1363 -887 -763 -681 -1139 Terdapat N = n3 = 64 prosesor yang tersedia pada komputer SIMD kubus-terhubung, dinyatakan dalam tabel 1-a berikut, sesuai algoritma tahap 1 diatas. Pada tahap 2 diperoleh tabel 1-b. Tabel 1-c adalah hasil tahap 3 sekaligus hasil perkalian matriks.
428
Tabel 1-a 17 -7 9 -18 31 -13 15 -20
23 -25 1 -30 26 -21 4 -2
27 -19 14 -28 22 -11 10 -6
3 -5 16 -12 8 -32 29 -24
17 -7 9 -18 31 -13 15 -20
23 -25 1 -30 26 -21 4 -2
27 -19 14 -28 22 -11 10 -6
3 -5 16 -12 8 -32 29 -24
17 -7 9 -18 31 -13 15 -20
23 -25 1 -30 26 -21 4 -2
27 -19 14 -28 22 -11 10 -6
3 -5 16 -12 8 -32 29 -24
17 -7 9 -18 31 -13 15 -20
23 -25 1 -30 26 -21 4 -2
27 -19 14 -28 22 -11 10 -6
3 -5 16 -12 8 -32 29 -24
Tabel 1-b 17 -7 9 -18 31 -13 15 -20
17 -25 9 -30 31 -21 15 -2
17 -19 9 -28 31 -11 15 -6
17 -5 9 -12 31 -32 15 -24
23 -18 1 -18 26 -18 4 -18
23 -30 1 -30 26 -30 4 -30
23 -28 1 -28 26 -28 4 -28
23 -12 1 -12 26 -12 2412
27 -13 14 -13 22 -13 10 -13
27 -21 14 -21 22 -21 10 -21
27 -11 14 -11 22 -11 10 -11
Tabel 1-c -944 -583 -1131 -887
-1688 -581 -2033 -763
-1282 -449 -1607 -681
-1297 -889 -1363 -1139
27 -32 14 -32 22 -32 10 -32
3 -20 16 -20 8 -20 29 -20
3 -2 16 -2 8 -2 29 -2
3 -6 16 -6 8 -6 29 -6
3 -24 16 -24 8 -24 29 -24
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
ANALISIS Pada tahap 1 dan 3 terdiri dari q iterasi dengan waktu konstan, sementara tahap 2 mengambil waktu konstan. Setiap nilai c(i,j) adalah jumlah dari n elemen. Prosedur perkalian matriks kubus-terhubung berjalan dalam waktu t(n) = O(log n). Pada prosedur perkalian matriks dengan kubus-terhubung terdiri dari n3 prosesor, sehingga biaya yang dimiliki c(n) = O(n3 log(n)). Waktu pelaksanaan prosedur perkalian matriks secara berurutan adalah Ω(n) = n 3 [6], dengan biaya c(n) = O(n3). Berarti waktu pelaksanaan, prosedur perkalian matriks kubus-terhubung lebih cepat dibandingkan secara berurutan, namun dari segi biaya lebih tinggi.
KESIMPULAN Algoritma paralel merupakan salah satu metode penyelesaian bagi suatu permasalahan tertentu yang dirancang untuk komputer paralel. Dengan algoritma paralel, jumlah prosesor dapat dirancang sesuai dengan kebutuhan ditinjau dari faktor biaya. Alur instruksi dan data yang diproses dapat didistribusikan ke masing-masing prosesor. Simulasi operasi perkalian matriks dengan matriks dan matriks dengan vektor merupakan salah satu cara penerapan dalam algoritma paralel. Algoritma pada jaringan-interkoneksi dapat disimulasikan dalam model memori bersama dengan salah satu langkah antara lain Tree-Connection dan Cube- Connection. Waktu yang diperlukan pada pohon-terhubung jika dibandingkan dengan secara berurutan lebih singkat dan biaya lebih kecil atau sama. Pada kubus-terhubung, waktu pelaksanaan, lebih cepat dibandingkan secara berurutan, namun demikian dari segi biaya lebih tinggi.
DAFTAR PUSTAKA 1. AKL, SELIM G., The Design and Analysis of Parallel Algorithms, Prentice Hall, Inc., New Jersey, 1989. 2. DESROCHERS, GEORGE R., Principles of Parallel and Multiprocessing, McGraw-Hill Book Co., Singapore, 1988.
0
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
3. GRAMMATIKAKIS, MILTOS D.; FRANK HSU, D. AND KRAETZL, MIRO, Parallel System Interconnections and Communications, CRC Press LLC, New York, 2001. 4. LEWIS, TED G.; EL-REWINI, HISHAM, Introduction to Parallel Computing, Prentice Hall Int. Editions, 1992. 5. QUINN, MICHAEL J., Parallel Computing, Theory and Practice, Mc Graw-Hill Inc, Second Editions, 1994. 6. SURYADI, M.T., Pengantar Analisis Algoritma, penerbit Gunadarma, Jakarta, 1996.
DAFTAR RIWAYAT HIDUP 1. Nama
: Dra. Mike Susmikanti, MM
2. Tempat/Tanggal Lahir
: Jakarta, 12 November 1956
3. Instansi
: BATAN
4. Pekerjaan / Jabatan
: Staf PPIN-BATAN
5. Riwayat Pendidikan
:
• S1Matematika Statistik –FIPIA UI • S2 Magister Manajemen 6. Pengalaman Kerja
:
• 1980-sekarang , BATAN
1
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Lampiran-1 : Prosedur perkalian matriks m x n dengan vektor n x 1 khusus n = 2. Procedure MVTREE (A,U); var
A,TEMP : array[1..20, 1..20] of Integer; P,V,U : array[1..20] of Integer; I,J,K,L,M,N,IT,Root : Integer; FVar : Text; FName : String;
begin Writeln(FVar,'Process Tree Multiplication of Matrix & Vector :'); for I := 1 to M do begin for J := 1 to N do begin TEMP[I,J] := A[I,J]*U[J]; P[J] := TEMP[I,J]; writeLn(FVar,'P(',J,') : ',P[J]); end; end; for I := 1 to M do begin IT := 0; Root :=0; for J := N+1 to 2*N-1 do begin P[J] := TEMP[I,(J-N)+IT] + TEMP[I,(J-N)+IT+1]; WriteLn(FVar,'Processor(',J,') :',P[J]); IT := IT + 1; Root := P[J]; end; WriteLn(FVar,'Root(',I,') :',Root); V[I]:= Root; end; end
2
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Lampiran-2 : Prosedur perkalian matriks m x n dengan vektor n x 1 untuk n > 2. Procedure MULTITREE (A, U) ; var
A,TEMP : array[1..10, 1..10] of Integer; P,V,U : array[1..10] of Integer; I,J,K,L,M,N,IT,Root : Integer; FVar : Text; FName : String;
begin Writeln(Fvar,'Process Tree Multiplication of Matrix & Vector :'); for I := 1 to M do begin for J := 1 to N do begin TEMP[I,J] := A[I,J]*U[J]; P[J] := TEMP[I,J]; writeLn('Processor(',J,') : ',P[J]); writeLn(FVar,'Processor(',J,') : ',P[J]); end; end; for I := 1 to M do begin IT := 0; Root := 0; for J := N+1 to 2*N-1 do begin IF J < 2*N-1 then begin P[J] := TEMP[I,(J-N)+IT] + TEMP[I,(J-N)+IT+1]; WriteLn('Processor(',J,') :',P[J]); WriteLn(FVar,'Processor(',J,') :',P[J]); IT := IT + 1; Root := Root + P[J]; end; end; WriteLn('Root(',I,') :',Root); WriteLn(FVar,'Root(',I,') :',Root); V[I]:= Root; end; end;
3
Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (417-434)
Lampiran-3 : Prosedur perkalian matriks dengan matriks Procedure PRODCUB;
var
A,B,C : array[1..10, 1..10, 1..10] of integer; TOT : array[1..10, 1..10] of integer; i,j,k,n,idx : Integer; FVar : Text; FName : String;
begin for i := 1 to n do for j := 1 to n do for k := 1 to n do begin A[i,j,k] := A[1,j,k]; B[i,j,k] := B[1,j,k]; end; WriteLn(FVar,'The content of Proccessor for elemen A & B'); idx := 1; for i := 1 to n do for j := 1 to n do for k := 1 to n do begin A[i,j,k] := A[i,j,i]; B[i,j,k] := B[i,i,k]; WriteLn(FVar,'P(',idx,')',A[i,j,k],' & ',B[i,j,k]); idx := idx + 1; end; for i := 1 to n do for j := 1 to n do for k := 1 to n do begin C[i,j,k] := A[i,j,k]*B[i,j,k]; end; Writeln(FVar,'Matrix or Processor Ouput'); for j := 1 to n do for k := 1 to n do begin TOT[j,k] := 0; for i := 1 to n do begin TOT[j,k] := TOT[j,k] + C[i,j,k]; end; WriteLn(FVar,TOT[j,k]); end; end;
4