SystemC Simulation Semantics and Scheduler Steps

[Ivan]

Hello everyone, 

first of all I apologize if the post is too big and I know sometimes people get discouraged to read big posts. On the other hand I spent quite some time trying to make the post as clear as possible for the reader. So please do not get discouraged :).

My SystemC version: SystemC 2.3.1
My operating System: Ubuntu 16.04

I am trying to understand how SystemC simulator works, and for that I ran the following code:

SC_MODULE(EventNotifications) {

	sc_event evt1;

	void p1() {
		evt1.notify(10, SC_NS);
		evt1.notify(5, SC_NS);
		evt1.notify();
		evt1.notify(0, SC_NS);
		wait(10, SC_NS);
		evt1.notify(5, SC_NS);
		wait(10, SC_NS);
	}

	void p2() {
		wait(10, SC_NS);
		evt1.cancel();
		evt1.notify();
		wait(10,SC_NS);
	}

	void p3() {
		cout << "evt1 is activated at " << sc_time_stamp() << endl;
	}

	SC_CTOR(EventNotifications){

		SC_THREAD(p1);
		SC_THREAD(p2);
		SC_METHOD(p3);
		sensitive << evt1;
		dont_initialize();
	}
};

I referred to the SystemC Language Reference Manual 2.0.1: http://homes.di.unimi.it/~pedersini/AD/SystemC_v201_LRM.pdf

and in my explanation down below, I used the following abbreviations: 
R = {} - list of runnable processes, 
D = {} - list of processes that have been notified using delta notifications, 
T = {} - list of processes where timed notification has been used e.g. event.notify( >0, SC_NS) 

2.4.1 Scheduler Steps at page 6 from the SystemC Language Reference Manual 2.0.1 was used for the following reasoning of how this code works:

Initialize phase:
    We initialize all the processes that are ready to run. Process p3 at the beginning will not be runnable due to dont_initialize command. So only p1 and p2 processes runnable, as a result  R = {p1, p2} at  the end of initialize phase. Now we go to the evaluation phase. We start with simulation time equal to 0ns.

Simulation time = 0 ns

    Evaluation phase (delta cycle = 0):
        We have at the beginning R = {p1, p2}, D = {} (empty list) and  T = {}. Let's say scheduler decides to execute p1 first, so p1 gets removed from R, effectively R = {p2}.
        Then we execute 1st timed notifications evt1.notify(10, SC_NS), after that we have evt1.notify(5, SC_NS), since 5ns is earlier than 10ns, only 5ns will be remembered so we have T = {p3}.
        Next statement is evt1.notify() which is immediate notification, and will overwrite the previous notification evt1.notify(5, SC_NS). Immediate notification is put into the list p3, R ={p3}, and T = {}. Next statement is evt1.notify(0, SC_NS), so p3 will be put in the list D. So now we have R = {p3}, D = {p3}, T ={}. 
    
        Question 1: if I swapped two statements evt1.notify(0, SC_NS) and evt1.notify() here, will the delta notification will be removed? In my opinion only evt1.nofity() will be remembered:
        From page 128 of the manual: "A given sc_event object can have at most one pending notification at any point. If multiple notifications are made to an event that would violate this rule, the “earliest notification wins” rule is applied to determine which notification is discarded."
        As a result I would have R = {p3, p2}, D = {}, T = {}. Now we encounter the wait(10, SC_NS) and p1 is put to wait. 

        Question 2: Since I we have wait(10, SC_NS), does that mean that the process p3 will be put in separate list/queue of sleep processes? Let's call it list S, so we would have S = {p1} effectively? 
 
        Next let's say scheduler decides to run p2, so we remove p2 from the R list and we have R = {p3}. There we encounter wait(10, SC_NS), and p2 gets into S list, S = {p1, p2}.
        Now we have R = {p3} and p3 gets executed, so immediate notification gets executed at simulation time 0 ns as 1st console output indicates. Now method p3 exits, and list R is empty, R = {}, so we go to update phase.
    
    Update phase (delta cycle = 0):
        Nothing to be updated. We just go to the next delta cycle phase.
        
    Next delta cycle phase(delta cycle = 0):
        We increment delta cycle, and check all the contents of list D and put them in the list R. In our case D = {p3}, thus R = {p3}. Now we go back to evaluation phase.
        
    Evaluation phase(delta cycle = 1):
        We run only p3, here so the delta notification happens at simulation time 0 ns + 1 delta cycle. R = {}, we go to the update phase.
        
    Update phase (delta cycle = 1):
        Nothing to be updated. Go to next delta cycle phase.
        
    Next delta cycle phase(delta cycle = 1):
        We increment delta cycle, but since D = {}, we go to the increase simulation time phase.
        
    Increase simulation time phase (delta cycle = 2):
        From the page 6: "If there are no more timed event notifications, the simulation is finished. Else, advance the current simulation time to the time of the earliest (next) pending timed event notification."
        Now back to my Question 2, since we T = {}, that would mean that we have no timed event notifications, and based on reference manual simulation should be finished, which is not the case here if you run the code. 
        So from my understanding, the processes that were called with wait operation, will not be put in the "list of sleep processes" but instead they will be put to either list T or D.
        I think in case wait(>0, SC_NS), process gets put into the T list, and if wait(0, SC_NS) is called process should be put into the D list. So in our case T = {p1, p2}?
        We increase simulation time to the earliest 10 ns, and contents of list T = {p1, p2} are put into the list R = {p1, p2}. and we go to the next evaluation phase.
        
