Algorithms in computer-aided design of VLSI circuits.

Yang, Meng

Abstract

With the increased complexity of Very Large Scale Integrated (VLSI) circuits,
Computer Aided Design (CAD) plays an even more important role. Top-down
design methodology and layout of VLSI are reviewed. Moreover, previously
published algorithms in CAD of VLSI design are outlined.
In certain applications, Reed-Muller (RM) forms when implemented with
AND/XOR or OR/XNOR logic have shown some attractive advantages over
the standard Boolean logic based on AND/OR logic. The RM forms implemented
with OR/XNOR logic, known as Dual Forms of Reed-Muller (DFRM),
is the Dual form of traditional RM implemented with AND /XOR.
Map folding and transformation techniques are presented for the conversion
between standard Boolean and DFRM expansions of any polarity. Bidirectional
multi-segment computer based conversion algorithms are also proposed
for large functions based on the concept of Boolean polarity for canonical
product-of-sums Boolean functions. Furthermore, another two tabular based
conversion algorithms, serial and parallel tabular techniques, are presented for
the conversion of large functions between standard Boolean and DFRM expansions
of any polarity. The algorithms were tested for examples of up to 25
variables using the MCNC and IWLS'93 benchmarks.
Any n-variable Boolean function can be expressed by a Fixed Polarity
Reed-Muller (FPRM) form. In order to have a compact Multi-level MPRM
(MMPRM) expansion, a method called on-set table method is developed.
The method derives MMPRM expansions directly from FPRM expansions.
If searching all polarities of FPRM expansions, the MMPRM expansions with
the least number of literals can be obtained. As a result, it is possible to find
the best polarity expansion among 2n FPRM expansions instead of searching
2n2n
-
1 MPRM expansions within reasonable time for large functions. Furthermore,
it uses on-set coefficients only and hence reduces the usage of memory
dramatically.
Currently, XOR and XNOR gates can be implemented into Look-Up Tables
(LUT) of Field Programmable Gate Arrays (FPGAs). However, FPGA
placement is categorised to be NP-complete. Efficient placement algorithms
are very important to CAD design tools. Two algorithms based on Genetic
Algorithm (GA) and GA with Simulated Annealing (SA) are presented for the
placement of symmetrical FPGA. Both of algorithms could achieve comparable
results to those obtained by Versatile Placement and Routing (VPR) tools
in terms of the number of routing channel tracks.

Citation

Yang, M. Algorithms in computer-aided design of VLSI circuits. (Thesis). Edinburgh Napier University. http://researchrepository.napier.ac.uk/id/eprint/6493

• Thesis Type: Thesis
• Deposit Date: Nov 14, 2013
• Peer Reviewed: Not Peer Reviewed
• Keywords: Very Large Scale Integrated (VLSI) circuits; Computer Aided Design (CAD); Dual Forms of Reed-Muller (DFRM)
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/6493
• Contract Date: Nov 14, 2013
• Award Date: 2006-06