Performance-asymmetry-aware scheduling for Chip Multiprocessors with static core coupling

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2010.09.003 Byline: Jianbo Dong (a)(b), Lei Zhang (a), Yinhe Han (a)(b), Guihai Yan (a)(b), Xiaowei Li (a)(b) Keywords: Process variation; Thread-level redundancy; Chip Multiprocessor; Scheduling Abstract: Thread-level redundancy is an efficient approach for transient fault detection and recovery in Chip Multiprocessors (CMPs), in which two adjacent cores are statically coupled to form a functional Dual Modular Redundancy (DMR). Manufacturing process variations cause core-to-core (C2C) performance asymmetry across the chip, which can be further divided into the asymmetry among core-pairs and the asymmetry within a core-pair. We call them inter- and intra-pair asymmetries, respectively, both of which should be taken into considerations in application scheduling for CMPs with static core coupling. In this paper, we first formulate the above scheduling problem as a 0-1 programming problem to maximize the system Weighted Throughput. An efficient IVF&AppSen algorithm is then proposed, which we prove to be optimal when the number of applications equals to that of core-pairs. We also adapt the Simulated Annealing technique to tackle this problem when applications are less than core-pairs on chip. Simulations on a 64-core CMP shows that the proposed algorithms achieve 2.5-9.3% improvement in Weighted Throughput when compared to prior VarF&AppIPC algorithm. Author Affiliation: (a) Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, PR China (b) Graduate University of Chinese Academy of Sciences, Beijing, PR China Article History: Received 13 January 2010; Revised 17 May 2010; Accepted 7 September 2010 Article Note: (footnote) [star] The work was supported in part by National Basic Research Program of China (973) under Grant No. 2011CB302503, in part by National Natural Science Foundation of China (NSFC) under Grant Nos. 60806014, 60831160526, 60633060, 60921002, 61076037, 60906018, and in part by Hi-Tech Research and Development Program of China (863) under Grant No. 2009AA01Z126.