# Scheduling Chained Multiprocessor Tasks onto Large Multiprocessor System

T. K. Agrawal, R, Sharma, M. Ghose, A. Sahu
Department of Comp. Sc & Engg., IIT Guwahati,
Guwahati, Assam, India, PIN-781039. email:{tarun.k, r.sharma, g.manojit,
<EMAIL_ADDRESS>

###### Abstract

In this paper, we proposed an effective approach for scheduling of
multiprocessor unit time tasks with chain precedence on to large
multiprocessor system. The proposed longest chain maximum processor scheduling
algorithm is proved to be optimal for uniform chains and monotone (non-
increasing/non-decreasing) chains for both splitable and non-splitable
multiprocessor unit time tasks chain. Scheduling arbitrary chains of non-
splitable multiprocessor unit time tasks is proved to be NP-complete problem.
But scheduling arbitrary chains of splitable multiprocessor unit time tasks is
still an open problem to be proved whether it is NP-complete or can be solved
in polynomial time. We have used three heuristics (a) maximum criticality
first, (b) longest chain maximum criticality first and (c) longest chain
maximum processor first for scheduling of arbitrary chains. Also compared
performance of all three scheduling heuristics and found out that the proposed
longest chain maximum processor first performs better in most of the cases.

##  1 Introduction and Motivation

Modern computing system contains multiple cores which enable many applications
or tasks to execute concurrently. Chip multiprocessor exploits the increasing
device density in a single chip, so now a days we expects two or three order
number of cores on a chip. Also most of the applications by nature they are
parallel and their run time characteristics exhibit time varying phase
behavior [1, 2]. Applications impose different performance metric values in
different phases. During a phase an application have same value of performance
metrics. In [3, 5], Banerjee $et~{}al.$ used instruction per cycle (IPC),
instruction level parallelism (ILP) and L1 cache hits to detect phases of
applications execution time. As different phases of application have different
parallelism and memory access characteristics scheduling algorithm should
consider this fact to improve the performance, otherwise system will be
underutilized. In this work, we have considered the parallelism
characteristics of different phases of an application to schedule efficiently.
Without loss of generality, we can consider an application consist of a
sequence of task or phase, where each task or phase exhibit different degree
of parallelism. In this text, we have used task and phase interchangeably.
Tasks that require more than one processor at a time are called multiprocessor
tasks. Tasks requiring $k$ processors at a time are called $k$-width tasks.

In this paper we are concerned about scheduling of $N$ multi-phase
applications (chain of multiprocessor tasks, each of which have arbitrary
number of phases or tasks) onto $M$ processor system. Each phase or task has
two characteristics: one is execution time of phase and other is number of
processors required for execution of that phase. A phase of an application can
be scheduled on any subset of processors of given size (given by phase). So
this kind of application can be represented as collection of multiprocessor
task with chain precedence constraints. Interchangeably we say this as chain
of multiprocessor task throughout this paper. If execution time of a
multiprocessor task is 1 then we say it is a multiprocessor unit time task and
for multiprocessor unit time task we don’t use pre-exemption. A task is
splitable multiprocessor unit time task with k-width, means this task may be
run in splitable in term of processor. Suppose a task require $1$ unit time
$p$ processor then this task may execute $1$ unit on $d$ processor in current
time slot and remaining $p-d$ unit in any other time slots. If $d$ is integer
then task is unit splitable otherwise continuous splitable task. In this
paper, we have tried to link theoretical aspect of multiprocessor scheduling
and efficient scheduling multi-phase application on to multiprocessors to cope
up with modern days execution environment scenario (parallel multi-phase
application on large multi-processor system).

Non-preemptive scheduling of $N$ independent tasks (uni-processor task) on
$M\geq 3$ processors is NP-complete. Similarly, the problem of multiprocessor
tasks scheduling is NP-Hard for non-preemptive case and independent tasks of
arbitrary execution time [4]. If the execution time of each phase is
restricted to unit time then the problem is polynomially solvable for
arbitrary but fixed number of processor requirement case [4]. When preemption
is allowed we can solve independent tasks of arbitrary execution time with
arbitrary number of processors requirements in polynomial time [4]. Most of
the cases, if we add precedence constraint between tasks difficulty increases.
Scheduling multiprocessor applications which have precedence constraint as
directed acyclic graphs is NP-Complete. Many heuristics are proposed to
schedule them. We are considering precedence constraint chain in this paper
which is simplest precedence constraint. The problem scheduling multiprocessor
task with chain precedence is also strongly NP-Hard for than two processors
and non pre-emptable tasks of arbitrary execution time [4]. If execution time
is restricted to unit for chained applications then also the problem is
strongly NP-Hard for three processors with arbitrary processors requirement of
multiprocessor task [4].

In this paper we are considering three types of chains of multiprocessor unit
time task. These are (a) uniform chain, (b) monotonically increasing or
decreasing chains and (c) arbitrary chains. We are considering two types of
multiprocessor tasks also. These are (a) splitable tasks, and (b) non-
splitable tasks. Non-splitable task require all required processors
simultaneously at a time means $k$-width task can not be scheduled on $<$ $k$
processors and splitable task can be processed by allocating partial number of
processors at different times means $k$-width task can be scheduled on
processors less than $k$ at a time and remaining can be given on next time.
Our result is stronger result as compared to Blazewicz $et~{}al.$ [10], where
they consider scheduling of tasks requiring an arbitrary number of processors
between $1$ and $k$, where $k$ is fixed integer and unit time processing. Also
we have considered splitable and non-splitable version of the problem.

Rest of the paper is organized as follows: We have described the problem
formulation and variation of problem in Section 2. We have described previous
work in Section 3. We have described our proposed algorithm for scheduling of
uniform chains of splitable and non-splitable multiprocessor unit time tasks
in Section 4. Similarly, we have described algorithm for scheduling of
monotone chains of splitable and non-splitable multiprocessor unit time tasks
in Section 5. Section 6 describes about compared three heuristics to solve the
problem of scheduling arbitrary multiprocessor task chains and evaluates their
performance on various scenarios for both splitable and non-splitable task
chains. Finally, we have concluded about paper and pointed future works in
Section 7.

##  2 Problem Formulation

###  2.1 Scheduling of multiprocessor tasks on $M$ processor system with chain
constraint

A collection of $N$ application $C$ = $C_{1}$,$C_{2}$,….,$C_{N}$ has to be
executed by $M$ identical processors. Each application or chain consists of
$n_{i}$ phases or tasks where $i\in[1,2,..N]$. The processors requirement of
task $T_{ij}$ is $p_{ij}$, where $T_{ij}$ is $j^{th}$ phase or task of
application $C_{i}$ and it satisfies $1<p_{ij}\leq M$. Execution time $t_{ij}$
of each tasks $T_{ij}$ may be arbitrary. Figure 1(a) shows an example of
application system. In this example, we have 4 applications or chains
($C_{1}$, $C_{2}$, $C_{3}$ and $C_{4}$). Application $C_{1}$, $C_{2}$, $C_{3}$
and $C_{4}$ have 4 phases, 3 phases, 5 phases and 4 phases respectively. A
task of an application can’t start execution before complete execution of its
predecessor task of the same application.

An optimization criterion of multiprocessor scheduling is minimizing makespan
time $C_{max}$. The makespan is defined as the total length of the schedule
i.e. when all tasks of all applications are finished i.e.
$C_{max}=\smash{\displaystyle\max_{0\leq i\leq N}}\\{F_{i}\\}$ where $F_{i}$
is the finishing time of $i^{th}$chain or application.

(a) Arbitrary time

(b) Unit time

Figure 1: Multiprocessor tasks with chain precedence

The problem of scheduling of multiprocessors arbitrary time tasks with chains
is NP-complete, so for simplicity we assume execution time of each tasks
$T_{ij}$ equal to unit length i.e. $t_{ij}$ = $1$ where $i$ = $1$ to $N$ and
$j$ = $1$ to $n_{i}$, in this paper. We also assume that there is no
communication delay between tasks of an application and among the
applications. In the paper, we have used $n$ as total number of tasks (which
is different from $n_{i}$, the number of phases of application $C_{i}$) and
$m$ or $M$ as number of processor in the system.

###  2.2 Considered types of multiprocessor tasks

In this paper, we have assumed two types of tasks: (a) Non-splitable tasks
i.e. task can only be processed when all the required number of processor by
task are allocated to task at a time and (b) splitable tasks i.e. task can be
processed by allocating all required number of processor in pieces at
different time. Clearly, we can categorize the multiprocessor unit time tasks
with chain precedence into three following cases:

  1. 1.

Uniform chains: All the tasks of a chain have same number of processors
requirement and tasks of different chains may have different processors
requirement. Example of this kind of task system is shown in Figure 2(a). For
a given chain, all the task have same number of parallelism or processor
requirement, but this may be different for different chain.

(a) Uniform

(b) Decreasing

(c) Increasing

(d) Arbitrary

Figure 2: Multiprocessor unit time tasks with chain precedence

  2. 2.

Monotone chains: All the tasks of a chain have non-increasing (or non-
decreasing) processor requirement. All the chains of task system are one type
of chain either non-increasing or non-decreasing. Figure 2(b) and 2(c) shows
non-increasing and non-decreasing monotone chains of multiprocessor tasks
respectively. Considered monotone task system does not contain mix of both
non-increasing and non-decreasing chain.

  3. 3.

Arbitrary Chains: In this case, tasks of a chain have any arbitrary processors
requirement in arbitrary order as shown in Figure 2(d).

We have discussed scheduling approach of all three types of chains of
multiprocessor tasks (uniform, monotone and arbitrary) and also with both
types of multiprocessor tasks (splitable and non-splitable). So it becomes in
total six different types of chain of multiprocessor task system. We know that
lower bound (LB) of makespan time of scheduling chains of multiprocessor task
on multiprocessor can be calculated as [24]

$LB=\max\Big{(}\frac{\sum_{i=1}^{N}\sum_{j=1}^{n_{i}}p_{ij}}{M},max\\{n_{i}\\}\Big{)}$
(1)

where $p_{ij}$ is processor requirement of $j^{th}$ task of $i^{th}$
application, $N$ is number of chain, $M$ is number of processor and $n_{i}$ is
number of phase/task of $i^{th}$ chain. Let us assume OPT is optimal makespan
time produced by an optimal algorithm. So makespan time of any arbitrary
algorithm will be $LB+P_{waste}$ and it will satisfy the following relation.

$LB\leq OPT\leq LB+p_{waste}$ (2)

where $p_{waste}$ is minimum average CPU time wastage. Average CPU time
wastage is calculated as ratio of total CPU time wastage and total number of
processor ($M$). CPU time wastage at any time slot is the number of number of
free processor at that time unit. Wastage of CPU time happens because of these
following reasons.

  1. 1.

Some processors may be free at one time slot because the remaining processors
are not sufficient for any ready task (processor requirement of ready tasks is
higher than the available free processors).

  2. 2.

Some processors may be free if the total requirement of all ready tasks is
less than the total available processors at any one of the time slot.

##  3 Previous Work

###  3.1 Scheduling task on multiprocessor

As described in Section 1, non-preemptive scheduling of independent tasks on
$m\geq 3$ processors is NP-complete. Also, the problem of scheduling a finite
set of tasks having some precedence constraint on finite set of multiprocessor
with goal of minimizing makespan is NP-complete for most of the cases except
for a few simplified cases. Many heuristics with polynomial-time complexity
have been suggested based on their assumptions about the structure of the
parallel program and the target parallel architecture [12]. These assumptions
includes (a) uniform task execution times, (b) zero inter-task communication
times, (c) contention-free communication, (d) full connectivity of parallel
processors, and (e) availability of unlimited number of processors.
However these assumptions may not hold in real world for a number of reasons.
Even after making above assumptions, scheduling problem is NP-complete in
these following cases [12] : (a) scheduling tasks with uniform weights to an
arbitrary number of processors and (b) scheduling tasks with weights equal to
one or two units to two processors.

As stated in [12] there are only three special cases for which there exist
optimal polynomial time algorithms. These cases are (a) scheduling tree-
structured task graphs with uniform node weights on arbitrary number of
processors in linear time by Hu’s [15] highest level first heuristics, (b)
scheduling arbitrary task graphs with uniform node weights on two processors
in quadratic time by Graham et. al. [14], (c) scheduling an interval ordered
task graph with uniform node weights to an arbitrary number of processors have
been solved in linear time by Papadimitriou et. al. [11]. However, even in
these cases, communication among tasks of the parallel program is assumed to
take zero time. In [17], Ullman proved that DAG scheduling problems where
considered DAG’s nodes have unit weights and system has $m$ processors are NP-
complete. He also proved that DAG scheduling problem where nodes have either
one or two as a weight value and system has two processors is also NP-
complete. Figure 3, shows complexity of scheduling problems without
communication time between tasks in tabular form.

Structure | Uniprocessor Tasks | Unit time multiprocessor tasks
---|---|---
(Processing time) | (Processor Requirement)
Unit | Arbitrary | Arbitrary | Unit | Arbitrary | Arbitrary
| (Non-pre | (Preem- |  | (Non-spl | (Split
| emptive) | ptive) |  | itable) | able)
DAG | NPC | NPC | NPC | NPC | NPC | OPEN
|  Ullman[17] | [17] | [26] | [26] |  Bz[4] |
Tree | $O(n)$ | NPC | $n\log n$ | $O(n)$ | NPC | OPEN
|  Hu[4] | [24] | [9] | Hu |  Bz[4] |
Chain | $O(n)$ | NPC | $n+m\log n$ | $O(n)$ | NPC | OPEN
|  Hu [4] | [26] | [9] |  Hu[4] |  Bz[4] |
Indepe- | $O(n)$ | NPC | $O(n)$ | $O(n)$ | NPC, | NPC
ndent |  |  | [26] |  |  Bz[10] |  Bz[10]
Figure 3: Complexity of scheduling problems on P processors without
communication time between tasks

###  3.2 Scheduling multiprocessor task on multiprocessor

The problem of scheduling multiprocessor tasks on multiprocessor is even more
harder. Blazewicz $et~{}al.$ [4], proposed $O(n\log n)$ time algorithm for
chained multiprocessor tasks where processor requirement is uniform for each
task in a chain, where $n$ is number of task and $m$ is number of processor.
They proposed $O(n\log n)$ algorithm for same type of applications with
processor requirement in either increasing or decreasing fashion in a chain
but having only two types of tasks either requiring $1$ processor or $k$
processor. Gonzalez $et~{}al.$ [9], proposed a polynomial time preemptive
algorithm for scheduling trees in $O(n\log m)$ time in off-line mode.
Algorithm given by them solves forests of $n$ tasks onto $m$ identical
processors by minimizing the number of preemption in worst case. Blazewicz
$et~{}al.$ [7], proposed scheduling algorithm for independent processor tasks.
They divided the tasks into two sets $t-type$ sets and $w-type$ sets. $t$-type
tasks are those tasks which require one arbitrary processor for execution and
$w$-type are those which require two arbitrary processors. The non preemptive
version of scheduling $t$ and $w$ types tasks is NP-complete but in this
preemptive version is given which schedules $t$ and $w$ tasks in $O(n\log m)$
time. Blazewicz $et~{}al.$ [10] proposed linear time algorithm for scheduling
tasks requiring an arbitrary number of processors between $1$ and $k$, where
$k$ is fixed integer and unit time processing. If $k$ is not fixed than
problem is NP-complete. They considered both preemptive and non preemptive
versions for two types of problem sets. One is if there are only two types of
tasks in the set, one requiring $1$ processor and other requiring $k$
processors then both non preemptive version and preemptive version take $O(n)$
time to schedule the tasks. Second is if tasks require arbitrary number of
processors between $1$ and $k$ then non preemptive version gives complexity
O$(m^{k-1}.n^{k})$ and preemptive version gives complexity of $O(n^{m})$. Li
$et~{}al.$ [13], proposed a task duplication based scheduling algorithm for
fork-join task graph with complexity of $O(n^{2})$. Blazewicz $et~{}al.$ [8],
proposed a scheduling algorithm for two-processors tasks on uniform
$2$-processor system and schedule $w$ and $t$ types tasks in $O(nm+n\log n)$
time.

##  4 Uniform Chains of Multiprocessor Unit Time Tasks

###  4.1 Splitable multiprocessor tasks

In this section, we propose an optimal algorithm longest chain maximum
processor first (LCMPF) for the minimization of makespan using simple rules.
As shown in algorithm 1 it works on two criteria, first one is length of chain
and second is processor occupancy of task. The application which has longest
chain means maximum number of phases (application length) will first
scheduled. If two or more applications or chains are of same length then the
application which have more number of processor requirement (initial
requirement) of task will be scheduled first. Figure 4(a) shows an example of
uniform chain multiprocessor unit time task system. Initial processor
requirement of chain $C_{1}$, $C_{2}$, $C_{3}$ and $C_{4}$ is $p_{1}$,
$p_{2}$, $p_{3}$ and $p_{4}$ respectively. Total number of phases or tasks in
$C_{1}$, $C_{2}$, $C_{3}$ and $C_{4}$ is $4$, $3$, $5$ and $4$ respectively.

Input: Set of $N$ Application Chains and $M$ Processors.

1: while All chains are not scheduled completely do

2: Sort chains in the non-increasing order of remaining unscheduled chain
length.

3: while at least one processor is free do

4: if there are two or more chains of same unscheduled length then

5: Select next ready task $T_{ij}$ from that chain which has max. proc. req.
(initial req.) in all chains of same length.

6: else Select next ready task $T_{ij}$ from chain with longest unscheduled
length.

7: if Remaining processors m are more than $p_{ij}$ of selected task $T_{ij}$
then

8: Schedule task $T_{ij}$ on Allocated Processors

9: else Schedule task $T_{ij}$ on remaining processors m and make this task as
next ready task for current chain with proc. req. equal to $p_{ij}$-m.

Algorithm 1 Longest Chain Maximum Processor First (LCMPF)

(a) Uniform chains of multiprocessor unit time task

(b) Assuming some values: applications set at time = 1

Figure 4: Example of uniform chains of multiprocessor unit time task

Pseudocode for LCMPF is shown in Algorithm 1. In this example, assuming M =
16, $p_{1}$ = 8, $p_{2}$ = 4, $p_{3}$ = 6 and $p_{4}$ = 10, uniform chain task
system of multiprocessor unit time tasks is shown in Figure 4(b). algorithm
works as follows: initially at time $t=0$, chains in sorted order based on
remaining unscheduled length are $C_{3}$, $C_{1}$, $C_{4}$ and $C_{2}$ and
number of free processors is $16$. So task $T_{31}$ will be scheduled first.
Now, number of remaining free processors is $m=16-6=10$. Now, next longest
chains are $C_{1}$ and $C_{4}$ but initial processor requirement of $C_{4}$
(i.e. $p_{4}$ = 10) is greater than initial processor requirement of $C_{1}$
(i.e. $p_{1}$ = 8), so next task to be scheduled will be $T_{41}$. Now, number
of remaining free processors is $m=10-10=0$ so no task can be scheduled next
in this time slot. As there is no free processor so CPU time wastage in
current time slot ($t=0$) is 0.

Time complexity of this can be analyzed as follows: Sorting chains requires
$O(N\log N)$ time and finding chain which requires maximum initial processors
from longest chains of same length takes $O(N)$ time. For one time slot,
scheduling will take time O($N+N\log N$) time, so total time complexity of
scheduling task system by LCMPF algorithm is $C_{max}$.$(N+N\log N)$, where
$C_{max}$ is constant.

Let us assume length of chain have an upper bound $L$. In this case, instead
of sorting we can use $L$ different bins to put the application with length
$l$ to bin number $l$ where highest bin is $L$, next highest bin is $L-1$ and
so on. This will take $O(N)$ time to put all the applications to bins. If we
want all applications in each bin to be in sorted order based on initial
processor requirement, then process of inserting all applications to bins
requires $O(N\log N)$ time.

Every time slot, we need to take out some applications from the current
highest bin ($L^{{}^{\prime}}$) and get inserted to next highest bin
($L^{{}^{\prime}}-1$). If we want applications in the bins in sorted order
based on initial processor requirement then it will take $O(N)$ time. Let
$\alpha$ be the number of applications get executed in a time slot, then we
need to do maximum $\alpha$ applications to be removed from current highest
bin ($L^{{}^{\prime}}$) to next current highest bin $(L^{{}^{\prime}}-1)$. So
time complexity of this operation will be $O(\alpha+\beta)$, where $\beta$ is
the number of applications already in next current highest bin
$(L^{{}^{\prime}}-1)$. Overall time complexity of algorithm will be $O(N\log
N)+C_{max}.(\alpha+\beta)$.

######  Theorem 4.1.

Longest chain maximum processor first algorithm always gives optimal makespan
time for uniform chains with splitable tasks.

###### Proof.

We always try to use all the processors at all the time slots to make
$p_{waste}$ minimum. CPU time wastage happens when the total number of
processor requirement of all the ready tasks in a particular time slot is less
than $M$. Optimality of LCMPF is shown as result of proof of Lemma 4.2 and
Lemma 4.3. ∎

######  Lemma 4.2.

Selecting tasks from long chain first will not increase the CPU wastage time
in future time slot.

###### Proof.

Selecting long chain task first reduces the chances of free processors in
future time slots. Let there be an algorithm $A^{{}^{\prime}}$ which gives the
optimal makespan time $T^{{}^{\prime}}$ and our approach LCMPF is giving
makespan time $T$. As from equation (1) lower bound of makespan $LB$ will be
same in both algorithms. As $A^{{}^{\prime}}$ is optimal, we can say that

$p_{waste}(A^{{}^{\prime}})\leq p_{waste}(LCMPF)$ (3)

where $p_{waste}(A^{{}^{\prime}})$ is average CPU time wastage of algorithm
$A^{{}^{\prime}}$ and $p_{waste}(LCMPF)$ is average CPU time wastage of
algorithm LCMPF.

If our approach selects task from longest chain (let the length of chain is
$l$) then the optimal algorithm $A^{{}^{\prime}}$ select task from any chain
of length $l^{{}^{\prime}}$ where $l^{{}^{\prime}}\leq l$. This will happen
each time and there will be 0 or more number of tasks of an arbitrary
application remaining at last. Assume that two tasks of only application are
remaining at last then the CPU wastage will increase because we can complete
only one task at one time.

Figure 5: Best and worst case behavior of algorithm $A^{{}^{\prime}}$ and
LCMPF

The figure 5 depict the worst case behavior. Assuming $16$ processors, in best
case LCMPF algorithm selects $T_{11}$ first and $A^{{}^{\prime}}$ selects
either $T_{11}$ or $T_{21}$ first. In both cases total CPU time wastage will
be $16-8=8$. In worst case LCMPF selects $T_{11}$ first so total CPU time
wastage will be 16-(1+8) = $7$ only but if $A^{{}^{\prime}}$ selects $T_{21}$
first then total CPU time wastage will be $(16-1)+(16-8)=15+8=23$. So in last
worst case there will be situation in $A^{{}^{\prime}}$ that two phases of an
arbitrary application will remain unscheduled i.e.

$p_{waste}(A^{{}^{\prime}})\geq p_{waste}(LCMPF)$ (4)

So by contradiction, we can say that selecting tasks from long chain first
reduces the CPU time wastage. ∎

######  Lemma 4.3.

Selecting task from highest number of processors requiring (initial
requirement) chain will not increase the CPU time wastage of current time
slot.

###### Proof.

Let there be an optimal algorithm $A^{{}^{\prime}}$ which gives the optimal
makespan time then it will choose the task from the chain which requires
initial processors at least one less than initial processors of task chosen by
our approach LCMPF. If $A^{{}^{\prime}}$ is occupying less processors then
obviously $A^{{}^{\prime}}$ is giving more CPU time wastage then LCMPF. ∎

Our approach LCMPF gives minimum CPU time wastage so it gives optimal makespan
time.

###  4.2 Non-splitable multiprocessor tasks

In this case, our application system consists of N uniform chains of non-
splitable multiprocessor unit time tasks. Non-splitable multiprocessor task
means task can be processed only by giving all the required number of
processor as a whole at that time.

In the Algorithm 2, we are proposing an optimal algorithm for the minimization
of make-span. This algorithm is similar to Algorithm 1 except it does not use
the second criteria (i.e. maximum processor occupancy). If we use LCMPF then
also makespan time will be same for uniform chains having non-splitable
multiprocessor unit time tasks but time complexity will increase because of
second criteria. As soon as we found longest unvisited chain we select the
next ready task of that chain, no matter if there are other chains of same
length with high or less number of processor requirement.

Input: Set of $N$ Application Chains and $M$ Processors.

1: while All chains are not scheduled completely do

2: Sort chains in the non-increasing order of remaining unscheduled chain
length.

3: while Processors are free and at least one chain in unvisited do

4: if only one unvisited chains of same unscheduled length then

5: Select ready task $T_{ij}$ from unvisited chain with longest unscheduled
length.

6: else Select ready task $T_{ij}$ from any chain (or, FCFS basis).

7: if Remaining processors m are more than $p_{ij}$then

8: Schedule task $T_{ij}$ on Allocated Processors

9: else Mark this chain as visited;

10: Mark all chains as unvisited. $T_{sch}=T_{sch}+1$

Algorithm 2 Longest Chain First (LCF)

To demonstrate the working of our scheduling approach, let us consider example
of same set of applications described in Subsection 4.1 and it is shown in
Figure 4(a). Pseudo code for proposed longest chain first (LCF) approach is
shown in Algorithm 2. The algorithm works as follows: initially at time $t=0$,
chains in sorted order based on remaining unscheduled length are $C_{3}$,
$C_{1}$, $C_{4}$ and $C_{2}$ and number of free processors is $16$. So task
$T_{31}$ will first scheduled. Now, number of remaining free processors is
$m=16-6=10$ and next longest unvisited chains are $C_{1}$ and $C_{4}$. We can
schedule ready task from any chain but we will schedule according to first
come first served basis. It will not affect the makespan time, only scheduling
order so next task to be scheduled will be $T_{11}$. Now, number of remaining
free processors is $m=10-8=2$. Next longest unvisited chain is $C_{4}$ but it
has more processor requirement (i.e. $p_{4}$ = 10) than remaining free
processors (i.e. $m$ = 2). Same problem is with $C_{2}$. Now, all the chains
are visited so we can’t schedule any task in current time slot. CPU time
wastage in current time slot ($t=0$) is 2.

If we assume maximum length of chain may be arbitrary, then complexity will be
$C_{max}$ times the sorting time that is $C_{max}.(N\log N)$. But if length of
chains are bounded by $L$ then instead of sorting we can use $L$ different
bins to put the application with length ${}^{\prime}l^{\prime}$ to bin number
${}^{\prime}l^{\prime}$ where highest bin is $L$, next highest bin is $L-1$
and so on. This will take $O(N)$ time to put all applications to bins.

Every time slot, we need to take out some applications from the current
highest bin ($L^{{}^{\prime}}$) and get inserted to next highest bin
($L^{{}^{\prime}}-1$). Let $\alpha$ be the number of applications get executed
in a time slot, then we need to do maximum $\alpha$ applications to be removed
from current highest bin ($L^{{}^{\prime}}$) to next current highest bin
$(L^{{}^{\prime}}-1)$. So time complexity of this operation will be $\alpha$.
Overall time complexity of algorithm will be $O(N)+\alpha.C_{max}$.

######  Theorem 4.4.

Longest chain first algorithm always gives optimal makespan time for uniform
chains with non-splitable multiprocessor unit time tasks.

###### Proof.

Let there be an optimal algorithm $A^{{}^{\prime}}$ which gives schedule
length $C_{max}=OPT$. Suppose the optimal algorithm produces a sequence of
scheduled multiprocessor tasks at time slot $t_{i}$, where $t=1$ to $C_{max}$.
Suppose there are $N$ uniform chains of non-splitable multiprocessor tasks
namely $a-chain$, $b-chain$, $c-chain$, $d-chain$ and etc. with processor
requirement $a$, $b$, $c$, $d$ and etc. as shown in Figure 6.

Figure 6: Uniform chains of non-splitable multiprocessor unit time tasks

The optimal algorithm produces a output sequence of scheduled tasks for
example $1(a,b)$, $2(a,c)$, $3(c,d,a)$, $4(a,d)$………., where $i(j,k,..)$
represents a task from $j$, a task from $k$ and so on are scheduled at time
slot $t=i$. We can see from the scheduled sequence that between a nearby pair,
scheduled slot may be exchanged. For an example, $1(a,b)$ and $2(a,c)$ can be
exchanged without affecting the optimality and precedence constraint to
$2(a,b)$ and $1(a,c)$. So in this way, we can sort the scheduling sequence by
$A^{{}^{\prime}}$ to get the required scheduling sequence by LCF. ∎

As optimal sequence can be converted to LCF sequence without changing
$C_{max}$, so our LCF is optimal. But we can’t guarantee that LCF is the only
algorithm which produces optimal result. There may be other algorithm that may
produce optimal result.

##  5 Monotone chains of multiprocessor unit time tasks

Non-increasing chains of multiprocessor unit time tasks can be scheduled
optimally. Our proposed approaches LCMPF (Algorithm 1) and LCF (Algorithm 2)
will produce optimal makespan time for non-increasing chains of splitable and
non-splitable multiprocessor unit time tasks respectively. An example of non-
increasing chains of multiprocessor unit time tasks is shown in Figure 2(b).
Optimality of LCMPF and LCF for non-increasing chains of splitable and non-
splitable multiprocessor unit time tasks respectively can be proved by Theorem
5.2 and Theorem 5.

######  Theorem 5.1.

LCMPF algorithm schedules non-increasing chains of splitable multiprocessor
unit time tasks optimally.

###### Proof.

As shown in Theorem 4.4, $P_{waste}$ by longest chain maximum processor first
is minimum for uniform chains of multiprocessor unit time tasks. As we are
choosing maximum processor first if chain lengths are same and this satisfy
both uniform chains and non-increasing chains. So it is obvious that choosing
maximum processor task of a chain will choose the task with highest processor
requirement of the chain which is the ready task of the chain. As the
subsequent tasks of chain require less number of processor then the
$P_{waste}(LCMPF)$ of current slot will be minimum and also maintains the
$C_{max}$ to be optimal. ∎

######  Theorem 5.2.

LCF algorithm schedules non-increasing chains of non-splitable multiprocessor
unit time tasks optimally.

###### Proof.

As shown in Lemma 4.2, scheduled sequence given by an optimal algorithm
$A^{{}^{\prime}}$ can be converted into scheduled sequence given by LCF
without affecting optimality of makespan in case of uniform chains. Same can
be done in case of non-increasing chain without affecting the optimality. ∎

An example of non-decreasing chains of multiprocessor unit time tasks is shown
in Figure 2(c). This type of chain can also be scheduled for both types
(splitable and non-spilitable) of task same as uniform chains. LCMPF and LCF
will give optimal make-span time for non-decreasing chains of splitable and
non-splitable multiprocessor tasks respectively. Optimality of LCMPF and LCF
for non-decreasing chains of splitable and non-splitable multiprocessor unit
time tasks respectively can be proved by Theorem 5.3 and Theorem 5.4.

######  Theorem 5.3.

LCMPF algorithm schedules non-decreasing chains of splitable multiprocessor
unit time tasks optimally.

###### Proof.

Non-decreasing chains of multiprocessor unit time tasks can be formed by
reversing the order of non-increasing chain. Reversing the chain order does
not increase the chain length and it can be scheduled optimally by LCMPF. Non-
decreasing chains are just opposite chains of non-increasing chains. Let the
schedule order $D$ we get is $a_{1}$, $a_{2}$, $a_{3}$ and $a_{4}$ of non-
decreasing chains. If we reverse the chains and schedule them as non-
increasing chains then the order of tasks for scheduling we will get the
opposite of $D$, and that is $a_{4}$, $a_{3}$, $a_{2}$ and $a_{1}$. As
schedule for non-increasing chains is optimal, we can say that schedule for
non-decreasing is also optimal. ∎

######  Theorem 5.4.

LCF algorithm schedules non-decreasing chains of non-splitable multiprocessor
unit time tasks optimally.

###### Proof.

As shown in Theorem 5.3, non-decreasing chain can be converted into non-
increasing chains by reversing order. LCF gives optimal solution for non-
increasing chains so we can say schedule by LCF for non-decreasing chains of
non-splitable multiprocessor unit time tasks will also be optimal.
∎

##  6 Arbitrary Chains of multiprocessor unit time tasks

###  6.1 Non-splitable tasks

In this we are considering system of application of non-splitable
multiprocessor unit time tasks with arbitrary number of processor requirement
in each phase of a chain. Unlike the processor requirement of multiprocessor
task of uniform chains or monotone chains where are same or in non-increasing
(or non-decreasing) order. Figure 2(d) shows an example of arbitrary chains of
multiprocessor unit time tasks. As the tasks are multiprocessor unit time
tasks and non-splitable in terms of processor, this problem is proved to be a
hard problem [4].

We have used three heuristics for this problem and compared the performance.
The proposed heuristics are (a) maximum criticality first (MCF), (b) longest
chain maximum criticality first (LCMCF), and (c) longest chain maximum
processor first (LCMPF). Longest chain maximum processor first heuristic is
described in Section 4.1.

As defined in [15], we level each multiprocessor task of chain with its
criticality value, which is sum of processor requirement of self and all of
its successors. The criticality of task $T_{ij}$ is calculated as

$CV_{ij}=\sum_{k=j}^{k=n_{i}}p_{ik}$ (5)

where $CV_{ij}$ is the criticality of $j^{th}$ task of $i^{th}$ chain,
$p_{ik}$ is processor requirement of task $T_{ik}$ and $n_{i}$ is number of
phases or tasks of $i^{th}$ chain. Figure 7 shows calculated criticality value
of tasks of a example chain and now every task have one more parameter that is
$CV_{ij}$.

Figure 7: Criticality of tasks of chain

Pseudocode for MCF heuristic is shown in Algorithm 3. Initially, it calculates
the criticality value (using equation 5) of tasks of all applications. In
every scheduling step, it try to select subset of tasks from set of ready
tasks to schedule that gives the maximum criticality value with total number
of processors in the subset of ready tasks is less then $M$. If ready task of
$i^{th}$ chain is $T_{ir}$ and its criticality value is $CV_{ir}$ and
processor requirement is $p_{ir}$ then we need to select a subset $S$ from the
ready tasks so that the following objective meets

$max(\sum_{T_{ir}\in S}CV_{ir})\>\>\>with\>\>\>\sum_{T_{ir}\in S}p_{ir}\leq M$
(6)

This is similar to solving 0-1 knapsack problem.

Input: Set of $N$ Application or Chains and $M$ Processors.
Output: Schedule for application’s tasks.

1: Calculate criticality for each task of each application.

2: Initialize ready queue with the first task of all applications

3: while All chains are not scheduled or ready queue is not empty do

4: Select subset from ready tasks that gives maximum criticality and which has
total processor requirement less than or equal to M.

5: Update ready queue with the ready tasks(i.e. whose previous tasks have been
scheduled).

Algorithm 3 Maximum criticality first scheduling (MCF)

Pseudo code for LCMCF is shown in Algorithm 4. It is similar to LCMPF except
the difference between second criteria of selection in choosing ready tasks.
LCMPF chooses the ready task with maximum processor while LCMCF chooses the
task with maximum criticality.

Input: Set of $N$ Application or Chains and $M$ Processors.
Output: Schedule for application’s tasks.

1: Calculate criticality for each task of each application.

2: while All chains are not scheduled do

3: Sort chains in the decreasing order of remaining unscheduled chain length.

4: while Processors are free and at least one chain is unvisited do

5: if There are two or more unvisited chains of same length then

6: Select ready task $T_{ij}$ which has maximum criticality among all ready
tasks of unvisited longest chains .

7: if There are two or more tasks of same criticality then

8: Select any task.

9: else

10: Select ready task $T_{ij}$ from longest and unvisited chain.

11: if Remaining processors $m$ are more than $p_{ij}$ then

12: Schedule task $T_{ij}$ on allocated Processors

13: else

14: Mark this chain as visited

15: Mark all chains as unvisited

Algorithm 4 Longest Chain Maximum Criticality First (LCMCF)

Figure 8 shows the set of 5 arbitrary applications with non-splitable
multiprocessor unit time tasks. Second parameter in each task of each chain is
the criticality of that task calculated by equation 5. Assuming 20 processors,
lower bound (LB) for the example task system will be $\simeq 8$. Scheduled
outputs of all three proposed heuristics for set of applications (Figure 8)
are shown in Figure 9 in tabular form. For this set of applications, all three
heuristics give same makespan time $C_{max}=9$ and total CPU time wastage
equals to 21 (and $p_{waste}=21/20=1.05\simeq 1$) but different set of tasks
are scheduled in a time slot.

Figure 8: Chain of non-splitable multiprocessor tasks with criticality values Time | MCF output | LCMCF output | LCMPF output
---|---|---|---
At time t = 0 |  $T_{11}$, $T_{31}$, $T_{41}$ |  $T_{31}$, $T_{41}$, $T_{51}$ |  $T_{31}$, $T_{41}$, $T_{51}$
At time t = 1 |  $T_{32}$, $T_{42}$, $T_{51}$ |  $T_{32}$, $T_{42}$, $T_{52}$ |  $T_{21}$, $T_{52}$
At time t = 2 |  $T_{21}$, $T_{52}$ |  $T_{21}$, $T_{53}$ |  $T_{32}$, $T_{42}$, $T_{53}$
At time t = 3 |  $T_{12}$, $T_{53}$ |  $T_{11}$, $T_{43}$ |  $T_{22}$, $T_{54}$
At time t = 4 |  $T_{43}$, $T_{54}$ |  $T_{22}$, $T_{54}$ |  $T_{32}$, $T_{42}$, $T_{52}$
At time t = 5 |  $T_{33}$, $T_{44}$, $T_{55}$ |  $T_{12}$, $T_{23}$, $T_{55}$ |  $T_{11}$, $T_{43}$
At time t = 6 |  $T_{22}$, $T_{45}$ |  $T_{44}$, $T_{24}$, $T_{56}$ |  $T_{12}$, $T_{23}$, $T_{55}$
At time t = 7 |  $T_{13}$, $T_{23}$ | $T_{13}$ |  $T_{24}$, $T_{44}$, $T_{56}$
At time t = 8 |  $T_{24}$, $T_{56}$ |  $T_{33}$, $T_{45}$ |  $T_{23}$, $T_{45}$
Figure 9: Scheduling results of all three heuristics of task system shown in
Figure 8 on 20 processors

(a) Cmax $L_{MCF}$=9, $L_{LCMCF}$=8 and $L_{LCMPF}$=8)

