检索结果-内蒙古大学图书馆

Efficient parallel Algorithms for Pattern Recognition

parallel Algorithms and Applications 1994年第1-2期2卷 81-98页

作者： Das, Sajal K Fisher, Paul S Zhang, Hua Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX 76203-6886 United States

Finitely inductive (F1) sequences are a class of sequences, finite or infinite, which are amenable to a certain mathematical representation which has direct significance to pattern recognition and string matching. Pattern recognition using the Fl technique first transforms known patterns into function table(s) by factoring, and then uses the function table(s) to match an input pattern by following. Factoring is done off line and only once for each pattern. The sequential time for matching two sequences depends only upon the length of the input sequence. In this paper, we propose cost-optimal (i.e., efficient) parallel algorithms for FI sequence processing. These algorithms include parallel factoring and following by bucket packing on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. The proposed algorithms also have implications lo parallel integer sorting. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Finitely inductive sequences Integer sorting parallel algorithms Pattern recognition String matching

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for managing a parallel heap

引用

parallel Algorithms and Applications 1994年第3-4期4卷 281-299页

作者： Das, Sajal K. Horng, Wen-Bing Moon, Gyo S. Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX 76203-6886 United States Dept. of Computer Science and Information Engineering Tamkang Univ Tamsui Taipei Taiwan

We design a cost-optimal algorithm for managing a parallel heap on an exclusive-read exclusive-write (EREW), parallel random access machine (PRAM) model. We also analyze the time and space complexities of our algorithm, which efficiently employs p processors in the range 1 ≤ p ≤ n, where n is the maximum number of items in the parallel heap. It is assumed that a delete-think-insert cycle is repeatedly performed, and each processor requires an arbitrary but the same amount of time (called the think time) for processing an item which in turn generates at most two new items. The use of a global data structure for each level of the heap helps reduce the working memory space required. The time complexity for deleting p items of the highest priority from the parallel heap is O(log p), while that for inserting at most 2p new items is O(log n). With or without incorporating the think time, the speedup of our algorithm is shown to be linear, i.e. O(p). Hence this algorithm is an improvement in time over the one proposed by Deo and Prasad [5, 6]. © 1994, Taylor & Francis Group, LLC. All rights reserved.

关键词： Data structure EREW PRAM Heap Linear speedup parallel algorithm Priority queue

来源：评论

学校读者我要写书评

暂无评论

Cost-optimal parallel algorithms for finitely inductive sequences 26

Cost-optimal parallel algorithms for finitely inductive sequ...

引用

26th Hawaii International Conference on System sciences, HICSS 1993

作者： Das, S.K. Fisher, P.S. Zhang, H. Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas DentonTX76203-3886 United States

ISBN: (纸本)0818632305

Finitely inductive (FI) sequences are a class of sequences, finite or infinite, which are amenable to a certain mathematical representation which has direct significance to pattern recognition and string matching. Pattern recognition using the FI technique first transforms known patterns into function table(s) by factoring, and then uses the function iable(s) to match an input pattern by following. Factoring is done off line and only once for each pattern. The sequential time for matching two sequences depends only upon the length of the input sequence. In this paper, we propose cost-optimal (i.e., efficient) parallel algorithms for FI sequence processing. These algorithms include parallel factoring and following by bucket packing and by hashing on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. © 1993 IEEE.

关键词： Pattern recognition

来源：评论

学校读者我要写书评

暂无评论

Cost-optimal parallel algorithms for finitely inductive sequences

Cost-optimal parallel algorithms for finitely inductive sequ...

引用

Annual Hawaii International Conference on System sciences (HICSS)

作者： S.K. Das P.S. Fisher H. Zhang Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas Denton TX USA

Finitely inductive (FI) sequences are a class of sequences, finite or infinite, which are amenable to a certain mathematical representation which has direct significance to pattern recognition and string matching. The authors propose cost-optimal parallel algorithms for FI sequence processing. These algorithms include parallel factoring and following by bucket packing and by hashing on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. Each of the algorithms achieves cost-optimal speedup under certain conditions as detailed.< >

