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

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2002年第12期13卷 1220-1233页

作者： Hodzic, E Shang, WJ Santa Clara Univ Dept Comp Engn Santa Clara CA 95053 USA

With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses the selection of an optimal supernode shape of a supernode transformation (also known as tiling). We identify three parameters of a supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For supernode transformations on algorithms with perfectly nested loops and uniform dependencies, we prove the optimality of a constant linear schedule vector and give a necessary and sufficient condition for optimal relative side lengths. We also prove that the total running time is minimized by a cutting hyperplane direction matrix from a particular subset of all valid directions and we discuss the cases where this subset is unique. The results are derived in continuous space and should be considered approximate. Our model does not include cache effects and assumes an unbounded number of available processors, the communication cost approximated by a constant, uniform dependences, and loop bounds known at compile time. A comprehensive example is discussed with an application of the results to the Jacobi algorithm.

关键词： supernode transformation tiling algorithm partitioning parallelizing compilers minimizing running time distributed memory multicomputer

来源：评论

学校读者我要写书评

暂无评论

An Analytical Evaluation of Data Dependence Analysis Techniques

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2019年第5-6期47卷 781-804页

作者： Niedzielski, David Psarris, Kleanthis Theoharis, Theoharis Massey Univ Albany Inst Informat & Math Sci Auckland New Zealand CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Natl Univ Athens Dept Informat Athens 15784 Greece

Optimizing compilers rely upon data dependence analysis to reveal the ordering constraints among statements in a program that need to be preserved in order to produce valid optimized and parallel code. Testing array references for data dependence is equivalent to determining whether a system of equalities and inequalities has an integer solution. A number of data dependence tests have been proposed in the literature. In each test there are different tradeoffs between accuracy and efficiency. In this paper we study the fundamental relationships between several data dependence tests. We consider the Banerjee Extreme Value test, Fourier Motzkin Variable Elimination (FMVE), the I-Test, and the Omega test, which are representative of the state of the art in data dependence analysis. The Banerjee Extreme Value test and FMVE can only determine the existence of real solutions to a system. Thus they can only disprove, but not prove, data dependence. The I-Test and the Omega test refine the Banerjee Extreme Value test and FMVE, respectively, to the integer domain and can prove data dependence. The Omega test is a more accurate data dependence test, but with worst case exponential time complexity. The I-Test is a polynomial time test, but it is not always conclusive. We first show that FMVE is equivalent to the Banerjee Extreme Value test. We then show that the Omega test's technique to refine FMVE to integer solutions (dark shadow) is equivalent to the I-Test's refinement of the Banerjee Extreme Value test to integer solutions (the accuracy condition). We prove that the I-Test returns an inconclusive ("maybe") answer if and only if the Omega test requires an exponential time exhaustive search to produce an exact answer (the so-called "Omega Test Nightmare").

关键词： parallelizing compilers Data dependence Program analysis Automatic parallelization Compiler optimization

来源：评论

学校读者我要写书评

暂无评论

List scheduling in the presence of branches - A theoretical evaluation

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期196卷 347-363页

作者： Gasperoni, F Schwiegelshohn, U Univ Dortmund Dept Comp Engn D-44221 Dortmund Germany Telecom Paris ENST F-75634 Paris 13 France

The extraction of operation level parallelism from sequential code has become an important problem in compiler research due to the proliferation of superscalar and VLIW architectures. This problem becomes especially hard for code containing a large number of conditionals. In this paper we extend previous work on straight line code scheduling by looking at task systems with branches. First, we define an optimality measure based on the probability of the various execution paths. Then, we apply a list scheduling algorithm to these systems and derive a worst-case-performance guarantee for this method. Finally, we show that there are branching task systems for which this bound is almost tight. (C) 1998-Elevier Science B.V. All rights reserved.

关键词： instruction scheduling performance guarantee parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

The UTFLA: uniformization of non-uniform iteration spaces in two-level perfect nested loops using SFLA

引用

JOURNAL OF SUPERCOMPUTING 2016年第6期72卷 2221-2234页

