1 |
Υλοποίηση και εξομοίωση ενός max-min fair sharing αλγορίθμου και σύγκριση αλγορίθμων χρονοπρογραμματισμού σε Grids / Implementation and simulation of fair grid scheduling algorithmsΝταφούλη, Ελένη 26 February 2009 (has links)
Θέμα της παρούσας εργασίας είναι η υλοποίηση και εξομοίωση δίκαιων
αλγόριθμων χρονοπρογραμματισμού σε Grids και η σύγκρισή τους με κλασικούς
αλγόριθμους χρονοπρογραμματισμού.
Η βασική ιδέα πίσω από την τεχνολογία Grid και τις υπηρεσίες που παρέχει είναι
η ενοποίηση υπολογιστικών και αποθηκευτικών πόρων και η συνολική θεώρηση τους
από τους χρήστες. Με τον τρόπο αυτό γίνεται δυνατή η ανάπτυξη πολύπλοκων και
απαιτητικών εφαρμογών, τόσο στον χώρο της επιστημονικής έρευνας, όσο και στα
πλαίσια της παραγωγής εμπορικών λύσεων.
Ένα τέτοιο σύστημα απαιτεί διαμοιρασμό των υπολογιστικών και άλλων πόρων
καθώς και μεγάλες ταχύτητες σύνδεσης μεταξύ τους. Οι αλγόριθμοι χρονοπρογραμματισμού αναλαμβάνουν τον αποδοτικό διαμοιρασμό των πόρων ώστε να
επιτυγχάνεται καλύτερη ποιότητα υπηρεσίας. Η αποτελεσματικότητα ενός
αλγόριθμου χρονοπρογραμματισμού εξαρτάται από την συνάρτηση που θέλουμε να
βελτιστοποιήσουμε, που με τη σειρά της εξαρτάται από τεχνο-οικονομικά κριτήρια.
Στην προσπάθεια βελτιστοποίησης της εκάστοτε συνάρτησης ευνοούνται κάποιες
προς εκτέλεση διεργασίες έναντι άλλων. Ένας δίκαιος αλγόριθμος
χρονοπρογραμματισμού όμως θα πρέπει να συμπεριφέρεται με τον ίδιο τρόπο σε
όλες τις διεργασίες ανεξαρτήτως των χαρακτηριστικών τους.
Στην εργασία που θα παρουσιάσουμε, αναλύουμε δύο δίκαιους αλγόριθμους
χρονοπρογραμματισμού, τον Fair Completion Time (Ordering) και τον Fair
Completion Time Estimation (Assignment). Κατόπιν τους υλοποιούμε και τους
εξομοιώνουμε με το GridSim Toolkit και συγκρίνουμε την απόδοση τους με
κλασικούς αλγόριθμους χρονοπρογραμματισμού. / The subject of this thesis is the implementation and simulation of fair scheduling algorithms
applied on Computational Grids and their comparison with the classic scheduling algorithms.
The basic idea of the Grid Technology and the services it provides, is the unification of
computational and storage resources. This way it is possible to serve sophisticated applications, in
fields like scientific research and trading.
A Grid Network demands the sharing of the computational and storage resources, and high
bandwidth connections between them. Scheduling algorithms are responsible for the efficient
assignment of tasks to resources for better quality of service. Evaluating the efficiency of a
scheduling algorithm depends on a utility function that we seek to optimize which in turns
depends on techno-economic criteria. As a result of trying to optimize the utility function, some
tasks with specific characteristics are favoured against others. A fair scheduling algorithm
however should treat all tasks in the same way regardless of their characteristics.
In this thesis we study the Fair Completion Time Ordering Algorithm and suggest a new fair
scheduling algorithm called Fair Completion Time Estimation Assignment Algorithm. We
implement and simulate these algorithms using the GridSim Toolkit and compare them with the
classic scheduling algorithms.
|
2 |
Escalonamento de aplicações paralelas: de clusters para gridsJacinto, Daniele Santini 24 August 2007 (has links)
Made available in DSpace on 2016-06-02T19:05:26Z (GMT). No. of bitstreams: 1
1631.pdf: 1988300 bytes, checksum: e305adb917a8fdf720897942982390b7 (MD5)
Previous issue date: 2007-08-24 / Different algorithms provide efficient scheduling of parallel applications on distributed and
heterogeneous computational platforms, such as computational grids.
Most scheduling algorithms for such environments require an application model represented
by a directed acyclic graph (DAG), selecting tasks for execution according to their processing
and communication characteristics.
The obtainment of DAGs for real applications, however, is not a simple quest. The required
knowledge about the application tasks and the communication among them, considering
existing transmission cycles, harden the elaboration of appropriate graphs.
Particularly, MPI programs, that represent a meaningful portion of existing parallel applications,
usually present a cyclic communication model among the master and the processing
nodes. This behavior prevents most scheduling algorithms to be employed as they recursively
traverse the graphs to prioritize the tasks.
In this sense, this work presents a mechanism for the automatic creation of DAGs for real
MPI application originally developed for homogeneous clusters. In order to do so, applications
go through a monitored execution in a cluster and the collected data are used for the elaboration
of an appropriate DAGs. Data dependencies are identified and existing cycles among the
tasks are eliminated. The HEFT scheduling algorithm is used to evaluate the application model
and the schedule obtained is then automatically converted into an RSL (Resource Specification
Language) file for execution in a grid with Globus.
Results from running real applications and simulations show using the grid can be advantageous. / Algoritmos diferentes possibilitam o escalonamento eficiente de aplicações paralelas em
plataformas computacionais heterogêneas e distribuídas, tais como grids computacionais. Vários
algoritmos de escalonamento para esses ambientes necessitam de um modelo de aplicação
representado por um grafo acíclico direcionado (GAD), selecionando tarefas para execução de
acordo com suas características de comunicação e de processamento.
A obtenção de um GAD para uma aplicação real, contudo, não é uma questão simples.
O conhecimento necessário sobre as tarefas da aplicação e as comunicações entre elas, considerando
ciclos de transmissão, dificulta a elaboração de um grafo apropriado.
Particularmente, programas MPI, os quais representam uma parcela significativa das aplicações
paralelas, apresentam um modelo de comunicação cíclico entre o nó master e os nós
de processamento. Esse comportamento impede a utilização de muitos algoritmos de escalonamento
devido ao fato de eles percorrerem o grafo recursivamente para priorizar as tarefas. Nesse sentido, esse trabalho apresenta um mecanismo para a criação automática de GADs
para aplicações MPI reais originalmente desenvolvidas para clusters homogêneos. Para essa
implementação, aplicações são monitoradas durante a execução em um cluster e os dados coletados
são usados para a elaboração de um GADs apropriados. Dependências de dados são
identificadas e ciclos existentes entre as tarefas são eliminados. O algoritmo de escalonamento HEFT é usado para avaliar o modelo de aplicação e o
escalonamento obtido é então automaticamente convertido em um arquivo RSL (Resource Specification
Language) para execução em um grid com Globus.
Resultados de execuções de aplicações reais e simulações demonstram que o uso de grid
pode ser vantajoso.
|
Page generated in 0.0128 seconds