关键词： parallel algorithms Pattern recognition Pattern matching distributed computing computer science Impedance matching Phase change random access memory Multiple signal classification Signal detection Motion detection

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel algorithms on interval graphs 4th

Efficient parallel algorithms on interval graphs

引用

4th International parallel Architectures and Languages Europe Conference, PARLE 1992

作者： Das, Sajal K. Chen, Calvin C. -Y. Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas DentonTX76203 United States

ISBN: (纸本)9783540555995

We design efficient parallel algorithms for solving several problems on interval graphs. The problems include finding a BFS-tree and DFS-tree, articulation points and bridges, and minimum coloring. Each of our algorithms requires O(log n) time employing O(n) processors on the EREW PRAM model, where n is the number of vertices. The proposed algorithms for computing articulation points and bridges have better performance in terms of the cost (i.e, processor-time product) than the existing algorithms in [RR90], yet having the same time complexity. Our novel approach to the construction of BFS tree is based on elegantly capturing the structure of a given collection of intervals. This structure reveals important properties of the corresponding interval graph, and is found to be instrumental in solving many other problems on such graphs. Although the time- and processor-complexities of the proposed DFS-tree construction or minimum-coloring is comparable with the best-known ones [KI89], our approach to these problems are new. For example, the approach to the construction of a DFS tree is based on reducing the problem into an all dominating neighbors (ADN) problem;while that to the minimum coloring is by transforming this problem into a linked list ranking problem. © Springer-Verlag Berlin Heidelberg 1992.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel fractional cascading on hypercube multiprocessors

引用

Computational Geometry: Theory and Applications 1992年第3期2卷 141-141页

作者： Dehne, F. Ferreira, A. Rau-Chaplin, A. Center for Parallel and Distributed Computing School of Computer Science Carleton University Ottawa Canada K1S 5B6 CNRS-Laboratoire de l'Informatique du Parallelisme Ecole Normale Superieure de Lyon 69364 Lyon cedex 07 France

Dehne, F., A. Ferreira and A. Rau-Chaplin, parallel fractional cascading on hypercube multiprocessors, Computational Geometry: Theory and Applications 2 (1992) 141–167. In this paper we present a new data-structuring technique for parallel computational geometry on a hypercube multiprocessor. This technique, called hypercube cascading, is an efficient parallel implementation of fractional cascading for the hypercube multiprocessor. That is, it allows complex data structures with catalogs to be traversed efficiently in parallel by a large number of simultaneous queries. We show that for monotone graphs with n nodes, m multiple look-up queries with path length at most p (including catalog look-ups) can be executed independently, in parallel, in time O( p log N + t s ( N )) on a hypercube multiprocessor of size N = max n, itm . The term t s ( N ) denotes the time for sorting N elements on a hypercube of size N ; currently t s ( N ) = O(log N log log N ). Note that, the best known sequential time complexity for one multiple look-up query, as presented by Chazelle and Guibas, is O( p + log N ). Our solution allows an arbitrary number of search queries to access the same node and its catalog at the same time. We present two parallel computational geometry applications of this technique: multiple stabbing of a simple polygonal path and multiple slanted range search.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Efficient construction of catastrophic patterns for VLSI reconfigurable arrays with bidirectional links 4

Efficient construction of catastrophic patterns for VLSI rec...

引用

4th International Conference on computing and Information, ICCI 1992

作者： Nayak, Amiya Pagli, Linda Santoro, Nicola Center for Parallel and Distributed Computing School of Computer Science Carleton University OttawaKlS 5B6 Canada Dipartimento di Scienze dell'Informazione University of Pisa Corso Italia 40 Pisa56100 Italy

ISBN: (纸本)081862812X

