Thermal-aware Output Polarity Selection Based on And-Inverter Graph Manipulation

Author(s): Apangshu Das*, Sambhu Nath Pradhan

Journal Name: Recent Advances in Electrical & Electronic Engineering
Formerly Recent Patents on Electrical & Electronic Engineering

Volume 12 , Issue 1 , 2019

Become EABM
Become Reviewer
Call for Editor

Graphical Abstract:


Background: Output polarity of the sub-function is generally considered to reduce the area and power of a circuit at the two-level realization. Along with area and power, the power-density is also one of the significant parameter which needs to be consider, because power-density directly converges to circuit temperature. More than 50% of the modern day integrated circuits are damaged due to excessive overheating.

Methods: This work demonstrates the impact of efficient power density based logic synthesis (in the form of suitable polarity selection of sub-function of Programmable Logic Arrays (PLAs) for its multilevel realization) for the reduction of temperature. Two-level PLA optimization using output polarity selection is considered first and compared with other existing techniques and then And-Invert Graphs (AIG) based multi-level realization has been considered to overcome the redundant solution generated in two-level synthesis. AIG nodes and associated power dissipation can be reduced by rewriting, refactoring and balancing technique. Reduction of nodes leads to the reduction of the area but on the contrary increases power and power density of the circuit. A meta-heuristic search approach i.e., Nondominated Sorting Genetic Algorithm-II (NSGA-II) is proposed to select the suitable output polarity of PLA sub-functions for its optimal realization.

Results: Best power density based solution saves up to 8.29% power density compared to ‘espresso – dopo’ based solutions. Around 9.57% saving in area and 9.67% saving in power (switching activity) are obtained with respect to ‘espresso’ based solution using NSGA-II.

Conclusion: Suitable output polarity realized circuit is converted into multi-level AIG structure and synthesized to overcome the redundant solution at the two-level circuit. It is observed that with the increase in power density, the temperature of a particular circuit is also increases.

Keywords: And-inverter graphs, crowding distance, multi-level synthesis, NSGA-II, output polarity selection, pareto-optimal solution, PLA, thermal-aware.

