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

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

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of Learning with a Small Number of Nodes

On the Complexity of Learning with a Small Number of Nodes

引用

1992 International Joint Conference on Neural Networks, IJCNN 1992

作者： Parberry, Ian Center for Research in Parallel and Distributed Computing Department of Computer Sciences University of North Texas United States

ISBN: (纸本)0780305590

It is shown that the loading pioblem foi a 6 node neural netwoik with node function set AC^ (that is, the conjunction or disjunction of a subset of the inputs or their complements) is AiV complete. It can be deduced from this observation that the loading problem for a 6 node analog neural network is AfV hard. ©1992 IEEE

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the complexity of learning with a small number of nodes

On the complexity of learning with a small number of nodes

引用

International Joint Conference on Neural Networks (IJCNN)

作者： I. Parberry Center for Research in Parallel and Distributed Computing Department of Computer Sciences University of North Texas Denton TX USA

It is shown that the loading problem for a six-node neural network with a node function set AC/sub 10/, i.e., the conjunction or disjunction of a subset of the inputs or their complements is NP complete. It can be deduced from this observation that the loading problem for a six-node analog neural network is NP hard. The loading problem for a four-node neural network with a node function set equal to AC/sub 10/ plus the three-input equality function is shown to be NP complete, and it is indicated how the required results can be derived in a similar fashion. Three loading problems are studied.< >

关键词： Neural networks computer architecture distributed computing computer networks Boolean functions Concurrent computing Page description languages Electronic mail

来源：评论

学校读者我要写书评

暂无评论

PERFORMANCE OF parallel SPANNING TREE ALGORITHMS ON LINEAR ARRAYS OF TRANSPUTERS AND UNIX SYSTEMS

引用

parallel computing 1991年第4-5期17卷 527-551页

作者： DAS, SK YANG, CQ Center for Research in Parallel and Distributed Computing Department of Computer Sciences University of North Texas P.O. Box 13886 Denton TX 76203-3886 USA

This paper presents empirical performance of parallel algorithms for connected graphs on the transputer and Unix systems, where processes are configured as a one-dimensional array. We conduct experiments for implementing (i) spanning tree algorithm (SPT-list) with unordered list of edges as input, (ii) SPT algorithm with adjacency matrix, (iii) minimum spanning tree algorithm (MST) with weight matrix as input, and (iv) SPT algorithm derived from MST algorithm by assigning each edge-weight equal to 1. The empirical study is performed with a wide range of random graphs, generated for various (uniformly distributed) edge-densities (d) for a given number (n) of vertices. We plot curves for resulting speedups as functions of n, d, and p. The edge-density d is varied between 0.1 and 0.9;maximum number of vertices (or edges) considered are 300 (or 40 000) and 500 (or 110 000) for transputer and Unix systems, respectively;and the number of processors p varies from 1 through 8 in the transputer system while 1 through 4 in the Unix system. A maximum speedup of 2.98 is obtained on transputers, and that for the Unix system is 3.0. We observe that the speedups of all algorithms vary with increasing number of vertices or edge-density. However, employing more processing units in an algorithm does not necessarily enhance its speedup because of additional communication overhead.

关键词： TRANSPUTERS LINEAR ARRAY PERFORMANCE STUDY parallel GRAPH ALGORITHM SPANNING TREE MINIMUM SPANNING TREE

来源：评论

学校读者我要写书评

暂无评论

Performance of parallel spanning tree algorithms on linear arrays of transputers and Unix systems 5

Performance of parallel spanning tree algorithms on linear a...

引用

5th International parallel Processing Symposium, IPPS 1991

作者： Das, Sajal K. Yang, Cui-Qing Center for Research in Parallel and Distributed Computing Department of Computer Sciences University of North Texas DentonTX76203-3886 United States

ISBN: (纸本)0818691670

This paper presents empirical performance of parallel algorithms for computing a spanning tree (SPT) and a minimum spanning tree (MST) of connected graphs on the Transputer and Unix systems, where processors are configured as a onedimensional array. The parallel MST algorithm uses a weight matrix data structure;and three implementations of the SPT algorithm are presented with unordered edge-list, linked adjacency list and adjacency matrix as data structures. The experiments are conducted with a wide range of random graphs, generated for various edge-densities (d) for a given number (n) of vertices. The edge-density is varied between 0.1 and 0.9, and the maximum number of vertices (or edges) considered are 300 (or 40,000) and 500 (or 110,000) for transputer and Unix systems, respectively. A maximum speed-up of 2.98 is achieved on the transputer network of 8 processors, and that for the Unix system is 3.0 with 4 processes. © 1991 IEEE.

关键词： Transputers

来源：评论

学校读者我要写书评

暂无评论

A cost-optimal parallel algorithm for the parentheses matching problem on an EREW PRAM 5

A cost-optimal parallel algorithm for the parentheses matchi...

引用

5th International parallel Processing Symposium, IPPS 1991

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

We present a cost-optimal parallel algorithm for the parentheses matching problem on the EREW PRAM model For n parentheses, the algorithm requires O(n/p + log n) time and O(n + p log p) space, employing p processors. ... 详细信息

ISBN: (纸本)0818691670

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Managing a parallel heap efficiently 3rd

Managing a parallel heap efficiently

引用

3rd International Conference on parallel Architectures and Languages Europe, PARLE 1991

作者： Das, Sajal K. Horng, Wen-Bing Center for Research in Parallel and Distributed Computing Department of Computer Science University of North Texas DentonTX76203-3886 United States

ISBN: (纸本)9783540541516

We design a cost-optimal algorithm for managing a parallel heap on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. This is an improvement in space and time over the one recently proposed by Deo and Prasad [4]. Our approach efficiently employs p processors in the range 1 ≤ p ≤ n, where n is the maximum number of items in a 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 α (a constant) new items. The time required for deleting p items of the highest priority from the parallel heap is O(l), while that for inserting at most αp new items is 0(logn). With or without incorporating the think time, the speedup of our algorithm is proved to be linear, i.e. 0(p). Using a global, working data structure for each level of the heap, it is shown that the additional memory space required for our parallel heap is much less than that for the existing one [4]. Furthermore, the proposed algorithm retains the strict priority ordering of a sequential heap. © Springer-Verlag Berlin Heidelberg 1991.

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：