作者： Mahjoub, Shabnam Vojoudi, Hakimeh Islamic Azad Univ Dept Comp Engn Langaroud Branch Langaroud Iran

One of the factors increasing the execution time of computational programs is the loops, and parallelization of the loops is used to decrease this time. One of the steps of parallelizing compilers is uniformization of non-uniform loops in wavefront method which is considered as a NP-hard problem. In this paper, a new method has been presented to make uniform the non-uniform two-level perfect nested loops using the frog-leaping algorithm, called UTFLA, which is a combination of deterministic and stochastic methods, because the challenge most of loop paralleling methods, old or dynamic or new ones, face is the high algorithm execution time. UTFLA has been designed in a way to find the best results with the lowest amount of basic dependency cone size in the minimum possible time and gives more appropriate results in a more reasonable time compared to other methods.

关键词： parallelizing compilers Uniformization Loops Frog leaping algorithm

来源：评论

学校读者我要写书评

暂无评论

Design and implementation of a communication-efficient data-parallel program compiling system

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2001年第5期17卷 825-839页

作者： Shih, KP Lai, CY Sheu, JP Tseng, YC Tamkang Univ Dept Comp Sci & Informat Engn Taipei 251 Taiwan Natl Cent Univ Dept Comp Sci & Informat Engn Tao Yuan 320 Taiwan Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 300 Taiwan

In this paper, we present the design and implementation of a data-parallel compiling system. The system has been implemented on a DEC Alpha 3000 workstation and incorporated into a parallel programming environment called UPPER (User-interactive Parallel Programming EnviRonment). Given an HPF program, the built-in compiler system can automatically analyze the access pattern of the HPF program, enumerate the computation and communication sets, and then generate the SPMD code for execution on nCUBE/2. Moreover, the user interface is designed to help the programmer to capture some information during the compilation and execution phases, including interprocessor communication, distribution of data elements onto processors, and execution results.

关键词： communication sets distributed-memory multicomputers high performance Fortran (HPF) parallelizing compilers single program multiple data (SPMD)

来源：评论

学校读者我要写书评

暂无评论

Analysis of local enumeration and storage schemes in HPF

引用

PARALLEL COMPUTING 1998年第3-4期24卷 355-382页

作者： Sips, HJ Denissen, W van Reeuwijk, K Delft Univ Technol Dept Comp Sci NL-2628 BZ Delft Netherlands

In this paper, we analyze the properties and efficiency of three basic local enumeration and three storage compression schemes for cyclic(ln) data distributions in High Performance Fortran (HPF). The methods an presented in a unified framework, showing the relations between the various methods. We show that for array accesses that are affine functions of the loop bounds, efficient local enumeration and storage compression schemes can be derived. Furthermore, the basic set enumeration and storage techniques are shown to be orthogonal, if the local storage compression scheme is collapsible. This allows choosing the most appropriate method in parts of the computation and communication phases of parallel loops. Performance figures of the methods show that programs with cyclic(m) data distributions can be executed efficiently even without compile-time knowledge of the relevant access, alignment, and distribution parameters. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers data parallel languages High Performance Fortran

来源：评论

学校读者我要写书评

暂无评论

Data dependence analysis for array references

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2000年第1期52卷 55-65页

作者： Huang, TC Yang, CM Natl Sun Yat Sen Univ Dept Elect Engn Kaohsiung 804 Taiwan

Data dependence analysis is essential in order to determine whether a loop can be vectorized or parallelized. It is used to investigate whether two memory references in a loop are in the same location. In this paper we present a new scheme of exact data dependence analysis for array subscript analysis in parallel programs, called interval reduction (IR) test. This method reduces the solution interval of each constraint variable in the dependence equation by repeated projection. Once the effective solution interval of any variable shrinks to empty, this linear diophantine equation has no integer solution and the memory accesses subject to this constraint are then independent. Otherwise, all the integer solutions can be found, and thus the dependence distance can be computed as well. Experimental results are also presented to show its effectiveness compared to the Power test and the Omega test. (C) 2000 Published by Elsevier Science Inc. All rights reserved.

关键词： array references data dependence analysis interval reduction test linear diophantine equation parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

COMPILE-TIME TECHNIQUES FOR DATA DISTRIBUTION IN DISTRIBUTED MEMORY MACHINES

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1991年第4期2卷 472-482页

作者： RAMANUJAM, J SADAYAPPAN, P OHIO STATE UNIV DEPT COMP & INFORMAT SCICOLUMBUSOH 43210

This paper addresses the problem of partitioning data for distributed memory machines (multicomputers). In current day multicomputers, interprocessor communication is more time-consuming than instruction execution. If insufficient attention is paid to the data allocation problem, then the amount of time spent in interprocessor communication might be so high as to seriously undermine the benefits of parallelism. It is therefore worthwhile for a compiler to analyze patterns of data usage to determine allocation, in order to minimize interprocessor communication. We present a machine-independent analysis of communication-free partitions. We present a matrix notation to describe array accesses in fully parallel loops which lets us derive sufficient conditions for communication-free partitioning (decomposition) of arrays. In the case of a commonly occurring class of accesses, we present a problem formulation to minimize communication costs, when communication-free partitioning of arrays is not possible.

关键词： ACCESS AND DEPENDENCE BASED ARRAY PARTITIONING COMMUNICATION-FREE PARTITIONING DATA DECOMPOSITION DISTRIBUTED MEMORY MACHINES parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Efficient compiler and run-time support for parallel irregular reductions

引用

PARALLEL COMPUTING 2000年第13-14期26卷 1861-1887页

作者： Han, H Tseng, CW Univ Maryland Dept Comp Sci College Pk MD 20742 USA

Many scientific applications are comprised of irregular reductions on large data sets. In shared-memory parallel programs, these irregular reductions are typically computed in parallel using replicated buffers, then combined using synchronization. We develop LOCALWRITE, a new technique which partitions irregular reductions so that each processor computes values only for locally assigned data, eliminating the need for buffers or synchronized writes. Computation is replicated if its results are needed on multiple processors. We experimentally evaluate its performance for three irregular codes on a software DSM running on a distributed-memory multiprocessor and two shared-memory multiprocessors while varying connectivity, locality, and adaptivity. Results show LOCALWRITE improves performance significantly compared to using replicated buffers, and can match or exceed explicit message-passing gather/scatter for applications with low locality or high adaptivity. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers locality optimizations irregular computations

来源：评论

学校读者我要写书评

暂无评论

Parallel solutions of simple indexed recurrence equations

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2001年第1期12卷 22-37页

作者： Ben-Asher, Y Haber, G Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Matam Adv Technol Ctr IBM Res Lab IL-31905 Haifa Israel

We define a new type of recurrence equations called "Simple Indexed Recurrences" (SIR). In this type of equations. ordinary recurrences are generalized to X[g(i)] = op(i) (X[f(i)],X[g(i)]), where f,g : {1... n}bar right arrow{1...m}, op(i)(x, y) is a binary associative operator and g is distinct. i.e., For All (i) not equal j g(i) not equal g(j). This enables us to model certain sequential loops as a sequence of SIR equations. A parallel algorithm that solves a set of SIR equations will, in fact, parallelize sequential loops of the above type. Such a parallel SIR algorithm must be efficient enough to compete with the O(n) work complexity of the original loop. We show why efficient parallel algorithms for the related problems of List Ranking and Tree Contraction. which require O(n.) work, cannot be applied to solving SIR. We instead use repeated iterations of pointer jumping to compute the final values of X[] in n/p . log p steps and n . logp work, with I, processors. A sequence of experiments was performed to test the effect of synchronous and asynchronous executions on the actual performance of the algorithm. These experiments show that pointer jumping requires O(n) work in most practical cases of SIR loops. An efficient solution is given for the special case where we know how to compute the inverse of op(i), and finally, useful applications of SIR to the well-known Livermore Loops benchmark are presented.

关键词： ordinary recurrence equations indexed recurrence equations pointer jumping list ranking tree contraction parallel prefix sums Euler tour parallelizing compilers Livermore Loops benchmark

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：