(b) Cmax $L_{MCF}$=9, $L_{LCMCF}$=10 and $L_{LCMPF}$=9

(c) Cmax $L_{MCF}$=7, $L_{LCMCF}$=7 and $L_{LCMPF}$=8

Figure 10: Performance of MCF, LCMCF and LCMPF on contradictory examples

(a) M = 64, Apps = 100

(b) M = 64, Apps = 1000

(c) M = 512, Apps = 100

(d) M = 512, Apps = 1000

Figure 11: Comparison between MCF, LCMCF and LCMPF

(a) Phase variation = $\pm 10\%$

(b) Phase variation = $\pm 50\%$

Figure 12: Comparison between MCF, LCMCF and LCMPF with variation of phases in
different applications

Among these three heuristics, no one gives best result for all the case. One
heuristic may perform better as compared to other two in some specific case
(lower the $C_{max}$ value, better the result). As shown in Figure 10,
performance of LCMCF and LCMPF is better compare to MCF for application set 1
(shown in Figure 10(a)), performance of MCF and LCMPF is better than LCMCF for
applications set 2 (shown in figure 10(b)) and performance of MCF and LCMCF is
better than LCMPF for application set 3 (shown in Figure 10(c)).

Figures 11a and 11b show the performance of MCF, LCMCF and LCMPF scheduling of
100 and 1000 applications respectively with different number of phases on 64
processor system. Figures 11c and 11d show the performance of same scheduling
approaches of same application set on 512 processors. We observed that:

  1. 1.

