Computer Science Technical Reports

Permanent URI for this collectionhttps://hdl.handle.net/2104/4824

Browse

Now showing 1 - 20 of 76

Using GF(2) matrices in Simulation and Logic Synthesis
(2009-01-23T16:31:18Z) Maurer, Peter M.
GF(2) matrices are matrices of ones and zeros under modulo 2 arithmetic. Like the GF(2) polynomials used in error detection and correction, they have many potential uses in Electronic Design Automation (EDA). Non-singular matrices can be used to define new classes of symmetry called conjugate symmetries. Conjugate symmetries have been used to speed up certain kinds of functional-level simulations, and have other potential uses. GF(2) matrices can also be used to transform Boolean vector spaces and simplify Boolean functions. Although matrix transformations can be complex, simpler single-bit matrices can be used instead of general matrices. This simplifies the approach without loss of generality. Singular matrices can be used to reduce the complexity of certain functions, beyond what is normally possible with conventional simplification techniques. GF(2) matrices can also be used to define exotic symmetries called strange symmetries and collapsed symmetries. These exotic symmetries may prove useful in future EDA applications.
Using GF2 Matrices to Simplify Boolean Logic
(2009-01-23T19:40:41Z) Maurer, Peter M.
Conventional logic simplification can be couched in terms of singular GF(2) matrices. The advantage to doing this is that different matrices can be used to combine terms that are separated by a Hamming distance greater than one. Although this sort of thing can be done without matrices, it is not clear what one would do after finding such terms. We show that by applying a matrix transformation to the inputs of a function, we can combine terms that are at arbitrary distances. We also show that we can further simplify functions by transforming the input vector space with a non-singular transformation.
A Quick Algorithm for Identifying Conjugate Groups in GF(2)
(2009-02-18T17:19:42Z) Maurer, Peter M.
This report gives the details an algorithm for determining whether two matrix groups are conjugate to one another. Each group is designated by a pair of matrices that generate the group. The algorithm is able to determine whether the two generated groups are conjugate to one another without actually generating the groups.
Categories for Component Level Design
(2009-02-18T17:21:56Z) Maurer, Peter M.
Several research problems are discussed, including communication mechanisms and the interface between components and the glue logic used to tie them together. A technique for engineering new component-level applications is presented. This technique divides an application into a set of tightly coupled parts each one of which can be placed in a specific category. Each of these categories has its own design methodology, most of which rely heavily on object oriented design. Once the features of an application have been divided into categories, they can be implemented as off- the-shelf components, new components, or as glue logic. The categorization scheme gives guidelines for the placement of each feature. The categorization scheme relies on the ability to pass pointers complex objects between components. The dangers of such practices are discussed, and suggestions are made for future research that might help mitigate these dangers.
The Complexity of Detecting Symmetric Functions
(2009-02-18T17:23:29Z) Maurer, Peter M.
The characterization of the symmetries of boolean functions is important both in automatic layout synthesis, and in automatic verification of manually created layouts. It is possible to characterize the symmetries of an n-input boolean function as an arbitrary subgroup, G, of S(n), the symmetric group of order n. Given an expression e, which represents an n-input boolean function F, and a subgroup G of S(n) the problem of whether F possesses symmetry G is an NP-complete problem. The concept of an orbit can be used to characterize the various types of symmetry for a specified number of inputs. This classification can then be used, along with a few partitioning rules to completely determine the symmetries of a Boolean function. This technique requires that the truth-table of a function be completely enumerated, and thus has a running time proportional to 2^n where n is the number of inputs of the function. Some of the mathematical concepts presented to support the NP-completeness result have intriguing possibilities for circuit minimization.
The GF2Matrices Classes: A Programming Package for Mathematical Research
(2009-03-31T14:31:06Z) Maurer, Peter M.
Over the past few years I have been engaged in an intense study of GF(2) matrices, especially of dimensions 2, 3, 4, and 5. The software I used for this study was mostly a bunch of ad-hoc subroutines scattered over numerous projects. This package consolidates all of this software into a system of classes. This software can be used to reproduce any of my results.
: GF2Matrices
(2009-03-31T14:52:17Z) Maurer, Peter M.
This is the software described in the technical report “The GF2Matrices Classes: A Programming Package for Mathematical Research.” Over the past few years I have been engaged in an intense study of GF(2) matrices, especially of dimensions 2, 3, 4, and 5. The software I used for this study was mostly a bunch of ad-hoc subroutines scattered over numerous projects. This package consolidates all of this software into a system of classes. This software can be used to reproduce any of my results. This package is distributed without any warranty of any kind.
The GF(2) General Linear Group for Dimensions 2, 3, 4, and 5
(2009-04-15T18:43:53Z) Maurer, Peter M.
This report contains some data about the General Linear Groups of GF(2) for dimensions 2, 3, 4, and 5. These groups are groups of matrices over GF(2), the integers modulo 2. The General Linear Group of order is the set of all non-singular matrices over some field, in this case, GF(2). We give the conjugacy classes of all matrices and all isomorphs of the symmetric group. The analysis for dimension 5 is incomplete. The observations we make here will be supported using short programs that use the GF2Matrices package, which is available as a Baylor Computer Science Technical report. (See http://beardocs.baylor.edu).
Metamorphic programming
(2009-04-15T18:45:38Z) Maurer, Peter M.
Metamorphic programming is an effective tool for creating efficient and elegant solutions to many programming problems, at least once you get over the shock of seeing code that violates many of the accepted rules of good programming. We have used metamorphosis for many years to solve problems in the logic-level simulation of VLSI circuits. These solutions have provided some spectacular gains in performance, inspiring us to look for metamorphic solutions to other problems. We have found metamorphic solutions to many problems including string searching, sorting, and depth first search, most of which provide performance gains over conventional coding. A few of these solutions are presented here. These programs violate the rules of good programming, but with a few minor compiler enhancements, our programming techniques become clean and well structured.
A Search Strategy Using a Hamming-Distance Oracle
(2009-08-04T16:47:04Z) Maurer, Peter M.
The objective of the algorithm described in this report is to optimally guess a hidden binary string based on queries to an oracle where the length of the string is known beforehand. A C++ version of the algorithm is given along with a theoretical discussion of why the algorithm works. A discussion of the worst and average-case performance is given along with some discussion of optimality.
AN APPLICATION OF GROUP THEORY TO THE ANALYSIS OF SYMMETRIC GATES
(2009-10-26T15:35:05Z) Maurer, Peter M.
A method for determining the symmetries of the inputs of a logic gate either from its truth table or from facts obtained by inspection of its circuit is presented. The symmetry rule of a gate with n inputs is defined in terms of a subgroup of the symmetric group of degree n. This technique leads to an expanded and more complete definition of partial symmetry than has previously appeared. This definition of symmetry is used to show that the set of Boolean expressions that represent non-totally-symmetric functions is NP-complete. The group-theoretic concept of conjugate sets is used to identify symmetry rules that are fundamentally the same but applied to different sets of inputs. A complete analysis of all forms of symmetry for 2-input, 3-input and 4-input gates is provided. An example is given to show how this theory was applied to a problem in VLSI design verification.
Deduction by Induction
(2009-10-26T15:36:19Z) Maurer, Peter M.
In this report, I offer a technique for computing power sums that is: intuitive, well-motivated, generalizable to all k, and suitable for presentation to pre-calculus students.
Designing a Capstone Course to Simulate the Industrial Environment
(2009-10-26T15:40:33Z) Speegle, Gregory David.
The creation of a capstone course for an un- dergraduate computer science curriculum mirrors traditional software design. Initially, a high-level goal is created. This is refined into lower-level specifications by conducting interviews with the users. The implementation is based on these specifications. In our case, the capstone course is to simulate (as much as possible) the student experiences after graduation. Lower level specifications are created by approximately 20 hours of interviews with developers, testers and project managers in consulting, development and information technology departments. The results of these interviews are synthesized into a cap
The Functional Hardware Design Language
(2009-10-28T15:45:08Z) Maurer, Peter M.
The Functional Hardware Design Language is an expandable language that is designed to make it easy to specify gate-level. FHDL currently supports the specification of gates, high-level functional blocks, state machines, ROM and PLA contents, and parameterized functional blocks. The language is easily extendable.
The FHDL Manual
(2009-10-28T15:46:02Z) Maurer, Peter M.
The Functional Hardware Design Language can be used to create all parts of a digital design. It can be used to design logic-level circuits with ordinary gates, flip-flops and mid-sized functional blocks. It is hierarchical in nature and can support any type of hierarchical design. It can be used to design ROMs, PLAs, and Algorithmic State Machines. Simulations can be controlled through a high-level-language interface. This interface can be used to design test benches and to perform component-level testing on hierarchical designs. A powerful macro language can be used to create parameterized functional blocks and expression-level circuits. The language is extensible and may provide other features in the future.
Unit Delay Scheduling for the Inversion Algorithm
(2009-11-05T16:36:19Z) Maurer, Peter M.
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 presents an implementation which is based on the Unit-Delay model. Although the most basic form of the Inversion Algorithm can be converted to Unit Delay with little difficulty, special considerations must be taken to avoid scheduling conflicts. The main problems discussed in this paper are avoiding scheduling conflicts, and minimizing the amount of storage space required to do so. 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.
Three-Valued Simulation with the Inversion Algorithm
(2009-11-05T16:40:07Z) Maurer, Peter M.
The Inversion Algorithm is an event-driven logic simulation technique that is competitive with Levelized Compiled Code Simulation. Previous versions of the Inversion Algorithm have been limited to purely binary simulation. The algorithm presented here extends the Inversion Algorithm to three-valued simulation while preserving the desirable properties of the two-valued algorithm. Because of the richer transformation structure used in three-valued simulation, the scheduling technique is significantly more complex than that of the two-valued algorithm. The procedure for collapsing simultaneous events is also significantly more complex. Once a three-valued net achieves a stable binary value, it is possible to replace the three-valued simulation with a more efficient two-valued simulation. Experimental data shows that the three-valued algorithm is also competitive with levelized compiled code simulation.
Event Driven Simulation without Loops or Conditionals
(2009-11-05T16:42:01Z) Maurer, Peter M.
Event driven simulation normally requires a great deal of computation to perform a multitude of different tasks. The purpose of this paper is to show that none of these computations are necessary. Most computations are devoted to computing new states for other data structures. The technique presented here does not use state variables or any other type of state code. Subroutine addresses are used instead to maintain states. This permits the elimination of all state-testing code, and all state computation code. Our technique is significantly faster than conventional event-driven simulation. Unlike other techniques that focus on state-machine based simulation, our technique can easily be extended to virtually any logic model and any delay model.
Two New Techniques for Unit-Delay Compiled Simulation
(2009-11-05T16:43:41Z) Maurer, Peter M.
The PC-set method and the parallel technique are two methods for generating compiled unit-delay simulations of acyclic circuits. 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 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 simulations. Although the parallel technique provides for efficient simulations with a reasonable amount of generated code, there are several opportunities for optimization. The two optimization schemes presented here are called bit-field trimming and shift-elimination. Two different methods of shift elimination are presented, one which is based on breaking cycles in an undirected graph, and one which is based on tracing paths through a network. Performance results are presented for both simulation techniques, and for all optimizations. Comparisons with interpreted event-driven simulation using the ISCAS 85 benchmarks show a factor of 4 improvement for the PC-set method and a factor of ten improvement for the parallel technique. Similar studies for the optimization schemes show an average performance improvement of 47% over the unoptimized simulations.
The Inversion Algorithm for Digital Simulation
(2009-11-05T16:45:25Z) Maurer, Peter M.
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 be retargeted for new platforms with little effort.

Browse

Browsing Computer Science Technical Reports by Issue Date