US 5,630,156 A · Process for parallel operation of several computation units, especially in image processing, and corresponding architecture

Abstract

Improved process for parallel operation of several computation units, especially in image processing, and corresponding architecture. Several computation units which are together intended to evaluate in an iterative and cellular manner the convergence values of a plurality of variables associated respectively with the various points of a predetermined grid each variable having to satisfy a prespecified iterative relation between itself and n neighbouring variables associated with n neighbouring grid points (P2-P5), a memory means is assigned per point of the grid, intended to store successively all the values of the variable associated with this grid point, the computation units are apportioned in such a way as to assign every grid point to a computation unit and two distinct computation units to two chosen neighbouring points of the grid, all the computation units are made to operate in parallel and independently of one another, and for each current point of the grid, the computation unit assigned to this current point is made to compute each successive value of the variable associated with this current point on the basis of the value contained in the memory means assigned to the current point and of those available and arising from the memory means assigned to the points neighbouring the current point, irrespective of the iteration levels to which these available values correspond, and the said computation unit is made to store each new value thus computed in the memory means associated with the current point.

Claims36

Dependent claims

A process for affecting a pseudo-asynchronism of operation between several computation units (PE1, PE2) which are together intended to evaluate in an iterative and cellular manner convergence values of a plurality of variables associated respectively with various points (P1-P5) of a predetermined grid (MA), each variable having to satisfy a prespecified iterative relation between itself and n neighboring variables associated with n neighboring grid points (P2-P5), wherein:

a memory means (AM1, BM1, Z1) is assigned per point of the grid, intended to store successively all the values of the variable associated with this grid point (P1),
the computation units are apportioned in such a way as to assign every grid point (P1) to a computation unit and two distinct computation units (PE1, PE2) to two chosen neighboring points (P1, P2) of the grid,
all the computation units are made to operate in parallel and independently of one another,
and for each current point of the grid,
the computation unit assigned to this current point is made to compute each successive value of the variable associated with this current point on the basis of the value contained in the memory means assigned to the current point and of those available and arising from the memory means assigned to the points neighboring the current point, irrespective of iteration levels to which these available values correspond, and
the said computation unit is made to store each new value thus computed in the memory means associated with the current point.

3 more elements

A pseudo-asynchronous parallel architecture of computation units, which are together intended to evaluate in an iterative and cellular manner convergence values of a plurality of variables associated respectively with various points (P1-P5) of a predetermined grid (MA), each variable having to satisfy a prespecified iterative relation between itself an n neighboring variables associated with n neighboring grid points (P2-P5), including an apportioning of the computation units assigning every point of the grid to a computation unit and two distinct computation units to at least two chosen neighboring points of the grid, and comprising:

a first memory means (AM1, BM1, Z1) associated with each current point (P1) of the grid, for successively storing all the values of the current variable of the current point, and capable of being connected to the computation unit (PE1) assigned to this current point (P1);
n transfer means (N1, E1, S1, W1) linked respectively to the first n memory means assigned to the n points neighboring each current point and capable of delivering respectively, to the computation unit assigned to the said current point, n available values derived from those contained in the first n memory means;
means for controlling the operation of each computation unit, which are capable of respectively making all the computation units operate in parallel and independently of one another;
and
processing means incorporated respectively in each computation unit, and capable respectively, on the basis of the value contained in the first memory means of the current point and of the values delivered by the n corresponding transfer means, irrespective of the iteration levels to which these delivered values correspond,
of determining a new value for the variable associated with the current point, and
of storing this new value in the said first memory means of the current point.

4 more elements

Dependencies are inferred from the claim text.

Process for parallel operation of several computation units, especially in image processing, and corresponding architecture

Life of this patent

Process for parallel operation of several computation units, especially in image processing, and corresponding architecture

Life of this patent

Abstract

Claims36