R.K. Brayton, G.D. Hachtel, C.T. McMullen, and A.L. Sangiovanni-Vincentelli, “Logic minimization algorithms for VLSI synthesis”, 1st Ed.; Kluwer Academic Publishers: Springer, 1985., 1985.
S.J. Hong, R.G. Cain, and D.L. Ostapko, "MINI: A heuristic approach for logic minimization", IBM J. Res. Develop., vol. 18, pp. 443-458, 1974.
J. Hlavička, and P. Fišer, "BOOM: A heuristic Boolean minimizer. In", Proc. IEEE/ACM Int. Conf. Comput.-Aided Design San Jose, CA, USA, 2001pp. 439-442
T. Sasao, "Input variable assignment and output phase optimization of PLA’s", IEEE Trans. Comput., vol. 33, pp. 879-894, 1984.
C.L. Wey, and T.Y. Chang, "An efficient output phase assignment for PLA minimization", IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol. 9, pp. 1-7, 1990.
Y. Xu, M. Abd-El-Barr, and C. McCrosky, "Graph-based output phase assignment for PLA minimization", IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol. 14, pp. 613-622, 1995.
R. Hossian, and A. Albicki, "Low power via reduced switching activity and its application to PLAs In", Proc. IEEE Int. ASIC Conf.IEEE Computer Society Press, Rochester, NewYork, , 1994pp. 100-103
S. Chaudhury, and S. Chattopadhyay, "Output phase assignment for area and power minimization in PLAs", J. Indian Inst. Sci., vol. 86, pp. 33-43, 2006.
S.N. Pradhan, and S. Chattopadhyay, "Sub-function polarity selection of PLAs with area-power trade-off In:", Proc. Int. Conf. on Systemics Cybernetics and Informations Hyderabad, India, 2008
N. Mahadevamurty, and F.N. Najm, "“High-level area and power estimation for VLSI circuits”, IEEE Transact. Comput.-Aided Design Integrat. Circuit", Syst., vol. 18, pp. 697-713, 1999.
S. Gupta, and F.N. Najm, "“Power modeling for high-level power estimation”, IEEE Transact. Very Large Scale Integrat. (VLSI)", Syst., vol. 8, pp. 18-29, 2000.
L. Shang, and R.P. Dick, "Thermal crisis: Challenges and potential solutions", IEEE Potentials, vol. 25, pp. 31-35, 2006.
A. Das, A. Debnath, and S.N. Pradhan, "Area, power and temperature optimization during binary decision diagram based circuit synthesis In:", IEEE International Conference on Devices for Integrated Circuit (DevIC) Kalyani, India, 2017pp. 778-782
The Temperature Ratings of Electronic Parts In: Electronics COOLING [online]. 2004. Available at, (Accessed Oct 12, 2017).
K. Sankaranarayanan, S. Velusamy, M. Stan, and K. Skadron, "“A case for thermal-aware floorplanning at the microarchitectural level”, J. Instruct.-", Level Parallel., vol. 7, pp. 1-16, 2005.
W. Huang, K. Sankaranarayanan, K. Skadron, R.J. Ribando, and M.R. Stan, "Accurate, pre-RTL temperature-aware design using a parameterized, geometric thermal model", IEEE Trans. Comput., vol. 57, pp. 1277-1288, 2008.
M. Pedram, and S. Nazarian, "Thermal modeling, analysis, and management in VLSI circuits: Principles and methods", Proc. IEEE, vol. 94, pp. 1487-1501, 2006.
R. Brayton, and A. Mishchenko, “ABC: An academic industrial-strength verification tool”, Comput. Aided Verif., Springer Berlin Heidelberg, 2010, pp. 24-40.
S.B. Akers, "Binary decision diagrams", IEEE Trans. Comput., vol. 100, pp. 509-516, 1978.
K. Deb, A. Pratap, S. Agarwal, and T.A.M.T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II", IEEE Trans. Evol. Comput., vol. 6, pp. 182-197, 2002.
" HotSpot tool. In: HotSpot [online]. 2015. Available at: (Accessed Sep 20, 2017). ",
A. Mishchenko, S. Chatterjee, and R. Brayton, Integrating logic synthesis, technology mapping, and retiming In Proc. IWLS'05,
A. Das, and S.N. Pradhan, "Shared reed-muller decision diagram based thermal-aware AND-XOR decomposition of logic circuits", VLSI Des., vol. 2016, pp. 1-14, 2016.
A. Das, S.R. Choudhury, B.K. Kumar, and S.N. Pradhan, "An elitist area-power density trade-off in VLSI floorplan using genetic algorithm In", 7th IEEE International Conference on Electrical & Computer Engineering (ICECE) Dhaka, Bangladesh, 2012pp. 729-732
A. Das, and S.N. Pradhan, "Thermal aware FPRM based AND-XOR network synthesis of logic circuits In", 2nd IEEE International Conference on Recent Trends in Information Systems (ReTIS) Kolkata, India, 2015pp. 497-502
A. Das, and S.N. Pradhan, "Thermal aware output polarity selection of programmable logic arrays In:", IEEE International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV) Shillong, India, 2015pp. 68-71
"P. Choudhury, and S.N. Pradhan, “Thermal aware power gated design”, In: IET 5th International Conference on Advances in Recent Technologies Communication and Computing (ARTCom), Bangalore, India, 2013, pp. 126-130",
P. Choudhury, D. Nath, V. Rai, and S.N. Pradhan, "Thermal aware AND-OR-XOR network synthesis In: IEEE 19th International Symposium on VLSI Design and Test (VDAT), Ahmedabad, India, 2015, pp. 1-6. ",
E.M. Singh, S.K. Jit, L.L.C.M.R. Murgai, and R.K.B.A. Sangiovanni-Vincentelli, "SIS: A System for sequential circuit synthesis", University of California, Berkeley 94720, (1992), 4. Available at: ERL-92-41.pdf.
K. Skadron, M.R. Stan, W. Huang, S. Velusamy, K. Sankaranarayanan, and D. Tarjan, "Temperature-aware computer systems", Opportunit. Chall. IEEE Micro, vol. 23, pp. 52-61, 2003.
"W.L. Hung, Y. Xie, N. Vijaykrishnan, C. Addo-Quaye, T. Theocharides, M.J. Irwin, “Thermal-aware floor planning using genetic algorithms”, In: IEEE. 6th International Symposium on Quality of Electronic Design (ISQED), San Jose, CA, USA, 2005, pp. 634-639",

Rights & PermissionsPrintExport Cite as

Article Details

Year: 2019
Published on: 10 January, 2019
Page: [30 - 39]
Pages: 10
DOI: 10.2174/2352096511666180320120016
Price: $25

Article Metrics

PDF: 13