http://iet.metastore.ingenta.com
1887

Effective regularity extraction and placement techniques for datapath-intensive circuits

Effective regularity extraction and placement techniques for datapath-intensive circuits

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • R.X. Nijssen , J.A. Jess .
        1. Nijssen, R.X., Jess, J.A.: ‘Two-dimensional datapath regularity extraction’. Proc. IFIP Workshop Logic Architecture Synthesis, Grenoble, France, December 1996, pp. 110117.
        . Proc. IFIP Workshop Logic Architecture Synthesis , 110 - 117
    2. 2)
      • N. Viswanathan , M. Pan , C. Chu .
        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.
        . Proc. Asia South Pacific Design Automation Conf. , 135 - 140
    3. 3)
      • A.B. Kahng , Q. Wang .
        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.
        . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 5 , 734 - 747
    4. 4)
      • T.C. Chen , Z.W. Jiang , T.C. Hsu .
        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.
        . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 7 , 1228 - 1240
    5. 5)
      • T.F. Chan , J. Cong , J.R. Shinnerl .
        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.
        . Proc. Int. Symp. Physical Design , 212 - 214
    6. 6)
      • S.I. Ward , M.C. Kim , N. Viswanathan .
        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.
        . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 2 , 228 - 241
    7. 7)
      • J.A. Roy , D.A. Papa , S.N. Adya .
        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.
        . Proc. Int. Symp. Physical Design , 224 - 226
    8. 8)
      • J.A. Roy , I.L. Markov .
        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.
        . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 4 , 632 - 644
    9. 9)
      • M.C. Kim , D.J. Lee , I.L. Markov .
        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.
        . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 1 , 50 - 60
    10. 10)
      • S.I. Ward , D.Z. Pan , E.E. Swartzlander .
        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/.
        .
    11. 11)
      • G. Odawara , T. Hiraide , O. Nishina .
        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.
        . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 3 , 355 - 363
    12. 12)
      • M. Hirsch , D. Siewiorek .
        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.
        . Proc. Int. Conf. Computer Aided Design , 456 - 459
    13. 13)
      • S.R. Arikati , R. Varadarajan .
        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.
        . Proc. Int. Conf. Computer-Aided Design , 542 - 545
    14. 14)
      • S. Chou , M.K. Hsu , Y.W. Chang .
        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.
        . Proc. Design Automation Conf. , 762 - 767
    15. 15)
      • S.I. Ward , M.C. Kim , N. Viswanathan .
        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.
        . Proc. Int. Symp. Physical Design , 79 - 86
    16. 16)
      • S.I. Ward , D. Ding , D.Z. Pan .
        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.
        . Proc. Design Automation Conf. , 756 - 761
    17. 17)
      • T.H. Cormen , C.E. Leiserson , R.L. Rivest . (2009)
        17. Cormen, T.H., Leiserson, C.E., Rivest, R.L., et al: ‘Introduction to algorithms’ (MIT Press, 2009, 3rd edn.).
        .
    18. 18)
      • I. Lim , Y. Wang , H. Shin .
        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.
        . Proc. Int. Conf. Electronics, Information & Communication , 442 - 443
    19. 19)
      • J. Cong , M. Xie .
        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.
        . IEEE Trans. Comput. Aided Design Integr. Circuits Syst. , 8 , 1349 - 1362
    20. 20)
      • D. Hill .
        20. Hill, D.: ‘Method and system for high speed detailed placement of cells within an integrated circuit design’. US patent 6,370,673, 2002.
        .
    21. 21)
      • M. Pan , N. Viswanathan , C. Chu .
        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.
        . Proc. Int. Conf. Computer Aided Design , 48 - 55
    22. 22)
      • H. Shojaei , A. A. Davoodi , J. Linderoth .
        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.
        . Proc. Int. Conf. on Computer Aided Design , 256 - 262
    23. 23)
      • S.I. Ward , D.A. Papa , Z. Li .
        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.
        . Proc. ACM Int. Symp. Physical Design , 91 - 98
    24. 24)
      • N. Viswanathan , C.J. Alpert , C. Sze .
        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.
        . Proc. Int. Symp. Physical Design , 141 - 146
    25. 25)
      • N. Viswanathan , C.J. Alpert , C. Sze .
        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.
        . Proc. Design, Automation Conf. , 774 - 782
    26. 26)
      • J. Hu , J.A. Roy , I.L. Markov .
        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.
        . Proc. Int. Symp. Physical Design , 35 - 41
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
This is a required field
Please enter a valid email address