Graph Analysis and Transformation Techniques for Runtime Minimization in Multi-Threaded Architectures

This paper describes a method of analysis for detecting and minimizing memory latency using a directed data dependency graph produced from a compiler. These results are applicable to the development of methods for the optimal generation of instruction threads to be executed on a multi-threaded, datadriven architecture. The resulting runtime reductions are accomplished by minimizing memory access times by individual processing elements. Additionally, these analysis methods can be used to predict measures of achievable parallelism for a given program graph which can be exploited by a reconfigurable, multi-threaded architecture. 1 Introduction This paper describes a method for the detection and minimization of memory latencies in a datadriven, multi-threaded architecture using a directed graph which contains program data dependency information. This method consists of first analyzing the data dependency graph followed by the application of transformation rules that modify the content of..