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

Data dependence analysis techniques for increased accuracy and extracted parallelism

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2004年第4期32卷 317-359页

作者： Kyriakopoulos, K Psarris, K Univ Texas Dept Comp Sci San Antonio TX 78249 USA

parallelizing compilers rely on data dependence information in order to produce valid parallel code. Traditional data dependence analysis techniques, such as the Banerjee test and the I-Test, can efficiently compute data dependence information for simple instances of the data dependence problem. However, in more complex cases involving triangular or trapezoidal loop regions, symbolic variables, and multidimensional arrays with coupled subscripts these tests, including the triangular Banerjee test, ignore or simplify many of the constraints and thus introduce approximations, especially when testing for data dependence under direction vector constraints. The Omega test can accurately handle such complex cases, but at a higher computation cost. In this paper we extend the ideas behind the I-Test and present new techniques to handle complex instances of the dependence problem, which are frequently found in actual source code. In particular, we provide polynomial-time techniques that can prove or disprove data dependences, subject to any direction vector, in loops with triangular or trapezoidal bounds, symbolic variables, and multidimensional arrays with coupled subscripts. We also investigate the impact of the proposed data dependence analysis techniques in practice. We perform an extensive experimental evaluation of the data dependence analysis tests, including the I-Test, the Omega test and the proposed new techniques. We compare these tests in terms of data dependence accuracy, compilation efficiency and effectiveness in program parallelization. We run several experiments using the Perfect Club benchmarks and the scientific library Lapack. We analyze the trade-off between accuracy and efficiency and the reasons for any approximation of each data dependence test. We determine the impact of the dependence analysis phase on the total compilation time and we measure the number of loops parallelized by each test. We conclude that we can employ polynomial-time techniques t

关键词： parallelizing compilers data dependence program analysis automatic parallelization compiler optimization

来源：评论

学校读者我要写书评

暂无评论

The infinity Lambda test: A multi-dimensional version of Banerjee infinity test

引用

PARALLEL COMPUTING 2000年第10期26卷 1275-1295页

作者： Chang, WL Chu, CP Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

The Banerjee infinity test accurately determines data dependence for one linear equation under symbolic limits and any given direction vectors (U. Banerjee, Depence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988;P.M. Petersen, Evaluation of programs and parallelizing compilers using dynamic analysis techniques, Ph.D. Thesis, University of Illinois at Urbana-Champaign, January 1993). For m linear equations with the same constraints, as each linear equation has to be tested separately, the Banerjee infinity test may generally lose the accuracy. In this paper, we proposed the infinity Lambda test - a multidimensional version of the Banerjee infinity test. The infinity Lambda test can be applied to deal with data dependence of coupled arrays with symbolic (unknown at compile time) bounds. Experiments with benchmark showed that the infinity Lambda test increases the success rate of the Lambda test by approximately 12%. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers vectorizing compilers data dependence analysis

来源：评论

学校读者我要写书评

暂无评论

Scalable Conditional Induction Variables (CIV) Analysis

Scalable Conditional Induction Variables (CIV) Analysis

引用

Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO)

作者： Oancea, Cosmin E. Rauchwerger, Lawrence Univ Copenhagen Dept Comp Sci DK-1168 Copenhagen Denmark Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

ISBN: (纸本)9781479981625

Subscripts using induction variables that cannot be expressed as a formula in terms of the enclosing-loop indices appear in the low-level implementation of common programming abstractions such as filter, or stack operations and pose significant challenges to automatic parallelization. Because the complexity of such induction variables is often due to their conditional evaluation across the iteration space of loops we name them Conditional Induction Variables (CIV). This paper presents a flow-sensitive technique that summarizes both such CIV-based and affine subscripts to program level, using the same representation. Our technique requires no modifications of our dependence tests, which is agnostic to the original shape of the subscripts, and is more powerful than previously reported dependence tests that rely on the pairwise disambiguation of read-write references. We have implemented the CIV analysis in our parallelizing compiler and evaluated its impact on five Fortran benchmarks. We have found that that there are many important loops using CIV subscripts and that our analysis can lead to their scalable parallelization. This in turn has led to the parallelization of the benchmark programs they appear in.

关键词： parallelization parallelizing compilers corner marks Stack operations Conditional BENCHMARKS Loops Scalability In-law LOW LEVEL read/write Agnostic formula

来源：评论

学校读者我要写书评

暂无评论

Compiling parallel MATLAB for general distributions using telescoping languages

Compiling parallel MATLAB for general distributions using te...

引用

32nd IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Fletcher, Mary McCosh, Cheryl Jin, Guohua Kennedy, Ken Rice Univ Dept Comp Sci Houston TX 77005 USA

