Research on symmetry detection focuses on identifying and detecting new types of symmetry. We present an algorithm that is capable of detecting any type of permutation-based symmetry, including many types for which there are no existing algorithms. General symmetry detection is library-based, but symmetries that can be parameterized, (i.e. total, partial, rotational, and dihedral symmetry), can be detected without using libraries. In many cases it is faster than existing techniques. Furthermore, it is simpler than most existing techniques, and can easily be incorporated into existing software.

Detecting the symmetries of a Boolean function can lead to simpler implementations both at the hardware and software level. Large clusters of mutually symmetric variables are more advantageous than small clusters. One way to extend the symmetry of a function is to detect abstract two-cofactor relations in addition to ordinary symmetric relations. Unfortunately, ordinary symmetries are simply transitive but more complex types of relations are not. This paper shows how to convert the more complex relations into ordinary symmetries, allowing them to be used to form large clusters of symmetric variables, larger than would be possible using ordinary symmetries.

State machine based simulation of Boolean functions is substantially faster if the function being simulated is symmetric. Unfortunately function symmetries are comparatively rare. Conjugate symmetries can be used to reduce the state space for functions that have no detectable symmetries, allowing the benefits of symmetry to be applied to a much wider class of functions. Substantial improvements in simulation speed, from 30-40% have been realized using these techniques

A binary component is a separately compiled program that can be used as a part of a larger program. Binary components generally conform to an accepted technology such as JavaBeans or ActiveX, and generally support a rich program interface containing properties, methods and events. Binary components are generally used in a graphical user interface (GUI) environment. There are a number of benefits to be realized by converting command-line software into binary components. The most important of these is that GUI environments are more popular and more familiar to most people than command-line environments. Using binary components can greatly simplify a GUI implementation, to the point where it is only slightly more complicated than a typical command-line implementation. However there are benefits that go beyond mere convenience. Binary components have much richer interfaces than command-line programs. Binary components are service-oriented rather than task-oriented. A task-oriented program has a main routine that is devoted to accomplishing a single task. A service-oriented component has no main routine or main function, but instead provides a variety of services to its clients. Binary components can be easily integrated with one another, which permits a design where each major feature of an application is implemented in a different component. Such a design encourages software reuse at the component level and facilitates low-impact feature upgrades. We first delineate a design-pattern-based methodology for converting command-line programs into components. We then illustrate these principles using two projects, a simulation system for digital circuits, and a data generation system for software and hardware testing. Copyright © 2005 John Wiley & Sons, Ltd.

State machine-based simulation is an efficient event-driven simulation technique which has been used to simulate gate-level circuits. Although this approach has been proven to be successful, the techniques that have been used up to now have been limited in several ways. This paper introduces generic state machines that can be used in a wide variety of contexts. These machines are then used to create efficient new simulation techniques that can be applied not just to gates, but to a wide variety of specifications, including Boolean expressions, binary decision diagrams and truth tables. These techniques can combine clusters of gates into a single simulation unit that can be simulated as efficiently as a single gate. The resultant state machines can be simplified by identifying and combining symmetric inputs. Two different types of symmetries can be detected, ordinary symmetry, such as that exhibited by an AND gate, and inverted symmetry, where an input is symmetric with the complement of another input. Both sorts of symmetry can be used for state machine simplification. Experimental results show a substantial reduction in simulation time for complex circuits.

