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

A Survey of loop parallelization: Models, Approaches, and Recent Developments

INTERNATIONAL JOURNAL OF GRID AND DISTRIBUTED COMPUTING 2016年第11期9卷 143-156页

作者： Yao, Hong Deng, Huifang Zou, Caifeng South China Univ Technol Sch Comp Sci & Engn Guangzhou 510006 Guangdong Peoples R China

In cloud computing era, automatic parallelization is still significant for virtualization platform. However, after several decades of development, the overall effect is still to be improved. Summary of the mainstream technology developments will be beneficial to reveal the future direction and trend. This paper reviews the technology of loop parallelization, which is the key issue in automatic parallelization. After introducing the basic models and approaches, we focus on the recent developments, on which we obtain the trend of this field and the conclusions about future.

关键词： Automatic parallelization loop parallelization loop transformation Data dependence Polyhedral model Program dependence graph

来源：评论

学校读者我要写书评

暂无评论

How to Speed up Embedded Multi-core Systems Using Locality Conscious Array Distribution for loop parallelization

How to Speed up Embedded Multi-core Systems Using Locality C...

引用

ARCS 2016;29th International Conference on Architecture of Computing Systems

作者： Niklas Hehenkamp Remko van Wagensveld Dominik Schoenwetter Christian Facchi Ulrich Margull Dietmar Fey Ralph Mader Technische Hochschule Ingolstadt Chair of Computer Science 3 (Computer Architecture) Friedrich-Alexander-University Erlangen-Nurnberg (FAU) Continental Automotive GmbH

Safety critical embedded systems in the automotive domain will increasingly depend on parallel processing architectures. Since concurrency has largely been exploited on task level, future applications will feature growing proportions of parallel implementations on data level such as loop parallelism. Efficient memory utilization becomes inevitable to overcome future challenges facing the memory wall in modern computing. This work suggests an approach for data locality conscious memory accessing and data distribution implementations in embedded multi-core systems. The results have been validated by a case study on a modern Engine Control Unit focusing on the parallelization of widely spread array intensive loops.

关键词： Memory access Multi-core loop parallelization Embedded system Embedded systems parallelization loops data layer memory utilization Consciousness locality data Contraceptive Coil Concurrency Speeding embedding

来源：评论

学校读者我要写书评

暂无评论

Map-Reduce Inspired loop parallelization on CGRA

Map-Reduce Inspired Loop Parallelization on CGRA

引用

IEEE International Symposium on Circuits and Systems

作者： Shengjia Shao Shouyi Yin Leibo Liu Shaojun Wei Department of Computing Imperial College London London SW7 2AZ UK Department of Microelectronics Tsinghua University Beijing 100084 China

ISBN: (纸本)9781479934331

Our work investigates how to map loops efficiently onto Coarse Grained Reconfigurable Architecture (CGRA). This paper examines the properties of CGRA and builds Map-Reduce inspired models for the loop parallelization problem. We solve our model using Geometric Programming methods to obtain best loop unrolling parameters. Those parameters are used in the Back-End process that followed. Experiment results show the proposed approach achieved up to 44% performance gain compared to a state-of-the-art loop unrolling scheme.

关键词： Map-Reduce CGRA loop parallelization

来源：评论

学校读者我要写书评

暂无评论

A Method of Computation Decomposition on Tightly-Nested loop Automatic parallelization

A Method of Computation Decomposition on Tightly-Nested Loop...

引用

3rd International Symposium on Intelligent Information Technology Application

作者： Yan, Zhao Liu, Lei Jilin Univ Coll Comp Sci & Technol Changchun 130023 Peoples R China

ISBN: (纸本)9780769538594

An automatic parallelization method for tightly-nested loops running on multi-core system has been proposed. First, according to the physical characteristics of multi-core processors, a way has been presented to solve the problem on dada locality during data decomposition;Second, for increasing parallel granularity of tight nested loops, the method discussed in this article studied computation decomposition based on workload, and brought forward how to compute the workload of loop iteration that can be run in parallel, and at last according to the size of the workload, determined the granularity of parallel loops to achieve to reduce the parallel overhead brought by the parallel iteration of small workload. Using this method,an automatic parallelization model based on workload can be constructed.

关键词： computation decomposition workload data decomposition data locality loop parallelization

来源：评论

学校读者我要写书评

暂无评论

A hardware hot loop path detector for dynamic parallelization and optimization

A hardware hot loop path detector for dynamic parallelizatio...

引用

4th IASTED International Conference on Advances in Computer Science and Technology, ACST 2008

作者： Baba, Takanobu Yanome, Hideto Ootsu, Kanemitsu Yokota, Takashi Department of Information Science Faculty of Engineering Utsunomiya University 7-1-2 Yoto Utsunomiya Tochigi 321-8585 Japan

