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

Optimization of data distribution and processor allocation problem using simulated annealing

JOURNAL OF SUPERCOMPUTING 2003年第3期25卷 237-253页

作者： Onbasioglu, E Özdamar, L Yeditepe Univ Dept Comp Engn TR-81120 Istanbul Turkey Yeditepe Univ Dept Syst Engn TR-81120 Istanbul Turkey

In this study, a global optimization meta-heuristic is developed for the problem of determining the optimum data distribution and degree of parallelism in parallelizing a sequential program for distributed memory machines. The parallel program is considered as the union of consecutive stages and the method deals with all the stages in the entire program rather than proposing solutions for each stage. The meta-heuristic developed here for this specific problem combines simulated annealing and hill climbing (SA-HC) in the search for the optimum configuration. Performance is tested in terms of the total execution time of the program including communication and computation times. Two exemplary codes from the literature, the first being computation intensive and the second being communication intensive, are utilized in the experiments. The performance of the SA-HC algorithm provides satisfactory results for these illustrative examples.

关键词： data distribution processor allocation optimization simulated annealing parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Generation of injective and reversible modular mappings

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2003年第1期14卷 1-12页

作者： Lee, HJ Fortes, JAB Seoul Natl Univ Sch Elect Engn & Comp Sci Seoul 151744 South Korea Univ Florida Dept Elect & Comp Engn Adv Comp & Informat Syst Lab Gainesville FL 32611 USA

A modular mapping consists of a linear transformation followed by modulo operations. It is characterized by a transformation matrix and a vector of moduli, called the modulus vector. Modular mappings are useful to derive parallel versions of algorithms with commutative operations and algorithms intended for execution on processor arrays with toroidal networks. In order to preserve algorithm correctness, modular mappings must be injective. Results of previous work characterize injective modular mappings of rectangular index sets. This paper provides a technique to generate modular appings that satisfy these injective conditions and extends the results to general index sets. For an n-dimensional rectangular index set, the technique has 0(n(2),n!) complexity. To facilitate generation of efficient code, modular mappings must also be reversible (i.e., have easily described inverses). An O(n(2)) method is provided to generate reversible modular mappings. This method reduces the search space by fixing entries of the modulus vector while attempting to minimize the number of entries to exclude few solutions. For general index sets defined by linear inequalities, injectivity can be checked by formulating and solving a set of linear inequalities. A modified Fourier-Motzkin elimination is proposed to solve these inequalities. To generate an injective modular mapping of an index set defined by linear inequalities, this paper proposes a technique that attempts to minimize the values of the entries of the modulus vector. Several examples are provided to illustrate the application of the above mentioned methods, including the case of BLAS routines.

关键词： parallel processing algorithm transformation systolic array parallelizing compiler BLAS-like algorithm modular mapping

来源：评论

学校读者我要写书评

暂无评论

Segmented alignment: An enhanced model to align data parallel programs of HPF

引用

JOURNAL OF SUPERCOMPUTING 2003年第1期25卷 17-41页

作者： Hwang, GH Chen, GW Lee, JK Ju, RDC Natl Taiwan Normal Univ Dept Informat & Comp Educ Taipei Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan Intel Corp Microprocessor Res Labs Santa Clara CA 95052 USA

In this paper, we propose a new automatic data alignment model called segmented alignment. The conventional data alignment model, such as that used in High-Performance Fortran (HPF), aligns arrays with the whole index domain. The principle of our proposed segmented alignment is to allow alignment relations within delimited index domains. We first provide motivating examples to illustrate how code fragments of HPF with EOSHIFT or CSHIFT operations, or produced by synthesis operations can benefit from our enhanced alignment scheme. Second, we show that this new model can be implemented in HPF-like languages by adding WHEN and IN constructs to them. In addition, we show that the new proposed schemes for WHEN and IN constructs can be emulated using standard HPF syntax. Finally, we address issues related to automatic data alignment for the new proposed model, and present an algorithm to automatically align programs using our segmented alignment scheme. Since the optimal algorithm to do this is NP-hard, a practical heuristic is also given. Our experiments were performed on a DEC Alpha Farm with HPF environments. Our experiments confirm our theory that our proposed alignment scheme can significantly enhance not only the performance of HPF code fragments with EOSHIFT or CSHIFT operations, but also that of codes produced by synthesis operations.

关键词： automatic array alignment segmented alignment HPF compilers distributed-memory machines compiler optimization parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An overview of the APC compiler for distributed memory machines

An overview of the APC compiler for distributed memory machi...

引用

International Conference on Parallel and Distributed Processing Techniques and Applications

作者： Zotov, S Institute for Microprocessors Russian Academy of Sciences Moscow 117997 GSP-7 Block 1 Nahimovski prosp. 36 Russian Federation

ISBN: (纸本)1892512459

The APC compiler provides automatic parallelization of sequential FORTRAN77 programs for efficient execution on distributed memory machines. It performs source to source transformation making one-dimensional block data partitioning and loops distribution decisions, reduction recognition and I/O statements processing. APC consists of the two main components: Analyzer and Partitioner. Analyzer is used as a platform to parse the source program into an intermediate representation and to perform useful analysis and transformations. Partitioner makes all the decisions about data partitioning, loops distributions and program modification. A special Parallelization Interface component was designed to adapt Analyzer for the task of automatic parallelization of sequential programs. This paper presents a technique that is used to automatically parallelize sequential programs and describes Parallelization Interface to Analyzer which provides Partitioner with objects affecting parallelization and dependencies between the objects. The paper also presents first results obtained on Fortran77 tests. Though significant work remains to optimize the algorithms presented in this article, preliminary results lead us to believe APC will generate efficient code for a large class of data-parallel programs.

关键词： Automatic dynamic data partitioning parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Multigrain parallel processing on compiler cooperative OSCAR chip multiprocessor architecture

引用

IEICE TRANSACTIONS ON ELECTRONICS 2003年第4期E86C卷 570-579页

作者： Kimura, K Kodaka, T Obata, M Kasahara, H Waseda Univ Adv Res Inst Sci & Engn Tokyo 1698555 Japan Waseda Univ Dept Elect Elect & Comp Engn Tokyo 1698555 Japan Adv Parallelizing Compiler Project Tokyo 1698555 Japan

This paper describes multigrain parallel processing on OSCAR (Optimally SCheduled Advanced multiprocessoR) chip multiprocessor architecture. OSCAR compiler cooperative chip multiprocessor architecture aims at development of scalable, high effective performance and cost effective chip multiprocessor with ease of use by compiler supports. OSCAR chip multiprocessor architecture integrates simple single issue processors having distributed shared data memory for optimal, use of data locality over different loops and fine grain data transfer and synchronization, local data memory for private data recognized by compiler, and compiler controllable data transfer unit for overlapping data transfer to hide data transfer overhead. This OSCAR chip multiprocessor and OSCAR multigrain parallelizing compiler have been developed. simultaneously. Performance of multigrain parallel processing on OSCAR chip multiprocessor architecture is evaluated using SPEC fp 2000/95 benchmark suite. When microSPARC like single issue core is used, OSCAR chip multiprocessor architecture gives us 2.36 times speedup in fpppp, 2.64 times in su2cor, 2.88 times in turb3d, 2.98 times in hydro2d, 3.84 times in tomcatv, 3.84 times in mgrid and 3.97 times in swim respectively for four processors against single processor.

关键词： chip multiprocessor multigrain parallel processing parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Interactive and Symbolic Data Dependence Analysis Based on Ranges of Expressions

引用

Journal of Computer Science & Technology 2002年第2期17卷 160-171页

作者：杨博郑丰宙王鼎兴郑纬民 Department of Computer Science and Technology Tsinghua University Beijing 100084 P.R. China

Traditional data dependence testing algorithms have become very accurate and efficient for simple subscript expressions, but they cannot handle symbolic expressions because of the complexity of data-flow and lack of the semantic information of variables in programs. In this paper, a range-based testing and query approach, called DDTQ, is proposed to eliminate data dependence between array references with symbolic subscripts. DDTQ firstly extracts data dependence information from the symbolic subscripts, a testing algorithm is then used to disprove the dependence based on the ranges of expressions. The assumed dependence that cannot be handled by the disprover will be converted into simple questions by a question engine so that the compiler can solve them by user interaction in a friendly way. The experiment on perfect benchmarks indicates that DDTQ is effective in improving the parallelizing capability of the compiler.

关键词： parallelizing compiler data dependence testing user interaction question engine

来源：评论

学校读者我要写书评

暂无评论

Scheduling GEN_BLOCK array redistribution

引用

JOURNAL OF SUPERCOMPUTING 2002年第3期22卷 251-267页

作者： Yook, HG Park, MS Samsung Elect Co Ltd Suwon South Korea Korea Univ Dept Comp Engn & Sci Seoul South Korea

This article is devoted to the redistribution of arrays that are distributed in a GEN_BLOCK fashion over a processor grid. While GEN_BLOCK redistribution is essential for load balancing, prior research about redistribution has been focused on block-cyclic redistribution. The proposed scheduling algorithm exploits a spatial locality in message passing from a seemingly irregular array redistribution. The algorithm attempts to obtain near optimal scheduling by trying to minimize communication step size and the number of steps. According to experiments on CRAY T3E and IBM SP2, the algorithm shows good performance in typical distributed memory machines.

关键词： HPF parallelizing compiler array redistribution GEN_BLOCK

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：