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
 
Search WWH ::




Custom Search