**排序方式：**共有18条查询结果，搜索用时 109 毫秒

1.

Parameterized Polyhedra and Their Vertices

**总被引：2，自引：0，他引：2**Algorithms specified for parametrically sized problems are more general purpose and more reusable than algorithms for fixed sized problems. For this reason, there is a need for representing and symbolically analyzing linearly parameterized algorithms. An important class of parallel algorithms can be described as systems of parameterized affine recurrence equations (PARE). In this representation, linearly parameterized polyhedra are used to describe the domains of variables. This paper describes an algorithm which computes the set of parameterized vertices of a polyhedron, given its representation as a system of parameterized inequalities. This provides an important tool for the symbolic analysis of the parameterized domains used to define variables and computation domains in PAREs. A library of operations on parameterized polyhedra based on the Polyhedral Library has been written in C and is freely distributed. 相似文献

2.

K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations

*下载免费PDF全文***总被引：1，自引：0，他引：1**1IntroductionAlgorithmshavebeenproposedtosolvelinearrecurrencesinparallell1-13].Someofthemsupposeunlimitednumberofprocessorsbeingusedwhileothersuselimitednumberofprocessors.P-M.KoggeandH.S.Stoneproposedarecursivedou-blingalgorithmforthesolutionofageneraJclassofrecuxrenceequationsl1].Itisthefastestalgorithm(thetimeisO(log,N))whenthenumberofprocessingelemelltspiseqllaltoN.Howeveritisnotoptimalintermsofefficiency:itsspeedupisO(de),whileitsefficiencyisO(wt).TherecursivedoublingapproachcanPro… 相似文献

3.

In this paper, we deal with linear and nonlinear perturbations of first-order recurrence systems with constant coefficients having infinitely many equilibria. We give sufficient conditions for the asymptotic constancy of the solutions of the perturbed equation. As a consequence of our main theorem, we obtain sufficient conditions for systems of higher-order difference equations to have asymptotic equilibrium. 相似文献

4.

本文提出一种新的解Ｋｏｇｇｅ和Ｓｔｏｎｅ所定义的一类递推方程的优化的并行算法，当采用ｐ台处理机，对规模为Ｎ的一类递推方程求解时，该算法的加速比为Ｏ（ｐ），其中１≤ｐ≤Ｎ＾１－ε，ε是一个任意小的正数，与已有的并行算法相比，该算法具有效率高，适用范围广的优点，该算法可以在ＥＲＥＷ ＰＲＡＭ模型机上实现，也可以在具有素数内存系统的流水线向量处理机上实现。 相似文献

5.

Vincent Loechner Catherine Mongenet 《International journal of parallel programming》2000,28(1):47-102

This paper deals with communication optimization which is a crucial issue in automatic parallelization. From a system of parameterized affine recurrence equations we propose a heuristic that determines a set of efficient space-time transformations. It focuses on distant communications removal using broadcast—including anticipated broadcast, and locality enforcement. 相似文献

6.

Jean-Marc Vincent 《Discrete Event Dynamic Systems》1997,7(2):209-232

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in

^{K}of the form**T**(n+1) =_{ n+1}(**T**(*n*)) where_{ n }is a random operator*monotone*and 1—*linear*. We establish that the behaviour of the extremas of the process**T**(*n*) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points. 相似文献7.

Catherine Mongenet 《International journal of parallel programming》1997,25(6):497-524

This paper introduces results on placement and communications minimization for systems of affine recurrence equations. We show how to classify the dependences according to the number and nature of communications they may result in. We give both communication-free conditions and conditions for an efficient use of broadcast or neighbor-to-neighbor communication primitives. Since the dependences of a problem can generally not be all communication-free, we finally introduce a heuristic to globally minimize the communications based on the classification of dependences. 相似文献

8.

This paper presents an optimal algorithm for detecting line or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular, this algorithm is optimal for the classical approximation by direction sectors. This result generalizes, to the case of several statements. Wolf and Lam's algorithm which is optimal for a single statement. Our algorithm relies on a dependence uniformization process and on parallelization techniques related to system of uniform recurrence equations. It can also be viewed as a combination of both Allen and Kennedy's algorithm and Wolf and Lam's algorithm. 相似文献

9.

Sanjay V. Rajopadhye 《Distributed Computing》1989,3(2):88-105

We present a technique for synthesizing systolic arrays which have non-uniform data flow governed by control signals. The starting point for the synthesis is an

*Affine Recurrence Equation*—a generalization of the simple recurrences encountered in mathematics. A large class of programs, including most (single and multiple) nested-loop programs can be described by such recurrences. In this paper we extend our earlier work (Rajopadhye and Fujimoto 1986) in two principal directions. Firstly, we characterize a class of transformations called*data pipelining*and show that they yield recurrences that have*linear conditional expressions*governing the computation. Secondly, we discuss the synthesis of systolic arrays that have non-uniform data flow governed by control signals. We show how to derive the control signals in such arrays by applying similar pipelining transformations to these*linear conditional expressions*. The approach is illustrated by deriving the Guibas-Kung-Thompson architecture for computing the cost of optimal string parenthesization.Supported by a University of Utah Graduate Research Fellowship, and NSF grant No. MIP-8802454 相似文献10.

Shun-Shii Lin 《Journal of scientific computing》1994,9(1):65-80

A chained-matrices approach for parallel computing the

*n*th convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction in*O*(log*n*) time on the EREW PRAM model or a network with*O*(*n*/log*n*) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as and**e**, in*O*(log*m*) time by using*O*(*m*/log*m*) processors for a result with*m*-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the general*m*th order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.This work was supported in part by National Science Council of the Republic of China under Contract NSC 77-0408-E002-09. 相似文献