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

Maximizing multiprocessor performance with the SUIF compiler

COMPUTER 1996年第12期29卷 84-&页

作者： Hall, MW Anderson, JM Amarasinghe, SP Murphy, BR Liao, SW Bugnion, E Lam, MS STANFORD UNIV DEPT COMP SCISTANFORDCA 94305 STANFORD UNIV DEPT ELECT ENGNSTANFORDCA 94305

Multiple processors can work together to speed up single applications, but sequential programs must be rewritten to take advantage of the extra processors. One way to do this is through automatic parallelization with a compiler. Multiprocessors pose especially challenging problems for parallelizing compilers. Sufficient work must be performed in parallel to overcome processor synchronization and communication overhead. Moreover, multiprocessor memory hierarchies are complex, containing both shared memory and multiple levels of cache memory. Thus, two techniques are essential in obtaining good multiprocessor performance for array-based numerical programs: locating coarse-grain parallelism and managing multiprocessor memory use. The authors describe new technology in the Stanford SUIF compiler that enables it to successfully carry out these techniques. First, a suite of robust analysis techniques operate across procedure boundaries to locate coarse-grain parallelism so that large computations can execute independently in parallel. Then, to help eliminate cache misses, affine partitioning is used to improve processor reuse of data, and data permutation and data strip-mining make contiguous the data accessed by each processor in the shared address space. When employed in the automatic parallelizing compiler, these techniques significantly affect the performance of half the NAS and SPECfp95 benchmark suites.

关键词： Mathematics Computing Parallelising compilers Multiprocessing Systems Performance Evaluation Optimising compilers Benchmark Programs Multiprocessor Performance SUIF Compiler Automatic Parallelization Techniques Stanford University Intermediate Format Compiler Array Based Numerical Programs parallelizing compilers Memory Optimization Techniques Robust Analysis Techniques Speedups NAS SPE Cfp 95 Parallel Processing Phased Arrays Program Processors Information Analysis Concurrent Computing Privatization Throughput Multiprocessing Systems Cache Memory Programming Profession

来源：评论

学校读者我要写书评

暂无评论

Using global code motions to improve the quality of results for high-level synthesis

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2004年第2期23卷 302-312页

作者： Gupta, S Savoiu, N Dutt, N Gupta, R Nicolau, A Univ Calif Irvine Ctr Embedded Comp Syst Irvine CA 92697 USA Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

The quality of synthesis results for most, high-level synthesis approaches is strongly affected by the choice of control flow (through conditions and loops) in the input description. This leads to a need for high-level and compiler transformations that overcome the effects of programming style on the quality of generated circuits. To address this issue, we have developed a set of speculative code-motion transformations that enable movement of operations through, beyond, and into conditionals with the objective of maximizing performance. We have implemented these code transformations, along with supporting code-motion techniques and variable renaming techniques, in a high-level synthesis research framework called Spark. Spark takes a behavioral description in ANSI-C as input and generates synthesizable register-transfer level VHDL. We present results for experiments on designs derived from three real-life multimedia and image processing applications, namely, the MPEG-1 and -2 and GNU image manipulation program applications. We rind that the speculative-code motions lead to reductions between 36% and 59% in the number of states in the finite-state machine (controller complexity) and the cycles on the longest path (performance) compared with the case when only nonspeculative code motions are employed. Also, logic synthesis results show fairly constant critical path lengths (clock period) and a marginal increase in area.

关键词： code motions embedded systems high-level synthesis parallelizing compilers speculation

来源：评论

学校读者我要写书评

暂无评论

Automatic data and computation decomposition on distributed memory parallel computers

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2002年第1期24卷 1-50页

作者： Lee, P Kedem, ZM Acad Sinica Inst Informat Sci Taipei 11529 Taiwan Acad Sinica Ctr Appl Sci & Engn Res Taipei 11529 Taiwan NYU Courant Inst Math Sci Dept Comp Sci New York NY 10003 USA

