Version 19 (modified by 14 years ago) (diff) | ,
---|
GAIIA
- The team: Mihai Istin - mihai.istin , Andreea Visan - andreea.visan
Abstract
Task scheduling is one of the most important management aspects in a distributed system because this component should achieve two main goals: on the one hand efficient use of available resources and on the other hand high performance in solving tasks. Because of the fact that the scheduling problem is an NP-Complete problem, a near-optimal algorithm is a desired solution. A third goal is the fact that the algorithm should provide the results very fast. This project's aim is to develop a parallel solution for a near-optimal algorithm for dependent task scheduling in distributed systems.
Technologies and Languages
- C/C++
- MPI
- OPENMP
Project Activity (main steps)
- [Nov, 20] - the serial solution
- [Dec, 11] - OPENMP tunning
- [Dec, 18] - MPI tunning
- [Jan, 8] - experimental tests, conclusions
- [Jan, 12] - the paper
Status
- Nov, 20 - the serial solution is functional
- Dec, 9 - 75% of the OPENMP tunning is ready
Details
The problem
The input:
- the graph of tasks that have to be scheduled
- the graph of available resources
The output:
- the scheduling meaning the task-resource associations
The goal:
- load balancing
- minimum makespan
The algorithm:
- uses genetic algorithms
- chromosome representation:
- uses the topological level and the inverse topological level of a node
- introduces the notion of floating nodes:
- single point crossover
- 3 types of mutation:
** partial-gene mutation ** swap-gene mutation ** topological hyper-mutation
Attachments (23)
-
chromosome.jpg (18.2 KB) - added by 14 years ago.
The chromosome's representation
-
DAG.jpg (52.1 KB) - added by 14 years ago.
The DAG of tasks
-
floating_nodes.jpg (170.8 KB) - added by 14 years ago.
Example of floating nodes
- 1.jpg (29.2 KB) - added by 14 years ago.
-
2.jpg (37.1 KB) - added by 14 years ago.
Execution - 2 threads
-
4.jpg (50.1 KB) - added by 14 years ago.
Execution - 4 threads
-
8.jpg (76.4 KB) - added by 14 years ago.
Execution - 8 threads
-
overview.jpg (124.1 KB) - added by 14 years ago.
Sun Studio Performance Analyzer - function overview
-
ia.jpg (22.6 KB) - added by 14 years ago.
The Immune Algorithm
-
execp.jpg (37.0 KB) - added by 14 years ago.
(Parallel) Execution model
-
execd.jpg (41.3 KB) - added by 14 years ago.
(Distributed) Execution model
- grafic2.jpg (170.1 KB) - added by 14 years ago.
-
grafic1.jpg (16.6 KB) - added by 14 years ago.
Evolution (thread)
- runtime.jpg (21.1 KB) - added by 14 years ago.
- tab.jpg (13.1 KB) - added by 14 years ago.
- tab2.jpg (29.3 KB) - added by 14 years ago.
- form1.jpg (5.8 KB) - added by 14 years ago.
- form2.jpg (6.4 KB) - added by 14 years ago.
- form3.jpg (9.6 KB) - added by 14 years ago.
- tour.jpg (19.7 KB) - added by 14 years ago.
- sort1.jpg (21.4 KB) - added by 14 years ago.
- sort2.jpg (16.6 KB) - added by 14 years ago.
- multi.png (25.4 KB) - added by 14 years ago.
Download all attachments as: .zip