access icon free Effective regularity extraction and placement techniques for datapath-intensive circuits

Regular structures, like datapath, are important components of integrated circuits. Datapath logic is usually placed with high regularity and compactness for higher performance by using manual placement. The authors propose effective datapath regularity extraction and placement (DREP) techniques which simultaneously place datapath logic and random logic. This method detects datapath logic and effectively formats regular datapath structures while optimizing the order of functional stages and placement of datapath blocks. Moreover, the datapath structures are further optimized by using bit-slice order adjustment and partitioning techniques during global placement. Partitioning of a big datapath macro greatly increases the placement flexibility, since partitioned sub-blocks of the datapath macro can be optimally placed with other blocks. A new effective method is also suggested to decide the block to be partitioned and the granularity of partitioning. Similar to the manual placement results, the datapath logic is regularly placed and the datapath cells are aligned well, vertically or horizontally by the DREP techniques. When compared with the state-of-the-art works, the experimental results show that the new techniques produce significantly better results than other methods in terms of half perimeter wire length, Steiner wire length, and routability, measured from the detail routing results.

Inspec keywords: integrated circuit design; wires (electric); microprocessor chips; network routing

Other keywords: datapath block placement; DREP technique; circuit design; regular datapath structures; bit-slice order adjustment; datapath-intensive circuits; datapath regularity extraction and placement techniques; half perimeter wire length; datapath cells; placement flexibility; datapath logic; Steiner wire length; routability; global placement; big datapath macro partitioning; integrated circuit components; random logic

Subjects: Digital circuit design, modelling and testing; Microprocessors and microcomputers; Microprocessor chips

