Mis-pga

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:

Cube-free

No cube divides the expression evenly.

Primary divisors

of expression f are
.

Kernels

of expression f are
.

Residue

r associated with kernel k of a function f is obtained by substituting all occurrences of k in f by a new variable.

Support

of function f
set of variables f explicitly depends on.
= cardinality of .

Feasible Function

f is feasible if (K: number of LUT inputs).

Feasible Network

every intermediate node is a feasible function.

Logic synthesis by mis-pga has the following phases:

1. Logic optimization
2. Decomposition to a feasible network.
3. Node number minimization.

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,

• and
• 
•