ISBN: (纸本)1424407281

Matlab is one of the most popular computer languages for technical and scientific programming. However, until recently, it has been limited to running on uniprocessors. One strategy for overcoming this limitation is to introduce global distributed arrays, with those arrays distributed across the processors of a parallel machine. In this paper, we describe the compilation technology we have designed for Matlab D, a distributed-array extension of Matlab. Our approach is distinguished by a two-phase compilation technology with support for a rich collection of data distributions. By precompiling array operations and communication steps into Fortran plus MPI, the time to compile an application using those operations is significantly reduced. This paper includes preliminary results that demonstrate that this approach can dramatically improve performance, scaling well to at least 32 processors.

关键词： parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

A DISTRIBUTED IMPLEMENTATION OF SHARED VIRTUAL MEMORY WITH STRONG AND WEAK COHERENCE 2nd

A DISTRIBUTED IMPLEMENTATION OF SHARED VIRTUAL MEMORY WITH S...

引用

2ND EUROPEAN CONF ON DISTRIBUTED MEMORY COMPUTING ( EDMCC2 )

作者： GILOI, WK HASTEDT, C SCHOEN, F SCHROEDERPREIKSCHAT, W GMD Research Center for Innovative Computer Systems and Technology Technical University of Berlin Germany

ISBN: (纸本)3540539514

A virtual shared memory architecture (VSMA) is a distributed memory architecture that looks to the application software as if it were a shared memory system. The major problem with such a system is to maintain the coherence of the distributed data entities. Shared virtual memory means that the shared data entities are pages of local virtual memories with demand paging. Memory coherence may be strong or weak. Strong coherence is a scheme where all the shared data entities look from the outside as if they were stored in one coherent memory. This simplifies programming of a distributed memory system at the cost of a high message traffic in the system, needed to maintain the strong coherence. The efficiency of the system can be increased by adding a weak coherence scheme that allows for multiple writes by different threads of control into the same page. The price of the weak coherence scheme is the need for explicit program synchronizations, needed to reestablish at the end the strong coherence of the result. For the computer architect, the challenging question is how to implement a VSMA most efficiently and, specifically, by what architectural means to support the implementation. In the paper a new solution to this question is presented based upon an innovative distributed memory architecture in which communication is conducted by a dedicated communication processor in each node rather than by the node CPU. This will make the exchange of short, fixed-size messages, e.g., invalidation notices, very efficient. Therefore, it becomes more appropriate to minimize the overall administrative overhead, even at the cost of more message traffic. On that rationale, a novel, capability-based mechanism for both strong and weak coherence of shared virtual memory is presented. The weak coherence scheme is built on top of the strong coherence, utilizing its mechanisms. The proposed implementation is totally distributed and based on a strict need to know philosophy. Consequently, the e

关键词： DISTRIBUTED MEMORY ARCHITECTURE VIRTUAL SHARED MEMORY ARCHITECTURE STRONG AND WEAK DATA COHERENCE COMMUNICATION HARDWARE parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Enhancing the Performance of a Multiplayer Game by Using a parallelizing Compiler

Enhancing the Performance of a Multiplayer Game by Using a P...

引用

17th International Conference on Computer Games (CGAMES) - AI, Animation, Mobile, Interactive Multimedia, Educational and Serious Games

作者： Al-Dosary, Yasir I. M. Kimura, Keiji Kasahara, Hironori Narita, Seinosuke Waseda Univ Dept Comp Sci & Engn Shinjuku Ku Tokyo 1698555 Japan

ISBN: (纸本)9781467311199

Video Games have been a very popular form of digital entertainment in recent years. They have been delivered in state of the art technologies that include multi-core processors that are known to be the leading contributor in enhancing the performance of computer applications. Since parallel programming is a difficult technology to implement, that field in Video Games is still rich with areas for advancements. This paper investigates performance enhancement in Video Games when using parallelizing compilers and the difficulties involved in achieving that. This experiment conducts several stages in attempting to parallelize a well-renowned sequentially written Video Game called ioquake3. First, the Game is profiled for discovering bottlenecks, then examined by hand on how much parallelism could be extracted from those bottlenecks, and what sort of hazards exist in delivering a parallel-friendly version of ioquake3. Then, the Game code is rewritten into a hazard-free version while also modified to comply with the Parallelizable-C rules, which crucially aid parallelizing compilers in extracting parallelism. Next, the program is compiled using a parallelizing compiler called OSCAR (Optimally Scheduled Advanced Multiprocessor) to produce a parallel version of ioquake3. Finally, the performance of the newly produced parallel version of ioquake3 on a Multi-core platform is analyzed. The following is found: (1) the parallelized game by the compiler from the revised sequential program of the game is found to achieve a 5.1 faster performance at 8-threads than original one on an IBM Power 5+ machine that is equipped with 8-cores, and (2) hazards are caused by thread contentions over globally shared data, and as well as thread private data, and (3) AI driven players are represented very similarly to Human players inside ioquake3 engine, which gives an estimation of the costs for parallelizing Human driven sessions, and (4) 70% of the costs of the experiment is spent in analyzing

