Sequential Synthesis for Table Look Up Programmable Gate Arrays

The algorithms for synthesis onto programmable gate arrays (PGAs) have so far addressed only the combinational logic problem [2] [3] [4] [5]. We present two approaches for mapping a sequential circuit onto a popular table look up architecture, the Xilinx 3090 architecture. In the first, combinational and sequential elements are mapped simultaneously. This is formulated as a binate covering problem. It may not be computationally feasible to go for an exact solution [6]. We describe a new heuristic to solve the binate covering formulation of the mapping problem. In the second approach, combinational elements are mapped first, followed by the sequential elements. Two algorithms are investigated: one based on network flows, and the other, on a greedy assignment. One of the contributions of this work is a fast way of determining whether two functions, along with some flip-flops, can be placed on a single logic block of Xilinx 3090. We also show that a small set of 19 patterns is complete for this block, in the sense that there exists an optimum realization of a network in terms of instances of the basic block, each configured as one of these patterns.