ECMP 486: Research in VLSI Systems

Notes on Paper by Robert Walker

Some parts of this paper photocopied too dark to read. Here is what those parts say:

On front page:

Scheduling -- a central task in high-level synthesis -- involves determining the execution order of operations in a behavioral description. After introducing the scheduling problem, this tutorial describes four scheduling algorithms commonly used to solve it.

Figure 4:

for each operation oi
  if oi has no immediate predecessors
    cstep(oi) = 1;
    /*  cstep (oi) indicates control step
        into which operation oi is scheduled  */
  else
    cstep(oi) = maximum cstep of any of oi's 
                immediate predecessors

Figure 5:

current-cstep = 0

while there are unscheduled operations
  
   current-cstep = current-cstep + 1 

   place data-ready operations into the ready list,
   evaluate the priority of each operation, 
   and sort the ready list in order of priority.

   while there are data-ready operations in the 
   ready list that meet the resource constraints
 
      Choose the highest priority data-ready operation oi
      from the ready list

      cstp(oi) = current-cstep

Figure 6:

construct an ASAP and an ALAP schedule, 
determine the schedule length, and
compute the schedule interval of each operation.

construct a histogram for each operation type k.

while there are unscheduled operations

  delta (Cbest) = infinity

  for each operation oi

    for each cstep sj in Si

      compute increase in cost delta(Cij) if 
      operation oi is scheduled into cstep sj

      if delta(Cij) < delta(Cbest)

         delta(Cbest) = delta(Cij)

         bestop = i; beststep = j;

  cstep (bestop) = beststep

  update histograms

Joan Carletta, carletta@ces.cwru.edu