Information Technology Reference
In-Depth Information
- Macro-block type: Indicates the type of block size present, i.e. 4x4/8x8/
16x16.
- Position of macroblock dependency in memory hierarchy: For each depen-
dency of a macro-block, the position in the memory hierarchy (L1 cache, L2
cache or DRAM) where the dependency macroblock is present.
- Cache flush time: For each dependency of a macroblock, the value of ˄ .
4.1 Proposed Algorithm
Our heuristic method uses simple priority-based scheduling. It has a ready queue
A of macro-blocks that can be accessed by any processor. A processor that be-
comes idle accesses the ready queue, calculates the priority value of each macro-
block present in the queue using the algorithm described below and then chooses
the one having the highest priority for decoding. Priority of a macro-block de-
pends on the position of the macro-blocks in memory, their cache flush times
and the number of available macro-blocks in the ready queue. While assigning
priority, we take into account the following factors:
- Minimum cache flush time of L2 among all nodes ( CFT L 2 ): We examine each
node in A , one or more of whose parents reside in the L2 cache. For each node,
we compute the parent with minimum ˄ value (i.e. has the most chance of
being evicted), and find that node in A whose parent has the highest chance
of being evicted, i.e, the minimum ˄ value - we call this CFT L 2 .Wehave
a threshold value t L 2 , which we compare with CFT L 2 .If CFT L 2 is greater
than the threshold value, then we know that there are no nodes in the L2
cache that are at risk of being flushed. So, we are then free to choose which
node will be selected depending on other constraints. On the other hand, if
CFT L 2 is less than or equal to the threshold value, then we need to ensure
that those nodes which are about to be flushed are accessed quickly by the
decoder. The scheduler, therefore, needs to schedule the children of nodes
about to be flushed from L2 cache as quickly as possible.
- Minimum cache flush time of L1 among all nodes ( CFT L 1 ): As with L2, we
similarly use the threshold value t L 1 to compare with CFT L 2 .
- Memory access time of L1 and L2: We know that L1 has a much lower
memory access time as compared to L2. When there is no danger of any
required node to be flushed from L1 or L2, we assign higher priority to
nodes whose parents are in L1. The higher the number of parents in L1, the
higher is the priority of a node.
- Number of free nodes in the ready queue: One of our objectives is to ensure
that idle time of processor cores is reduced. So we aim to have enough nodes
in our available list so that processor cores remain busy in processing nodes.
When fewer nodes are present in the available list, we give more priority to
nodes that have more outgoing edges.
- For source nodes, i.e, nodes with no incoming edges, we give weightage to
the number of neighbours that have been processed. This ensures adjacent
nodes are processed at approximately similar times to maintain temporal
locality.
Search WWH ::




Custom Search