Formal Verification of DTM for Thermal Management in On-chip Multi-core Systems using nuXmv

Faiq Khalid Lodhi , Syed Ali Asadullah Bukhari and Osman Hasan

Abstract

With the growing interest in using distributed task migration algorithms for dynamic thermal management (DTM) in multi-core chips comes the challenge of their rigorous verification. Traditional analysis techniques, like simulation and emulation, cannot cope with the design complexity and distributed nature of such algorithms and thus compromise on the rigor and accuracy of the analysis results. Formal methods, especially model checking, can play a vital role in alleviating these issues. Due to the presence of continuous elements, such as temperatures, and the large number of cores running the distributed algorithms in this analysis, we propose to use the nuXmv model checker to analyze distributed task migration algorithms for DTM. The main motivations behind this choice include the ability to handle the real data type and the scalable SMT based bounded model checking capabilities in nuXmv that perfectly fit the stability and deadlock analysis requirements of the distributed DTM algorithms. The paper presents the detailed analysis of a state-of-the-art task migration algorithm of distributed DTM for many-core systems. The functional and timing verification is done on a larger grid size of 9 x 9 cores, which is thermally managed by the selected DTM approach. The results indicate the usefulness of the proposed approach, as we have been able to catch a couple of discrepancies in the original model and gain many new insights about the behavior of the algorithm.

Methodology

nad

Finite-State Machine of the Selected Task Migration Algorithm

Helpful Material

Publications

  1. S. A. A. Bukhari, F. K. Lodhi, O. Hasan, M.Shafique and J..Henkel, “Formal Verification of Distributed Task Migration for Thermal Management in On-chip Multi-core Systems using nuXmv”, Third International Workshop on Formal Techniques for Safety-Critical Systems (FTSCS 2014), Luxembourg City, Luxembourg, 2014, To Appear.