Information Technology Reference
In-Depth Information
Algorithm 1.
CalculatePriority
1:
p
data
ₐ CalculateDataPriority
(
A
)
2:
p
available
ₐ CalculateAvailablePriority
(
A
)
3:
for all
node n
∈
A
do
4:
p
data
+
p
available
1
p
[
n
]
ₐ
// x is the number of available MB nodes in
A
x
5:
end for
Algorithm 2.
CalculateDataPriority
1:
Q ₐ
n∈A
parent
[
n
]
2:
CFT
L
2
ₐ
min
L
2
˄
L
2
[
n
];
CFT
L
1
ₐ
min
L
1
˄
L
1
[
n
];
cachePriority ₐ none
n
∈
Q
∩
n
∈
Q
∩
3:
if
CFT
L
2
<t
L
2
then
4:
cachePriority ₐ L
2
5:
else if
CFT
L
1
<t
L
1
then
6:
cachePriority ₐ L
1
7:
end if
8:
if
cachePriority
!=
none
then
9:
for all
node n
∈
A
do
10:
p
data
[
n
]
ₐ
parent
[
n
]
˄
cachePriority
[
p
]
min
p
∈
11:
end for
12:
else
13:
for all
node n
∈
A
do
14:
p
data
[
n
]
ₐ
(
l ∗|nodes
[
L
2]
∩ parent
[
n
]
|
+
|nodes
[
L
1]
∩ parent
[
n
]
|
)
/ |parent
[
n
]
|
15:
end for
16:
end if
17:
return
p
data
Algorithm 3.
CalculateAvailablePriority
1:
for all
node n
∈
A
do
2: p
outgoing
[n]
ₐ
no of outgoing edges from current available node
3:
if
s
n
is source
then
4: p
source
[n]
ₐ
no of spatial neighbours of this node processed
5: p
parallel
[n]
ₐ k ∗ p
source
[
n
]+(1
− k
)
∗ p
outgoing
[
n
]
6:
else
7: p
parallel
[n]
ₐ p
outgoing
8:
end if
9:
end for
10:
11:
return
p
parallel
Algorithm 1 uses simple priority-based scheduling exploiting the factors dis-
cussed. There are two distinct priority components -
p
data
and
p
parallel
.
p
data
is
calculated based on the position of a node's parents in the cache hierarchy. A
node whose parent is in danger of being evicted from the L2 cache (obtained by
comparing the parent node's CFT with
t
L
2
) is given priority. If no parent is in
danger of being evicted from L2 cache, we then perform the same process for L1