An automated method for memory allocation using acyclic digraphs

Abstract

In many cases more effective memory utilization in digital computers can be accomplished through the use of memory management techniques such as virtual memory and/or the overlay facilities of the linkage editor. Methodologies necessary to reduce the amount of effort required to use the overlay facilities are presented. In addition, a method is given which can reduce the size of a program's working set, resulting in more effective hardware utilization in a virtual memory environment. The algorithms are developed using an acyclic digraph as an abstract representation of the program. A topological order is used as the basis for the node numbering scheme, producing an upper triangular adjacency matrix. The upper triangular adjacency matrix is used as the starting point of the method. The adjacency matrix is converted into a minimal connectivity matrix which exhibits the same transitive relationships. The paths through the minimal connectivity graph are used for placing program segments in memory. The minimal connectivity matrix is used directly when the program is to be used in virtual memory. The method is extended for use with overlays by producing the path matrix and using the columns as exclusion vectors to prevent exclusive calls between overlay segments. In special cases the use of duplicate segments within the program is shown to increase efficiency with the use of overlayed or virtual memory.