> (1) For each block, make a yes/no decision on whether to move it to
> the faster memory. The address of each block within its memory (the
> slow memory or the fast memory) is equal to the sum of the size of the
> preceding blocks that were assigned to the same memory. That is, the
> order of the blocks within each memory remains the same as in the
> original layout and no padding bytes are introduced.
Sure, the order remains the same. However, the block addresses might
change due to additional jump instructions that I have to insert to
preserve correct program flow. Let's say I have this contiguous
allocation of blocks in memory:
A B C D
and b is the implicit successor, i.e. it's on the fall-through edge.
Further, it should be assumed that all blocks start at an 8byte
alignment boundary so that no penalties are incurred during fetching.
Moving B to faster memory, I must add an additional jump instruction
at the end of block A to direct control flow to B. This addition
instruction changes to increases the addresses of the following blocks
C and D which might lead to the worst-case situation where for example
block D (or some of its later successors) now starts at an address
that is 16bit before a 8byte address boundary. In that case the
processor takes longer to fetch instructions from that block as was
before the movement of B. And these domino effects might happen
everywhere in the code when I add some new jumps. Thus, its very hard
to restrict the movement of a single block to some local range. What I
need is some oracle that is able to predict the global effect on the
code when a small local change was done.
> For this problem, dynamic programming is indeed a useful technique.
> Consider working sequentially through the list of blocks, deciding for
> each one whether to move it to fast memory or not. The optimal decision
> on whether to move block k does not depend on the specific choices you
> made regarding each of blocks 1 through k-1. Instead, it just depends
> on the total size in bytes of the blocks in the range from 1 through k-1
> that were selected for fast memory. This total size is what determines
> all three relevant facts: (1) how many bytes of the fast memory's
> capacity are still available for blocks k and onward, (2) what the
> address of block k would be if left in the slow memory, (3) what the
> address of block k would be if moved to the fast memory.
Ok, this make sense if I decide "in advance" what blocks will be
moved. I always assumed a given memory layout where I tries to
successively move blocks without a "total" view at the entire set of
blocks.
However, I still see the problem with the additional jump instructions
that I have to add. I'm unfamiliar with dynamic programming (yes, I
will study some literature on this soon :-)), so maybe you can answer
my question. Can I express in the formulation of the knapsack problem
the fact that the movement of block N+1 to faster memory will lead to
an increased code (by the jump) of block N?
And I'm still not very sure how to integrate my misalignment problem
into the problem of dynamic programming. Let's say I have tree blocks
A B C D. I could in advance compute the execution time of each block
when it was placed in slow memory or in fast memory. The most
efficient way would be to put either the entire text section of the
code into the slow or the fast memory to get the two reference values
for that. However, these values are only true if considered as one
set. When I decide to move block B to faster memory, I can't guarantee
for block D (which was decided to stay in slow memory) that it's run
time is what was decided in advance since it might incur a fetch
misalignment penalty slowing down its execution below the values that
was determined when B was still between A and C and D was not
misaligned. Can such a situation be also modeled with dynamic
programming?
|
