The intra-cellular calcium signaling pathways of a neuron depends on both biochemical reactions and diffusions. Some quasi-isolated compartments (e.g., spines) are so small and calcium concentrations are so low that one extra molecule diffusing in by chance can make a nontrivial difference in concentration (percentage-wise). These rare events can affect dynamics discretely in such a way that they cannot be evaluated by a deterministic and continuous simulation. Stochastic models of such a system provide a more detailed understanding of these systems than existing deterministic models because they capture their behavior at a molecular level. Our research focuses on the development of a high performance parallel discrete event simulation environment, Neuron Time Warp (NTW), which is intended for use in the parallel simulation of stochastic reaction-diffusion systems such as intra-calcium signaling. NTW is integrated with NEURON, a simulator which is widely used within the neuroscience community. We simulate two models, a calcium buffer and a calcium wave model. The calcium buffer model is employed in order to verify the correctness and performance of NTW by comparing it to a sequential deterministic simulation in NEURON. We also derived a discrete event calcium wave model from a deterministic model using the stochastic $\text{IP}_{3}\text{R}$IP3R structure.

This paper describes a parallel discrete event simulator, Neuron Time Warp-Multi Thread (NTW-MT), developed for the simulation of reaction diffusion models of neurons. The simulator was developed as part of the NEURON project and is intended to be included in NEURON. It relies upon a stochastic discrete event model developed for chemical reactions. NTW-MT is optimistic and thread-based, in which communication latency among threads within the same process is minimized by pointers. We investigate the performance of NTW-MT on a reaction-diffusion model for the transmission of calcium waves in a neuron. Calcium plays a fundamental role in the second messenger system of a neuron. However, the mechanism by which calcium waves are transmitted is not entirely understood. Stochastic models are more realistic than deterministic models for small populations of ions such as those found in apical dendrites. To be more precise, we simulate a stochastic discrete event model for calcium wave propagation on an unbranched apical dendrite of a hippocampal pyramidal neuron. We examine the performance of NTW-MT on this calcium wave model and compare it to the performance of (1) a process based optimistic simulator and (2) a threaded simulator which uses a single priority (SQ) queue for each thread. Our multi-threaded simulator is shown to achieve superior performance to these simulators.

As computing systems grow to exascale levels of performance, the smallest elements of a single processor can greatly affect the entire computer system (e.g. its power consumption). As future generations of processors are developed, simulation at the gate level is necessary to ensure that the necessary target performance benchmarks are met prior to fabrication. The most common simulation tools available today utilize either a single node or small clusters and as such create a bottleneck in the development process. This paper focuses on the massively parallel simulation of logic gate circuit models using supercomputer systems. The focus of this performance study leverages the OpenSPARC T2 processor design using Rensselaer's Optimistic Simulation System (ROSS). We conduct simulations of the crossbar component on both a 24-core SMP machine and an IBM Blue Gene/L. Using a single SMP core as the baseline, our performance experiments on 1024 cores of the Blue Gene/L demonstrate more than 131-times faster execution. Our results capitalize on the balanced compute and network power of the Blue Gene/L system.

A major part of the design process for Integrated Circuits (IC) is the process of circuit verification, in which the correctness of a circuit's design is evaluated. Discrete event simulation is a central tool in this effort. As proscribed by Moore's law, the number of transistors which can be placed on an IC doubles every 18 months. As a result, simulation has become the major bottleneck in the circuit design process. To alleviate this difficulty, it is possible to make use of parallel (or distributed) circuit simulation. In this paper, we make use of a parallel gate-level simulator which we developed and which is based upon Time Warp. Gate-level simulations exhibit two characteristics which can easily result in either instability or severely degraded simulation performance. Because of the low computational granularity of a gate-level simulation and because the computational load varies throughout the course of the simulation, the performance of Time Warp can be either severely degraded or be unstable. Restraining the optimism of Time Warp via a bounded window and utilizing dynamic load balancing are approaches to deal with these difficulties. In this paper, we make use of learning techniques from artificial intelligence (multiagent Q-learning, simulated annealing) to develop a combined bounded window and dynamic load balancing algorithm for parallel digital logic simulation. We evaluated the performance of these algorithms on open source Sparc and Leon designs and on two Viterbi decoder designs. We observed up to 60 percent improvement in simulation time of one of the decoders using this approach.

