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

On the Complexity of Commutativity Analysis

International Journal of Foundations of Computer Science 1997年第1期8卷 81-94页

作者： Oscar H. Ibarra Pedro C. Diniz Martin C. Rinard University of California Santa Barbara California 93106-5110 U.S.A Supported in part by NSF/NASA/ARPA Grant IRI94-11330. Sponsored by the PRAXIS XXI program administrated by Portugal's JNICT – Junta Nacional de Investigação Científica e Tecnológica and holds a Fulbright travel grant. Supported in part by an Alfred P. Sloan Research Fellowship.

Two operations commute if they generate the same result regardless of the order in which they execute. Commutativity is an important property — commuting operations enable significant optimizations in the fields of parallel computing, optimizing compilers, parallelizing compilers and database concurrency control. Algorithms that statically decide if operations commute can be an important component of systems in these fields because they enable the automatic application of these optimizations. In this paper we define the commutativity decision problem and establish its complexity for a variety of basic instructions and control constructs. Although deciding commutativity is, in general, undecidable or computationally intractable, we believe that efficient algorithms exist that can solve many of the cases that arise in practice.

关键词： Computational complexity commutativity analysis program symbolic analysis parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Automated transformation of sequential divide-and-conquer algorithms into parallel programs

引用

COMPUTERS AND ARTIFICIAL INTELLIGENCE 1995年第6期14卷 579-596页

作者： Freisleben, B Kielmann, T UNIV SIEGEN DEPT ELECT ENGN & COMP SCI FB12 D-57068 SIEGEN GERMANY

Divide-and-conquer algorithms obtain the solution to a given problem by dividing it into subproblems, solving these recursively and combining their solutions. In this paper we present a system that automatically transforms sequential divide-and-conquer algorithms written in the C programming language into parallel code which is then executed on message-passing multicomputers. The user of the system is expected to add only a few annotations to an existing sequential program. The strategies required for transforming sequential source code to executable binaries are discussed. The performance speedups attainable will be illustrated by several examples.

关键词： divide-and-conquer algorithms automatic parallelization parallelizing compilers message-passing multicomputers transputer systems workstation clusters

来源：评论

学校读者我要写书评

暂无评论

Code Optimizations for Parallelization of Programs using Data Dependence Identifier

引用

INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS 2021年第10期12卷 837-846页

作者： Alluru, Kavya Jeganathan, L. Vellore Inst Technol Sch Comp Sci & Engn Chennai Tamil Nadu India Vellore Inst Technol Ctr Adv Data Sci Chennai Tamil Nadu India

In a parallelizing Compiler, code transformations help to reduce the data dependencies and identify parallelism in a code. In our earlier paper, we proposed a model Data Dependence Identifier (DDI), in which a program P is represented as graph G(P). Using G(P), we could identify data dependencies in a program and also perform transformations like dead code elimination and constant propagation. In this paper, we present algorithms for loop invariant code motion, live range analysis, node splitting and loop fusion code transformations using DDI in polynomial time.

关键词： Automatic parallelization parallelizing compilers code optimizations data dependence loop invariant code motion node splitting live range analysis loop fusion

来源：评论

学校读者我要写书评

暂无评论

Migration of vectorized iterative solvers to distributed-memory architectures

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1996年第1期17卷 239-259页

作者： Pommerell, C Ruhl, R AT&T BELL LABS MURRAY HILL NJ 07974 USA INTEGRATED SYST ENGN AG CH-8005 ZURICH SWITZERLAND

Distributed-memory parallel processors (DMPPs) can deliver peak performance higher than vector supercomputers while promising a better cost-performance ratio. Programming, however, is harder than on traditional vector systems, especially when problems necessitating unstructured solution methods are considered. A class of such applications, with large resource requirements, is the numerical solution of partial differential equations (PDEs) on nonuniformly refined three-dimensional finite element discretizations. Porting an application of this class from vector and shared-memory parallel machines to DMPPs involves some fundamental algorithm changes, such as grid decomposition, mapping, and coloring strategies. In addition, no standardized language interface is available to ease the efficient parallelization and porting among DMPPs and between vector computers and DMPPs. This article describes how PILS-an existing package for the iterative solution of large unstructured sparse linear systems of equations on vector computers-was ported to DMPPs, using the parallelizing Fortran compiler Oxygen. Two DMPPs, namely an Intel Paragon and a Fujitsu AP1000, were used to evaluate the performance of the generated parallel program quantitatively. The results indicate how an application should be designed to be portable among supercomputers of different architecture. Several language and architecture features are essential for such a porting process and ease the parallelization of similar applications drastically.

关键词： distributed-memory parallel processing large-scale scientific computing iterative solvers parallelizing compilers inspector-executor unstructured sparse matrix computations

来源：评论

学校读者我要写书评

暂无评论

Formal methods to generate parallel iterative codes for PDE-based applications

Formal methods to generate parallel iterative codes for PDE-...

引用

IEEE International Conference on Engineering of Complex Computer Systems

作者： Peiyi Tang Department of Computer Science University of Arkansas Little Rock Little Rock AR USA

Developing parallel software is far more complex than traditional sequential software. An effective approach to deal with the complexity of parallel software is domain-specific programming in an abstraction higher than general-purpose programming languages. In this paper, we focus on the domain of the applications based on partial differential equations (PDE) and provide a formal framework and methods for PDE compilers to generate parallel iterative codes for the domain. We also provide a PDE compiler optimization to minimize the number of messages between parallel processors. Our framework and methods can be used to build PDE compilers to generate efficient parallel software for PDE-based applications automatically.

关键词： parallelizing compilers Optimizing compilers Parallel programming Partial differential equations Minimization methods Software requirements and specifications Message passing

来源：评论

学校读者我要写书评

暂无评论

A fine-grained MIMD architecture based upon register channels 23

A fine-grained MIMD architecture based upon register channel...

引用

Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture

作者： Rajiv Gupta Department of Computer Science University of Pittsburgh 220 Alumni Hall Pittsburgh PA

ISBN: (纸本)9780897914130

This paper discusses the use of shared register channels as a data exchange mechanism among processors in a fine-grained MIMD system with a load/store architecture. A register channel is provided with a synchronization bit that is used to ensure that a processor succeeds in reading a channel only after a value has been written to the channel. The instructions supported by this load/store architecture allow both registers and register channels to be used as operand sources and result destinations. Conditional load, store, and move instructions are provided to allow processors to exchange values through channels in presence of aliasing caused by array references. Compiler support required to take proper advantage of channels is briefly discussed. In contrast to a VLIW machine a system with channels does not require strict lockstep operation of its processors. This reduces the delays caused by unpredictable events such as memory bank conflicts.

关键词： parallelizing compilers instruction scheduling multiprocessor system fine-grained parallelism channels aliasing

来源：评论

学校读者我要写书评

暂无评论

Automatic Parallelization of Recursive Procedures 99

Automatic Parallelization of Recursive Procedures

引用

Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques

作者： Manish Gupta Sayak Mukhopadhyay Navin Sinha

ISBN: (纸本)9780769504254

parallelizing compilers have traditionally focussed mainly on parallelizing loops. This paper presents a new framework for automatically parallelizing recursive procedures that typically appear in divide-and-conquer algorithms. We present compile-time analysis to detect the independence of multiple recursive calls in a procedure. This allows exploitation of a scalable form of nested parallelism, where each parallel task can further spawn off parallel work in subsequent recursive *** describe a run-time system which efficiently supports this kind of nested parallelism without unnecessarily blocking tasks. We have implemented this framework in a parallelizing compiler, which is able to automatically parallelize programs like quicksort and mergesort, written in *** cases where even the advanced symbolic analysis and array section analysis we describe are not able to prove the independence of procedure calls, we propose novel techniques for speculative run-time parallelization, which are more efficient and powerful in this context than analogous techniques proposed previously for speculatively parallelizing loops. Our experimental results on an IBM G30 SMP machine show good speedups obtained by following our approach.

关键词： symbolic analysis parallelizing compilers recursive procedures automatic parallelization divide and conquer interprocedural analysis

来源：评论

学校读者我要写书评

暂无评论

Proceedings Seventh Workshop on Interaction between compilers and Computer Architectures. INTERACT-7 2003

Proceedings Seventh Workshop on Interaction between Compiler...

引用

Annual Workshop on Interaction between compilers and Computer Architectures

The following topics are dealt with: Java virtual machine (JVM) optimization and prefetching; procedure optimization; low power aware architecture and optimization; and region based optimization.

关键词： Optimizing compilers Computer architecture Memory management Power demand parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Multi-processor performance on the Tera MTA 98

Multi-processor performance on the Tera MTA

引用

Proceedings of the 1998 ACM/IEEE conference on Supercomputing

作者： Allan Snavely Larry Carter Jay Boisseau Amit Majumdar Kang Su Gatlin Nick Mitchell John Feo Brian Koblenz SDSC/UCSD SDSC UCSD Tera Computer

ISBN: (纸本)9780897919845

The Tera MTA is a revolutionary commercial computer based on a multithreaded processor architecture. In contrast to many other parallel architectures, the Tera MTA can effectively use high amounts of parallelism on a single processor. By running multiple threads on a single processor, it can tolerate memory latency and to keep the processor saturated. If the computation is sufficiently large, it can benefit from running on multiple processors. A primary architectural goal of the MTA is that it provide scalable performance over multiple processors. This paper is a preliminary investigation of the first multi-processor Tera *** a previous paper [1] we reported that on the kernel NAS 2 benchmarks [2], a single-processor MTA system running at the architected clock speed would be similar in performance to a single processor of the Cray T90. We found that the compilers of both machines were able to find the necessary threads or vector operations, after making standard changes to the random number generator. In this paper we update the single-processor results in two ways: we use only actual clock speeds, and we report improvements given by further tuning of the MTA *** then investigate the performance of the best single-processor codes when run on a two-processor MTA, making no further tuning effort. The parallel efficiency of the codes range from 77% to 99%. An analysis shows that the "serial bottlenecks" -- unparallelized code sections and the cost of allocating and freeing the parallel hardware resources -- account for less than a percent of the runtimes. Thus, Amdahl's Law needn't take effect on the NAS benchmarks until there are hundreds of processors running thousands of ***, the major source of inefficiency appears to be an imperfect network connecting the processors to the memory. Ideally, the network can support one memory reference per instruction. The current hardware has defects that reduce the throughput to about 85% of this rate. Except f

关键词： tera multithreaded architecture performance tuning performance evaluation NAS parallel benchmarks scalability analysis parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：