Register Allocation with Variable Sizes

I have to solve a problem which is similar to register allocation, but
harder (NP-hard to be precise). The compiler has to allocate storage for
matrices (of known size) in memory. Since the matrices cannot all reside
in memory together (not enough memory) they must be transferred between
memory and disk as the program executes. The objective is to minimize the
amount of transfers.


(The application is a programming language to do calculations on matrices
as a basic data type.)


If the matrices were of identical size then this is the same as the
register allocation problem and it's not hard to solve. Because the
matrices have different sizes the problem is immediately NP-hard (actually
I think it's complete by transformation from PARTITION).


Has anyone out there in compiler-land had to solve such a problem, or seen
references to literature?


Alan Heirich
California Institute of Technology
heirich@caltech.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.