Heterogeneous Computing Drivers
◼ Solving grand challenge applications (which
cannot be solved by single computer)
Aerospace
Internet &
Life Sciences
Ecommerce
Digital Biology
Military Applications
CAD/CAM 3
Running Applications
Efficiently
1. Work Harder (increase the speed of
processor)
2. Work Smarter (design efficient
algorithm)
3. Get help (way to Heterogeneous
Computing)
◼ Coordinated use of diverse set of
resources to provide efficient
processing 4
Task Scheduling
◼ A major challenge is to effectively use
available resources
◼ Decompose an application into several
tasks
◼ Each task is computationally
homogeneous
5
Task Scheduling
◼ After decomposition assignment is needed
to a suitable machine (Scheduling)
◼ Efficient scheduling algorithms are
necessary to achieve high performance for
submitted applications
6
Background and Related Work
◼ Conventional high performance systems
consists of homogeneous processors
and support one execution mode
◼ Well suited to applications requiring one
particular execution mode
◼ Many applications consist of tasks
exhibiting different computing
environments
7
Background and Related Work
◼ Homogeneous system perform poorly
◼ Powerful and expensive homogenous
system does not solve problem
◼ HC systems solve this problem
8
Special
Vector MIMD SIMD purpose
Serial
Computer
25 25 25 25 T
Total time: 100
units
Vector
Computer
1 17 20 12 Total time: 50
units
Heterogeneous
Suite
1 1 1 1Total time: 4
units
Hypothetical example of the advantage of using HC systems
9
NP-Completeness of
Scheduling Problem
◼ NP-Complete, obtaining optimal solution
is not feasible
◼ Can be only found through exhaustive
search
◼ There are nm different ways to assign m
tasks to n machines
10
NP-Completeness of Mapping
Problem
◼ Example: 5 machines and 30 tasks
◼ 530 possible assignments
◼ If it takes only one nanosecond to
evaluate the quality of one mapping
then 1000 years are needed to evaluate
all 11
NP-Completeness of Mapping
Problem
◼ Not solved by algorithms with
polynomial time complexity
◼ Greedy heuristics, Genetic Algorithms,
Approximation Algorithms, and Ant-
Colony Optimization
◼ Greedy heuristics are widely used for
task scheduling and are reported to be
effective and efficient
12
Greedy heuristics
◼ Greedy heuristics is an iterative process
◼ In each step an individual task is
chosen from the set of tasks
◼ Selected task is assigned to respective
machine based on some performance
metric.
◼ Repeated until all the tasks are
scheduled
13
Necessary Concepts
◼ The heuristics that assign a task to a
machine vary in the information they use
◼ Assign task to machine that becomes
available soonest
◼ Assign task to machine which executes it
fastest
◼ Task may be assigned to the machine that
completes it earliest
14
Ready time for machines
m1 m2 m3
75 110 200
Completion time = ready time
+ execution time
Execution time for tasks
m1 m2 m3
t1 50 20 15
t2 20 60 15
t3 20 50 15
15
Well known task Scheduling
Algorithms
➢ Minimum Execution Time (MET)
➢ Minimum Completion Time (MCT)
➢ Min-min
➢ Max-min
➢ Heaviest Task First (HTF)
➢ Segmented Min-min
16
List Scheduling
◼ List scheduling techniques are also
widely used in task scheduling
problems. List scheduling techniques
assign a priority to tasks that are ready
to be executed based on a particular
heuristic, then sort the list of tasks in
decreasing priority
17
◼ A typical scheduling algorithm:
while tasks left to schedule
Determine the set of ready tasks
Pick one of the ready tasks
Pick one of the available hosts
Assign the task to the host
end while
◼ Remaining question: how do we define
the priority?
18
Heterogeneous Processors
◼ What if not all processors are identical??
◼ Heterogeneous compute speeds
◼ The algorithm can be modified as follows
while tasks left to schedule
or all unscheduled tasks Ti
for all hosts Hj
compute the completion time of Ti on Hj: CTi,j
end for
compute the priority as a function of all CTi,j: Pi
end for
pick task Tk with the best Pk Priority computation
pick host Hl that minimizes CTk,l
schedule task Tk on host Hl
inside the loop
end while (dynamic priorities19)
Two parameters
while tasks left to schedule
for all unscheduled tasks Ti
for all hosts Hj
compute the completion time of Ti on Hj: CTi,j
end for
compute the priority as a function of all CTi,j: Pi
end for
pick task Tk with the best Pk
pick host Hl that minimizes CTk,l
schedule task Tk on host Hl
end while
Define the priority
Define “best”
20
Two parameters
while tasks left to schedule
for all unscheduled tasks Ti
for all hosts Hj
compute the completion time of Ti on Hj: CTi,j
end for
compute the priority as a function of all CTi,j: Pi
end for
pick task Tk with the best Pk
pick host Hl that minimizes CTk,l
schedule task Tk on host Hl
end while Max
Min
Min of the CTi,j
Max of the CTi,j
21
Heterogeneity?
◼ Uniform Heterogeneity: If task A takes time TA and
task B takes time TB on a processor p, then task A
takes time TA and task B takes time TB on another
processor p’, for all tasks and processors
◼ Otherwise we have Non-Uniform Heterogeneity
tasks tasks
machines
machines
10 24 23 8 10 24 23 8
20 48 46 16 16 8 30 2
40 96 92 32 70 12 27 10
Uniform Non-Uniform
22
ETC matrix
◼ An ETC matrix is said to be consistent if
whenever a machine mj executes any
task ti faster than machine mk , then
machine mj executes all tasks faster
than machine mk. Consistent matrices
were generated by sorting each row of
the
23
◼ In contrast, inconsistent matrices characterize
the situation where machine mj may be faster
than machine mk for some tasks and slower
for others
◼ Partially-consistent matrices are inconsistent
matrices that include a consistent submatrix
of a predefined size
24
The execution time of 4 tasks on
4 machines
25
26
27
◼ A computation type most suited for the
execution of a part of application is referred
to as The computation requirement of that
particular application part
◼ A computation type supported by some
architecture is referred to as the execution
mode of that particular architecture
28