Transformation of nested loops to UREs

The first goal in our methodology is to transform an algorithm given in nested-loop form, which may include non-constant dependencies, to an equivalent URE with localized parametric DVs. The motivation for this starting point is also discussed in chapter 4. The applicability of such a transformation is restricted by the complexity of the index functions of the feedback variables. Therefore, our attention is focused on WSACs [20], which are characterized by identical linear index functions of the feedback variable. In this approach UREs are derived directly, in contrast to the technique described in chapter 4 where the dependence graph (DG) is extracted. 

Definitions of the fundamental terms used throughout this chapter are given next. The general form of a nested loop considered here is  

A variable that appears in both sides of a statement is called a feedback variable. Any element of the set A (F(i)) i G / is called a variable instance. Variables with common name but diiferent index functions are considered as 

Let a variable instance computed at a point ii use the value of a variable instance generated at another point i2 The vector d = i2-ii is called dependence vector. The dependence graph (DG) is a directed graph, where each node corresponds to a point i G and each edge corresponds to a DV joining two dependent points of the index space. 

In order to transform a nested loop with linear dependencies into an equivalent URE form, the propagation space of each variable should be determined and the localization of the data movements should be performed. Generally, propagation exists when the propagation space of a variable instance contains more than one node of the index space. The propagation in the index space can take two different forms, namely broadcast operations and Jan-in . More specifically, broadcasting occurs when a value of an instance is distributed to many nodes of the space, while fan-in occurs when different values of an instance are concentrated from many nodes to one node. The latter is the main feature of WSACs [20]. 

---