An Elitist Non-Dominated Multi-Objective Genetic Algorithm Based Temperature Aware Circuit Synthesis.

Apangshu Das; Sambhu Nath Pradhan

doi:10.9781/ijimai.2020.07.003

Authors

Apangshu Das National Institute of Technology Agartala
Sambhu Nath Pradhan National Institute of Technology Agartala

DOI:

https://doi.org/10.9781/ijimai.2020.07.003

Keywords:

Thermal Aware, Mixed Polarity Reed-muller, Non-Dominated Sorting Genetic Algorithm II (NSGA-II)

Supporting Agencies

This work was supported by SMDP-C2SD project sponsored by Ministry of Electronics and Information Technology (Meity), Govt. of India.

Abstract

At sub-nanometre technology, temperature is one of the important design parameters to be taken care of during the target implementation for the circuit for its long term and reliable operation. High device package density leads to high power density that generates high temperatures. The temperature of a chip is directly proportional to the power density of the chip. So, the power density of a chip can be minimized to reduce the possibility of the high temperature generation. Temperature minimization approaches are generally addressed at the physical design level but it incurs high cooling cost. To reduce the cooling cost, the temperature minimization approaches can be addressed at the logic level. In this work, the Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) based multi-objective heuristic approach is proposed to select the efficient input variable polarity of Mixed Polarity Reed-Muller (MPRM) expansion for simultaneous optimization of area, power, and temperature. A Pareto optimal solution set is obtained from the vast solution set of 3n (‘n’ is the number of input variables) different polarities of MPRM. Tabular technique is used for input polarity conversion from Sum-of-Product (SOP) form to MPRM form. Finally, using CADENCE and HotSpot tool absolute temperature, silicon area and power consumption of the synthesized circuits are calculated and are reported. The proposed algorithm saves around 76.20% silicon area, 29.09% power dissipation and reduces 17.06% peak temperature in comparison with the reported values in the literature.

Downloads

Download data is not yet available.

References

[1] T. Sasao, Logic synthesis and optimization, 1st ed. MA: Kluwer Academic Publishers, Springer US, 1993, ch. 13.

[2] J. Saul, Logic synthesis for arithmetic circuits using the reed-muller representation, in Proc. of 3rd IEEE The European Conference on Design Automation, Belgium, 1992, pp. 109-113.

[3] H. Rahaman, D.K. Das and B.B. Bhattacharya, “Testable design of AND– EXOR logic networks with universal test sets,” Comp. & Elec. Eng., Vol. 35, no. 5, pp. 644-658, Sept. 2009.

[4] S. Chattopadhyay, S. Roy and P.P. Chaudhuri, “Synthesis of highly testable fixed-polarity AND-XOR canonical networks-A genetic algorithm-based approach,” IEEE trans. on comps., Vol. 45, no. 4, pp. 487-490, Apr. 1996.

[5] T. Villa, T. Kam, R. K. Brayton and A. L. Sangiovanni-Vincentelli, Synthesis of finite state machines: logic optimization, Springer Science & Business Media, Dec. 2012, ch. 10.

[6] W. Pengjun, and L. Hui, “Low power mapping for AND/XOR circuits and its application in searching the best mixed-polarity,’ J. of Semiconductors, Vol. 32, no. 2, pp. 025007, 2011.

[7] U. Narayanan and C.L. Liu, “Low power logic synthesis for XOR based circuits,”in Proc. of the IEEE/ACM International conference on Computeraided design, USA, 1997, pp. 570-574.

[8] Z. He, L. Xiao, L. Ruan, F. Gu, Z. Huo, G. Qin, M. Zhu, L. Zhang, R. Liu, and X. Wang, “A Power and Area Optimization Approach of Mixed Polarity Reed-Muller Expression for Incompletely Specified Boolean Functions,” J. of Comp. Sci. and Techn., Vol. 32, no. 2, pp. 297-311, Mar. 2017.

[9] T. Sasao, Switching theory for logic synthesis, 1st ed. Springer Science & Business Media, 2012, ch. 3.

[10] B.A. Al Jassani, N. Urquhart and A.E.A. Almaini, “Manipulation and optimisation techniques for Boolean logic,” IET Comp. & Dig. Techn., Vol. 4, no. 3, pp. 227-239, may 2010.

[11] Y. S. Xia, L.Y. Wang, Z.G. Zhou, X.E. Ye and J.P. Hu, “Novel synthesis and optimization of multi-level mixed polarity Reed-Muller functions,” J. of Comp. Sci. and Techn., Vol. 20, no. 6, pp. 895-900, Nov. 2005.

[12] Z. He, L. Xiao, Z. Huo, T. Wang, and X. Wang, “Fast Minimization of Fixed Polarity Reed-Muller Expressions,” IEEE Access, Vol. 7, pp. 24843- 24851, 2019.

[13] Z. He, L. Xiao, Z. Huo, C. Wang, J. Liu and X. Wang, “POA-FPRMs: Power Optimization Approach of Fixed Polarity Reed-Muller Expressions for Incompletely Specified Boolean Functions,” Chinese Journal of Electronics, Vol. 28, no. 6, pp. 1144-1151, 2019.

[14] C. Chen, B. Lin, and M. Zhu, “Verification Method for Area Optimization of Mixed-Polarity Reed-Muller Logic Circuits,” Journal of Engg. Sci. & Techn. Rev., Vol. 11, no. 1, pp. 28-34, 2018.

[15] Z. He, L. Xiao, F. Gu, L. Ruan, Z. Huo, M. Li, M. Zhu, L. Zhang, R. Liu, and X. Wang, “EDOA: an efficient delay optimization approach for mixedpolarity Reed-Muller logic circuits under the unit delay model,” Frontiers of Comp. Sci., Vol. 13, no. 5, pp. 1102-1115, 2019.

