Sk no. 92 / Dikti / Kep / 1996


download 40.89 Kb.
jenengSk no. 92 / Dikti / Kep / 1996
KoleksiDokumen
t.kabeh-ngerti.com > Gambar > Dokumen
UNIVERSITAS GUNADARMA

SK No. 92 / Dikti / Kep / 1996

Fakultas Ilmu Komputer, Teknologi Industri, Ekonomi,
Teknik Sipil & Perencanaan, Psikologi, Sastra



Soal Ujian Akhir Semester


Mata Kuliah

: Algoritma Pengolahan Paralel

Tanggal

: / / 2005

Fakultas

: Teknik Industri

Waktu

: 60 Menit

Jenjang / Jurusan

: S1 / Informatika

Dosen

:

Tingkat / Kelas

: IV / 4IA01-12

Sifat

: Tutup Buku

Semester / Tahun

: ATA 2004/2005

Jumlah Soal

: 40 soal pilihan berganda


Pilihlah jawaban yang benar!


  1. Yang mana dari kelas komputer di bawah ini yang tidak termasuk komputer paralel:

a. SIMD b. MISD c. SISD d. MIMD
2. Transaksi pada satu nomer rekening bank dapat dilakukan dari berbagai kantor cabang, ATM, dsb., tetapi rekapitulasi transaksi tersebut hanya dapat dilihat oleh pihak yang berwenang. Metode seperti ini disebut:

a. Exclusive-Read, Exclusive-Write (EREW)

b. Concurrent-Read, Exclusive-Write (CREW)

c. Concurrent-Read, Concurrent-Write (CRCW)

d. Exclusive-Read, Concurrent-Write (ERCW)
3. Prosesor yang terletak di sudut-sudut SIMD Mesh N prosesor, memiliki jalur ke ..... prosesor lainnya:

a. 2 b. 4 c. 2 N d. N
4. Yang mana yang BENAR dari pernyataan tentang SIMD Tree Connection di bawah ini:

a. Setiap prosesor hanya bisa berkomunikasi dengan tingkat di bawah (children) –nya.

b. Setiap prosesor terhubung dengan 3 prosesor lainnya.

c. Semua prosesor terhubung dengan root.

d. Jalur dari parent ke children hanya satu arah.
5. Jumlah prosesor pada SIMD Perfect Shuffle Connection adalah:

a. Kelipatan 2 b. Pangkat dari 2

c. Bisa berapa saja d. Kuadrat suatu bilangan
6. Perbedaan Perfect Shuffle dengan Shuffle Exchange adalah:

a. Jalur Perfect Shuffle satu arah, sedangkan Shuffle Exchange dua arah.

b. Jalur-jalur satu arah pada Perfect Shuffle ditambah lagi dengan jalur dua arah prosesor genap dengan prosesor sesudahnya untuk membentuk Shuffle Exchange.

c. Semua prosesor pada Perfect Shuffle terhubung ke semua prosesor lainnya, sedangkan pada Shuffle Exchange hanya ke prosesor di sebelahnya.

d. Jalur-jalur satu arah pada Perfect Shuffle dibalik arahnya untuk membentuk Shuffle Exchange.
7. Komputer paralel MIMD dengan memori bersama disebut:

a. Multicomputers b. loosely coupled machines

c. distributed systems d. tightly coupled machines
8. Yang mana dari taksonomi paralel berikut ini yang bekerja secara asinkron:

a. Array b. Systolic c. SIMD d. MIMD
9. Multiprosesor pipeline dengan data didistribusikan dari memori ke array prosesor sebelum kembali ke memori merupakan komputer paralel dengan paradigma:

a. Systolic b. MIMD c. reduksi d. Graf
10. Yang merupakan kontribusi paradigma systolic terhadap kinerja komputer paralel adalah, kecuali:

a. distribusi dan partisi data.

b. mereduksi delay yang disebabkan oleh input/output dan referensi memori.

c. kecepatan yang sangat tinggi dengan menghindari bottleneck input/output.

d. implementasi lock.
11. Graf untuk implementasi paradigma reduksi memiliki node paling bawah yang terdiri dari:

a. nilai b. operator

c. nilai dan operator d. sign, nilai dan operator
12. Yang dimaksud dengan speedup adalah:

a. jumlah hasil pemrosesan yang dikeluarkan per satuan waktu.

b. pembagian tahap komputasi dengan output satu segmen merupakan input bagi segmen yang lain.

c. manipulasi concurrent data yang menjadi bagian dari satu atau lebih proses yang menyelesaikan satu masalah.

d. rasio antara waktu yang diperlukan untuk melakukan komputasi dengan algoritma sekuensial, dengan waktu yang diperlukan untuk melakukan hal yang sama dengan algoritma paralel.
13. Algoritma paralel yang baik adalah yang:

a. meminimalkan jumlah iterasi.

b. memaksimalkan jumlah prosesor yang terpakai.

c. meminimalkan jumlah komunikasi yang dilaksanakan setiap prosesor.

d. meminimalkan jumlah baris algoritma tersebut.
14. Algoritma PRAM memiliki dua fase, yaitu:

a. mengirimkan data, kemudian setiap prosesor mengolah data yang diterimanya.

b. mengolah data dan mengirimkannya ke semua prosesor lain.

c. mengaktifkan prosesor dan mengirimkan data.

d. mengaktifkan sejumlah prosesor, kemudian prosesor tersebut melakukan komputasi secara paralel.
15. Instruksi meta pada PRAM untuk mengaktifkan prosesor yang digunakan adalah:

a. for all
b. for all


do do

activate spawn

endfor endfor
c. spawn () d. activate ()
16. Algoritma EREW PRAM reduksi paralel untuk penjumlahan n nilai yang diimplementasikan dengan array yang dapat digambarkan dengan pohon biner, memerlukan prosesor sebanyak:

a. log n b.  n/2 c. n/2 d. n/2
17. Kompleksitas algoritma pada no. 16 di atas adalah:

a. (n/2) b. (log n) c. ( n/2) d. (n/2)
18. Perulangan for yang sekuensial pada algoritma no. 16 adalah sebanyak:

a. n/2 kali b.  n/2 kali

c. log n kali d. n/2 kali
19. Salah satu aplikasi prefix sum adalah untuk:

a. konversi bilangan.

b. kompresi data.

c. menampilkan kode ASCII.

d. memisahkan satu tipe data dari tipe yang lainnya.
20. Pada algoritma preorder tree traversal, setiap edge akan terlewati sebanyak:

a. 1 kali b. p kali (p = jumlah node)

c. n kali (n = jumlah data) d. 2 kali
21. Dua deret bilangan A dan B yang terurut naik, masing-masing dengan n bilangan, digabung (merge) menjadi satu. Algoritma sekuensial memerlukan waktu:

a. O(n) b. O(2n) c. O(n) d. O(3n)
22. Kekurangan (n, n)-merging network dibandingkan komputer sekuensial terdapat pada aspek:

a. biaya b. jumlah rekursi

c. running time d. jumlah iterasi
23. Jika p(2n) menyatakan jumlah comparator dan t(2n) menunjukkan waktu yang diperlukan oleh (n, n)-merging network untuk melakukan merge dua deret yang panjangnya masing-masing n, biaya yang diperlukan sama dengan:

a. p(2n) x t(2n) b. p(2n)

c. t(2n) d. p(2n) / t(2n)
24. Dari no. 23, jika p(2n) = 1 + n log n, dan t(2n) = 1 + log n, biaya yang diperlukan adalah:

a. O(1 + log n) b. O(1 + n log n)

c. O(log n) d. O(n log2 n)
25. Syarat awal (n, n)-merging network adalah:

a. n harus merupakan bilangan pangkat 2.

b. n tidak boleh lebih dari 20.

c. Kedua deret harus urut turun.

d. Kedua deret harus sudah berurut.
26. Worst case untuk proses searching deret yang terdiri dari n elemen dengan algoritma sekuensial adalah:

a. O(2n) b. O(n/2) c. O(log n) d. O(n)
27. Search elemen x pada deret terurut S yang terdiri dari n elemen dengan N prosesor komputer EREW SM SIMD dilakukan dengan:

a. semua prosesor membaca S seluruhnya.

b. setiap prosesor membaca satu elemen.

c. S dibagi dua bagian: high dan low

