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

This document is currently not available here.

Share

COinS