Algorithms in computer-aided design of VLSI circuits.

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 standard Boolean logic based on AND/OR logic. The RM forms implemented with OR/XNOR logic, known as Dual Forms of Reed–Muller (DFRM), are 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, 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 the on-set table method is developed. The method derives MMPRM expansions directly from FPRM expansions. By searching all polarities of FPRM expansions, MMPRM expansions with the least number of literals can be obtained. As a result, it is possible to find the best polarity expansion among 2^n FPRM expansions instead of searching 2^(n·2^n−1) MPRM expansions within reasonable time for large functions. Furthermore, it uses on-set coefficients only and hence reduces memory usage dramatically. Currently, XOR and XNOR gates can be implemented into look-up tables (LUTs) of field-programmable gate arrays (FPGAs). However, FPGA placement is categorised as NP-complete. Efficient placement algorithms are therefore 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 algorithms achieve comparable results to those obtained by Versatile Placement and Routing (VPR) tools in terms of the number of routing channel tracks.