Notes from Dynamic Matching and Scheduling of a class of independent tasks on heterogeneous computing systems

Title : Dynamic Matching and Scheduling of a class of independent tasks on heterogeneous computing systems

Authors : Muthucumaru Maheshwaran, Shoukat Ali, Howard Jay Siegel, Debra Hengsen, Richard F. Freund

Year 1999

Journal of Distributed and Parallel Computing

Heterogeneous Systems : schemes are necessary to assign tasks to machines (matching)

then compute order of execution (scheduling)

mapping - the process of matching and scheduling tasks

Dynamic

Static (a priori)

In immediate mode, task is mapped onto machine as soon as it arrives at the mapper.

In batch mode, tasks are collected and examined and then mapped.

Expected execution time of a task a on machine j is the amount of time taken by j to execute t in j given j has no load when t is assigned to it.

It includes time to move the code or data to j.

Expected Completion Time is the wall clock time of task i on machine j after having finished any previously assigned tasks.

Ready time : the earliest time machine is going to be ready after completing the tasks currently assigned to it.

This is based on a combination of actual task execution times (for tasks that have completed) and

estimated expected task execution times (for tasks waiting to execute),

Reading these definitions feel like someone just defogged my windscreen.... clears up a lot of doubts... 

Immediate mode heuristics (only those i need to know)

Minimum completion Time (MCT) : assigns each task to the machine that results in the task's earliest Completion time.

As task arrives, all machines are examined to determine the machine that gives earliest completion time for the task.

so it takes O(m) time to map a given task.

Minimum execution Time (MET) : assigns each task to the machine that performs that task's computation in the least amount of execution time.

This does not consider machine ready times...

can cause severe unbalance in load among machines.

Adv : it gives each task to the machine that performs it in the least amount of execution time and heuristic is very simple.

Heuristic needs O(m) time to complete.

I'm lovin' the paper :D  all my doubts are being answered now :) :)  

kay so now i'm gonna try implementing MCT 'n MET in cloudsim...

I'll do MET first 'cos that's straightforward...