Re: [sv-ec] Scheduling algorithm discussions

Gord,

Your write-up does a good job at capturing the two options we 
discussed during the meeting. I wanted to add clarify some of
the issues you raised in the message.

Approach I proposes the addition of a new post-Reactive-NBA 
region (I prefer to call it just Reactive-NBA) to be processed 
following the Reactive region. You correctly point out that an
 implication of this addition is that #0 (Inactive) events in programs
would behave differently than in a module, namely that processes 
suspended by a #0 would execute BEFORE other Reactive-region 
processes triggered by the execution of program code, whereas in 
a module the expectation would be that such processes would execute 
AFTER all processes triggered by the execution of the Active region.

However, the #0 anomaly is easily addressed by the addition of another 
region, a Reactive-Inactive (pardon the oxymoron) into which programs 
can post #0 events. This would leave the interaction between "program" 
processes and "design" processes (caused by calls to side-effecting tasks 
or functions in the design from within programs) as the only observable 
difference between the two approaches. In this sense I believe that both 
approaches are approximately comparable --- both approaches require the 
addition of at least two regions (Reactive and Reactive-Inactive) to provide 
atomic write-back of values from programs to the "design" and equivalent
behavior for #0 events.

Approach II proposes that we retain post-Reactive-NBA in order to
propagate values from the program back to the design. However, that
region is not strictly needed. Given that this approach requires that all
Reactive regions be processed before looping back to the design regions,
we could just as easily post all program-to-design NBAs in the regular
(design) NBA region. This has a nice property (IMHO) of treating all
NBA's into the design in the same way, regardless of whether the origin
of the NBA is a program or a module. As I pointed above, this slight
adjustment to approach II requires only two Reactive regions: Reactive
and Inactive. The additional Reactive-NBA region could be added to
support program-to-program NBA's, which are currently not allowed.

    Arturo

----- Original Message ----- 
From: "Gordon Vreugdenhil" <gordonv@Model.com>
To: "SV_EC List" <sv-ec@eda.org>
Sent: Friday, April 29, 2005 4:07 PM
Subject: [sv-ec] Scheduling algorithm discussions


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