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' .
Source:
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' .
Source:
http://www.herowintolo.stta.ac.id/2011/11/sistem-terdistribusi-2-2-switched.html
http://acm.tju.edu.cn/acm/showp2197.html
No comments:
Post a Comment