For a fixed number of processors, when number of applications increase, the
difference between LB and makespan time decreases i.e. efficiency in time
increases.

  2. 2.

For fixed number of processors and applications, when upper limit of number of
phases an application can have increase efficiency in time increases for all
three heuristics.

  3. 3.

Avgerage ratio of $C_{max}$ and $LB$ will always be better in LCMPF.

Again Figure 12 shows the performance of MCF, LCMCF and LCMPF scheduling of
application system with 10% and 50% variation of number of phases of
applications with one another for 500 applications on 100 processors. Our
observation says that

  1. 1.

For a fixed number of processors and applications, when phase variation, the
difference between LB and makespan time varies i.e. efficiency in time
increases or decreases.

  2. 2.

For fixed number of processors, applications and phase variation, when number
of phases an application can have increase efficiency in time increases for
all three heuristics.

Time complexity of MCF will be the complexity of 0-1 knapsack solution at each
time slot. As problem of 0-1 knapsack can be solved in pseudo-polynomial time
with respect to capacity of knapsack and total number of item, so in our case
it will be $O(NM)$, so total complexity of MCF is $C_{max}.NM$. As described
in Section 4, complexity of LCMCF will be same as complexity of LCMPF.

Overall LCMPF will give better results than MCF and LCMCF for any set of
applications having any number of phases and any number of applications.