Software components have existed in one form or another for a number of years. Work in this area can be classified into two broad categories. On the one hand, a number of researchers have approached the concept of software components from a first principles perspective, advancing ideas regarding what constitutes the ideal component paradigm from perspectives of efficiency, verifiability and reusability. On the other hand, recent commercial advances in a number of popular technologies have elevated the software component concept into widespread use within the software practitioner community. Such technologies include a number of technologies made popular by Microsoft (such as Active-X, COM, DCOM and Visual Basic), as well as CORBA and Java Beans.Neither of these perspectives on software components has become a standard cornerstone of software development pedagogy. Yet both perspectives may have an important role in preparing software developers to build high-quality software in the context of modern software development technologies. In particular, teaching students how to design and construct software components from first principles provides students with important guidance as to the "right way" to structure correct and efficient software systems (i.e., with emphasis on "what" component-based systems should contain). On the other hand, teaching students about current commercial component technologies exposes students to the important dimension of best commercial practice (i.e., with emphasis on "how" component-based systems could be built).The participants of this panel are all actively involved in the development of courses and curricula that provide various perspectives on component-based systems. They represent both the first principles and commercial perspectives discussed above. Position statements for each of the panelists appear below.

This paper shows how to simulate a circuit as an interlocked collection of state machines. Separate state-machines are used to represent nets and gates. The technique permits intermixing of logic models, direct simulation of higher-level functions, and optimization techniques for fanout free circuits. These techniques are an extension of techniques that have been used to achieve high-performance event-driven simulations. New more efficient state-machine implementations are presented, and experimental data is presented that show the efficiency of the new techniques.

The past several years have seen much research in event driven logic simulation. Various logic and delay models have been explored. Most simulation research has focused on improving simulation performance. New approaches to both compiled and event driven simulation have been explored. The internal operations of event-driven simulators can be divided into two categories, scheduling, and gate simulation. Much effort has been focused on reducing the cost of scheduling. There has also been effort to reduce the cost of gate simulation. It has also been shown that explicit computation of gate outputs is unnecessary, as long as event propagation is computed correctly. Even though research has reduced the complexity of both scheduling and gate simulation, it is still necessary to test for event propagation and cancellation, and it is necessary to perform some computations during gate simulation. This paper shows that none of these computations are necessary. Most computations are devoted to testing internal states and computing new internal states. In our technique, subroutine addresses are used to maintain states. This permits the elimination of all state-testing and state-computation code. Our technique is significantly faster than conventional event-driven simulation. Unlike earlier methods, our approach can easily be extended to any logic model or any delay model.

For some types of simulation, it is difficult or impossible to improve performance by packing several vectors to be packed into a single word. One example of such an algorithm is inversion algorithm, which does not represent net values in the conventional way. This paper presents a novel technique, called software bit-slicing for performing simultaneous simulation of several input vectors on a conventional uniprocessor. As with conventional vector-packing techniques, this technique is able to assign a different input vector to each bit of a word, permitting the simultaneous simulation of n vectors, where n is the number of bits in a word. The inversion algorithm is used to give an example of this technique. For this example, a 6x speedup can be realized by using software bit-slicing. The same technique should be widely applicable to many different types of simulation.

The inversion algorithm is an event-driven algorithm, whose performance rivals or exceeds that of levelized compiled code simulation, even at activity rates of 50% or more. The inversion algorithm has several unique features, the most remarkable of which is the size of the run-time code. The basic algorithm can be implemented using no more than a page of run-time code, although in practice, it is more efficient to provide several different variations of the basic algorithm. The run-time code is independent of the circuit under test, so the algorithm can be implemented either as a compiled code or an interpreted simulator with little variation in performance. Because of the small size of the run-time code, the run-time portions of the inversion algorithm can be implemented in assembly language for peak efficiency, and still can be retargeted for new platforms with little effort.

The Inversion Algorithm is an event driven algorithm whose performance meets or exceeds that of Levelized Compiled Code simulation, even when the activity rate is unrealistically high. Existing implementations of the Inversion Algorithm are based on the Zero Delay model. This paper extends the algorithm to more realistic timing models. The main problems discussed in this paper are avoiding scheduling conflicts, and minimizing the amount of storage space. These problems are made considerably more difficult by the deletion of NOT gates and the collapsing of various connections. These optimizations transform the simulation into a multi-delay simulation under the transport delay model. A complete solution to the scheduling problem is presented under these conditions.

