In this paper, we propose an enumeration method to check link conflicts in the mapping of n-dimensional uniform dependence algorithms with arbitrary convex index sets into k-dimensional processor arrays. Previous methods on checking the link conflicts had to examine either the whole index set or the I/O spaces whose size are O(N/sup 2n/) or O(N/sup n-1/), respectively, where N is the problem size of the n-dimensional uniform dependence algorithm. In our approach, checking the link conflicts is done by enumerating integer solutions of a mixed integer linear program. In order to enumerate integer solutions efficiently, a representation of the integer solutions is devised so that the size of the space enumerated is O((2N)/sup n-k/). Thus, our approach to checking link conflicts has better performance than previous methods, especially for larger k. For the special case k=n-2, we show that link conflicts can be checked by solving two linear programs in one variable.

The purpose of this paper is to describe a new method to design unidirectional modular extensible linear arrays for regular algorithms. The time complexity of our method is polynomial and depends only on the number of dimensions of the regular algorithm. The designed linear array is asymptotically optimal in space and time.

The data-flow graph (DFG) is an important graph-theoretic model for multiprocessor implementation of real-time digital signal processing (DSP) algorithms. Given a time schedule for a DFG, we consider the problem of the processor-optimal assignment for a fully static schedule. Previously, the solution of this problem was found by solving an integer programming problem. We propose a linear programming approach to solving the problem.

The problem of designing space-optimal 2D regular arrays for N/spl times/N/spl times/N cubical mesh algorithms with linear schedule ai+bj+ck, 1/spl les/a/spl les/b/spl les/c, and N=nc, is studied. Three novel nonlinear processor allocation methods, each of which works by combining a partitioning technique (gcd-partition) with different nonlinear processor allocation procedures (traces), are proposed to handle different cases. In cases where a+b/spl les/c, which are dealt with by the first processor allocation method, space-optimal designs can always he obtained in which the number of processing elements is equal to N/sup 2c. For other cases where a+b>c and either a=b and b=c, two other optimal processor allocation methods are proposed. Besides, the closed form expressions for the optimal number of processing elements are derived for these cases.>

A two-step regularization method in which first permutation sequences and then broadcast planes are selected is proposed to design various regular iterative algorithms for matrix multiplication. The regular iterative algorithms are then spacetime mapped to regular arrays, such as mesh, cylindrical, two-layered mesh, and orbital arrays. The proposed method can be used to design regular arrays with execution time of less than N (problem size).>

We present some new regular iterative algorithms for matrix multiplication and transitive closure. With these algorithms, by spacetime mapping the 2-D arrays with 2N-1 and upper bound [(3N-1)/2] execution times for matrix multiplication can be obtained. Meanwhile, we can derive a 2-D array with 4N-2 execution rime for transitive closure based on the sequential Warshall-Floyd algorithm. All these new 2-D arrays for matrix multiplication and transitive closure have the advantages of faster and more regular than other previous designs.>

The method of decomposing a dependence graph into multiple phases with an appropriate m-phase schedule function is useful for designing faster regular arrays for matrix multiplication and transitive closure. In this paper, we further apply this method to design several parallel algorithms for the algebraic path problem and derive N/spl times/N 2D regular arrays with execution times [9N/2]-2 (for the cylindrical array and the orthogonal one) and 4N-2 (for the spherical one).>

Algorithms which are to be mapped onto interconnecting processing elements in order to design a systolic array are conventionally represented by graphs or networks. This paper introduces the concept of algebraic representation and uses a generating function to represent a systolic array.

Some combinatorial characteristics of matrix multiplication on regular two-dimensional arrays are studied. From the studies, the authors are able to design many efficient varieties of the cylindrical array and the two-layered mesh array for matrix multiplication. To design a cylindrical array for matrix multiplication, a systematic design procedure is proposed. In this design procedure, Latin square (a special type of matrix) plays an important role. To design a two-layered mesh array, it is found that there is a transformation procedure to transform a cylindrical array to a two-layered mesh array.>