Graph Transformation Algorithms for Array Memory Optimization in Applicative Languages

摘要

In applicative language implementations, the potential copying of array elements can severely restrict the efficiency of the run-time code. In many instances, copy avoidance can be achieved through memory preallocation. This Ph.D. dissertation presents a compile-time graph algorithm strategy, for use with the SISAL programming language, that identifies cases where preallocating memory storage locations for array aggregates is possible. The preallocation actions to be taken are specified by providing intermediate language graph transformations that designate the run-time creation of memory buffers prior to array creation. The preallocation analysis algorithms predict a significant savings in the execution time of selected sample programs; more than 90% of the array copying operations can be removed from existing unoptimized implementations. The results indicate that array memory allocation for some applicative language programs can be efficient. 93 refs., 58 figs., 6 tabs. (ERA citation 13:013879)