Simulation time = 10 ns:

    Evaluation phase (delta cycle = 0):
        Here we can either run p1 or p2. Let's say p2 is run first, and we encounter evt1.cancel(), since there are no pending events nothing will happen. Then we execute evt1.notify(), and p3 gets into the list R, so R = {p1, p3}. Then wait encountered, so T = {p2}.
        
        Now let's say scheduler decides to execute p3, and then immediate notification happens at simulation time of 10 ns.
        Now R = {p1}, so p1 gets executed and there we have evt1.notify(5, SC_NS), so p3 gets into the list T = {p2, p3}. Then we execute wait(10, SC_NS), and p1 sleeps again. So T = {p2, p3, p1}. Since R = {0}, we go to update phase.

        
    Update phase (delta cycle = 0):
        Nothing to be updated, so we go to the next phase.
        
    Next delta cycle phase (delta cycle = 0):
        We increment delta cycle. Nothing in list D, so we go to the next phase.
        
    Increase simulation time phase (delta cycle = 1):
        We put contents of T into R, thus R = {p2, p3, p1}, and we increment time to the earliest pending notification, since we had evt1.notify(5, SC_NS) and threads slept for 10 ns, we chose 5 ns. So simulated time is increased to 15 ns. We again go to the evaluation phase.

Simulation time = 15 ns:
    
    Evaluation phase (delta cycle = 0):
        Here R = {p2, p3, p1}, so let's say we execute p3 first, as result timed notification evt1.notify(5, SC_NS), happens at simulated time 15 ns. Now R = {p2, p1}, and p1 executes, since nothing after last wait statement thread terminates. Same situation for p2, so p2 terminates. R ={} go to next phase.
        
    Update phase (delta cycle = 0):
        Go to next phase.
        
    Next delta cycle phase (delta cycle = 0):
        Delta cycle updates, since D = {}, we go to the next phase
        
    Increase simulation time phase (delta cycle = 1):
        Since T = {}, nothing to be simulated and simulation ends. 

So this would explain the following result I got outputted on the console:

evt1 is activated at 0 s
evt1 is activated at 0 s
evt1 is activated at 5 ns
evt1 is activated at 10 ns
 

I tried to check my assumption that when wait(0, SC_NS) gets called in some process, the process will be put in the D list. So I ran this code:

