= GAIIA =

 * SVN: https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/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) ==
 

{{{
- the serial solution
- OPENMP tunning
- MPI tunning
- experimental tests, conclusions
}}}

== Details ==

== The problem ==

The input:
 * the graph of tasks that have to be scheduled 
[[Image(DAG.jpg)]]
 * 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: 
[[Image(chromosome.jpg)]]
 * uses the topological level and the inverse topological level of a node
 * introduces the notion of floating nodes: 
[[Image(floating_nodes.jpg)]]
 * single point crossover
 * 3 types of mutation:


{{{
- partial-gene mutation
- swap-gene mutation
- topological hyper-mutation
}}}

  
== Experimental results ==
 
Sun Studio Performance Analyzer results:

 * OMP version - 1 thread
[[Image(1.jpg)]]

 * OMP version - 2 thread
[[Image(2.jpg)]]

 * OMP version - 4 thread
[[Image(4.jpg)]]

 * OMP version - 8 thread
[[Image(8.jpg)]]