[ Up to the Home Page of CS-534 ]
© copyright Dept. of Computer Science, Univ. of Crete
CS-534: Packet Switch Architecture

Exercise Set 8:
Switching Fabric Topologies

Assigned: 2000-04-13 (week 9b) -- Due: 2000-05-09 (week 11)

8.1 Internal Blocking in Banyans

Η άσκηση αυτή αναφέρεται στο δίκτυo Banyan με περιττό πλήθος M επιπέδων. Οπως απεδείχθη κατά την διάλεξη της 13ης/4ου, υπάρχει μία μετάθεση κατά την δρομολόγηση της οποίας, κάποιοι από τους σύνδεσμους του μεσαίου επιπέδου (M-1)/2 πρέπει να δρομολογήσουν sqrt{N/2} (δηλαδή, τετραγωνική ρίζα του {N/2}) πακέτα. Να αποδείξετε ότι αυτή η συμφόρηση είναι η χειρότερη δυνατή. Μπορείτε να υποδείξετε κάποια άλλη μετάθεση που να έχει την ίδια συμφόρηση σε κάποιους άλλους συνδέσμους;

8.2 Permutation Routing in Buffered Banyans

Βασιζόμενοι στην προηγουμένη άσκηση να αποδείξετε ότι τα πακέτα οποιασδήποτε μεταθέσεως μπορούν να δρομολογηθούν σε χρόνο της τάξεως μεγέθους του sqrt(N) (δηλαδή της τετραγωνικής ρίζας του Ν), εφ όσον το μέγεθος ενταμιευτών στους μεταγωγείς του δικτύου Banyan είναι απεριόριστο. (Θεωρήσατε ότι η μετάδοση κάθε πακέτου σε ένα σύνδεσμο διαρκεί μία μονάδα χρόνου.) Ποίο είναι το μέγεθος ενταμιευτών που χρησιμοποιείται πραγματικά; Η διευκρίνηση αυτή είναι απαραίτητη διότι αποδεικνύεται (αρκετά δύσκολα όμως) ότι αν το μέγεθος των ενταμιευτών είναι σταθερό (δηλαδή, φραγμένο από μία σταθερά, ανεξάρτητη του N), τότε υπάρχουν μεταθέσεις που η δρομολόγησή τους διαρκεί χρόνο της τάξεως μεγέθους του Ν.

8.3 Rearrangeably Non-Blocking Benes Network

Να δρομολογήσετε non-blocking την εξής μετάθεση στο δίκτυο Benes 8 κόμβων: Κατόπιν, να επαληθεύσετε ότι αν οι κόμβοι εισόδου 0 και 3 ενάλλαξουν αμοιβαία προορισμούς, τότε μεταβάλλονται και κάποια από τα άλλα μονοπάτια.

8.4 Circular Bitonic Sequence Sorting

Στην άσκηση αυτή αποδεικνύεται η βασική ιδιότητα στην οποία στηρίζεται η κατασκευή του Batcher Sorting Network. Εστω μια ακολουθία a_0,...,a_{2N-1} η οποία είναι κυκλικά δίτονη (circular bitonic), δηλαδή προκύπτει από κυκλική ολίσθηση μιας ακολουθίας b_0,...,b_{2N-1}, η οποία είναι δίτονη με το αρχικό της τμήμα αύξον:

b_0 =< b_1 =< ... =< b_J >= b_{J+1} >= ... >= b_{2N-1}

πχ. η ακολουθία 4,5,6,7,1,0,2,3, που έχει προκύψει από την 2,3,4,5,6,7,1,0. Ορίζομε τις ακολουθίες

d_i = min(a_i, a_{i+N}), i=0,...,N-1, (1) και

e_i = max(a_i, a_{i+N}), i=0,...,N-1. (2)

Να αποδείξετε ότι και αυτές οι ακολουθίες είναι κυκλικά δίτονες, καθώς επίσης και ότι

max(d_0,...,d_{N-1}) =< min(e_0,...,e_{N-1}). (3)

To τελικό συμπέρασμα της ανωτέρω ιδιότητας είναι ότι λαμβάνοντας μία κυκλικά δίτονη ακολουθία μεγέθους 2N, και υποδιαιρώντας την σε δύο υπακολουθίες μεγέθους N με τον κανόνα των (1) και (2), προκύπτουν δύο υπακολουθίες που μπορούν να γίνουν sorted ξεχωριστά λόγω της (3). Επιπλέον, επειδή οι υπακολουθίες αυτές είναι επίσης κυκλικά δίτονες, μπορούμε να εφαρμόσουμε την ίδια μέθοδο αναδρομικά.

Υπόδειξη: Να εργασθείτε αρχικά με την δίτονη ακολουθία b_i, και να εξετάσετε χωριστά τις περιπτώσεις b_{N-1} =< b_{2N-1} και b_{N-1}>b_{2N-1}.

[ Up to the Home Page of CS-534 ]
© copyright University of Crete, Greece.
Written: 14 April 2000, by G. Stamoulis.
Last updated: April 2000, by M. Katevenis.