[16] A. Das, and S. N. Pradhan, “Area-Power-Temperature Aware ANDXOR Network Synthesis Based on Shared Mixed Polarity Reed-Muller Expansion,” Int. J. of Intelligent Sys. and App., Vol. 10, no. 12, pp. 35-46, 2018.

[17] A. Das, A. Debnath and S.N. Pradhan, “Area, power and temperature optimization during binary decision diagram based circuit synthesis,” in proc. IEEE International conference on Devices for Integrated Circuit, India, 2017, pp. 778-782.

[18] The Temperature Ratings of Electronic Parts. In: Electronics COOLING [online]. 2004. Available: http://www.electronics-cooling.com/2004/02/the-temperature-ratings-of-electronic-parts/. [last accessed July 2018].

[19] L. Wang, “Fast algorithms for thermal-aware floorplanning,” J. of Circ., Sys., and Comp., Vol. 23, no. 07, pp. 1450098, 2014.

[20] K. Sankaranarayanan, S. Velusamy, M. Stan, and K. Skadron, “A case for thermal-aware floorplanning at the microarchitectural level,” J. of Instr.- Lev. Parallelism, Vol. 7, no. 1, pp. 8-16, May 2005.

[21] S. Gunther, F. Binns, D.M. Carmean and J.C. Hall, “Managing the impact of increasing microprocessor power consumption,” Intel Techn. J., Vol. 5, no. 1, pp. 1-9, 2001.

[22] A. Das, and S.N. Pradhan, “Shared Reed-Muller Decision Diagram Based Thermal-Aware AND-XOR Decomposition of Logic Circuits,” VLSI Design, Vol. 2016, pp. 1-14, Mar. 2016.

[23] A. Das and S.N. Pradhan, “Thermal aware FPRM based AND-XOR network synthesis of logic circuits,”in proc. 2nd IEEE International Conference on Recent Trends in Information Systems, India, 2015, pp. 497- 502.

[24] A. Das, and S.N. Pradhan, “Thermal aware output polarity selection of programmable logic arrays,”in proc. IEEE International Conference on Electronic Design, Computer Networks & Automated Verification, India, 2015, pp. 68-71.

[25] A. Das, S. R. Choudhury, B.K. Kumar and S.N. Pradhan, “An elitist areapower density trade-off in VLSI floorplan using genetic algorithm,”in proc. 7th IEEE International Conference on Electrical and Computer Engineering,Bangladesh, 2012, pp. 729-732.

[26] P. Choudhury, K. Manna, V. Rai, and S. N. Pradhan, “Thermal-Aware Partitioning and Encoding of Power-Gated FSM,” J. of Circ., Sys.and Comp., Vol. 28, no. 9, pp. 1950144, 2018.

[27] M. Pedram, and S. Nazarian, “Thermal modeling, analysis, and management in VLSI circuits: Principles and methods,”in Proc. of the IEEE, Vol. 94, no. 8, pp. 1487-1501, Sept. 2006.

[28] L. Shang, and R.P. Dick, “Thermal crisis: challenges and potential solutions,” IEEE Potentials, Vol. 25, no. 5, pp. 31-35, Sept. 2006.

[29] R. E. Ladner, “On the structure of polynomial time reducibility,” Journal of the ACM, Vol. 22, no. 1, pp. 155-171, Jan. 1975.

[30] W. Huang, S. Ghosh, S. Velusamy, K. Sankaranarayanan, K. Skadron, & M. R. Stan, “HotSpot: A compact thermal modeling methodology for early-stage VLSI design,” IEEE Trans. on Very Large Scale Integration Sys., Vol. 14, no. 5, pp. 501-513, Jul. 2006.

[31] Cadence Innovus Implementation System. Available: https://www.cadence.com/content/dam/cadence-www/global/en_US/documents/tools/digital-design-signoff/innovus-implementation-system-ds.pdf. [last accessed August 2018].

[32] S. N. Pradhan, M. T. Kumar, and S. Chattopdhyay, “AND-OR-XOR Network Synthesis with Area-Power trade-off” Journal of Circ., Sys., and Comp., Vol. 20, no. 06, pp. 1019-1035, 2011.

[33] K. Deb, A. Pratap, S. Agarwal and T.A.M.T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. on Evo. Comp. Vol. 6, no. 2, pp. 182-197, Apr. 2002.

[34] S. Chaudhury, S. Chattopadhyay, “Output phase assignment for area and power minimization in PLAs,” Journal of Indian Inst. Sci., Vol. 86, pp. 33- 43, Jan-Feb., 2006.

[35] MCNC and LGSynth93 benchmarks. In: Collection of Digital Design Benchmarks [online]. Available: http://ddd.fit.cvut.cz/prj/Benchmarks/. [last accessed September 2018].

[36] S. Chaudhury, and S. Chattopadhyay, “Fixed polarity Reed-Muller network synthesis and its application in AND-OR/XOR-based circuit realization with area-power trade-off,” IETE J. of Resarch, Vol. 54, no. 5, pp. 353-363, Sept. 2008.

[37] A. Das, and S. N. Pradhan, “Thermal-aware Output Polarity Selection Based on And-Inverter Graph Manipulation,” Rec. Adv. in Elec.& Electronic Engg., Vol. 12, no. 1, pp. 30-39, Feb. 2019.

[38] S. N. Pradhan, and S. Chattopadhyay, “Two-level AND-XOR networks synthesis with area-power trade-off,” Int. J. of Comp. Sci. and Net. Sec.,Vol 8, no. 9, pp. 365-375, Sept. 2008.