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

compiler techniques for the distribution of data and computation

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2003年第6期14卷 545-562页

作者： Navarro, A Zapata, E Padua, D Univ Malaga Dept Comp Architecture Malaga 29080 Spain Univ Illinois Dept Comp Sci Digital Comp Lab 3318 Urbana IL 61801 USA

This paper presents a new method that can be applied by a parallelizing compiler to find, without user intervention, the iteration and data decompositions that minimize communication and load imbalance overheads in parallel programs targeted at NUMA architectures. One of the key ingredients in our approach is the representation of locality as a Locality-Communication Graph (LCG) and the formulation of the compiler technique as a Mixed Integer Nonlinear Programming (MINLP) optimization problem on this graph. The objective function and constraints of the optimization problem model communication costs and load imbalance. The solution to this optimization problem is a decomposition that minimizes the parallel execution overhead. This paper summarizes the process of how the compiler extracts the locality information from a nonannotated code and focuses on how this compiler can derive the optimization problem, solve it, and generate the parallel code with the automatically selected iteration and data distributions. In addition, we include a discussion about our model and the solutions-the decompositions-that it provides. The approach presented in the paper is evaluated using several benchmarks. The experimental results demonstrate that the MINLP formulation does not increase compilation time significantly and that our framework generates very efficient iteration/data distributions for a variety of NUMA machines.

关键词： parallelizing compiler locality analysis load balancing communication pattern mixed integer nonlinear programming

来源：评论

学校读者我要写书评

暂无评论

New shape analysis and interprocedural techniques for automatic parallelization of C codes

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2002年第1期30卷 37-64页

作者： Corbera, F Asenjo, R Zapata, E Univ Malaga Comp Architecture Dept E-29080 Malaga Spain

Automatic parallelization of codes with complex data structures is becoming very important. These complex, and often recursive, data structures are widely used in scientific computing. Shape analysis is one of the key steps in the automatic parallelization of such codes. In this paper we extend the Static Shape Graph (SSG) method to enable the successful and accurate detection of complex doubly-linked structures. We have also included an interprocedural analysis in our framework. These techniques have been implemented in a compiler, which has been validated for several C codes. In particular, we present the results the compiler achieves for the C sparse LU factorization algorithm and for a recursive code generating a tree data structure. The output SSG perfectly describes the complex data structure used in these codes.

关键词： parallelizing compiler shape analysis pointers recursive data structures shape graphs

来源：评论

学校读者我要写书评

暂无评论

Bit length optimization of fractional part on floating to fixed point conversion for high-level synthesis

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2003年第12期E86A卷 3184-3191页

作者： Doi, N Horiyama, T Nakanishi, M Kimura, S Watanabe, K Waseda Univ Grad Sch Informat Prod & Syst Kitakyushu Fukuoka 8080135 Japan Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Nara Inst Sci & Technol Grad Sch Informat Sci Nara 6300101 Japan

In the hardware synthesis from a high-level language such as C, the bit length of variables is one of the key issues for the area and speed optimization. Usually, designers are required to optimize the bit-length of each variable manually using the time-consuming simulation on huge-data. In this paper, we propose an optimization method of the fractional bit length in the conversion from floating-point variables to fixed-point variables. The method is based on error propagation and the backward propagation of the accuracy limitation. The method is fully analytical and fast compared to simulation based methods.

关键词： HDL high-level synthesis parallelizing compiler bit length

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

K-DT: a formal system for the evaluation of linear data dependence testing techniques

引用

JOURNAL OF SUPERCOMPUTING 2018年第4期74卷 1655-1675页

作者： Zhao, Jie Zhao, Rongcai Natl Digital Switching Syst Engn & Technol Res Ct Zhengzhou 450001 Henan Peoples R China Zhongyuan Univ Technol Zhengzhou 450007 Henan Peoples R China

The power of data dependence testing techniques of a parallelizing compiler is its essence to transform and optimize programs. Numerous techniques were proposed in the past, and it is, however, still a challenging problem to evaluate the relative power of these techniques to better understand the data dependence testing problem. In the past, either empirical studies or experimental evaluation results are published to compare these data dependence testing techniques, being not able to convince the research community completely. In this paper, we show a theoretical study on this issue, comparing the power on disproving dependences of existing techniques by proving theorems in a proposed formal system K-DT. Besides, we also present the upper bounds of these techniques and introduce their minimum complete sets. To the best of our knowledge, K-DT is the first formal system used to compare the power of data dependence testing techniques, and this paper is the first work to show the upper bounds and minimum complete sets of data dependence testing techniques.