The multidelay parallel (MDP) technique is a multidelay logic simulation algorithm that uses no timing wheel, or any other event-sorting mechanism. Instead, wide bit-fields containing net-values for several different times are used to resolve out-of-order events. Bit-parallel operations are performed to simulate gates at the required times. The MDP technique was originally designed to be implemented in hardware, but the current software version of the algorithm has proven to be competitive with conventional event-driven multidelay simulation. Two versions of the MDP technique are presented in this paper, fixed alignment and variable alignment. The fixed alignment algorithm provides bit-fields that are wide enough to capture any event that could occur during the simulation of an input vector, while the variable alignment algorithm uses a minimum-width bit field which is just wide enough to capture those events that could occur at an individual step in the simulation. A prototype hardware design is discussed briefly.

The gateway technique is a method for switching segments of code into and out of the instruction stream. When added to the straight-line code generated by a compiled simulator, gateways can be used to enhance the performance of the generated code by switching only those segments of code that actually need to be executed into the instruction stream. The convergence algorithm is an oblivious compiled code algorithm that can be used with many different types of circuits, including cyclic asynchronous circuits. In its oblivious form, the convergence algorithm provides only modest gains in performance over interpreted event-driven simulation, but with the addition of gateways, the performance of the algorithm increases significantly. Experimental data shows that with gateways, the convergence algorithm runs in about 1/5th the time required for an interpreted event-driven simulation. Additional work has been done to reduce the amount of code generated by the convergence algorithm, and to enhance the locality of the code to improve its performance on machines with caches. When used with a multi-delay algorithm, gateways allow simulations to be performed in 1/3 the time required by interpreted simulations. Gateways also allow zero-delay simulations to be more responsive to the activity rate of the circuit, and allow event driven simulations to outperform levelized compiled code when the activity rate of the circuit falls below 13%.>

The multi-delay parallel (MDP) technique is a multi-delay logic simulation algorithm that uses no event-sorting mechanism. Wide bit-fields and bit-parallel operations are used to resolve out-of-order events. Although the MDP technique was designed to be implemented in hardware, the software version has proven to be competitive with ordinary multi-delay simulation. Two versions of the MDP technique are presented: fixed alignment and variable alignment. The fixed alignment algorithm uses bit-fields that are wide enough to capture any event that could occur during the simulation, while the variable alignment algorithm uses a minimum-width bit field.

The shadow algorithm, which is an event-driven unit-delay simulation technique that has been designed to take advantage of the instruction caches present in many of the latest workstations, is discussed. The algorithm is based on the threaded-code technique, but uses a dynamically created linked list of environments called shadows. Compiled shadow algorithm simulations run in about 1/5th the time required for a conventional interpreted event-driven simulation. The interpreted shadow algorithm runs in about 1/4th the time of a conventional interpretive simulation.>

Abstract DGL is a context‐free grammar‐based language for generating test data. Although many of the features of DGL are implemented in a straighforward way, the implementation of several of the most important features is neither trivial nor obvious. Before one can understand the implementation of these features, however, it is necessary to understand the overall structure of the compiler and its output, which was designed to be flexible enough to incorporate new features easily. Variables and chains are two of the most important features of DGL, and also two of the trickiest features to implement. The run‐time dictionaires, which are built into the C code generated by the compiler, are implemented as pure code rather than as table‐look‐up routines. The compiler itself is reasonably straightforward, except for the expansion of character sets and compile‐time macros. These two features can cause the ‘multi‐dimensional’ expansion of a string, the implementation of which must be carefully designed.

