Simultaneous placement with clustering and duplication

ABSTRACT

Clustering, duplication, and placement are critical steps in a cluster-based FPGA design flow. Clustering has a great impact on the wirelength, timing, and routability of a circuit. Logic duplication is an effective method for improving performance while maintaining the logic equivalence of a circuit. Based on several novel algorithmic contributions, we present an efficient and effective algorithm named SPCD (simultaneous placement with clustering and duplication) which performs clustering and duplication during placement for wirelength and timing minimization. First, we incorporate a path counting-based net weighting scheme for more effective timing optimization. Secondly, we introduce a novel method of moving a fragment of a cluster (called a fragment level move) during placement to optimize the clustering structure. To reduce the critical path detour during legalization from a more global perspective, we also introduce the notions of a monotone region and a global monotone region in which improvement to the local/global path detour is guaranteed. Furthermore, we introduce a notion of a constrained gain graph to embed all complex FPGA clustering constraints, and implement an optimal incremental legalization algorithm under such constraints. Finally, in order to reduce the circuit area, we formulate a timing-constrained global redundancy removal problem and propose a heuristic solution. Our SPCD algorithm outperforms a widely used academic FPGA placement flow, T-VPack + VPR, with an average reduction of 31% in the longest path estimate delay and 18% in the routed delay. We also apply our SPCD algorithm to Altera's Stratix architecture in a commercial FPGA implementation flow (Quartus II 4.0). The routed result achieved by our SPCD algorithm outperforms VPR by 20% and outperforms Quartus II 4.0 by 4%.

References

1. Beraudo, G. and Lillis, J. 2003. Timing optimization of FPGA placements by logic replication. In Proceedings of the ACM/IEEE Design Automation Conference, 196--201.
2. Betz, V. and Rose, J. 1997. VPR: A new packing, placement and routing tool for FPGA research. In Proceedings of the International Workshop on Field Programmable Logic and Application, 213--222.
3. Bozorgzadeh, E., Ogrenci, S., and Sarrafzadeh, M. 2001. Routability-Driven packing for cluster-based FPGAs. In Proceedings of the Asia and South Pacific Design Automation Conference (Yokohama, Japan). 629--634.
4. Chen, G. and Cong, J. 2004. Simultaneous timing driven clustering and placement for FPGAs. In Proceedings of the International Conference on Field Programmable Logic and Its Applications (Antwerp, Belgium). 158--167.
5. Chen, G. and Cong, J. 2005. Simultaneous timing-driven placement and duplication. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 51--59.
6. Cong, J. and Ding, Y. 1994. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Compute.-Aided Des. 13, 1 (Jan.), 1--12.
7. Cong, J., Li, H., and Wu, C. 1999. Simultaneous circuit partitioning/clustering with retiming for performance optimization. In Proceedings of the 36th ACM/IEEE Design Automation Conference (New Orleans, La.). 460--465.
8. Hrkic, M., Lillis, J., and Beraudo, G. 2004. An approach to placement-coupled logic replication. In Proceedings of the ACM/IEEE Design Automation Conference (San Diego, Calif.). 711--716.
9. Hur, S.-W. and Lillis, J. 2000. Mongrel: Hybrid techniques for standard cell placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 165--170.
10. Kong, T. 2002. A novel net weighting algorithm for timing-driven placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 172--176.
11. Lillis, J., Cheng, C.-K., and Lin, T.-T. Y. 1996. Algorithms for optimal introduction of redundant logic for timing and area optimization. In Proceedings of the IEEE International Symposium on Circuits and Systems, 196--201.
12. Marquardt, A., Betz, V., and Rose, J. 1999. Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 37--46.
13. Marquardt, A., Betz, V., and Rose, J. 2000. Timing-driven placement for FPGAs. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 203--213.
14. Neumann, I., Stoffel, D., Hartje, H., and Kunz, W. 1999. Cell replication and redundancy elimination during placement for cycle time optimization. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 25--30.
15. Sentovich, E., Singh, K., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, Stephan, P., Brayton, R., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Electronics Research Laboratory. Memorandum No. UCB/ERL M92/41.
16. Srivastava, A., Kastner, R., and Sarrafzadeh, M. 2000. Timing driven gate duplication: Complexity issues and algorithms. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 447--450.
17. The FPGA Place-and-Route Challenge. http://www.eecg.toronto.edu/∼vaughn/challenge/challenge.html.
18. Stratix Device Handbook. http://www.altera.com/literature/lit-stx.jsp.
19. Simultaneous Placement with Clustering and Duplication for LUT-based FPGA Designs. http://ballade.cs.ucla.edu/∼chg/spcd.

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing

• Mathematics of computing

  • Mathematical software