Partitioning regular computational graphs

When massive applications are considered for parallel processing, or when the parallel machine is small compared to the potential parallelism of the application, usual methods for implementation have to reduce the associated computational graph by means of compaction or partitioning. In the field of signal processing, some huge applications composed of array processing operations in nested loops are endowed with a strong regularity. The purpose here is to detect and measure this regularity from the analysis of the application program, and use this information for partitioning, i.e. to aggregate or superpose the tasks and dependence vectors that repeat several/many times in the graph. The class of the applications studied ought first to be restricted to programs composed with sequences of loop nests and an adequate model is therefore defined. Using the loop parameters in the model, some necessary conditions must then be established for periodic dependence constraints. Then, the whole graph must be processed and the best program granularity proposed to the application designer from program analysis. A small example regular graph is processed as a first validation of the approach.