Browsing by Author "TSAY, JC"

Now showing 1 - 17 of 17

A COST-OPTIMAL SYSTOLIC ALGORITHM FOR GENERATING SUBSETS
(1994)
TSAY, JC
;
LEE, WP
;
交大名義發表
;
工學院
;
National Chiao Tung University
Subset generation, generating all 2'' - 1 subsets of an n-element set, is frequently necessary in combinatorial algorithms. In this paper, we shall utilize Moldovan's space-time mapping methodology to design a systolic algorithm for the subset generation problem. The algorithm is a cost-optimal design and can generate all subsets in lexicographic order. Since it can be run on a simple linear systolic array, it is amenable to VLSI implementation.
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).
A SYSTOLIC DESIGN FOR GENERATING COMBINATIONS IN LEXICOGRAPHIC ORDER
(1990-01-01)
TSAY, JC
;
LIN, CJ
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
A SYSTOLIC DESIGN FOR GENERATING PERMUTATIONS IN LEXICOGRAPHIC ORDER
(1994-05-01)
LEE, WP
;
TSAY, JC
;
工學院
;
College of Engineering
In this paper, we shall design a systolic algorithm for generating all N! permutations of N objects. The algorithm is time efficient, generates all permutations in lexicographic order, and can be executed on a simple computation model (systolic array). Furthermore, because the algorithm is systolic, it is suitable for VLSI implementation.
A SYSTOLIC GENERATION OF COMBINATIONS
(1989)
LIN, CJ
;
TSAY, JC
;
應用數學系
;
Department of Applied Mathematics
ADAPTABLE QUAD TREE TECHNIQUES
(1993-07-01)
SU, SJ
;
KUO, YS
;
TSAY, JC
;
資訊工程學系
;
Department of Computer Science
The quad tree is a widely used data structure for region queries. Quad trees normally perform reasonably efficient on the majority of layout data, but could perform very poor on certain extreme data. This demonstrates the quad tree's deficiency in its adaptability to peculiar layout data. We address two aspects of the adaptability problem. On the one hand, the threshold of a quad tree is allowed to change in order to match the global complexity of the layout. On the other hand, a new quad subdivision criterion is developed which adapts a quad tree to the nonuniform distribution of objects with various sizes. Experiments have indicated that the two techniques are indeed useful in coping with the peculiarity of extreme layout data.
AN OPTIMAL PARALLEL ALGORITHM FOR GENERATING PERMUTATIONS IN MINIMAL CHANGE ORDER
(1994-03-01)
TSAY, JC
;
LEE, WP
;
交大名義發表
;
工學院
;
National Chiao Tung University
Permutation generation is an important problem in combinatorial computing. In this paper we present an optimal parallel algorithm to generate all N! permutations of N objects. The algorithm is designed to be executed on a very simple computation model that is a linear array with N identical processors. Because of the simplicity and regularity of the processors, the model is very suitable for VLSI implementation. Another advantageous characteristic of this design is that it can generate all the permutations in minimal change order.
AN OPTIMAL PARALLEL ALGORITHM FOR GENERATING PERMUTATIONS IN MINIMAL CHANGE ORDER
(1994-03-01)
TSAY, JC
;
LEE, WP
;
資訊工程學系
;
Department of Computer Science
Permutation generation is an important problem in combinatorial computing. In this paper we present an optimal parallel algorithm to generate all N! permutations of N objects. The algorithm is designed to be executed on a very simple computation model that is a linear array with N identical processors. Because of the simplicity and regularity of the processors, the model is very suitable for VLSI implementation. Another advantageous characteristic of this design is that it can generate all the permutations in minimal change order.
DESIGN AND IMPLEMENTATION OF A CHINESE TERMINAL CONTROLLER
(1981)
TSAY, JC
;
CHANG, YM
;
交大名義發表
;
工學院
;
National Chiao Tung University
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.
GENERATING FUNCTION AND EQUIVALENT TRANSFORMATION FOR SYSTOLIC ARRAYS
(1989-05-01)
TSAY, JC
;
HOU, YC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
ON EQUIVALENT SYSTOLIC DESIGNS OF LU DECOMPOSITION AND ITS ALGEBRAIC REPRESENTATION
(1992-12-01)
HOU, YC
;
TSAY, JC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
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 ASPECTS OF PARALLEL ALGORITHM DESIGN FOR MATRIX MULTIPLICATION
(1992-03-01)
TSAY, JC
;
SY, Y
;
工學院
;
College of Engineering
In this paper, some combinatorial characteristics of matrix multiplication on regular two-dimensional arrays are studied. From the studies, we 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, we find that there is a transformation procedure to transform a cylindrical array to a two-layered mesh array.
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.
SYSTOLIC FLOW
(1990-03-01)
TSAY, JC
;
YUAN, S
;
資訊工程學系
;
Department of Computer Science
UNIFIED APPROACH TO DESIGNING PARALLEL WINOGRAD ALGORITHMS
(1994-05-01)
YUAN, S
;
TSAY, JC
;
交大名義發表
;
工學院
;
National Chiao Tung University
Although the recurrence equation for the Winograd algorithm is uniform, no unified approach has been proposed to design parallel Winograd algorithms. In the paper the authors propose a unified approach to designing parallel Winograd algorithms. Using this approach, several parallel algorithms are designed. These algorithms are executed on regular arrays including conventional systolic arrays and nonplanar regular arrays. A comparison of their performance is given.