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

MINIMAL DATA DEPENDENCE ABSTRACTIONS FOR LOOP TRANSFORMATIONS - EXTENDED VERSION

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1995年第4期23卷 359-388页

作者： YANG, YQ ANCOURT, C IRIGOIN, F Centre de Recherche en Informatique École Nationale Supérieure des Mines de Paris Paris France

Many abstractions of program dependences have already been proposed, such as the Dependence Distance, the Dependence Direction Vector, the Dependence Level or the Dependence Cone. These different abstractions have different precisions. The minimal abstraction associated to a transformation is the abstraction that contains the minimal amount of information necessary to decide when such a transformation is legal. Minimal abstractions for loop reordering and unimodular transformations are presented. As an example, the dependence cone, which approximates dependences by a convex cone of the dependence distance vectors, is the minimal abstraction for unimodular transformations. It also contains enough information for legally applying all loop reordering transformations and finding the same set of valid mono- and multi-dimensional linear schedules as the dependence distance set.

关键词： parallelizing compiler PROGRAM TRANSFORMATION DATA DEPENDENCE ABSTRACTION

来源：评论

学校读者我要写书评

暂无评论

ARCHITECTURE AND C++-PROGRAMMING ENVIRONMENT OF A HIGHLY PARALLEL IMAGE SIGNAL PROCESSOR

MICROPROCESSING AND MICROPROGRAMMING

引用

MICROPROCESSING AND MICROPROGRAMMING 1995年第5-6期41卷 391-408页

作者： KNEIP, J OHMACHT, M RONNER, K PIRSCH, P Laboratorium für Informationstechnologie Universität Hannover Schneiderberg 32 D-30167 Hannover Germany

A highly parallel single-chip image signal processor architecture has been derived by analysis of image processing algorithms. Available levels of parallelism and their associated demands on data access, control and complexity of operations were taken into account. The RISC-architecture, called ''HiPAR-DSP'', consists of a control unit, 16 parallel ASIMD-controlled datapaths with autonomous addressing and instruction selection capability, a local data cache per data path, a shared memory with matrix type data access and a powerful DMA-unit. The proposed architecture was designed by assessing the results of an analysis of characteristic algorithm properties with respect to their inherent parallelization resources, achievable speed up and implementation costs. This resulted in a proper balance between the degree of parallelism and flexibility, leading to a high performance for a wide field of applications. Additional measures were taken to support an efficient high level programmability of the processor. This was achieved by the concurrent implementation of special architectural features and a C++-programming environment. It consists of an adaptation of the GNU C++-compiler and an optimizing assembler, supporting all levels of concurrence offered by the hardware. While most levels of parallelization are kept invisible to the programmer, data-level parallelism is expressed by the programmer using special new data types added to the standard C/C++-data-types. A sustained performance of about 2.0 Gigaoperations per second is achieved by the 100 MHz clocked processor for numerous image processing algorithms, leading to a processing time e.g. for a normalized correlation of a 512 x 512 image with a 32 x 32 correlation mask of 450 ms. Thus, a performance is achieved with a programmable parallel processor architecture that hitherto required the application of a dedicated integrated circuit.

关键词： PARALLEL VLSI RISC PROCESSOR SHARED MEMORY ARCHITECTURE AUTONOMOUS SIMD CONTROLLING IMAGE PROCESSING parallelizing compiler PARALLEL LANGUAGE EXTENSION

来源：评论

学校读者我要写书评

暂无评论

Techniques for compiling programs on distributed memory multicomputers

引用

PARALLEL COMPUTING 1995年第12期21卷 1895-1923页

作者： Lee, PZ Institute of Information Science Academia Sinica Taipei Taiwan ROC

It is widely accepted that distributed memory parallel computers will play an important role in solving computation-intensive problems. However, the design of an algorithm in a distributed memory system is time-consuming and error-prone, because a programmer is forced to manage both parallelism and communication. In this paper, we present techniques for compiling programs on distributed memory parallel computers. We will study the storage management of data arrays and the execution schedule arrangement of Do-loop programs on distributed memory parallel computers. First, we introduce formulas for representing data distribution of specific data arrays across processors. Then, we define communication cost for some message-passing communication operations. Next, we derive a dynamic programming algorithm for data distribution. After that, we show how to improve the communication time by pipelining data, and illustrate how to use data-dependence information for pipelining data. Jacobi's iterative algorithm and the Gauss elimination algorithm for linear systems are used to illustrate our method. We also present experimental results on a 32-node nCUBE-2 computer.

关键词： data-dependence vector data partition and distribution distribution function distributed memory computer dynamic programming algorithm for data distribution parallelizing compiler pipelining

来源：评论

学校读者我要写书评

暂无评论

Symbolic array dataflow analysis for array privatization and program parallelization

Symbolic array dataflow analysis for array privatization and...

引用

1995 ACM/IEEE Supercomputing Conference (SC 95)

作者： Gu, JJ Li, ZY Lee, G Univ of Minnesota Minneapolis United States

ISBN: (纸本)0897918622

Array dataflow information plays an important role for successful automatic parallelization of Fortran programs. This paper proposes a powerful symbolic array dataflow analysis to support array privatization and loop parallelization for programs with arbitrary control flow graphs and acyclic call graphs. Our scheme summarizes array access information using guarded array regions and propagates such regions over a Hierarchical Supergraph (HSG). The use of guards allows us to use the information in IF conditions to sharpen the array dataflow analysis and thereby to handle difficult cases which elude other existing techniques. The guarded array regions retain the simplicity of set operations for regular array regions in common cases, and they enhance regular array regions in complicated cases by using guards to handle complex symbolic expressions and array shapes. Scalar values that appear in array subscripts and loop limits are substituted on the fly during the array information propagation, which disambiguates the symbolic values precisely for set operations. We present efficient algorithms that implement our scheme. Initial experiments of applying our analysis to Perfect Benchmarks show promising results of improved array privatization. Copyright 1995 by the Association for Computing Machinery, Inc. (ACM).

关键词： parallelizing compiler array dataflow analysis interprocedural analysis array privatization symbolic analysis

来源：评论

学校读者我要写书评

暂无评论

AUTOMATIC DATA AND COMPUTATION DECOMPOSITION FOR DISTRIBUTED-MEMORY MACHINES

引用

Parallel Processing Letters 1995年第4期5卷 539-550页

作者： QI NING VINCENT VAN DONGEN GUANG R. GAO Qi Ning is now affiliated with Convex Computer Corporation 3000 Waterview Parkway Richardson TX 75083-3851. Centre de Recherche Informatique de Montréal 1801 McGill Avenue Bureau 800 Montreal Quebec Canada H3A 2N4 Canada School of Computer Science McGill University Montreal Quebec Canada H3A 2A7 Canada

In this paper, we develop an automatic compile-time computation and data decomposition technique for distributed-memory machines. Our method handles complex programs containing perfect and non-perfect loop nests with or without loop-carried dependences. Applying our algorithms, a program will be divided into collections (called clusters) of loop nests, such that data redistributions are allowed only between the clusters. Within each cluster of loop nests, decomposition and data locality constraints are formulated as a system of homogeneous linear equations which is solved by polynomial time algorithms. Our algorithm can selectively relax data locality constraints within a cluster to achieve a balance between parallelism and data locality. Such relaxations are guided by exploiting the hierarchical program nesting structures from outer to inner nesting levels to keep the communications at a outer-most level possible.

关键词： Automatic loop parallelization parallelizing compiler data computation decomposition for distributed-memory machines

来源：评论

学校读者我要写书评

暂无评论

EXTENSIONS TO CYCLE SHRINKING

引用

INTERNATIONAL JOURNAL OF HIGH SPEED COMPUTING 1995年第2期7卷 265-284页

作者： SETHI, A BISWAS, S SANYAL, A INDIAN INST TECHNOL DEPT COMP SCI & ENGNBOMBAY 400076MAHARASHTRAINDIA

An important part of a parallelizing compiler is the restructuring phase, which extracts parallelism from a sequential program. We consider an important restructuring transformation called cycle shrinking [5], which partitions the iteration space of a loop so that the iterations within each group of the partition can be executed in parallel. The method in [5] mainly deals with dependences with constant distances. In this paper, we propose certain extensions to the cycle shrinking transformation. For dependences with constant distances, we present an algorithm which, under certain fairly general conditions, partitions the iteration space in a minimal number of groups. Under such conditions, our method is optimal while the previous methods are not. We have also proposed an algorithm to handle a large class of loops which have dependences with variable distances. This problem is considerably harder and has not been considered before in full generality.

关键词： parallelizing compiler RESTRUCTURING TRANSFORMATIONS DEPENDENCE DISTANCES CYCLE SHRINKING

来源：评论

学校读者我要写书评

暂无评论

THE POLARIS INTERNAL REPRESENTATION

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1994年第5期22卷 553-586页

作者： FAIGIN, KA WEATHERFORD, SA HOEFLINGER, JP PADUA, DA PETERSEN, PM 1. Center for Supercomputing Research and Development University of Illinois at Urbana-Champaign 61801 Urbana Illinois

The Polaris Program Manipulation System is a production quality tool for source-to-source transformations and complex analysis of Fortran code. In this paper, we describe the motivations for and the implementation of Polaris' internal representation (IR). The IR is composed of a basic abstract syntax tree on top of which exist many layers of functionality. This functionality allows complex operations on the data structure. Further, the IR is designed to enforce the consistency of the internal structure in terms of both the correctness of the data structures and the correctness of the Fortran code being manipulated. In addition, operations on the IR result in the automatic updating of affected data structures such as flow information. We describe how the system's philosophies developed from its predecessor, the Delta prototyping system, and how they were implemented in Polaris' IR. We also provide a number of examples of using the Polaris system.

关键词： INTERNAL REPRESENTATION OBJECT-ORIENTED parallelizing compiler SOURCE-TO-SOURCE TRANSFORMATION

来源：评论

学校读者我要写书评

暂无评论

Optimizing FORTRAN Programs for Hierarchical Memory Parallel Processing Systems

引用

Journal of Computer Science & Technology 1993年第3期8卷 209-220页

作者：金国华陈福接 Department of Computer Science Changsha Institute of TechnologyChangsha 410073

Parallel loops account for the greatest amount of parallelism in numerical *** nested loops in parallel with low run-time overhead is thus very important for achieving high perform- ance in parallel processing ***,in parallel processing systems with caches or local memo- ries in memory hierarchies,“thrashing problem”may arise whenever data move back and forth between the caches or local memories in different processors. Previous techniques can only deal with the rather simple cases with one linear function in the perfect- ly nested *** this paper,we present a parallel program optimizing technique called hybrid loop inter- change(HLI)for the cases with multiple linear functions and loop carried data dependences in the nested *** HLI we can easily eliminate or reduce the thrashing phenomena without reducing the program parallelism.

关键词： Thrashing problem hierarchical memory cache parallelizing compiler hybrid loop interchange FORTRAN

来源：评论

学校读者我要写书评

暂无评论

Loop Staggering,Loop Compacting:Restructuring Techniques for Thrashing Problem

引用

Journal of Computer Science & Technology 1993年第1期8卷 49-56页

作者：金国华杨学军陈福接 Dept.of Computer Science Changsha Institute of TechnologyChangsha 410073

Parallel loops account for the greatest amount of parallelism in numerical *** nested loops in parallel with low run-time overhead is thus very important for achieving high performance in parallel processing ***,in parallel processing systems with caches or local memories in memory hierarchies,“thrashing problem”may arise when data move back and forth frequently between the caches or local memories in different *** techniques associated with parallel compiler to solve the problem are not completely *** this paper,we present two restructuring techniques called loop staggering,loop staggering and compacting,with which we can not only eliminate the cache or local memory thrashing phenomena significantly,but also exploit the potential parallelism existing in outer serial *** staggering benefits the dynamic loop scheduling strategies,whereas loop staggering and compacting is good for static loop scheduling strategies,Our method especially benefits parallel programs,in which a parallel loop is enclosed by a serial loop and array elements are repeatedly used in the different iterations of the parallel loop.

关键词： parallelizing compiler loop staggering loop compacting thrashing problem cache

来源：评论

学校读者我要写书评

暂无评论

DEPENDENCE UNIFORMIZATION - A LOOP PARALLELIZATION TECHNIQUE

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第5期4卷 547-558页

作者： TZEN, TH NI, LM MICHIGAN STATE UNIV DEPT COMP SCIE LANSINGMI 48824

In general, any nested loop can be parallelized as long as all dependence constraints among iterations are preserved by applying appropriate synchronizations. However, the performance is significantly affected by the synchronization overhead. In case of irregular and complex dependence constraints, it is very difficult to efficiently and systematically arrange synchronization primitives. In this paper, we propose a new method, data dependence uniformization, to overcome the difficulties in parallelizing a doubly nested loop with irregular dependence constraints. Our approach is based on the concept of vector decomposition. A simple set of basic dependences is developed of which all dependence constraints can be composed. The set of basic dependences then will be added to every iteration to replace all original dependences so that the dependence constraints become uniform. Finally, an efficient synchronization method is presented to obey the uniform dependence constraints in every iteration.

关键词： DEPENDENCE CONSTRAINT LOOP ITERATION LOOP PARALLELIZATION parallelizing compiler PROCESS SYNCHRONIZATION VECTOR DECOMPOSITION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：