MIDTERM EXAM EXAMPLE
ECE 575
Object-Oriented, Discrete Event Simulation
Midterm Exam, Oct 27, 1994
Open Book.
1. In each of the following, circle the most applicable architecture.
Explain your answer:
a) A staff of volunteers handling incoming pledges for a fund raising drive
multiserver pipeline divide&conquer
Explanation:
________________________________________________________________________
________________________________________________________________________
b) A committee assigned to produce a report that has formed into independent
sub-committees
multiserver pipeline divide&conquer
Explanation:
________________________________________________________________________
________________________________________________________________________
c) The processing of criminal cases as they wind through the legal system
multiserver pipeline divide&conquer
Explanation:
________________________________________________________________________
________________________________________________________________________
d) A surgical team in a hospital operating room
multiserver pipeline divide&conquer
Explanation:
________________________________________________________________________
________________________________________________________________________
e) A group of tellers at a bank each serving the next person in the line
formed in a waiting area common to all the tellers (no lines form in front
of each teller)
multiserver pipeline divide&conquer
Explanation:
________________________________________________________________________
________________________________________________________________________
f) Voters in an election.
multiserver pipeline divide&conquer
Explanation:
________________________________________________________________________
________________________________________________________________________
2. Consider a binary tree having height h (there are h>0 levels and each node
has 2 children). Each non-leaf node has a divide and conquer co-ordinator with
associated partitioner and compiler. The partitioner and compiler take time,
pt, to partition a problem, and time, ct, to compile the partial results,
respectively. The coordinator at a node receives problems from its parent and
sends the partitioned subproblems to its two children. The children return
solved subproblems to the parent, which when both partial solutions are obtained
and compiled, sends the solved problem to its parent. The root node receives
problems from external world and returns solutions to it. The leaf nodes each
contain a single processor without queue. When a problem is partitioned, each
subproblem takes exactly half the original processing time. It takes time com
for a problem packet to travel (one way) between parent and child.
Let TA(h,p) be the turnaround time for a problem to be solved arriving at a
node at level h, assuming that problems take p time units to solve (by a single
processor).
a) We have that
TA(h,p) = C + TA(h-1,p/2)
where C = _________________________________
b) This equation is solved as:
TA(h,p) = h*C + p*2-h
Explain why the turnaround time first decreases and then increases as the height
of the tree, h, increases
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
c) The maximum throughput possible for a binary architecture of height h is:
____________________________________________________________
d) If queues were added to each of the coordinators would the maximum possible
throughput increase? yes_____ no _____ depends ______
Explanation:
________________________________________________________________________
________________________________________________________________________
e) Under the same conditions (addition of queues to coordinators), if the
problem arrival rate exceeds the maximum possible throughput, would the average
turnaround time be ( larger than _____ smaller than______ the same as
_________ ) TA(h,p)?.
Explanation:
________________________________________________________________________
________________________________________________________________________
f) What advantage is there for adding queues to the coordinators:
________________________________________________________________________
3) We want to design a generator with a state variable that holds a container.
The generator consults this container for the next output and time-advance. The
container holds a finite number of such output/time-advance pairs and the
generator cycles through these pairs forever (until receiving a stop). Consider
each container below:
container Suitable Best Choice Reason
yes no yes no
stack ___________________________ ___________________________
queue ___________________________ ___________________________
set ___________________________ ___________________________
binrel ___________________________ ___________________________
4) An acceptor is an experimental frame component that monitors a simulation run
for occurrence of 'interesting' conditions. For example, it may count the number
of external events received on an input port and issue a stop signal when this
number reaches a particular value. Although in class, we have placed the
expiration of observation time in the transducer, the natural place to put it is
the acceptor. When the acceptor receives a positive number on port 'start, it
starts waiting for interesting inputs for an observation interval given by the
positive number.
Fill in the missing code (examine the complete model description first):
(make-pair atomic-models 'acc)
(send acc def-state '(
_________________________________
_________________________________
_________________________________
))
(send acc set-s
(make-state
'phase 'passive
'sigma 'inf
_________________________________
_________________________________
_________________________________
)
)
(define (ext-acc s e x)
(set-state-clock! s (+ (state-clock s) e))
(case (content-port x)
(start (hold-in _________ ________________))
(in (when (interesting? (content-value x))
;;assume that interesting? has been defined
(set-state-events! s (+ (state-events s) 1))
)
(if (>= (____________ ) (state-threshhold s))
(hold-in _______ _________)
:::else
___________
)
)
(else (error 'ext-acc "invalid input port name --> %~" (content-port x)))
)
)
)
(define (int-acc s)
(case (state-phase s)
(active (passivate))
))
(define (out-acc s)
(case (state-phase s)
(active
(make-content 'port 'stop)
(else (make-content))
))
(send acc set-ext-transfn ext-acc)
(send acc set-int-transfn int-acc)
(send acc set-outputfn out-acc)
5) A System Entity Structure can be pruned to give the following simulation models
Draw the SES showing all entities, aspects, specializations and coupling
(aspects and specializations may be any names you choose).