Optimality Study Project


As the final economic and physical barriers to continued increases in CMOS circuit densities begin to take shape, automated design tools play an ever more important role in determining system performance. Recently we showed that existing circuit layouts are surprisingly far from optimal in terms of total wirelength. Using a set of cleverly constructed circuit-placement examples with known optima (PEKO) that match many industrial circuit characteristics, our study shows that the results of leading placement tools from both industry and academia are 70% to 150% away from the optimal solutions in terms of the total wirelength on these cases. This result has attracted considerable attention among industrial designers and academic researchers, including an EE Times cover story on Feb. 5, 2003 and another article on Apr. 10, 2003 and over 300 downloads (as of Nov. 2007) of the PEKO test suite from our web site by major universities and EDA and semiconductor companies, e.g., Cadence, Magma, IBM, and Intel. This work has been extended for partitioning, floorplanning and timing-driven placement algorithms.

After many of the placement optimality questions were answered, people became interested in asking similar questions about logic synthesis. To begin to address the optimality in logic synthesis two sets of circuits were created. Using these circuits and their derivatives (called LEKO and LEKU, respectively), we showed that although leading FPGA technology mapping algorithms can produce close to optimal solutions, the results from the entire logic synthesis flow (logic optimization + mapping) are far from optimal. The LEKU circuits were constructed to show where the logic synthesis flow can be improved, while the LEKO circuits specifically deal with the performance of the technology mapping. The best industrial and academic FPGA synthesis flows are around 70 times larger in terms of area on average, and in some cases as much as 500 times larger on LEKU examples. These phenomenal numbers generated significant interest including two articles (an EE Times cover story on 2/20/2006 and an FPGA Journal article on 4/25/2006), and many downloads (over 30 registered users and over 250 downloads as of Nov. 2007) from industry (Mentor Graphics, Altera, Xilinx, Magma DA, Synplicity) and from universities all over the world.


People
Research Leader
Professor Jason Cong
Students
  • Michail Romesis
  • Min Xie
  • Kirill Minkovich


  • Benchmarks

    PEKO - Placement Examples with Known Optimal Solution
    PEKU - Placement Examples with Tight Upper Bound of Optimal Solution
    TPEKO - Timing-Driven Placement Examples with Known Optimal Solution
    BEKU - Partitioning Examples with Tight Upper Bound of Optimal Solution
    AFEKO - Floorplanning Examples with Known Optimal area
    LEKO/LEKU - Logic synthesis Examples with Known Optimal/Upper-bounds




    Publications
    1. C.-C. Chang, J. Cong, and M. Xie"Optimality and Scalability Study of Existing Placement Algorithms", Asia South Pacific Design Automation Conference, Kitakyushu, Japan, pp. 621-627, January 2003.
    2. J. Cong, M. Romesis, and M. Xie "Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms", Proc. of the International Symposium on Physical Design , Monterey , CA, pp. 88-94, April 2003.
    3. J. Cong, M. Romesis, and M. Xie "Optimality and Stability Study of Timing-Driven Placement Algorithms", UCLA Computer Science Department Technical Report #030030
    4. J. Cong, M. Romesis, and M. Xie "Optimality and Stability Study of Timing-Driven Placement Algorithms", Proc. of the International Conference on Computer-Aided Design, San Jose, CA, pp. 472 - 478, November 2003.
    5. J. Cong, G. Nataneli, M. Romesis, and J. Shinnerl "An Area-Optimality Study of Floorplanning", Proc. of the International Symposium on Physical Design, Phoenix, AZ, pp. 78 - 83, April 2004.
    6. C. Chang, J. Cong, M. Romesis, and M. Xie "Optimality and Scalability Study of Existing Placement Algorithms", IEEE Trans. on Computer-Aided Design, pp. 537 - 549, April 2004.
    7. J. Cong and K. Minkovich, "Optimality Study of Logic Synthesis for LUT-Based FPGAs,"   Proceedings of the 14th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Monterey, CA, February 2006.
    8. J. Cong and K. Minkovich, "Optimality Study of Logic Synthesis for LUT-Based FPGAs,"   TCAD: Special Edition for FPGA, 2006.

    Sponsors


    Copyright  2003.  The Regents of the University of California.
    Last modified: