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

PARALLEL LOOPS - A TEST SUITE FOR parallelizing compilers - DESCRIPTION AND EXAMPLE RESULTS

PARALLEL COMPUTING 1991年第10-11期17卷 1247-1255页

作者： DONGARRA, J FURTNEY, M REINHARDT, S RUSSELL, J CRAY RES INC EAGANMN 55121 OAK RIDGE NATL LAB MATH SCI SECTOAK RIDGETN 37831

Several multiprocessor systems are now commercially available, and advances in compiler technology provide automatic conversion of programs to run on such systems. However, no accepted measure of this parallel compiler ability exists. This paper presents a test suite of subroutines and loops, called Parallel Loops, designed to (1) measure the ability of parallelizing compilers to convert code to run in parallel and (2) determine how effectively parallel hardware and software work together to achieve high performance across a range of problem sizes. In addition, we present the results of compiling this suite using two commercially available parallelizing Fortran compilers, Cray and Convex.

关键词： MULTIPROCESSOR SYSTEMS parallelizing compilers PARALLEL TEST SUITE RESULTS CRAY CONVEX

来源：评论

学校读者我要写书评

暂无评论

A unified symbolic evaluation framework for parallelizing compilers

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2000年第11期11卷 1105-1125页

作者： Fahringer, T Scholz, B Univ Vienna Inst Software Sci A-1090 Vienna Austria Vienna Univ Technol Inst Comp Languages A-1040 Vienna Austria

The quality of many optimizations and analyses of parallelizing compilers depends significantly on the ability to evaluate symbolic expressions and on the amount of information available about program variables at arbitrary program points. In this paper, we describe an effective and unified symbolic evaluation framework that statically determines the values of variables and symbolic expressions, assumptions about and constraints between variable values, and the condition under which control flow reaches a program statement. We introduce the program context, a novel representation for comprehensive and compact control and data flow analysis information. Program contexts are described as first order logic formulas, which allows us to use public domain software for standard symbolic manipulation. Computations are represented as algebraic expressions defined over a program's problem size. Our symbolic evaluation techniques comprise accurate modeling of assignment and input/output statements, branches, loops, recurrences, arrays, and procedures. All of our techniques target both linear, as well as nonlinear, expressions and constraints. Efficiency of symbolic evaluation is highly improved by aggressive simplification techniques. A variety of examples, including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication, are used to illustrate the effectiveness of our approach. We present results from a preliminary implementation of our framework, which is used as part of a parallelizing compiler that demonstrates the potential performance gains achievable by employing symbolic evaluation to support program parallelization.

关键词： symbolic analysis symbolic evaluation program context data-flow and control-flow analysis symbolic dependence testing compiler optimizations parallelizing compilers parallel systems

来源：评论

学校读者我要写书评

暂无评论

COMMUNICATION-FREE DATA ALLOCATION TECHNIQUES FOR parallelizing compilers ON MULTICOMPUTERS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第9期5卷 924-938页

作者： CHEN, TS SHEU, JP Department of Computer Science and Information Engineering National Central University Chungli Taiwan

In distributed memory multicomputers, local memory accesses are much faster than those involving interprocessor communication. For the sake of reducing or even eliminating the interprocessor communication, the array elements in programs must be carefully distributed to local memory of processors for parallel execution. In this paper, we devote our efforts to the techniques of allocating array elements of nested loops onto multicomputers in a communication-free fashion for parallelizing compilers. We first analyze the pattern of references among all arrays referenced by a nested loop, and then partition the iteration space into blocks without interblock communication. The arrays can be partitioned under the communication-free criteria with nonduplicate or duplicate data. Finally, a heuristic method for mapping the partitioned array elements and iterations onto the fixed-size multicomputers under the consideration of load balancing is proposed. Based on our methods, the nested loops can execute without any communication overhead on the distributed memory multicomputers. Moreover, the performance of the strategies with nonduplicate and duplicate data for matrix multiplication is studied.

关键词： DATA ALLOCATION DATA DEPENDENCE DISTRIBUTED MEMORY MULTICOMPUTERS INTERPROCESSOR COMMUNICATION parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Statement-level communication-free partitioning techniques for parallelizing compilers

引用

JOURNAL OF SUPERCOMPUTING 2000年第3期15卷 243-269页

作者： Shih, KP Sheu, JP Huang, CH Natl Cent Univ Dept Comp Sci & Informat Engn Chungli 32054 Taiwan Natl Dong Hua Univ Dept Comp Sci & Informat Engn Hualien Taiwan

