= 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) ==
 
 * [Nov, 29] - the serial solution 
 * [Dec, 15] - OPENMP tunning
 * [Dec, 24] - MPI tunning
 * [Dec, 30] - experimental tests, conclusions
 * [Jan, 6]  - the paper


== Status ==
 
 * Nov, 27 - the serial solution is functional
 * Dec, 10 - 75% of the OPENMP tunning is ready

== Details ==

== The problem ==

The input:
 * the graph of tasks that have to be scheduled [https://ncit-cluster.grid.pub.ro/trac/PP2009/attachment/wiki/GAIIA/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: [https://ncit-cluster.grid.pub.ro/trac/PP2009/attachment/wiki/GAIIA/chromosome.jpg]
 * 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