Tugas Sistem Terdistribusi

An Omega switching Network

Switching Omega merupakan jaringan interkoneksi antara modul memory dan modul processor pada sistem jaringan multiprocessor. Jaringan switching omega merupakan salah satu bentuk dari jaringan delta. Jaringan switching Omega pertama kali dipublikasikan oleh Duncan H Lawrie. 

 Jaringan omega pada gambar di atas adalah salah satu contoh. Jaringan ini berisi empat (2 x 2) switch, masing-masing mempunyai dua input dan dua output. Setiap switch memiliki rute baik input ke output atau sebaliknya. Switch ini dapat diatur dalam nanodetik atau kurang.

Dalam kasus umum, dengan n CPU dan n memori, jaringan omega log2 n switching memerlukan tahap, masing-masing berisi n/2 switch, dengan total (n log2 n) / 2 switch. Walaupun untuk n besar ini jauh lebih baik daripada n kuadrat.

Gambar 1. Perfect shuffle

Gambar 2.  Omega switching network

Kabel pola jaringan switching omega sering disebut Perfect Shuffle , karena pencampuran sinyal pada setiap tahap menyerupai setumpuk kartu yang dipotong setengah dan kemudian dicampur kartu untuk kartu, yang juga dapat digambarkan dengan menggunakan rumus :

δ (x _n-1 , x _n-2 ... x ₁ , x ₀ ) = x _n-2 , x _n-3 ... x ₁ , x ₀ , x _n-1 (x _i = 0 atau 1, i = [0, n-1])

Jadi untuk N = 8, perfect shuffle akan menjadi seperti Gambar 1. Dengan menggunakan pola ini, jaringan switching omega untuk N = 8 akan menjadi seperti Gambar 2.

Untuk melihat bagaimana jaringan omega bekerja, anggaplah bahwa CPU 011 ingin membaca sebuah kata dari modul memori 110. CPU mengirim pesan BACA untuk beralih 4A mengandung 110 di bidang Modul. Switch mengambil pertama (yaitu, paling kiri) sedikit 110 dan menggunakannya untuk routing. A 0 rute ke output atas dan rute 1 ke yang lebih rendah. Karena bit ini adalah 1, pesan disalurkan melalui output yang lebih rendah untuk 4B.

Semua switch tahap kedua, termasuk 4B, menggunakan bit kedua untuk routing. Ini juga merupakan 1, sehingga pesan sekarang diteruskan melalui output yang lebih rendah ke 4C. Bit ketiga diuji dan ditemukan menjadi 0. Akibatnya, pesan keluar pada output atas dan tiba di memori 110, seperti yang diinginkan. Jalan yang diikuti oleh pesan ini ditandai pada Gambar 2 dengan huruf a.

Contohnya adalah untuk jaringan N omega switching acak (N = 2 ^k , 1 ≤ k ≤ 26). Dari jaringan tersebut harus output jalur sinyal antara CPU dan memori yang diberikan di UMA.

INPUT

Baris pertama inputan adalah nomor M (1 ≤ M ≤ 100), menunjukkan jumlah kasus uji. Untuk setiap kasus uji, baris pertama berisi dua nomor N dan S. N adalah jumlah CPU dan Memory. Kemudian S adalah garis mengikuti, setiap baris memberikan dua angka i dan j, masing-masing mewakili CPU yang mengirimkan sinyal ke Memory j.

OUTPUT

Pada setiap kasus tes, terlebih dahulu harus output baris "Kasus t:", di mana t adalah jumlah kasus. Kemudian garis S, output jalur sinyal antara CPU yang diberikan dan Memory. Format output dari setiap jalur diberikan dalam Sampel output tanpa tanda hubung yang mengikat. Setelah itu, Output baris kosong setelah setiap kasus uji.

Contoh input

1

8 4

3 6

4 0

0 7

1 1

Contoh output

Kasus 1:

4A-4B-4C

1A-1B-1C

1A-2B-4C

2A-3B-1C

Petunjuk

1. CPU dan Memory selalu ditandai dari 0 sampai N-1.
2. Untuk setiap (1 ≤ i ≤ log ₂ N) tahap, switch akan ditandai dengan 1a, 2a, 3a ... (N / 2), di mana sebuah huruf i menghitung dari 'A' ke 'Z' .

Source:
http://www.herowintolo.stta.ac.id/2011/11/sistem-terdistribusi-2-2-switched.html
http://acm.tju.edu.cn/acm/showp2197.html