Browsing by Author "Ma, YC"

Now showing 1 - 5 of 5

A dominance relation enhanced branch-and-bound task allocation
(2001-09-01)
Ma, YC
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
We investigate the task allocation problem of allocating a parallel program on parallel processors with non-uniform communication latencies. A branch-and-bound algorithm with a dominance relation is proposed to obtain an optimal task assignment. The key observation on deriving the dominance relation is that tasks can be clustered according to communication weights. The dominance relation is effective to prune the search space when the task clustering boundary - a small cut - is met. The proposed algorithm is compared to the A*-algorithm for task allocation. Experiment shows that our proposed algorithm achieves a speed-up ranging from 1.02 to 1.68, depending on the degree of task clustering and parallelism. This shows the effectiveness of the proposed dominance relation. (C) 2001 Elsevier Science Inc. All rights reserved.
Branch-and-bound task allocation with task clustering-based pruning
(2004-11-01)
Ma, YC
;
Chen, TF
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state-space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state-space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state-space searching approach feasible for practical use. (C) 2004 Published by Elsevier Inc.
Expressing the expected product images in product design of micro-electronic products
(2001-04-01)
Chuang, MC
;
Ma, YC
;
應用藝術研究所
;
Institute of Applied Arts
In order to explore how to effectively express product image when designing products, micro-electronic products were used as examples in this study to conduct a comprehensive investigation. Firstly. through a questionnaire survey, we deduced that the five most expected images perceived in micro-electronic products are: (i) high-technology. (ii) efficiency, (iii) lightness and handiness, (iv) nobility, and (v) delicacy. Next, sample product photographs were presented to the subjects in order to make various evaluations. Through semantic differential analysis, factor analysis and multidimensional scaling analysis, the subjects' perception of these images for the evaluated products was revealed acid a perceptual map of these products derived. Design subjects' perception was compared to that of non-design subjects. Finally, through morphological analysis of these products, the critical 'form elements' and approaches of form treatment among these products were extracted. By using multiple linear regression, the relationships between each image and Various form features were concluded. These findings can be further applied not only to establish a desired image in designing products, but also to reduce the perceptual gap between designers and users. Relevance to industry In the development of micro-electronic products, methods enabling the designer to create an appropriate image for a product so that it may communicate with the user are always critical issues. From this study, the expected images of micro-electronic products and the corresponding form features to achieve these images were extracted. A design guideline was summarized accordingly by which the time and cost of product development can be reduced while the quality of the product designed can be enhanced. (C) 2001 Elsevier Science B.V. All rights reserved.
Posting file partitioning and parallel information retrieval
(2002-08-15)
Ma, YC
;
Chen, TF
;
Chung, CP
;
資訊工程學系
;
Department of Computer Science
The rapid growth in Internet usages brings new challenges on designing a scalable information retrieval system. To reduce the response time of a query to a large database, we parallelize both CPU computation and disk access of Boolean query processing on a cluster of workstations. The key issue is to partition the inverted file such that, during parallel query processing, each workstation consults only its own locally resident data to complete its task. To achieve this goal, we treat the set of all postings referring to a document ID as an object to be allocated in the develop data placement problem. Following the partitioning by document ID principle, we develop posting file partitioning algorithms to transform a sequential information retrieval system to a parallel information retrieval system. The advantage is that a better speed-up can be achieved by deriving from the fast sequential approach the compressed posting file. The partitioning schemes are designed to balance work-load of workstations in parallel query processing without increasing the average disk access time per posting. The experiment shows that almost linear speed-up can be achieved and the performance bottleneck in previous work, which parallelize only disk access, can be removed. This work shows that, by using parallel processing technique, it is feasible to build a scalable information retrieval system. (C) 2001 Elsevier Science Inc. All rights reserved.
Variable-size data item placement for load and storage balancing
(2003-05-15)
Ma, YC
;
Chiu, JC
;
Chen, TF
;
Chung, CP
;
資訊工程學系
The rapid growth of Internet brings the need for a low cost high performance file system. Two objectives are to be pursued in building such a large scale storage system on multiple disks: load balancing and storage minimization. We investigate the optimization problem of placing variable-size data items onto multiple disks with replication to achieve the two objectives. An approximate algorithm, called LSB Placement, is proposed for the optimization problem. The algorithm performs bin packing along with MMPacking to obtain a load balanced placement with near-optimal storage balancing. The key issue in deriving the algorithm is to find the optimal bin capacity for the bin packing to reduce storage cost. We derive the optimal bin capacity and prove that LSB Placement algorithm is asymptotically 1-optimal on storage balancing. That is, when the problem size exceeds certain threshold, the algorithm generates a load balanced placement in which the data sizes allocated on disks are almost balanced. We demonstrate that, for various Web applications, a load balanced placement can be generated with disk capacity not exceeding 10% more than the balanced storage space. This shows that the LSB Placement algorithm is useful in constructing a low cost and high performance storage system. (C) 2002 Elsevier Science Inc. All rights reserved.