Maisie Publication Abstracts
Maisie is a C-based simulation language that can be used for
sequential and parallel execution of discrete-event simulation
models. It can also be used as a parallel programming
language.
Papers in three categories:
- Language description
- Language implementations
- Applications
For information about obtaining copies of papers not available here,
see our Article Reprints page.
Language Descriptions
Designing Efficient Simulations Using Maisie
Rajive L. Bagrodia
Citation: Proceedings of the 1991 Winter Simulation Conference, Dec. 8-11, 1991, Phoenix, AZ, pp. 243-247
Annotation: Short language tutorial
PostScript file (decompress using gunzip)
Abstract:
Maisie is a C-based simulation language that encourages
iterative design of efficient simulations using step-wise
refinements. Maisie is among the few languages that cleanly
separates the simulation program from the underlying algorithm
(sequential or parallel) that is used to execute the program.
It is thus possible to design a sequential simulation and, if
needed, to subsequently port it to a parallel machine with few
modifications. This paper gives a brief introduction to modeling
and simulation using Maisie. It develops a complete Maisie model
of a queuing network and illustrates both sequential and parallel
implementations of the model.
Maisie: A Language for the Design of Efficient Discrete-Event Simulations
Rajive L. Bagrodia and Wen-Toh Liao
Citation: IEEE Transactions on Software Engineering, Vol. 20(4), April, 1994, pp. 225-238
PostScript file (decompress using gunzip)
Abstract:
Maisie is a C-based discrete-event simulation language that
was designed to cleanly separate a simulation model from the underlying
algorithm (sequential or parallel) used for the execution of the
model. With few modifications, a Maisie program may be executed by
using a sequential simulation algorithm, a parallel conservative
algorithm or a parallel optimistic algorithm. The language constructs
allow the run-time system to implement optimizations that reduce
recomputation and state saving overheads for optimistic simulations
and synchronization overheads for conservative implementations.
This paper presents the Maisie simulation language, describes a set of
optimizations, and illustrates the use of the language in the design
of efficient parallel simulations.
Maisie User Manual (Release 2.1 -- 06/10/93)
Rajive Bagrodia and Wen-Toh Liao
Citation: UCLA Computer Science Dept., Technical Report
PostScript file
Language Implementations:
A Unifying Framework for Distributed Simulation
Rajive Bagrodia, K. Mani Chandy, and Wen-Toh Liao
Citation: ACM Transactions on Modeling and Computer Simulation, Vol. 1(4), October, 1991, pp. 348-385.
Abstract:
A theory of distributed simulation applicable to both
discrete-event and continuous simulation is presented. It derives
many existing simulation algorithms from the theory and describes
an implementation of a new algorithm derived from the theory. A
high-level discrete-event simulation language has been implemented,
using the new algorithm, on parallel computers: performance
results of the implementation are also presented.
An Experimental Study on the Performance of the Space-Time Simulation Algorithm
Rajive Bagrodia, K. Mani Chandy, and Wen-Toh Liao
Citation: Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS'92), Jan. 1992, Vol. 24(3), pp. 159-168.
Abstract:
Most performance studies for parallel simulations only
exploit spatial parallelism in the execution of a simulation model.
This paper describes a performance study that used space parallelism,
time parallelism as well as a combination of the two decomposition
strategies to reduce the execution time for simulating models of simple
stochastic benchmarks. In the simulation of a feed forward network,
the time-parallel implementation used a simple strategy to correct
estimated future states of a process that effectively eliminated
rollbacks. The paper presents speedup curves for a number of
configurations and also analyzes the major cost components of the
parallel simulation algorithm.
Transparent Implementation of Conservative Algorithms in Parallel Simulation Languages
Vikas Jha and Rajive L. Bagrodia
Citation: Proceedings of the 1993 Winter Simulation Conference.
Compressed PostScript file
Abstract:
Parallel discrete event simulation offers significant
speedup over the traditional sequential event list algorithm. A
number of conservative and optimistic algorithms have been proposed
and studies for parallel simulation. We examine the problem of
transparent execution of a simulation model using conservative
algorithms, and present experimental results on the performance
of these transparent implementations. The conservative algorithms
implemented and compared include the null message algorithm, the
conditional-event algorithm, and a new algorithm which is a
combination of these. We describe how dynamic topology can be
supported by conservative algorithms. Language constructs to
express lookahead are discussed. Finally, performance
measurements on a variety of benchmarks are presented, along with
a study of the relationship between model characteristics like
lookahead, communication topology and the performance of
conservative algorithms.
Transparent Optimizations of Overheads in Optimistic Simulations
Rajive Bagrodia and Wen-Toh Liao
Citation: Proceedings of the 1992 Winter Simulation Conference, Dec. 1992, Arlington, VA.
Abstract:
A large fraction of the overhead in a typical optimistic
simulation is due to the state-saving and recomputation needed to
correct a potentially incorrect computation. Traditional mechanisms
that are used to trigger recomputations may incur significantly
greater overheads than are necessary to ensure a correct computation.
In this paper, we describe a performance study of an optimization
mechanism which uses application semantics to identify artificial
rollback in an optimistic simulation. Detection of artificial
rollbacks can reduce unnecessary recomputations and indirectly
reduce state-saving overheads. The detection mechanism has been
transparently implemented in a distributed simulation language
called Maisie. The paper demonstrates that detection of
artificial rollbacks can yield significant performance improvements
in the simulation of stochastic systems.
Applications
Parallel Simulation of a High-Speed Wormhole Routing Network
Rajive Bagrodia, Yu-an Chen, Mario Gerla, Bruce Kwan, Jay Martin,
Prasasth Palnati, and Simon Walton
Citation: Proceedings of the 10th Workshop on Parallel and Distributed
Simulations, 1996.
Abstract:
A flexible simulator has been developed to simulate a two-level metropolitan
area network which uses wormhole routing. To accurately model the
nature of wormhole routing, the simulator performs discrete-byte rather than
discrete-packet simulation. Despite the increased computational workload
that this implies, it has been possible to create a simulator with
acceptable performance by writing it in Maisie, a parallel discrete-event
simulation language. The simulator provides an accurate model of an actual
high-speed, source-routing, wormhole network (the Myrinet). This is the
first such simulator in existence.
The paper describes the simulator and reports on the performance of parallel
implementations of the simulator on a 24-node IBM SP multicomputer. The
parallel implementations were used to evaluate possible performance
improvements in the execution time of the model using both conservative and
optimistic simulation algorithms.
A Hierarchical Simulation Environment for Mobile Wireless Networks
Rajive Bagrodia, M. Gerla, Leonard Kleinrock, Joel Short, and T.-C. Tsai
Citation: Proceedings of the 1995 Winter Simulation Conference, December 1995.
Postscipt file (use gunzip to decompress)
Abstract:
A hierarchical simulator has been designed for multi-media communication
protocols in a wireless mobile environment. The hierarchical approach integrates
performance evaluation of protocols with their implementation. The approach
supports scalability studies of the protocols in an efficient manner using coarse grain
models that abstract implementation details of the protocol and its execution
environment by a few key parameters. Fine grain, low-level models that capture
implementation details are used fro detailed evaluation of small networks and for
automatic implementation on radio platforms. The design, evaluation, and
implementation cycle is closed by feeding the measurements from the implementation
back into the model to improve its accuracy. The paper describes the use of the
environment in the evaluation and implementation of a cluster-based multihop protocol
for multimedia traffic.
COMPOSE: An Object Oriented Environment for Parallel Discrete-Event Simulations
Jay Martin and Rajive Bagrodia
Citation: Proceedings of the 1995 Winter Simulation Conference, December 1995.
Postscipt file (use gunzip to decompress)
Abstract:
Existing environments for parallel discrete-event simulation provide support
for either conservative or optimistic algortithms, with very few supporting
both. This paper describes a parallel simulation environment that supports the
execution of a model using an existing adaptive simulation algotrithm where
sub-models may be synchronized using conservative or optimistic algorithms,
and an object may dynamically change its mode of synchronization. The
environment has been designed as a C++ class library and has been implemented
on an IBM SP2 multicomputer.
Mobile Wireless Network System Simulation
Joel Short, Rajive Bagrodia, Leonard Kleinrock
Citation: Proceedings of the ACM Mobile Communication Networking Conference,
Berkeley, CA, November 1995.
Postscipt file (use gunzip to decompress)
Abstract:
This paper describes an advanced simulation environment which is used to examine,
validate, and predict the performance of mobile wireless network systems. This
simulation environment overcomes many of the limitations found with analytical
models, experimentation, and other commercial network simulators available on the
market today. We identify a set of components which make up mobile wireless
systems and describe a set of flexible modules which can be used to model the various
components and their integration. These models are developed using the Maisie
simulation language. By modeling the various components and their integration ,
this simulation environment is able to accurately predict the performance bottlenecks
of a multimedia wireless network system being developed at UCLA, determine the
trade-off point between the various bottlenecks, and provide performance
measurements and validation of algorithms which are not possible through
experimentation and too complex for analysis.
Parallel Simulation of Data Parallel Programs
Sundeep Prakash and Rajive Bagrodia
Citation: Proceedings of the Eighth Workshop on Languages and Compilers
for Parallel Computing, Columbus, OH, August 1995.
Postscipt file (use gunzip to decompress)
Abstract:
Accurate simulations of parallel programs for large datasets can often be slow;
parallel execution has been shown to offer significant potential in reducing the
execution time of many discrete-event simulators. This paper describes the design
and implementation of a parallel simulator called DPSIM that simulates the execution
of data parallel programs on contemporary message-passing parallel architectures.
The simulator has been implemented on the IBM SPx using a conservative synchronization algorithm. This paper describes the design and implementation of
DPSIM; the performance of the simulator is presented for a variety of applications
including Gauss Jordan elimination, fast Fourier transforms, and matrix multiplication.
Parallel Gate-level Circuit Simulation on Shared Memory Architectures
Rajive Bagrodia, Yu-an Chen, Vikas Jha, and Nicki Sonpar
Citation: Proceedings of the Ninth Workshop on Parallel and Distributed
Simulations, Lake Placid, NY, June 1995. Publisher: IEEE Computer Society
Press, Los Alamitos,
CA, pp. 170-174.
Postscript file
Abstract:
This paper presents the results of an experimental study to evaluate the effectiveness
of parallel simulations in reducing the execution of gate-level models of VLSI circuits.
Specific contributions of this paper include (I) the design of a gate-level parallel
simulator that can be executed without any changes on both distributed memory and
shared memory parallel architectures, (ii) demonstrated speedups with both conservative
and optimistic simulation protocols (almost all previous studies on circuit simulation
have failed to extract speedups with conservative protocols); in particular we showed
that a speedup of about 3 was obtained on 8 processors of a Sparc1000 for conservative
algorithms and about 2 for optimistic algorithms for circuits in the ISCAS85
benchmark suite; and (iii) performance comparison between shared memory and
distrubuted memory implementations of the simulator.
Parallel Logic Level Simulation of VLSI Circuits
Rajive Bagrodia, Zheng Li, Vikas Jha, Yuan Chen, and Jason Cong
Citation: Proceedings of the 1994 Winter Simulation Conference, J. D. Tew, S. Manivannan, D. A. Sadowski, and A. F. Seila (Eds.), 1994, pp. 1354-1361.
Abstract:
Interest in the exploitation of parallelism in circuit
simulation has been increasing steadily. In this paper, we study
parallel logic level simulation of combinational VLSI Boolean
networks using both conservative and optimistic simulation algorithms.
In particular, we describe a logic level circuit simulator that uses
an acyclic multi-way network partitioning algorithm to decompose
Boolean networks and an algorithm-independent simulation language
that allows a discrete-event simulation model to be executed
using a variety of simulation algorithms. The simulator has been
implemented on an IBM SP1 supercomputer and was used to simulate
a set of combinational Boolean circuits from the ISCAS85 benchmark
suite. Our results show that it is feasible to obtain speedups
for even relatively small circuits using both conservative and
optimistic methods.
Acyclic Multi-Way Partitioning of Boolean Networks
Jason Cong, Zheng Li, and Rajive Bagrodia
Citation: Proceedings of 31st ACM/IEEE Design Automation Conference, 1994, pp. 670-675.
Abstract:
Acyclic partitioning on combinational boolean networks has
wide range of applications, from multiple FPGA chip partitioning to
parallel circuit simulation. In this paper, we present two
efficient algorithms for the acyclic multi-way partitioning. One
is a generalized FM-based algorithm. The other is based on the
theory of maximum fanout-free cone (MFFC) decomposition. They
acyclic FM-algorithm usually results in larger cut-size, as
expected, compared to the undirected FM-algorithm due to the
acyclic constraint. To our surprise, however, the MFFC-based
acyclic partitioning algorithm consistently produces smaller
(50% on average) cut-sized solutions than the conventional
FM-algorithm. This result suggests that considering signal
directions during the process can lead to very natural circuit
decomposition and clustering, which in turn results in better
partitioning solutions. We have also implemented parallel gate
level simulators in Maisie and applied our partitioning algorithms
to evaluate their impact on circuit simulation.
Parallel Simulation of the Sharks World Problem
Rajive L. Bagrodia and Wen-Toh Liao
Citation: Proceedings of the 1990 Winter Simulation Conference, Dec. 9-12, 1990, New Orleans, LA, pp. 191-198.
Abstract:
The Sharks World problem has been suggested as a suitable
application to evaluate the effectiveness of parallel simulation
algorithms. This paper develops a simulation model in Maisie, a
C-based simulation language. With minor modifications, a Maisie
program may be executed using either sequential or parallel simulation
algorithms. The paper presents the results of executing the Maisie
model on a multicomputer architecture using the space-time simulation
algorithm.
Last updated Friday, 18-Sep-1998 17:24:24 PDT