References

    1. 1)
      • 20. Hill, D.: ‘Method and system for high speed detailed placement of cells within an integrated circuit design’. US patent 6,370,673, 2002.
    2. 2)
      • 9. Kim, M.C., Lee, D.J., Markov, I.L.: ‘SimPL: an effective placement algorithm’, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2012, 31, (1), pp. 5060.
    3. 3)
      • 4. Chen, T.C., Jiang, Z.W., Hsu, T.C., et al: ‘NTUplace3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints’, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2008, 27, (7), pp. 12281240.
    4. 4)
      • 6. Ward, S.I., Kim, M.C., Viswanathan, N., et al: ‘Structure-aware placement techniques for designs with datapaths’, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2013, 32, (2), pp. 228241.
    5. 5)
      • 19. Cong, J., Xie, M.: ‘A robust mixed-size legalization and detailed placement algorithm’, IEEE Trans. Comput. Aided Design Integr. Circuits Syst., 2008, 27, (8), pp. 13491362.
    6. 6)
      • 11. Odawara, G., Hiraide, T., Nishina, O.: ‘Partitioning and placement technique for CMOS gate arrays’, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1987, 6, (3), pp. 355363.
    7. 7)
      • 21. Pan, M., Viswanathan, N., Chu, C.: ‘An efficient and effective detailed placement algorithm’. Proc. Int. Conf. Computer Aided Design, San Jose, CA, USA, November 2005, pp. 4855.
    8. 8)
      • 8. Roy, J.A., Markov, I.L.: ‘Seeing the forest and the trees: Steiner wire length optimization in placement’, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2007, 26, (4), pp. 632644.
    9. 9)
      • 3. Kahng, A.B., Wang, Q.: ‘Implementation and extensibility of an analytic placer’, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2005, 24, (5), pp. 734747.
    10. 10)
      • 23. Ward, S.I., Papa, D.A., Li, Z., et al: ‘Quantifying academic placer performance on custom designs’. Proc. ACM Int. Symp. Physical Design, Santa Barbara, CA, USA, March 2011, pp. 9198.
    11. 11)
      • 14. Chou, S., Hsu, M.K., Chang, Y.W.: ‘Structure-aware placement for datapath-intensive circuit designs’. Proc. Design Automation Conf., San Francisco, CA, USA, June 2012, pp. 762767.
    12. 12)
      • 12. Hirsch, M., Siewiorek, D.: ‘Automatically extracting structure from a logical design’. Proc. Int. Conf. Computer Aided Design, Santa Clara, CA, USA, November 1988, pp. 456459.
    13. 13)
      • 22. Shojaei, H., A. Davoodi, A., Linderoth, J.: ‘Congestion analysis for global routing via integer programming’. Proc. Int. Conf. on Computer Aided Design, San Jose, CA, USA, November 2011, pp. 256262.
    14. 14)
      • 13. Arikati, S.R., Varadarajan, R.: ‘A signature based approach to regularity extraction’. Proc. Int. Conf. Computer-Aided Design, San Jose, CA, USA, November 1997, pp. 542545.
    15. 15)
      • 25. Viswanathan, N., Alpert, C.J., Sze, C., et al: ‘The DAC 2012 routability-driven placement contest and benchmark suite’. Proc. Design, Automation Conf., San Francisco, CA, USA, June 2012, pp. 774782.
    16. 16)
      • 24. Viswanathan, N., Alpert, C.J., Sze, C., et al: ‘The ISPD-2011 routability-driven placement contest and benchmark suite’. Proc. Int. Symp. Physical Design, Santa Barbara, CA, USA, March 2011, pp. 141146.
    17. 17)
      • 10. Ward, S.I., Pan, D.Z., Swartzlander, E.E.Jr.: ‘ISPD datapath benchmark suite’, 2011, Available at http://www.cerc.utexas.edu/utda/download/DP/.
    18. 18)
      • 18. Lim, I., Wang, Y., Shin, H.: ‘Analytical placement using continuous density function’. Proc. Int. Conf. Electronics, Information & Communication, Jeongseon, South Korea, February 2012, pp. 442443.
    19. 19)
      • 5. Chan, T.F., Cong, J., Shinnerl, J.R., et al: ‘mPL6: enhanced multilevel mixed-size placement’. Proc. Int. Symp. Physical Design, San Jose, CA, USA, April 2006, pp. 212214.
    20. 20)
      • 2. Viswanathan, N., Pan, M., Chu, C.: ‘FastPlace 3.0: a fast multilevel quadratic placement algorithm with placement congestion control’. Proc. Asia South Pacific Design Automation Conf., Yokohama, Japan, January 2007, pp. 135140.
    21. 21)
      • 1. Nijssen, R.X., Jess, J.A.: ‘Two-dimensional datapath regularity extraction’. Proc. IFIP Workshop Logic Architecture Synthesis, Grenoble, France, December 1996, pp. 110117.
    22. 22)
      • 26. Hu, J., Roy, J.A., Markov, I.L.: ‘Completing high-quality global routes’. Proc. Int. Symp. Physical Design, San Francisco, CA, USA, March 2010, pp. 3541.
    23. 23)
      • 17. Cormen, T.H., Leiserson, C.E., Rivest, R.L., et al: ‘Introduction to algorithms’ (MIT Press, 2009, 3rd edn.).
    24. 24)
      • 16. Ward, S.I., Ding, D., Pan, D.Z.: ‘PADE: a high-performance placer with automatic datapath extraction and evaluation through high-dimensional data learning’. Proc. Design Automation Conf., San Francisco, CA, USA, June 2012, pp. 756761.
    25. 25)
      • 15. Ward, S.I., Kim, M.C., Viswanathan, N., et al: ‘Keep it straight: teaching placement how to better handle designs with datapaths’. Proc. Int. Symp. Physical Design, Napa, CA, USA, March 2012, pp. 7986.
    26. 26)
      • 7. Roy, J.A., Papa, D.A., Adya, S.N., et al: ‘Capo: robust and scalable open-source min-cut floorplacer’. Proc. Int. Symp. Physical Design, San Francisco, CA, USA, April 2005, pp. 224226.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2016.0249
Loading

Related content

content/journals/10.1049/iet-cds.2016.0249
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading