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

Scalable parallel computational geometry for coarse grained multicomputers

international JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1996年第3期6卷 379-400页

作者： Dehne, F Fabri, A RauChaplin, A CARLETON UNIV SCH COMP SCIOTTAWAON K1S 5B6CANADA INRIA F-06902 SOPHIA ANTIPOLISFRANCE

We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O(n/p) much greater than O(1) local memory and all processors are connected via some arbitrary interconnection network (e.g. mesh, hypercube, fat tree). We present O(T-sequential/p + T-s(n,p)) time scalable parallel algorithms for several computational geometry problems. T-s(n,p) refers to the time of a global sort operation. Our results are independent of the multicomputer's interconnection network. Their time complexities become optimal when T-sequential/p dominates T-s(n,p) or when T-s(n,p) is optimal. This is the case for several standard architectures, including meshes and hypercubes, and a wide range of ratios n/p that include many of the currently available machine configurations. Our methods also have some important practical advantages: For interprocessor communication, they use only a small fixed number of one global routing operation, global sort, and all other programming is in the sequential domain. Furthermore, our algorithms use only a small number of very large messages, which greatly reduces the overhead for the communication protocol between processors. (Note however, that our time complexities account for the lengths of messages.) Experiments show that our methods are easy to implement and give good timing results.

关键词： computational geometry parallel algorithms scalability

来源：评论

学校读者我要写书评

暂无评论

Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs

Optimal fine and medium grain parallelism detection in polyh...

引用

international Conference on parallel Architecture and Compilation Techniques (PACT)

作者： A. Darte F. Vivien Laboratoire LIP URA CNRS 1398 Ecole Normale Supérieure de Lyon Lyon France

This paper proposes an optimal algorithm for detecting fine or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular it is optimal for direction vectors, which generalizes Wolf and Lam's algorithm (1991) to the case of several statements. It relies on a dependence uniformization process and an parallelization techniques related to system of uniform recurrence equations.

关键词： Linear programming Approximation algorithms Difference equations Linear systems Scheduling algorithm Vectors

来源：评论

学校读者我要写书评

暂无评论

Recursive hierarchical swapped networks: versatile interconnection architectures for highly parallel systems

Recursive hierarchical swapped networks: versatile interconn...

引用

international symposium on parallel and Distributed Processing (IPDPS)

作者： Chi-Hsiang Yeh B. Parhami Department of Electrical and Computer Engineering University of California Santa Barbara CA USA

The authors propose a new class of interconnection networks called recursive hierarchical swapped networks (RHSN) for general-purpose parallel processing. The node degrees of RHSNs can vary from a small number to as large as required, depending on recursive and hierarchical composition parameters and the nucleus graph chosen. The diameter of an RHSN can be asymptotically optimal within a small constant factor. They present efficient routing, semigroup computation, ascend/descend, matrix-matrix multiplication, and emulation algorithms, thus proving the versatility of RHSNs. In particular on suitably constructed RHSNs, matrix multiplication can be performed faster than the DNS algorithm on a hypercube. Furthermore, ascend/descend algorithms, semigroup computation, and parallel prefix computation can be done using algorithms with asymptotically fewer communication steps than on a hypercube.

关键词： Joining processes Hypercubes Fault tolerance Multiprocessor interconnection networks

来源：评论

学校读者我要写书评

暂无评论

On combining technology and theory in search of a parallel computation model

On combining technology and theory in search of a parallel c...

引用

international Conference on parallel Processing Workshops (ICPPW)

作者： JaJa Institute for Advanced Computer Studies and Department of Electrical Engineering University of Maryland College Park MD USA

