TUGAS AKHIR MATA KULIAH PEMROSESAN PARALEL ALGORITME FOX UNTUK PERKALIAN MATRIKS. Disusun Oleh:

TUGAS AKHIR MATA KULIAH PEMROSESAN PARALEL ALGORITME FOX UNTUK PERKALIAN MATRIKS

Disusun Oleh: Kelompok 6 Auriza Rahmad Akbar Rifki Yusri Haidar Hasanul Fajri Nuras Fathoni Arief Musyaffa

G64050089 G64050964 G64051421 G64053198

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009

|i

Daftar Isi No Daftar Isi .............................................................................................................................. ii Daftar Gambar ................................................................................................................... iii 1.

Pendahuluan ............................................................................................................... 1 1.1. Latar Belakang .......................................................................................................... 1 1.2. Dasar Teori ............................................................................................................... 1 1.2.1. Algoritme Sekuensial........................................................................................ 1 1.2.2. Algoritme Paralel............................................................................................... 2

2. Metode Foster................................................................................................................. 4 2.1. Partisi Data ............................................................................................................... 4 2.2. Komunikasi ............................................................................................................... 5 2.3. Aglomerasi ............................................................................................................... 7 2.4. Mapping ................................................................................................................... 7 3.

Analisis Kerja dan Kompleksitas .................................................................................. 8 3.1 Kompleksitas ............................................................................................................. 9 3.1.1. Analisis Kompleksitas dalam Satu Iterasi .......................................................... 9 3.1.2. Kompleksitas Waktu dalam Satu Iterasi ........................................................... 9 3.1.3. Kompleksitas Waktu dalam 𝒑 Iterasi ............................................................. 9 3.2 Speedup .................................................................................................................... 9 3.3 Efisiensi ................................................................................................................... 10 3.4 Isoefisiensi ............................................................................................................... 10 3.4.1. Relasi Isoefisiensi ............................................................................................ 10 3.4.2. Fungsi Isoefisiensi ........................................................................................... 10

4. Kode Program ............................................................................................................... 12 4.1. Fungsi Utama (main) ............................................................................................. 12 4.2. Struct GRID_INFO_T ............................................................................................... 13 4.3. Struct LOCAL_MATRIX_T ........................................................................................ 13 4.4. Fungsi Setup_grid................................................................................................... 13 4.5. Fungsi Fox............................................................................................................... 14 Daftar Pustaka................................................................................................................... 15

| ii

Daftar Gambar Halaman Gambar 1. Proses Perkalian Matriks ................................................................................... 2 Gambar 2. Skema Blok Checkerboard ................................................................................. 2 Gambar 3. Pembagian blok-blok matriks untuk P=16 ........................................................ 4 Gambar 4. Proses broadcast pada prosesor 𝑨𝒊, 𝒊 ke prosesor lain yang sebaris............... 5 Gambar 5. Perkalian antara matriks 𝑻 (matriks 𝑨𝒊, 𝒊 yang telah di-broadcast) dan 𝑩 ...... 5 Gambar 6. Penggeseran (roll) tiap elemen ke atas pada matriks 𝑩 ................................... 6 Gambar 7. Proses broadcast dari prosesor 𝑨𝒊, (𝒊 + 𝟏)𝒎𝒐𝒅𝒑 ke prosesor lain yang sebaris. ................................................................................................................................ 6 Gambar 8. Perkalian antara matriks 𝑻 dan 𝑩 ..................................................................... 6

| iii

1. Pendahuluan 1.1. Latar Belakang Perkalian matriks merupakan salah satu masalah utama dalam perhitungan matriks. Terdapat beberapa algoritme paralel untuk melakukan operasi perkalian matriks ini. Beberapa diantaranya dilakukan berdasarkan pembagian blok checkerboard. Salah satu algoritme yang terkenal adalah algoritme Fox.

1.2. Dasar Teori Perkalian antara matriks 𝐴𝑚 ,𝑛 yang terdiri dari 𝑚 baris dan 𝑛 kolom dengan matriks 𝐵𝑛 ,𝑙 yang terdiri dari 𝑛 baris dan 𝑙 kolom akan menghasilkan matriks 𝐶 dengan 𝑚 baris dan 𝑙 kolom. Setiap elemen matriks C dihitung berdasarkan rumus: 𝑛−1

