Ανάπτυξη χρονοπρογραμματιστή με τυχαίες επιλογές

• Κύριος συγγραφέας: Τόλλος, Αθανάσιος
• Άλλοι συγγραφείς: Σερπάνος, Δημήτριος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2014
• Θέματα: Χρονοπρογραμματισμός; Scheduler; Ranking; 005.1

Ο σύγχρονος κόσμος των δικτύων και του internet απαιτεί πολύ υψηλές ταχύτητες διασυνδέσεων στα διάφορα δίκτυα. Ξεκινώντας ακόμα και από τα οικιακά δίκτυα και τα τοπικά δίκτυα (LAN), στα πανεπιστημιακά δίκτυα (campus networks), στα μητροπολιτικά δίκτυα (MAN), στα δίκτυα ευρύτερης περιοχής (WAN) και στα δίκτυα κορμού του internet (core networks). Σε όλα αυτά τα δίκτυα χρησιμοποιούνται κατά κόρον μεταγωγείς (switches) και δρομολογητές (routers) προκειμένου να μεταφέρουν την δικτυακή πληροφορία από την αφετηρία της στον προορισμό της διασχίζοντας πληθώρα άλλων δικτύων. Πυρήνα των μεταγωγέων και των δρομολογητών αποτελεί ο χρονοπρογραμματιστής, ένας αλγόριθμος δηλαδή υλοποιημένος στο hardware της εκάστοτε συσκευής, που αποφασίζει την προώθηση της πληροφορίας από την είσοδό της στην έξοδό της, αφού προηγουμένως έχει καθοριστεί με άλλο μηχανισμό η θύρα εξόδου της πληροφορίας. Η σημασία του χρονοπρογραμματιστή γίνεται φανερή από την πληθώρα προβλημάτων που πρέπει να επιλύσει. Επιλεκτικά, κάποια από τα προβλήματα είναι ο ανταγωνισμός εισόδων για την ίδια έξοδο, το ταίριασμα εισόδων – εξόδων, η ελάχιστη δυνατόν καθυστέρηση στην διερχόμενη πληροφορία, η σταθερότητα λειτουργίας, η μεγιστοποίηση της διαμεταγωγής (throughput), η δικαιοσύνη στην εξυπηρέτηση εισόδων και εξόδων, κ.α. Στην παρούσα διπλωματική παρουσιάζεται η οικογένεια αλγορίθμων χρονοπρογραμματισμού ROLM (Randomized On-Line Matching), η οποία υλοποιεί τυχαιότητα με αποδοτικό και αποτελεσματικό τρόπο. Οι επιδόσεις αυτές φαίνονται στη μικρή καθυστέρηση στην προώθηση πακέτων (packet forwarding), επιτυγχάνοντας έτσι υψηλή διαμεταγωγή (throughput) και στα χαρακτηριστικά δικαιοσύνης που προσφέρουν, σε σχέση με τις υπάρχουσες ανταγωνιστικές υλοποιήσεις, που δεν χρησιμοποιούν τυχαιότητα αλλά ντετερμινιστικές μεθόδους απόφασης. Τα αποτελέσματα αυτά οφείλονται στο βασικό αλγόριθμο της οικογένειας ROLM, τον Ranking, o οποίος υπολογίζει μέγιστο ταίριασμα εισόδων – εξόδων. Οι αλγόριθμοι αυτοί επιλέγουν τυχαία εισόδους για προώθηση στις εξόδους που ζητούν, επιλογή η οποία μπορεί να οδηγήσει σε χρονοπρογραμματιστές υψηλών ταχυτήτων, ταχύτητες που ορίζει η εκάστοτε τεχνολογία υλοποίησης και η ταχύτητα των συνδέσμων δικτύου. Ο αλγόριθμος Ranking υλοποιείται σε software και σε hardware (υλικό), στην πλατφόρμα FPSLIC της ATMEL. Η πλατφόρμα αυτή περιέχει έναν 8μπιτο επεξεργαστή, τον AVR, και ένα προγραμματιζόμενο πίνακα πυλών (FPGA) στην ίδια πλακέτα κατασκευασμένα με την ίδια τεχνολογία. Έτσι, οι μετρήσεις των δύο υλοποιήσεων είναι συγκρίσιμες. Το πρόγραμμα που αναπτύσσεται, τόσο για την software όσο και για την hardware υλοποίηση, δέχεται ως παράμετρο το μέγεθος του μεταγωγέα. Έτσι, μετρώνται και συγκρίνονται χαρακτηριστικά όπως η ταχύτητα, ο χρόνος απόφασης, η επιφάνεια και το πλήθος θυρών I/O, για μεταγωγείς μεγέθους τεσσάρων εισόδων και τεσσάρων εξόδων (4x4), 8x8, 16x16 και 32x32.