Mis-pga was developed by Murgai et al at University of California Berkeley, and was presented 27th ACM/IEEE Design Automation Conference [3] in 1990. The same group had developed logic synthesis tools (such as misII) for standard PLD's. Those tools consist of two separate phases; technology-independent optimization and technology mapping. However they thought the complexity of the functions that can be implemented by LUT's would not be tractable in such traditional strategies. The mis-pga can be applied to both LUT-based and Multiplexer-based gate arrays. Here only the former is introduced.
There are several important keywords for mis-pga:
Logic synthesis by mis-pga has the following phases:
For the first step, they used their misII. For decomposition, they introduced two algorithms, Roth-Karp and Partition. However, they did not use the former in their experiments in [3] due to its high computation costs. The partition extracts kernels of non-feasible nodes, and chooses the the kernel with minimum cost. The cost of kernel k is given by , where r is the residue of kernel k. The node number minimization phase takes two steps; covering and merging. Covering is to find nodes that can be collapsed and the resulting nodes are still feasible. Mis-pga was developed for Xilinx 3000 series FPGA's. If two functions f and g satisfy,