###  6.2 Splitable tasks

Scheduling of arbitrary chains of splitable multiprocessor unit time tasks is
an interesting problem. As of our knowledge, no one have found polynomial time
solution and also no one has proved that this problem is NP-Complete. Using
processor as continuous medium which behaves like electrical charge passing
from task to task in the DAG (instead of chain), author of paper [27], solve
this in iterative ways with complexity is $O(e^{2}+ne+I(n+e))$, where $e$ is
the number of edges in the precedence graph and $I$ is the number of
iterations in the algorithm. They use optimality conditions impose by a set of
nonlinear equations on the flow of processing power (processors) and on the
completion times of independent paths of execution which is analogous to
Kirchhoff’s laws of electrical circuit theory. But our main aim is to solve in
using discrete approach.

We have also used the same MCF, LCMCF and LCMPF heuristics to schedule this
kind of application on to multicore. As multiprocessor task are splitable, we
use fractional knapsack in MCF heuristic. Experiment shows all three
heuristics produce exactly same result for randomly generated examples. We
also observe that all three heuristics perform equally if sum of processor
requirement of all the ready multiprocessor tasks is $\geq M$ in all schedule
time slot except the last time slot. If this condition is violated then LCMPF
performed better than other two heuristics.

##  7 Conclusion and Future work

