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

Exploitation of parallelism to nested loops with dependence cycles

JOURNAL OF SYSTEMS ARCHITECTURE 2004年第12期50卷 729-742页

作者： Chang, WL Chu, CP Ho, M So Taiwan Univ Technol Dept Informat Management Tainan 710 Taiwan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

In this paper, we analyze the recurrences from the breakability of the dependence links formed in general multi-statements in a nested loop. The major findings include: (1) A sink variable renaming technique, which can reposition an undesired anti-dependence and/or output-dependence link, is capable of breaking an anti-dependence and/or output-dependence link. (2) For recurrences connected by only true dependences, a dynamic dependence concept and the derived technique are powerful in terms of parallelism exploitation. (3) By the employment of global dependence testing, link-breaking strategy, Tarjan's depth-first search algorithm, and a topological sorting, an algorithm for resolving a general multi-statement recurrence in a nested loop is proposed. Experiments with benchmark cited from Vector loops showed that among 134 subroutines tested, 3 had their parallelism exploitation amended by our proposed method. That is, our offered algorithm increased the rate of parallelism exploitation of Vector loops by approximately 2.24%. (C) 2004 Published by Elsevier B.V.

关键词： parallelizing compilers vectorizing compilers loop optimization data dependence analysis dependence cycle parallelism exploitation

来源：评论

学校读者我要写书评

暂无评论

An approximate method for filtering out data dependencies with a sufficiently large distance between memory references

引用

JOURNAL OF SUPERCOMPUTING 2011年第2期56卷 226-244页

作者： Bulic, Patricio Dobravec, Tomaz Univ Ljubljana Fac Comp & Informat Sci Ljubljana 1000 Slovenia

In this paper we present an approximate algorithm for detecting and filtering data dependencies with a sufficiently large distance between memory references. A sequence of the same operations (typically enclosed in a 'for' loop) can be replaced with a single SIMD operation if the distance between memory references is greater than or equal to the number of data processed in the SIMD register. Some loops that could not be vectorized on traditional vector processors, can still be parallelized for short SIMD execution. There are a number of approximate data-dependence tests that have been proposed in the literature but in all of them data dependency will be assumed when actually there is no such a dependence that could restrict parallelization related to the short SIMD execution model. By examining the properties of linear subscript expressions of possibly conflicting data references, our algorithm gives the green light to the parallelization process if some sufficient conditions regarding the dependence distance are met. Our method is based on the Banerjee test and checks the minimum and maximum distances between memory references within the iteration space rather than searching for the existence of an integer solution to the dependence equation. The proposed method extends the accuracy and applicability of the classical Banerjee test.

关键词： Data dependency Multimedia extensions SIMD instructions vectorizing compilers

来源：评论

学校读者我要写书评

暂无评论

Applying Data Mapping Techniques to Vector DSPs

引用

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 2009年第1期57卷 57-72页

作者： Westermann, Peter Schwoerer, Ludwig Kaufmann, Andre Dortmund Univ Technol Circuits & Syst Lab D-44221 Dortmund Germany Bochum Univ Appl Sci Inst Commun & Elect D-44801 Bochum Germany Nokia GmbH D-44807 Bochum Germany

Vector digital signal processors (DSPs) offer a good performance to power consumption ratio. Therefore, they are suitable for mobile devices in software defined radio applications. These vector DSPs require input algorithms with vector operations. The performance of vectorized algorithms to a great extent depends on the distribution of data on vector elements. Traditional algorithms for vectorization focus on the extraction of parallelism from a program;we propose an analysis tool that focuses on the selection of an efficient dynamic data mapping for vector DSPs. We transferred Garcia's communication parallelism graph (Garcia et al., IEEE Trans Parallel Distrib Syst 12: 416-431, 2001) for distributed memory multiprocessor systems to vector DSPs. By alternating the representation of two-dimensional data distributions and the cost models, we are able to determine a dynamic mapping of data on vector elements on the Embedded Vector Processor (EVP) (van Berkel et al., Proceedings of the 2004 software-defined radio technical conference SDR'04, 2004). Additionally, we propose a new efficient algorithm for processing the graph representation that operates in two steps. We demonstrate the capabilities of our tool by describing the vectorization of some MIMO OFDM algorithms.

关键词： Vector DSPs vectorizing compilers

来源：评论

学校读者我要写书评

暂无评论

The infinity Lambda test: A multi-dimensional version of Banerjee infinity test

引用

PARALLEL COMPUTING 2000年第10期26卷 1275-1295页

作者： Chang, WL Chu, CP Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

