Browsing by Author "CHANG, PY"

Now showing 1 - 4 of 4

A FAMILY OF EFFICIENT REGULAT ARRAYS FOR ALGEBRAIC PATH PROBLEM
(1994-07-01)
CHANG, PY
;
TSAY, JC
;
交大名義發表
;
工學院
;
National Chiao Tung University
It has been shown that the method of decomposing a dependence graph into multiple phases with appropriate m-phase schedule function is useful for designing faster regular arrays for matrix multiplication and transitive closure. In this paper, we will further apply this method to design several parallel algorithms for Algebraic Path Problem and derive N x N 2-D regular arrays with execution time [9N/2] - 2 (cylindrical array and orthogonal one) and 4N - 2 (spherical one).
DESIGN OF EFFICIENT REGULAR ARRAYS FOR MATRIX MULTIPLICATION BY 2-STEP REGULARIZATION
(1995-02-01)
TSAY, JC
;
CHANG, PY
;
交大名義發表
;
工學院
;
National Chiao Tung University
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).
DESIGN OF SPACE-OPTIMAL REGULAR ARRAYS FOR ALGORITHMS WITH LINEAR SCHEDULES
(1995-05-01)
TSAY, JC
;
CHANG, PY
;
交大名義發表
;
工學院
;
National Chiao Tung University
The problem of designing space-optimal 2D regular arrays for N x N x N cubical mesh algorithms with linear schedule ai + bj + ck, 1 less than or equal to a less than or equal to b less than or equal to 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 less than or equal to c, which are dealt with by the first processor allocation method, space-optimal designs can always be obtained in which the number of processing elements is equal to N-2/c. 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.
SOME NEW DESIGNS OF 2-D ARRAY FOR MATRIX MULTIPLICATION AND TRANSITIVE CLOSURE
(1995-04-01)
TSAY, JC
;
CHANG, PY
;
交大名義發表
;
工學院
;
National Chiao Tung University
In this paper, 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 [(3N-1)/2] execution times for matrix multiplication can be obtained, Meanwhile, we can derive a 2-D array with 4N-2 execution time 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.