In the framework of fully permutable loops, tiling is a compiler technique (also known as ‘loop blocking’) that has been extensively studied as a source-to-source program transformation. Little work has been devoted to the mapping and scheduling of the tiles on to physical parallel processors. We present several new results in the context of limited computational resources and assuming communication–computation overlap. In particular, under some reasonable assumptions, we derive the optimal mapping and scheduling of tiles to physical processors. Copyright © 1999 John Wiley & Sons, Ltd.

This paper is devoted to a low-complexity algorithm for retiming circuits without cycles, i.e., those whose network graph is a direct acyclic graph (DAG). On one hand, DAGs have a great practical importance, as shown by the on-line arithmetic circuits used as a target application in this paper. On the other hand, retiming is a costly design optimization technique, in particular when applied to large circuits. Hence the need to design a specialized retiming algorithm to handle DAGs more efficiently than general-purpose retiming algorithms. Our algorithm dramatically improves on current solutions in the literature. We gain an order of magnitude in the worst case complexity, and we show convincing experimental results at the end of this paper.

This paper elaborates on a new view on software pipelining, called decomposed software pipelining. The approach is to decouple the problem into resource constraints and dependence constraints. Resource constraints management amounts to scheduling an acyclic graph subject to resource constraints for which an efficiency bound is known, resulting in a bound for loop scheduling. The acyclic graph is obtained by cutting some particular edges of the (cyclic) dependence graph. In this paper, we cut edges in a different way, using circuit retiming algorithms, so as to minimize both the longest dependence path in the acyclic graph, and the number of edges in the acyclic graph. With this technique, we improve the efficiency bound given for Gasperoni and Schwlegelshohn algorithm, and we reduce the constraints that remain for the acyclic problem. We believe this framework to be of interest because it brings a new insight into the software problem by establishing its deep link with the circuit retiming problem.

In the framework of perfect loop nests with uniform dependences, tiling has been extensively studied as a source-to-source program transformation. Little work has been devoted to the mapping and scheduling of the tiles on to physical processors. We present several new results in the context of limited computational resources, and assuming communication-computation overlap. In particular, under some reasonable assumptions, we derive the optimal mapping and scheduling of tiles to physical processors.

In this paper we build upon results of D.A. Padua and M.J. Wolfe (1986), who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such transformations. Then, given a loop nest, we aim at determining which statements should be transformed so as to break artificial cycles involving anti or output dependences. The problem of finding the mininum number of statements to be transformed is shown to be NP-complete in the strong sense, and we propose two efficient heuristics.

lVe present yet another heuristic for the software pipelining problem.This heuristic brings a new insight to the software pipelining problem by establishing its deep link with the circuit retiming problem.Also, in the single resource class case, our new heuristic is guaranteed, with a better bound than that of [6].Finally, we point out that, in its simplest form, our algorithm has a lower complexity.

The subject of this article is a hyperplane partitioning problem applied to perfect loop nests. This work is aimed at increasing the computation granularity to reduce the overhead due to communication. This study is different from previous work as it takes redundant communication into account. We propose an algorithm giving the optimal solution and various examples to show the validity of this report.