Version 24 (modified by andreea.visan, 14 years ago) (diff)



  • The team: Mihai Istin - mihai.istin , Andreea Visan - andreea.visan


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

Project Activity (main steps)

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


The problem

The input:

  • the graph of tasks that have to be scheduled

The DAG of tasks

  • 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:

The chromosome's representation

  • uses the topological level and the inverse topological level of a node
  • introduces the notion of floating nodes:

Example 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

Execution - 2 threads

  • OMP version - 4 thread

Execution - 4 threads

  • OMP version - 8 thread

Execution - 8 threads

Attachments (23)

Download all attachments as: .zip