A fundamental problem in parallel computing is to design high-level, architecture independent, algorithms that execute efficiently on general purpose parallel machines. The aim is to be able to achieve portability and high performance simultaneously. A key to accomplishing this is the existence of a computation model that can bridge the gap between the high level programming models and the underlying hardware models. There are currently two factors that make this fundamental problem more tractable. The first is the emergence of a dominant parallel architecture consisting of a number of powerful microprocessors interconnected by either a proprietary interconnect, or a standard off-the-shelf interconnect (such as an ATM switch). The second factor is the emergence of standards, such as the message passing standard MPI, for which efficient implementations are either available or about to appear on most machines. Our recent work has exploited these two developments by developing a methodology based on (1) a simple computation model for the current MIMD platforms that incorporates communication cost into the complexity of the algorithms, and (2) a SPMD programming model that makes effective use of communication primitives. We describe our approach for validating the computation model based on extensive experimentation and the development of benchmarks, and discuss its extension to the emerging clusters of Symmetric Multiprocessors (SMPs) architecture.

关键词： parallel machines parallel algorithms parallel architectures

来源：评论

学校读者我要写书评

暂无评论

Compile-time inter-query dependence analysis

Compile-time inter-query dependence analysis

引用

international symposium on parallel and Distributed Processing (IPDPS)

作者： S. Parthasarathy Wei Li M. Cierniak M.J. Zaki Department of Computer Science University of Rochester Rochester NY USA

Most parallel databases exploit two types of parallelism: intra-query parallelism and inter-transaction concurrency. Between these two cases lies another type of parallelism: inter-query parallelism within a transaction or application. Exploiting inter-query parallelism requires either compiler support to automatically parallelize the existing embedded query programs; or programming support to write explicitly parallel query programs. The authors present compiler analysis to automatically detect parallelism in the embedded query programs. They present compiler algorithms for detecting dependences in such programs. They show that the properties of some aggregate functions such as MIN and MAX can help reduce statically computed dependences.

关键词： parallel processing Program processors Testing Transaction databases Aggregates Database systems Concurrent computing Automatic programming parallel programming Computer science

来源：评论

学校读者我要写书评

暂无评论

Iterative dynamic programming: an approach to minimum energy trajectory planning for robotic manipulators

Iterative dynamic programming: an approach to minimum energy...

引用

IEEE international Conference on Robotics and Automation (ICRA)

作者： G. Field Y. Stepanenko Precision MicroDynamics Inc. Victoria BC Canada Department of Mechanical Engineering University of Victoria Victoria BC Canada

This paper proposes a technique of iterative dynamic programming to plan minimum energy consumption trajectories for robotic manipulators. The dynamic programming method is modified to perform a series of dynamic programming passes over a small reconfigurable grid covering only a portion of the solution space at any one pass. Although strictly no longer a global optimization process, this iterative approach retains the ability to avoid some poor local minima while avoiding the curse of dimensionality associated with a pure dynamic programming approach. The algorithm has an inherent parallel structure, allowing for reduced computation time on parallel architecture computers. No limiting assumptions are made about the performance index, or function to be optimized. As such, extremely complex functions and constraints are easily handled. Joint actuator and time constraints are considered in this work. The modified dynamic programming approach is verified experimentally by planning and executing a minimum energy consumption path for a Reis V15 industrial manipulator.

关键词： Iterative methods Dynamic programming Energy consumption Manipulator dynamics Concurrent computing Trajectory Orbital robotics Iterative algorithms parallel architectures Performance analysis

来源：评论

学校读者我要写书评

暂无评论

Parametric analysis of polyhedral iteration spaces

Parametric analysis of polyhedral iteration spaces

引用

international Conference on Application Specific Systems (ASAP), architectures and Processors

作者： P. Clauss V. Loechner ICPS University of Louis Pasteur Brant France

In the area of automatic parallelization of programs, analyzing and transforming loop nests with parametric affine loop bounds requires fundamental mathematical results. The most common geometrical model of iteration spaces, called the polytope model, is based on mathematics dealing with convex and discrete geometry, linear programming, combinatorics and geometry of numbers. In this paper, we present an automatic method for computing the number of integer points contained in a convex polytope or in a union of convex polytopes. The procedure consists of first, computing the parametric vertices of a polytope defined by a set of parametric linear constraints, and then computing the Ehrhart polynomial, i.e. a parametric expression of the number of integer points. The paper is illustrated with the computation of the maximum available parallelism of a given loop nest.

关键词： Solid modeling Mathematical model parallel processing Linear programming Combinatorial mathematics Polynomials Concurrent computing Computational geometry Partitioning algorithms Algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for fast computation of normalized edit distances

Parallel algorithms for fast computation of normalized edit ...

引用

international symposium on parallel and Distributed Processing (IPDPS)

作者： O. Egecioglu M. Ibel Department of Computer Science University of California Santa Barbara CA USA

The authors give work-optimal and polylogarithmic time parallel algorithms for solving the normalized edit distance problem. The normalized edit distance between two strings X and Y with lengths n/spl ges/m is the minimum quotient of the sum of the costs of edit operations transforming X into Y by the length of the edit path corresponding to those edit operations. Marzal and Vidal (1993) proposed a sequential algorithm with a time complexity of O(nm/sup 2/). They show that this algorithm can be parallelized work-optimally on an array of n (or m) processors, and on a mesh of n/spl times/m processors. They then propose a sublinear time algorithm that is almost work-optimal: using O(mn/sup 1.75/) processors, the time complexity of the algorithm is O(n/sup 0.75/ log n) and the total number of operations is O (mn/sup 2.5/ log n). This algorithm runs on a CREW PRAM, but is likely to work on weaker PRAM models and hypercubes with minor modifications. Finally, they present a polylogarithmic O(log/sup 2/ n) time algorithm based on matrix multiplication which runs on a O(n/sup 6//log n) processor hypercube.

关键词： parallel algorithms Concurrent computing Signal processing algorithms Costs Phase change random access memory Hypercubes Dynamic programming Information retrieval Computer science parallel programming

来源：评论

学校读者我要写书评

暂无评论

Linear time approximation schemes for parallel processor scheduling

Linear time approximation schemes for parallel processor sch...

引用

international symposium on parallel and Distributed Processing (IPDPS)

作者： Y. Kopidakis D. Fayard V. Zissimopoulos Université de Paris-Sud Orsay France

The authors present a general framework for approximation schemes on parallel processor scheduling. They propose /spl epsiv/-approximation algorithms for scheduling on identical, uniform and unrelated machines when the number of processors is fixed. For each of the three problems considered, they perform grouping on job processing times in order to produce a transformed scheduling instance where the number of distinct task types is bounded. They optimally solve the corresponding mixed integer program and prove that the optimal makespans for the initial and the transformed problems can differ at most by a factor of 1+/spl epsiv/ The complexity of all /spl epsiv/-approximation algorithms is O(n), where n is the number of jobs to be scheduled.

关键词： Linear approximation Processor scheduling Polynomials Approximation algorithms Scheduling algorithm Costs NP-complete problem Linear programming

来源：评论

学校读者我要写书评

暂无评论

A task migration implementation of the Message-Passing Interface

A task migration implementation of the Message-Passing Inter...

引用

international symposium on High Performance Distributed Computing

作者： J. Robinson S.H. Russ B. Flachs B. Heckel NSF Engineering Research Center for Computatiorial Field Simulation Mississippi State University USA MicroMagnetic Inc. Sunnyvale CA USA

In order to use networks of workstations in parallel processing applications, several schemes have been devised to allow processes on different, possibly heterogeneous, platforms to communicate with one another. The Message-Passing Interface (MPI) is one such scheme that allows for message-passing across different architectures. The MPI specification does not make provisions for the migration of a process between machines. This paper describes the work required to modify, an MPI implementation to allow for task migration. It also describes "Hector", our heterogeneous computing task allocator that is used to migrate tasks automatically and improve the overall performance of a parallel program.

关键词： Workstations Concurrent computing parallel processing parallel programming Computer networks Computational modeling Computer architecture Scientific computing Floating-point arithmetic Distributed computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：