SC_MODULE(DeltaTimeWait) {

	void p1(void) {

		while (true) {

			cout << "p1: " << sc_time_stamp() << endl;
			wait(0, SC_NS);
		}
	}

	void p2(void) {

		while (true) {

			cout << "p2: " << sc_time_stamp() << endl;
			wait(0, SC_NS);
		}
	}

	SC_CTOR(DeltaTimeWait) {

		SC_THREAD(p1);
		SC_THREAD(p2);
	}
};

There is also one thing I noticed. For example if I change the order of the thread registration in the constructor of the 1st code, and having SC_THREAD(p2) before the SC_THREAD(p1), I get different result.

SC_CTOR(Task5_d){

		SC_THREAD(p2);
		SC_THREAD(p1);
		SC_METHOD(p3);
		sensitive << evt1;
		dont_initialize();
	}

I get the following result:

evt1 is activated at 0 s
evt1 is activated at 0 s
evt1 is activated at 10 ns

I am not sure if my reasoning for this result is correct. So I think that we get his output due to reason that at the point where simulation time was 10 ns, we had two choices, we could either schedule p1 or p2 first.

Simulation time = 10 ns:

    Evaluation phase (delta cycle = 0):
       At this point as I have mentioned earlier, we can either run p1 or p2 first. And in the first case we assumed p2 was run first. But if we assume now p1 will be run 1st instead of p2. So now p1 gets executed and statement evt1.notfiy(5, SC_NS) is encountered. As a result, process p1 gets into the list T and then we sleep the process. Now the process p2 gets scheduled, and the 1st line we encounter is evt1.cancel(), which as result would cancel pending notification evt1.notfiy(5, SC_NS) from process p1. After that evt1.notify() is executed which results p3 getting into R list. So p3 being only in the list R, we execute process p3, and evt1 is notified at simulation of time 10 ns.  

Question 3: How come that order of thread registration actually affects the order of the process being scheduled?

I am not sure if my reasoning is correct, so I would appreciate your feedback, as I am only a beginner in SystemC.

 

Looking forward to your feedback.

Ivan.

[Philipp A Hartmann]

Hi Ivan,

instead of referring to the very old 2.01. LRM, I suggest to check the IEEE Std. 1666-2011 for SystemC, which could can download at no cost (sponsored by Accellera) via https://standards.ieee.org/findstds/standard/1666-2011.html.  This document includes the normative answers to all of your questions.

 

10 hours ago, Ivan said:

Question 1: if I swapped two statements evt1.notify(0, SC_NS) and evt1.notify() here, will the delta notification will be removed? In my opinion only evt1.nofity() will be remembered:

Yes, see section 5.10.8 of the aforementioned standard.

 

10 hours ago, Ivan said:

 Question 2: Since I we have wait(10, SC_NS), does that mean that the process p3 will be put in separate list/queue of sleep processes? Let's call it list S, so we would have S = {p1} effectively? 

Kind of, yes.  This is called "time out", see section 4.2(.1) of the standard.

 

10 hours ago, Ivan said:

Question 3: How come that order of thread registration actually affects the order of the process being scheduled?

The order to execution of processes in the runnable queue is entirely implementation-defined. See section 4.2.1.2.

Hope that helps,
  Philipp

Disclaimer: I haven't checked all of your post for correctness and focused on the questions instead.

.

 

[Ivan]

Hallo Phillip,

thank you for the document. It's exactly what I needed. I find it to be very helpful.

I want to ask two more things.

 

12 hours ago, Ivan said:

 Question 2: Since I we have wait(10, SC_NS), does that mean that the process p3 will be put in separate list/queue of sleep processes? Let's call it list S, so we would have S = {p1} effectively? 

Quote

 

Kind of, yes.  This is called "time out", see section 4.2(.1) of the standard.

 

I read section 4.2.1 of the document you provided and there it's stated:

"A time-out results from, and only from, certain calls to functions wait or next_trigger, which are member functions of class sc_module, member functions of class sc_prim_channel, and non-member functions. A time-out resulting from a call with a zero-valued time argument is added to the set of delta notifications and time-outs. A time-out resulting from a call with a non-zero-valued time argument is added to the set of timed notifications and time-outs (see 5.2.17 and 5.2.18)."

So timeout list with processes that executed wait(0, SC_NS) are scheduled in the next delta cycles and timeout list with processes that executed wait(>0, SC_NS) are scheduled in the next evaluation phase (after we increment the simulation time)?

I have one more question regarding the code from my 1st post.

SC_MODULE(DeltaTimeWait) {

	void p1(void) {

		while (true) {

			cout << "p1: " << sc_time_stamp() << endl;
			wait(0, SC_NS);
		}
	}

	void p2(void) {

		while (true) {

			cout << "p2: " << sc_time_stamp() << endl;
			wait(0, SC_NS);
		}
	}

	SC_CTOR(DeltaTimeWait) {

		SC_THREAD(p1);
		SC_THREAD(p2);
	}
};

Output: 

p1: 0 s
p1: 0 s
p2: 0 s
p2: 0 s
p1: 0 s
p1: 0 s
p2: 0 s
p2: 0 s
p1: 0 s
p1: 0 s
p2: 0 s
p2: 0 s
p1: 0 s

I am not sure why p1 is executed twice at the beginning. From my understanding when the first evaluation phase is run, both p1 and p2 are in the set of runnable processes. Now p1 gets scheduled, and statement wait(0, SC_NS) gets executed, so the p1 will be put in the list of "delta notifications timeouts". So p1 gets executed in the next delta cycle? Now p2 is still in runnable list, shouldn't p2 be scheduled as a 2nd process and not p1? And then after we execute p2 there are no runnable processes anymore. So we would go to update phase, and from there to the next delta cycle phase, and p1 gets executed again? After that we increase the simulation time and go to the evaluation phase again?

 Best regards,

Ivan

 

[Roman Popov]

8 hours ago, Ivan said:

I am not sure why p1 is executed twice at the beginning. 

This is unexpected. Probably you don't see a full simulation log or your simulator has a bug.

Try to add delta cycle counts to log:

	void p1(void) {
		while (true) {
			cout << "p1: " << sc_time_stamp() << " delta " << sc_delta_count() << endl;
			wait(0, SC_NS);
		}
	}

	void p2(void) {
		while (true) {
			cout << "p2: " << sc_time_stamp() << " delta " << sc_delta_count() << endl;
			wait(0, SC_NS);
		}
	}

 

[Roman Popov]

In general, there is no such concept as a "list of sleep processes" in SystemC. Because, really, all processes are sleeping, except the one that is currently evaluated.

For scheduling, there are two "lists" that simulator needs to maintain (my interpretation of LRM 4.2.1):

1. Set of runnable processes - that are process that will be evaluated in a current evaluation phase (current delta cycle).
2. Event notification queue, where notifications are prioritized by time. First come delta notifications (The set of delta notifications and time-outs), then timed notifications, prioritized by notification time (The set of timed notifications and time-outs) 

Probably the source of confusion here, is when you call wait(0,SC_NS) you don't see any event. But in fact there is a hidden "internal" event that you notify when you call wait(). This hidden event implements "time-outs".

Quote

So timeout list with processes that executed wait(0, SC_NS) are scheduled in the next delta cycles and timeout list with processes that executed wait(>0, SC_NS) are scheduled in the next evaluation phase (after we increment the simulation time)?

> Yes, wait(X, SC_NS) works the same way as event.notify(X,SC_NS).

SystemC scheduling is all about event notifications. There are 3 types:

1. event.notify()  - Immediate notification.  This will put all processes subscribed to event into set of runnable processes. That is, they will be executed in the current delta cycle.
2. event.notify(SC_ZERO_TIME) - Delta notification.  This will put delta event notification into event notification queue.
3. event.notify( sc_time > 0 ) - Timed notification. This will put timed event notification into event notification queue.

[Ivan]

1 hour ago, Roman Popov said:

This is unexpected. Probably you don't see a full simulation log or your simulator has a bug.

Try to add delta cycle counts to log:

	void p1(void) {
		while (true) {
			cout << "p1: " << sc_time_stamp() << " delta " << sc_delta_count() << endl;
			wait(0, SC_NS);
		}
	}

	void p2(void) {
		while (true) {
			cout << "p2: " << sc_time_stamp() << " delta " << sc_delta_count() << endl;
			wait(0, SC_NS);
		}
	}

 

Hey Roman

sc_delta_count() is very useful for understanding the code. I ran code with sc_delta_count now and I got reasonable result:

p2: 0 s delta: 1
p1: 0 s delta: 1
p1: 0 s delta: 2
p2: 0 s delta: 2
p2: 0 s delta: 3
p1: 0 s delta: 3
…

What I also learnt using this command is that once the simulation time gets incremented, delta count doesn't get reset to 0.

Quote

Probably the source of confusion here, is when you call wait(0,SC_NS) you don't see any event. But in fact there is a hidden "internal" event that you notify when you call wait().

So when I call wait(0, SC_NS) it will internally make call to event.notify(0, SC_NS) and wait(>0, SC_NS) would call event.notify(0>, SC_NS)?

 

 

 

[Roman Popov]

27 minutes ago, Ivan said:

So when I call wait(0, SC_NS) it will internally make call to event.notify(0, SC_NS) and wait(>0, SC_NS) would call event.notify(0>, SC_NS)?

Yes, this is how reference open-source SystemC kernel is implemented. You can compile SystemC in debug mode and step into wait(t) inside debugger to see for yourself.

Such an implementation is not mandatory by SystemC standard, but afaik most commercial SystemC simulators are derived from reference one and most likely are implemented in the same way.

[Ivan]

Thanks Roman and Philipp, I think I finally fully understood it. The document you provided helped me a lot to understand how simulation works. I have to say it's much more descriptive than the previous old version I was using.

However I just have one more question to clarify my understanding of the simulation. I was reading LRM document and came up to the following:

4.2.2 Initialization, cycles, and pauses in the scheduling algorithm

Update requests may be created during elaboration or before the initialization phase, and they shall be scheduled to execute in the update phase during the initialization phase. 
Delta notifications and timed notifications may be created during elaboration or before the initialization phase. Such delta notifications shall be scheduled to occur in the delta notification phase during the initialization phase. "

4.2.1.1 Initialization phase
Perform the following three steps in the order given: 
a) Run the update phase as defined in 4.2.1.3 but without continuing to the delta notification phase.
b) Add every method and thread process instance in the object hierarchy to the set of runnable processes, but exclude those process instances for which the function dont_initialize has been called, and exclude clocked thread processes. 
c) Run the delta notification phase, as defined in 4.2.1.4. At the end of the delta notification phase, go to the evaluation phase.

NOTE—The update and delta notification phases are necessary because update requests can be created during elaboration in order to set initial values for primitive channels, for example, from function initialize of class sc_inout."

 

So if I understood correctly these two sections, once we ran the elaboration phase, all primitive channels will be initialized to zero and these updates will be put in the updated list. We now transit to initialization phase, part a) of 4.2.1.1. 
Question 1: Does this mean that all assignments to zero of primitive channels done in the elaboration phase will trigger an "event value changed", and all these processes sensitive to these events will be put in the set of delta notifications?  

In part a) it says we do not go to the delta notification phase, but instead we go to the part b) where all the processes are put in the set of runnable processes. Once we are in part c) or in the delta notifications phase we would also add processes from set of delta notifications lists to the set of runnable processes, but inside the set of runnable processes we already have all the processes added in part b). Adding additional processes to the list would effectively would do nothing from my point of view, since I read previously that in the set of processes, a process can appear only once, and if extra ones appear, they will be removed. 
Question 2: So if only effectively processes added in part b) will be scheduled in the next evaluation phase, why do we even have part c). So why do we not directly go from update phase to the evaluation phase? Is it just to be consistent with the simulation steps or I misunderstood something?

