Browsing by Author "Tsay, JC"

Now showing 1 - 6 of 6

An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays
(1999-07-01)
Ke, JY
;
Tsay, JC
;
資訊工程學系
;
Department of Computer Science
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-dimensianal 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-2n) or O(Nn-1), respectively, where hr 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)(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 he checked by solving two linear programs in one variable.
An approach to designing modular extensible linear arrays for regular algorithms
(1998-02-01)
Chang, PY
;
Tsay, JC
;
工學院
;
College of Engineering
The purpose of this paper is to describe a new method to design unidirectional modular extensible linear arrays far 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.
Designing lower-dimensional regular arrays for algorithms with uniform dependencies
(1996-02-25)
Tsay, JC
;
Chang, PY
;
交大名義發表
;
工學院
;
National Chiao Tung University
In this paper, we will propose a polynomial-time method to design m-dimensional regular arrays for n (n greater than or equal to m + 1) dimensional algorithms with uniform dependencies, regular algorithms. The proposed method has two steps: the first one is to transform an independently partitioned regular algorithm to a new one, which has an identity dependence matrix. We call this step identity transformation, which is an affine one. In the second step, we propose a spacetime mapping in a fixed form to map the new regular algorithm to a lower-dimensional regular array. Thus, an affine spacetime mapping is constructed by combining the identity transformation and the fixed form's spacetime mapping together. With the proposed affine spacetime mapping, the original regular algorithm can be mapped to a lower-dimensional regular array in polynomial time, which depends only on the number of dimensions of the regular algorithm. Meanwhile, the designed regular array is asymptotically optimal in time and space. (C) 1996 Academic Press, Inc.
Finding space-optimal linear array for uniform dependence algorithms with arbitrary convex index sets
(1998-12-01)
Ke, JY
;
Tsay, JC
;
資訊工程學系
;
Department of Computer Science
The mapping of an n-dimensional uniform dependence algorithm onto a linear processor array can be considered as a linear transformation problem. However, to find a linear space-optimal transformation is difficult because the conditions for checking a correct mapping and the space cost function do not have closed-form expressions, especially when the index set J of an n-dimensional algorithm is of an arbitrary bounded convex index set. In this paper, we propose an enumeration method to find a space-optimal PE allocation vector for mapping an n-dimensional uniform dependence algorithm with an arbitrary bounded convex index set onto a linear processor array, assuming that a linear schedule is given a priori.
Fully static processor optimal assignment of data-flow graphs
(1997-05-01)
Ho, YC
;
Tsay, JC
;
資訊工程學系
;
Department of Computer Science
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. In this letter, we propose a linear programming approach to solving the problem.
JTEAM: A framework for effective teamwork of BDI-based agents
(2003)
Hsu, CL
;
Chou, SF
;
Tsay, JC
;
Wang, FJ
;
資訊工程學系
The multi-agent systems approach promises significant benefits to distributed systems engineering, such as enhanced interoperability, scalability, and reconfigurability. Moreover, the teamwork of multiple agents can unite the capabilities of individual agents to solve problems of greater complexity than those solved by the individual agents. This paper presents a framework for effective teamwork of BDI (Belief-Desire-Intention)-based agents. The framework is built on JAM derived from PRS (Procedural Reasoning System), which is an intelligent agent architecture based on BDI theories. The framework extends the single agent capabilities of JAM and creates a teamwork infrastructure to effectively unite multiple agents' capabilities to solve problems collaboratively.