𝑐𝑖𝑗 =

𝑎𝑖𝑘 ∙ 𝑏𝑘𝑗 ,

0 ≤ 𝑖 < 𝑚, 0 ≤ 𝑗 < 𝑙.

𝑘=0

Seperti yang dapat dilihat pada persamaan di atas, setiap elemen matriks 𝐶 adalah hasil inner product dari baris terkait pada matriks 𝐴 dan kolom terkait pada matriks 𝐵. Algoritme mengeksekusi perkalian dan penjumlahan sebanyak 𝑚. 𝑛. 𝑙 pada elemen-elemen matriks asal. Pada kasus matriks persegi, dengan ukuran 𝑛 × 𝑛, jumlah operasi yang dieksekusi adalah sebesar Ο(𝑛3 ). Sebenarnya terdapat juga algoritme perkalian matriks sekuensial dengan kompleksitas komputasi yang lebih kecil (contoh: algoritme Strassen). Akan tetapi, mempelajari algoritme semacam itu membutuhkan usaha yang lebih besar dan demi kesederhanaan, akan digunakan algoritme sekuensial yang dijelaskan di atas sebagai dasar untuk pengembangan metode paralel. Diasumsikan bahwa semua matriks yang digunakan adalah matriks persegi dan berukuran 𝑛 × 𝑛.

