ARSITEKTUR KOMPUTER PARALEL
DAN
UKURAN KOMPLEKSITAS
I. PENDAHULUAN
Jumlah data yang didapat dari pendeteksian keadaan cuaca, polusi udara dan unsurunsur kimia lapisan bumi menunjukkan nilai rata-rata 1010 bit (binary digit) per detik. Sedangkan dalam operasi kedokteran dengan bantuan scanner (penyinaran), penyajian grafik rekonstruksi ruang dengan komputer baik dari data langsung yang didapat dari pemotongan melintang suatu organ tubuh maupun dari data pemutaran koordinat pada berbagai sudut pandang, minimal memerlukan kecepatan proses operasi hitung sebesar 1015 kali per detik.
Kedua contoh di atas mengungkapkan bahwa kita perlu merancang komputer cepat tipe paralel guna memproses data dalam ukuran besar dan dalam waktu singkat untuk berbagai bidang aplikasi, antara lain: kedokteran, klimatologi, penerbangan, eksplorasi, hankam, astronomi dan lain sebagainya. Hal ini disebabkan komputer sekuensial dipandang sangat terbatas kemampuannya untuk menyelesaikan kasus-kasus seperti kedua contoh tersebut.
Beberapa studi tentang komputer paralel telah diperkenalkan, baik yang bersifat arsitektur [Selim, 1989; Knob, 1990; Saad, 1990; Carmona, 1991; Jaja, 1992 dan Bertsekas, --] maupun dari segi kompleksitasnya [Golub, 1989; Schendel, 1984]. Dalam penyajian ini, kita membahas berbagai ragam arsitektur paralel dan ukuran kompleksitasnya antara komputer tipe sekuensial dan paralel. Tujuan membahas arsitektur adalah untuk mengetahui nilai efisiensi kerja prosesor pada berbagai model dari perancangan (arsitektur) komputer. Sedangkan tujuan membahas kompleksitas program adalah untuk mengetahui kecepatan eksekusi program, kecepatan komunikasi data dan jumlah minimal prosesor yang harus digunakan dalam menyelesaikan suatu masalah tertentu secara paralel.
II. PEMBAHASAN
2.1 Jenis-jenis Arsitektur Komputer
2.1.1 Komputer SISD
Gambar 1.a menyajikan arsitektur mesin komputer SISD (Single Instruction Single Data) dari model Von Neumann. Jenis ini merupakan komputer sekuensial dengan ciri pokok hanya memiliki satu prosesor (Schendel, 1984).
Skema kerja prosesor menurut gambar tersebut menunjukkan bahwa kemampuan mesin sekuensial dalam menjalankan eksekusi program, setiap operasi aritmatika ataupun logika dilakukan dalam satu unit kalkulasi. Hal ini disebabkan dalam setiap instruksi, mesin hanya mampu membaca data dalam sekali kerja. Oleh sebab itu dapat disimpulkan bahwa penggunaan mesin ini pada bidang aplikasi sangat terbatas, sebab kemampuan dari prosesornya terbatas. Contoh dari kelompok ini adalah jenis personal komputer (PC) dan mini komputer.
2.1.2 Komputer SIMD
Gambar 1.b menyajikan arsitektur mesin komputer SIMD (Single Instruction Multiple Data) dari jenis komputer paralel. Dari skema dapat dicirikan bahwa tipe ini terdapat N prosesor yang masing-masing prosesor dihubungkan dengan memori lokal sehingga data dan program dapat disimpan. Selain itu semua prosesor dikendalikan oleh satu unit kontrol (Knob, 1990).
Kemampuan pokok yang dimiliki oleh mesin ini menunjukkan bahwa pada saat yang sama, setiap prosesor mampu mengeksekusi instruksi-instruksi yang sama dari data yang berbeda. Mesin yang dapat dimasukkan dalam tipe ini antara lain ILLIAC IV, TAR-100, DRAY-1, STARAN IV dan ILC (memiliki 4096 prosesor).
2.1.3 Komputer MISD
Jenis yang ketiga adalah komputer paralel MISD (Multiple Instruction Single Data). Dalam gambar 1.c, mesin MISD memiliki satu unit memori. Kemampuan yang dimiliki untuk mengeksekusi program menunjukkan bahwa pada setiap saat, satu data dari memori dioperasikan oleh setiap prosesor menurut instruksi-instruksi dari setiap unit kontrol. Jadi secara paralel, satu data yang sama dapat diproses oleh prosesor-prosesor yang berlainan.
Secara struktural, mesin ini nampak ekivalen dengan mesin SISD. Hanya karena memiliki prosesor bebas lebih dari satu, maka mesin ini dapat dikatakan sebagai mesin multi-prosesor yang kemampuannya relatif masih terbatas untuk digunakan di bidang-bidang aplikasi.
2.1.4 Komputer MIMD
Model komputer MIMD (Multiple Instruction Multiple Data) merupakan jenis komputer paralel yang disajikan pada gambar 1.d. Mesin ini memiliki N prosesor bebas dan masing-masing prosesor mempunyai satu unit kontrol, sehingga mesin ini dapat kita sebut sebagai mesin multikomputer. Ciri lain yang ada pada mesin tersebut adalah prosesor-prosesornya saling bekerja sama dalam unit Input-Output dan memori utama, sehingga mesin ini dapat dikategorikan sebagai mesin multiprosesor.
Kemampuan mesin MIMD menunjukkan bahwa pada setiat saat, secara serentak prosesor-prosesor dapat menjalankan instruksi-instruksi yang berlainan secara paralel. Dari model susunan prosesornya, dapat disimpulkan bahwa komputer semacam ini dapat dimanfaatkan untuk aplikasi khusus guna memecahkan masalah yang membutuhkan operasi-operasi resolusi tinggi dan sangat kompleks.
2.2 Ukuran Kompleksitas
Misalkan diketahui masalah sederhana tentang menjumlahkan N data acak pada satu tabel data (array), maka algoritma untuk mesin sekuensial dan paralel dapat disusun sebagai berikut:
a). mesin sekuensial, satu prosesor:
Begin
jum := 0;
for i := 1 to n do
jum := jum + T(i);
End.
b). mesin paralel, N prosesor dan data sebanyak n = 2h terdapat dalam tabel T.
Begin
read(T(i),a);
write(a,B(i));
for h := 1 to log n do {penjelajahan jumlah}
if (i<= n/2h) then
Begin
read(B(2i-1),x);
read(B(2i),y);
z := x + y;
write(z,T(i));
End;
if i := 1 then write(z, jumlah);
End.
Pada kasus sekuensial, untuk mendapatkan jumlah bilangan dalam tabel data, operasioperasi biner dilakukan secara assosiatif berulang sebanyak (n-1) kali kalkulasi. Pada kasus paralel menunjukkan bahwa proses kalkulasi biner dilakukan dengan cara penjelajahan secara diagram pohon menurut graf berarah non-siklik. Dengan demikian ukuran kompleksitas algoritma komputer paralel tersebut dapat diterangkan melalui konsep-konsep dan prinsip-prisip yang ada pada teori graf berarah non-siklik.
Suatu graf berarah non-siklik didefinisikan sebagai pasangan (T,S) dengan T menyatakan himpunan titik dan S adalah himpunan segmen pada T. Himpunan segmen ini dapat juga kita pandang sebagai himpunan pasangan (i,j) dengan i dan j suatu titik dari anggota T. Dengan demikian setiap titik menyajikan suatu operasi hitung dari prosesor.
Segmen-segmen pada T tergantung dari data yang ada, artinya untuk setiap (i,j) , maka j tergantung dari hasil operasi yang ada di i.
Contoh kongkrit :
(x1 + x2 )(x2 + x3) = x1 x2 + x2
2 + x1 x3 + x2 x3 = r.
Model-1:
Data: x1 x2 x3
[x] [x] [x] [x]
x1 x2 x1 x3 x2
2 x2 x3
[+] [+]
x1 x2 + x2
2 x1 x3 + x2 x3
[+]
x1 x2 + x2
2 + x1 x3 + x2 x3 = r
Model-2:
Data: x1 x2 x3
[+] [+]
x1 + x2 x2 + x3
[x]
(x1 + x2)( x2 + x3) = r
Ukuran kompleksitas dapat dipandang sebagai kuantitas suatu sumber yang diperlukan untuk mengeksekusi program, yaitu menyangkut banyaknya prosesor, lama eksekusi dan banyaknya pesan atau informasi dari program. Dengan menggunakan metode graf nonsiklik, perhitungan kompleksitas dalam waktu t, diperlukan beberapa peristilahan berikut:
III. KESIMPULAN
Berdasarkan pembahasan, maka dapat disimpulkan bahwa:
a). penggunaan komputer sekuensial relatif sangat terbatas dalam aplikasi, sehingga perlu dikembangkan generasi jenis komputer paralel dalam bentuk arsitektur SIMD, MISD dan MIMD.
b). perbandingan kompleksitas mesin sekuensial terhadap mesin paralel dapat diukur melalui kecepatan eksekusi program dan efisiensi antara kedua jenis mesin komputer tersebut.
KEPUSTAKAAN
[1]. Bertsekas, D.P. dan Tsitsiklis, J.N. --, Parallel and Distributed Computation, Prentis Hall International Inc.,
[2]. Carmona, E.A. dan Rice, M.D. 1991, Modeling the Serial and Parallel Fraction of Parallel Algorithm, Journal of Parallel and Distributed Computing, No. 13 , P.286-298,
[3]. Golub, G.H. dan Loan, C.F.V. 1989, Matrix Computations, J.H. University Press,
[4]. Jaja, J. 1992, An Introduction to Parallel Algorithm, Addison-Wesley P.C.,
[5]. Knob, K. dkk. 1990, Data Optimization: Allocation of Array to Reduce Communication on SIMD Machine, Journal of Parallel and Distributed Computing Volume --, No. 8 , P.108-118,
[6]. Saad, Y dan Schuldz, M.H. 1990, Data Communication in Hypercubes, Journal of Parallel and Distributed Computing Volume --, No. 6, P.115-135,
[7]. Schendel, U. 1984, Introduction to Numerical Methods for Parallel Computer, E.H. Limited,
Tidak ada komentar:
Posting Komentar