关键词： parallelizing compiler Data dependence testing technique Predicate logic Minimum complete set

来源：评论

学校读者我要写书评

暂无评论

TOWARDS SYSTOLIZING COMPILATION

引用

DISTRIBUTED COMPUTING 1991年第1期5卷 7-24页

作者： LENGAUER, C BARNETT, M HUDSON, DG UNIV TEXAS DEPT COMP SCI AUSTIN TX 78712 USA

A scheme for the compilation of imperative or functional programs into systolic programs is demonstrated on matrix composition/decomposition and Gauss-Jordan elimination. Using this scheme, programs for the processor ... 详细信息

关键词： DISTRIBUTED PARALLELISM parallelizing compiler SYSTOLIC ARRAY

来源：评论

学校读者我要写书评

暂无评论

A novel compiler support for automatic parallelization on multicore systems

引用

PARALLEL COMPUTING 2013年第9期39卷 442-460页

作者： Andion, Jose M. Arenaz, Manuel Rodriguez, Gabriel Tourino, Juan Univ A Coruna Dept Elect & Syst La Coruna 15071 Spain

The widespread use of multicore processors is not a consequence of significant advances in parallel programming. In contrast, multicore processors arise due to the complexity of building power-efficient, high-clock-rate, single-core chips. Automatic parallelization of sequential applications is the ideal solution for making parallel programming as easy as writing programs for sequential computers. However, automatic parallelization remains a grand challenge due to its need for complex program analysis and the existence of unknowns during compilation. This paper proposes a new method for converting a sequential application into a parallel counterpart that can be executed on current multicore processors. It hinges on an intermediate representation based on the concept of domain-independent kernel (e.g., assignment, reduction, recurrence). Such kernel-centric view hides the complexity of the implementation details, enabling the construction of the parallel version even when the source code of the sequential application contains different syntactic variations of the computations (e.g., pointers, arrays, complex control flows). Experiments that evaluate the effectiveness and performance of our approach with respect to state-of-the-art compilers are also presented. The benchmark suite consists of synthetic codes that represent common domain-independent kernels, dense/sparse linear algebra and image processing routines, and full-scale applications from SPEC CPU2000. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Automatic parallelization parallelizing compiler Source-to-source compiler compiler intermediate representation Domain-independent kernel Multicore processor

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Automatic parallelization of representative-based clustering algorithms for multicore cluster systems

引用

INTERNATIONAL JOURNAL OF DATA SCIENCE AND ANALYTICS 2020年第2期10卷 135-159页

作者： Islam, Saiyedul Balasubramaniam, Sundar Gupta, Shruti Brajesh, Shikhar Badlani, Rohan Labhishetty, Nitin Baid, Abhinav Goyal, Poonam Goyal, Navneet Birla Inst Technol & Sci Pilani Adv Data Analyt & Parallel Technol Lab Dept Comp Sci & Informat Syst Pilani Campus Pilani Rajasthan India

Ease of programming and optimal parallel performance have historically been on the opposite side of a trade-off, forcing the user to choose. With the advent of the Big Data era and the rapid evolution of sequential algorithms, the data analytics community can no longer afford the trade-off. We observed that several clustering algorithms often share common traits-particularly, algorithms belonging to the same class of clustering exhibit significant overlap in processing steps. Here, we present our observation on domain patterns in representative-based clustering algorithms and how they manifest as clearly identifiable programming patterns when mapped to a Domain Specific Language (DSL). We have integrated the signatures of these patterns in the DSL compiler for parallelism identification and automatic parallel code generation. The compiler either generates MPI C++ code for distributed memory parallel processing or MPI-OpenMP C++ code for hybrid memory parallel processing, depending upon the target architecture. Our experiments on different state-of-the-art parallelization frameworks show that our system can achieve near-optimal speedup while requiring a fraction of the programming effort, making it an ideal choice for the data analytics community. Results are presented for both distributed and hybrid memory systems.

关键词： Clustering Domain Specific Language parallelizing compiler High Performance Computing Programming patterns

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：