1.2.1. Algoritme Sekuensial Algoritme perkalian matriks sekuensial mencakup tiga nested loop: float A[n][n]; float B[n][n]; float C[n][n]; int i,j,k; ... for (i=0; i
Algoritme tersebut merupakan sebuah prosedur iteratif dan menghitung barisbaris pada matriks 𝐶 secara sekuensial. Baris matriks 𝐶 dihitung per iterasi outer loop (variabel loop 𝑖). Hal ini ditunjukkan gambar di bawah:

|1

Gambar 1. Proses Perkalian Matriks

Dari gambar tersebut, dapat dilihat bahwa selama iterasi pertama variabel loop 𝑖, baris pertama matriks 𝐴 dan semua kolom matriks 𝐵 digunakan untuk menghitung elemen-elemen baris pertama matriks 𝐶 yang dihasilkan. Karena setiap elemen matriks 𝐶 adalah hasil perkalian skalar dari baris matriks 𝐴 dan kolom matriks 𝐵, maka diperlukan operasi sebanyak 𝑛2 (𝑐𝑛) untuk menghitung semua elemen matriks 𝐶 dengan 𝑐 adalah operasi dasar dalam perkalian matriks (dalam hal ini perkalian dan penambahan).

1.2.2. Algoritme Paralel Pengulangan operasi perhitungan yang sama untuk elemen matriks yang berbeda merupakan hal yang biasa terjadi untuk metode penghitungan matriks. Dalam hal ini, dapat dikatakan terdapat paralelisme data. Hasilnya, operasi untuk memparalelkan operasi matriks dapat direduksi pada hampir semua kasus dengan mendistribusikan matriks ke tiap prosesor yang ada. Pilihan dalam metode mendistribusikan matriks menentukan penggunaan metode komputasi paralel tertentu. Adanya skema distribusi data yang beragam menghasilkan beberapa algoritme paralel untuk melakukan perhitungan matriks. Metode distribusi matriks yang paling umum dan banyak digunakan terdiri atas pembagian data ke dalam beberapa larik (vertikal dan horizontal) atau bagian-bagian berbentuk persegi (sub-blok). Dalam pembagian sub-blok matriks checkerboard, matriks dibagi menjadi sekumpulan elemen persegi. Cara pembagiannya dijelaskan lebih lanjut pada bagian 2.1. yang membahas tentang partisi data. Tiap prosesor melakukan komputasi sub-bloknya masing-masing. Untuk mendapatkan gambaran secara umum mengenai skema ini, perhatikan gambar di bawah. Misalkan kita memiliki matriks berukuran 8 × 8 (𝑛 = 8) dan kita akan menggunakan 16 prosesor (𝑝 = 16) untuk menghitung perkalian matriks menggunakan skema checkerboard, maka setiap prosesor akan mendapatkan sub-blok 𝑛 yang berukuran sebesar 2 × 2 (𝑛 = 𝑝 = 2).

Gambar 2. Skema Blok Checkerboard

|2

Secara garis besar, algoritme Fox bekerja dalam 𝑝 iterasi. Dalam setiap iterasi terdapat tiga langkah, yaitu broadcast, multiply, dan roll. Algoritme Fox hampir sama dengan algoritme Cannon. Perbedaannya adalah pada algoritme Cannon pada langkah pertama menggunakan roll, sedangkan algoritme Fox menggunakan broadcast. Penjelasan lebih lanjut tentang algoritme Fox ini terdapat pada bagian 2.2. yang membahas mengenai komunikasi pada algoritme.

|3

2. Metode Foster 2.1. Partisi Data Misalkan kita ingin mengalikan dua buah matriks A dan B untuk membentuk matriks C. 𝐶 =𝐴∙𝐵 Diasumsikan semua matriks adalah persegi, sehingga algoritme Fox dapat digeneralisasi untuk memproses matriks persegi. Matriks input 𝐴 dan 𝐵 didekomposisi menjadi beberapa sub-blok persegi. Jika kita memiliki 𝑃 prosesor, kita memiliki sub-blok sebanyak 𝑃 baris dan kolom. Hal ini berarti 𝑃 juga harus berbentuk persegi. Satu sub-blok diberikan ke tiap prosesor dalam grid sesuai dengan struktur subblok. Algoritme Fox menjamin bahwa matriks output 𝐶 memiliki dekomposisi yang sama dengan matriks 𝐴 dan 𝐵. Jika 𝐴, 𝐵, dan 𝐶 berukuran 𝑛 × 𝑛, maka setiap prosesor menyimpan sub-blok berukuran 𝑛 × 𝑛, dengan 𝑛 = 𝑛/ 𝑝. Prosesor diberi label (𝑖, 𝑗), dengan 𝑖, 𝑗 = 0, 1, … , 𝑝 − 1. Jika 𝐶 𝑖,𝑗 adalah sub-blok pada posisi (𝑖, 𝑗), maka masalah perkalian matriks dapat dinyatakan dalam bentuk blok matriks: 𝑝−1

𝐶 𝑖,𝑗 =

𝐴𝑖,𝑛 𝐵𝑛,𝑗 𝑛=0

Berikut contoh struktur sub-blok untuk matriks A dengan P = 16 ( 𝑃 = 4). Setiap prosesor mengerjakan 1 sub-blok saja.

Gambar 3. Pembagian blok-blok matriks untuk 𝒑=16

|4

2.2. Komunikasi Algoritma Fox bekerja dengan urutan broadcast, multiply dan roll untuk setiap iterasinya. Berikut pseudocode dari algoritma Fox. set 𝐶 = 0 for (𝑠𝑡𝑎𝑔𝑒 = 0 ∶

𝑝 − 1) do

Tiap baris prosesor 𝑖, mem-broadcast sub-blok 𝐴𝑖,𝑗 ke prosesor lain pada baris yang sama, dengan 𝑗 = 𝑖 + 𝑠𝑡𝑎𝑔𝑒 𝑚𝑜𝑑 𝑝, setiap prosesor menyimpan subblok broadcast dalam sebuah array 𝑇 Kalikan sub-matriks temporer 𝑇 pada tiap prosesor dengan sub-blok 𝐵 sekarang dan tambahkan hasilnya ke 𝐶 Setiap prosesor mengirimkan sub-blok 𝐵 sekarang ke prosesor di atasnya dan menerima sub-blok dari prosesor di bawahnya dan dijadikan sebagai sub-blok 𝐵 sekarang yang baru. Wrap around dari atas ke bawah. end

Berdasarkan algoritma di atas, kita memerlukan broadcast parsial sepanjang baris dan roll (geser satu) pada kolom. Keduanya merupakan komunikasi kolektif. Rowbroadcast adalah broadcast pada sub-grup khusus dari prosesor. Roll dilakukan sebagai varian dari operasi MPI_Sendrecv dengan kondisi batas melingkar (wrapped). Terdapat juga fungsi MPI khusus untuk mendefinisikan mesh prosesor dua dimensi. Berikut ilustrasi dari komunikasi algoritma Fox. Stage 0 Row Broadcast

Gambar 4. Proses broadcast pada prosesor 𝑨𝒊,𝒊 ke prosesor lain yang sebaris

Multiply

Gambar 5. Perkalian antara matriks 𝑻 (matriks 𝑨𝒊,𝒊 yang telah di-broadcast) dan 𝑩

|5

Roll

Gambar 6. Penggeseran (roll) tiap elemen ke atas pada matriks 𝑩

Stage 1 Row broadcast

Gambar 7. Proses broadcast dari prosesor 𝑨𝒊,(𝒊+𝟏)𝒎𝒐𝒅

𝒑

ke prosesor lain yang sebaris.

Multiply

Gambar 8. Perkalian antara matriks 𝑻 dan 𝑩

Matriks hasil penggeseran dari matriks 𝐴, yaitu matriks 𝑇 dikalikan dengan matriks 𝐵 yang telah mengalami penggeseran. Hasil perkalian tadi kemudian dikalikan dengan matriks 𝐶 yang telah diperoleh sebelumnya.

|6

Tiga langkah di atas (broadcast, multiply dan roll) dilakukan dalam setiap stage sebanyak

𝑝 stage. Selanjutnya kita lihat hasil keseluruhan algoritme pada salah satu

blok, yaitu 𝐶 21 . 𝑠𝑡𝑎𝑔𝑒 = 0: 𝑠𝑡𝑎𝑔𝑒 = 1: 𝑠𝑡𝑎𝑔𝑒 = 2: 𝑠𝑡𝑎𝑔𝑒 = 3:

∴

𝑇= 𝐶= 𝑇= 𝐶= 𝑇= 𝐶= 𝑇= 𝐶=

𝐴22 ; 𝐵 = 𝐵21 𝐴22 𝐵21 𝐴23 ; 𝐵 = 𝐵31 𝐴22 𝐵21 + 𝐴23 𝐵31 𝐴20 ; 𝐵 = 𝐵01 𝐴22 𝐵21 + 𝐴23 𝐵31 + 𝐴20 𝐵01 𝐴21 ; 𝐵 = 𝐵11 𝐴22 𝐵21 + 𝐴23 𝐵31 + 𝐴20 𝐵01 + 𝐴21 𝐵11

𝐶 21 = 𝐴22 𝐵21 + 𝐴23 𝐵31 + 𝐴20 𝐵01 + 𝐴21 𝐵11

2.3. Aglomerasi Algoritme Fox menggunakan skema checkerboard yang merupakan perbaikan dari algoritme perkalian matriks paralel yang berdasarkan skema baris (rowwise). Dengan skema ini sub-tugas diaglomerasi ke dalam satu sub-blok yang diproses oleh satu prosesor. Dengan demikian tugas yang telah diaglomerasi memiliki biaya komputasi dan komunikasi yang sama untuk tiap prosesor. Skema ini juga meningkatkan lokalitas dari algoritme paralel, karena tiap prosesor memproses sub-bloknya masing-masing.

2.4. Mapping Strategi mapping yang digunakan didasari oleh karakteristik algoritme paralel. Karakeristik algoritme Fox antara lain: jumlah tugasnya statis, pola komunikasinya terstruktur, dan waktu komputasi tiap tugas konstan. Dari karakteristik tersebut, maka strategi mapping yang digunakan adalah mengaglomerasi tugas untuk meminimalkan komunikasi dan membuat satu tugas untuk tiap prosesor. Strategi ini sudah diterapkan dalam skema checkerboard. Tiap prosesor bertanggung jawab untuk menghitung hasil perkalian matriks pada satu sub-blok saja. Untuk mengeksekusi algoritme Fox dengan efisien, dimana sub-tugas dasar membentuk grid persegi dan komunikasi data terdiri atas transmisi blok sepanjang baris dan kolom grid sub-tugas, topologi jaringan seharusnya juga berbentuk grid persegi. Dalam kasus ini dimungkinkan untuk memetakan dengan mudah kumpulan sub-tugas ke dalam kumpulan prosesor dengan menempatkan sub-tugas dasar (𝑖, 𝑗) pada prosesor 𝑃 𝑖, 𝑗 . Struktur yang diperlukan untuk jaringan komunikasi data dapat disediakan pada level fisik, jika topologi jaringannya adalah grid atau graf komplit.

|7

3. Analisis Kerja dan Kompleksitas Dalam analisis kerja algoritme paralel, digunakan istilah sebagai berikut: Jumlah Prosesor, 𝑝: Jumlah unit pemrosesan yang sama pada komputer paralel untuk menyelesaikan suatu masalah. Ukuran Masalah, 𝑊: Waktu yang diperlukan algoritme serial untuk menyelesaikan masalah yang diberikan pada prosesor tunggal. Hal ini juga sama dengan jumlah total dari semua pekerjaan berguna yang dilakukan oleh seluruh prosesor ketika menyelesaikan masalah yang sama secara paralel menggunakan prosesor sebanyak 𝑝. Misalnya, untuk perkalian dua buah matriks 𝑛 × 𝑛, dapat dikatakan 𝑊 = 𝑂(𝑛3 ). Waktu Eksekusi Paralel, 𝑇𝑝 : Waktu yang diperlukan oleh sebanyak p prosesor untuk menyelesaikan masalah. Untuk sistem paralel yang diberikan, 𝑇𝑝 merupakan fungsi dari ukuran masalah dan banyak prosesor. Speedup Paralel, 𝑆: Perbandingan antara 𝑊 dengan 𝑇𝑝 Overhead Paralel Total, 𝑇𝑜 : Jumlah total dari keseluruhan overhead yang terjadi pada semua prosesor selama eksekusi paralel dari algoritme. Overhead ini termasuk biaya komunikasi, pekerjaan sampingan dan waktu idle sehubungan dengan sinkronisasi dan komponen serial dari algoritme. Untuk sistem paralel yang diberikan, 𝑇𝑝 biasanya merupakan fungsi dari ukuran masalah dan banyak prosesor dan sering dituliskan sebagai 𝑇0 𝑊, 𝑝 . Oleh karena itu, 𝑇0 𝑊, 𝑝 = 𝑝𝑇𝑝 − 𝑊. Efisiensi, 𝐸: Perbandingan antara 𝑆 dengan 𝑝. Oleh karena itu, 𝐸 = 𝑊 𝑝𝑇𝑝 = 1

𝑇𝑝

1+𝑊

Biaya Komunikasi Data, 𝑡𝑠 dan 𝑡𝑤 : Pada suatu komputer paralel dengan message passing, waktu yang dibutuhkan untuk menyelesaikan transfer dari suatu pesan yang mengandung 𝑚 words antara dua prosesor bersebelahan adalah 𝑡𝑠 + 𝑡𝑤∙ 𝑚, dengan 𝑡𝑠 merupakan waktu startup pesan, dan 𝑡𝑤 (waktu komunikasi per-word) sama dengan

𝑦 , 𝐵

dimana 𝐵 merupakan bandwidth

saluran komunikasi antar prosesor dalam byte/detik dan 𝑦 merupakan jumlah byte per word.

|8

3.1 Kompleksitas 3.1.1. Analisis Kompleksitas dalam Satu Iterasi Row-Broadcast (Logaritmik) 𝑠𝑡𝑒𝑝

𝑡𝑏𝑐𝑎𝑠𝑡 = log 𝑝 𝑡𝑠 +

𝑏𝑙𝑜𝑐𝑘 𝑠𝑖𝑧𝑒 𝑛 𝑛 ⋅ 𝑝 𝑝

⋅ 𝑡𝑤

= log 𝑝 𝑡𝑠 +

𝑛2 𝑡 𝑝 𝑤

Block Multiply 𝑡𝑚𝑢𝑙𝑡 =

𝑛 𝑝

⋅

𝑛 𝑝

⋅

𝑛 𝑝

=

𝑛3 𝑝 𝑝

Column Roll 𝑏𝑙𝑜𝑐𝑘 𝑠𝑖𝑧𝑒

𝑡𝑟𝑜𝑙𝑙 = 𝑡𝑠 +

𝑛

𝑝

⋅

𝑛

𝑝

⋅ 𝑡𝑤 = 𝑡𝑠 +

𝑛2 𝑡 𝑝 𝑤

3.1.2. Kompleksitas Waktu dalam Satu Iterasi 𝑇1 = 𝑡𝑏𝑐𝑎𝑠𝑡 + 𝑡𝑚𝑢𝑙𝑡 + 𝑡𝑟𝑜𝑙𝑙 =

𝑛3 𝑝 𝑝

+ (log 𝑝 + 1) 𝑡𝑠 +

𝑛2 𝑝

=

𝑛3 𝑝 𝑝

+ log 2 𝑝 𝑡𝑠 +

𝑛2 𝑝

⋅ 𝑡𝑤

=

𝑛3 𝑝 𝑝

+ log 4𝑝 𝑡𝑠 +

𝑛2 𝑝

⋅ 𝑡𝑤

⋅ 𝑡𝑤

3.1.3. Kompleksitas Waktu dalam 𝒑 Iterasi 𝑇𝑃 = 𝑇1 ⋅ 𝑝 = 𝑇𝑃 =

𝑛3 + log 4𝑝 𝑝 𝑛3 𝑝

𝑝. 𝑡𝑠 +

𝑛2

+ 𝑝 log 4𝑝 . 𝑡𝑠 +

𝑐𝑜𝑚𝑝

𝑝 𝑛2 𝑝

⋅ 𝑡𝑤 log 4𝑝 . 𝑡𝑤

𝑐𝑜𝑚𝑚𝑢𝑛𝑖𝑐𝑎𝑡𝑖𝑜𝑛

3.2 Speedup 𝑆=

𝑊 = 𝑇𝑃 𝑛3 𝑝 +

𝑛3 𝑝 log 4𝑝 . 𝑡𝑠 +

𝑛2 log 4𝑝 . 𝑡𝑤 𝑝

|9

3.3 Efisiensi 𝐸=

𝑊 𝑛3 = 𝑝𝑇𝑝 𝑛3 + 𝑝 𝑝 log 4𝑝 . 𝑡𝑠 + 𝑛2 𝑝 log 4𝑝 . 𝑡𝑤

3.4 Isoefisiensi 3.4.1. Relasi Isoefisiensi Untuk mempertahankan efisiensi yang konstan, 𝑊 harus proporsional terhadap 𝑇𝑂 𝑊, 𝑝 , atau relasi di bawah ini harus terpenuhi: 𝑊 = 𝐾𝑇𝑂 𝑊, 𝑝 𝐸

Di sini 𝐾 = 1−𝐸 adalah konstan, tergantung pada efisiensi yang ingin dipertahankan. Persamaan di atas adalah relasi utama yang digunakan untuk menentukan fungsi isoefisiensi. Overhead Total 𝑇𝑂 𝑊, 𝑝 = 𝑝. 𝑇𝑃 − 𝑊 = 𝑝1.5 . log(4𝑝)0.5 . 𝑡𝑠 + 𝑛2 𝑝0.5 . log(4𝑝)0.5 . 𝑡𝑤 𝑠𝑡𝑎𝑟𝑡𝑢𝑝

𝑑𝑎𝑡𝑎 𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟

Isoefisiensi Terhadap 𝒕𝒔 𝑛3 = 𝑊 ∝ 𝐾. 𝑝1.5 . log(4𝑝)0.5 . 𝑡𝑠 Isoefisiensi Terhadap 𝒕𝒘 𝑛3 = 𝑊 ∝ 𝐾. 𝑛2 𝑝0.5 . log(4𝑝)0.5 . 𝑡𝑤 ⇒ 𝑛 ∝ 𝐾. 𝑝0.5 . log(4𝑝)0.5 . 𝑡𝑤 ⇒ 𝑛3 = 𝑊 ∝ 𝐾 3 . 𝑝1.5 . log 3 (4𝑝)0.5 . 𝑡𝑤 3

3.4.2. Fungsi Isoefisiensi Fungsi efisiensi dalam sistem paralel umumnya berupa fungsi polinomial dari 𝑝, yaitu Ο(𝑝 𝑥 ), dimana 𝑥 < 1. Pangkat 𝑝 yang kecil dalam fungsi esoefisiensi menandakan skalabilitas yang tinggi. Menurut persamaan isoefisiensi di atas dari 𝑡𝑠 dan 𝑡𝑤 , fungsi isoefisiensi asimtotik untuk algoritme Fox adalah Θ 𝑝1.5 . log 3 (4𝑝)0.5 . Fungsi isoefisiensi ini didapat dari algoritme Fox yang menggunakan skema broadcast logaritmik dengan fungsi MPI_Bcast.

| 10

Menurut Fox et al. hasil tersebut dapat ditingkatkan dengan menggunakan skema pipe-broadcast sehingga menghasilkan fungsi efisiensi Ο 𝑝1.5 . Terlebih lagi jika komunikasi dilakukan dengan cara asynchronous, komunikasi dan komputasi dapat dilakukan bersamaan, sehingga mengurangi waktu eksekusi sampai hampir dua kali lebih cepat daripada algoritme Cannon. Fungsi isoefisiensi di atas berarti jika jumlah prosesor bertambah dari 𝑝 menjadi 𝑝′, ukuran masalah 𝑊 (dalam hal ini 𝑛3 ) harus bertambah sebesar 𝑝′1.5 𝑝1.5 kali lipat untuk mendapatkan efisiensi yang sama seperti dengan jumlah prosesor sebanyak 𝑝. Misalnya jumlah prosesor bertambah dari 4 menjadi 16, maka ukuran masalah harus bertambah sebesar 64/8 = 8 kali lipat. Atau dengan kata lain ukuran matriks (𝑛) harus bertambah sebanyak dua kali lipat (8𝑛3 = (2𝑛)3 ).

| 11

4. Kode Program Kode program yang ditampilkan hanyalah modul utama dari program paralel. Beberapa fungsi pembantu tidak ditampilkan. Meskipun demikian, proses algoritme Fox dapat dipahami tanpa menampilkan fungsi tersebut.

4.1. Fungsi Utama (main) Fungsi utama mengimplementasikan skema komputasi dengan pemanggilan sekuensial pada subprogram yang diperlukan. LOCAL_MATRIX_T* temp_mat; int main(int argc, char* argv[]) int p; // int my_rank; // GRID_INFO_T grid; // LOCAL_MATRIX_T* local_A; LOCAL_MATRIX_T* local_B; LOCAL_MATRIX_T* local_C; int n; // int n_bar; //

{ Number of processes Rank of process Grid info of process

Order of matrix Order of submatrix

void Setup_grid(GRID_INFO_T* grid); void Fox(int n, GRID_INFO_T* grid, LOCAL_MATRIX_T* local_A, LOCAL_MATRIX_T* local_B, LOCAL_MATRIX_T* local_C); MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Comm_size(MPI_COMM_WORLD, &p); Setup_grid(&grid); // Setup the grid info of process if (my_rank == 0) { printf("What's the order of the matrices?\n"); scanf("%d", &n); } MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); n_bar = n/grid.q; local_A = Local_matrix_allocate(n_bar); Order(local_A) = n_bar; Generate_matrix("Generate A", local_A, &grid, n); Print_matrix("Matrix A =", local_A, &grid, n); local_B = Local_matrix_allocate(n_bar); Order(local_B) = n_bar; Generate_matrix("Generate B", local_B, &grid, n); Print_matrix("Matrix B =", local_B, &grid, n); Build_matrix_type(local_A); temp_mat = Local_matrix_allocate(n_bar); local_C = Local_matrix_allocate(n_bar); Order(local_C) = n_bar; Fox(n, &grid, local_A, local_B, local_C); Print_matrix("The product is", local_C, &grid, n); Free_local_matrix(&local_A); Free_local_matrix(&local_B); Free_local_matrix(&local_C); return MPI_Finalize(); }

| 12

4.2. Struct GRID_INFO_T Struktur ini menyimpan informasi grid, sehingga pengiriman parameter pada fungsi lebih singkat dan mudah. typedef struct GridInfo { int p; /* Total number of processes MPI_Comm comm; /* Communicator for entire grid MPI_Comm row_comm; /* Communicator for my row MPI_Comm col_comm; /* Communicator for my col int q; /* Order of grid int my_row; /* My row number int my_col; /* My column number int my_rank; /* My rank in the grid comm } GRID_INFO_T;

*/ */ */ */ */ */ */ */

4.3. Struct LOCAL_MATRIX_T Struktur ini menyimpan informasi matriks, sehingga pengoperasian matriks menjadi lebih mudah. #define MAX 65536 typedef struct LocalMatrix { int n_bar; #define Order(A) ((A)->n_bar) float entries[MAX]; #define Entry(A,i,j) (*(((A)->entries) + ((A)->n_bar)*(i) + (j))) } LOCAL_MATRIX_T;

4.4. Fungsi Setup_grid Fungsi ini akan membuat komunikator dua dimensi dalam grid persegi, menentukan koordinat tiap prosesor, dan membuat komunikator untuk tiap baris dan kolom secara terpisah. void Setup_grid( GRID_INFO_T* int old_rank; int dimensions[2]; int wrap_around[2]; int coordinates[2]; int free_coords[2];

grid

/* out */) {

/* Set up Global Grid Information */ MPI_Comm_size(MPI_COMM_WORLD, &(grid->p)); MPI_Comm_rank(MPI_COMM_WORLD, &old_rank); /* We assume p is a perfect square */ grid->q = (int) sqrt((double) grid->p); dimensions[0] = dimensions[1] = grid->q; /* We want a circular shift in second dimension. */ /* Don't care about first */ wrap_around[0] = wrap_around[1] = 1; MPI_Cart_create(MPI_COMM_WORLD, 2, dimensions, wrap_around, 1, &(grid->comm)); MPI_Comm_rank(grid->comm, &(grid->my_rank)); MPI_Cart_coords(grid->comm, grid->my_rank, 2, coordinates); grid->my_row = coordinates[0];

| 13

grid->my_col = coordinates[1]; /* Set up row communicators */ free_coords[0] = 0; free_coords[1] = 1; MPI_Cart_sub(grid->comm, free_coords, &(grid->row_comm)); /* Set up column communicators */ free_coords[0] = 1; free_coords[1] = 0; MPI_Cart_sub(grid->comm, free_coords, &(grid->col_comm)); }

4.5. Fungsi Fox Fungsi ini akan menjalankan algoritme Fox untuk perkalian matriks. Pada tiap stage dilakukan tiga langkah, yaitu broadcast, multiply, dan roll. void Fox( int GRID_INFO_T* LOCAL_MATRIX_T* LOCAL_MATRIX_T* LOCAL_MATRIX_T* LOCAL_MATRIX_T* int int int int int MPI_Status

n grid local_A local_B local_C

/* /* /* /* /*

in in in in out

*/, */, */, */, */) {

temp_A; /* Storage for the sub/* matrix of A used during /* the current stage stage; bcast_root; n_bar; /* n/sqrt(p) source; dest; status;

*/ */ */ */

n_bar = n/grid->q; Set_to_zero(local_C); /* Calculate addresses for circular shift of B */ source = (grid->my_row + 1) % grid->q; dest = (grid->my_row + grid->q - 1) % grid->q; /* Set aside storage for the broadcast block of A */ temp_A = Local_matrix_allocate(n_bar); for (stage = 0; stage < grid->q; stage++) { bcast_root = (grid->my_row + stage) % grid->q; if (bcast_root == grid->my_col) { MPI_Bcast(local_A, 1, local_matrix_mpi_t, bcast_root, grid->row_comm); Local_matrix_multiply(local_A, local_B, local_C); } else { MPI_Bcast(temp_A, 1, local_matrix_mpi_t, bcast_root, grid->row_comm); Local_matrix_multiply(temp_A, local_B, local_C); } MPI_Sendrecv_replace(local_B, 1, local_matrix_mpi_t, dest, 0/* sendtag*/, source, 0/*recvtag*/, grid->col_comm, &status); } }

| 14

Daftar Pustaka Fox G. 2005. Parallel Matrix Multiplication and other Full Matrix Algorithms. Indiana: Indiana University Gupta A, Kumar V. Scalability of Parallel Algorithm for Matrix Multiplication. Minnesota: University of Minnesota Quinn M. 2003. Parallel Programming in C With MPI and OpenMP. New York : McGraw Hill

| 15