ISBN: (纸本)9780889867307

Dynamic parallelization and optimization of a loop is a crucial issue for enhancing the performance of sequential programs as loops account for a large fraction of execution time. loop level parallelism can also be extracted efficiently due to its regular structure. Based on the observation that only a limited number of paths are executed frequently in hot loops, we propose a hardware hot loop path detector to specify such hot loops and their hot paths accurately so that the dynamic optimizer may utilize the detected information effectively. The detector consists of a stack structured bit-tracing unit that identifies loop paths at a subroutine level, a hot loop detector that detects hot loops by utilizing loop path information and a hot path accumulator of loop paths. Experiments using SPEC CINT2000 show that loop paths occupy a small fraction (14.46%) of Ball-Larus paths but are detected frequently (64.45% of Ball-Larus paths). A combined small scale hot loop detector and hot path accumulator (32 entries each) attain a detection accuracy of 97.10% for the hottest loop path and 93.83% for the top 2 hottest loop paths and their order within hot loops.

关键词： Dynamic optimization Hardware hot loop path detector loop parallelization

来源：评论

学校读者我要写书评

暂无评论

Scheduling data-flow graphs via retiming and unfolding

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第12期8卷 1259-1267页

作者： Chao, LF Sha, EHM Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA Univ Notre Dame Dept Comp Sci & Engn Notre Dame IN 46556 USA

loop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration;the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented.

关键词： data-flow graphs loop parallelization parallel processing retiming scheduling unfolding

来源：评论

学校读者我要写书评

暂无评论

Optimally Maximizing Iteration-Level loop Parallelism

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2012年第3期23卷 564-572页

作者： Liu, Duo Wang, Yi Shao, Zili Guo, Minyi Xue, Jingling Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China SW Univ Sci & Technol Sch Comp Sci & Technol Mianyang Peoples R China Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200030 Peoples R China Univ New S Wales Sch Comp Sci & Engn Programming Languages & Compilers Grp Sydney NSW Australia

loops are the main source of parallelism in many applications. This paper solves the open problem of extracting the maximal number of iterations from a loop to run parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum nonzero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative nonoptimal algorithms using a set of benchmarks frequently used in prior work and a set of graphs generated by TGFF.

关键词： loop parallelization loop transformation retiming data dependence graph iteration-level parallelism

来源：评论

学校读者我要写书评

暂无评论

RUN-TIME parallelization AND SCHEDULING OF loopS

引用

IEEE TRANSACTIONS ON COMPUTERS 1991年第5期40卷 603-612页

作者： SALTZ, JH MIRCHANDANEY, R CROWLEY, K YALE UNIV DEPT COMP SCINEW HAVENCT 06520

In this paper, we study run-time methods to automatically parallelize and schedule iterations of a do loop in certain cases, where compile-time information is inadequate. The methods we present in this paper involve execution time preprocessing of the loop. At compile-time, these methods set up the framework for performing a loop dependency analysis. At run-time, wavefronts of concurrently executable loop iterations are identified. Using this wavefront information, loop iterations are reordered for increased parallelism. We utilize symbolic transformation rules to produce: 1) inspector procedures that perform execution time preprocessing and 2) executors or transformed versions of source code loop structures. These transformed loop structures carry out the calculations planned in the inspector procedures. We present performance results from experiments conducted on the Encore Multimax. These results illustrate that run-time reordering of loop indexes can have a significant impact on performance. Furthermore, the overheads associated with this type of reordering are amortized when the loop is executed several times with the same dependency structure.

关键词： COMPILER EXECUTOR INSPECTOR LEVEL SET loop parallelization SHARED MEMORY SPARSE TRIANGULAR SOLVE

来源：评论

学校读者我要写书评

暂无评论

PolyJIT: Polyhedral Optimization Just in Time

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2019年第5-6期47卷 874-906页

作者： Simbuerger, Andreas Apel, Sven Groesslinger, Armin Lengauer, Christian Univ Passau Passau Germany

While polyhedral optimization appeared in mainstream compilers during the past decade, its profitability in scenarios outside its classic domain of linear-algebra programs has remained in question. Recent implementations, such as the LLVM plugin Polly, produce promising speedups, but the restriction to affine loop programs with control flow known at compile time continues to be a limiting factor. PolyJIT combines polyhedral optimization with multi-versioning at run time, at which one has access to knowledge enabling polyhedral optimization, which is not available at compile time. By means of a fully-fledged implementation of a light-weight just-in-time compiler and a series of experiments on a selection of real-world and benchmark programs, we demonstrate that the consideration of run-time knowledge helps in tackling compile-time violations of affinity and, consequently, offers new opportunities of optimization at run time.

关键词： JIT compilation loop parallelization Polyhedron model

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：