Distributed logic simulation: performance studies of event-driven and time- first evaluation algorithms

Abstract

With the increasing complexity of VLSI circuits, simulation of digital circuits is becoming a more complex and time consuming task. Of the different types of simulators available for analysing the design at various stages of the VLSI design process, logic level simulators are extensively used. The complexity of VLSI circuit design further demands faster logic simulation techniques to carry out simulation in a reasonable time frame. One of the ways to speed up existing logic simulation algorithms is by exploiting the inherent parallelism in their sequential versions and implementing the algorithms on parallel machines. Current trends in parallel logic simulation focus on mapping simulation algorithms onto processors of general purpose parallel machines. However, existing methods of mapping sequential logic simulation algorithms onto parallel machines do not satisfactorily address the suitability of a particular sequential algorithm for parallel implementation. In this context, this dissertation develops and analyses two distributed logic simulation algorithms-the centralized time event driven algorithm and the Time First evaluation algorithm (T Algorithm)-mapped onto a network of workstations. The characteristics of the concurrency inherent in each algorithm are analysed, and their performance on ISCAS benchmark circuits is investigated. A distributed event driven algorithm based on the central dispatcher model is developed. This method does not partition the circuit but exploits object concurrency by processing independent events concurrently. Measurements on ISCAS85 and ISCAS89 benchmark circuits show that the event driven algorithm exhibits: • 5 to 48 concurrent element evaluations • 3 to 32 concurrent node updates Its performance is quantified using: 1. Execution time of tasks on individual workstations 2. Amount of data transferred among workstations 3. Computational load profiles A fanout based event list assignment scheme is proposed to achieve even computational load. However, performance improvement with additional workstations is limited due to the restricted concurrency in the event driven algorithm. A distributed Time First evaluation algorithm is also developed. This algorithm partitions gates associated with each level of the circuit among workstations. A levelization algorithm is used as preprocessing. Measured concurrency ranges from: • 10 to 111 element evaluations -representing a 2–2.5× increase over the event driven algorithm. Sequential versions of the T Algorithm run 2–5× faster than the event driven version. A load balancing heuristic is proposed by assigning weights to gates. To drastically reduce communication overhead, a Fanout Free Region (FFR) based partitioning method is adopted. A scheme is also proposed for extending the T Algorithm to simulate synchronous sequential circuits. A detailed comparison between the two algorithms demonstrates the clear suitability of the Time First evaluation algorithm for parallel and distributed implementation. Its communication overhead is significantly lower, and its inherent concurrency is much higher. Thus, the T Algorithm appears to be a viable alternative to the event driven algorithm for parallel logic simulation.