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 1 ,
x 0 ) = x n-2 , x n-3 ... x 1 ,
x 0 , x n-1 (x i =
0 atau 1, i = [0, n-1])
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 2 N) tahap, switch akan ditandai dengan 1a, 2a, 3a ... (N / 2), di mana sebuah huruf i menghitung dari 'A' ke 'Z' .
Sumber Refrensi :
http://www.herowintolo.stta.ac.id/2011/11/sistem-terdistribusi-2-2-switched.html
http://acm.tju.edu.cn/acm/showp2197.html
2. Untuk setiap (1 ≤ i ≤ log 2 N) tahap, switch akan ditandai dengan 1a, 2a, 3a ... (N / 2), di mana sebuah huruf i menghitung dari 'A' ke 'Z' .
Sumber Refrensi :
http://www.herowintolo.stta.ac.id/2011/11/sistem-terdistribusi-2-2-switched.html
http://acm.tju.edu.cn/acm/showp2197.html
Tidak ada komentar:
Posting Komentar