d. membagi S sebanyak N, masing-masing dengan panjang n/N.
28. Untuk searching deret acak dengan EREW, setiap prosesor membaca:

a. data dari prosesor lain b. subsequence bagiannya

c. belum tentu mendapat data d. semua data
29. Yang mana dari pernyataan mengenai searching deret acak di bawah ini yang tidak benar:

a. CRCW lebih baik dari EREW.

b. ERCW lebih baik dari CRCW.

c. Sequential search lebih baik dari EREW.

d. EREW lebih baik dari CRCW.
30. Prosesor dengan identitas 000 pada SIMD Cube Connection akan terhubung dengan prosesor:

a. 001, 011, 111 b. 010, 100, 000

c. 010, 100, 111 d. 001, 010, 100
Gunakan algoritma berikut ini untuk soal no. 31 s/d 35
SUM(EREW PRAM)

Initial condition : List of n≥1 elements stored in A[0 ... (n-1)]

Final condition : Sum of elements stored in A[0]

Global variables : n, A[0 ... (n-1)], j

begin

spawn (P0, P1, P2, ..., )

for all Pi where 0≤i do

for j←0 to do

if i modulo 2j = 0 and 2i + 2j < n then

A[2i] ← A[2i] + A[2i + 2j]

endif

endfor

endfor

end
31. Yang dilakukan oleh algoritma di atas adalah:

a. Merging 2 deret yang masing-masing terdiri dari n elemen

b. Menghitung sisa pembagian dua elemen

c. Menghitung log n

d. Menjumlahkan n elemen


  1. Jika n = 10, prosesor yang dipakai sebanyak:

a. 10 b. 9 c. 5 d. 4
33. Loop for j←0 to do ... endfor, dilakukan oleh:

a. Semua prosesor secara sekuensial b. Prosesor genap saja

c. Semua prosesor secara paralel d. Prosesor ganjil saja
34. Untuk i = 7 dan j = 1:

a. A[2i] ← A[2i] + A[2i + 2j] dilakukan

b. Nilai kebenaran i modulo 2j = 0 adalah TRUE

c. A[2i] ← A[2i] + A[2i + 2j] tidak dilakukan

d. Loop j berjalan 7 kali
35. Untuk n = 10, j akan bernilai:

a. Dari 0 s/d 10 b. Dari 0 s/d 3

c. Dari 0 s/d 9 d. Dari 1 s/d 4

Konfigurasi paralel berikut ini digunakan untuk transpose matriks 4x4. Gunakan gambar ini untuk soal no. 36 s/d 40.




P11 P12 P13 P14







P21 P22 P23 P24







P31 P32 P33 P34



P41 P42 P43 P44
36. Jika ordo matriks adalah n x n, jumlah unit prosesor yang diperlukan untuk transpose adalah:

a. log n b. n2 c. n3 d. n
37. Dengan aliran data yang digambarkan di atas, setiap prosesor harus memiliki register sebanyak:

a. 4 b. 3 c. 16 d. 1


  1. Waktu yang diperlukan untuk menjalankan algoritma paralel yang dilakukan oleh gambar di atas sebanding dengan:

a. n2 b. log n c. n d. n3
39. procedure TRANSPOSE (A)

for i = 2 to n do

for j = 1 to i-1 do

aijaji

end for

end for.

Loop j akan dilakukan satu kali saja, jika nilai i sama dengan:

a. 1 b. 3 c. 4 d. 2


  1. Mana yang benar dari pernyataan di bawah ini:

a. Algoritma pada no. 39 tidak dapat berjalan pada konfigurasi prosesor 2 dimensi di atas.

b. Algoritma pada no. 39 dapat berjalan pada konfigurasi tersebut..

c. Algoritma tersebut hanya dapat berjalan pada shuffle exchange.

d. Algoritma ini bisa berjalan pada semua konfigurasi paralel.

Share ing jaringan sosial


Similar:

U niversitas gunadarma sk no. 92 / Dikti / Kep / 1996

U niversitas gunadarma sk no. 92 / dikti / Kep /1996

U niversitas gunadarma sk no. 92 / dikti / Kep /1996

Tengen


Nalika Nyalin materi nyedhiyani link © 2000-2017
kontak
t.kabeh-ngerti.com
.. Home