EECS 298-11: CAD Seminar
Wednesday, March 5, 1997, 5pm
Cory Hall--Hogan Room

   FPGA Mapping, Retiming, and Pipelining for Performance Optimization

                         Jason Cong
             UCLA Computer Science Department
                    Los Angeles, CA 90095
                      <cong@cs.ucla.edu>

In this talk, I shall first review the previous work on depth-optimal mapping
(FlowMap by Cong and Ding) and optimal mapping with retiming for clock
period minimization (SeqMapII by Pan and Liu).
Then, I shall present the recent research results from my group on
FPGA Mapping, Retiming, and Pipelining for Performance Optimization.
First, we developed a very efficient and scalable algorithm, named TurboMap,
for optimal mapping with retiming.  It used a number of novel techniques
to improve the efficiency of the previous approach, including
(i) efficient label update with single K-cut computation based on the
monotone property, (ii) incremental construction of partial flow networks
for K-cut computaton, and (iii) SCC (strongly connected component) partition.
As a result, TurboMap runs > 1000 times faster than SeqMapII, but yet still
guarantees the optimal clock period and uses fewer LUTs and FFs.
Furthermore,  we developed an efficient mapping with resynthesis technique
for minimizing the maximum loop's delay-to-register ratio,
so that the circuit can be optimally pipelined for the best performance.
For the MCNC and ISCAS89 benchmark circuits used in our experiments,
we achieve an average reduction of clock period by factor of 1.4 to 2.2
compared to the best known existing methods.