This paper addresses the problem of communication-free partition of iteration spaces and data spaces along hyperplanes. To finding more possible communication-free hyperplane partitions, we treat statements within a loop body as separate schedulable units. Instead of using the information about data dependence distance or direction vectors, our technique explicitly formulates array references as transformations from statement-iteration spaces to data spaces. Based on these transformations, the necessary and sufficient conditions for communication-free partition along hyperplanes to be feasible have been proposed. This approach can be applied to all programs with an imperfectly nested loop or sequences of imperfectly nested loops, whose array references are affine functions of outer loop indices or loop invariant variables. The proposed approach is more practical than existing methods in finding the data and computation distribution patterns that can cause the processor to execute fully-parallel on multicomputers without any interprocessor communication.

关键词： communication-free data communication distributed-memory multicomputers hyperplane partition parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

DEMONSTRATION OF AUTOMATIC DATA PARTITIONING TECHNIQUES FOR parallelizing compilers ON MULTICOMPUTERS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第2期3卷 179-193页

作者： GUPTA, M BANERJEE, P UNIV ILLINOIS ELECT & COMP ENGNURBANAIL 61801 UNIV ILLINOIS COORDINATED SCI LABCTR RELIABLE & HIGH PERFORMANCE COMPURBANAIL 61801

An important problem facing numerous research projects on parallelizing compilers for distributed memory machines is that of automatically determining a suitable data partitioning scheme for a program. Most of the current projects leave this tedious problem almost entirely to the user. In this paper, we present a novel approach to the problem of automatic data partitioning. We introduce the notion of constraints on data distribution, and show how, based on performance considerations, a compiler identifies constraints to be imposed on the distribution of various data structures. These constraints are then combined by the compiler to obtain a complete and consistent picture of the data distribution scheme, one that offers good performance in terms of the overall execution time. We present results of a study we performed on Fortran programs taken from the Linpack and Eispack libraries and the Perfect Benchmarks to determine the applicability of our approach to real programs. The results are very encouraging, and demonstrate the feasibility of automatic data partitioning for programs with regular computations that may be statically analyzed, which covers an extremely significant class of scientific application programs.

关键词： AUTOMATIC DATA PARTITIONING CONSTRAINTS INTERPROCESSOR COMMUNICATION MULTICOMPUTERS parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

An experimental evaluation of data dependence analysis techniques

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2004年第3期15卷 196-213页

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

Optimizing compilers rely upon program analysis techniques to detect data dependences between program statements. Data dependence information captures the essential ordering constraints of the statements in a program that need to be preserved in order to produce valid optimized and parallel code. Data dependence testing is very important for automatic parallelization, vectorization, and any other code transformation. In this paper, we examine the impact of data dependence analysis in practice. A number of data dependence tests have been proposed in the literature. In each test, there are different trade offs between accuracy and efficiency. We present an experimental evaluation of several data dependence tests, including the Banerjee test, the I-Test, and the Omega test. We compare these tests in terms of data dependence accuracy, compilation efficiency, effectiveness in parallelization, and program execution performance. We analyze the reasons why a data dependence test can be inexact and we explain how the examined tests handle such cases. We run various experiments using the Perfect Club Benchmarks and the scientific library Lapack. We present the measured accuracy of each test and the reasons for any approximation. We compare these tests in terms of efficiency and we analyze the trade offs between accuracy and efficiency. We also determine the impact of each data dependence test on the total compilation time. Finally, we measure the number of loops parallelized by each test and we compare the execution performance of each benchmark on a multiprocessor. Our results indicate that the Omega test is more accurate, but also very inefficient in the cases where the other two tests are inaccurate. In general, the cost of the Omega test is high and uses a significant percentage of the total compilation time. Furthermore, the difference in accuracy of the Omega test over the Banerjee test and the I-Test does not improve parallelization and program execution performance.

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

来源：评论

学校读者我要写书评

暂无评论

Communication-free alignment for array references with linear subscripts in three loop index variables or quadratic subscripts

引用

JOURNAL OF SUPERCOMPUTING 2001年第1期20卷 67-83页

作者： Chang, WL Chu, CP Wu, JH Kung Shan Technol Univ Dept Management Informat Syst Tainan 701 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Bau et al. proposed an efficient and precise data alignment method to ascertain whether there is communication-free alignment of array reference function with linear subscripts in one loop index variable. Chu et al. presented an efficient and precise data alignment method to determine whether there is communication-free alignment of array reference function with linear subscripts in two loop index variables or quadratic subscripts (ai(2)+bi+d). However, for array reference function with linear subscripts in three loop index variables or quadratic subscripts (ai(2)+bi+cj+d), their methods cannot be applied. In this paper, we propose two new alignment functions for loop iteration space and array elements. The new alignment functions can be applied towards checking whether there is communication-free alignment of array reference function with linear subscripts in three loop index variables or quadratic subscripts. Experiments with benchmarks taken from Parallel loop and Vector loop showed that among the 7 nested loops tested, three of them had their data alignment improved by the method proposed.

关键词： parallelizing compilers communication-free alignment parallel computing loop optimization data dependence analysis load balancing

来源：评论

学校读者我要写书评

暂无评论

Characterizing the memory behavior of compiler-parallelized applications

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1996年第12期7卷 1224-1237页

作者： Torrie, E Martonosi, M Tseng, CW Hall, MW PRINCETON UNIV DEPT ELECT ENGNPRINCETONNJ 08544 UNIV MARYLAND DEPT COMP SCICOLLEGE PKMD 20742 UNIV SO CALIF INST INFORMAT SCIMARINA DEL REYCA 90292

Compiler-parallelized applications are increasing in importance as moderate-scale multiprocessors become common. This paper evaluates how features of advanced memory systems (e.g., longer cache lines) impact memory system behavior for applications amenable to compiler parallelization. Using full-sized input data sets and applications taken from standard benchmark suites, we measure statistics such as speedups, synchronization and load imbalance, causes of cache misses, cache line utilization, data traffic, and memory costs. This exploration allows us to draw several conclusions. First, we find that larger granularity parallelism often correlates with good memory system behavior, good overall performance, and high speedup in these applications. Second, we show that when long (512 byte) cache lines are used, many of these applications suffer from false sharing and low cache line utilization. Third, we identity some of the common artifacts in compiler-parallelized codes that can lead to false sharing or other types of poor memory system performance, and we suggest methods for improving them. Overall, this study offers both an important snapshot of the behavior of applications compiled by state-of-the-art compilers, as well as an increased understanding of the interplay between cache line size, program granularity, and memory performance in moderate- scale multiprocessors.

关键词： parallelizing compilers memory hierarchies shared-memory multiprocessors cache performance false and true sharing parallelism granularity

来源：评论

学校读者我要写书评

暂无评论

AUTOMATIC EXTRACTION OF FUNCTIONAL PARALLELISM FROM ORDINARY PROGRAMS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第2期3卷 166-178页

作者： GIRKAR, M POLYCHRONOPOULOS, CD UNIV ILLINOIS DEPT ELECT & COMP ENGNURBANAIL 61801

Thus far, parallelism at the loop level (or data-parallelism) has been almost exclusively the main target of parallelizing compilers. The variety of new parallel architectures and recent progress in interprocedural dependence analysis, suggest new directions for the exploitation of parallelism across loop and procedure boundaries (or functional-parallelism). This paper presents the Hierarchical Task Graph (HTG) as an intermediate parallel program representation which encapsulates minimal data and control dependences, and which can be used for the extraction and exploitation of functional, or task-level parallelism. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability to a variety of parallel architectures. We focus on the construction of the HTG at a given hierarchy level, the derivation of the execution conditions of tasks which maximizes task-level parallelism, and the optimization of these conditions which results in reducing synchronization overhead imposed by data and control dependences. We present algorithms for the formation of tasks and their execution conditions based on data and control dependence constraints. Subsequently, we discuss the issue of optimization of such conditions and propose optimization algorithms. The HTG, which is being implemented in the Parafrase-2 compiler, is used as the intermediate representation of parallel Fortran and C programs for generating parallel source as well as parallel machine code.

关键词： CODE GENERATION CONTROL AND DATA DEPENDENCE INTERMEDIATE PROGRAM REPRESENTATION PARALLEL LANGUAGES parallelizing compilers SYNCHRONIZATION

来源：评论

学校读者我要写书评

暂无评论

Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism

引用

JOURNAL OF LOGIC PROGRAMMING 1999年第2期38卷 165-218页

作者： Muthukumar, K Bueno, F de la Banda, MG Hermenegildo, M Univ Politecn Madrid Fac Informat Sch Comp Sci E-28660 Madrid Spain Apple Comp Inc Cupertino CA 95014 USA Monash Univ Dept Comp Sci Clayton Vic 3168 Australia

A framework for the automatic parallelization of (constraint) logic programs is proposed and proved correct. Intuitively, the parallelization process replaces conjunctions of literals with parallel expressions. Such expressions trigger at run-time the exploitation of restricted, goal-level, independent and parallelism. The parallelization process performs two steps. The first one builds a conditional dependency graph (which can be simplified using compile-time analysis information), while the second transforms the resulting graph into linear conditional expressions, the parallel expressions of the &-Prolog language. Several heuristic algorithms for the latter ("annotation") process are proposed and proved correct. Algorithms are also given which determine if there is any loss of parallelism in the linearization process with respect to a proposed notion of maximal parallelism. Finally, a system is presented which implements the proposed approach. The performance of the different annotation algorithms is compared experimentally in this system by studying the time spent in parallelization and the effectiveness of the results in terms of speedups. (C) 1999 Elsevier Science Inc. All rights reserved.

关键词： automatic parallelization parallelizing compilers conditional dependency graphs and-parallelism &-Prolog

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：