RegPlace: a high quality open-source placement framework for structured ASICs

ABSTRACT

Structured ASICs have recently emerged as an exciting alternative to ASIC or FPGA design style as they provide a new trade-off between the high performance of ASIC design and low non-recurring engineering (NRE) costs of FPGA design. To fully utilize the benefits of structured ASICs, key physical design stage like placement should be made aware of modularity of their architecture. In this work, we propose a novel solution to placement for structured ASICs. In particular, we propose creation of intermediate virtual platform to exploit the regularity of structured ASIC and Integer Linear Program and network flow formulations for satisfying constraints associated with typical structured ASIC clock architectures. A preliminary version of this work recently won the structured ASIC placement contest by eASIC [1]. Our placer achieves 35% and 5% wirelength improvement over other placers and can place a design of 1 million cells in approximately 4 hours.

REFERENCES

• 1: "eASIC Corporate Website." http://www.easic.com/.
• 2: H. Schmit, A. Gupta, and R. Ciobanu, "Placement Challenges for Structured ASICs," in ISPD '08: Proceedings of the 2008 International Symposium on Physical design, pp. 84--86, ACM, 2008.
• 3: "SOC Central." http://www.soccentral.com/.
• 4: A. Chakraborty, A. Kumar, and D. Pan, "Regplace," http://www.cerc.utexas.edu/utda/download/RegPlace.htm.
• 5: J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, A. N. Ng, J. F. Lu, and I. L. Markov, "Capo: Robust and Scalable Open-source min-cut Floorplacer," in ISPD '05: Proceedings of the 2005 International Symposium on Physical design, pp. 224--226, ACM, 2005.
• 6: T. F. Chan, J. Cong, J. R. Shinnerl, K. Sze, and M. Xie, "mpl6: Enhanced Multilevel Mixed-size Placement," in ISPD '06: Proceedings of the 2006 International Symposium on Physical design, pp. 212--214, ACM, 2006.
• 7: N. Viswanathan, M. Pan, and C. Chu, "FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion control," in ASP-DAC '07: Proceedings of the 2007 conference on Asia South Pacific design automation, pp. 135--140, IEEE Computer Society, 2007.
• 8: T. Luo and D. Z. Pan, "DPlace2.0: A Stable and Efficient Analytical Placement Based on Diffusion," in ASP-DAC '08: Proceedings of the 2008 conference on Asia and South Pacific design automation, pp. 346--351, IEEE Computer Society Press, 2008.
• 9: "SOC Encounter tool." http://www.cadence.com/products/di/soc_encounter.
• 10: V. Betz and J. Rose, "VPR: A New Packing, Placement and Routing Tool for FPGA Research," in FPL '97: Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, pp. 213--222, Springer-Verlag, 1997.
• 11: K. Eguro, S. Hauck, and A. Sharma, "Architecture-adaptive Range Limit Windowing for Simulated Annealing FPGA Placement," in DAC '05: Proceedings of the 42nd annual conference on Design automation, pp. 439--444, ACM, 2005.
• 12: A. C. Ling, D. P. Singh, and S. D. Brown, "Incremental Placement for Structured ASICs Using the Transportation Problem," Very Large Scale Integration, 2007. VLSI - SoC 2007. IFIP International Conference on, pp. 172--177, Oct. 2007.
• 13: T. Okamoto, T. Kimoto, and N. Maeda, "Design Methodology and Tools for NEC Electronics' Structured ASIC ISSP," in ISPD '04: Proceedings of the 2004 International Symposium on Physical design, pp. 90--96, ACM, 2004.
• 14: H. W. Kuhn, "The Hungarian Method for the Assignment Problem," Naval Research Logistics Quarterly, vol. 2, pp. 83--97, 1955.
• 15: S. Goto, "An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit layout," Circuits and Systems, IEEE Transactions on, vol. 28, pp. 12--18, Jan 1981.
• 16: M. Pan, N. Viswanathan, and C. Chu, "An Efficient and Effective Detailed Placement Algorithm," Computer-Aided Design, International Conference on, vol. 0, pp. 48--55, 2005.
• 17: "GNU Linear Programming Kit." http://www.gnu.org/software/glpk/.
• 18: "Michigan Wolverine Placer by Dongjin Lee and Igor Markov."
• 19: "The Esteem Placer, written by Bob Erickson, an independent software consultant." http://www.linkedin.com/in/boberickson.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
FPGA, global placement, legalization, placement, regular ASIC, structured ASIC