blomma-graphs-logo

Sprint 2

2/09 - 9/09

Agenda

  1. Structure
  2. Scheduling algorithms
    1. LAST
    2. DLS
    3. Genetic Scheduling
  3. Scheduled task format
  4. Example

Structure

scheduling-package.png

Scheduling algorithms

LAST

Localized Allocation of
Static Tasks

  • Groups: already scheduled tasks
  • Frontiers: schedule candidates
  • DEdge: defined/undefined edge
  • DNode: scheduling priority
  • CostCalculation: earliest possible start time

LAST

Procedure

  1. Update frontiers
  2. Calculate DNodes
  3. Choose Task with highest DNode
  4. Schedule it on processor with earliest start time
  5. Repeat

DLS

Dynamic Level Scheduling

  • ReadyPool: pool of ready tasks to be scheduled
  • B Level: path to end task which takes the most time
  • EST per CPU: earliest start time of a task on every cpu
  • Dynamic Level: B Level - EST per CPU

DLS

Procedure

Initial ready pool with first task and its B-Level

  1. Calculate EST per CPU for every task
  2. Choose the task CPU pair with the highest DL
  3. Allocate the task to the CPU
  4. Delete the task from the ready pool
  5. Check dependency of new tasks
  6. Calculate B Level of new ready tasks
  7. Add ready tasks to raedy pool

Genetic Scheduling

  • Initial population based on heuristic algorithm
  • Search around this approximate area
  • Try to find a optimal schedule
  • By searching shortest finishing time
  • Limited by the number of generations

Genetic Scheduling

Procedure

  1. Create initial population
  2. Loop
    1. Evaluate Fitness
    2. Selection & Elitism
    3. (Swap Crossover)
    4. Swap Mutation
    5. Combine Mating Pool & Elitism Set
  3. Creating final schedule

Genetic Scheduling

Chromosomes

  • Processor based chromosomes
    All tasks assigned to a single processor
  • Schedule based chromosome
    Replicate the the initial schedule
  • (Random chromosomes)

Genetic Scheduling

Schedule Encoding

  • Encode task to processor allocation as chromosomes
  • 2 dimensional chromosomes
    • List of processors
    • List of tasks for this processor
  • Example
p0  t1  t2  t4  t5  t7
p1  t3  t6

Genetic Scheduling

Chromosome Decoding

  • List of all ready tasks for scheduling
    (All dependencies fullfilled, sorted by task id)
  • Chromosome with assigment of tasks to processors
  • Iterate through graph and assign first task from ready list to processor as defined by the chromosome

Genetic Scheduling

Mutation

  • (Swap Crossover)
    Create mask chromosomes based on two parents, flip on crossover points based on masking
  • Swap mutation
    propability of 0.5, swap two tasks in a chromsome

Genetic Scheduling

Selection

  • Mating (90%) and elitism (10%) pool
  • Mutate only mating pool
  • Selection based on shortest finishing time

Scheduled task format

Description

Short

starttime cpu_id node_id

Extended

starttime cpu_id node_id communicationtime computationtime

Sample

0   0   0   1   0
1   1   1   2   0
3   1   2   5   0
4   0   3   3   1
8   1   4   10  0
8   0   5   8   0
16  0   6   1   0

Example

Initial graph

Initial scheduled graph

0   0   0   1   0
1   0   1   2   0
3   0   2   5   0
8   0   3   3   0
11  0   4   10  0
12  1   5   8   1
21  0   6   1   0

22

GS based scheduled graph

0   0   0   1   0
1   0   1   2   0
3   0   2   5   0
4   1   3   3   1
8   0   4   10  0
8   1   5   8   0
16  1   6   1   0

18