Algoritma & Pengolahan Paralel

 

Algoritma & Pengolahan Paralel

 

 

1. Yang mana yang BENAR dari pernyataan tentang SIMD Tree Connection di bawah ini:

Setiap prosesor terhubung dengan parent dan, jika ada, children-nya. 

 

2.       Prosesor yang terletak di sudut-sudut SIMD Mesh N prosesor, memiliki jalur ke ..... prosesor lainnya:

 2 

3.       Jika p(2n) = 1 + n log n menyatakan jumlah comparator dan t(2n) = 1 + log menunjukkan waktu yang diperlukan oleh (n, n)-merging network untuk melakukan merge dua deret yang panjangnya masing-masing n, biaya yang diperlukan adalah:

O(n log2 n) 

 

4.       Yang dimaksud dengan speedup adalah:

rasio antara waktu yang diperlukan untuk melakukan komputasi dengan algoritma sekuensial, dengan waktu yang diperlukan untuk melakukan hal yang sama dengan algoritma paralel. 

 

5.       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:

p(2n) x t(2n) 

 

6.       Analisis waktu yang diperlukan oleh algoritma paralel dibagi menjadi 2 bagian yaitu:

waktu komputasi dan waktu komunikasi 

 

7.       Syarat awal (n, n)-merging network adalah:

n harus merupakan bilangan pangkat 2. 

8.       Pada komputer paralel dengan sistem interconnection network, prosesor satu dengan prosesor lainnya terhubung melalui:

Jaringan 

 

9.       Perulangan for yang sekuensial pada algoritma EREW PRAM reduksi paralel untuk penjumlahan n nilai yang diimplementasikan dengan array yang dapat digambarkan dengan pohon biner, adalah sebanyak:

log n kali 

 

10.   Komputer SM MIMD dikenal juga dengan istilah:

Tightly coupled machine 

 

11.   Algoritma EREW PRAM reduksi paralel untuk penjumlahan n nilai yang diimplementasikan dengan array yang dapat digambarkan dengan pohon biner, memiliki kompleksitas yang setara dengan:

log n 

 

12.   Algoritma PRAM memiliki dua fase, yaitu:

mengaktifkan sejumlah prosesor, kemudian prosesor tersebut melakukan komputasi secara paralel. 

 

13.   Message passing di mana prosesor master mengirim data yang sama ke semua prosesor lain, termasuk dirinya sendiri disebut:

broadcast 

 

14.   Penyelesaian persamaan simultan linier dengan sistem pengolahan paralel membutuhkan prosesor sebanyak:

bisa berapa saja 

 

15.   Penyelesaian persamaan simultan linier dengan sistem pengolahan paralel dilakukan dengan pendekatan yang sama dengan operasi:

matriks 

 

16.   Dalam membandingkan kinerja suatu algoritma pada mesin paralel, satuan ukuran yang paling tepat adalah:

Cost 

 

17.   Sistem paralel yang berupa multikomputer lebih disukai karena, kecuali:

digunakan secara dedicated 

 

18.   Perbedaan Perfect Shuffle dengan Shuffle Exchange adalah:

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

 

19.   Instruksi dasar pada algoritma transpose matriks EREW adalah:

pertukaran tempat antara 2 elemen 

 

20.   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:

Exclusive-Read, Concurrent-Write (ERCW) 

 

21.   Worst case untuk proses searching deret yang terdiri dari n elemen dengan algoritma sekuensial adalah:

O(n) 

 

22.   Berdasarkan konsep data stream dan instruction stream, arsitektur komputer dibedakan menjadi

SISD, SIMD, MISD, MIMD 

 

23.   Urutan konfigurasi paralel untuk melaksakan transpose matriks dari yang paling baik ke yang paling buruk dalam hal biaya (cost) adalah:

EREW-shuffle-mesh 

 

24.   Tightly couple machine sering juga disebut dengan istilah:

Multiprocessors 

 

25.   Konfigurasi tree untuk implementasi algoritma pre-order memiliki node paling bawah yang terdiri dari:

nilai 

 

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

SISD 

 

27.   Komputer paralel MIMD dengan memori bersama disebut:

tightly coupled machines 

 

28.   Jumlah prosesor pada SIMD Perfect Shuffle Connection adalah:

Pangkat dari 2 

 

29.   Konfigurasi sistem paralel yang tidak menggambarkan prosesor dan memori secara terpisah merupakan:

interconnection network 

 

30.   Salah satu penerapan prefix sum adalah untuk:

memisahkan satu tipe data dari tipe yang lainnya. 

 

31.   Bagian algoritma yang biasanya belum dilakukan secara paralel adalah:

inisialisasi 

 

32.   Pada algoritma preorder tree traversal, setiap edge akan terlewati sebanyak:

2 kali 

 

33.   Penyelesaian persamaan simultan linier dengan substitusi mundur dilakukan setelah terlebih dahulu menjadikan sistem persamaan tersebut menjadi matriks:

segitiga atas

 

34.   Prosesor dengan identitas 000 pada SIMD Cube Connection akan terhubung dengan prosesor:

001, 010, 100 

 

35.   Instruksi meta pada PRAM untuk mengaktifkan prosesor yang digunakan adalah:

spawn (<nama prosesor>) 

 

36.   Dua deret bilangan A dan B yang terurut naik, masing-masing dengan n bilangan, digabung (merge) menjadi satu. Algoritma sekuensial memerlukan waktu:

O(n) 

 

37.   Organisasi prosesor mirip matriks pada komputer SIMD disebut:

Mesh