[sv-ec] Scheduling algorithm discussions

From: Gordon Vreugdenhil <gordonv_at_.....>
Date: Fri Apr 29 2005 - 16:07:34 PDT
The attached file describes my understanding of the scheduling
algorithms that were discussed today.  Anyone on the call, please
feel free to modify, extend, or correct this.

Gord.
-- 
--------------------------------------------------------------------
Gordon Vreugdenhil,  Staff Engineer               503-685-0808
Model Technology (Mentor Graphics)                gordonv@model.com



There were several possible variants of the scheduling
algorithm discussed today to deal with issues involving
program-design interactions.  The following documents
my understanding of the approaches as variants of
"execute_time_slot" in the reference algorithm.  The other
components of the reference algorithm are unchanged.



Approach I
----------

This approach just attempts to give a description of
the intent to delay design changes (via NBAs) until
after program threads are complete.

Define a new region "post-reactive-nba" which follows
the reactive region.  All nba assignments from 
program to module are scheduled into this region.

No real change in the algorithm is needed other than 
having "post-reactive-nba" become one of the iterative
regions.

Implications:  
    - NBAs are still restricted to design elements
    - #0 has odd semantics in that non-program threads
      can run between program threads
    - program threads cannot use events to trigger
      other program threads without having 
      the potential for non-program threads to run



Approach II
-----------

Approach II basically creates two symmetric sub-loops in
the overall scheduler.  The basic intent is to express
the following:
   while there are more events
       while there are more design events
           process design events
       while there are more testbench events
           process testbench events
       propagate values from testbench to design

This allows a greater separation and more consistent
semantics for nbas, continous assigns, etc. between
the design and program.


The following is the most general case of what we discussed --
it would allow for program-program NBAs as well ad program-module
NBAs.  That is easy to restrict by removing regions from the
described algorithm.



Define "design iterative region" to be the sequence of
regions from "inactive through post-observed" in the 
existing diagram.

Define new regions "Reactive-inactive" and "Reactive-NBA"
which exist after Reactive (corresponding pli regions
can be assumed).  Reactive-nba is used only for nbas from
program code to program variables.

Retain "post-reactive-nba" from Approach I for NBAs from
the program code to design variables.  It now occurs after 
reactive-nba.


Define "reactive iteration region" to be the sequence of 
regions "reactive-inactive, reactive-nba".  Note that
post-reactive-nba is NOT part of the "reactive iteration
region" list.  It is part of the set of iterative regions.


execute_time_slot {
    execute_region (preponed);
    while (any iterative region is non-empty) {
        while (active region or "design iterative region" is non-empty) {
            execute_region (active);
            foreach region in "design iterative regions" 
                if (region is non-empty) {
                    move events in region to the active region;
                    break from foreach scan loop;
                }
            }
        }
        while (reactive region or "reactive iteration region" is non-empty) {
            execute_region (reactive);
            foreach region in "reactive iterative regions"
                if (region is non-empty) {
                    move events in region to the reactive region;
                    break from foreach scan loop;
                }
            }
        }
        execute_region(post-reactive-nba)
    }
    execute_region (postponed);
}



Implications:
    - testbench to testbench nba is permitted
    - #0 has a direct correlation to "normal" module semantics
    - reactive threads can trigger each other with no design
      thread interactions
Received on Fri Apr 29 16:07:41 2005

This archive was generated by hypermail 2.1.8 : Fri Apr 29 2005 - 16:08:57 PDT