Register Allocation with Variable Sizes (Alan Heirich)
Sun, 18 Sep 1994 03:52:08 GMT

          From comp.compilers

Related articles
Register Allocation with Variable Sizes (1994-09-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Alan Heirich)
Keywords: registers, optimize
Organization: California Institute of Technology
Date: Sun, 18 Sep 1994 03:52:08 GMT

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

Post a followup to this message

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