Paper Info
Title
Parallel Solutions of Indexed Recurrence Equations
Abstract
A new type of recurrence equations called "indexed recurrences" (IR) is defined, in which the common notion of X[i] = op(X[i],X[i-1]) i=1..n is generalized to X[g(i)] = op(X[f(i)],X[h(i)]) f,g,h:{1..n} - {1..m}. This enables us to model sequential loops of the form for i = 1 to n do begin X[g(i)] := op(X[f(i)],X[h(i)]); as IR equations.Thus, a parallel algorithm that solves a set of IR equations is in fact a way to transform sequential loops into parallel ones. Note that the circuit evaluation problem (CVP) can also be expressed as a set of IR equations. Therefore an efficient parallel solution to the general IR problem is not likely to be found, as such solution would also solve the CVP, showing that P is a subset of, or equal NC.In this paper we introduce parallel algorithms for two variants of the IR equations problem: 1. An O(log n) greedy algorithm for solving IR equations where g(i) is distinct and h(i) = g(i) using O(n) processors.2. An O(log^2 n) algorithm with no restriction on f,g or h, using up to O(n^2) processors.However, we show that for general IR, 'op' must be commutative so that a parallel computation can be used.
Year
Venue
Keywords
1997
IPPS
parallel algorithm,general IR problem,general IR,IR equations problem,circuit evaluation problem,sequential loop,parallel computation,greedy algorithm,efficient parallel solution,Indexed Recurrence Equations,IR equation,Parallel Solutions
DocType
ISBN
Citations 
Conference
0-8186-7792-9
2
PageRank 
References 
Authors
0.42
3
2
Name
Order
Citations
PageRank
Gadi Haber1559.19
Yosi Ben-Asher220632.29