Browse Prior Art Database

Scheduling Algorithm for the MDSE

IP.com Disclosure Number: IPCOM000109672D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 3 page(s) / 140K

Publishing Venue

IBM

Related People

Beece, DK: AUTHOR [+2]

Abstract

A scheduling algorithm designed for the architecture of the MDSE is disclosed. This simple algorithm can produce a feasible schedule for a very large number of gates within a reasonable amount of computational resources. Several desirable features of the algorithm are discussed and statistics from design models are presented.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Scheduling Algorithm for the MDSE

       A  scheduling algorithm designed for the architecture of
the MDSE is disclosed.  This simple algorithm can produce a feasible
schedule for a very large number of gates within a reasonable amount
of computational resources.  Several desirable features of the
algorithm are discussed and statistics from design models are
presented.

      In prior art, a new special-purpose simulator, the MDSE, was
described.  The simulation primitives for the MDSE can be
conceptualized as tasks, for example, the evaluation of an AND gate.
The simulation model, therefore, is abstracted into a task graph with
each gate and array evaluation being a task of unit task length.
Such a task graph is a directed acrylic graph because all cycles are
broken by latches.  Scheduling algorithms for such graphs have been
widely discussed in the literature (*).  However, most of these
algorithms, optimal or otherwise, are mainly academic in the sense
that the topology of the communication network and the communication
delays are not considered.  Hence, while these algorithms produce a
theoretically feasible schedule, the schedule may be inapplicable to
a realistic machine architecture due to communication bottlenecks and
delays.  Moreover, their complexity may preclude their use on very
large task graphs (millions of tasks).  The algorithm disclosed here
takes the topology of the communication network and communication
delays of the MDSE into account.  This algorithm has linear
complexity, and thus makes it suitable for very large graphs.

      The goal of a scheduling algorithm is the identification of
sets of tasks which can be processed in parallel and assign them to
processors such that the completion time is shortest.  A simple way
to classify parallel tasks is by rank ordering the tasks.  The
algorithm disclosed here produces a schedule directly based on a
judiciously chosen rank order assignment.

      A basic rank ordering, hereafter refered to as earliest
precedence relation ordering, assigns rank 1 to tasks that are
primary inputs and then a rank of r to a task if its predecessors are
assigned and r-1 is the maximum of the ranks of its predecessors.  An
essential property of this type of rank ordering is that the rank of
any task is less than that of any of its descendents.  It, therefore,
provides a feasible schedule if all tasks at rank r are assigned
before all of those at rank r+1 for each r.

      Although this algorithm is fast and simple, it can be improved
substantially.  For typical designs, the distribution in the number
of tasks versus the earliest precedence relation ordering is uneven.
Frequently, the number of tasks at ranks near the maximum rank is
much less than the number of processors available, so that quite a
few processors would be left idle in the later cycles.  A better
schedule is obtained by generating a rank order which obeys the above
essential property but wit...