The Banerjee infinity test accurately determines data dependence for one linear equation under symbolic limits and any given direction vectors (U. Banerjee, Depence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988;P.M. Petersen, Evaluation of programs and parallelizing compilers using dynamic analysis techniques, Ph.D. Thesis, University of Illinois at Urbana-Champaign, January 1993). For m linear equations with the same constraints, as each linear equation has to be tested separately, the Banerjee infinity test may generally lose the accuracy. In this paper, we proposed the infinity Lambda test - a multidimensional version of the Banerjee infinity test. The infinity Lambda test can be applied to deal with data dependence of coupled arrays with symbolic (unknown at compile time) bounds. Experiments with benchmark showed that the infinity Lambda test increases the success rate of the Lambda test by approximately 12%. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： parallelizing compilers vectorizing compilers data dependence analysis

来源：评论

学校读者我要写书评

暂无评论

Applying Data Mapping Techniques to Vector DSPs

Applying Data Mapping Techniques to Vector DSPs

引用

7th SAMOS International Workshop

ISBN: (纸本)1424410584

关键词： Vector DSPs vectorizing compilers

来源：评论

学校读者我要写书评

暂无评论

An efficient way to filter out data dependences with a sufficiently large distance between memory references

引用

ACM SIGPLAN NOTICES 2005年第4期40卷 51-60页

作者： Bulic, P Gustin, V Univ Ljubljana Fac Comp & Informat Sci Ljubljana 1000 Slovenia

There are a number of data dependence tests that have been proposed in the literature. The most widely used approximate data dependence tests are the Banerjee inequality and the GCD test. In this paper we consider parallelization for microprocessors with the multimedia extensions. For the short SIMD parallelism extraction it is essential that, if dependency exists, then the distance between memory references is greater than or equal to the number of data processed in the SIMD register. This implies that some loops that could not be vectorized on traditional vector processors can still be parallelized for the short SIMD execution. In this paper we present an accurate and simple method that can filter out data dependences with a sufficiently large distance between memory references for linear array references within a nested loop. The presented method is suitable for use in a dependence analyzer that is organized as a series of tests, progressively increasing in accuracy, as a replacement for the GCD or Banerjee tests.

关键词： data dependence analysis SIMD microprocessors vectorizing compilers

来源：评论

学校读者我要写书评

暂无评论

Testing data dependency for microprocessors with a short SIMD instruction set

ELEKTROTEHNISKI VESTNIK-ELECTROCHEMICAL REVIEW

引用

ELEKTROTEHNISKI VESTNIK-ELECTROCHEMICAL REVIEW 2009年第1-2期76卷 13-18页

作者： Bulic, Patricio Dobravec, Tomaz Univ Ljubljani Fak Racunalnistvo Informat Trzaska 25 Ljubljana 1000 Slovenia

In this paper we present an algorithm for the data-dependency problem related to microprocessors with a multimedia extension (i.e., including short SIMD instructions). Actually, there is a number of data-dependency tests proposed in literature (Banerjee test [2], GCD test [11], Omega test [7], Power test [10], etc.) which are all based on solving the linear dependence system. These tests would prohibit any vectorization if dependence exists even though this dependence would not be violeted after the vectorization. As an extension to the Baner-jee test, the presented method checks whether the vectorization affects any existing depenedence relation by checking the distance between two conflicting memory references. We assume a p-nested for loop. In short SIMD processing, we can process VI data simultaneously and these data must be successively stored in the memory. All the data must be of the same bit length b and the SIMD registers must V-l . b bits long. Thus, the problem of SIMD vectorization becomes a problem of whether we can unroll the innermost loop V-l times and substitute the simultaneous statements with a single SHAD statement that performs the same operation at a time, over V-l b-bits data in the (V-l . b)-bits SIMD register. In this paper, we prove that the distance between the memory references in the innermost loop, which is defined as d(i', i '') = i ''(p) - i'(p) is d(i', i '') = -a ''(p)zeta(i', i '') - vertical bar a'(p) - a ''(p) vertical bar i'(p). SIMD vectorization can be performed iff the distance between the memory references in the innermost loop is greater than or equal to the number of data processed in the SIMD register (V-l), i.e. max(i',i '' is an element of Ip) - a ''(p) zeta(i', i '') - vertical bar a'(p) - a ''(p) vertical bar i'(p) <= 0 or min(i',i '' is an element of Ip) -a ''(p)zeta(i', i '') - vertical bar a'(p) - a ''(p) vertical bar i'(p) >= V-l. As we compute only the bounds of an integer affine function, the presented method re

关键词： data dependency multimedia extensions SIMD instructions vectorizing compilers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：