关键词： component Video Games Quake ioquake3 parallel Computing parallelizing compilers OSCAR

来源：评论

学校读者我要写书评

暂无评论

Extracting Coarse-Grained Parallelism for Affine Perfectly Nested Quasi-uniform Loops 1

引用

9th International Conference on Parallel Processing and Applied Mathematics (PPAM)

作者： Bielecki, Wlodzimierz Kraska, Krzysztof W Pomeranian Univ Technol Fac Comp Sci & Informat Technol PL-71210 Szczecin Poland

ISBN: (数字)9783642314643

ISBN: (纸本)9783642314636;9783642314643

This paper presents a new approach for the extraction of coarse-grained parallelism available in program loops. The approach permits for extracting parallelism for both uniform and quasi-uniform perfectly nested parameterized loops, where the loop bounds and data accesses are affine functions of loop indices and symbolic parameters. It extracts a set of synchronization-free code fragments. The procedure has a polynomial time complexity except for one step of calculations. The effectiveness and time complexity of the approach are evaluated by means of loops of the NAS Parallel Benchmark suite.

关键词： parallelizing compilers loop transformation quasi-uniform dependences polyhedral model

来源：评论

学校读者我要写书评

暂无评论

PROCESSOR ALLOCATION AND SCHEDULING OF MACRO DATA-FLOW GRAPHS ON DISTRIBUTED-MEMORY MULTICOMPUTERS BY THE PARADIGM COMPILER

PROCESSOR ALLOCATION AND SCHEDULING OF MACRO DATA-FLOW GRAPH...

引用

1993 International Conference on Parallel Processing

作者： RAMASWAMY, S BANERJEE, P UNIV ILLINOIS CTR RELIABLE & HIGH PERFORMANCE COMPURBANAIL 61801

ISBN: (纸本)0849389852

Functional or Control parallelism is an effective way to increase speedups in Multicomputers. Programs for these machines are represented by Macro Dataflow Graphs (MDGs) for the purpose of functional parallelism analysis and exploitation. Algorithms for allocation and scheduling of MDGs have been discussed along with some analysis of their optimality. These algorithms attempt to minimize the execution time of any given MDG through exploitation of functional parallelism. Our preliminary results show their effectiveness over naive algorithms. © 1993 IEEE.

关键词： MACRO DATA-FLOW GRAPHS DISTRIBUTED MEMORY MULTICOMPUTERS ALLOCATION AND SCHEDULING parallelizing compilers OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

Optimization techniques for parallel codes of irregular scientific computations

Optimization techniques for parallel codes of irregular scie...

引用

31st International Conference on Parallel Processing (ICPP 2002)

作者： Guo, MY Chang, WL Pan, Y Univ Aizu Dept Comp Software Fukushima 9658580 Japan

ISBN: (纸本)0769516807

In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. For an irregular loop with nonlinear array subscripts, the loop is transformed to a normalized single loop, then we partition the loop iterations to processors on which the minimal communication cost is ensured when executing those iterations. We also give some interprocedural optimization techniques for communication preprocessing when the irregular code has the procedure call. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

关键词： parallelizing compilers irregular scientific application communication optimization loop transformation loop partitioning interprocedural optimization

来源：评论

学校读者我要写书评

暂无评论

Three-dimensional orthogonal tile sizing problem: Mathematical programming approach

Three-dimensional orthogonal tile sizing problem: Mathematic...

引用

IEEE International Conference on Application-Specific Systems, Architectures and Processes

作者： Andonov, R Yanev, N Bourzoufi, H Universite de Valenciennes Valenciennes France

ISBN: (纸本)0818679581

We discuss in this paper the problem of finding the optimal tiling transformation of three-dimensional uniform recurrences on a two-dimensional torus/grid of distributed-memory general-purpose machines. We show that even for the simplest case of recurrences which allows for such transformation, the corresponding problem of minimizing the total running time is a non-trivial non-linear integer programming problem. For the later we derive an O(1) algorithm for finding a good approximation solution. The theoretical evaluations and the experimental results show the obtained solution approximates the original minimum sufficiently well in the context of the considered problem. Such analytical results are of obvious interest and can be successfully used in parallelizing compilers as well as in performance tuning of parallel codes.

关键词： tiling mapping parallelizing compilers integer optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：