Χρονοδρομολόγηση παράλληλων εργασιών σε υπολογιστικά Clouds: μοντελοποίηση, προσομοίωση και ανάλυση της απόδοσης
Creators: name: Μοσχάκης, Ιωάννης Αθανασίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2010
Subjects: Προσομοίωση Απόδοσης
Χρονοδρομολόγηση εργασιών τύπου Gang
Υπολογιστικά Clouds
Performance Simulation
Gang Scheduling
Cloud computing

description: η εργασία αυτή αφορά την μελέτη της απόδοσης ενός κατανεμημένου συστήματος βασισμένου στο μοντέλο του Cloud Computing και συγκεκριμένα στην αρχιτεκτονική του amazon ec2, η οποία θα περιγραφεί σε επόμενο κεφάλαιο.Το σύστημα που προσομοιώθηκε αποτελεί ένα gang scheduled high performance computing, σύστημα με εργασίες (jobs) με μεγάλο βαθμό παραλληλισμού, που απαιτούν την ταυτόχρονη εκτέλεση των διεργασιών τους (tasks) οι οποίες επικοινωνούν συνεχώς μεταξύ τους κατά την διάρκεια της εκτέλεσης τους. ως μονάδες επεξεργασίας ορίζονται οι εικονικές μηχανές, οι οποίες στον πραγματικό κόσμο αποτελούν virtualized instances λειτουργικών συστημάτων, που εκτελούν κάποιες συγκεκριμένες λειτουργίες και γι' αυτό το λόγο μπορούν να κλωνοποιηθούν σε μικρό χρόνο και να προστεθούν στο σύστημα. έτσι το σύστημα μας διαθέτει 32 εικονικές μηχανές μόνιμα δεσμευμένες και πέραν αυτών έχει την δυνατότητα να δεσμεύσει περισσότερες έως και 64 ανάλογα με τις απαιτήσεις παραλληλισμού των εργασιών, που υπάρχουν κάθε στιγμή. φυσικά η δέσμευση νέων μηχανών δεν είναι μια διαδικασία που γίνεται την ίδια στιγμή αλλά υπάρχει μια σχετική καθυστέρηση από την στιγμή που, το σύστημα, αιτείται μια νέα μηχανή μέχρι τη στιγμή που αυτή γίνεται διαθέσιμη προς το σύστημα. οι εργασίες εισέρχονται στο σύστημα σε μια εικονική μηχανή με ουρά, που επιτελεί τον ρόλο του διανεμητή ο οποίος εφαρμόζει τον αλγόριθμο shortest queue first και κάνει χρήση της ουράς μόνο για τις εργασίες που η διανομή τους αναβλήθηκε έως ότου δεσμεύσουμε επαρκή αριθμό εικονικών μηχανών. oι πολιτικές δρομολόγησης προς εκτέλεση των διεργασιών που εξετάστηκαν είναι η adaptive first come first serve και η adaptive largest job first served που αποτελούν τις δύο πιο κλασσικές μεθόδους δρομολόγησης που χρησιμοποιούνται σε gang scheduled συστήματα. η πολιτική δέσμευσης-αποδέσμευσης εικονικών μηχανών βασίζεται στην λογική της απολύτως αναγκαίας υπολογιστικής ικανότητας του συστήματος, κοινώς δεν δεσμεύουμε μηχανές που δεν χρειαζόμαστε και δεν αποδεσμεύουμε μηχανές εκτός και αν αυτές είναι πλήρως idle. οι εργασίες έχουν βαθμό παραλληλισμού είτε από 1 έως 32 είτε από 33 έως 64 με διακριτή ομοιόμορφη κατανομή και εξετάζουμε τρία διαφορετικά σενάρια ως προς το ποσοστό των εργασιών, που τελικά θα ανήκουν στην μία κατηγορία και το ποσοστό των εργασιών, που θα ανήκουν στην άλλη. σκοπός της μελέτης αυτής είναι να ερευνήσουμε αν ένα σύστημα που βασίζεται στο cloud μοντέλο αρχιτεκτονικής είναι κατάλληλο για gang scheduled και να δούμε αν οι μέθοδοι δρομολόγησης που εφαρμόζονται κλασικά είναι κατάλληλοι για ένα σύστημα με δυναμικά μεταβαλλόμενο αριθμό επεξεργαστικών μονάδων και να συγκρίνουμε την μεταξύ τους απόδοση. επίσης εξετάζουμε το αντίκτυπο που έχει η διαφοροποίηση της ποσόστωσης στα μεγέθη των εργασιών.
description: this thesis studies the performance of a distributed system, which is based on the cloud computing model and more specifically on the architecture of the amazon ec2 of which we're going present a full description later in this document. the system, which was simulated, is a gang scheduled high performance computing based system with highly parallel jobs. every job consists of multiple parallel tasks that are required to run simultaneously and without interrupts in order to continuously communicate with each other during runtime. as computational units we define virtual machines, which in the real world are virtualized instances of operating systems that are configured to do a specific job and for that reason they can be easily cloned and in a short time be available to the system. thus our system includes 32 virtual machines that are permanently available to the system and it has the option to provision for more virtual machines up to a total number of 64 depending on the requirements of the jobs that are in the system at any specific moment. naturally virtual machine provisioning requires some time and only after some relative delay does the virtual machine become available to the system. jobs enter the system through a virtual machine utilized as the dispatcher, which includes a queue, but only for jobs whose dispatch was delayed because of inadequate number of virtual machines available to the system at the time of their insertion. those jobs are dispatched the moment the provisioned for virtual machines become available. dispatcher utilizes the shortest queue first algorithm in order to dispatch the parallel tasks of the jobs to the corresponding virtual machines. two types of task scheduling were implemented, adaptive first come first serve (afcfs) and adaptive largest job first served (aljfs). these two are the most commonly used scheduling methods in the simulation of gang scheduled systems. the policy that was implemented for provisioning and releasing virtual machines is based on the need to have paradigm, thus provisioning only for virtual machines that are currently needed and releasing them if they ever become idle. jobs have a degree of parallelism ranging from 1 to 32 and from 33 to 64. degrees are random numbers following the discrete uniform distribution. in our system we study 3 different scenarios, which differ in the possibility of a job belonging to the first group (1-32) or the second group (33-64). the purpose of this study is to examine if a system that is structured based on the cloud computing model is appropriate for gang scheduled hpc and to find out if the scheduling policies that are used in non-dynamic gang scheduled systems with a stable number of servers can also be used with equal efficiency in a system with a number of processing units that is dynamically changing. we also examine the impact that the change of the job size possibility has on the total results of the system.