Campus Event Calendar

Event Entry

What and Who

Algorithms for Compile-Time Memory Optimization

Jordan Gergov
Max-Planck-Institut für Informatik
AG1 Mittagsseminar
AG 1, AG 2  
AG Audience

Date, Time and Location

Wednesday, 9 December 98
30 Minutes


Let P be a program in a structured programming language, eg Pascal.

The compiler can use control-flow analysis and similar techniques to
determine pairs of source-code objects in P (eg arrays, records) such
that the objects in each pair cannot ``interfere'' with each other at
run-time and, hence, can share memory. The Compile-Time Memory Allocation
problem is to construct a memory allocation for the objects in P such that
the memory usage is minimized and memory regions of objects that do not
``interfere'' at run-time are allowed to overlap.

We propose the first polynomial-time algorithm for this problem with a
performance guarantee as well as a new and simple O(nlog(n)) time
3-approximation for off-line Dynamic Storage Allocation (DSA). The latter
result improves the best previous approximation ratio of 5 for DSA.


Jordan Gergov
(0681) 9325-528
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Memory Allocation, Compiler Optimization, Approximation Algorithms
This talk is a short presentation of my SODA'99 results.