Transcript The El-Rewini/Ali Scheduling of In

SMU - CSE 8388 Spring 2005
Instructor: Dr. H. El-Rewini
The El-Rewini/Ali Scheduling of
In-Forest Task Graph on Two
Processors with Communication
Project Presentation
By David Y. Feinstein
April 25, 2005
Problem description
 An in-forest task graph allows only one successor
task for each node. Out-forest task graphs are
reversed.
 The Hu Scheduling algorithm (1961) of in/out-forest
task graphs on arbitrary number of processor assumes
no communication cost.
 The El-Rewini/Ali algorithm (1994) was the first to
achieve optimal scheduling of in/out-forest tasks graph
with communication. It does limit the maximum
number of processors to two.
The El-Rewini/Ali algorithm introduced the notion of
Augmental Graph to compensate for the
communication cost. The Augmental Graph can be
scheduled using the Hu algorithm followed by the
SwapAll check to verify or correct the resulting
schedule.
My proposed solution
 This project provided an advanced framework to
simulate both Hu algorithm (on arbitrary number of
processors) and the El-Rewini/Ali algorithm.
 User can create, edit and store task graphs using
node and successor arc editors.
 After the required algorithm is selected, the user can
animate the process of the GANTT diagram
creation.
 Augmental graph creation is show in the detailed
algorithm output memo control. Sibling analysis
results can be seen graphically.
 My project currently supports only the In-Forest – it
can be easily extended for Out-Forest task graphs.
Assumptions




Execution time of all tasks takes is one unit of time.
Communication (in the El-Rewini/Ali algorithm) tasks
one unit of time.
Since the program currently supports only In-Forest
task graphs, all successor arcs are pointing
downward. (Arrow heads not shown for graph
clarity)
The file extension name for this project is “*.eas” (for
El-Rewini Ali Scheduling)
Overview
In-Forest Task Graph Creation



The user first generates the empty graph, after
setting the number of levels.
Use Node Insert/Delete set the proper number of
nodes
Use the successor editor to set the successor
Here is a sample of graph (also
stored in “test1.eas”)
The Default Process Setup Selection is the
El-Rewini/Ali optimal algorithm with
Communication.



The El-Rewini/Ali Algorithm is the default.
Number of processor is automatically set to 2
Must have a created graph (or a graph file *.eas
open).
The Hu Algorithm is Limited to No
Communication



When selecting the “Hu Only” process, the Hu
algorithm will run without communication.
You can set any number of processors.
Users can simulate homework 4 Problem 10-1
(using file “test2.eas”)
The Augmental Graph Creation is an
Essential Step of El-Rewini/Ali Algorithm


The Augmental Graph process performs sibling
analysis in the algorithm output screen.
The use can select the “Show Sibling in Graph” or
“Show Augmental Graph.
This partial display shows the
detail algorithm output box
Other portions of the display show
the Sibling Analysis and the Graph
creation process.
Selecting “Show Sibling in Graph”
Selecting “Show Augmental Graph”
Notice what happens if we do not select “minimize
arc crossing”. The result is still correct…
Hu Scheduling Control



You can use animation or single step.
The Hu Scheduling animation can be shown on the
GANTT diagram or even on the graph itself.
For El-Rewini/Ali, the Hu process works on the
Augmental Graph.
During the Hu animation, Done nodes are
in read, Ready nodes are shown in Green.
Gantt Diagram and program
output listing details


The Final process in the El-Rewini/Ali is checking
the resulting Hu Schedule. The program performs
the SwapAll operation if required.
Homework 4 problem 10-7 can be verified with the
file test2.eas
File “test1.eas” required one
swapall operation at time-6
Conclusions



The El-Rewini/Ali Augmental Graph was a critical
and elegant inventive step in order to solve the
problem of scheduling in-forest task graphs with
communication.
Computation cost for the Augmental Graph creation
are relatively minimal.
When using the Hu Only (without communications not show on the slides but can be run on the
program) – we quickly reach a point where adding
processors do not increase the output.