# PARSEC Simulation Tutorial

This tutorial is out of date and has been removed from the Parsec web page until it can be updated. There are structures described in this document which are not supported by the Parsec language. Do not use this document as a reference!

## Introduction

PARSEC is a C-based language for simulation, or more specifically, it is a language for parallel discrete event simulation. This tutorial provides an interactive introduction to PARSEC. The remainder of this introduction provides an overview of discrete event simulation and parallel simulation. This section can be skipped if the reader is familiar with simulation concepts. The PARSEC Language begins describing the PARSEC language constructs interactively building a small example program. More complex examples are shown in the next section, followed by execution instructions (which are described more fully in the User's Manual), and advanced PARSEC facilities.

### Simulation

A simulation model may be used to predict the behavior of a physical system under a variety of operating conditions. In the process-interaction approach to simulation, a physical system is assumed to consist of a set of physical processes that interact with each other at discrete points in time; these interactions are refered to as events. In its simulation model, a logical process (LP) is used to model one or more physical processes (PP); the events in the physical system are modeled by message exchanges among the corresponding logical processes in the model.

Consider a bank teller as a simple example of a physical system. We assume that the bank has n teller windows that are open. A teller is said to be idle if she is not servicing a customer and is otherwise said to be busy. Customers arrive at the bank and wait for service in a common queue. The customer at the head of the queue goes to any teller that is idle. After receiving the desired service the customer leaves the bank. We are interested in measuring the average and maximum time that is spent by a customer in the bank. We may be interested in using the model to examine how these metrics change as the number of tellers, the service rate of the teller, or the arrival rate of customers is modified. The processes in this system are the tellers and the queue of waiting customers; interesting events are the arrival of a customer at the queue (henceforth called the arrival event), departure of a customer from the queue, arrival of a customer at a teller (the begin-service event), and departure of a customer from a teller (the end-service event). We will ignore the time spent by a customer in walking from the head of the queue to a teller window; thus the departure of a customer from the queue and his/her arrival at the teller are really the same event.

In its simulation model, we can define logical processes to model the teller and queue processes in the physical system. The logical processes are refered to as teller and queue respectively. Although the model will contain n tellers, for simplicity we will use teller to refer to a specific teller process. We also define a source process that creates customers. The customers in the physical system are abstracted via the events and need not be modeled as explicit logical processes. The model defines a source process that generates customers and a sink process that collects statistics on the time spent by a customer in the bank. The arrival event can now be modeled by sending a message from the source process to the queue process; the message contains the arrival time of the customer and perhaps a unique id that is used to track the customer. Similarly the begin-service event is simulated by sending a message from the queue to a teller and the end-service event by sending a message from the teller to the sink. The PARSEC constructs to define LPs and their interactions via messages are described in the next section The PARSEC Language.

A primary activity in a simulation model is the scheduling of future events. For instance, the source must schedule the arrival of future customers and a teller must schedule the end-service event. Some of these events simulate the passage of time in the physical system, whereas others are assumed to occur instantaneously. Messages used to simulate physical events are associated with a send time and a receive time. By default, the send and receive time of a message are set to the simulation time of the sender LP. In general, the receive time of a message can be explicitly set to any future value greater than or equal to its send time. An LP may also suspend itself for a specific interval of simulation time to simulate passage of physical time in performing an activity. For instance, assume that the service time for a client at a teller is t units. On receiving a begin-service message at say time T, a teller may either immediately send an end-service message with a receive time of T+t to the sink LP or it may suspend itself for t time units and then send an end-service message with receive and send times of T+t to the sink. The PARSEC constructs to schedule events are described in the Events section.

### Parallel Simulation

A PARSEC model can be executed using sequential or parallel simulation algorithms. The sequential algorithm typically uses an ordered data structure called the global event list which stores all events that are generated in the system in their timestamp order. Details on the commands to compile and execute a model on a sequential platform are contained in the manual.

For parallel execution, each LP or entity in the model is mapped to a specific processor. Each processor, say P, has its own event list which stores the events for the entities that are mapped to P. Parallel synchronization algorithms have been defined to ensure that events in the event lists stored on different processors are executed in their global timestamp order. Enforcing this requirement, referred to as the causality constraint, is the central problem in efficient execution of parallel simulations. Two primary approaches have been suggested to solve the synchronization problem: conservative and optimistic.

Conservative algorithms do not permit any causality error: each object in the simulation processes an incoming message only when the underlying synchronization algorithm can guarantee that it will not subsequently receive a message with a smaller timestamp. This constraint may introduce deadlocks, which are typically avoided by using null messages. A null message is a timestamped signal sent by an LP to indicate to other LPs a lower bound on the timestamp of its future messages. If an LP sends a null message with timestamp T+la at simulation time T, we say that the LP has a lookahead of la, (the LP is looking la units ahead in its future). In general, the larger the lookahead of an LP, the better its performance with conservative protocols. Efficient implementation of null messages is also facilitated if each LP maintains the set of its source and/or destination LPs. PARSEC provides a set of constructs to specify the lookahead and topology of a model and thus improve its performance with conservative implementations. These constructs are described in detail in the section Optimizing for Parallel Execution.

In optimistic protocols, an LP is allowed to process events in any order; however, the underlying synchronization protocol must detect and correct violations of the causality constraint. The simplest mechanism for this is to have each LP periodically save (or checkpoint) its state. Subsequently, if it is discovered that the LP processed messages in an incorrect order, it can be rolled back to an appropriate checkpointed state, following which the events are processed in their correct order. The rollback may also require that the LP unsend or cancel the messages that it had itself sent to other LPs in the system. An optimistic algorithm is also required to periodically compute a lower bound on the timestamp of the earliest global event, also called the Global Virtual Time or GVT. As the model is guaranteed to not contain any events with a timestamp smaller than GVT, all checkpoints timestamped earlier than GVT can be reclaimed. PARSEC provides a set of facilities that can be used to control the various parameters that affect the performance of an optimistic implementation. These include setting the frequency of checkpointing, and GVT computation among others. For a detailed description of these facilities, the reader is refered to the section on Optimizing for Parallel Execution

Details on the commands to compile and execute a PARSEC model on different parallel platforms using a variety of synchronization algorithms are contained in the manual.

## The PARSEC Language

PARSEC is a C-based language that was designed to cleanly separate the simulation model from the underlying algorithm (sequential or parallel) that may be used to execute the model. A program written in PARSEC is independent of any synchronization algorithm. When it is compiled, the analyst can indicate the specific simulation algorithm that is to be used to synchronize execution of the model: sequential, parallel conservative, or parallel optimistic. The compiler generates the appropriate code to interface the model with the corresponding run-time system: a splay-tree based implementation of the global event-list algorithm for the sequential implementation, a null-message or conditional event implementation of the parallel conservative synchronization algorithm, or a space-time implementation of the optimistic synchronization algorithm.

PARSEC has been implemented on a variety of sequential workstations and laptop machines, on networks of workstations and on scalable MPP platforms like the distributed memory IBM SP2 and on symmetric multiprocessor (SMP) platforms like the shared memory SparcStation 1000. It has been used for the parallel simulation of a number of applications in diverse areas including queueing networks, VLSI designs, parallel programs, mobile wireless multimedia networks, ATM networks, and high-speed communication switches and protocols.

PARSEC adopts the process interaction approach to discrete-event simulation. An object (also referred to as a PP for physical process) or set of objects in the physical system is represented by a logical process or LP. Interactions among PPs (events) are modeled by message exchanges among the corresponding LPs. We first describe the PARSEC primitives to define processes and the interprocess communication primitives and subsequently indicate how they are used to describe events.

### Entities

A PARSEC program is a collection of entity definitions and C functions. An entity definition (or an entity type) describes a class of objects. An entity instance, called simply an entity, represents a specific object in the physical system. Every PARSEC program must have a driver entity. This entity initiates execution of the simulation program and serves essentially the same purpose as the main function in C.

The declaration of an entity is syntactically similar to that of a C function; the key difference is that unlike a function, an entity does not return a value, and, in fact, generally doesn't return at all! An entity type consists of a heading that declares the name and formal parameters of the entity type and a body that declares local variables and defines its actions. For instance, the entity type declared in Figure 1 describes an object that models a resource manager. This entity type will be used as a running example to illustrate various PARSEC constructs. The heading in line 3 of the figure indicates that the entity type is called Manager and has one integer parameter called num_resources. The body of the entity is contained within curly braces in lines 4-13. The body is a compound C statement that may also include constructs to send and receive messages as described subseqeuntly.

An entity is created by the execution of a new statement and is automatically assigned a unique id on creation. PARSEC defines a type called ename which is used to store entity-identifiers. The following statement will create an instance of entity type Manager and store its identifier in variable manager, which must be declared to be of type ename.

manager = new Manager(10);

An entity can internally refer to its id using the keyword self. An entity instance terminates itself by `falling off the end'.

 ``` 1 message Request {ename requester;};  2 message Release {};  3 entity Manager (int num_resources) {  4   int resources = num_resources;  5   for (;;)  6     receive (Request req) when (resources > 0) {  7       resources--;  8       send Resource{} to req.requester;  9     } 10     or receive (Release rel) { 11       resources++; 12     } 13 }```

An entity may contain an optional

### Messages

Entities communicate with each other using buffered message passing. Every entity has a unique message buffer; asynchronous send and receive primitives are provided to respectively deposit and remove messages from the buffer.

#### Declaring Message Types

PARSEC uses typed messages. An entity type must define the types of messages that may be received by its instances. A message type is similar to a struct in C and consists of a name and a (possibly empty) parameter list. For instance, two message types are defined for the Manager entity type(lines 1-2): Request which has one parameter of type ename, and Release which has no parameters.

#### Sending a Message

An entity sends a message by executing a send statement. Each message is transparently timestamped with the current simulation time and is deposited in the destination buffer at the same (simulation) time at which it is sent. The send statement has the following form:

send message_type to destination;

where destination is a variable of type ename and message_type is a message whose type has been declared by the destination entity destination. For instance, execution of the send statement in line 8of the Manager will deposit a message of type Resource in the message buffer of the entity identified by requester. Message type declarations are global to a program (even if declared in separate files), so should be declared in a common header file.

#### Receiving a message

An entity accepts messages from its message-buffer by executing a PARSEC wait statement. In its most commonly used version, the receive statement has the following syntactic form:

```        receive (mt1 mv1) [when b1] statement1;
or receive (mt2 mv2) [when b2] statement2;
.
.
.
or receive (mtn mvn) [when bn] statementn;```

where mti is a message-type, mvi is a read-only message variable, bi an optional boolean expression referred to as a guard, and statementi is any C or PARSEC statement. The guard is a side-effect free boolean expression that may refer to local variables or message parameters. If omitted, the guard is assumed to be the constant true. The message-type and guard are together referred to as a resume condition and the resume condition together with the statement is refered to as a resume statement. A resume condition with message-type mti and guard bi is said to be enabled if the message buffer contains a message of type mti, which if delivered to the entity would cause bi to evaluate to true; the corresponding message is called an enabling message. A resume condition that is not enabled is said to be disabled.

For instance, the receive statement in line 6of the Manager entity consists of two resume statements. The resume condition (line 6) in the first statement ensures that the entity accepts a Request message only if enough resources are available (resources > 0). If so, the resource is allocated to the requesting entity (line 7-8). The second resume statement (line 10) accepts a Release message and simply increments the count of available resources. As discussed subsequently, the resume condition in a receive statement may include multiple message-types, each with its own boolean expression. This allows many complex enabling conditions to be expressed directly, without requiring the programmer to describe the buffering explicitly.

If two or more resume conditions in a receive statement are enabled, the timestamps on the corresponding enabling messages are compared and the message with the earliest timestamp is removed and delivered to the entity. By default, if all resume conditions in the receive statement are disabled, the corresponding entity is suspended until it receives an enabling message. A timeout mechanism is also supported as described in the section after the following.

### Events

Each event in a discrete-event simulation model simulates some activity of interest in the physical system and may involve one or more objects. Every event is associated with a time stamp that indicates the time at which the corresponding event occurs in the system. Execution of a discrete-event simulation model requires that all events in the system be executed in their strict time stamp order.

Since an event is modeled by a message in a PARSEC program, each message carries a timestamp. By default, the timestamp placed on a message is the current (simulation) time of the entity that sends the message. A message may be explicitly timestamped with a future time as described later.

The simulation time of an entity can be advanced only when it receives a message or when it executes a hold statement. When an entity with a simulation time ts, receives a message with time stamp te, the simulation time of the entity is set to the larger of ts or te. This ensures that the simulation time of an entity increases monotonically.

A hold statement is used to suspend the entity for a given duration in simulation time. For instance, the following statement will cause the entity executing the statement to suspend until the simulation time of the system advances by t time units. In other words, if the the simulation time of the entity was ts prior to execution of the hold statement, it will be ts + t when the entity executes the statement following the hold statement.

hold(t);

As explained earlier, advances in simulation time such as this are used to represent the time required by some activity (i.e. event) in the physical system being simulated.

As an example, consider the Job entity in Figure 2. The entity periodically sends a request for a resource to the manager and waits to receive the Resource message indicating availability of the resource. It simulates use of the resource by executing the hold statement (line 8) which causes the simulation time for the entity to advance by the specified time interval. It then returns the resource to the pool by sending a Release message to the manager (line 9).

 ``` 1 message Resource {};  2 entity Job(int   processing_time,  3            ename manager}{  4   for (;;) {  5     hold(processing_time);  6     send Request{self} to manager;  7     receive (Resource res) {  8       hold(processing_time);  9       send Release to manager; 10     } 11   } 12 }```

#### Conditional Events and Timeouts

PARSEC also provides constructs to schedule conditional future events. These are events that may be cancelled after they have been scheduled. A conditional event is scheduled by using a variation of the receive statement introduced in the previous section. A receive statement may optionally specify a delay-time as follows:

```        receive (mt1 mv1) [when b1] statement1;
...
or timeout after (tc) {
...
}```

Assume that an entity executes a receive statement with delay-time tc at time t. This causes a message of type timeout, with timestamp t + tc, to be conditionally scheduled for the entity. This message is cancelled if an enabling message is available in the message buffer of the entity within the inclusive interval [t, t + tc]; otherwise the timeout message is sent to the entity by the runtime system. The message type timeout is declared automatically by the compiler for every entity and must not be declared by the user. If tc is omitted, it is set by default to an arbitrarily large number such that the corresponding entity is blocked (potentially forever) until an enabling message is available in its buffer. In particular, if tc is specified to be 0, the statement works like a non-blocking receive: if the message buffer does not contain any enabling message, the entity will continue execution at the same simulation time at which it was suspended.

The event corresponding to the receipt of a timeout message is conditional because it is cancelled if an enabling message is received by the entity. Such a statement can be used to model interruptible and asynchronous activities in the physical system.

## Examples

### Topology Creation

We present a series of examples that demonstrate the types of communication topologies that are commonly used in PARSEC programs. The examples use a simple entity type called Delay. The entity simply waits until it receives a message of type Ping. On receipt of the message, it suspends itself for a randomly distributed interval (in simulation time) and then forwards the message to one of its communication partners. On completion of the simulation, each entity is sent an endsim message by the run-time system. This message is used by the entity to print out the total number of hops made by the message

The first example demonstrates communication between a pair of Delay entities. The simulation is run for 10000 time units and uses a single Ping message. Every PARSEC program must have a driver entity. This entity is responsible for initiating the simulation (similar to the main function of a C program). (Exercise: Modify the example to use 10 ping messages; print the number of round trips made by each ping message at the end of the simulation time.)

 ```message Init_Delay {   ename id; }; message Ping{   int id;   int trips; }; entity Delay(int id, int delay_time) {   ename next;   message Ping ping;   receive (Init_Delay init)      next = init.id;   while (1)     receive (Ping p) {       ping = p;       if (ping.id == id) {         printf("\n Message No %d: Number of round trips completed %d",                id, ping.trips);          ping.trips++;       }       hold(delay_time);       send Ping{ping.id, ping.trips} to next;       } }       ``` ```entity driver() {   ename e1, e2;   e1 = new Delay(1, 10);   e2 = new Delay(2, 10);    send Init_Delay{e2} to e1;    send Init_Delay{e1} to e2;    send Ping{1,0} to e1;    send Ping{2,0} to e2;    setmaxclock(10000); }```

The next example sets up a ring containing 5 delay entities, where each entity knows the identity of its successor entity. The code for the entity is not changed; rather only the driver is changed to modify the communication topology. (Exercise: modify the program such that each entity knows the identity of both its predecessor and successor entities)

 ```entity driver() {   ename prev, next, first;   first = new Delay(10);   prev  = first;   for (i = 0; i < 4; i++) {     next = new Delay{10};     send Init_Delay{next} to prev;     prev = next;   }   send Init_Delay{first} to prev; }```

We now generalize the definition of a delay entity to allow multiple communication partners. The following entity called DelayFork is connected to N entities. On receiving a ping message, the entity forwards this message to any one of the N neighbors with equal probability. The identity of the communication partners of the DelayFork entity are sent to it using an InitDelayFork message. This message has two parameters count which refers to the number of communication partners for the entity and array id-set that contains their identifiers. The declaration of the array id-set restricts the entity to a maximum of 10 communication partners.

 ```message InitDelayFork{   int   count;   ename id-set[10]; }; entity DelayFork(int id, int delay_time) {   ename next[10];   int i, N;   receive (InitDelayFork init) {     N = init.count;     for (i = 0; i < N; i++)       next[i] = init.id-set[i];   }   while (1)     receive (Ping ping) {       printf("\n Message No %d: Number of hops completed %d",              id, ping.hops);        hold(delay_time);       send Ping{ping.id, ping.hops+1} to next[urand(1,N)];     } }```

The driver entity to set up a fully connected network of 5 DelayFork entities is as follows:

 ```entity driver() {   ename eids[5],i;        for (i = 0; i < 5; i++)     eids[i] = new DelayFork(i, 10);   for (i = 0; i < 5; i++)     send InitDelayFork{5, eids[0]:5*sizeof(ename)} to eids[i];   setmaxclock (10000); }```

### Servers

#### Priority Server: Preemptive

 ```message HighPriorityJob{   int processing_time; }; message LowPriorityJob{   int processing_time; }; entity PriorityServer() {   int time_left;   int current_time;   while (1) {     receive (HighPriorityJob high) {       hold(high.processing_time);       /* process job */     }     or receive (LowPriorityJob low) {       current_time = simclock();       time_left    = low.processing_time;       while (time_left > 0) {         receive (HighPriorityJob high) {           time_left   -= (simclock() - current_time);           current_time = simclock();           hold(high.processing_time);           /* process job */         }         or timeout after (time_left) {           time_left = 0;           /* process low priority job */         }       }     }   } }```

## Execution of PARSEC Programs

PARSEC programs are executed just as normal C programs are executed. Please see the PARSEC User's Manual for details on compilation and execution of PARSEC Programs.

A PARSEC program is a collection of entity and function definitions. Each program must include an entity called driver. This entity plays a role similar to the main function of a C program -- execution of a PARSEC model begins by executing the first statement in the body of the driver entity.

A PARSEC simulation terminates when the simulation clock exceeds the specified simulation horizon (the time period over which the model is to be simulated). The simulation horizon is specified using the predefined setmaxclock function which takes a value of type clocktype (or any numeric value, typically).

### Explicit Message Timestamps

By default, the timestamp placed on a message is the (simulation) time of the entity that sends the message. A message may be explicitly timestamped with a future time using the following variation of the send statement:

send message_type to destination after t

The preceding statement will cause the message message_type to carry a timestamp of clock+t, where clock refers to the current simulation time of entity destination.

For instance, the body of the job entity in Figure 2 could be written as shown in Figure 7 where both send statements use the after clauses to store explicit future timestamps on the messages. However, there is one significant difference between using a hold statement followed by a send and directly specifying the timestamp in the send statement: in the former case, the hold statement causes the simulation time of the entity to advance; not so in the latter. In particular, the hold statement is used to simulate processing time within the entity, while the send ... after construct is used to simulate a transmission delay.

 ```entity Job(int processing_time, int transmission_delay, ename manager) {   for (;;) {     send Request{self} to manager after transmission_delay;     receive(Resource res) {       hold(processing_time);       send Release to manager after transmission_delay;     }   } }```

Several PARSEC facilities are available for specifying more complex resume conditions in receive statements, such as using message parameters in guards, compound resume statements, etc. Most of these facilities are more useful to the parallel programmer rather than the parallel simulator. In a simulation, it is usually appropriate for the message with the lowest time-stamp to be chosen. Nevertheless, some of these features will be described briefly.

#### Message Parameters

The guard in a resume statement can reference both local variables of the entity and message parameters. For instance, assume that the manager in our running example receives requests for one or more printer units and that incoming requests are serviced using the first-fit discipline. The following fragment shows how the resume condition is modified to ensure that a Request message is accepted only if the requested number of units are available.

```        message Request {ename requester; int count; };
.
.
.
receive (Request req) when (req.count <= resources)
.
.
.```

PARSEC also provides a number of pre-defined functions that may be used by an entity to inspect its message buffer. For instance, the function qsize(message_type) returns the number of messages of type message_type in the buffer. A special form of this function called qempty(message_type) is defined, which returns true if the buffer does not contain any messages of type message_type, and returns false otherwise. This function may be used to impose priorities on incoming messages. Assume that the manager is to be modified such that a request message is accepted only if no Release messages are present in the buffer. A simple way to do this is to strengthen the guard for the Request message as follows:

`        receive (Request req) when (qempty(Release) && (req.count <= resources));`

#### Compound Resume

At times, we would like to not process an event until two or more enabling conditions are met. For example, in the Dining Philosophers problem, the Philosopher cannot eat until he acquires two forks. This can be specified in PARSEC using a compound resume. The following is a generic example of its use.

```        receive (Ma ma, Mb mb, ... , Mn mn) when (ba && bb && bn) {
statement;
}```

However, as of this writing, compound resume conditions have not been implemented in PARSEC.

### Friend Functions

Friend functions add some of the functionality of C++ to PARSEC. Basically, they are functions which can access the local variables of an entity without passing them as parameters. They were provided in PARSEC to support backward compatibility with Maisie, and because people love to use them. However, friend functions have proven in the past to lead to poor programming practices, are generally less efficient than ordinary function calls, and are very difficult to debug. On efficiency and stylistic grounds, we recommend not using them.  Please see the PARSEC User's Manual for details on their use.

## Parallel Execution

Executing in parallel requires that the program be linked with one of the parallel runtime systems. See the PARSEC User's Manual for details on compilation options. However, to run effectively in parallel, a number of additional guidelines should be followed, and in some cases are explicitly required.

### General Guidelines

#### Restrictions

Parallel PARSEC programs must conform to the following restrictions. These restrictions apply to almost any message-based parallel language and are not specific to PARSEC. The PARSEC compiler will not generate errors or warnings for the following problems because the same compiler is used whether the simulation is run sequentually or in parallel. (Simulation algorithms are switched by linking in another simulation runtime library.) When a program violating these rules runs in parallel it will most likely abort or produce incorrect results.

• Shared/Global Variables: A parallel PARSEC simulation should not use `global' variables. This includes function and file scope static variables since they are basically equivalent to global variables. Also, it is forbidden for two entities to have pointers to the same data. The state of an entity must be solely determined by the variables declared in it and these variables must not be shared between entities. These restrictions arise for the following reasons:
• PARSEC assumes that all changes to an entity's state are the result of messages. This is violated with shared entity state.
• Optimistic simulation requires entity state saving which doesn't work with shared state. Global variables are not checkpointed by the optimistic runtime system.
• Shared memory machines will have 1 copy of the global variables while distributed memory machines will have N (non-consistent) copies, making such programs non-portable.

There are exceptions to this rule. Read-only variables initialized at the beginning of the simulation can be global. The problem with this is that on distributed memory machines the initial values assigned on one node are not propagated to any other nodes. Thus each node's global variables must be initialized individually. One way to solve this problem in a portable fashion would be to initialize the globals when they are first used by reading the proper values from a centrally accessible file.

• Pointers cannot be passed in messages or entity initialization parameters. Note that this implies that dynamic linked-list data-structures cannot be passed. (Arrays must be used instead.) This restriction is because a pointer on one node of a distributed memory computer is meaningless on another node.

#### Partitioning

For parallel implementations, the simulation model must be partitioned by allocating entities among the processors. PARSEC allows the programmer to specify the specific node on which an entity will be created by using the at option during entity creation. In general, the model should be partitioned such that message communication between nodes is minimized. Also, there must be some parallelism in the simulation, i.e. multiple nodes should be doing work on the simulation concurrently. For example, a simulation with a single packet bouncing around a network will not have any parallelism. Depending on whether the parallel execution uses conservative or optimistic algorithms, further refinements, described in the next sections, may be needed to improve its performance.

### Conservative Simulation

There are two main additions that need to be made to a simulation program written in PARSEC, in order to enable it to run using conservative protocols:

1. communication topology, and

#### Communication Topology

The runtime system needs to be informed about the communication topology between the entities in the system. This information is used by the system to do the necessary synchronization. The runtime system implicitly maintains a source-set and a destination-set for each entity. source-set is the set of all the entities that a given entity can receive messages from, and destination-set is the set of all the entities that it can send messages to. Every entity needs to inform the runtime system of the entities in its source or destination set. This is done by using the following PARSEC system calls:

• del_source(e): Delete ename e from my source set.
• del_dest(e): Delete ename e from my destination set.

Exceptions:

• If an entity e1 creates entity e2, then at the time of entity creation, the runtime system automatically places e2's ename in e1's destination set, and e1's ename in e2's source set. If this link is not necessary for the given simulation, user can delete this link, by using del_dest in the parent, and del_source in the child, immediately following the entity creation.
• An entity does not need to add itself to its source or destination set, even if it intends to send messages to itself.
• If an entity e1 in the source-set of an entity e2 terminates (finishes execution), e1 is automatically deleted from the source-set of e2. However, if one of the destinations dies, it has to be explicitly removed from the destination list. (Otherwise, it will cause some inefficiency - not an error.)

For the conservative runtime, the sparser the topology, the better the performance. Therefore, only add the sources and destinations that are actually going to be used. If you have more links than you are going to use, e.g. a completely connected network, it is not going to create an error situation - it is only going to make the simulation less efficient (note that you have to ensure that lookahead is non-zero in every cycle of links -- see the next section. Introducing unnecessary links may make this job tougher).

• Static Topology: If the simulation topology is static i.e. all the entities and their source and destination set are created at simulation time 0, and they do not change until the end of simulation, your job is very simple. For each entity, as soon as it finds its sources and destinations (has to be at simulation time 0), add them to its source and destination sets using the calls mentioned above. Do not worry about deleting sources or destinations.
• Dynamic Topology: If the topology is dynamically changing, you have to ensure the following conditions while adding/deleting source or destinations (we only give conditions for adding. Similar conditions exist for deletion). If the earliest message on a channel from entity b to c has a timestamp t, then, the user has to ensure that the following conditions are satisfied:
1. c should add b to its source set before or at simulation time t.
2. If c adds b to its source set at simulation time , b should add c to its destination set before or at simulation time .

Whenever an entity issues a receive in PARSEC, there is a possibility that it may be suspended (for instance, if the message buffer does not contain any messages of the type specified by the receive statement). Before being suspended, an entity can inform the runtime about the minimum timestamp increment (i.e. the difference between the timestamp on an outgoing message and the timestamp on the preceding input message) on the earliest output that the entity may generate. This value is called lookahead, and is expressed using the function call setlookahead(v,m), where v is the value of the lookahead, and m is a ceiling on that lookahead (explained subsequently).

Lookahead is used by the runtime to ensure that the parallel simulation does not deadlock, and to improve its performance. A sufficient condition (weaker conditions also exist, but we will not discuss them, in order to keep discussion simple) to avoid deadlock is as follows: In every cycle of the simulation model, there should be at least one entity that always issues a setlookahead(v,m) with a positive v before going into a receive statement. In general, the larger the lookahead in the system, the better the performance.

Consider the following situation: A pre-emptive priority server entity has scheduled a timeout after timestamp t, corresponding to a tentative departure of a low priority job, if no high priority job arrives before the timeout. The entity, therefore, is suspended waiting for a high message, or a timeout. Suppose the precomputed service time for the high job is s. If the next job that leaves the entity is in response to a high job received (which will pre-empt the current job), then the timestamp increment would be equal to s. But, if the next job goes out in response to the timeout (i.e. if the current job is not pre-empted), the timestamp increment is zero. Therefore, according to the definition of lookahead given above, the lookahead that the entity can express before going into the receive would be only zero. The second parameter of the setlookahead function is provided to help in such situation. In the above described situation, before going into receive, user can say setlookahead(s,simclock() + t) which means that the lookahead of the entity is equal to s, subject to a maximum value of simclock() + t. Whenever max lookahead is not relevant, the programmer needs to say setlookahead(v,MAXINT) before every receive statement.

setlookahead needs to be called before issuing each receive statement because these values are reset after each message receive.

Examples:

• FCFS servers: Since an FCFS server would be suspended only waiting for a new job, it should call setlookahead(next_service_time, MAXINT) before issuing any receive, where next_service_time is the service time for the next job.
• Pre-emptive Priority servers: a priority server may suspend in two places:
• Waiting for a new job: In this case it should call setlookahead(next_service_time, MAXINT) before issuing receive, where next_service_time is the minimum of the service times of each service class.
• Waiting for the servicing of the current job to finish: In this case, it should call setlookahead(next_service_time, current_departure_time) before issuing the receive, where next_service_time is the minimum of the next service times for all the service classes that can pre-empt the current job, and current_departure_time is the departure time for the job in service.

### Optimistic Simulation

Variables

• Global variables are not checkpointed; if the global variables are modified during execution, it will lead to program errors.
• All variables declared within each entity will be (transparently) checkpointed by the run-time system at some checkpointing frequency.
• Dynamic memory acquired by an entity via the standard operating system calls (e.g. malloc() etc), are not checkpointed. However, the PARSEC optimistic runtime system provides four functions to handle dynamic memory in the entity; all memory acquired using these functions will be checkpointed. The first two are used to allocate successive blocks of a fixed size:
• char * MC_Fmalloc(nbytes)
• void MC_Ffree(pointer)

This is an optimization in the memory management: when the program calls MC_Fmalloc(nbytes), the runtime will get a block of memory, partition this block into small pieces, and put them into the free memory pool in the runtime.

The remaining two functions are used to allocate memory blocks of variable sizes and are analogous to the standard dynamic memory allocation function provided by UNIX.

• char * MC_Vmalloc(nbytes)
• void MC_Vfree(pointer)

Variable-size memory operations are supposed to be used infrequently and for larger data structures.

NOTE: Memory allocated by standard C libraries (malloc() etc.) should not be freed at the end of the simulation with the free() function, because this will prevent rollback.

Messages

• Variable length messages: (Variable length messages are those which include a union of types, or perhaps an oversized array, different parts of which are used each time it is sent.) Unused portions of the message must be zeroed out each time it is sent. If an entity is rolled back, it may be rolled back before the current GVT (depending on the checkpointing interval). Since the entity re-computes the messages before GVT, it should re-generate exactly the same outgoing messages. If the unused portion of the message contains garbage data, the runtime may think that the entity generated a new message before the GVT, which would be considered an error.
• Simultaneous Messages: if there is a receive statement with multiple message types, the execution of your model must be independent of the order in which those simultaneous messages arrive. For example, the following program will cause errors in optimistic runtime.
• ```entity Distributor() {
for(;;)
assign a job to A;
}
assign a job to B;
}
}```

If both a request_from_A and a request_from_B messages arrive at the same simulation time, but the request_from_B arrives earlier in real time, the distributor will give job1 to B, and later give job2 to A. However, if the distributor entity is rolled back, it may assign job1 to A and job2 to B because both requests are in its input queue after the rollback. This kind of non-determinism will confuse the optimistic runtime system into reporting an error.  This is a subtle error which requires careful design to avoid.

Input and Output

• Users must be careful about I/O operations in optimistic simulation because the standard C I/O functions are not reversible (i.e. cannot be rolled back).
• INPUT:

• For example, the following program will execute the wrong data after a rollback happens because we don't roll back the file pointer.

```    FILE  *fin;
char   line[LSIZE];
while( fgets( line, LSIZE, fin ) != NULL ) {
process mymsg according to the context of the array "line".
}
} /* while */```

The correct way of programming is:

```    FILE  *fin;
char   line[LSIZE];
int  f_offset = 0;

while(1) {
fseek(fin, f_offset, 0);
if( fgets(line, LSIZE, fin) == NULL ) break;
f_offset += strlen(line);

process mymsg according to the context of the array "line".
}
} /* while */```
• OUTPUT:

• Users can use mayc_fprintf() instead of fprintf() function. The runtime system keeps output data internally and prints them out after commitment.

System Parameters

• The performance of optimistic simulation depends on several system parameters, i.e.:
• save_interval : the check-pointing interval (# of time advancing).

• For example, assigning 30 to save_interval will tell system to checkpoint an entity when the entity advances its clock 30 times.

• gvt_window : the interval for processing GVT computation. (#_events)

• For example, assigning 300 to gvt_window will inform the runtime system to perform GVT computation after 300 events have been processed in this processor.

• throttle_window : the window size within which an entity can be processed aggressively. (# of time units)

• If the throttle_window is set to 4000, an entity stops processing future events when its LVT is larger than GVT by 4000 time units and just waits for synchronization.

• garbage_collect : the interval for performing garbage collection. (#_of_gvt_comp).

• If the garbage_collect is set to 5, the runtime system will collect committed data after it performs GVT computation five times.

• delayed_receive_window: the interval for NOT receiving remote messages. (#_time_units)

• In order to avoid frequently polling incoming message buffer, users can enlarge delayed_receive_window. If the delayed_receive_window is set to 5, the runtime system won't check the system message buffer unless its LVT is greater than previous polling time stamp by 5.

In order to assign values to these parameters, users need to create a file called MC_opt_parameters . Users can insert "parameter value" pairs in the file. If a parameter is not specified by users or the file "MC_opt_parameters" does not exist in the current working directory, the runtime system chooses default values.

```    File MC_opt_parameters contains:
------------------------
save_interval    30
throttle_window  4000
gvt_window       300
------------------------
```

This is the output generated by the optimistic runtime system:

```-------------------------------------------------------------------------
| Total nodes | xth node |  ftime  |  clock  |    max sim_t    | f_minu |
|    2        |     1    |   52.61 |    4.01 |     168001      |  38.55 |
-------------------------------------------------------------------------
| Save_inter  | Send_ev  | Wait_w  | sync_ev | garbage_w |  throttle_w  |
|      60     |      1   |      1  |    500  |       0   |      4000    |
-------------------------------------------------------------------------
|Ent_exe_t|State_sve_t| Block_t | Rlback_t |Garbage_t|  Wait_t | Send_t |
|   31.10 |      1.98 |    1.46 |     0.39 |    0.12 |   15.24 |   2.58 |
|    4056 |       76  |      33 |       12 |      69 |     248 |    123 |
-------------------------------------------------------------------------
|True_comp|  msg_out  |canceled |  resent  |remote_srh| sys_srh| event_q|
|  96.83% |       123 |       1 |        0 |     2.20 |   0.02 |   1.35 |
-------------------------------------------------------------------------```

Misc

• No zero-lookahead cycles should exist. Please refer to the previous section on conservative algorithm.
• If a random number generator is used, the seeds must be defined inside the entity so that the seed can be checkpointed.

#### Known Bugs

• We don't know of any, please tell us.

## References

Fujimoto 1993
Parallel Discrete Event Simulation: Will the field survive?

R. Fujimoto
ORSA Journal on Computing, Volume 5(3), 1993, pp. 213-230.

Maisie 1994
Maisie: A Language for the Design of Efficient Discrete-Event Simulations,

Rajive L. Bagrodia and Wen-Toh Liao,
IEEE Transactions on Software Engineering, Vol. 20(4), April, 1994, pp. 225-238.
(Gzipped PostScript File)

PARSEC User Manual
(PostScript File)

Written by Rajive Bagrodia and Richard Meyer.

Last updated: Thursday, 28-Aug-97 20:48:21 PDT