The area of path planning has received a great deal of attention recently, algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be th...
详细信息
ISBN:
(纸本)0769523978
The area of path planning has received a great deal of attention recently, algorithms are required that can deliver optimal paths for robots to take over homogeneous or non-homogeneous terrain. Optimal paths may be those that involve the shortest distance travelled, the least number of turns or the least number of ascents and descents. The often highly complex nature of terrains and the necessity for realtime solutions have lead to a requirement for the development of parallel algorithms. Such problems have been notoriously difficult to parellelise efficiently;indeed it has been said that an efficiency of 25-60% should be considered a success. In this paper we present a parallel algorithm for finding optimal paths over non-homogeneous terrain that demonstrates superlinear speed-up.
作者：
Chen, SPitt, GYork Univ
Sch Analyt Studies & Informat Technol N York ON M3J 1P3 Canada York Univ
Dept Math N York ON M3J 1P3 Canada
The preservation of common components has been recently isolated as a beneficial feature of genetic algorithms. One interpretation of this benefit is that the preservation of common components can direct the search pr...
详细信息
ISBN:
(纸本)3540265511
The preservation of common components has been recently isolated as a beneficial feature of genetic algorithms. One interpretation of this benefit is that the preservation of common components can direct the search process to focus on the most promising parts of the search space. If this advantage can be transferred from genetic algorithms, it may be possible to improve the overall effectiveness of other heuristic search techniques. To identify common components, multiple solutions are required - like those available from a set of parallel searches. Results with simulated annealing and the Traveling Salesman Problem show that the sharing of common components can be an effective method to coordinate parallel search.
Successful participation in task-oriented, inference-rich dialogs requires, among other things, understanding of specifications implicitly conveyed through the exploitation of parallel structures. Several linguistic o...
详细信息
ISBN:
(纸本)3540260315
Successful participation in task-oriented, inference-rich dialogs requires, among other things, understanding of specifications implicitly conveyed through the exploitation of parallel structures. Several linguistic operators create specifications of this kind, including "the other way (a)round", "vice-versa", and "analogously";unfortunately, automatic reconstruction of the intended specification is difficult due to the inherent dependence on given context and domain. We address this problem by a well-informed reasoning process. The techniques applied include building deep semantic representations, application of categories of patterns underlying a formal reconstruction, and using pragmaticallymotivated and domain-justified preferences. Our approach is not only suitable for improving the understanding in everyday discourse, but it specifically aims at extending capabilities in a tutorial dialog system, where stressing generalities and analogies is a major concern.
Modern cluster file systems such as PVFS that stripe files across multiple nodes have shown to provide high aggregate I/O bandwidth but are prone to data loss since the failure of a single disk or server affects the w...
详细信息
ISBN:
(纸本)3540290311
Modern cluster file systems such as PVFS that stripe files across multiple nodes have shown to provide high aggregate I/O bandwidth but are prone to data loss since the failure of a single disk or server affects the whole file system. To address this problem a number of distributed data redundancy schemes have been proposed that represent different trade-offs between performance, storage efficiency and level of fault tolerance. However the actual level of dependability of an enhanced striped file system is determined by more than just the redundancy scheme adopted, depending in general on other factors such as the type of fault detection mechanism, the nature and the speed of the recovery. In this paper we address the question of how to assess the dependability of CSAR, a version of PVFS augmented with a RAID5 distributed redundancy scheme we described in a previous work.
One of the fundamental components of large-scale gene discovery projects is that of clustering of expressed sequence tags (ESTs) from complementary DNA (cDNA) clone libraries. Clustering is used to create non-redundan...
详细信息
One of the fundamental components of large-scale gene discovery projects is that of clustering of expressed sequence tags (ESTs) from complementary DNA (cDNA) clone libraries. Clustering is used to create non-redundant catalogs and indices of these sequences. In particular, clustering of ESTs is frequently used to estimate the number of genes derived from cDNA-based gene discovery efforts. This paper presents a novel parallel extension to an EST clustering program, UIcluster4, that incorporates alternative splicing information and a new parallelization strategy. The results are compared to other parallelized EST clustering systems in terms of overall processing time and in accuracy of the resulting clustering. (c) 2004 Published by Elsevier B.V.
In this paper, we design genetic algorithm and simulated annealing algorithm and their parallel versions to solve the Closest String Problem. Our implementation and experiments show usefulness of the parallel CA and S...
详细信息
ISBN:
(纸本)354027894X
In this paper, we design genetic algorithm and simulated annealing algorithm and their parallel versions to solve the Closest String Problem. Our implementation and experiments show usefulness of the parallel CA and SA algorithms.
The 0-1 knapsack problem is considered. A parallel dynamic programming multi-method using dominance technique and processor cooperation is proposed. Different load balancing approaches are studied. Computational exper...
详细信息
ISBN:
(纸本)076952513X
The 0-1 knapsack problem is considered. A parallel dynamic programming multi-method using dominance technique and processor cooperation is proposed. Different load balancing approaches are studied. Computational experiments carried out on an Origin 3800 supercomputer are reported and analyzed.
Finding common fixed points of a set of operators with some kind of contracting properties is a problem that has attracted much attention in the last decades. Probably the least demanding of such operators are the so-...
详细信息
Finding common fixed points of a set of operators with some kind of contracting properties is a problem that has attracted much attention in the last decades. Probably the least demanding of such operators are the so-called paracontractions, for which it is only needed that the image of a point under such operator is not farther away from the set of fixed points of the operator than the original point. In what follows, we present two parallel algorithms for finding common fixed points of a finite set of paracontractions;in the first one, the complete set of operators is involved at each iteration step;the second algorithm has a block-iterative nature.
Our main interest is oriented towards keeping both local and parallel jobs together in a non-dedicated cluster. In order to obtain some profits from the parallel applications, it is important to consider time and spac...
详细信息
ISBN:
(纸本)3540287000
Our main interest is oriented towards keeping both local and parallel jobs together in a non-dedicated cluster. In order to obtain some profits from the parallel applications, it is important to consider time and space sharing as a mean to enhance the scheduling decisions. In this work, we introduce an integral scheduling system for non-dedicated clusters, termed CISNE. It includes both a previously developed dynamic coscheduling system and a space-sharing job scheduler to make better scheduling decisions than can be made separately. CISNE allows multiple parallel applications to be executed concurrently in a non dedicated Linux cluster with a good performance, as much from the point of view of the local user as that of the parallel application user. This is possible without disturbing the local user and obtaining profits for the parallel user. The good performance of CISNE has been evaluated in a Linux cluster.
In this paper, we propose an associative parallel algorithm for updating a minimum spanning tree when a vertex and all its incident edges axe deleted from the underlying graph. This algorithm is represented as the cor...
详细信息
ISBN:
(纸本)3540281266
In this paper, we propose an associative parallel algorithm for updating a minimum spanning tree when a vertex and all its incident edges axe deleted from the underlying graph. This algorithm is represented as the corresponding procedure implemented on a model of associative parallel systems of the SIMD typo with vertical data processing (the STAR-machine). We justify the correctness of this procedure and evaluate its time complexity.
暂无评论