To exploit parallelism on shared memory parallel computers (SMPCs), it is natural to focus on decomposing the computation (mainly by distributing the iterations of the nested Do-Loops). In contrast, on distributed memory parallel computers (DMPCs), the decomposition of computation and the distribution of data must both be handled-in order to balance the computation load and to minimize the migration of data. We propose and validate experimentally a method for handling computations and data synergistically to minimize the overall execution time on DMPCs. The method is based on a number of novel techniques, also presented in this article. The core idea is to rank the "importance" of data arrays in a program and specify some of the dominant. The intuition is that the dominant arrays are the ones whose migration would be the most expensive. Using the correspondence between iteration space mapping vectors and distributed dimensions of the dominant data array in each nested Do-loop, allows us to design algorithms for determining data and computation decompositions at the same time. Based on data distribution, computation decomposition for each nested Do-loop is determined based on either the "owner computes" rule or the "owner stores" rule with respect to the dominant data array. If all temporal dependence relations across iteration partitions are regular, we use tiling to allow pipelining and the overlapping of computation and communication. However, in order to use tiling on DMPCs, we needed to extend the existing techniques for determining tiling vectors and tile sizes, as they were originally suited for SMPCs only. The overall method is illustrated on programs for the 2D heat equation, for the Gaussian elimination with pivoting, and for the 2D fast Fourier transform on a linear processor array and on a 2D processor grid.

关键词： algorithms languages computation decomposition data alignment data distribution distributed-memory computers dominant data array iteration space mapping vector parallelizing compilers spatial dependence vector temporal dependence vector tiling techniques

来源：评论

学校读者我要写书评

暂无评论

HIGH-SPEED SYNCHRONIZATION OF PROCESSORS USING FUZZY BARRIERS

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1990年第1期19卷 53-73页

作者： GUPTA, R EPSTEIN, M UNIV PITTSBURGH DEPT COMP SCIPITTSBURGHPA 15260 N AMER PHILIPS LIGHTING CORP PHILIPS LABSBARIACLIFF MANORNY 10510

Parallel programs are commonly written using barriers to synchronize parallel processes. Upon reaching a barrier, a processor must stall until all participating processors reach the barrier. A software implementation of the barrier mechanism using shared variables has two major drawbacks. Firstly, the execution of the barrier may be slow since it requires execution of several instructions. Secondly, processors that are stalled waiting for other processors to reach the barrier cannot do any useful work. In this paper, the notion of thefuzzy barrier is presented, that avoids these drawbacks. The first problem is avoided by implementing the mechanism in hardware. The second problem is solved by extending the barrier concept to include a region of statements that can be executed by a processor while it awaits synchronization. The barrier regions are constructed by a compiler and consist of instructions such that a processor is ready to synchronize upon reaching the first instruction and must synchronize before exiting the region. When synchronization does occur, the processors could be executing at any point in their respective barrier regions. The larger the barrier region, the more likely it is that none of the processors will have to stall. Hardware fuzzy barriers have been implemented as part of a RISC-based multi-processor system. Results based on a software implementation of the fuzzy barrier on the Encore multiprocessor indicate that the synchronization overhead can be greatly reduced using the mechaism.

关键词： Multiprocessor systems barrier synchronization synchronization overhead parallelizing compilers code reordering

来源：评论

学校读者我要写书评

暂无评论

Skewed data partition and alignment techniques for compiling programs on distributed memory multicomputers

引用

JOURNAL OF SUPERCOMPUTING 2002年第2期21卷 191-211页

作者： Chen, TS Chang, CY Chang Jung Univ Dept Informat Management Tainan 711 Taiwan Aletheia Univ Dept Comp & Informat Sci Taipei Taiwan

Minimizing data communication over processors is the key to compile programs for distributed memory multicomputers. In this paper, we propose new data partition and alignment techniques for partitioning and aligning data arrays with a program in a way of minimizing communication over processors. We use skewed alignment instead of the dimension-ordered alignment techniques to align data arrays. By developing the skewed scheme, we can solve more complex programs with minimized data communication than that of the dimension-ordered scheme. Finally, we compare the proposed scheme with the dimension-ordered alignment one by experimental results. The experimental results show that our proposed scheme has more opportunities to align data arrays such that data communications over processors can be minimized.

关键词： array alignment data distribution data partition distributed memory multicomputers parallelizing compilers

来源：评论

学校读者我要写书评

暂无评论

Interprocedural analysis for loop scheduling and data allocation

引用

PARALLEL COMPUTING 1998年第3-4期24卷 477-504页

作者： Nguyen, TN Li, ZY Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA IBM Corp Rochester MN 55906 USA

In order to reduce remote memory accesses on CC-NUMA multiprocessors, we present an interprocedural analysis to support static loop scheduling and data allocation. Given a parallelized program, the compiler constructs graphs which represent globally and interprocedurally the remote reference penalties associated with different choices for loop scheduling and data allocation. After deriving an optimal solution according to those graphs, the compiler generates data allocation directives and schedules DOALL loops. Experiments indicate that the proposed compiler scheme is efficient and simulation results show good performance of the parallel code. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers shared memory multiprocessors non-uniform memory access data allocation loop scheduling interprocedural analysis

来源：评论