[Roman Popov]

Here is an example illustrating initialization semantics.

 

#include <systemc.h>

SC_MODULE(test_init) {

    SC_CTOR(test_init) {
        SC_METHOD(method0);

        SC_METHOD(method1);
        sensitive << sig0;
        dont_initialize();

        SC_METHOD(method2);
        sensitive << sig1;
        dont_initialize();

        sig1 = 1;
    }

    void method0() {
        cout << "method0\n";
    }

    sc_signal<int> sig0{"sig0",42};

    void method1() {
        cout << "method1  sig0 == " << sig0 << endl;
    }

    sc_signal<int> sig1{"sig1"};

    void method2() {
        cout << "method2 sig1 == " << sig1
        << " sig0 == " << sig0 <<  endl;
    }

};

int sc_main (int argc, char**argv) {
    test_init mod{"mod"};
    sc_start();
    return 0;
}

 

Simulation output:

method0
method2 sig1 == 1 sig0 == 42

I think it covers both questions.

[Ivan]

20 hours ago, Roman Popov said:

Here is an example illustrating initialization semantics.

 

#include <systemc.h>

SC_MODULE(test_init) {

    SC_CTOR(test_init) {
        SC_METHOD(method0);

        SC_METHOD(method1);
        sensitive << sig0;
        dont_initialize();

        SC_METHOD(method2);
        sensitive << sig1;
        dont_initialize();

        sig1 = 1;
    }

    void method0() {
        cout << "method0\n";
    }

    sc_signal<int> sig0{"sig0",42};

    void method1() {
        cout << "method1  sig0 == " << sig0 << endl;
    }

    sc_signal<int> sig1{"sig1"};

    void method2() {
        cout << "method2 sig1 == " << sig1
        << " sig0 == " << sig0 <<  endl;
    }

};

int sc_main (int argc, char**argv) {
    test_init mod{"mod"};
    sc_start();
    return 0;
}

 

Simulation output:

method0
method2 sig1 == 1 sig0 == 42

I think it covers both questions.

I was trying to understand the output of your program referring to the section 4.2.1.1:

Elaboration
    both sig0 and sig1 are put in the update list
    
Initialization
    a) Update: sig0 and sig1 get updated, since method1 and method2 are sensitive to sig1.value_changed_event, sig2.value_changed_event respectively so both method1 and method2 should be put in delta notifications list D = {method1, method2}.
    b) We put method0 in the runnable list R = {method0}
    c) Delta notification: contents of D stored in R, R = {method0, method1, method2}
       Evaluation: Shouldn't all 3 processes be executed?

[Roman Popov]

21 hours ago, Ivan said:

both sig0 and sig1 are put in the update list

No. Only assignment (or write() method) triggers update request. Constructor initializes signal value directly.

So sig0 constructor generates no events and method1 is not activated.

[Ivan]

Thank you a lot Roman! You definitely clarified all the things that were not clear to me! 

Have a nice day.

[LaoShaw]

On 8/18/2018 at 6:47 AM, Ivan said:

I was trying to understand the output of your program referring to the section 4.2.1.1:

Elaboration
    both sig0 and sig1 are put in the update list
    
Initialization
    a) Update: sig0 and sig1 get updated, since method1 and method2 are sensitive to sig1.value_changed_event, sig2.value_changed_event respectively so both method1 and method2 should be put in delta notifications list D = {method1, method2}.
    b) We put method0 in the runnable list R = {method0}
    c) Delta notification: contents of D stored in R, R = {method0, method1, method2}
       Evaluation: Shouldn't all 3 processes be executed?

"since method1 and method2 are sensitive to sig1.value_changed_event, sig2.value_changed_event respectively so both method1 and method2 should be put in delta notifications list D"  -- why is that, are you saying whenever static sensitivity event triggers the waiting method will be put into delta-notification list? I think it should be next sc_time_stamp instead.