The potential change (PC)-set method and the parallel technique for generating compiled unit-delay simulators for acrylic circuits are discussed. The PC-set method analyzes the network, determines the set of potential change times for each net, and generates gate simulations for each potential change. The parallel technique, which is based on the concept of bit-parallel simulation is faster and generates less code than the PC-set method, but it is not amenable to data-parallel simulation of multiple input vectors. Both techniques are based on the well-known levelization algorithm used to generate zero-delay levelized compiled code simulation. Two optimizations of the basic parallel technique are presented, called bit-field trimming and shift elimination. Performance results using the ISCAS 85 benchmarks show a factor-of-four improvement for the PC-set method and a factor-of-ten improvement for the parallel technique. The optimization schemes show an average performance improvement of 47% over the unoptimized simulations.>

Several algorithms for scheduling high-level functional blocks that assume the blocks may not be physically divided and that pseudocycles may be present due to the grouping of elements within blocks are presented. These algorithms rely on dependency information derived from the block-definitions to create a logical (rather than physical) partitioning of the circuit. The partitioned network is scheduled by an algorithm that is based on levelized scheduling with various heuristics added. The choice of the algorithm is based on the randomness of the partitioning technique. For highly random partitioning, PCSF performs best, while for partitioning that conforms closely to the signal flow of the circuit, FIQ performs best. For circuits in between, MEO is shown to perform best. These techniques represent an improvement over the technique of simulating blocks in random order, since no block will be scheduled unless there is a potential for performing useful work by simulating the block. The problem of finding the minimal schedule is shown to be NP-complete, hence, a heuristic approach to the problem is justified. A technique for computing the dependencies of a block is also presented.>

The PC-set method and the parallel technique are two methods for performing compiled unit-delay simulation. The PC-set method analyzes the network, determines the set of potential change times for each net, and generates gate simulations for each potential change. The parallel technique, which is based on the concept of parallel fault simulation, is faster and generates less code than the PC-method, but is less flexible. Benchmark comparisons with interpreted event-driven simulation show a factor of four improvement for the PC-set method and a factor of ten improvement for the parallel technique.

LECSIM is a highly efficient logic simulator which integrates the advantages of event driven interpretive simulation and levelized compiled simulation. Two techniques contribute to the high efficiency. First it employs the zero-delay simulation model with levelized event scheduling to eliminate most unnecessary evaluations. Second, it compiles the central event scheduler into simple local scheduling segments which reduces the overhead of event scheduling. Experimental results show that LECSIM runs about 8-77 time faster than traditional unit-delay event-driven interpretive simulator. LECSIM also provides the option of scheduling with respect to individual gates or with respect to fan-out free blocks. When the circuit is partitioned into fan-out free blocks, the speed increases by a factor of 2-3. With partitioning, the speed of LECSIM is only about 1.5-3.4 times slower than a levelized compiled simulation for the combinational circuits we have tested.

The parallel technique is a purely compiled method for unit-delay simulation that is based on levelized compiled simulation and bit parallel simulation. The parallel technique provides rapid simulations with a reasonable amount of code, but there are opportunities for optimization. The author presents two schemes: bit-field trimming and shift-elimination. Performance results are presented that demonstrate an average performance improvement of 47%.>

This paper presents a method for scheduling high-level blocks for functional simulation under the assumptions that circuits may be cyclic (due to element grouping), and that blocks cannot be broken down into simpler elements. The solution presented here may simulate one block many times per clock period. Obtaining a minimal schedule for a cyclic circuit is shown to be NP-complete, and two approximation algorithms are presented, along with empirical data to evaluate their effectiveness.

The logic-to-logic comparator (LLC) is described as a tool that verifies VLSI layouts by comparing the logic diagrams for a circuit with structures extracted from the circuit's layout. LLC can operate at either the gate or the transistor level, although the gate level is preferred. It is similar to other graph-isomorphism-based tools, but incorporates some important improvements. The most important of these is a path-comparison algorithm that uses dynamically calculated global information. In addition, LLC contains a gate-matching algorithm that can use certain types of symmetry to distinguish between gates that appear to be identical to less sophisticated algorithms. LLC has been used to verify several commercially available VLSI chips.>