Formal Verification of Distributed Task Migration for Thermal Management in On-chip Multi-core Systems using nuXmv

Syed Ali Asadullah Bukhari and Faiq Khalid Lodhi,

ali.asadullah@seecs.edu.pkfaiq.khalid@seecs.edu.pk 

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.

Finite-State Machine of the Selected Task Migration Algorithm

Syed Ali Asadullah Bukhari and Faiq Khalid are Post Graduate students of Electrical Engineering at NUST School of Electrical Engineering & Computer Science. They are working on this project in the System Analysis & Verification (SAVE) Lab of NUST-SEECS, under the supervision of Dr. Osman Hasan.