Word-level array design

The space-time mapping of the parametric URE derived in the previous step is accomplished by decomposing the index space to independent subsets of variable instances. The number of these subsets depends on the DVs and can be modified by alternative selection of the URE parameters. This results in a variety of array architectures in terms of size, PE utilization, and interconnection patterns. This method is complementary to the approaches introduced in chapters 3, 4, and 6, as indicated there. However, many of the proposed techniques can be combined. 

In most existing regular processor array synthesis methodologies [8,12, 19], the index space of a recurrence is viewed as an entity, while linear allocation and timing functions are used to determine the parallel execution of the algorithm. A different approach to the mapping problem is presented here, based on the existence of independent subsets of variables in the index space of many ap- 

Any point, i, of the index space can be expressed as an integer-coefBcient linear combination of the DVs, plus an integer initial vector im [15]  

For each a subset of the index space is defined. Any point of a subset can be used as an initial vector for this subset. Therefore, if No is the number of the different subsets of the index space, then only No initial vectors are required and thus m = 1,2. Nq 1. In general, the number of independent subsets is equal to the greatest common divisor of the minor determinants of the dependence matrix [25]. Let Ti = i t i) = 1, where i is a point of the index space and (i) is its execution time [5]. If G Ti, m = 1,2. No then any point of the index space can be written in the form of equation (9), each point of the index space belongs to one subset only, and there is no dependence between different subsets. 

The mapping of the normalized subsets is accomplished by the determination of a timing and an allocation function. The timing function is obtained by solving an integer programming problem for each subset. The problem constraints are 

---

Table 1 displays an orthogonal array of strength three because it contains each of the 23 = 8 level combinations of any set of three factors exactly twice. In other words, its projection onto any set of three factors consists of two replicates of the complete 23 factorial design. 

---