ΕΘΝΙΚΟ ΚΑΙ ΚΑΠΟΔΙΣΤΡΙΑΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΟΜΕΑΣ ΘΕΩΡΗΤΙΚΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ

ΜΑΘΗΜΑ: ΠΑΡΑΛΛΗΛΑ ΣΥΣΤΗΜΑΤΑ & ΑΛΓΟΡΙΘΜΟΙ
ΔΙΔΑΣΚΟΝΤΕΣ: Θ. ΘΕΟΧΑΡΗΣ - Λ. ΜΠΟΥΚΑΣ
ΕΞΑΜΗΝΟ: ΕΑΡΙΝΟ 1999

1^η ΕΡΓΑΣΙΑ: Ταξινόμηση σε υπερκύβο με χρήση PVM

Ζητείται να γίνει ταξινόμηση ενός πλήθους Ν-αριθμών, με χρήση 8 επεξεργαστών (workstations) σε τοπολογία υπερκύβου (βλ. Σχήμα).

• Κατασκευή τοπολογίας υπερκύβου στο PVM.
• Ο 0-επεξεργαστής διαβάζει από αρχείο τα δεδομένα και αφού τα διασπάσει σε 8 ισόποσα τμήματα, τα προωθεί στους υπόλοιπους επεξεργαστές.
• Όλοι οι επεξεργαστές αφού λάβουν τα δεδομένα τα ταξινομούν με μία μέθοδο ταξινόμησης (π.χ. quicksort).
• Κατόπιν, για κάθε διάσταση του υπερκύβου, ζεύγη επεξεργαστών επικοινωνούν και ένας απο κάθε ξεύγος λαμβάνει τον ταξινομημένο πίνακα του γείτονά του.
• Κάθε επεξεργαστής που λαμβάνει ταξινομημένο πίνακα κάνει συνένωση με τον δικό του ταξινομημένο πίνακα (merge-sort), οπότε δημιουργείται ένας νέος ταξινομημένος πίνακας. Ετσι σε κάθε βήμα το μήκος της ακολουθίας διπλασιάζεται.
• Η παραπάνω διαδικασία επαναλαμβάνεται μέχρι ο 0-επεξεργαστής να έχει τον τελικό ταξινομημένο πίνακα.
• Να γίνει μέτρηση απόδοσης του παραπάνω αλγορίθμου για Ν=8, 16, 64, 512, 1024.