Particle Swarm Optimization Based Task Scheduling
for Multi-core Systems Under Aging Effect
Jinbin Tu
School of Computer Science and
Engineering
Nanjing University of Science
and Technology
Nanjing, China
116106000707@njust.edu.cn
Tianhao Yang
School of Computer Science and
Engineering
Nanjing University of Science
and Technology
Nanjing, China
116106000706@njust.edu.cn
Yi Zhang
School of Computer Science and
Engineering
Nanjing University of Science
and Technology
Nanjing, China
yzhang@njust.edu.cn
Jin Sun
School of Computer Science and
Engineering
Nanjing University of Science
and Technology
Nanjing, China
sunj@njust.edu.cn
Abstract—As the size of the transistor continues to shrink, a
number of reliability issues have emerged in network-on-chip (NoC)
design. Taking into account the performance degradation induced
by Negative Bias Temperature Instability (NBTI) aging effect, this
paper proposes an aging-aware task scheduling framework for NoC-
based multi-core systems. This framework relies on a NBTI aging
model to evaluate the degradation of core’s operating frequency to
establish the task scheduling model under aging effect. Then, we
develop a particle swarm optimization (PSO)-based heuristic to solve
the scheduling problem with an optimization objective of total task
completion time, and finally obtain a scheduling result with higher
efficiency compared with traditional scheduling algorithms without
considering of NBTI aging effect. Experiments show that the
proposed aging-aware task-scheduling algorithm achieves not only
shorter makespan and higher throughput, but also better reliability
over non-aging-aware ones.
Keywords—network-on-chip, negative bias temperature
instability, task scheduling, particle swarm optimization
I. INTRODUCTION
With the rapid growth of the number of IP cores integrated
on a single chip, the on-chip system based on shared bus
architecture is faced with bottlenecks that are difficult to control,
poor communication efficiency and poor scalability. Therefore,
the researchers proposed a network-based and routing-based
network-on-chip (NoC) architecture, so that IP core can
communicate through the network interconnect structure,
implementing the separation of communication and computing
operations[1]. NoC has become an effective solution for future
multi-core system design. On the other hand, As device feature
sizes continue to shrink, long-term reliability or permanent fault
such as Negative Bias Temperature Instability (NBTI) affects
system life-span, and leads to the low yield and short mean-time-
to-failure (MTTF) in multi-core systems[2, 3]. Therefore, it is
increasingly important to take into the consideration of NBTI
aging effect in almost every aspect of NoC design, including
task scheduling, workload balancing, and power management,
etc.
In this multi-core era, task scheduling problem has become
an important research focus, which determines how to map the
tasks of an realistic application onto IP cores to achieve optimal
system performance and efficiency. In general, scheduling
algorithm can be divided into static scheduling and dynamic
scheduling[4]. Static task scheduling is usually done at
compilation time, e.g. list-based algorithm [5,
6], Clustering
Algorithm [7-9] and duplication based algorithms [7, 8]. In
contrast, depending on the dynamic situation of NoC system,
dynamic task scheduling is performed when mapping the tasks
onto corresponding processing elements in real time for
satisfying system requirements. This category of scheduling
methods generally uses heuristic or meta-heuristic strategies to
search for best schedules, such as genetic algorithm (GA) [10]
and ant colony optimization (ACO) [11,
12], dynamic
scheduling algorithm based on task pool [13], particle swarm
optimization (PSO) [14] and dynamic scheduling algorithm
based on real-time constraints[4, 15]. In many scenarios, task
scheduling is proved to be an NP-complete problem. More
importantly, most of existing methods fail to take into account
device aging induced by NBTI effect, and therefore may lead to
considerable degradation in system performance and reliability.
It can be predicted that the aging phenomenon caused by
NBTI effect will become more and more serious as the
integration of chip increases, resulting in a significant difference
in the performance of NoC devices, within the nano-scale NoC
design research in the future, and brings a huge challenge for the
reliability design of the NoC system. If there is no systematic
and effective method to accurately describe and predict
differences in device performance degradation and to design an
effective task scheduling algorithm, it will lead to serious
reliability problems and reduce the operational efficiency of
NoC system. This paper proposes incorporating the NBTI-
induced device performance degradation into the task
scheduling framework, and determines the best mapping
relationships between tasks and aged cores. This aging-aware
scheduling framework relies on a NBTI aging model to evaluate
the degradation of core’s operating frequency to establish the
task scheduling model under aging effect. Then, we develop a
particle swarm optimization (PSO)-based heuristic to solve the
scheduling problem with an optimization objective of total task
completion time, and finally obtain a scheduling result with
higher efficiency compared with traditional scheduling
algorithms without considering of NBTI aging effect.
Experiments show that the proposed aging-aware task
This work was supported by the National Natural Science Foundation of
China (NSFC) under Grant Nos. 61502234 and 71501096, the Natural Science
Foundation of Jiangsu Province of China under Grant Nos. BK20150785 and
BK20161072, the Project funded by China Postdoctoral Science Foundation
under Grant No. 2015M581801, and the Fundamental Research Funds for the
Central Universities under Grant No. 30916011325.
978-1-5386-1978-0/17/$31.00 ©2017 IEEE