Tim Frink <plfriko@[EMAIL PROTECTED]
> writes:
>...
> I'm not sure if dynamic programming is an approach that I can apply to
> my problem [of deciding which blocks to move to faster memory]....
From your original posting, it is not clear to me which of the
following problems you want to solve (in each case, optimizing the
total speed of the program, which is dependent on the addresses of the
blocks):
(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.
(2) Make the same decisions as problem (1), but if an N-byte block is
moved to the fast memory, up to N padding bytes can be left in its
place in the slow memory. The actual number of padding bytes is an
additional output of the decision process.
(3) Solve some other even more general placement problem, where the
number of padding bytes is not limited to N, or padding bytes are also
allowed in the fast memory, or the blocks can be permuted into a
different order.
For the moment, I will assume you want to solve problem (1), both
because this seems closest to the way you initially stated the
problem, and because it is the simplest.
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.
This would lead to a dynamic programming solution using a
two-dimensional table, with one dimension indexed by block number and
the other dimension indexed by number of bytes.
The other piece of guidance I would offer is to look specifically at
the literature on dynamic programming solutions to the knapsack
problem, rather than just dynamic programming in general. Your
problem (or at least what I am taking to be your problem -- number 1
in my list) is a generalization of the 0-1 knapsack problem. Unlike
the standard problem, the items are in a sequence rather than a set
and the value of each item changes depending on how much of the
capacity of the knapsack is filled. However, the standard dynamic
programming approach to the knapsack problem still works.
|
