MIME-Version: 1.0 Server: CERN/3.0 Date: Tuesday, 07-Jan-97 15:58:12 GMT Content-Type: text/html Content-Length: 6741 Last-Modified: Tuesday, 09-May-95 21:20:41 GMT
The abstracts of papers by members of this group in the above area are listed below. Please use the email addresses at the end of each abstract to get further details.
We consider the problem of minimizing the number of logic modules for Actel 2 or Actel 3 sequential circuits. We make use of the fact that if a flip-flop is the only destination of its driving combinational block, then both the flip-flop and the combinational block can be put in a sequential module. Retiming technique is applied to minimize the number of registers that can not be merged with combinational blocks. We formulate the problem as an integer linear program. We show that the constraint matrix of the integer program is totally unimodular. As a result, we can solve our logic module minimization problem optimally by solving the linear relaxation of the integer program.Contact: yaoping@cs.utexas.edu
We consider the problem of performance driven lookup-table (LUT) based technology mapping for FPGAs using a general delay model. In the general delay model, each interconnection edge has a weight representing the delay of the interconnection. This model is particularly useful when combined with an iterative re-technology mapping process where the actual delays of the placed and routed circuit are fed-back to the technology mapping phase to improve the mapping based on the more realistic delay estimation. Well known technology mappers such as FlowMap and Chortle-d only minimize the number of levels in the technology mapped circuit and hence are not suitable for such an iterative re-technology mapping process. Recently, Mathur and Liu studied the performance driven technology mapping problem using the general delay model and presented an effective heuristic algorithm for the problem. In this paper, we present an efficient technology mapping algorithm that achieves provably optimal delay in the technology mapped circuit using the general delay model. Our algorithm is a non-trivial generalization of FlowMap. A key problem in our algorithm is to compute a K-feasible network cut such that the circuit delay on every cut edge is upper-bounded by a specific value. We implemented our algorithm in a LUT based FPGA technology mapping package called Edge-Map, and tested Edge-Map on a set of benchmark circuits.Contact: yanghh@cs.utexas.edu
As device feature size decreases, interconnection delay becomes the dominating factor of system performance. Thus it is important that accurate physical information is used during high level synthesis. In this paper, we consider the problem of simultaneously performing functional-unit binding and floorplanning. Experimental results indicate that our approach to combine binding and floorplanning is superior to the traditional approach of separating the two tasks.Contact: fang@cerc.utexas.edu
Technology mapping requires the unmapped logic network to be represented in terms of base functions. Technology decomposition is the step that transforms arbitrary networks to this form. Typically such decomposition schemes ignore the fact that certain circuit elements can be mapped more efficiently by treating them separately during decomposition. Multiplexers are in one such category of circuit elements. They appear very naturally in circuits, in the form of datapath elements, and as a result of synthesis of CASE statements in HDL specifications of control logic. Mapping them using multiplexers in technology libraries has many advantages. In this paper, we give an algorithm for optimally decomposing multiplexers, so as to minimize the delay of the network. We present the results of mapping networks, decomposed by such a scheme, to Actel2 and lsi_10K libraries, which are rich in multiplexers. Experimental results indicate that the quality of the mapped circuits, measured in terms of area, delay, and routability, is greatly improved, when compared to a Huffman tree based AND-OR decomposition scheme.Contact: thakur@cs.utexas.edu
We address the technology mapping problem for lookup table FPGAs. The area minimization problem, for mapping K-bounded networks, consisting of nodes with at most K inputs, using K-input lookup tables, is known to be NP-complete for K>=5. The complexity was unknown for K=2,3, and 4. The corresponding delay minimization problem (under the constant delay model) was solved in polynomial time by the flow-map algorithm, for arbitrary values of K. We study the class of K-bounded networks, where all nodes have exactly K inputs. We call such networks K-exact. We give a characterization of mapping solutions for such networks. This leads to a polynomial time algorithm for computing the simultaneous area and delay minimum mapping for such networks using K-input lookup tables. We also show that the flow-map algorithm minimizes the area of the mapped network as well, for K-exact networks. We then show that for K=2 the mapping solution for a 2-bounded network, minimizing the area and delay simultaneously, can be easily obtained from that of a 2-exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2-input lookup tables can be solved in polynomial time, resolving an open problem.Contact: thakur@cs.utexas.edu