GLOBALLY OPTIMUM SELECTION OF MEMORY STORAGE PATTERNS.

Abstract

A problem of current interest in the use of today's supercomputers is how to store data so that it can be most efficiently accessed during vector operations. Algorithms, suitable for compiler implementation, that assign globally optimal storage patterns (shapes) to data structures are developed. A graph model is used to solve this problem, which is called the shapes problem. The operations and data structures of a program are represented by the nodes and arcs of a graph, respectively. Each node, representing an operation, is associated with a cost, and each are representing a data structure, can be assigned one of a set of shapes. The cost associated with each node is a function of the shapes assigned to the arcs touching that node. The cost for the whole graph is the sum of the costs of all nodes. Thus the globally optimal shape assignment is the one that minimizes the cost of the graph. Application of two of the algorithms to a numerical analysis problem involving matrices is demonstrated.