Parallel discrete event simulation can be applied as a fast and cost effective approach for the gate level simulation of current VLSI circuits. In this paper we combine a dynamic load balancing algorithm and a bounded window algorithm for optimistic gate level simulation. The bounded time window prevents the simulation from being too optimistic and from excessive rollbacks. We utilize a machine learning algorithm (Q-learning) to effect this combination. We introduce two dynamic load-balancing algorithms for balancing the communication and computational load and use two learning agents to combine these algorithms. One learning agent combines the two learning algorithms and learns their corresponding parameters, while the second optimizes the value of the time window. Experimental results show up to a 46% improvement in the simulation time using this combined algorithm for several open source circuits. To the best of our knowledge, this is the first time that Q-learning has been used to optimize an optimistic gate level simulation.

In this paper, we present a dynamic load-balancing algorithm for parallel digital logic simulation making use of reinforcement learning. We first introduce two dynamic load-balancing algorithms oriented towards balancing the computational and communication load respectively and then utilize reinforcement learning to create an algorithm which is a combination of the first two algorithms. In addition, the algorithm determines the value of two important parameters-the number of processors which participate in the algorithm and the load which is exchanged during its execution. We investigate the algorithms on gate level simulations of several open source VLSI circuits.

As proscribed by Moore's law, the size of integrated circuits has grown geometrically, resulting in simulation becoming the major bottleneck in the circuit design process. Parallel simulation provides us with a way to cope with this growth. In this paper, we describe an optimistic (time warp) parallel discrete event simulator which can simulate all synthesizeable Verilog circuits. We investigate its scalability and describe a machine learning based dynamic load balancing algorithm for use with the simulator. We initially developed two dynamic load balancing algorithms to balance the load and the communication, respectively, during the course of a simulation. Making use of reinforcement learning (RL), we then created an algorithm which is an amalgam of these two algorithms. To the best of our knowledge, this is the first time that RL has been used for the dynamic load-balancing of time warp. We investigated the scalability and the effectiveness of the dynamic load balancing algorithms on gate level simulations of several realistic very large scale integration (VLSI) circuits. Our experimental results showed that our simulator is indeed scalable. They also reveled a 88.6% improvement in the simulation time through the use of our RL algorithm.

As a consequence of Moore's law, the size of integrated circuits has grown extensively, resulting in simulation becoming the major bottleneck in the circuit design process. Consequently, parallel simulation has emerged as an approach which can be both fast and cost effective. In this paper, we examine the performance of a parallel Verilog simulator on four large, real designs. As previous work has made use of either relatively small benchmarks or synthetic circuits, the use of these circuits is far more realistic. We develop a parser for Verilog files enabling us to simulate in parallel all synthesizable Verilog circuits. We utilize four circuits as our test benches; the LEON Processor with 200 k gates, the OpenSparc T2 processor with 400 k gates and two Viterbi decoder circuits with 100 k and 800 k gates respectively. The simulator makes use of XTW and to our knowledge is the first Verilog simulator which can parse all synthesizable Verilog files. We observed 4,000,000 events per second on 32 processors for the Viterbi decoder with 800 k gates. The simulators' performance was shown to be scalable.

We describe, in this paper, a multiway partitioning algorithm for parallel gate level Verilog simulation. The algorithm is an extension of a multi-level algorithm which only creates two partitions. Like its predecessor, it takes advantage of the design hierarchy present in a Verilog circuit design. The information it makes use of is contained in the modules and their instances. The algorithm makes use of a hypergraph model of the Verilog design in which a vertex in the hypergraph represents a module instance. Our new algorithm relies upon a metric whose function is to balance the load and the communications between the modules of the Verilog design. pre-simulation is used to to evaluate the partitioning metric. When compared to hMetis, a well known multilevel partitioning algorithm, our algorithm produces a superior speedup and a reduced cut-size.