Scheduling with considering the phase behavior improve the system performance.
Our proposed approach LCMPF scheduling of uniform and monotone chain of
multiprocessor unit time task is proved to optimal. If the multiprocessor task
are non-splitable, then LCF approach is optimal, we don’t need to consider
processor occupancy criteria of multiprocessor task.

Scheduling arbitrary chain of multiprocessor unit time task is in NP-complete.
In this case our proposed LCMPF based heuristics perform better as compared to
MCF and LCMCF heuristics. We believe that scheduling of arbitrary chain of
splitable multiprocessor unit time task is still an open problem. We have also
compared performance of proposed LCMPF and other MCF and LCMCF heuristics for
scheduling this kind of task. In future, we are planning to try to solve
scheduling of arbitrary chain of splitable multiprocessor unit time task. Also
solve the same with other restrictive precedence constraints and or with some
communication model.

## References

  * [1] T. Sherwood, S. Sair, and B. Calder, Phase tracking and prediction, ACM SIGARCH Comp. Arch. News, Vol. 31, No. 2, 2003, pp. 336–349.
  * [2] C. B. Cho and T. Li, Complexity-based program phase analysis and classification, in Proc. of PACT, 2006, pp. 105–113.
  * [3] S. Banerjee, G. Surendra, and S. K. Nandy, On the effectiveness of phase based regression models to trade power and performance using dynamic processor adaptation, J. Syst. Archit., Vol. 54, No. 8, 2008, pp. 797–815.
  * [4] J. Blazewicz, Zhen liu, Scheduling multiprocessor tasks with chain constraint, Euro. J of Op. Res., Final version, 1996.
  * [5] Amrutlal D Sueresh and Sahu, A., Scheduling of multi-phase applications on to mesh multicore architecture, IEEE Indicon, Dec 2014.
  * [6] Jianzhong Du and Joseph Y-T. Leung, Complexity of Scheduling Parallel Task Systems, SIAM J. on Dis. Math.., Vol. 2, No. 4, 1989, pp. 473-487.
  * [7] J. Blazewicz, J. Weglarz and M. Drabowski, Scheduling independent 2-processor tasks to minimize schedule length, Info. Proc. Lett., Vol. 18, No. 4, 1984, pp. 267-273
  * [8] J. Błaz̀ewicz, M. Drozdowski, G. Schmidt and D. De Werra, Scheduling independent 2-processor tasks on a uniform duo-processor system, Dis. App. Math., Vol. 28, No. 1, 1990, pp. 11-20.
  * [9] Teofilo F. Gonzalez and Donald B. Johnson, A New Algorithm for Preemptive Scheduling of Trees, J. of ACM, Vol. 27, No. 2, 1980, pp. 287-312.
  * [10] J. Blazewicz, J. Weglarz and M. Drabowski, Scheduling Multiprocessor Tasks to Minimize Schedule Length, IEEE Tran. on Comp., Vol. C-35, No. 5, 1986.
  * [11] C. H. Papadimitriou and M. Yannakakis, Scheduling Interval-Ordered Tasks, SIAM J. Comput., Vol. 8, No. 3, 1987, pp.405-409.
  * [12] Yu-Kwong Kwokand and Ishfaq Ahmad, Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors, ACM Comp. Surveys (CSUR), Vol. 31, No. 4, 1999, pp. 406-471.
  * [13] Qinghua Li, Youlin Ruan, ShidaYang and Tingyao Jiang, An optimal scheduling algorithm for fork-join task graphs, Par. and Dist. Comp., Appl. and Tech., 2003.
  * [14] E.G. Coffman and R.L. Graham, Optimal Scheduling for Two-Processor Systems, Acta Informatica, Vol. 1, 1972, pp. 200-213.
  * [15] T.C. Hu, Parallel Sequencing and Assembly Line Problems, Oper. Res., Vol. 19, No. 6, Nov. 1961, pp. 841-848.
  * [16] M.R. Garey and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
  * [17] J. Ullman, NP-Complete Scheduling Problems, J. of Comp. and Sys. Sc., Vol. 10, 1975, pp. 384-393.
  * [18] R. Sethi, Scheduling Graphs on Two Processors, SIAM J. on Computing, Vol. 5, No. 1, Mar. 1976, pp. 73-82.
  * [19] J. Blazewicz, et al, Scheduling independent multiprocessor tasks on a uniform k-processor system, Par. Comp., Vol. 20, 1994, pp. 15-28.
  * [20] J. Blazewicz and Zhen Liu, Linear and quadratic algorithm for scheduling chains and opposite chains, Euro. J. of Ope. Res., Vol. 137, No. 2, 2002.
  * [21] J. Blazewicz and Daniel Kobler, Review of properties of different precedence graphs for scheduling problems, Euro. J. of Ope. Res., Vol. 142, 2002.
  * [22] Teofilo Gonzalez and Sartaj Sahni, Flowshop and Jobshop Schedules: Complexity and Operation, Op. Res., Vol. 26, No. 1, Jan-Feb. 1978.
  * [23] Teofilo F. Gonzalez and Donald B. Johnson, A New Algorithm for Preemptive Scheduling of Trees, J. ACM, Vol. 27, 1980, pp. 287-312.
  * [24] Peter Brucker, Scheduling Algorithms, Fifth Edition, Springer, 2006.
  * [25] Giorgio C. Buttazzo, Hard Real Time Computing Systems: Predictable Scheduling Algorithms and Applications, Third Edition, Springer, 2011.
  * [26] R. McNaughton, Scheduling with deadline and loss functions, Management Science, 6:1-12, 1959
  * [27] G.N.Srinivasa Prasanna, B.R.Musicus, Generalized multiprocessor scheduling for directed acyclic graphs, Proc. of IEEE Supercomputing, 1994, 237-246.