学校读者我要写书评

暂无评论

On supernode transformation with minimized total running time

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1998年第5期9卷 417-428页

作者： Hodzic, E Shang, WJ AT&T Bell Labs San Jose CA 95134 USA 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 how to find an optimal supernode size and optimal supernode relative side lengths of a supernode transformation (also known as tiling). We identify three parameters of supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For algorithms with perfectly nested loops and uniform dependencies, for sufficiently large supernodes and number of processors, and for the case where multiple supernodes are mapped to a single processor, we give an order n polynomial whose real positive roots include the optimal supernode size. For two special cases, 1) two-dimensional algorithm problems and 2) n-dimensional algorithm problems, where the communication cost is dominated by the startup penalty and, therefore, can be approximated by a constant, we give a closed form expression for the optimal supernode size, which is independent of the supernode relative side lengths and cutting hyperplanes. For the case where the algorithm iteration index space and the supernodes are hyperrectangular, we give closed form expressions for the optimal supernode relative side lengths. Our experiment shows a good match of the closed form expressions with experimental data.

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

来源：评论

学校读者我要写书评

暂无评论

Compiling array references with affine functions for data-parallel programs

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 1998年第4期14卷 695-723页

作者： Wei, WH Shih, KP Sheu, JP Natl Cent Univ Dept Comp Sci & Informat Engn Chungli 320 Taiwan

An important research topic is parallelizing of compilers to generate local memory access sequences and communication sets while compiling a data-parallel language into an SPMD (Single Program Multiple Data) program. In this paper, we present a scheme to efficiently enumerate local memory access sequences and to evaluate communication sets. We use a class table to store information that is extracted from array sections and data distribution patterns. Given array references and data distributions, we can utilize the class table to generate communication sets in closed forms. Furthermore, we derive the algorithms for sending and receiving necessary data between processors. An algorithm for generating the class table is presented, and the time complexity of this algorithm is O(s), where s is the array section stride. The technique of generating communication sets for one index variable has been implemented on a DEC Alpha 3000 workstation. The experimental results confirm the advantage of our scheme, especially when the array section stride is larger than the block size. Finally, we adapt our approach to handle array references with multiple index variables. The time complexity for constructing the whole class table is O(s(2)).

关键词： communication set data-parallel language distributed memory multicomputers HPF parallelizing compilers SPMD

来源：评论

学校读者我要写书评

暂无评论

RUNTIME SUPPORT AND COMPILATION METHODS FOR USER-SPECIFIED IRREGULAR DATA DISTRIBUTIONS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第8期6卷 815-831页

作者： PONNUSAMY, R SALTZ, J CHOUDHARY, A HWANG, YS UNIV MARYLAND DEPT COMP SCI COLLEGE PK MD 20742 USA UNIV MARYLAND INST ADV COMP STUDIES COLLEGE PK MD 20742 USA

This paper describes two new ideas by which a High Performance Fortran compiler can deal with irregular computations effectively. The first mechanism invokes a user specified mapping procedure via a set of proposed compiler directives. The directives allow use of program arrays to describe graph connectivity, spatial location of array elements, and computational load. The second mechanism is a conservative method for compiling irregular loops in which dependence arises only due to reduction operations. This mechanism in many cases enables a compiler to recognize that it is possible to reuse previously computed information from inspectors (e.g., communication schedules, loop iteration partitions, and information that associates off-processor data copies with on-processor buffer locations). This paper also presents performance results for these mechanisms from a Fortran 90D compiler implementation.

关键词： RUNTIME SUPPORT parallelizing compilers DATA DISTRIBUTIONS HIGH PERFORMANCE FORTRAN LANGUAGE DIRECTIVES IRREGULAR PROBLEMS DISTRIBUTED MEMORY MACHINES

来源：评论

学校读者我要写书评

暂无评论

Maximizing parallelism and minimizing synchronization with affine partitions

引用

PARALLEL COMPUTING 1998年第3-4期24卷 445-475页

作者： Lim, AW Lam, MS Stanford Univ Comp Syst Lab Stanford CA 94305 USA

This paper presents an algorithm to find the optimal affine partitions that maximize the degree of parallelism and minimize the degree of synchronization in programs with arbitrary loop nestings and affine data accesses. The problem is formulated without the use of imprecise data dependence abstractions such as data dependence vectors. The algorithm presented subsumes previously proposed loop transformation algorithms that are based on unimodular transformations, loop distribution, fusion, scaling, reindexing, and statement reordering. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： affine partitions affine transforms parallelizing compilers multiprocessors parallelism coarse granularity synchronization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：