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

• 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

Experimental results

Sun Studio Performance Analyzer results:

• OMP version - 1 thread

• OMP version - 2 thread

• OMP version - 4 thread

• OMP version - 8 thread