Patterns of faults that are catastrophic for regular architectures, particularly the systolic arrays, have been studied. For a given link configuration, there are many fault patterns which are catastrophic. Among those, there is a particular fault pattern, called the reference fault pattern, which is crucial for the development of testing techniques;furthermore, the efficiency of any testing algorithm can be further improved in the presence of efficient algorithms for constructing the reference fault pattern. In this paper, we develop a new algorithm for the construction of the reference fault pattern for VLSI reconfigurable arrays in which the links are bidirectional. The complexity of the new algorithm is 0(kN) which is a significant improvement over the existing 0(N2) algorithm, where k is the number of bypass links, and N is the length of the largest bypass link. ©1992 IEEE.

关键词： Systolic arrays

来源：评论

学校读者我要写书评

暂无评论

Recognition of catastrophic faults

Recognition of catastrophic faults

引用

1992 IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, DFT 1992

作者： Nayak, Amiya Pagli, Linda Santoro, Nicola Center for Parallel and Distributed Computing School of Computer Science Carleton University OttawaONK1S 5B6 Canada Dipartimento di Scienze dell'Informazione University of Pisa Corso Italia 40 Pisa56100 Italy

ISBN: (纸本)0818628375

Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. Regular systems are being designed with massive redundancy built into them [5,6,12], These systems also make use of the redundancy to reconfigure in the event of failure in one or more components;normally, a reconfiguration process is triggered as soon as a fault is detected. Many different reconfiguration schemes [1-4,6,7,10-13] have been proposed in the literature which reconfigure regular systems in the presence of faulty components. The distribution of faults can have severe impact on the effectiveness of any reconfiguration scheme;in fact, patterns of faults occurring at strategic locations may render an entire system unusable regardless of its component redundancy and of its reconfiguration capabilities. For a given design, it is not difficult to identify a set of elements whose failure will have catastrophic consequence. There exist many patterns (random distribution) of faults, not in a block, which can be fatal for the system [9]. Therefore, the characterization of such fault patterns is crucial for the identification, testing and detection of such catastrophic events. © 1992 IEEE.

关键词： Redundancy

来源：评论

学校读者我要写书评

暂无评论

Efficient construction of catastrophic patterns for VLSI reconfigurable arrays with bidirectional links

Efficient construction of catastrophic patterns for VLSI rec...

引用

International Conference on computing and Information (ICCI)

作者： A. Nayak L. Pagli N. Santoro Center for Parallel & Distributed Computing School of Computer Science Carleton University Ottawa Canada Dipartimento di Scienze dellInformazione University of Pisa Pisa Italy

Patterns of faults that are catastrophic for regular architectures, particularly the systolic arrays, have been studied. For a given link configuration, there are many fault patterns which are catastrophic. Among those, there is a particular fault pattern, called the reference fault pattern, which is crucial for the development of testing techniques; furthermore, the efficiency of any testing algorithm can be further improved in the presence of efficient algorithms for constructing the reference fault pattern. The authors develop a new algorithm for the construction of the reference fault pattern for VLSI reconfigurable arrays in which the links are bidirectional. The complexity of the new algorithm is O(kN) which is a significant improvement over the existing O(N/sup 2/) algorithm, where k is the number of bypass links, and N is the length of the largest bypass link.< >

关键词： Very large scale integration Redundancy Systolic arrays distributed computing computer science Fault tolerance Clustering algorithms System testing Fault diagnosis Sufficient conditions

来源：评论

学校读者我要写书评

暂无评论

Recognition of catastrophic faults

Recognition of catastrophic faults

引用

IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems

For a given design, it is not difficult to identify a set of elements whose failure will have catastrophic consequence. There exist many patterns (random distribution) of faults, not in a block, which can be fatal for the system. Therefore, the characterization of such fault patterns is crucial for the identification, testing and detection of such catastrophic events. This paper, is concerned with the development of efficient recognition schemes; that is, efficient mechanisms which automatically determine whether or not an observed/detected pattern of faults will have catastrophic consequences. The problem of recognizing whether a fault pattern is catastrophic has been addressed.< >

关键词： Redundancy Pattern recognition Fault tolerance Fault detection Event detection Testing distributed computing computer science Fault diagnosis Sufficient conditions

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：