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

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 08)

作者： Zhai, Antonia Wang, Shengyue Yew, Pen-Chung He, Guojin Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA

No abstract available.

ISBN: (纸本)9781595939609

No abstract available.

关键词： Thread-Level Speculation Multicore systems compiler Optimizations parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

Communication-free data alignment for arrays with exponential references in parallelizing compilers for scalable parallel systems

引用

JOURNAL OF SUPERCOMPUTING 2012年第1期60卷 4-30页

作者： Guo, Minyi Chang, Weng-Long Jiang, Bo Huang, Shu-Chien Tsai, Sien-Tang Ho, Michael (Shan-Hui) Dalian Maritime Univ Sch Informat Engn Dalian 116026 Liaoning Peoples R China Natl Kaohsiung Univ Appl Sci Dept Comp Sci & Informat Engn Kaohsiung 807 Taiwan Univ Aizu Sch Comp Sci & Engn Aizu Wakamatsu Fukushima 9658580 Japan Natl PingTung Univ Educ Dept Comp Sci Pingtung Taiwan So Taiwan Univ Technol Dept Informat Management Tainan 710 Taiwan Ming Chuan Univ Sch Informat Technol Dept Informat Management Tao Yuan 333 Taiwan

In loops, some arrays are referenced with induction variables. To parallelize such kind of loops, those induction variables should be substituted. Thus, those array references that were substituted are formulated as nonlinear expressions. The goal of data alignment is to intelligently map the computations and data onto a set of virtual processors which are organized as a Cartesian grid (or a template in HPF terms), and to provide data locality for parallelizing compilers so that data access communication costs can be minimized. Most data alignment methods are mainly devised to align the referenced arrays using linear subscripts or quadratic subscripts with n loop index variables, and the methods are well developed. Seldom work, however, is researched on the nonlinear expressions of index variables. This paper proposes a new communication-free data alignment technique to align the referenced arrays using exponential subscripts with n loop index variables or other complex nonlinear expressions. The experimental results using SPEC95FP Benchmarks point out that the techniques proposed in the paper can improve the execution time of the subroutines in these benchmarks.

关键词： parallelizing compiler Communication-free alignment Communication optimization Loop optimization Data dependence analysis Load balancing

来源：评论

学校读者我要写书评

暂无评论

Using knowledge-based systems for research on parallelizing compilers

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2001年第3期13卷 181-208页

作者： Yang, CT Tseng, SS Fann, YW Tsai, TK Hsieh, MH Wu, CT Natl Space Program Off Ground Syst Sect Hsinchu 300 Taiwan Natl Chiao Tung Univ Dept Comp & Informat Sci Hsinchu 300 Taiwan

The main function of parallelizing compilers is to analyze sequential programs, in particular the loop structure, to detect hidden parallelism and automatically restructure sequential programs into parallel subtasks that are executed on a multiprocessor. This article describes the design and implementation of an efficient parallelizing compiler to parallelize loops and achieve high speedup rates on multiprocessor systems. It is well known that the execution efficiency of a loop can be enhanced if the loop is executed in parallel or partially parallel, such as in a DOALL or DOACROSS loop. This article also reviews a practical parallel loop detector (PPD) that is implemented in our PFPC on finding the parallelism in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by verifying array subscripts. In addition, a new model by using knowledge-based approach is proposed to exploit more loop parallelisms in this paper. The knowledge-based approach integrates existing loop transformations and loop scheduling algorithms to make good use of their ability to extract loop parallelisms. Two rule-based systems, called the KPLT and IPLS, are then developed using repertory grid analysis and attribute-ordering tables respectively, to construct the knowledge bases. These systems can choose an appropriate transform and loop schedule, and then apply the resulting methods to perform loop parallelization and obtain a high speedup rate. For example, the IPLS system can choose an appropriate loop schedule for running on multiprocessor systems. Finally, a runtime technique based on the inspector/executor scheme is proposed in this article for finding available parallelism on loops. Our inspector can determine the wavefronts of a loop with any complex indirected array-indexing pattern by building a DEF-USE table. The inspector is fully parallel without any synchronization. Experimental results show that the new method can resolve any complex data dependence patter

关键词： parallelizing compiler knowledge-based system loop parallelization multithreaded OS program restructuring

来源：评论

学校读者我要写书评

暂无评论

PPD: A practical parallel loop detector for parallelizing compilers on multiprocessor systems

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1996年第11期E79D卷 1545-1560页

作者： Yang, CT Wu, CT Tseng, SS Department of Computer and Information Science National Chiao Tung University Hsinchu 300 . Taiwan

It is well known that extracting parallel loops plays a significant role in designing parallelizing compilers. The execution efficiency of a loop is enhanced when the loop can be executed in parallel or partial parallel, like a DOALL or DOACROSS loop. This paper reports on the practical parallelism detector (PPD) that is implemented in PFPC (a portable FORTRAN parallelizing compiler running on OSF/1) at NCTU to concentrate on finding the parallelism available in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by invoking a combination of the ZIV test and the I test for verifying array subscripts. Furthermore, if DOACROSS loops are available, an optimization of synchronization statement is made. Experimental results show that PPD is more reliable and accurate than previous approaches.

关键词： parallelizing compiler data dependence analysis dependent tests DOALL loops DOACROSS loops loop parallelization I test

来源：评论

学校读者我要写书评

暂无评论

Using knowledge-based techniques on loop parallelization for parallelizing compilers

引用

PARALLEL COMPUTING 1997年第3期23卷 291-309页

作者： Yang, CT Tseng, SS Chuang, CD Shih, WC NATL CHIAO TUNG UNIV DEPT COMP & INFORMAT SCIHSINCHU 300TAIWAN

In this paper we propose a knowledge-based approach for solving data dependence testing and loop scheduling problems. A rule-based system, called the K-Test, is developed by repertory grid and attribute ording table to construct the knowledge base. The K-Test chooses an appropriate testing algorithm according to some features of the input program by using knowledge-based techniques, and then applies the resulting test to detect data dependences for loop parallelization. Another rule-based system, called the KPLS, is also proposed to be able to choose an appropriate scheduling by inferring some features of loops and assign parallel loops on multiprocessors for achieving high speedup. The experimental results show that the graceful speedup obtained by our compiler is obvious.

关键词： parallelizing compiler data dependence testing loop parallelization parallel loop scheduling knowledge-based repertory grid analysis speedup

来源：评论

学校读者我要写书评

暂无评论

Scheduling contention-free irregular redistributions in parallelizing compilers

引用

JOURNAL OF SUPERCOMPUTING 2007年第3期40卷 229-247页

作者： Hsu, Ching-Hsien Chen, Shih-Chang Lan, Chao-Yang Chung Hua Univ Dept Comp Sci & Informat Engn Hsinchu 300 Taiwan

Irregular array redistribution has been paid attention recently since it can distribute different size of data segment to heterogeneous processors according to their computational ability. It's also the reason why it has been kept an eye on load balance. High Performance Fortran Version 2 (HPF2) provides GEN-BLOCK distribution format which facilitates generalized block distributions. In this paper, we present a two-phase degree-reduction (TPDR) method for scheduling HPF2 irregular array redistribution. Using a bipartite communication graph, the first phase of TPDR schedules communication links adjacent to processors that with degree greater than two. A communication step will be scheduled follow each degree- reduction iteration. The second phase of TPDR schedules remaining messages of all processors that with degree-2 and degree-1 using an adjustable coloring mechanism. Ali extended algorithm based on TPDR is also presented itt this paper. Effectiveness of the proposed methods not only avoids node contention but also shortens the overall communication cost. The proposed methods are also practicable due to low algorithmic complexity. To evaluate the performance of our methods, we have implemented both algorithms along with the divide-and-conquer algorithm and two scheduling mechanism. The simulation results show improvement of total communication costs.

关键词： irregular redistribution communication scheduling GEN_BLOCK degree-reduction parallelizing compiler

来源：评论

学校读者我要写书评

暂无评论

A new practical array data dependence analysis for parallelizing compilers

A new practical array data dependence analysis for paralleli...

引用

International Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems

作者： Mineo, M Uehara, T Saito, S Kunieda, Y Wakayama Univ Fac Syst Engn Grad Sch Wakayama 6408510 Japan

ISBN: (纸本)0769520197

Data dependence analysis is essential for automatic parallelizing compilers. compilers determine the possibility of parallelization on given source programs by using the result from data dependence analysis. Several dependence analysis tests on array data have been already proposed. Each test cannot avoid the trade-off between its analysis speed and exactness of analysis. Among such tests, the Omega test is well known as an exact test for the broader class of index expressions. However, the Omega test algorithm is so complicated that its analysis is very time consuming and it is difficult to implement the Omega test. Therefore, in this paper a new original test is proposed, whose algorithm combines both the Simplex method for linear programming and an exhaustive solution search method. The algorithm, its implementation details, and evaluation applied to concrete numerical programs are also described.

关键词： data dependence dependence analysis linear programming parallelization 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

来源：评论

学校读者我要写书评

暂无评论

An improved nonlinear data dependence test

引用

JOURNAL OF SUPERCOMPUTING 2015年第1期71卷 340-368页

作者： Zhao, Jie Zhao, Rongcai Chen, Xi Zhao, Bo State Key Lab Math Engn & Adv Comp Wuxi 214125 Peoples R China

To further parallelize large-scale nonlinear scientific computing applications, some data dependence techniques for nonlinear subscripts, especially for quadratic subscripts, were proposed in the past. The quadratic programming (QP) test and polynomial variable interval (PVI) test are two representative techniques. The QP test, which serves as an exact but time-consuming technique, always gives conservative results when the coefficient matrix of the quadratic terms is not positive semi-definite, while the PVI test will lose efficiency when there exist mixed polynomials in the dependence equation. Focusing on the dependences caused by quadratic subscripts in nonlinear and irregular programs, we propose an improved nonlinear data dependence test in this paper. We first normalize a quadratic equation which is written in a general form, and determine whether the canonical equation is integer solvable in the region of interest based on the interval equation theory. Experimental results show that, compared with the QP test, our method maintains a much lower time complexity. Furthermore, it can detect more general dependences than other dependence testing methods like the PVI test in terms of quadratic subscripts.

关键词： parallelizing compiler Data dependence test Nonlinear subscript Interval equation

来源：评论

学校读者我要写书评

暂无评论

Mapping Multi-Domain Applications onto Coarse-Grained Reconfigurable Architectures

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2011年第5期30卷 637-650页

作者： Lee, Ganghee Choi, Kiyoung Dutt, Nikil D. Samsung Elect Co SoC Platform Dev Team System LSI Div Gyeonggi 445701 South Korea Seoul Natl Univ Sch Elect Engn & Comp Sci Seoul 151600 South Korea Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA Univ Calif Irvine Dept Elect Engn Irvine CA 92697 USA

Coarse-grained reconfigurable architectures (CGRAs) have drawn increasing attention due to their performance and flexibility. However, their applications have been restricted to domains based on integer arithmetic since typical CGRAs support only integer arithmetic or logical operations. This paper introduces approaches to mapping applications onto CGRAs supporting both integer and floating-point arithmetic. After presenting an optimal formulation using integer linear programming, we present a fast heuristic mapping algorithm. Our experiments on randomly generated examples generate optimal mapping results using our heuristic algorithm for 97% of the examples within a few seconds. We observe similar results for practical examples from multimedia and 3-D graphics benchmarks. The applications mapped on a CGRA show up to 120 times performance improvement compared to software implementations, demonstrating the potential for application acceleration on CGRAs supporting floating-point operations.

关键词： Design automation high-level synthesis parallelizing compiler reconfigurable architecture

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：