I
nte
rna
t
io
na
l J
o
urna
l o
f
E
lect
rica
l a
nd
Co
m
p
ute
r
E
ng
in
ee
ring
(
I
J
E
CE
)
Vo
l.
6
,
No
.
6
,
Dec
em
b
er
201
6
,
p
p
.
3
0
1
8
~
30
30
I
SS
N:
2
0
8
8
-
8708
,
DOI
: 1
0
.
1
1
5
9
1
/
i
j
ec
e
.
v
6i
6
.
1
0
1
4
0
3018
J
o
ur
na
l ho
m
ep
a
g
e
:
h
ttp
:
//ia
e
s
jo
u
r
n
a
l.c
o
m/o
n
lin
e/in
d
ex
.
p
h
p
/I
JE
C
E
Trends
i
n Ta
s
k
A
llo
ca
tion
Techniq
ues f
o
r Mul
ticore
Sy
ste
m
s
Arun K
u
m
a
r
S
un
da
r
Ra
j
a
n
1
,
Sh
rira
m
K
Va
s
ud
ev
a
n
2
,
Ni
r
m
a
la
Dev
i M
3
1
,3
De
p
a
rt
m
e
n
t
o
f
El
e
c
tr
o
n
ics
a
n
d
Co
m
m
u
n
ica
ti
o
n
E
n
g
in
e
e
rin
g
,
Am
rit
a
S
c
h
o
o
l
o
f
En
g
in
e
e
rin
g
Co
im
b
a
to
re
,
Am
rit
a
V
ish
w
a
V
id
y
a
p
e
e
th
a
m
,
Am
rit
a
Un
iv
e
r
sit
y
,
In
d
ia
2
De
p
a
rtme
n
t
o
f
Co
m
p
u
ter S
c
ien
c
e
En
g
in
e
e
rin
g
,
Am
rit
a
S
c
h
o
o
l
o
f
En
g
in
e
e
rin
g
Co
im
b
a
to
re
,
Am
rit
a
V
ish
w
a
V
id
y
a
p
e
e
th
a
m
,
Am
rit
a
Un
iv
e
r
sit
y
,
In
d
ia
Art
icle
I
nfo
AB
ST
RAC
T
A
r
ticle
his
to
r
y:
R
ec
eiv
ed
Feb
1
1
,
2
0
1
6
R
ev
i
s
ed
Sep
7
,
2
0
1
6
A
cc
ep
ted
Sep
21
,
2
0
1
6
A
s
th
e
f
u
n
c
ti
o
n
a
li
ty
in
re
a
l
-
ti
m
e
e
m
b
e
d
d
e
d
sy
st
e
m
s
b
e
c
o
m
in
g
c
o
m
p
lex
,
th
e
re
h
a
s
b
e
e
n
a
d
e
m
a
n
d
f
o
r
h
ig
h
e
r
c
o
m
p
u
tatio
n
c
a
p
a
b
il
it
y
,
e
x
p
lo
it
a
ti
o
n
o
f
p
a
ra
ll
e
li
sm
a
n
d
e
ff
e
c
ti
v
e
u
sa
g
e
o
f
th
e
re
so
u
rc
e
s.
F
u
rt
h
e
r,
tec
h
n
o
lo
g
ica
l
li
m
it
a
ti
o
n
s
in
u
n
ip
r
o
c
e
ss
o
r
in
te
rm
s
o
f
p
o
we
r
c
o
n
su
m
p
ti
o
n
,
sa
tu
ra
ti
o
n
in
in
stru
c
ti
o
n
lev
e
l
p
a
ra
ll
e
li
sm
,
d
e
lay
in
a
c
c
e
ss
o
f
m
e
m
o
r
y
b
lo
c
k
s
,
e
tc
.
led
t
o
th
e
e
m
e
rg
e
n
c
e
o
f
m
u
lt
ico
re
.
M
u
lt
ico
r
e
d
e
sig
n
h
a
s
it
s
c
h
a
ll
e
n
g
e
s
a
s
w
e
l
l.
In
c
re
a
se
in
n
u
m
b
e
r
o
f
c
o
re
s
h
a
s
ra
ise
d
th
e
d
e
m
a
n
d
f
o
r
p
ro
p
e
r
lo
a
d
d
istri
b
u
t
io
n
,
p
a
ra
ll
e
li
z
in
g
e
x
isti
n
g
se
q
u
e
n
ti
a
l
c
o
d
e
s,
e
n
a
b
l
in
g
e
f
fe
c
ti
v
e
c
o
m
m
u
n
ica
ti
o
n
a
n
d
sy
n
c
h
ro
n
iza
ti
o
n
b
e
tw
e
e
n
c
o
re
s,
m
e
m
o
r
y
a
n
d
I
/
O
d
e
v
ice
s.
T
h
is
p
a
p
e
r
h
a
d
i
d
e
n
ti
f
ied
a
n
d
c
o
m
p
a
re
d
th
e
d
istri
b
u
ti
o
n
sc
h
e
m
e
s
f
o
r
tas
k
d
istri
b
u
ti
o
n
in
a
m
u
lt
ico
re
e
n
v
iro
n
m
e
n
t
a
n
d
a
ls
o
th
e
a
lg
o
rit
h
m
s
su
it
a
b
le
f
o
r
d
e
c
e
n
tralize
d
tas
k
s
c
h
e
d
u
li
n
g
sc
h
e
m
e
.
In
a
d
d
it
i
o
n
,
t
h
is
p
a
p
e
r
h
a
d
a
d
d
re
ss
e
d
th
e
tec
h
n
iq
u
e
s
o
f
f
o
r
m
u
latin
g
p
a
ra
ll
e
l
tas
k
b
lo
c
k
s
f
ro
m
se
q
u
e
n
ti
a
l
c
o
d
e
.
K
ey
w
o
r
d
:
D
ec
en
tr
alize
d
s
c
h
e
m
e
Glo
b
al
s
ch
e
m
e
Har
d
w
ar
e
s
p
ec
u
lat
io
n
P
ar
titi
o
n
ed
s
ch
e
m
e
R
ea
l ti
m
e
o
p
er
atin
g
s
y
s
te
m
Sch
ed
u
l
in
g
al
g
o
r
ith
m
T
h
r
ea
d
lev
el
p
ar
allelis
m
Co
p
y
rig
h
t
©
2
0
1
6
In
stit
u
te o
f
A
d
v
a
n
c
e
d
E
n
g
i
n
e
e
rin
g
a
n
d
S
c
ien
c
e
.
Al
l
rig
h
ts
re
se
rv
e
d
.
C
o
r
r
e
s
p
o
nd
ing
A
uth
o
r
:
A
r
u
n
K
u
m
ar
Su
n
d
ar
R
aj
an
,
Dep
ar
t
m
en
t o
f
E
lectr
o
n
ics a
n
d
C
o
m
m
u
n
icat
io
n
E
n
g
i
n
ee
r
in
g
,
Am
r
ita
Sc
h
o
o
l o
f
E
n
g
i
n
ee
r
in
g
C
o
i
m
b
ato
r
e
,
Am
r
ita
Vi
s
h
w
a
Vid
y
ap
ee
th
a
m
,
Am
r
ita
Un
iv
er
s
it
y
,
I
n
d
ia.
E
m
ail:
s
_
ar
u
n
k
u
m
ar
@
cb
.
a
m
r
i
ta.
ed
u
1.
I
NT
RO
D
UCT
I
O
N
W
ith
co
n
ti
n
u
o
u
s
i
m
p
r
o
v
e
m
e
n
t
in
s
e
m
ico
n
d
u
cto
r
m
a
n
u
f
a
ctu
r
in
g
tec
h
n
o
lo
g
y
,
e
m
b
ed
d
in
g
m
an
y
p
r
o
ce
s
s
in
g
u
n
it
s
o
n
a
s
in
g
le
c
h
ip
h
as
b
ec
o
m
e
a
f
ea
s
ib
le
tec
h
n
o
lo
g
ical
tr
en
d
.
S
in
g
le
e
m
b
ed
d
ed
ch
ip
w
it
h
m
a
n
y
in
d
iv
id
u
al
p
r
o
ce
s
s
i
n
g
u
n
its
i
s
ter
m
ed
as
m
u
ltico
r
e
an
d
its
u
s
a
g
e
ca
n
b
e
s
ee
n
i
n
m
a
n
y
r
ea
l
ti
m
e
ap
p
licatio
n
s
lik
e
n
u
clea
r
p
o
w
er
p
lan
t
s
,
a
u
t
o
m
o
b
ile
a
n
d
ae
r
o
s
p
ac
e
i
n
d
u
s
tr
y
.
E
m
b
ed
d
ed
s
y
s
te
m
s
w
it
h
m
u
ltico
r
e
ar
e
d
ev
elo
p
ed
w
ith
e
x
p
ec
tatio
n
s
t
o
ac
h
iev
e
h
ig
h
er
p
er
f
o
r
m
a
n
ce
an
d
f
aster
p
ar
allel
ex
ec
u
tio
n
;
b
u
t
th
e
r
ep
lace
m
e
n
t
o
f
s
i
n
g
le
co
r
e
to
a
m
u
l
ti
co
r
e
h
ar
d
w
ar
e
alo
n
e
d
o
es
n
o
t
al
w
a
y
s
g
u
ar
an
tee
th
e
ex
p
ec
ted
h
i
g
h
er
p
er
f
o
r
m
a
n
ce
[1
-
3
]
.
A
lt
h
o
u
g
h
ea
ch
co
r
e
is
an
i
n
d
i
v
id
u
al
p
r
o
ce
s
s
i
n
g
u
n
it
w
it
h
c
ap
ab
ilit
y
to
w
o
r
k
i
n
d
ep
en
d
en
t
l
y
,
h
i
g
h
er
p
er
f
o
r
m
a
n
ce
ca
n
n
o
t
b
e
ac
h
ie
v
ed
u
n
les
s
t
h
er
e
ar
e
s
t
ep
s
to
en
s
u
r
e
p
r
o
p
er
lo
ad
d
is
tr
ib
u
tio
n
a
n
d
s
y
n
c
h
r
o
n
izatio
n
b
et
w
ee
n
co
r
es,
m
e
m
o
r
y
a
n
d
I
n
p
u
t
-
O
u
tp
u
t
d
e
v
ices
ar
e
tak
e
n
in
to
co
n
s
id
er
atio
n
.
L
o
ad
d
is
tr
ib
u
tio
n
is
h
an
d
led
b
y
a
tas
k
d
is
tr
ib
u
to
r
,
w
h
ic
h
w
il
l
b
e
ca
p
ab
le
o
f
av
o
id
in
g
p
r
io
r
ity
i
n
v
er
s
io
n
b
et
w
ee
n
ta
s
k
s
i
n
d
if
f
er
en
t
co
r
es,
lo
n
g
er
w
aiti
n
g
ti
m
e
an
d
u
n
n
ec
ce
s
ar
y
m
is
s
in
g
o
f
ta
s
k
d
ea
d
lin
es.
R
o
les
o
f
a
ta
s
k
d
is
tr
ib
u
to
r
ca
n
b
e
d
iv
id
ed
in
to
2
lev
els
.
First
o
n
d
ec
id
in
g
w
h
ic
h
co
r
e
s
h
o
u
l
d
ex
ec
u
te
th
e
tas
k
.
S
ec
o
n
d
is
o
n
d
ec
id
in
g
t
h
e
ti
m
e
an
d
o
r
d
er
o
f
th
e
task
ex
ec
u
tio
n
.
Fo
r
m
er
is
te
r
m
ed
as
allo
ca
tio
n
ac
tiv
it
y
;
w
h
ile
t
h
e
latter
is
ter
m
ed
as sc
h
ed
u
li
n
g
ac
tiv
it
y
.
Af
ter
id
e
n
ti
f
y
i
n
g
t
h
e
n
ee
d
f
or
ef
f
icien
t
tas
k
d
is
tr
ib
u
to
r
an
d
it
s
r
o
le,
n
e
x
t
is
to
d
is
ti
n
g
u
i
s
h
th
e
t
y
p
e
o
f
task
s
.
T
ask
s
ca
n
b
e
b
r
o
ad
ly
cl
ass
i
f
ied
in
to
t
w
o
t
y
p
es
n
a
m
el
y
s
eq
u
en
tia
l
an
d
p
a
r
a
llel
.
Seq
u
en
tial
ta
s
k
s
h
a
v
e
to
b
e
ex
ec
u
ted
u
n
d
i
v
id
ed
l
y
a
n
d
as
p
er
th
e
p
r
o
g
r
a
m
o
r
d
er
.
Vio
latin
g
t
h
is
r
u
le
ca
n
m
o
r
e
o
f
ten
lead
to
d
ata
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
E
C
E
I
SS
N:
2
0
8
8
-
8708
Tr
en
d
s
in
Ta
s
k
A
llo
ca
tio
n
Tech
n
iq
u
es fo
r
Mu
ltico
r
e
S
ystem
(
A
r
u
n
K
u
ma
r
S
u
n
d
a
r
R
a
ja
n
)
3019
in
co
n
s
is
te
n
cie
s
.
P
ar
allel
task
s
ar
e
in
d
ep
en
d
en
t
co
d
e
s
e
g
m
e
n
t
s
th
at
ca
n
b
e
e
x
ec
u
ted
i
n
p
ar
al
lel
a
m
o
n
g
d
i
f
f
er
en
t
co
r
es.
Han
d
lin
g
o
f
tas
k
t
y
p
e
s
i
s
elab
o
r
ated
in
th
e
Sectio
n
4
.
W
ith
a
b
r
ie
f
i
n
tr
o
d
u
ctio
n
to
t
h
e
b
asic
ter
m
i
n
o
lo
g
ies
(
as
d
ep
i
cted
in
Fi
g
u
r
e
1
)
,
t
h
is
p
ap
er
b
eg
in
s
w
i
th
an
h
i
s
to
r
ical
o
v
er
v
ie
w
o
f
t
h
e
r
esear
ch
ac
tiv
ities
i
n
Sectio
n
2
.
Sectio
n
3
d
escr
ib
es
in
d
etail
th
e
tas
k
allo
ca
tio
n
s
ch
e
m
es
s
u
itab
le
f
o
r
m
u
lt
ico
r
e
s
y
s
te
m
.
P
ar
allel
ex
ec
u
tio
n
o
f
tas
k
b
lo
ck
s
u
s
i
n
g
co
m
p
il
er
an
d
s
p
ec
u
lati
v
e
h
ar
d
w
ar
e
tec
h
n
iq
u
e
is
d
is
c
u
s
s
ed
in
Sect
io
n
4
.
I
n
ad
d
itio
n
,
c
o
n
tr
o
l
f
lo
w
a
n
d
d
ata
d
ep
en
d
en
cies
th
at
w
ill
ar
is
e
w
it
h
s
p
ec
u
la
tiv
e
h
ar
d
w
ar
e
i
s
also
ex
p
lai
n
ed
w
i
th
s
u
itab
le
ex
a
m
p
le
s
.
L
ater
,
m
at
h
e
m
a
tica
l
m
o
d
eli
n
g
o
f
tas
k
allo
ca
tio
n
alg
o
r
ith
m
s
f
o
r
d
ec
en
tr
alize
d
task
s
c
h
ed
u
l
in
g
s
c
h
e
m
e
is
b
r
o
u
g
h
t
o
u
t.
Fin
a
ll
y
,
a
co
n
s
o
lid
ated
r
ev
ie
w
is
p
r
esen
ted
in
Sectio
n
5.
HW
–
Har
d
w
ar
e;
Fig
u
r
e
1
.
B
u
ild
in
g
B
lo
ck
s
Des
cr
ib
in
g
Step
s
t
h
at
ar
e
I
n
v
o
lv
ed
f
r
o
m
T
ask
B
lo
ck
Fo
r
m
ati
o
n
t
o
C
o
r
e
A
llo
ca
tio
n
2.
RE
L
AT
E
D
W
O
RK
T
h
is
Sectio
n
b
r
in
g
s
o
u
t
a
n
o
v
er
v
ie
w
o
f
t
h
e
r
esear
ch
ac
ti
v
iti
es
t
h
at
w
er
e
ca
r
r
ied
o
u
t
w
it
h
r
esp
ec
t
to
th
e
tas
k
s
c
h
ed
u
li
n
g
an
d
allo
ca
t
io
n
,
s
tar
tin
g
f
r
o
m
s
i
n
g
le
co
r
e
an
d
ti
m
e
li
n
ed
to
m
u
ltico
r
e
s
ce
n
ar
io
.
Sch
ed
u
l
in
g
a
lg
o
r
it
h
m
s
w
er
e
o
f
t
w
o
t
y
p
e
s
,
n
a
m
el
y
ti
m
eli
n
e
d
r
iv
en
ap
p
r
o
ac
h
(
al
s
o
ter
m
ed
as
t
i
m
eli
n
e
s
ch
ed
u
lin
g
)
an
d
p
r
io
r
it
y
d
r
iv
e
n
ap
p
r
o
ac
h
.
I
n
ti
m
eli
n
e
s
ch
ed
u
li
n
g
[
4
]
,
th
e
ti
m
e
p
er
io
d
w
as
d
iv
id
ed
in
to
s
lo
ts
o
f
f
i
x
ed
len
g
th
a
n
d
tas
k
s
w
er
e
s
taticall
y
allo
ca
ted
to
a
s
lo
t
b
ased
o
n
th
eir
f
r
eq
u
e
n
c
y
a
n
d
ex
ec
u
tio
n
ti
m
e.
A
lt
h
o
u
g
h
t
i
m
e
lin
e
s
c
h
ed
u
l
i
n
g
w
as
s
tr
ai
g
h
t
f
o
r
w
ar
d
to
i
m
p
le
m
e
n
t,
it
w
as
f
r
ag
il
e
u
n
d
er
o
v
er
lo
ad
co
n
d
itio
n
s
-
w
h
er
e
a
tas
k
co
u
ld
ex
ce
ed
its
p
r
ed
icted
ex
ec
u
tio
n
ti
m
e
a
n
d
g
e
n
er
ate
a
d
o
m
i
n
o
k
in
d
o
f
ef
f
ec
t
o
n
th
e
s
u
b
s
eq
u
en
t
tas
k
s
to
s
u
r
p
ass
th
e
ir
ti
m
eli
n
e.
A
s
o
lu
tio
n
to
th
e
d
i
f
f
icu
lties
o
f
ti
m
el
i
n
e
d
r
iv
en
ap
p
r
o
ac
h
w
a
s
f
o
r
m
u
lated
i
n
p
r
io
r
it
y
d
r
iv
e
n
ap
p
r
o
ac
h
.
I
n
th
is
ap
p
r
o
ac
h
,
task
s
w
er
e
as
s
ig
n
ed
a
-
p
r
io
r
an
d
s
ch
ed
u
ler
w
o
r
k
ed
b
ased
o
n
th
e
p
r
io
r
ity
v
al
u
e.
Ou
t
o
f
th
e
m
a
n
y
p
r
io
r
it
y
b
a
s
ed
ap
p
r
o
ac
h
es
[
5
-
7
]
,
th
e
p
r
ed
o
m
in
a
n
t
w
er
e
R
ate
Mo
n
o
to
n
i
c
(
R
M)
–
w
h
er
e
th
e
p
r
io
r
ities
w
er
e
s
ta
ticall
y
as
s
ig
n
ed
to
th
e
task
s
an
d
E
ar
lies
t
Dea
d
lin
e
First
(
E
DF)
–
w
h
er
e
th
e
p
r
io
r
ities
w
er
e
d
y
n
a
m
ical
l
y
ass
ig
n
ed
to
th
e
tas
k
s
,
i
n
ac
h
iev
i
n
g
r
ea
l
ti
m
e
b
eh
a
v
io
r
f
o
r
s
in
g
le
co
r
e
en
v
ir
o
n
m
e
n
t.
I
n
p
ar
allel,
ex
p
e
r
i
m
en
ts
o
n
f
in
d
i
n
g
s
u
itab
l
e
an
d
ef
f
icie
n
t
al
g
o
r
ith
m
s
f
o
r
m
u
l
tico
r
e
en
v
ir
o
n
m
e
n
t
h
ad
g
ai
n
ed
i
m
p
o
r
tan
ce
.
E
x
p
er
i
m
en
ts
co
m
b
i
n
i
n
g
p
r
io
r
it
y
b
ased
alg
o
r
ith
m
s
(
R
M
an
d
E
DF)
th
at
w
er
e
s
u
cc
e
s
s
f
u
l
in
s
i
n
g
le
co
r
e
w
as
t
r
ied
o
v
er
m
u
ltico
r
e
en
v
ir
o
n
m
en
t.
Ma
j
o
r
co
n
ce
r
n
s
in
m
ap
p
i
n
g
s
u
c
h
alg
o
r
it
h
m
s
we
r
e
co
m
p
lex
it
y
,
lac
k
o
f
r
eu
s
ab
ilit
y
a
n
d
s
c
h
ed
u
lin
g
a
n
o
m
alie
s
w
i
th
r
esp
ec
t
to
lo
ad
d
is
tr
ib
u
tio
n
an
d
s
y
n
ch
r
o
n
izatio
n
b
et
w
ee
n
th
e
c
o
r
es [
8
-
1
0
]
.
I
n
o
r
d
er
to
ac
h
ie
v
e
e
f
f
ec
ti
v
e
l
o
ad
d
is
tr
ib
u
tio
n
,
r
esear
c
h
er
s
h
ad
co
m
e
u
p
w
it
h
v
ar
io
u
s
h
e
u
r
is
tic
tas
k
s
ch
ed
u
lin
g
tec
h
n
iq
u
e
s
b
ased
o
n
ex
ec
u
tio
n
ti
m
e,
co
m
p
le
t
io
n
ti
m
e
o
f
th
e
tas
k
a
n
d
als
o
co
m
b
i
n
atio
n
s
o
f
alg
o
r
ith
m
s
s
u
ch
a
s
MI
N
–
M
A
X
d
u
r
atio
n
al
g
o
r
ith
m
s
,
s
w
it
ch
in
g
al
g
o
r
ith
m
,
s
u
f
f
er
ag
e
al
g
o
r
ith
m
s
etc.
,
[
1
1
]
.
An
o
th
er
ap
p
r
o
ac
h
w
a
s
to
r
e
d
u
ce
th
e
m
a
k
esp
a
n
b
y
u
t
iliz
atio
n
o
f
p
ar
alle
l
tas
k
m
o
d
el
s
.
C
o
m
b
i
n
atio
n
o
f
s
eq
u
en
tial
a
n
d
p
ar
allel
ta
s
k
s
ch
ed
u
li
n
g
al
g
o
r
ith
m
s
li
k
e
MI
N
/
M
AX
–
R
o
u
n
d
R
o
b
in
,
M
I
N
/
M
A
X
–
L
o
ad
B
alan
ce
,
MI
N
/
M
A
X
–
M
in
Nu
m
b
er
o
f
T
ask
an
d
MI
N
/
MA
X
–
NT
W
P
w
as
e
x
p
er
i
m
e
n
ted
[
1
2
]
.
Deta
ils
o
f
th
ese
al
g
o
r
ith
m
s
ar
e
e
x
p
lain
ed
in
Sectio
n
5
o
f
t
h
is
p
ap
er
.
T
ask
s
ch
ed
u
li
n
g
alg
o
r
it
h
m
s
,
w
h
ic
h
w
er
e
m
o
r
e
o
r
less
a
co
m
b
in
at
io
n
o
f
s
i
n
g
le
co
r
e
al
g
o
r
ith
m
s
,
w
er
e
ass
u
m
ed
to
b
r
in
g
in
t
h
e
r
eq
u
ir
ed
p
er
f
o
r
m
an
ce
u
p
li
f
t
to
a
m
u
ltico
r
e
s
y
s
te
m
.
Ho
w
e
v
er
th
e
r
esu
lt
s
w
er
e
n
o
t
f
r
u
it
f
u
l.
A
s
tr
o
n
g
s
u
p
p
le
m
e
n
t
f
r
o
m
e
f
f
ec
ti
v
e
tas
k
al
lo
ca
tio
n
s
c
h
e
m
e
w
as
n
ee
d
o
f
t
h
e
h
o
u
r
.
T
y
p
icall
y
,
th
e
allo
ca
tio
n
s
c
h
e
m
es
ca
n
b
e
cl
ass
i
f
ied
u
n
d
er
g
lo
b
al,
p
ar
titi
o
n
ed
o
r
d
ec
en
tr
alize
d
s
ch
e
m
e
s
.
Sectio
n
4
o
f
th
i
s
p
ap
er
f
o
cu
s
es i
n
d
etail
ab
o
u
t th
e
tas
k
allo
ca
tio
n
s
c
h
e
m
es,
t
h
eir
m
eth
o
d
s
a
n
d
th
eir
p
r
o
s
&
c
o
n
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
0
8
8
-
8708
I
J
E
C
E
Vo
l.
6
,
No
.
6
,
Dec
em
b
er
2
0
1
6
:
3
0
1
8
–
30
30
3020
B
r
an
d
en
b
u
r
g
[
1
3
]
p
er
f
o
r
m
ed
an
ex
p
er
i
m
e
n
tal
s
tu
d
y
b
et
w
ee
n
p
ar
titi
o
n
ed
E
DF
an
d
g
lo
b
al
E
DF
u
s
i
n
g
L
I
T
MU
S
RT
-
a
d
er
iv
a
tiv
e
o
f
L
i
n
u
x
Ker
n
el
o
n
2
4
-
co
r
e
I
n
te
l
Xeo
n
p
lat
f
o
r
m
.
His
e
x
p
er
i
m
e
n
t
s
h
o
w
ed
th
at
p
ar
titi
o
n
ed
E
DF
w
o
u
ld
b
e
m
o
r
e
p
r
ef
er
ab
le
f
o
r
h
ar
d
r
ea
l
-
t
i
m
e
s
y
s
te
m
w
h
ile
g
lo
b
al
E
D
F
w
o
u
ld
b
e
m
o
r
e
ef
f
ec
tiv
e
in
a
s
o
f
t
r
ea
l
-
ti
m
e
s
y
s
te
m
.
An
o
t
h
er
ex
ten
s
iv
e
w
o
r
k
in
t
h
e
p
r
io
r
it
y
b
ased
al
g
o
r
it
h
m
f
o
r
m
u
ltico
r
e
w
a
s
don
e
b
y
Z
ap
ata
&
A
l
v
ar
ez
[
1
4
]
,
w
h
er
e
R
M
a
n
d
E
DF
al
g
o
r
ith
m
s
w
er
e
s
u
b
j
ec
ted
to
b
e
s
t
k
n
o
w
n
h
e
u
r
is
t
ic
f
u
n
ctio
n
s
:
w
o
r
s
t
f
it
(
W
F),
f
ir
s
t
f
it
(
F
F),
b
est
f
it
(
B
F)
an
d
n
e
x
t
f
it
(
N
F)
f
o
r
b
o
th
p
ar
titi
o
n
ed
an
d
g
lo
b
al
s
c
h
e
m
e.
Fu
r
t
h
er
s
tatic
s
ch
ed
u
li
n
g
o
n
p
ar
titi
o
n
ed
s
ch
e
m
e
f
o
r
s
in
g
le
co
r
e
an
d
m
u
ltico
r
e
p
r
o
ce
d
u
r
e
w
er
e
d
em
o
n
s
tr
ated
[
1
5
-
1
6
]
.
Me
an
w
h
ile
L
au
za
c
e
t
al.
,
[
1
7
]
h
ad
p
er
f
o
r
m
ed
a
co
m
p
ar
ativ
e
s
tu
d
y
o
f
g
lo
b
al
R
M
a
n
d
p
ar
titi
o
n
ed
R
M
s
ch
e
m
e.
T
h
eir
o
b
s
er
v
atio
n
als
o
s
h
o
w
ed
th
at
f
o
r
s
o
f
t
r
ea
l
-
ti
m
e
s
y
s
te
m
s
-
g
lo
b
al
s
c
h
ed
u
li
n
g
ca
n
p
er
f
o
r
m
b
etter
b
ec
au
s
e
o
v
er
lo
ad
ed
p
r
o
ce
s
s
o
r
s
ca
n
d
is
tr
ib
u
te
ta
s
k
s
to
u
n
d
er
lo
ad
ed
p
r
o
ce
s
s
o
r
s
d
y
n
a
m
i
ca
ll
y
,
w
h
er
ea
s
i
n
a
p
ar
titi
o
n
ed
s
c
h
e
m
e
a
ta
s
k
allo
ca
tio
n
w
a
s
f
i
x
ed
.
T
h
e
y
h
ad
al
s
o
p
o
in
ted
o
u
t
t
h
e
s
c
h
ed
u
lin
g
ef
f
ec
ts
o
f
R
M
w
it
h
r
esp
ec
t to
d
elay
s
ee
n
i
n
lo
w
p
r
io
r
it
y
tas
k
s
u
n
d
er
g
lo
b
al
an
d
p
ar
titi
o
n
i
n
g
s
c
h
e
m
e
o
f
a
m
u
l
tic
o
r
e
en
v
ir
o
n
m
en
t.
L
ee
et
al
.
,
[
1
8
]
h
ad
c
o
m
e
u
p
w
it
h
th
r
ee
alg
o
r
it
h
m
s
th
at
o
p
er
ate
o
n
d
ec
en
tr
alize
d
s
ch
em
e
n
a
m
el
y
L
o
ca
l
s
c
h
ed
u
li
n
g
,
I
n
ter
n
o
d
es
s
ch
ed
u
lin
g
a
n
d
Qu
e
u
e
b
alan
c
in
g
.
E
ac
h
o
f
t
h
eir
tech
n
iq
u
e
w
a
s
ev
al
u
ated
in
a
clu
s
ter
ed
e
n
v
ir
o
n
m
e
n
t
a
n
d
t
h
e
ir
ex
p
er
i
m
e
n
tal
r
e
s
u
lt
s
s
h
o
w
e
d
o
f
th
r
o
u
g
h
p
u
t
i
m
p
r
o
v
e
m
e
n
t
u
s
i
n
g
d
ec
en
tr
alize
d
s
ch
e
m
e.
W
ith
g
r
o
w
i
n
g
i
m
p
o
r
tan
ce
f
o
r
p
ar
allelis
m
,
w
h
ic
h
ca
n
b
r
in
g
i
n
h
i
g
h
er
p
er
f
o
r
m
a
n
ce
,
r
ea
l
-
ti
m
e
ap
p
licatio
n
s
s
tar
ted
to
f
o
cu
s
o
n
p
ar
allel
task
m
o
d
els.
T
r
ad
iti
o
n
all
y
co
m
p
iler
an
d
h
ar
d
w
ar
e
s
p
ec
u
latio
n
b
ased
ap
p
r
o
ac
h
es
w
er
e
u
s
ed
to
d
iv
id
e
s
eq
u
e
n
tial
tas
k
s
;
h
o
w
e
v
er
it
h
as
b
ec
o
m
e
co
m
p
licate
d
f
o
r
co
m
p
iler
to
s
taticall
y
d
eter
m
i
n
e
all
t
h
e
d
ep
en
d
en
cies
esp
ec
ial
l
y
f
o
r
p
r
o
g
r
a
m
s
w
it
h
d
y
n
a
m
ic
d
ata
s
tr
u
ctu
r
es.
C
o
n
tr
o
l
f
lo
w
an
d
d
ata
d
ep
en
d
en
cies
w
er
e
also
co
m
m
o
n
to
o
cc
u
r
w
h
i
le
p
ar
titi
o
n
in
g
a
tas
k
b
ased
o
n
s
p
ec
u
latio
n
.
I
n
Sectio
n
2
o
f
th
is
p
ap
er
,
p
ar
titi
o
n
in
g
tech
n
iq
u
e
s
an
d
d
ep
en
d
en
cies
t
h
at
w
o
u
ld
ar
is
e
ar
e
ex
p
lain
ed
in
d
etail
w
it
h
ex
a
m
p
l
e
s
.
Div
er
s
i
f
icat
io
n
o
f
tas
k
i
n
to
p
ar
allel
m
o
d
els
an
d
ap
p
l
y
i
n
g
t
h
e
tr
ad
itio
n
al
d
ea
d
lin
e
al
g
o
r
ith
m
s
w
er
e
d
escr
ib
ed
in
w
o
r
k
s
o
f
L
i
et
al
.
,
[
1
9
]
.
A
n
o
th
er
ap
p
r
o
ac
h
in
co
m
b
in
i
n
g
D
A
G
d
ir
ec
t
ac
y
clic
g
r
ap
h
s
w
as
d
escr
ib
ed
in
w
o
r
k
s
o
f
Sai
f
u
l
lah
et
a
l.
,
[
2
0
]
.
T
h
ese
ap
p
r
o
ac
h
es
co
u
ld
n
o
t
h
a
n
d
le
d
ep
en
d
en
cie
s
t
h
at
w
er
e
d
y
n
a
m
ic
i
n
n
at
u
r
e.
I
n
o
r
d
er
to
h
an
d
le
d
y
n
a
m
ic
d
ep
en
d
e
n
cies,
h
ar
d
w
ar
e
b
ased
ap
p
r
o
ac
h
u
s
i
n
g
ca
ch
e
li
k
e
s
tr
u
ct
u
r
es
-
ad
d
r
ess
r
eso
l
u
tio
n
b
u
f
f
er
(
AR
B
)
f
o
r
ce
n
tr
ali
ze
d
s
h
ar
ed
m
e
m
o
r
y
m
u
ltip
r
o
ce
s
s
o
r
[
2
1
]
an
d
s
p
ec
u
lat
i
v
e
v
er
s
io
n
i
n
g
ca
ch
e
(
SVC
)
f
o
r
d
is
tr
ib
u
ted
s
h
ar
ed
m
e
m
o
r
y
m
u
ltip
r
o
ce
s
s
o
r
[
2
2
]
h
av
e
b
ee
n
ex
p
lo
r
ed
.
I
n
th
e
s
e
tech
n
iq
u
es,
ea
ch
co
r
e
b
u
f
f
er
ed
th
e
v
alu
e
a
n
d
v
al
u
e
w
as
w
r
it
ten
to
m
ai
n
m
e
m
o
r
y
o
n
l
y
w
h
e
n
th
e
o
p
er
atio
n
w
as
co
m
m
itted
,
el
s
e
d
is
ca
r
d
ed
b
y
b
u
f
f
er
f
lu
s
h
i
n
g
tech
n
iq
u
e
s
.
E
x
te
n
s
iv
e
r
ep
o
r
t
o
n
s
p
ec
u
lati
v
e
m
u
ltit
h
r
ea
d
ar
ch
itect
u
r
e
ca
n
b
e
s
ee
n
i
n
t
h
e
w
o
r
k
s
o
f
So
h
i
a
n
d
Vij
ay
k
u
m
ar
[
2
3
]
.
Sp
ec
u
latio
n
f
o
r
d
ata
to
av
o
id
d
ep
en
d
en
c
y
w
as a
l
s
o
tr
ied
an
d
th
e
s
a
m
e
ca
n
b
e
s
ee
n
in
t
h
e
wo
r
k
s
o
f
Ha
m
m
o
n
d
et
al.
,
[
2
4
]
.
Of
late,
s
eq
u
en
tia
l
p
r
o
g
r
a
m
ca
n
b
e
co
n
v
er
ted
to
p
ar
al
lel
p
r
o
g
r
a
m
u
s
i
n
g
Op
en
MP
Fo
r
k
-
j
o
in
s
tr
u
ctu
r
e.
B
est
an
d
w
o
r
s
t
ca
s
e
s
ce
n
ar
io
s
o
f
u
s
in
g
t
h
is
f
o
r
k
-
j
o
in
m
o
d
el
w
er
e
ill
u
s
tr
ated
in
t
h
e
w
o
r
k
s
o
f
L
a
k
s
h
m
a
n
a
n
et
al.
,
[
2
5
]
.
Fo
r
b
etter
u
n
d
er
s
ta
n
d
in
g
o
f
s
c
h
ed
u
lin
g
ter
m
i
n
o
l
o
g
y
,
b
o
o
k
b
y
L
ab
r
o
s
s
e
[
2
6
]
o
n
µc
-
OS
I
I
an
d
f
o
r
to
p
ics
o
n
p
ar
allelis
m
,
b
o
o
k
b
y
He
n
n
e
s
s
y
&
P
atter
s
o
n
[
2
7
]
o
n
C
o
m
p
u
ter
A
r
ch
itect
u
r
e
i
s
r
ec
o
m
m
e
n
d
ed
as th
e
y
p
r
o
v
id
e
g
o
o
d
in
s
i
g
h
t.
3.
P
ARAL
L
E
L
E
X
E
CU
T
I
O
N
O
F
T
ASK
S
I
n
o
r
d
er
to
i
m
p
r
o
v
e
th
e
p
er
f
o
r
m
an
ce
a
n
d
to
u
tili
ze
th
e
ca
p
ab
ilit
y
o
f
m
u
ltico
r
e
s
y
s
te
m
,
tas
k
s
ar
e
s
p
li
t
in
to
s
m
aller
b
lo
ck
s
an
d
m
ad
e
to
ex
ec
u
te
s
i
m
u
l
tan
eo
u
s
l
y
i
n
m
o
r
e
th
a
n
o
n
e
co
r
e.
T
h
is
Se
ctio
n
ad
d
r
ess
es
o
n
tech
n
iq
u
es
n
ee
d
ed
f
o
r
p
ar
allel
co
d
e
ex
ec
u
tio
n
.
3
.
1
.
T
a
s
k
T
y
pe
s
T
ask
s
ar
e
b
r
o
ad
ly
class
i
f
ied
i
n
to
t
w
o
t
y
p
es
n
a
m
e
l
y
,
s
er
ial
o
r
s
eq
u
en
tial
tas
k
s
an
d
p
ar
allel
o
r
h
ig
h
p
er
f
o
r
m
a
n
ce
co
m
p
u
ti
n
g
tas
k
s
.
Seq
u
en
tia
l
tas
k
s
h
av
e
to
b
e
ex
ec
u
ted
u
n
d
i
v
id
ed
l
y
a
n
d
as
p
er
th
e
p
r
o
g
r
a
m
o
r
d
er
.
Vio
latin
g
th
i
s
r
u
le
w
o
u
ld
lead
to
d
at
a
in
co
n
s
i
s
te
n
c
ies.
On
t
h
e
o
th
er
h
an
d
,
p
ar
allel
task
s
ar
e
co
d
e
s
eg
m
e
n
ts
t
h
at
ar
e
in
d
ep
en
d
en
t
an
d
as
th
eir
n
a
m
e
s
u
g
g
est
s
,
ca
n
b
e
o
p
er
ated
in
p
ar
allel.
A
d
v
an
ta
g
e
o
f
p
ar
allel
task
i
s
r
ed
u
ctio
n
in
o
v
er
all
e
x
ec
u
t
io
n
ti
m
e.
T
h
e
ca
teg
o
r
y
u
n
d
er
w
h
ic
h
a
tas
k
f
all
s
p
u
r
el
y
d
ep
en
d
s
o
n
th
e
s
y
s
te
m
d
es
ig
n
.
B
ased
o
n
d
ep
en
d
en
c
y
i
n
co
d
i
n
g
,
s
o
m
e
Sectio
n
s
o
f
s
er
ial
t
ask
ar
e
d
iv
id
ed
i
n
to
s
u
b
tas
k
s
an
d
ea
c
h
s
u
b
tas
k
is
m
ad
e
to
r
u
n
in
p
ar
allel
a
m
o
n
g
th
e
co
r
es.
B
u
t
wh
o
p
er
f
o
r
m
s
th
e
b
r
ea
k
i
n
g
o
f
t
ask
s
in
to
s
u
b
tas
k
s
?
Su
b
tas
k
s
,
w
h
ich
ar
e
co
n
ti
g
u
o
u
s
p
ar
ts
o
f
in
s
tr
u
ct
io
n
s
tr
ea
m
an
d
ar
e
ex
ec
u
ted
in
p
ar
allel,
is
id
en
tif
ied
eit
h
er
b
y
p
r
o
g
r
am
m
er
d
u
r
i
n
g
t
h
e
d
esi
g
n
a
n
d
co
d
in
g
p
h
a
s
e
o
r
b
y
co
m
p
iler
o
r
b
y
u
s
i
n
g
a
s
p
ec
u
lati
v
e
h
ar
d
w
ar
e
(
So
h
i&
Vij
a
y
k
u
m
ar
(
2
0
0
9
)
)
.
D
etails o
f
ea
c
h
tech
n
iq
u
e
ar
e
el
ab
o
r
ated
in
th
e
f
o
llo
w
in
g
s
u
b
S
ec
tio
n
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
E
C
E
I
SS
N:
2
0
8
8
-
8708
Tr
en
d
s
in
Ta
s
k
A
llo
ca
tio
n
Tech
n
iq
u
es fo
r
Mu
ltico
r
e
S
ystem
(
A
r
u
n
K
u
ma
r
S
u
n
d
a
r
R
a
ja
n
)
3021
On
ce
t
h
e
s
u
b
tas
k
s
ar
e
id
en
tifi
ed
,
th
e
y
ca
n
b
e
allo
ca
ted
to
o
n
e
o
f
m
u
ltip
le
co
r
es,
eit
h
er
s
t
atica
ll
y
o
r
d
y
n
a
m
icall
y
,
u
s
i
n
g
t
h
e
allo
c
atio
n
s
c
h
e
m
e
s
.
Sectio
n
4
el
ab
o
r
ates
o
n
th
e
allo
ca
tio
n
s
ch
e
m
e.
P
ar
allelis
m
ac
h
iev
ed
b
y
b
r
ea
k
i
n
g
a
p
r
o
g
r
a
m
i
n
to
s
u
b
tas
k
s
i
s
o
f
te
n
r
e
f
e
r
r
ed
to
as
T
h
r
ea
d
lev
el
p
ar
allelis
m
T
L
P
an
d
th
i
s
tech
n
iq
u
e
i
s
d
i
f
f
er
en
t
f
r
o
m
I
n
s
tr
u
ctio
n
-
lev
el
p
ar
allelis
m
I
L
P
,
as
ea
c
h
s
u
b
tas
k
i
n
T
L
P
ca
n
c
o
n
tain
h
u
n
d
r
ed
s
to
m
illi
o
n
s
o
f
i
n
s
tr
u
ctio
n
s
t
h
at
ar
e
ex
ec
u
ted
i
n
p
ar
allel
w
i
th
o
t
h
er
s
u
b
tas
k
s
.
A
r
c
h
itect
u
r
e
th
at
u
s
es
t
h
r
ea
d
s
o
r
s
u
b
task
s
to
ex
ec
u
te
a
p
r
o
g
r
a
m
in
p
ar
allel
is
r
ef
er
r
ed
to
M
u
ltit
h
r
ea
d
A
r
c
h
itect
u
r
e.
E
v
e
n
t
u
all
y
,
th
is
t
y
p
e
o
f
ar
c
h
itect
u
r
e
ca
n
f
ac
ilit
ate
s
i
m
u
ltan
eo
u
s
e
x
ec
u
tio
n
o
f
m
u
ltip
le
ta
s
k
s
,
a
s
w
ell
a
s
m
u
ltip
le
s
u
b
tas
k
s
/
th
r
ea
d
s
.
Alo
n
g
w
ith
t
h
e
b
en
ef
its
o
f
f
as
ter
ex
ec
u
tio
n
d
u
e
to
p
ar
allelis
m
in
m
u
ltit
h
r
ea
d
ed
ar
ch
itectu
r
e,
ce
r
tain
o
v
er
h
e
ad
s
,
n
a
m
el
y
r
eso
u
r
ce
co
n
ten
tio
n
-
s
h
ar
ed
m
e
m
o
r
y
h
a
n
d
lin
g
,
s
y
n
ch
r
o
n
izatio
n
a
n
d
lo
ad
i
m
b
alan
ce
f
o
llo
w
.
I
n
th
e
u
p
co
m
in
g
p
ar
t,
tech
n
i
q
u
es
u
s
in
g
co
m
p
iler
an
d
h
ar
d
w
ar
e
to
b
r
ea
k
d
o
w
n
a
s
er
ial
task
in
to
p
ar
allel
ar
e
d
is
cu
s
s
ed
.
3
.
2
.
Co
m
pil
er
B
a
s
ed
P
a
ra
llelis
m
Fo
r
m
u
la
tio
n
o
f
s
u
b
tas
k
s
u
s
in
g
co
m
p
lier
is
s
tatic
in
n
a
tu
r
e
.
Du
r
in
g
co
m
p
ila
tio
n
o
f
a
p
r
o
g
r
a
m
,
th
e
co
m
p
lier
id
en
ti
f
ie
s
co
d
e
s
eq
u
en
ce
s
w
h
er
e
s
a
m
e
s
e
t
o
f
o
p
er
atio
n
s
ar
e
ap
p
lied
to
m
u
lt
ip
le
d
ata
ite
m
s
an
d
f
ac
ilit
ate
s
p
ar
allel
o
p
er
atio
n
to
th
at
co
d
e
s
eq
u
en
ce
.
F
o
r
ex
a
m
p
le,
co
n
s
id
er
iter
atio
n
f
o
r
ad
d
in
g
„
n
‟
o
b
j
ec
ts
o
f
an
ar
r
a
y
.
Let
‟
A
‟
b
e
th
e
A
r
r
a
y
o
f
s
iz
e
„
n
‟
,
„
e‟
b
e
th
e
ex
ec
u
tio
n
time
f
o
r
1
a
d
d
itio
n
o
p
era
tio
n
a
n
d
th
e
n
u
mb
er
o
f
co
r
es
b
e
„
m‟
Th
ere
w
ill
a
ls
o
b
e
a
d
d
itio
n
a
l
ex
ec
u
tio
n
time
fo
r
b
r
a
n
ch
in
g
o
p
era
tio
n
a
n
d
th
is
b
r
a
n
ch
in
g
time
is
cu
r
r
en
tly
ig
n
o
r
ed
fo
r
ea
s
y
u
n
d
ers
ta
n
d
in
g
o
f th
e
u
n
d
erlyin
g
co
n
ce
p
t.
I
n
a
s
eq
u
en
tial
u
n
ip
r
o
ce
s
s
o
r
,
th
e
lo
o
p
p
er
f
o
r
m
i
n
g
ad
d
itio
n
w
il
l
iter
ate
n
ti
m
e
s
an
d
th
e
r
e
s
u
lt
w
i
ll
b
e
av
ailab
le
o
n
l
y
af
ter
t
h
e
d
u
r
atio
n
o
f
n *
e
an
d
th
e
s
a
m
e
i
s
d
e
m
o
n
s
tr
ated
in
A
l
g
o
r
ith
m
1
.
Initialize
m
number of Cores(
C)
A
array of ‘n’ ele
ments
Sum
result of add
ition operation
m = 1; uniprocessor
/single cores
Sum = 0; initial value
i = 0;
for
every ‘i’
do until
‘i’
is equal to
‘n’
Sum = Sum + A[i];
Increment i;
end for
A
lg
o
r
ith
m
1
.
A
d
d
itio
n
o
p
era
tio
n
in
s
in
g
le
c
o
r
e
s
eq
u
en
tia
l e
x
ec
u
tio
n
C
o
mp
lexity:
n
*
e
;
n
-
n
u
mb
er
o
f e
n
tr
ies to
a
d
d
,
e
-
ex
ec
u
tio
n
time
fo
r
1
a
d
d
itio
n
o
p
era
tio
n
I
n
a
m
u
ltit
h
r
ea
d
ed
ar
ch
itect
u
r
e
w
it
h
t
h
e
s
u
p
p
o
r
t
o
f
co
m
p
iler
,
t
h
e
ad
d
itio
n
o
p
er
ati
o
n
ca
n
b
e
p
ar
titi
o
n
ed
a
m
o
n
g
th
e
co
r
es
t
o
co
m
p
lete
in
p
ar
allel.
T
h
is
t
ec
h
n
iq
u
e
w
o
u
ld
th
e
n
co
n
s
u
m
e
(
n
/m
+
m)
*
e
ex
ec
u
t
io
n
ti
m
e.
A
d
d
itio
n
al
ef
f
o
r
t
o
f
m
i
s
i
n
cl
u
d
ed
to
in
d
ica
te
t
h
at
r
es
u
lt
s
f
r
o
m
m
co
r
es
h
a
v
e
to
b
e
m
er
g
ed
/s
u
m
m
ed
u
p
to
g
et
h
er
.
I
n
A
l
g
o
r
ith
m
2
,
f
u
n
ctio
n
f
o
r
s
p
lit,
m
er
g
e
a
n
d
ad
d
is
s
h
o
w
n
f
o
r
r
ef
er
en
ce
.
Initialize
m
number of Cores(
C)
A
array of ‘n’ ele
ments
Sum
result of add
ition operation
Split
the ‘n’ addition operations among ‘m’ cores,
1 to n/m
for core P
0
[n/m + 1] to 2n/m
for core P
1
….
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
0
8
8
-
8708
I
J
E
C
E
Vo
l.
6
,
No
.
6
,
Dec
em
b
er
2
0
1
6
:
3
0
1
8
–
30
30
3022
….
[n(m
-
1)/m + 1] to n
for core P
m
add(start,end):
i = start;
count = count + 1; to identify the subtask number
for
every ‘i’
do until
‘i’
is equal to
‘end’ cores
Sum [count] = Sum [count] + A[i];
Increment i;
end for
merge:
for
every ‘i’
do until
‘i’
is equal to
‘m’ cores
Result =
Sum
(Values calculated in each core);
Increment i;
end for
A
lg
o
r
ith
m
2
.
A
d
d
itio
n
o
p
era
tio
n
in
Mu
ltit
h
r
ea
d
ed
A
r
ch
itectu
r
e
w
ith
co
mp
lier
o
p
timiz
a
tio
n
C
o
mp
lexity:
(
n
/m
+ m
)
*
e;
n
-
n
u
mb
er o
f e
n
tr
ies to
a
d
d
,
e
-
e
xe
cu
tio
n
time
fo
r
1
a
d
d
itio
n
o
p
era
tio
n
,
m
-
n
u
mb
er o
f c
o
r
es.
3
.
3
.
Sp
ec
ula
t
iv
ely
M
ultit
hrea
ded
A
rc
hite
ct
ure
I
n
Sp
ec
u
lati
v
el
y
m
u
ltit
h
r
ea
d
ed
ar
ch
itectu
r
e,
h
ar
d
w
ar
e
p
la
y
s
an
i
m
p
o
r
ta
n
t
r
o
le
in
p
ar
titi
o
n
i
n
g
s
eq
u
en
tial
p
r
o
g
r
a
m
i
n
to
s
u
b
ta
s
k
s
.
T
h
e
h
ar
d
w
ar
e
d
o
es
t
h
e
p
ar
titi
o
n
in
g
b
y
s
p
ec
u
lati
n
g
th
at
th
e
s
u
b
tas
k
s
ar
e
in
d
ep
en
d
en
t.
E
ac
h
s
u
b
tas
k
is
s
p
a
w
n
ed
f
r
o
m
a
n
o
t
h
er
s
u
b
ta
s
k
an
d
m
ad
e
to
p
r
o
ce
ed
in
p
ar
all
el.
T
h
e
k
e
y
id
ea
i
n
s
p
ec
u
latio
n
is
to
allo
w
o
u
t
o
f
o
r
d
er
ex
ec
u
tio
n
b
u
t
f
o
r
ce
s
t
h
e
in
s
tr
u
ctio
n
s
to
co
m
m
it
in
o
r
d
er
.
Hier
ar
ch
y
o
f
t
w
o
lev
el
in
s
tr
u
c
tio
n
co
m
m
it
m
e
n
t
is
r
eq
u
ir
ed
in
th
is
ar
ch
itect
u
r
e:
I
n
s
tr
u
ctio
n
s
w
it
h
i
n
ea
ch
co
r
e
(
s
u
b
task
s
)
m
u
s
t
lo
ca
ll
y
co
m
m
it
a
n
d
th
e
o
v
er
all
task
a
m
o
n
g
all
co
r
es
m
u
s
t
g
lo
b
all
y
co
m
m
it i
n
g
i
v
e
n
p
r
o
g
r
am
o
r
d
er
.
Dep
en
d
en
c
y
h
az
ar
d
s
t
h
at
w
o
u
ld
ar
is
e
in
a
s
p
ec
u
la
tiv
e
ap
p
r
o
ac
h
an
d
p
o
s
s
ib
le
s
o
l
u
tio
n
s
f
o
r
h
an
d
li
n
g
th
e
d
ep
en
d
en
c
y
ar
e
d
is
c
u
s
s
ed
as f
o
llo
w
s
.
3
.
3
.
1
.
Depende
ncy
T
h
o
u
g
h
t
h
is
ar
ch
i
tectu
r
e
s
p
e
cu
lates
t
h
at
th
e
s
u
b
tas
k
s
ar
e
in
d
ep
en
d
en
t,
i
n
r
ea
l
ti
m
e
s
ce
n
ar
io
s
th
e
s
u
b
tas
k
s
ca
n
h
a
v
e
co
n
tr
o
l
o
r
/an
d
d
ata
d
ep
en
d
en
cies.
C
o
n
tr
o
l
d
ep
en
d
en
cies
w
il
l
o
cc
u
r
w
h
e
n
a
b
r
an
c
h
d
ec
is
io
n
in
s
id
e
a
s
u
b
tas
k
d
eter
m
i
n
es
wh
ich
s
u
b
tas
k
to
b
e
ex
ec
u
ted
n
ex
t.
So
s
i
m
ilar
to
b
r
an
ch
p
r
ed
icto
r
s
s
ee
n
i
n
I
L
P
,
s
u
b
tas
k
lev
e
l
p
r
ed
icto
r
s
ar
e
n
ee
d
ed
to
p
r
e
d
ict
th
e
f
lo
w
.
L
i
k
e
w
is
e
d
ata
d
ep
en
d
en
cies
ca
n
also
ar
is
e
w
h
e
n
a
m
e
m
o
r
y
o
r
r
eg
is
ter
v
al
u
e
ca
l
cu
lated
in
o
n
e
s
u
b
tas
k
is
co
n
s
u
m
ed
in
o
t
h
er
s
u
b
tas
k
s
.
I
f
t
h
e
h
ar
d
w
ar
e
d
etec
ts
co
n
tr
o
l
o
r
d
ata
d
ep
en
d
en
cies
ac
r
o
s
s
th
e
s
u
b
ta
s
k
s
,
th
e
n
th
e
h
ar
d
w
ar
e
en
f
o
r
ce
s
t
h
e
co
r
r
ec
t
o
r
d
er
o
f
ex
ec
u
tio
n
o
f
d
ep
en
d
en
t
in
s
tr
u
ctio
n
s
a
m
o
n
g
th
e
s
u
b
tas
k
s
.
Har
d
w
ar
e
w
o
u
l
d
b
e
a
b
le
to
d
etec
t
th
e
d
ep
en
d
en
c
y
o
n
l
y
d
u
r
in
g
ex
ec
u
t
io
n
o
r
ea
r
l
y
if
R
eOr
d
er
B
u
f
f
er
s
(
R
OB
)
–
co
m
m
o
n
to
all
co
r
es is
u
s
ed
i
n
s
p
ec
u
la
tio
n
.
I
f
t
h
er
e
h
ad
b
ee
n
a
v
io
latio
n
o
f
co
n
tr
o
l
-
f
lo
w
d
ep
en
d
en
c
y
d
u
e
to
m
i
s
p
r
ed
ictio
n
o
r
a
d
ata
d
ep
en
d
en
c
y
w
h
er
e
co
n
s
u
m
er
h
ad
e
x
ec
u
ted
b
ef
o
r
e
its
p
r
o
d
u
ce
r
,
th
en
t
h
e
h
ar
d
w
ar
e
r
o
lls
b
ac
k
t
h
e
o
f
f
e
n
d
in
g
s
u
b
ta
s
k
s
a
n
d
all
s
u
b
tas
k
s
i
n
later
p
r
o
g
r
am
o
r
d
er
[
2
3
]
.
A
s
a
g
en
er
al
s
a
f
et
y
p
r
o
ce
d
u
r
e
all
th
e
s
u
b
task
s
f
o
llo
w
i
n
g
th
e
o
f
f
en
d
i
n
g
s
u
b
tas
k
s
ar
e
r
o
lled
b
ac
k
.
Me
c
h
an
i
s
m
s
to
id
en
ti
f
y
s
u
b
tas
k
s
t
h
at
ar
e
n
o
t
a
f
f
ec
ted
,
h
elp
s
to
r
ed
u
ce
n
u
m
b
er
o
f
u
n
w
an
ted
r
o
llb
ac
k
s
.
Fo
r
ex
am
p
le,
co
n
s
id
er
th
e
b
elo
w
co
d
e
s
n
ip
p
et
w
h
ic
h
h
i
g
h
li
g
h
t
s
th
e
co
n
tr
o
l
f
lo
w
d
ep
en
d
en
c
y
.
Subtask A
{
while(1)
{
.....
if (condition > 0)
.....
spawn subtask B
.....
else
spawn subtask C
}
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
E
C
E
I
SS
N:
2
0
8
8
-
8708
Tr
en
d
s
in
Ta
s
k
A
llo
ca
tio
n
Tech
n
iq
u
es fo
r
Mu
ltico
r
e
S
ystem
(
A
r
u
n
K
u
ma
r
S
u
n
d
a
r
R
a
ja
n
)
3023
}
C
o
n
tr
o
l
f
lo
w
o
f
th
e
p
r
o
g
r
a
m
is
p
ar
titi
o
n
ed
in
to
th
r
ee
s
u
b
ta
s
k
s
n
a
m
el
y
A
,
B
an
d
C
.
Su
b
t
ask
A
is
a
lo
o
p
b
o
d
y
w
h
er
e
ea
ch
i
ter
atio
n
is
a
n
i
n
s
ta
n
ce
o
f
th
e
s
u
b
task
.
On
e
i
n
s
ta
n
ce
o
f
Su
b
ta
s
k
A
is
p
r
ed
icted
co
r
r
ec
tl
y
an
d
s
p
a
w
n
s
s
u
b
tas
k
B
.
Har
d
w
ar
e
p
r
ed
icts
th
at
n
e
x
t
iter
atio
n
w
il
l
also
ch
o
o
s
e
s
u
b
tas
k
B
an
d
s
p
a
w
n
s
an
o
t
h
er
in
s
ta
n
ce
o
f
s
u
b
task
B
.
T
h
e
s
ec
o
n
d
p
r
ed
ictio
n
is
i
n
co
r
r
ec
t!
!
N
o
w
t
h
e
r
o
ll
b
ac
k
m
ec
h
a
n
is
m
f
l
u
s
h
es
th
e
i
n
s
ta
n
ce
o
f
s
u
b
ta
s
k
B
an
d
lo
ad
s
w
it
h
s
u
b
task
C
.
W
it
h
b
etter
task
le
v
el
p
r
ed
icto
r
s
,
r
o
ll b
ac
k
co
s
t c
an
b
e
av
er
ted
.
Si
m
i
lar
l
y
,
d
ata
d
ep
en
d
en
cies
ca
n
also
b
r
in
g
d
o
w
n
th
e
p
er
f
o
r
m
an
ce
o
f
m
u
ltit
h
r
ea
d
ed
ar
ch
itectu
r
e.
A
k
e
y
id
ea
f
o
r
d
etec
tin
g
d
ep
en
d
en
cies
is
to
k
ee
p
tr
ac
k
o
f
th
e
p
r
o
g
r
am
o
r
d
er
a
m
o
n
g
t
h
e
s
u
b
tas
k
s
.
W
h
e
n
o
n
e
s
u
b
tas
k
e
x
ec
u
tio
n
d
eter
m
i
n
es
th
e
n
e
x
t,
ta
s
k
p
r
ed
ictio
n
ca
n
b
e
d
o
n
e
co
r
r
ec
tl
y
o
n
l
y
if
t
h
e
n
e
x
t
s
eq
u
e
n
ce
i
n
p
r
o
g
r
am
o
r
d
er
is
k
n
o
w
n
.
Si
m
ilar
l
y
,
th
is
o
r
d
er
in
g
i
s
cr
iti
ca
l
in
d
etec
ti
n
g
a
n
d
en
f
o
r
cin
g
tr
u
e
r
e
g
is
ter
a
n
d
m
e
m
o
r
y
d
ep
en
d
en
cies.
3
.
3
.
2
.
H
a
za
rds
Fo
r
ex
a
m
p
le,
co
n
s
id
er
t
h
e
b
elo
w
co
d
e
s
n
ip
p
et
w
h
ic
h
h
ig
h
li
g
h
ts
o
n
t
h
e
d
ata
d
ep
en
d
en
c
y
m
ult
a,b,c;
h
ere,
a
= b
*
c
s
ub
x,y,z;
h
ere,
x
= y
-
z
m
ult
d,v,x;
h
ere,
d
= v
*
x
store
d,10(r1);
h
ere,
d
is
s
to
r
ed
in
mem
o
r
y
[
1
0
+R
1
]
add
y,a,x;
h
ere,
y
= a
+ x
div
d,u,t;
h
ere,
d
= u
/t
store
d,8(r2);
h
ere,
d
is
s
to
r
ed
in
mem
o
r
y
[
8
+R
2
]
*
R
1
a
n
d
R
2
a
r
e
r
eg
is
ters
o
f th
e
co
n
tr
o
ller
.
T
h
is
s
eq
u
en
tial
co
d
e
b
lo
ck
is
d
iv
id
ed
in
to
t
w
o
s
u
b
ta
s
k
s
A
an
d
B
to
f
ac
ilit
ate
p
ar
allel
ex
ec
u
t
io
n
.
No
te:
Su
b
tas
k
s
m
u
s
t b
e
co
n
ti
g
u
o
u
s
co
d
e
b
lo
ck
s
.
Su
b
ta
s
k
A
Su
b
ta
s
k
B
m
ult
a,b,c;
a
dd
y,a,x;
s
ub
x,y,z;
d
iv
d,u,t;
mult
d,v,x;
store
d,8(r2);
store
d,10(r1);
T
h
er
e
ar
e
3
p
o
s
s
ib
le
d
ata
in
co
n
s
is
ten
cie
s
th
at
m
a
y
r
is
e
f
r
o
m
p
ar
allel
ex
ec
u
tio
n
o
f
s
u
b
ta
s
k
A
an
d
s
u
b
tas
k
B
n
a
m
el
y
,
R
A
W
(
R
ea
d
Af
ter
W
r
ite)
v
io
latio
n
i
f
a
dd
in
s
tr
u
c
tio
n
o
f
s
u
b
tas
k
B
r
ea
d
s
th
e
s
o
u
r
ce
'a
'
b
efo
r
e
mult
i
n
s
tr
u
ctio
n
o
f
s
u
b
tas
k
A
w
r
i
tes o
n
to
it.
Su
b
ta
s
k
B
w
i
ll
h
a
v
e
o
ld
v
al
u
e
o
f
'a
'
,
w
h
ic
h
i
s
d
i
f
f
er
e
n
t
f
r
o
m
th
e
ac
t
u
al
p
r
o
g
r
a
m
o
r
d
er
.
W
A
R
(
W
r
ite
A
f
ter
R
ea
d
)
v
io
latio
n
if
sub
in
s
tr
u
c
tio
n
o
f
s
u
b
tas
k
A
r
ea
d
s
'y
'
f
r
o
m
r
e
g
is
ter
a
fte
r
add
i
n
s
tr
u
ctio
n
o
f
s
u
b
tas
k
B
w
r
ite
s
to
th
e
s
a
m
e
s
o
u
r
ce
'y
'
.
T
h
is
r
esu
lt
s
i
n
'
x
'
to
h
a
v
e
in
co
r
r
ec
t
v
alu
e
f
o
r
s
u
b
tas
k
A.
W
A
W
(
W
r
ite
A
f
ter
W
r
ite)
v
io
latio
n
i
f
store
in
s
tr
u
ctio
n
o
f
s
u
b
tas
k
A
a
n
d
s
u
b
tas
k
B
in
ter
c
h
an
g
e
in
ex
ec
u
tio
n
o
r
d
er
.
B
o
th
in
s
tr
u
cti
o
n
s
m
a
y
s
to
r
e
s
a
me
va
lu
e
a
t
b
o
th
th
e
mem
o
r
y
lo
ca
tio
n
s
w
h
ic
h
i
s
i
n
co
r
r
ec
t.
Div
o
r
mult
r
esu
lt
in
s
u
b
ta
s
k
s
w
il
l
b
e
to
tall
y
lo
s
t
a
n
d
o
n
l
y
t
h
e
last
ex
ec
u
ted
r
esu
lt
w
il
l b
e
r
ep
licated
in
b
o
t
h
th
e
m
e
m
o
r
ie
s
.
3
.
3
.
3
.
So
lutio
n
T
h
e
k
e
y
id
ea
to
ac
h
ie
v
e
p
er
f
o
r
m
an
ce
a
n
d
at
th
e
s
a
m
e
ti
m
e
t
o
av
o
id
h
az
ar
d
s
is
to
allo
w
o
u
t
o
f
o
r
d
er
ex
ec
u
t
io
n
f
o
r
p
ar
allelis
m
an
d
to
f
o
r
ce
t
h
e
in
s
tr
u
ct
io
n
s
to
c
o
m
m
i
t
i
n
p
r
o
g
r
a
m
o
r
d
er
.
Hier
ar
ch
y
o
f
t
w
o
lev
e
l
in
s
tr
u
ctio
n
co
m
m
i
t
i
s
r
eq
u
ir
ed
:
I
n
s
tr
u
ctio
n
s
w
it
h
i
n
ea
c
h
co
r
e
(
s
u
b
ta
s
k
s
)
m
u
s
t
lo
ca
ll
y
co
m
m
it
an
d
th
e
o
v
er
a
ll
task
a
m
o
n
g
all
co
r
es
m
u
s
t g
lo
b
all
y
co
m
m
it i
n
g
i
v
e
n
p
r
o
g
r
am
o
r
d
er
.
4.
T
ASK
A
L
L
O
CA
T
I
O
N
SCH
E
M
E
S
Hav
i
n
g
i
n
f
o
r
m
atio
n
o
n
th
e
p
o
s
s
ib
ilit
ie
s
o
f
ta
s
k
f
o
r
m
atio
n
n
e
x
t
i
s
to
d
is
tr
ib
u
te
tas
k
s
a
m
o
n
g
th
e
co
r
es.
T
h
e
tech
n
iq
u
e
s
f
o
r
task
allo
ca
tio
n
ar
e
class
if
ied
as
g
lo
b
al
s
ch
e
m
e,
p
ar
titi
o
n
ed
s
ch
e
m
e
an
d
d
ec
en
tr
alize
d
s
ch
e
m
e.
T
h
is
Sectio
n
elab
o
r
ates in
d
etail
o
n
t
h
e
b
en
e
f
it
s
an
d
d
r
aw
b
ac
k
s
o
f
ea
c
h
s
c
h
e
m
e
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
0
8
8
-
8708
I
J
E
C
E
Vo
l.
6
,
No
.
6
,
Dec
em
b
er
2
0
1
6
:
3
0
1
8
–
30
30
3024
4
.
1
.
G
lo
ba
l Sche
m
e
I
n
th
e
Glo
b
al
s
ch
e
m
e
(
Fig
u
r
e
2
)
,
a
ce
n
tr
alize
d
s
ch
ed
u
ler
m
a
n
ag
e
s
tas
k
al
lo
ca
tio
n
to
i
n
d
iv
i
d
u
al
co
r
es
an
d
co
n
tr
o
ls
th
e
s
ch
ed
u
li
n
g
s
eq
u
en
ce
g
lo
b
all
y
.
B
ein
g
a
ce
n
tr
alize
d
s
ch
ed
u
ler
,
it
k
n
o
w
s
th
e
s
tat
u
s
o
f
tas
k
s
alr
ea
d
y
a
llo
ca
ted
to
th
e
co
r
e,
s
o
w
h
e
n
e
v
er
a
h
ig
h
p
r
io
r
it
y
task
is
r
ea
d
y
to
ex
ec
u
te,
i
t
ca
n
b
e
i
m
m
ed
iatel
y
ass
i
g
n
ed
t
h
e
p
r
o
ce
s
s
in
g
u
n
it
f
o
r
ex
ec
u
tio
n
.
B
y
t
h
is
m
et
h
o
d
,
th
e
o
cc
u
r
r
en
ce
o
f
p
r
io
r
it
y
i
n
v
e
r
s
io
n
is
a
v
o
id
ed
.
“Prio
r
ity
in
ve
r
s
io
n
is
s
a
id
to
h
a
ve
o
cc
u
r
r
ed
w
h
en
a
h
i
g
h
er
p
r
io
r
ity
ta
s
k
is
w
a
itin
g
in
th
e
r
ea
d
y
q
u
eu
e
o
f o
n
e
c
o
r
e
w
h
ile
a
lo
w
er p
r
io
r
ity
ta
s
k
is
s
elec
ted
to
ex
ec
u
te
o
n
a
n
o
th
er c
o
r
e”.
[
1
2
]
n
–
n
u
m
b
er
o
f
tas
k
s
a
n
d
T
i
-
i
th
T
ask
in
th
e
ce
n
tr
al
q
u
e
u
e
Fig
u
r
e
2
.
Glo
b
al
Sch
e
m
e
w
i
th
3
co
r
es a
n
d
a
ce
n
tr
alize
d
s
ch
e
d
u
ler
I
n
th
is
s
ch
e
m
e,
ta
s
k
s
ar
e
n
o
t
a
l
w
a
y
s
f
ix
ed
to
a
p
ar
tic
u
lar
co
r
e.
Mig
r
atio
n
is
a
f
ea
t
u
r
e
w
h
er
e
task
s
ca
n
b
e
m
o
v
ed
f
r
o
m
o
n
e
co
r
e
to
an
o
th
er
an
d
th
i
s
f
ea
t
u
r
e
is
s
u
p
p
o
r
ted
in
th
is
g
lo
b
al
s
ch
e
m
e.
E
v
en
d
u
r
in
g
t
h
e
tas
k
ex
ec
u
t
io
n
,
tas
k
s
ca
n
b
e
m
o
v
ed
f
r
o
m
o
n
e
co
r
e
to
an
o
t
h
er
.
Sc
h
ed
u
lin
g
s
tatic
p
r
io
r
it
y
ta
s
k
s
u
n
d
er
g
lo
b
al
s
ch
e
m
e
b
y
e
x
ten
d
i
n
g
u
n
ip
r
o
ce
s
s
o
r
R
M
alg
o
r
ith
m
e
x
p
er
i
m
e
n
ted
b
y
An
d
er
s
s
o
n
et
al
.,
[
1
1
]
.
C
o
n
s
id
er
a
s
ce
n
ar
io
w
h
er
ein
t
h
e
tas
k
T1
r
u
n
n
in
g
i
n
C
o
r
e1
is
p
r
ee
m
p
ted
b
y
h
i
g
h
p
r
io
r
ity
tas
k
T2
;
n
o
w
th
e
ce
n
tr
alize
d
s
ch
ed
u
ler
allo
ca
tes
T2
to
C
o
r
e1
an
d
p
u
ts
tas
k
T1
o
n
h
o
ld
u
n
til
a
n
y
co
r
e
b
ec
o
m
es
av
ai
lab
le.
On
ce
a
co
r
e
b
ec
o
m
es
av
ailab
le,
s
a
y
C
o
r
e2
an
d
if
tas
k
T1
is
cu
r
r
en
tl
y
t
h
e
h
ig
h
es
t
p
r
io
r
ity
ta
s
k
i
n
r
ea
d
y
q
u
e
u
e,
th
e
n
it
is
s
c
h
ed
u
led
to
r
esu
m
e
its
e
x
ec
u
tio
n
f
r
o
m
C
o
r
e2
.
T
h
is
s
ch
e
m
e
m
a
y
a
ls
o
b
e
r
ef
e
r
r
ed
to
as
ce
n
tr
alize
d
s
ch
e
m
e
-
as
it
m
ain
ta
in
s
a
ce
n
tr
al
ized
r
ea
d
y
q
u
eu
e
an
d
it
en
s
u
r
es
th
a
t
n
o
s
a
m
e
ta
s
k
is
b
ei
n
g
e
x
ec
u
ted
at
th
e
s
a
m
e
ti
m
e,
r
ed
u
n
d
an
tl
y
i
n
m
u
lti
p
le
co
r
es.
C
o
n
s
tr
ain
t
o
f
th
i
s
s
c
h
e
m
e
i
s
s
ca
lab
ili
t
y
i
n
s
en
s
e
o
f
a
m
o
u
n
t o
f
tas
k
s
a
n
d
co
r
es
-
a
s
i
n
g
le
s
ch
ed
u
ler
h
a
s
to
m
an
a
g
e.
4
.
2
.
P
a
rt
it
io
ned Sche
m
e
I
n
th
e
p
ar
titi
o
n
ed
s
c
h
e
m
e
(
Fi
g
u
r
e
3
)
,
th
e
tas
k
s
ar
e
allo
ca
ted
to
in
d
iv
id
u
al
co
r
es
s
ta
tica
ll
y
b
y
t
h
e
s
y
s
te
m
d
esi
g
n
er
a
n
d
h
e
n
ce
f
o
r
th
t
h
e
tas
k
s
ar
e
ex
ec
u
ted
o
n
l
y
i
n
t
h
eir
r
esp
ec
ti
v
e
d
esi
g
n
a
ted
co
r
es.
Sch
ed
u
l
in
g
i
s
f
i
x
ed
in
n
a
tu
r
e,
w
h
er
e
t
h
e
p
ar
titi
o
n
i
n
g
h
as to
b
e
d
ec
id
ed
d
u
r
i
n
g
t
h
e
d
esi
g
n
o
r
i
m
p
le
m
e
n
tati
o
n
p
h
ase.
T
h
e
p
ar
titi
o
n
in
g
s
c
h
e
m
e
i
s
p
r
ef
er
r
ed
to
g
lo
b
al
s
c
h
e
m
e,
as
s
c
h
ed
u
li
n
g
f
o
r
m
u
ltico
r
e
ca
n
b
e
s
ee
n
a
s
a
n
alg
o
r
ith
m
f
o
r
s
c
h
ed
u
li
n
g
o
n
s
in
g
le
co
r
e,
to
w
h
ic
h
a
g
r
ea
t
v
ar
iet
y
o
f
s
c
h
ed
u
li
n
g
al
g
o
r
ith
m
s
alr
ea
d
y
e
x
is
t
an
d
task
s
ar
e
e
x
ec
u
ted
o
n
l
y
o
n
th
e
s
a
m
e
d
e
s
ig
n
ated
co
r
e.
S
tatic
s
c
h
ed
u
li
n
g
u
n
d
er
p
ar
titi
o
n
ed
s
ch
e
m
e
w
as
ex
p
er
i
m
e
n
ted
in
liter
at
u
r
e
[
1
2
]
,
[
1
5
-
1
6
]
.
E
f
f
icien
c
y
o
f
a
llo
ca
tio
n
d
ep
en
d
s
o
n
t
h
e
d
esi
g
n
o
f
h
o
w
th
e
task
s
ar
e
allo
ca
ted
ac
r
o
s
s
t
h
e
co
r
es.
A
cc
u
r
atel
y
id
en
ti
f
y
in
g
w
h
ic
h
task
r
u
n
s
at
a
g
i
v
en
m
o
m
e
n
t
is
n
o
t
p
o
s
s
ib
le
an
d
th
is
m
ak
e
s
t
h
e
s
ch
e
m
e
v
u
l
n
er
ab
le
to
p
r
io
r
it
y
i
n
v
er
s
i
o
n
.
Hen
ce
it
is
t
h
e
d
esi
g
n
er
‟
s
r
esp
o
n
s
ib
ilit
y
to
e
n
s
u
r
e
th
a
t
n
o
t
w
o
ta
s
k
s
ar
e
r
ed
u
n
d
an
tl
y
e
x
ec
u
ted
i
n
d
if
f
er
en
t c
o
r
es.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
E
C
E
I
SS
N:
2
0
8
8
-
8708
Tr
en
d
s
in
Ta
s
k
A
llo
ca
tio
n
Tech
n
iq
u
es fo
r
Mu
ltico
r
e
S
ystem
(
A
r
u
n
K
u
ma
r
S
u
n
d
a
r
R
a
ja
n
)
3025
n
,
m
,
k
–
n
u
m
b
er
o
f
tas
k
s
allo
ca
ted
to
ea
ch
co
r
e
an
d
T
i
-
i
th
T
ask
o
f
t
h
at
co
r
e
Fig
u
r
e
3
.
P
ar
titi
o
n
ed
Sch
e
m
e
w
it
h
3
co
r
es a
n
d
ea
ch
co
r
e
h
a
v
in
g
a
n
in
d
i
v
id
u
al
s
ch
ed
u
ler
4
.
3
.
Dis
t
ribute
d
o
r
D
ec
ent
ra
lized
Sche
m
e
Dec
en
tr
alize
d
s
c
h
e
m
e
co
m
b
i
n
es
t
h
e
ad
v
a
n
ta
g
es
s
ee
n
in
g
lo
b
al
an
d
p
ar
titi
o
n
ed
s
c
h
e
m
e,
th
er
eb
y
r
ed
u
cin
g
p
r
io
r
ity
i
n
v
er
s
io
n
a
n
d
at
th
e
s
a
m
e
ti
m
e
i
m
p
r
o
v
i
n
g
t
h
e
s
y
s
te
m
p
er
f
o
r
m
a
n
ce
.
I
n
th
e
d
ec
en
tr
alize
d
s
ch
e
m
e
(
Fi
g
u
r
e
4
)
,
th
er
e
ar
e
tw
o
lev
e
ls
o
f
s
ch
ed
u
ler
.
No
r
m
all
y
,
th
e
le
v
el
s
o
f
s
c
h
ed
u
ler
ar
e
r
ef
er
r
ed
as
L1
an
d
L2
.
L
ev
el
1
s
c
h
ed
u
ler
(
L1
)
is
s
i
m
ilar
to
th
e
o
n
e
i
n
ce
n
t
r
alize
d
s
ch
e
m
e
a
n
d
its
d
u
t
y
is
to
allo
ca
te
th
e
d
y
n
a
m
icall
y
q
u
eu
ed
u
p
tas
k
s
t
o
o
n
e
o
f
th
e
co
r
es
b
ased
o
n
th
e
av
ailab
ilit
y
.
L
e
v
el
2
s
ch
ed
u
ler
(
L2
)
is
s
p
ec
if
ic
to
ea
ch
co
r
e
an
d
it h
an
d
les t
h
e
task
s
th
at
ar
e
allo
ca
ted
to
it b
y
L1
[
1
2
]
,
[
1
8
]
.
Fig
u
r
e
4
.
Dec
en
tr
alize
d
Sch
e
m
e
w
it
h
3
L
2
s
c
h
ed
u
ler
s
a
n
d
1
L
1
s
ch
ed
u
ler
T
o
s
u
m
m
ar
ize,
L1
p
er
f
o
r
m
s
th
e
tas
k
allo
ca
tio
n
,
li
k
e
a
m
aster
o
f
all
co
r
es
an
d
L2
p
er
f
o
r
m
s
t
h
e
m
an
a
g
e
m
e
n
t
o
f
a
s
s
i
g
n
ed
co
r
e.
So
,
f
o
r
a
s
y
s
te
m
w
it
h
3
c
o
r
es,
th
er
e
w
i
ll
b
e
1
-
L1
a
n
d
3
-
L2
s
c
h
ed
u
ler
s
,
as
d
ep
icted
in
Fig
u
r
e
4
.
Sch
ed
u
le
r
L
2
also
m
ai
n
tai
n
s
i
n
f
o
r
m
atio
n
ab
o
u
t
task
s
p
er
tain
in
g
to
th
a
t
co
r
e,
lik
e
s
tate
o
f
th
e
tas
k
s
i
n
t
h
at
co
r
e,
n
u
m
b
er
o
f
tas
k
s
i
n
r
ea
d
y
an
d
w
ait
q
u
e
u
e
an
d
f
in
al
l
y
p
r
io
r
it
y
o
f
t
h
e
ta
s
k
s
.
Sin
ce
L1
is
th
e
m
aster
o
f
al
l
co
r
es,
it
ca
n
ac
ce
s
s
t
h
e
s
tat
u
s
in
f
o
r
m
a
tio
n
v
i
a
L2
b
ef
o
r
e
allo
ca
ti
n
g
a
ta
s
k
to
th
e
co
r
e.
I
n
t
h
is
d
ec
en
tr
alize
d
s
ch
e
m
e,
ef
f
icie
n
t
d
esi
g
n
o
f
th
e
L1
s
ch
ed
u
l
er
p
r
o
v
id
es
an
ef
f
ec
ti
v
e
s
o
l
u
tio
n
f
o
r
th
e
ta
s
k
s
ch
ed
u
lin
g
p
r
o
b
le
m
(
Ki
m
&
L
ee
(
2
0
1
5
)
)
.
T
h
e
L1
s
ch
ed
u
l
er
s
h
o
u
ld
b
e
ab
le
to
ef
f
icie
n
t
l
y
d
is
tr
ib
u
te
ta
s
k
s
a
m
o
n
g
co
r
es a
n
d
w
it
h
m
i
n
i
m
a
l o
v
er
h
ea
d
.
5.
T
ASK
A
L
L
O
CA
T
I
O
N
A
L
G
O
RIT
H
M
S
W
ith
a
clea
r
v
ie
w
o
n
t
h
e
all
o
ca
tio
n
s
ch
e
m
e
s
,
tech
n
iq
u
es
t
o
h
an
d
le
s
eq
u
en
tial
co
d
e
in
m
u
ltit
h
r
ea
d
ar
ch
itect
u
r
e
an
d
i
m
p
licit
d
ep
en
d
en
cie
s
t
h
at
w
o
u
ld
ar
is
e;
n
ex
t
s
tep
i
s
to
u
n
d
er
s
ta
n
d
t
h
e
alg
o
r
ith
m
s
.
T
h
is
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
0
8
8
-
8708
I
J
E
C
E
Vo
l.
6
,
No
.
6
,
Dec
em
b
er
2
0
1
6
:
3
0
1
8
–
30
30
3026
Sectio
n
b
e
g
i
n
s
w
it
h
i
n
tr
o
d
u
ct
io
n
to
t
h
e
ter
m
i
n
o
lo
g
ie
s
u
s
ed
in
m
a
th
e
m
atica
l
r
ep
r
esen
ta
ti
o
n
o
f
an
alg
o
r
it
h
m
,
f
o
llo
w
ed
b
y
t
h
e
co
r
e
allo
ca
tio
n
alg
o
r
it
h
m
s
t
h
at
ca
n
b
e
u
s
ed
to
d
is
tr
ib
u
te
task
s
b
et
w
ee
n
t
h
e
co
r
es.
C
o
n
s
id
er
a
m
u
ltico
r
e
s
y
s
te
m
S
w
it
h
n
co
r
es
an
d
ea
c
h
co
r
e
is
d
en
o
ted
as
C
i
,
f
o
r
all
i
=
1
to
n
.
L
et‟
s
as
s
u
m
e
t
h
at
t
h
i
s
m
u
l
tico
r
e
s
y
s
te
m
S
o
r
g
an
izes
t
h
e
p
r
o
g
r
a
m
i
n
to
m
tas
k
s
a
n
d
ea
ch
ta
s
k
is
d
en
o
ted
as
T
j
,
f
o
r
all
j
=
1
to
m
w
i
th
co
r
r
esp
o
n
d
in
g
ex
ec
u
tio
n
ti
m
e
E
j
an
d
task
p
r
io
r
ity
P
j
.
B
ased
o
n
th
e
ex
ec
u
tio
n
ti
m
e
E
j
,
th
e
ex
p
ec
ted
r
e
m
ain
in
g
e
x
ec
u
t
io
n
ti
m
e
[
E
R
T
]
o
f
th
e
ta
s
k
o
n
a
p
ar
ticu
lar
co
r
e
C
i
an
d
th
e
e
x
p
ec
t
ed
s
tar
t ti
m
e
[
E
ST
]
o
f
th
e
n
e
w
tas
k
th
a
t
w
ill b
e
all
o
ca
ted
b
y
L1
to
th
e
co
r
e
C
i
ca
n
b
e
ca
lcu
lated
.
5
.
1
.
Co
re
a
llo
ca
t
io
n
t
ec
hn
iqu
es
I
n
th
i
s
p
ar
t,
alg
o
r
ith
m
s
f
o
r
d
ec
en
tr
alize
d
s
c
h
e
m
e
w
i
th
d
y
n
a
m
ic
ta
s
k
i
n
f
lo
w
ar
e
p
r
esen
ted
(
Fig
u
r
e
5
)
.
R
o
le
o
f
t
h
ese
al
g
o
r
ith
m
s
is
t
o
d
y
n
a
m
icall
y
s
elec
t
a
co
r
e
an
d
allo
ca
te
tas
k
s
to
t
h
e
s
e
le
cted
co
r
e.
Var
io
u
s
alg
o
r
ith
m
s
p
er
tai
n
i
n
g
to
t
h
e
s
t
u
d
y
ar
e
d
is
cu
s
s
ed
as
f
o
llo
w
s
.
LB
-
L
o
ad
B
alan
ce
;
NT
WP
-
Nu
m
b
er
o
f
T
ask
s
,
W
aitin
g
ti
m
e
an
d
P
r
io
r
ity
M
NT
-
Min
i
m
u
m
N
u
m
b
er
o
f
T
ask
s
;
RR
-
R
o
u
n
d
R
o
b
in
Fig
u
r
e
5
.
A
llo
ca
tio
n
Sch
e
m
e
a
n
d
Ass
o
ciate
d
A
l
g
o
r
ith
m
5
.
1
.
1
.
Ro
un
d Ro
bin
(
RR)
a
lg
o
rit
hm
I
n
R
o
u
n
d
R
o
b
in
alg
o
r
it
h
m
,
ev
er
y
tas
k
is
tr
ea
ted
w
it
h
eq
u
al
p
r
io
r
ity
an
d
j
o
b
o
f
L1
s
ch
ed
u
ler
is
to
d
is
tr
ib
u
te
t
h
e
ta
s
k
s
,
a
s
a
n
d
w
h
en
t
h
e
y
ar
r
iv
e,
to
d
i
f
f
er
en
t
co
r
es
o
n
e
b
y
o
n
e.
P
s
eu
d
o
co
d
e
f
o
r
th
e
R
R
al
g
o
r
ith
m
is
p
r
esen
ted
in
Alg
o
r
it
h
m
3
.
F
o
r
ex
a
m
p
le,
I
f
ta
s
k
„
T
j
‟
a
r
r
ives
fir
s
t,
s
ch
e
d
u
ler
a
llo
ca
tes
th
is
ta
s
k
to
C
o
r
e
„
C
i
‟
fo
llo
w
ed
b
y
ta
s
k
„
T
j
+
1
‟
to
co
r
e
„C
i+
1
‟
a
n
d
s
o
o
n
.
Initialize
n
number of Cores(
C)
m
number of Tasks
to be allocated(T)
i
core number
for
each task ‘j’
do until
‘j’
is equal to
‘m’
if
('i' is less than or equal to 'n')
do
assign Task ‘T
j
’
to
Co
re
‘
C
i
’
increment ‘i’ to select next Core
elsedo
reinitialize ‘i’ to select first core
end for
A
lg
o
r
ith
m
3
.
Th
e
R
o
u
n
d
R
o
b
i
n
a
lg
o
r
ith
m
fo
r
„
m‟
ta
s
ks a
cro
s
s
„
n
‟
co
r
es.
I
n
th
i
s
r
o
u
n
d
r
o
b
in
f
as
h
io
n
,
allo
ca
tio
n
d
ep
en
d
s
o
n
l
y
o
n
t
h
e
ar
r
iv
al
o
r
d
er
o
f
th
e
tas
k
s
.
P
r
io
r
ity
i
s
ig
n
o
r
ed
as a
ll tas
k
s
ar
e
tr
ea
ted
eq
u
al
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
E
C
E
I
SS
N:
2
0
8
8
-
8708
Tr
en
d
s
in
Ta
s
k
A
llo
ca
tio
n
Tech
n
iq
u
es fo
r
Mu
ltico
r
e
S
ystem
(
A
r
u
n
K
u
ma
r
S
u
n
d
a
r
R
a
ja
n
)
30
27
5
.
1
.
2
.
M
ini
m
u
m
Nu
m
b
er
o
f
T
a
s
k
s
(
M
NT
)
a
lg
o
rit
h
m
I
n
MN
T
alg
o
r
ith
m
,
j
o
b
o
f
th
e
L1
s
ch
ed
u
ler
is
to
d
is
tr
ib
u
t
e
task
s
to
th
e
co
r
e
co
n
tain
i
n
g
m
in
i
m
u
m
n
u
m
b
er
o
f
tas
k
s
alr
ea
d
y
allo
c
ated
[
1
2
]
.
I
n
th
i
s
al
g
o
r
ith
m
,
a
l
lo
ca
tio
n
is
b
ased
o
n
t
h
e
ar
r
i
v
al
o
r
d
er
o
f
tas
k
s
a
n
d
p
r
io
r
ity
is
i
g
n
o
r
ed
.
P
s
eu
d
o
co
d
e
f
o
r
th
e
MN
T
alg
o
r
ith
m
i
s
p
r
esen
ted
in
A
l
g
o
r
it
h
m
4
.
Fo
r
ex
a
m
p
le,
I
f
C
o
r
e
„C
i
‟
h
a
s
5
ta
s
ks,
„C
i
+
1
‟
h
a
s
7
ta
s
ks
a
n
d
„C
i
+
2
‟
h
a
s
3
ta
s
ks.
Wh
en
ta
s
k
„
T
x
‟
a
r
r
ives
n
ex
t
,
s
ch
ed
u
ler a
llo
ca
tes th
is
ta
s
k
to
C
o
r
e
„C
i
+
2
‟,
w
h
ich
h
a
s
min
imu
m
n
u
mb
er o
f ta
s
ks.
MN
T
alg
o
r
ith
m
d
o
es
n
o
t
co
n
s
id
er
ab
o
u
t
th
e
v
ar
iatio
n
i
n
ex
ec
u
tio
n
ti
m
e
o
f
ea
ch
tas
k
,
w
h
ic
h
i
s
co
m
m
o
n
in
r
ea
l ti
m
e
s
y
s
te
m
s
.
Initialize
n
number of Cores(
C)
m
number of Tasks
already allocated to each core
i
core number
T
x
new task that ha
s arrived
for
each core ‘i’
do until
‘i’
is equal to
‘n’
index
Core number c
orresponding to
Min
(m
i
)
end for
assign Task ‘T
x
’
to
Co
re
‘
C
i
n
d
e
x
’
A
lg
o
r
ith
m
4
.
MN
T
a
lg
o
r
ith
m
w
h
ich
w
o
r
k
s
b
a
s
ed
o
n
min
i
mu
m
n
u
mb
er
o
f
a
llo
ca
ted
ta
s
ks
o
n
ea
ch
co
r
e.
5
.
1
.
3
.
Nu
m
ber
o
f
T
a
s
ks
,
Wa
it
ing
t
im
e
a
n
d P
rio
rit
y
(
NT
WP
)
a
lg
o
rit
h
m
NT
W
P
alg
o
r
ith
m
is
a
n
ex
te
n
s
io
n
o
f
MN
T
alg
o
r
ith
m
,
w
it
h
t
ask
p
r
io
r
it
y
b
ein
g
co
n
s
id
er
ed
b
ef
o
r
e
th
e
allo
t
m
e
n
t
is
m
ad
e.
Si
n
ce
r
ea
l
ti
m
e
s
y
s
te
m
,
u
s
ed
in
m
o
s
t
a
p
p
licatio
n
s
,
ca
n
n
o
t
tr
ea
t
all
task
s
to
h
av
e
eq
u
al
p
r
io
r
ity
–
tas
k
s
w
it
h
h
ig
h
er
p
r
io
r
ity
h
av
e
to
b
e
g
i
v
en
p
r
e
f
er
en
ce
i
n
ex
ec
u
tio
n
[
1
2
]
.
P
s
eu
d
o
co
d
e
f
o
r
th
e
NT
W
P
alg
o
r
ith
m
is
p
r
ese
n
ted
in
A
l
g
o
r
ith
m
5
.
I
n
NT
W
P
alg
o
r
ith
m
,
j
o
b
o
f
th
e
L1
s
ch
ed
u
ler
is
to
ch
ec
k
f
o
r
m
i
n
i
m
u
m
n
u
m
b
er
o
f
task
s
ass
i
g
n
ed
to
ea
ch
co
r
e,
an
d
th
en
ch
ec
k
s
f
o
r
co
r
es
w
it
h
m
in
i
m
u
m
E
R
T
an
d
f
in
all
y
c
h
o
o
s
es
t
h
e
co
r
e
w
i
t
h
m
i
n
i
m
u
m
s
u
m
o
f
task
p
r
io
r
ities
.
C
o
r
e
w
i
th
m
i
n
i
m
u
m
s
u
m
o
f
p
r
io
r
it
y
also
i
m
p
lies
t
h
at
th
is
co
r
e
co
n
tain
s
m
an
y
lo
w
p
r
io
r
it
y
task
s
co
m
p
ar
ed
to
o
th
er
co
r
es
an
d
th
er
e
i
s
a
h
i
g
h
p
o
s
s
ib
ilit
y
o
f
r
ed
u
ce
d
w
aiti
n
g
ti
m
e
f
o
r
h
i
g
h
p
r
io
r
it
y
tas
k
s
i
n
th
is
co
r
e.
NT
W
P
alg
o
r
ith
m
was d
esig
n
ed
in
o
r
d
er
to
r
ed
u
ce
p
r
io
r
ity
i
n
v
er
s
io
n
.
Initialize
n
number of Cores(
C)
m
i
number of Tasks
already allocated to each core
i
core number
T
x
new task that ha
s arrived
E
i
total execution
time of m
i
tasks in
each core
P
i
sum of prioritie
s of m
i
tasks in eac
h core
for
each core ‘i’
do until
‘i’
is equal to
‘n’
index
Core number c
orresponding to
Min
(m
i
)
flag
0
if
there are multiple values for ‘index’
do
E
i
=
Sum
(execution
times of tasks m
i
)i
n
c
or
e
index_1 = Compute
Min
(E
i
)
flag
1
if
there are multiple values for ‘index_1’
do
Pi =
Sum
(
priorities of task m
i
)in core
index_2 = Compute
Min
(P
i
)
flag
2
end for
Evaluation Warning : The document was created with Spire.PDF for Python.