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

International Conference on parallel and Distributed Processing Techniques and Applications (PDPTA 2001)

作者： Santos, EE Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA

Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm;namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)-(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided.

关键词： parallel complexity matrix multiplication LogP model parallel algorithms lower bounds and optimality numerical algorithms linear algebra parallel models

来源：评论

学校读者我要写书评

暂无评论

Optimal and efficient parallel tridiagonal solvers using direct methods

引用

JOURNAL OF SUPERCOMPUTING 2004年第2期30卷 97-115页

作者： Santos, EE Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA

The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered in this paper. In particular, two common direct methods for solving such systems are considered: odd-even cyclic reduction and prefix summing. For each method, a variety of lower bounds on execution time for solving tridiagonal linear systems are presented. Specifically, lower bounds are presented that (a) hold when the number of data items per processor is bounded, (b) are general lower bounds, and (c) for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Furthermore, algorithms are presented that have running times within a constant factor of the lower bounds provided. Lastly, a comparison of bounds for odd-even cyclic reduction and prefix summing is given.

关键词： tridiagonal solvers parallel algorithms parallel complexity direct methods LogP model linear algebra

来源：评论

学校读者我要写书评

暂无评论

Optimal and efficient parallel tridiagonal solvers using direct methods

Optimal and efficient parallel tridiagonal solvers using dir...

引用

International Conference on parallel and Distributed Processing Techniques and Applications

作者： Santos, EE Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA

关键词： tridiagonal solvers parallel algorithms parallel complexity direct methods LogP model linear algebra

来源：评论

学校读者我要写书评

暂无评论

Bounded size dictionary compression:: SC^k-completeness and NC algorithms

引用

INFORMATION AND COMPUTATION 2003年第2期180卷 101-112页

作者： De Agostino, S Silvestri, R Armstrong Atlantic State Univ Dept Comp Sci Savannah GA 31419 USA Univ Roma La Sapienza Dipartimento Sci Informaz I-00135 Rome Italy

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(Iog(k)n), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(Iog(k) n) space (that is, SCk). We also introduce a variation of this heuristic that turns out to be an SCk-complete problem (the original heuristic belongs to SCk+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： parallel complexity NC algorithms SCk-completeness data compression dictionary algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient and optimal parallel algorithms for cholesky decomposition

引用

Journal of Mathematical Modelling and Algorithms 2003年第3期2卷 217-234页

作者： Santos, Eunice E. Chu, Pei-Yue Department of Computer Science Virginia Polytechnic Institute and State University Blacksburg VA 24061 United States Department of Computer Science and Engineering Lehigh University Bethlehem PA 18015 United States

In this paper, we consider the problem of developing efficient and optimal parallel algorithms for Cholesky decomposition. We design our algorithms based on different data layouts and methods. We thereotically analyze the run-time of each algorithm. In order to determine the optimality of the algorithms designed, we derive theoretical lower bounds on running time based on initial data layout and compare them against the algorithmic run-times. To address portability, we design our algorithms and perform complexity analysis on the LogP model. Lastly, we implement our algorithms and analyze performance data. © 2004 Kluwer Academic Publishers. Printed in the Netherlands.

关键词： Algorithms and complexity Cholesky decomposition LogP model Numerical linear algebra parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Distributed query evaluation on semistructured data

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2002年第1期27卷 1-62页

作者： Suciu, D Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA AT&T Corp Shannon Labs New York NY 10013 USA

Semistructured data is modeled as a rooted, labeled graph. The simplest kinds of queries on such data are those which traverse paths described by regular path expressions. More complex queries combine several regular path expressions, with complex data restructuring, and with sub-queries. This article addresses the problem of efficient query evaluation on distributed, semistructured databases. In our setting, the nodes of the database are distributed over a fixed number of sites, and the edges are classified into local (with both ends in the same site) and cross edges (with ends in two distinct sites). Efficient evaluation in this context means that the number of communication steps is fixed (independent on the data or the query), and that the total amount of data sent depends only on the number of cross links and of the size of the query's result. We give such algorithms in three different settings. First, for the simple case of queries consisting of a single regular expression;second, for all queries in a calculus for graphs based on structural recursion which in addition to regular path expressions can perform nontrivial restructuring of the graph;and third, for a class of queries we call select-where queries that combine pattern matching and regular path expressions with data restructuring and subqueries. This article also includes a discussion on how these methods can be used to derive efficient view maintenance algorithms.

关键词： algorithm languages theory distributed evaluation nested queries parallel complexity regular expressions semistructured data

来源：评论

学校读者我要写书评

暂无评论

Sampling chaotic trajectories quickly in parallel

引用

JOURNAL OF STATISTICAL PHYSICS 2002年第3-4期109卷 863-873页

作者： Machta, J Univ Massachusetts Dept Phys Amherst MA 01003 USA

The parallel computational complexity of the quadratic map is studied. A parallel algorithm is described that generates typical pseudotrajectories of length t in a time that scales as log t and increases slowly in the accuracy demanded of the pseudotrajectory. Long pseudotrajectories are created in parallel by putting together many short pseudotrajectories;Monte Carlo procedures are used to eliminate the discontinuities between these short pseudotrajectories and then suitably randomize the resulting long pseudotrajectory. Numerical simulations are presented that show the scaling properties of the parallel algorithm. The existence of the fast parallel algorithm provides a way to formalize the intuitive notion that chaotic systems do not generate complex histories.

关键词： chaotic dynamics parallel complexity quadratic map path sampling

来源：评论

学校读者我要写书评

暂无评论

The characterization of parallel real-time optimization problems 16

The characterization of parallel real-time optimization prob...

引用

16th Annual International Symposium on High Performance Computing Systems and Applications

作者： Bruda, SD Akl, SG Queens Univ Dept Comp & Informat Sci Kingston ON K7L 3N6 Canada

ISBN: (纸本)0769516262

We identify the class of optimization problem expressible as independence systems that can be solved in real time using a parallel machine with polynomially bounded resources as being exactly the class of matroid for which the size of the optimal solution can be computed in parallel real time. We also extend previous results, showing that the solution obtained by a parallel algorithm is arbitrarily better than the solution reported by a sequential one not only for the real-time minimum-weight spanning tree (as previously known). Indeed, we show that, for all practical purposes, such a property does in fact hold for any optimization problem that falls into the aforementioned class.

关键词： real time parallel complexity optimization independence systems matroids

来源：评论

学校读者我要写书评

暂无评论

parallel complexity of numerically accurate linear system solvers

引用

SIAM JOURNAL ON COMPUTING 1999年第6期28卷 2030-2058页

作者： Leoncini, M Manzini, G Margara, L Univ Pisa Dipartimento Informat I-56125 Pisa Italy CNR IMC I-56126 Pisa Italy Univ Piemonte Orientale Dipartimento Sci & Tecnol Avanzate I-15100 Alessandria Italy Univ Bologna Dipartimento Sci Informaz I-40127 Bologna Italy

We prove a number of negative results about practical (i.e., work efficient and numerically accurate) algorithms for computing the main matrix factorizations. In particular, we prove that the popular Householder and Givens methods for computing the QR decomposition are P-complete, and hence presumably inherently sequential, under both real and floating point number models. We also prove that Gaussian elimination (GE) with a weak form of pivoting, which aims only at making the resulting algorithm nondegenerate, is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete over GF(2) or when restricted to symmetric positive definite matrices, for which it is known that even standard GE (no pivoting) does not fail. Altogether, the results of this paper give further formal support to the widespread belief that there is a tradeoff between parallelism and accuracy in numerical algorithms.

关键词： P-complete problems parallel complexity NC algorithms inherently sequential algorithms matrix factorization numerical stability

来源：评论

学校读者我要写书评

暂无评论

On cellular Arrays and other topics in parallel computing

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2002年第2期E85D卷 312-321页

作者： Ibarra, OH Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

We give an overview of the computational complexity of linear and mesh-connected cellular and iterative arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved. Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the "commutativity analysis" technique that is used in the areas of parallel computing and parallelizing compilers.

关键词： cellular array computational complexity parallel complexity reachability commutativity analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：