This example programs the Sieve of Eratosthenes to generate all prime numbers less than 1000. The first instance of the sieve entity is created by the driver and subsequent instances are created recursively such that the first number received by a new instance is a prime number. Subsequently the entity discards all multiples of its prime number and sends others to the next sieve in the pipeline. What follows is a Maisie program to do this. Note, nnodes() is a system defined function which returns the number of nodes used for the parallel execution.
1 #include "maisie.h"
2 entity sieve{myno}
3 int myno;
4 { message number { int number; };
5 ename next_sieve;
6 int myprime;
7 wait until mtype(number)
8 myprime = msg.number.number;
9 printf("Sieve number %d is for prime number %d\n", myno, myprime);
10 next_sieve = new sieve{ myno+1 } at ((myno+1)%nnodes());
11 for(;;)
12 wait until mtype(number)
13 if(msg.number.number % myprime)
14 invoke next_sieve with number = msg.number;
15 }
16
17 entity driver{}
18 { int i;
19 ename first;
20 first = new sieve{ 1 } at (1);
21 for(i = 2 ; i <= 1000; ++i)
22 invoke first with number { i };
23 }
We present a series of examples that demonstrate the types of communication topologies that are commonly used in Maisie 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. The function exp used in the code returns a truncated value sampled from a random exponential distribution with the given mean value. 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.
1 entity driver
2 { ename e1, e2;
3 e1= new delay(1,10);
4 e2= new delay(2,10);
5 invoke e1 with init{e2};
6 invoke e2 with init{e1};
7 invoke e1 with ping{1,0};
8 invoke e2 with ping{2,0};
9 maxclock ("10000");
10 }
11 entity delay{myno, mean_time}
12 int myno, mean_time;
13 { ename next;
14 message init{ename hisid;};
15 message ping{int mno, trips;}p1;
16
17 wait until mtype(init)
18 next=msg.init.hisid;
19
21 while (true) do
22 wait until
23 mtype(ping){
24 p1=msg.ping;
25 if (p1.mno==myno) {
26 printf("\n Message No", myno,
27 "Number of round trips completed", p1.trips);
28 p1.trips ++;
29 }
30 hold(exp(mean_time));
31 invoke next with ping{p1.mno, p1.trips };
32 }
33 }
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)
{
1 entity driver
2 { ename prev,next,first;
3 first = new delay(10);
4 prev = first;
5 for (i=0;i<4; i++)
6 { next = new delay(10);
7 invoke prev with init{next};
8 prev = next;
9 }
10 invoke prev with init{first}
11 invoke e2 with init{e1};
12 }
We now generalize the definition of a delay entity to allow multiple communication partners. The following entity called delay-fork 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 delay-fork entity are sent to it using an init-set 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.
1 entity delay-fork{myno, mean_time}
2 int myno, mean_time;
3 { ename next[10];
4 int i,N;
5 message init-set{int count; ename id-set[10];};
6 message ping{int mno, hops;}p1;
7
8 wait until mtype(init-set){
9 N= msg.init-set.count;
10 for (i=0; i<N; i++)
11 next[i]=msg.init-set.id-set[i];
12 }
13 while (true) do
14 wait until mtype(ping) {
15 p1=msg.ping;
16 printf("\n Message No", myno,
17 "Number of hops completed", p1.hops);
18 hold(exp(mean_time));
19 invoke next[urand(1,N)] with ping{p1.mno, p1.hops++};
20 }
21 }
The driver entity to set up a fully connected network of 5 delay-fork
entities is as follows:
1 entity driver
2 { ename eids[5],i;
3
4 for (i=0;i<5;i++)
5 eids[i] = new delay-fork(i,10);
6 for (i=0;i<5;i++)
7 invoke eids[i] with init{5, eids[0]:5*sizeof(ename)};
8 maxclock (10000);
9 }
Consider a closed queueing network (henceforth referred to as CQNF) that consists of N fully connected switches. Each switch is a tandem queue of Q fifo servers. A job that arrives at a queue is served sequentially by the Q servers and is thereafter routed to one of the N neighboring switches (including itself) with equal probability. The service time of a job at a server is generated from a negative exponential distribution, where all servers are assumed to have an identical mean service time. Each switch is initially assigned J jobs that make a predetermined number of trips through the network. Listing of a complete Maisie program to simulate this system is shown below:
#include "maisie.h"
#define N 16
extern entity basic_stats{};
1 entity driver{}
2 { ename rtr[N],q[N],stat1;
3 int i;
4 stat1 = new basic_stats{"Average System Time"};
5 for (i=0;i<N;i++)
6 q[i] = new queue{5,1000,stat1} at i;
7 for (i=0;i<N;i++)
8 rtr[i] = new router{10,10,q} at i;
9 for (i=0;i<N;i++)
10 invoke q[i] with idmsg{rtr[i]};
11 }
15 entity router{njobs,mtrips,qids}
16 int njobs, mtrips;
17 ename qids[N];
18 { message job{int stime; int count;} j1;
19 int i;
20 for (i=0;i<njobs;i++)
21 invoke qids[i%N] with job{0,0};
22 for (;;)
23 wait until mtype(job) {
24 j1=msg.job;
25 if (j1.count < mtrips) {
26 hold (j1.stime-sclock());
27 invoke qids[iurand(0,N-1)] with job=j1;}
28 }
29 }
30 entity queue{nsrvr, mtime, statid}
31 int nsrvr,mtime; ename statid;
32 { int i,t1,lastj[10];
33 ename rid;
34 message job{int stime; int count;} j1;
35 message idmsg{ ename id;};
36 wait until mtype(idmsg) rid= msg.idmsg.id;
37 for (i=0;i<nsrvr;i++)
38 lastj[i]=0;
39 for (;;)
40 wait until mtype(job) {
41 j1=msg.job;
42 t1=j1.stime;
43 for (i=0;i<nsrvr;i++) {
44 lastj[i]=MAX(t1,lastj[i]) + expon(mtime);
45 t1=lastj[i];
46 }
47 invoke rid with job{t1,j1.count+1};
48 invoke statid with value{(t1-j1.stime)};
49 }
50 }
The Maisie model consists of two primary entities:
a queue entity to model the tandem servers in a queue and a router entity
that routes a job after it has completed service at a queue.
Each job in the network may be modeled as a separate entity or be abstracted by a sequence of messages. We adopt the latter approach. The driver entity is responsible for creating the queue and router entities. As the queue and router entities communicate with each other, each must have the entity-identifier for the other. Rather than use global variables for this purpose, the appropriate id is passed to the entity as either an entity parameter (as when creating the router entities in line 8) or in a separate message (as for the queue entities in line 10). The driver entity also instantiates a statistics collection entity (basic_stats) from the Maisie library (line 4). This entity is used to compute the average system time spent by a job in a queue.
When the simulation is completed, every entity including the statistics collection entity is sent an endsim message. On receiving this message, the entity prints its report.
We first consider the queue entity (lines 30-50) that simulates service of incoming jobs at each of its servers. Array lastj tracks the time at which the last job serviced at the queue departed from each server. The service time for a job at the ith server is generated from an exponential distribution and used to update lastj [i] (line 44). When the job has been serviced at each server, its trip count and service completion time are incremented and it is forwarded to its router entity (line 47). Also, the total time spent by the job in the queue is sent to the statistics collection entity (line 48).
The jobs initially allocated to each switch of the physical network are initially allocated, in the simulation model, to the corresponding router entity. On being created, a router entity distributes these jobs among the various queue entities (line 21). Subsequently, for each incoming job, if the incoming job has not completed its required number of trips, the router entity generates a future message that simulates arrival of the job at the next switch in the network: it delays the job appropriately by executing a hold statement in line 26 (function sclock() returns the current value of the simulation clock), and then forwards the job to one of the N queue entities (line 27). Note that if the incoming job has completed the required number of trips, no additional messages are generated or scheduled. This implies that the event-list becomes empty when each job in the system has completed the required number of trips.
The program was subsequently refined for a parallel implementation where each queue and its corresponding router entity execute on a separate processor. Except for the driver entity, the remainder of the program remains unchanged. The driver entity must be changed to specify remote creation of entities. The modified driver entity is shown below. The only change in the entity is to extend each new statement with the at clause (lines 6 and 8) to indicate the processor number on which the corresponding entity is to be created and executed.
1 entity driver{}
2 { ename rtr[N],q[N],stat1;
3 int i;
4 stat1= new basic_stats{"System Time"};
5 for (i=0;i<N;i++)
6 q[i] = new queue{5,1000,stat1} at i;
7 for (i=0;i<N;i++)
8 rtr[i] = new router{10,10,q} at i;
9 for (i=0;i<N;i++)
10 invoke q[i] with idmsg{rtr[i]};
11 }