Global Optimization of Digital Circuits
Date of Award
12-1991
Document Type
Thesis
Degree Name
Master of Science
Department
Department of Electrical and Computer Engineering
Abstract
This thesis was divided into two tasks. The first task involved developing a parser which could translate a behavioral specification in Very High-Speed Integrated Circuits (VHSIC) Hardware Description Language (VHDL) into the format used by an existing digital circuit optimization tool, BOolean Reasoning In Scheme (BORIS). Since this toll is written in Scheme, a dialect of Lisp, the parser was also written in Scheme. The parser was implemented is Artez's modification of Earley's Algorithm. Additionally, a VHDL tokenizer was implemented in Scheme and a portion of the VHDL grammar was converted into the format which the parser uses. The second task was the incorporation of intermediate functions into BORIS. The existing BORIS contains a recursive optimization system that optimizes digital circuits by using circuit outputs as inputs into other circuits. Intermediate functions provide a greater selection of functions to be used as circuits inputs. Using both intermediate functions and output functions, the costs of the circuits in the test set were reduced by 43%. This is a 10% reduction when compared to the existing recursive optimization system. Incorporating intermediate functions into BORIS required the development of an intermediate-function generator and a set of control methods to keep the computation time from increasing exponentially.
AFIT Designator
AFIT-GCE-ENG-91D-04
DTIC Accession Number
ADA243740
Recommended Citation
Flandera, Richard, "Global Optimization of Digital Circuits" (1991). Theses and Dissertations. 7341.
https://scholar.afit.edu/etd/7341