In this paper, a new event scheduling mechanism XEQ and a new rollback procedure rb-messages are proposed for use in optimistic logic simulation. We incorporate both of these techniques in a simulator XTW. XTW groups LPs into clusters, and makes use of a multi-level queue, XEQ, to schedule events in the cluster. XEQ has an O(1) event scheduling time complexity. Our new rollback mechanism replaces the use of anti-messages by an rb-message, and eliminates the need for an output queue at each LP. Experimental comparisons to Time Warp reveal a superior performance on the part of XTW, while experimental results over large circuits (5-million-gate to 25-million-gate) shows XTW scales well with both the size of circuits and the number of processors.

The complexity of today's VLSI chip designs makes verification a necessary step before fabrication. As a result, gate-level logic simulation has became an integral component of the VLSI circuit design process which verifies the design and analyzes its behavior. Since the designs constantly grow in size and complexity, there is a need for ever more efficient simulations to keep the gate-level logic verification time acceptably small. The focus of this paper is an efficient simulation of large chip designs. We present the design and implementation of a new parallel simulator, called DSIM, and demonstrate DSIM's efficiency and speed by simulating a million gate circuit using different numbers of processors.

In this paper, we present a family of three algorithms which serve to perform checkpoints and to roll back time warp. These algorithms are primarily intended for use in simulations in which there are a large number of LPs and in which events have a small computational granularity. Important representatives of this class are VLSI and computer network simulations. In each of our algorithms, LPs are gathered into clusters via algorithms which are application dependent. In order to examine the performance of our algorithms and to compare them to Time Warp, we made use of two of the largest digital logic circuits available from the ISCAS89 benchmark series of combinational circuits. The execution time, number of states saved, and maximal memory consumption were compared to the same quantities for time warp. Our results indicated that each of the algorithms occupies a different point in the spectrum of possible trade-offs between memory usage and execution time, ranging from substantial memory savings (at a comparable cost in speed) to memory savings and a comparable speed to time warp. Hence, an important benefit of our algorithms is the ability to trade off memory requirements with execution time.

In this paper, a distributed cycle/knot detection algorithm for general graphs is presented. The algorithm distinguishes between cycles and knots and is the first algorithm to our knowledge which does so. It is especially relevant to an application such as parallel simulation in which 1) cycles and knots can arise frequently 2) the size of the graph is very large, and 3) it is necessary to know if a given node is in a cycle or a knot. It requires less communication than previous algorithms-2m vs. (at least) (4m) for the Chandy and Misra algorithm, where m is the number of links in the graph. It requires O (nlog (n)) bits of memory, where n is the number of nodes. The algorithm differs from the classical diffusing computation methods through its use of incomplete search messages to speed up the computation. We introduce a marking scheme in order to identify strongly connected subcomponents of the graph which cannot reach the initiator of the algorithm. This allows us to distinguish between the case in which the initiator is in a cycle (only) or is in a knot.

A load balancing algorithm for a discrete event simulation executed under Time Warp is presented. The algorithm rests upon recent developments in active process migration, which permit the use of dynamic strategies. Dynamic load balancing allows for readjustments when resource requirements vary during simulation. It is also useful when initial resource predictions are unknown or incorrect. A simulated multiprocessor environment (PARALLEX) was developed in order to evaluate the algorithm. The results indicate that substantial performance gains may be realized with the algorithm.>

A heuristic algorithm for computing the end-to-end delay of multiple-packet messages is developed. The network is assumed to use virtual circuits subject to window flow control. The model is presented. It results in a closed queuing network in which batch transitions may occur due to arrivals of multiple-packet messages. The algorithm is presented and developed in order to determine the message delay. Simulations are used to validate the resulting algorithm.>

A dynamic routing algorithm that has as its goal the control of congestion in a packet switching network is presented. The algorithm is based in part on the ARPANET SPF algorithm. However, instead of employing a delay metric, the authors make use of a combination of link and buffer utilizations. A detailed simulation model of the ARPANET was constructed to compare the performance of the congestion-based algorithm to the traditional delay-based (SPF) routing algorithm. The results indicate a substantial improvement in the delay and throughput of the network with the congestion-based routing algorithm.>