P2CTS-3D IC: An Efficient Placement Aware Partitioning and Clock Tree Synthesis in 3D-integrated Circuits
Article Sidebar
Published:
Oct 15, 2020
Keywords:
Three dimensional integrated circuits Partitioning Placement Routing Synthesis using clock tree Through silicon via
Main Article Content
Abstract
The three dimensional integration of electronic circuits (3D-ICs) is one of the most promising approaches to encounter eternally increasing demands of functionality, performance, and power consumption. However, there exist many challenges in the minimization of power dissipation, skew, latency, wirelength, and obstacle avoidance in 3D-ICs. To overcome the discussed problems, an efficient placement aware partitioning and synthesis by clock tree have been proposed in 3D-ICs. In the proposed framework, the first process begins with the partition of netlist into multiple layers using hybrid Chemical Reaction Optimization (CRO) and K-Medoid algorithm and the placement process has been executed using Grid Warping Technique (GWT). Then, the routing process has been performed using the Line Search (LS) algorithm. The clock tree synthesis process gets accomplished with a Density Sorting (DS) algorithm that considers multiple TSVs. Further, the Clock tree topology has been implemented using the algorithm of Merging with Defer and Embedding (DME) and the algorithm of Graph with Neighbor at the Nearest. Consequently, the buffering and the embedding processes have been carried out to measure the total power dissipation and timing parameters. The proposed work minimizes the skew value compared to the other existing methods like GAP, EP, and SEA and it also provides efficient clock tree synthesis with Defer Merging and Embedding (DME) and Nearest Neighbor Graph (NNG) algorithm based methods as well as it reduces the skew optimally. Finally, the performance of the proposed work has been evaluated and proved to be better by considering the following metrics such as wirelength, power, skew, latency, and area.
Article Details
How to Cite
Nair, R. K. R., Pothiraj, S., & Nagarajan, R. (2020). P2CTS-3D IC: An Efficient Placement Aware Partitioning and Clock Tree Synthesis in 3D-integrated Circuits. Applied Science and Engineering Progress, 13(4), 377–393. Retrieved from https://ph02.tci-thaijo.org/index.php/ijast/article/view/242308
Issue
Section
Research Articles
References
[1] R. K. R. Nair, S. Pothiraj, and T. R. R. Nair “A novel optimization approach for partitioning-based place and route in 3D integrated circuits,” The International Journal of Electrical Engineering & Education, Jun. 2020, doi: 0020720920930346.
[2] O. Adekomaya, T. Jamiru, E. R. Sadiku, and A. A. Adediran, “Sustainability of high temperature polymeric materials for electronic packaging applications,” Applied Science and Engineering Progress, vol. 11, no. 3, pp. 217–224, 2018.
[3] Z. Wang, S. Kanwal, L. Wang, and A. Chattopadhyay, “Automated high-level modeling of power, temperature and timing variation for microprocessor,” Applied Science and Engineering Progress, vol. 10, no. 3, pp. 163–175, 2017.
[4] J. Barreiro-Gomez, C. Ocampo-Martinez, and N. Quijano, “Partitioning for large-scale systems: A sequential distributed MPC design,” IFAC Papersonline, vol. 50, no.1, pp. 8838–8843, 2017.
[5] S. M. Sait, F. C. Oughali, and M. Al-Asli, “Design partitioning and layer assignment for 3D integrated circuits usingtabu search and simulated annealing,” Journal of Applied Research and Technology, vol. 14, no. 1, pp. 67–76, 2016.
[6] K. Manna, V. S. S. Teja, S. Chattopadhyay, and I. Sengupta, “TSV placement and core mapping for 3D mesh based network-on-chip design using extended Kernighan-Lin partitioning,” in 2015 IEEE Computer Society Annual Symposium on VLSI, 2015, pp. 392–397.
[7] S. D. Lin and D. H. Kim, “Detailed-placement-enabled dynamic power optimization of multi-tier gatelevel monolithic 3-D ICs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 7, pp. 845–854, 2018.
[8] S. Bechikh, A. Chaabani, and L. B. Said, “An efficient chemical reaction optimization algorithm for multiobjective optimization,” IEEE Transactions on Cybernetics, vol. 45, no. 10, pp. 2051–2064, Oct. 2015.
[9] M. T. Islam, P. K. Basak, P. Bhowmik, and M. Khan, “Data clustering using hybrid genetic algorithm with k-means and k-medoids algorithms,” in 23rd International Computer Science and Engineering Conference (ICSEC), 2019, pp. 123–128.
[10] M. Wang, G. Yang, J. Lin, S. Zhang, A. Shamir, S. Lu, and S. Hu, “Deep online video stabilization with multi-grid warping transformation learning,” IEEE Transactions on Image Processing, vol. 28, no. 5, pp. 2283–2292, May 2019.
[11] J. Zhang, “On the non-monotone armijo-type line search algorithm,” in Third International Conference on Information and Computing, Wuxi, 2010, pp. 308–311.
[12] R. Zhang, X. Wei, and T. Watanabe, “A sortingbased IO connection assignment for flip-chip designs,” in IEEE 10th International Conference on ASIC, 2013, pp. 1–4, doi: 10.1109/ASICON. 2013.6811927.
[13] H. Huang, W. Luk, W. Zhao, and X. Zeng, “DMEbased clock routing in the presence of obstacles,” in 2007 7th International Conference on ASIC, pp. 1225–1228.
[14] M. R. Trad, A. Joly, and N. Boujemaa, “Large scale KNN-graph approximation,” in IEEE 12th International Conference on Data Mining Workshops, Brussels, 2012, pp. 439–448.
[15] P. Sivaranjani and G. Srividhya,”3D IC partitioning by using fast force directed simulated annealing algorithm for reducing through-silicon vias,” International Journal of Advanced Trends in Engineering and Technology, vol. 1 no. 2, pp. 6–11, 2016.
[16] S. Banerjee, S. Majumder, and B. B. Bhattacharya, “A graph-based 3D IC partitioning technique,” presented at 2014 IEEE Computer Society Annual Symposium on VLSI, Florida, USA, Jul. 9–11, 2014.
[17] C. Jang and J. Chong, “Thermal-aware floor planning with min-cut die partition for 3D ICs,” ETRI Journal, vol. 36, no. 4, pp. 635–642, 2014
[18] H. Shanavas and R. K. Gnanamurthy,”Optimal solution for vlsi physical design automation using hybrid genetic algorithm,” Mathematical Problems in Engineering, vol. 2014, pp. 1–15, 2014.
[19] C. Serafy and A. Srivastava,”TSV replacement and shield insertion for TSV–TSV coupling reduction in 3-D global placement,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 4, pp. 554–562, 2015.
[20] K. Athikulwongse and S. K. Lim, “Exploiting dieto- die thermal coupling in 3-D IC placement,” IEEE Transactions On Very Large Scale Integration (Vlsi) Systems, vol. 22, no. 10, pp. 2145– 2155, 2014.
[21] K.-C. Chen, S.-Y. Lin, H.-S. Hung, and A.-Y. Wu, “Topology-aware adaptive routing for non-stationary irregular mesh in throttled 3D NoC systems,” IEEE Transactions On Parallel And Distributed Systems, vol. 24, no. 10, pp. 2109–2120, 2017.
[22] P. Ghosal, S. Das, and A. Das, “A new class of obstacle aware steiner routing in 3D integrated circuits,” Advances in Computing and Information Technology, vol. 178, pp. 697–706, 2013.
[23] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, J. Flich, and H. Tenhunen, “Path-based partitioning methods for 3D networks-on-chip with minimal adaptive routing,” IEEE Transactions on Computers, vol. 63, no. 3, pp. 718–733, 2014.
[24] Y. Cai, C. Deng, Q. Zhou, H. Yao, F. Niu, and C. N. Sze, “Obstacle-avoiding and slew-constrained clocktree synthesis with efficient buffer insertion,” IEEE Transactions on Very Large Scale Integration (Vlsi) Systems, vol. 23, no. 1, pp. 142–155, 2014.
[25] W. Liul, H. Dul, Y. Wangl, Y. Ma, Y. Xie, J. Quan, and H. Yangl, “TSV-aware topology generation for 3D clock tree synthesis,” in 14th Int'l Symposium on Quality Electronic Design, 2013, pp. 300–307.
[26] W. Liu, H. Dul, Y. Wang, Y. Ma, Y. Xie, J. Quan, and H. Yang, “Whitespace-aware TSV arrangement in 3-D clock tree synthesis,” IEEE Transactions on Very Large Scale Integration (Vlsi) Systems, vol. 23, no. 9, pp. 1842–1853, 2015.
[27] K. Maragos, K. Siozios, and D. Soudris, “A genetic algorithm based partitioning for 3-D reconfigurable architectures,” presented at HiPEAC Workshop on Reconfigurable Computing (WRC), Netherlands, 2015.
[28] J. Lu, H. Zhuang, and I. Kang, “ePlace-3D: Electrostatics based placement for 3D-ICs,” in ISPD '16 Proceedings of the 2016 on International Symposium on Physical Design, 2016, pp. 11–18.
[29] S. M. Sait and U. F. Siddiqi, “A stochastic evolution algorithm based 2D VLSI global router” Journal Integration, the VLSI Journal archive, vol. 53, pp. 115–125, 2016.
[30] L. Chandrakar, S. Ravi, and H. M. Kittur, “Power and obstacle aware 3D clock tree synthesis,” Elecrical and Electronic Enginnering, pp. 1–13, 2017, doi: 10.20944/preprints201705.0056.v1.
[31] S. S. Gill, R. Chandel, and A. Chandel, “Genetic algorithm based approach to circuit partitioning,” International Journal of Computer and Electrical Engineering, vol. 2, no. 2, pp. 196–202, 2010.
[32] N. Y. Aung, K. K. San, and S. Z. Hlaing, “Hybrid partition around medoids algorithm for large volume of data,” in 2019 International Conference on Advanced Information Technologies (ICAIT), 2019, pp. 280–285.
[33] X. Zhong, J. D. Ma, S. M. Fowler, and R. A. Rutenbar, “Large-scale placement by gridwarping,” in Proceedings of the 41st annual Design Automation Conference, pp. 351–356. 2004.
[34] J. Hightower and G. Borriello, “Location sensing techniques,” IEEE Computer, vol. 34, no. 8, pp. 57–66, 2001.
[35] A. Jayadev, A. Jafarpour, A. Orlitsky, and A. T. Suresh, “Sorting with adversarial comparators and application to density estimation,” in 2014 IEEE International Symposium on Information Theory, 2014, pp. 1682–1686.
[36] X. Zhao, J. Minz, and S. K. Lim, “Low-power and reliable clock network design for through-silicon via (TSV) based 3D ICs,” IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 1, no. 2, pp. 247–259, 2010.
[37] S. Osmolovskyi, J. Knechtel, I. L. Markov, and J. Lienig, “Optimal die placement for interposerbased 3D ICs,” in 23rd Asia and South Pacific Design Automation Conference, pp. 513–520, Jan. 2018.
[38] R. K. Dash, J. L. Risco-Martin, and A. K. Turuk, “A thermal driven genetic algorithm for three dimensional network-on-chip systems,” in SCSC'16 Proceedings of the Summer Computer Simulation Conference, 2016, vol. 47, pp. 1–8.
[39] É. Lepercq, Y. Blaquière, and Y. Savaria, “A pattern-based routing algorithm for a novel electronic system prototyping platform,” Integration, vol. 62, pp. 224–237, 2018.
[40] Y.-H. Fan, “Fast routing verification with complexity effect for SOC,” Applied Computing and Informatics, vol. 15, no. 2, pp. 144–152, 2019.
[41] S. R. Jain and K. Okabe, “Training a fully convolutional neural network to route integrated Circuits,” Computer Vision and Pattern Recognition, 2017, doi: arXiv:1706.08948.
[42] R. Ewetz and C.-K. Koh, “Fast clock scheduling and an application to clock tree synthesis,” Integration the VLSI Journal, vol. 56, pp. 115– 127, 2016.
[43] K. S. Kumar and J. Reuben, “Minimal buffer insertion based low power clock tree synthesis for 3D integrated circuits,” Journal of Circuits, Systems, and Computers, vol. 25, no. 11, 2016, doi: 10.1142/0218126616501425.
[44] F.-W. Chen and T. Hwang, “Clock-tree synthesis with methodology of reuse in 3D-IC,” ACM Journal on Emerging Technologies in Computing Systems, vol. 10, no. 3, pp. 1–22, Apr. 2014.
[45] T. Lu and A. Srivastava, “Gated low-power clock tree synthesis for 3D-ICs,” in Proceedings of the 2014 International Symposium on Low Power Electronics and Design, pp. 319–322, 2014
[46] H. Huang, W.-S. Luk, W. Zhao, and X. Zeng, “DME-based clock routing in the presence of obstacles,” in 7th International Conference on ASIC, 2007, pp. 1225–1228.
[47] W. Jakawat and R. Makkhongkaew, “Graph clustering with K-nearest neighbor constraints,” in 16th International Joint Conference on Computer Science and Software Engineering (JCSSE), pp. 309–313, 2019.
[48] S. S. Gill, R. Chandel, A. Chandel, “Genetic algorithm based approach to circuit partitioning,” International Journal of Computer and Electrical Engineering, vol. 2, no. 2, pp. 196–202, 2010.
[2] O. Adekomaya, T. Jamiru, E. R. Sadiku, and A. A. Adediran, “Sustainability of high temperature polymeric materials for electronic packaging applications,” Applied Science and Engineering Progress, vol. 11, no. 3, pp. 217–224, 2018.
[3] Z. Wang, S. Kanwal, L. Wang, and A. Chattopadhyay, “Automated high-level modeling of power, temperature and timing variation for microprocessor,” Applied Science and Engineering Progress, vol. 10, no. 3, pp. 163–175, 2017.
[4] J. Barreiro-Gomez, C. Ocampo-Martinez, and N. Quijano, “Partitioning for large-scale systems: A sequential distributed MPC design,” IFAC Papersonline, vol. 50, no.1, pp. 8838–8843, 2017.
[5] S. M. Sait, F. C. Oughali, and M. Al-Asli, “Design partitioning and layer assignment for 3D integrated circuits usingtabu search and simulated annealing,” Journal of Applied Research and Technology, vol. 14, no. 1, pp. 67–76, 2016.
[6] K. Manna, V. S. S. Teja, S. Chattopadhyay, and I. Sengupta, “TSV placement and core mapping for 3D mesh based network-on-chip design using extended Kernighan-Lin partitioning,” in 2015 IEEE Computer Society Annual Symposium on VLSI, 2015, pp. 392–397.
[7] S. D. Lin and D. H. Kim, “Detailed-placement-enabled dynamic power optimization of multi-tier gatelevel monolithic 3-D ICs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 7, pp. 845–854, 2018.
[8] S. Bechikh, A. Chaabani, and L. B. Said, “An efficient chemical reaction optimization algorithm for multiobjective optimization,” IEEE Transactions on Cybernetics, vol. 45, no. 10, pp. 2051–2064, Oct. 2015.
[9] M. T. Islam, P. K. Basak, P. Bhowmik, and M. Khan, “Data clustering using hybrid genetic algorithm with k-means and k-medoids algorithms,” in 23rd International Computer Science and Engineering Conference (ICSEC), 2019, pp. 123–128.
[10] M. Wang, G. Yang, J. Lin, S. Zhang, A. Shamir, S. Lu, and S. Hu, “Deep online video stabilization with multi-grid warping transformation learning,” IEEE Transactions on Image Processing, vol. 28, no. 5, pp. 2283–2292, May 2019.
[11] J. Zhang, “On the non-monotone armijo-type line search algorithm,” in Third International Conference on Information and Computing, Wuxi, 2010, pp. 308–311.
[12] R. Zhang, X. Wei, and T. Watanabe, “A sortingbased IO connection assignment for flip-chip designs,” in IEEE 10th International Conference on ASIC, 2013, pp. 1–4, doi: 10.1109/ASICON. 2013.6811927.
[13] H. Huang, W. Luk, W. Zhao, and X. Zeng, “DMEbased clock routing in the presence of obstacles,” in 2007 7th International Conference on ASIC, pp. 1225–1228.
[14] M. R. Trad, A. Joly, and N. Boujemaa, “Large scale KNN-graph approximation,” in IEEE 12th International Conference on Data Mining Workshops, Brussels, 2012, pp. 439–448.
[15] P. Sivaranjani and G. Srividhya,”3D IC partitioning by using fast force directed simulated annealing algorithm for reducing through-silicon vias,” International Journal of Advanced Trends in Engineering and Technology, vol. 1 no. 2, pp. 6–11, 2016.
[16] S. Banerjee, S. Majumder, and B. B. Bhattacharya, “A graph-based 3D IC partitioning technique,” presented at 2014 IEEE Computer Society Annual Symposium on VLSI, Florida, USA, Jul. 9–11, 2014.
[17] C. Jang and J. Chong, “Thermal-aware floor planning with min-cut die partition for 3D ICs,” ETRI Journal, vol. 36, no. 4, pp. 635–642, 2014
[18] H. Shanavas and R. K. Gnanamurthy,”Optimal solution for vlsi physical design automation using hybrid genetic algorithm,” Mathematical Problems in Engineering, vol. 2014, pp. 1–15, 2014.
[19] C. Serafy and A. Srivastava,”TSV replacement and shield insertion for TSV–TSV coupling reduction in 3-D global placement,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 4, pp. 554–562, 2015.
[20] K. Athikulwongse and S. K. Lim, “Exploiting dieto- die thermal coupling in 3-D IC placement,” IEEE Transactions On Very Large Scale Integration (Vlsi) Systems, vol. 22, no. 10, pp. 2145– 2155, 2014.
[21] K.-C. Chen, S.-Y. Lin, H.-S. Hung, and A.-Y. Wu, “Topology-aware adaptive routing for non-stationary irregular mesh in throttled 3D NoC systems,” IEEE Transactions On Parallel And Distributed Systems, vol. 24, no. 10, pp. 2109–2120, 2017.
[22] P. Ghosal, S. Das, and A. Das, “A new class of obstacle aware steiner routing in 3D integrated circuits,” Advances in Computing and Information Technology, vol. 178, pp. 697–706, 2013.
[23] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, J. Flich, and H. Tenhunen, “Path-based partitioning methods for 3D networks-on-chip with minimal adaptive routing,” IEEE Transactions on Computers, vol. 63, no. 3, pp. 718–733, 2014.
[24] Y. Cai, C. Deng, Q. Zhou, H. Yao, F. Niu, and C. N. Sze, “Obstacle-avoiding and slew-constrained clocktree synthesis with efficient buffer insertion,” IEEE Transactions on Very Large Scale Integration (Vlsi) Systems, vol. 23, no. 1, pp. 142–155, 2014.
[25] W. Liul, H. Dul, Y. Wangl, Y. Ma, Y. Xie, J. Quan, and H. Yangl, “TSV-aware topology generation for 3D clock tree synthesis,” in 14th Int'l Symposium on Quality Electronic Design, 2013, pp. 300–307.
[26] W. Liu, H. Dul, Y. Wang, Y. Ma, Y. Xie, J. Quan, and H. Yang, “Whitespace-aware TSV arrangement in 3-D clock tree synthesis,” IEEE Transactions on Very Large Scale Integration (Vlsi) Systems, vol. 23, no. 9, pp. 1842–1853, 2015.
[27] K. Maragos, K. Siozios, and D. Soudris, “A genetic algorithm based partitioning for 3-D reconfigurable architectures,” presented at HiPEAC Workshop on Reconfigurable Computing (WRC), Netherlands, 2015.
[28] J. Lu, H. Zhuang, and I. Kang, “ePlace-3D: Electrostatics based placement for 3D-ICs,” in ISPD '16 Proceedings of the 2016 on International Symposium on Physical Design, 2016, pp. 11–18.
[29] S. M. Sait and U. F. Siddiqi, “A stochastic evolution algorithm based 2D VLSI global router” Journal Integration, the VLSI Journal archive, vol. 53, pp. 115–125, 2016.
[30] L. Chandrakar, S. Ravi, and H. M. Kittur, “Power and obstacle aware 3D clock tree synthesis,” Elecrical and Electronic Enginnering, pp. 1–13, 2017, doi: 10.20944/preprints201705.0056.v1.
[31] S. S. Gill, R. Chandel, and A. Chandel, “Genetic algorithm based approach to circuit partitioning,” International Journal of Computer and Electrical Engineering, vol. 2, no. 2, pp. 196–202, 2010.
[32] N. Y. Aung, K. K. San, and S. Z. Hlaing, “Hybrid partition around medoids algorithm for large volume of data,” in 2019 International Conference on Advanced Information Technologies (ICAIT), 2019, pp. 280–285.
[33] X. Zhong, J. D. Ma, S. M. Fowler, and R. A. Rutenbar, “Large-scale placement by gridwarping,” in Proceedings of the 41st annual Design Automation Conference, pp. 351–356. 2004.
[34] J. Hightower and G. Borriello, “Location sensing techniques,” IEEE Computer, vol. 34, no. 8, pp. 57–66, 2001.
[35] A. Jayadev, A. Jafarpour, A. Orlitsky, and A. T. Suresh, “Sorting with adversarial comparators and application to density estimation,” in 2014 IEEE International Symposium on Information Theory, 2014, pp. 1682–1686.
[36] X. Zhao, J. Minz, and S. K. Lim, “Low-power and reliable clock network design for through-silicon via (TSV) based 3D ICs,” IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 1, no. 2, pp. 247–259, 2010.
[37] S. Osmolovskyi, J. Knechtel, I. L. Markov, and J. Lienig, “Optimal die placement for interposerbased 3D ICs,” in 23rd Asia and South Pacific Design Automation Conference, pp. 513–520, Jan. 2018.
[38] R. K. Dash, J. L. Risco-Martin, and A. K. Turuk, “A thermal driven genetic algorithm for three dimensional network-on-chip systems,” in SCSC'16 Proceedings of the Summer Computer Simulation Conference, 2016, vol. 47, pp. 1–8.
[39] É. Lepercq, Y. Blaquière, and Y. Savaria, “A pattern-based routing algorithm for a novel electronic system prototyping platform,” Integration, vol. 62, pp. 224–237, 2018.
[40] Y.-H. Fan, “Fast routing verification with complexity effect for SOC,” Applied Computing and Informatics, vol. 15, no. 2, pp. 144–152, 2019.
[41] S. R. Jain and K. Okabe, “Training a fully convolutional neural network to route integrated Circuits,” Computer Vision and Pattern Recognition, 2017, doi: arXiv:1706.08948.
[42] R. Ewetz and C.-K. Koh, “Fast clock scheduling and an application to clock tree synthesis,” Integration the VLSI Journal, vol. 56, pp. 115– 127, 2016.
[43] K. S. Kumar and J. Reuben, “Minimal buffer insertion based low power clock tree synthesis for 3D integrated circuits,” Journal of Circuits, Systems, and Computers, vol. 25, no. 11, 2016, doi: 10.1142/0218126616501425.
[44] F.-W. Chen and T. Hwang, “Clock-tree synthesis with methodology of reuse in 3D-IC,” ACM Journal on Emerging Technologies in Computing Systems, vol. 10, no. 3, pp. 1–22, Apr. 2014.
[45] T. Lu and A. Srivastava, “Gated low-power clock tree synthesis for 3D-ICs,” in Proceedings of the 2014 International Symposium on Low Power Electronics and Design, pp. 319–322, 2014
[46] H. Huang, W.-S. Luk, W. Zhao, and X. Zeng, “DME-based clock routing in the presence of obstacles,” in 7th International Conference on ASIC, 2007, pp. 1225–1228.
[47] W. Jakawat and R. Makkhongkaew, “Graph clustering with K-nearest neighbor constraints,” in 16th International Joint Conference on Computer Science and Software Engineering (JCSSE), pp. 309–313, 2019.
[48] S. S. Gill, R. Chandel, A. Chandel, “Genetic algorithm based approach to circuit partitioning,” International Journal of Computer and Electrical Engineering, vol. 2, no. 2, pp. 196–202, 2010.