COMPUTER MODELLING & NEW TECHNOLOGIES 2014 18(12B) 500-509 Chen Xiaoming, Liu Yan, Li Renfa
500
Power constraint communication-aware task scheduling in
reconfigurable multiprocessors
Xiaoming Chen, Yan Liu
, Renfa Li
College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, Hunan, China
Received 1 June 2014, www.cmnt.lv
Abstract
Heterogeneous multiprocessors with FPGA component have recently received a lot of attention due to its low cost and power
consumption. However, most of existing works about task scheduling algorithm focus on minimization of system cost or power
consumption. Actually, optimizing multiprocessor performance within a given power budget has recently received a lot of attention.
Peak power consumption should be carefully controlled than directly improve computing performance. Furthermore, FPGA component
in multiprocessors has essential parallelism ability to execute multiple tasks at same time using dynamic reconfigurable features. In
this environment, tasks and communications should be carefully scheduled because their execution orders affect the performance of
the whole chip. This paper presents an Integer Linear Programming (ILP) formulation that integrates the resource delay model and
FPGA-component with pipelined scheduling and global power control. Moreover, to enhance the computation efficiency, a heuristic
algorithm namely PCLS that integrates pipelined scheduling and global power control for heterogeneous multiprocessor architecture
is proposed. Experiments show that our ILP method obtains the optimal results when task nodes are less than 35. Proposed PCLS
heuristic algorithm achieves on average 10% higher makespan compare with DLS. For heavier synthetic task application, PCLS can
provide only about 12% performance degradation under 70% power budgets based on different heterogeneous multiprocessor
architectures.
Keywords: multiprocessors, task scheduling, system-on-chip, power control
1 Introduction
Technology scaling continues to support more transistors
be integrated into a chip and a typical multiprocessor chip
consist of many type of components such as general-
purpose CPU, DSP, FPGA and communication bus. An
important trend in embedded system is the use of
multiprocessor architectures to meet requirements of
applications, such as multiprocessor system-on-chip has
the potential ability to provide some advantages related to
system cost and power. Obtain these improvement
depends on designer make applications match with the
flexible components and configurability features provided
by the multiprocessor platform such as FPGA module.
Generally, as the system becomes larger and complicated,
the performance of the entire system is affected by the
execution order of tasks and communications known as
task mapping and scheduling problem.
Heterogeneous multiprocessor chips have potential to
obtain better area to performance ratio, high throughput
and high speed up. Exploiting inter-core heterogeneity is
challenging as it boils down to mapping tasks to most
appropriate cores and scheduling well suite task start time.
There are some challenges must be faced when solving
task scheduling problem on multiprocessor chips. Firstly,
only a subset of the total available cores used to execute
specific applications and the total number of cores maybe
large and heterogeneity including many kinds of
computing components and resources. Furthermore,
Corresponding author’s-e-mail: liuyan@hnu.edu.cn
hardware-related component such as FPGA can provide
essential ability to execute application parallel. Secondly,
designer needs to solve the task scheduling problem by
determining the execution order of tasks and
communications co-ordinately to run application tasks in a
multiprocessor system efficiently. Thirdly, power
dissipation has become a first-class constraint in current
microprocessor design. Power dissipation increasingly
constrains the design and application of multiprocessors. It
is important to control the peak power of a multiprocessor
chip to allow improved reliability and saved chip cooling
and package cost [1]. As the number of cores integrated in
multi-core processor chip increased, the power budget of
whole chip must be controlled. In other word, compared
with the previously studied power minimization problem,
now important problem is efficiently control the peak
power consumption of a multiprocessor chip to stay below
a desired budget at the same time providing ideal
performance. This paper addresses the problem of task
mapping and scheduling on multiprocessors considers
global power control. A linear program based approach
considering communication cost is proposed to formulate
the pipeline scheduling problem. Further, an efficient
heuristic algorithm named PCLS (Power constrain
Communication aware List Scheduling) is proposed and
validated for task scheduling on power constraint
multiprocessor system.