Method and apparatus for fault-tolerant parallel computation

• US 7,174,052 B2
• Filed: 01/15/2003
• Issued: 02/06/2007
• Est. Priority Date: 01/15/2003
• Status: Expired due to Fees

• Current Assignee: Conocophillips Company (ConocoPhillips)
• Original Assignee: Conocophillips Company (ConocoPhillips)
• Inventors: Menger, William Meredith
• Primary Examiner(s): Couso; Yon J.
• Application Number:
  US10/342,829
• Publication Number:
  US 20040136613A1
• Time in Patent Office: 1,483 Days
• Field of Search: 382/304, 382/298, 382/299, 382/260, 382/312, 345/502, 345/505, 345/564, 345/660, 345/667, 345/670, 345/671, 345/698, 348/246, 348/247, 358/1.2
• US Class Current: 382/304
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

A method and an apparatus for fault-tolerant computing in a parallel processing environment. Intermediate data points are determined from a set of input data by a plurality of processing elements operating in parallel. Preferably, the resolution of the intermediate data points is greater than the resolution required in an output imaging data set. The intermediate data points are spatially re-gridded to the resolution required in the output imaging data set, ignoring any missing data as a result of a processing element failing.

Claims

1. A method of generating from collected imaging data an output data set representing an object, the method comprising the steps of:

assigning grid points to be calculated of an intermediate data set to at least one of a plurality of processing elements, a resolution of the intermediate data set being greater than a desired resolution of the output data set;

generating from the collected imaging data by the plurality of processing elements the intermediate data set; and

generating from the intermediate data set the output data set having grid points of the desired resolution.

2. The method of claim 1, wherein the step of assigning is performed so as to reduce the instances that one of the processing elements is assigned to generate adjacent grid points.

3. The method of claim 1, wherein the step of assigning includes the steps of:

determining one or more factor sets from the number of available processing elements, each factor set containing a number of factors equivalent to the dimensions of the intermediate data set;

selecting from the factor sets a selected factor set in which the distance between the factors of the selected factor set is the least among the factor sets; and

assigning each grid point of the intermediate data set to the processing elements such that for each dimension of the intermediate data set each processing element calculates grid points at intervals substantially equivalent to the factors of the selected factor set in each respective dimension.

4. The method of claim 1, wherein the step of generating the output data set is performed by spatially regridding the intermediate data set.

5. The method of claim 1, wherein the step of generating the output data set is performed by a spectral decomposition and subsequent recomposition using a frequency transform.

6. The method of claim 1, wherein the step of generating the output data set is performed by a spectral decomposition and subsequent recomposition using a Fast Fourier Transform.

7. The method of claim 1, wherein the step of generating the output data set includes the steps of:

assigning each grid point of the output data set to at least one of the plurality of processing elements;

generating by one or more of the processing elements values for the grid points assigned to the processing elements and adjacent grid points; and

generating by one or more of the processing elements the output data set as the weighted sum of the values generated for each grid point of the output data set.

8. The method of claim 1, wherein the output data set represents a 2-dimensional image and the step of generating the output data set includes calculating each grid point of the output data set in accordance with the following equation:

$O_{\left(i,j\right)}=\frac{\sum <br><br>I_{\left(l,m\right)}<br><br>{\mathrm{e<br><br>}}^{-r}}{\sum <br><br>{\mathrm{e<br><br>}}^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m\right)},$

wherein;

O_(i,j) is the value of the output data set at location (i,j);

I_(l,m) is the value of the intermediate data set at location (l,m);

S_i and S_j are the strides in the dimensions corresponding to I and J, respectively; and

r is the vector distance between O_(i,j) and I_(l,m).

9. The method of claim 1, wherein the output data set represents a 3-dimensional image and the step of generating the output data set includes calculating each grid point of the output data set in accordance with the following equation:

$O_{\left(i,j,k\right)}=\frac{\sum <br><br>I_{\left(l,m,n\right)}<br><br>{\mathrm{e<br><br>}}^{-r}}{\sum <br><br>{\mathrm{e<br><br>}}^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2+S_k^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m,n\right)},$

wherein;

O_(i,j,k) is the calculated value of the output data set 140 at location (i,j,k);

I_(l,m,n) is the value of the intermediate data set 120 at location (l,m,n);

S_i, S_j, and S_k are the strides in the dimensions corresponding to I, J, and K, respectively; and

r is the vector distance between O_(i,j,k) and I_(l,m,n).

10. A method of generating from collected imaging data an output data set representing an object, the method comprising the steps of:

determining an intermediate grid density of an intermediate data set, the intermediate grid density having a plurality of grid points and being more dense than a desired grid density of the output data set;

assigning each grid point of the intermediate data set to at least one of a plurality of processing elements, the grid points being positioned in accordance with the intermediate grid density;

generating by the processing elements each grid point of the intermediate data set; and

generating from the intermediate data set the output data set having the desired grid density.

11. The method of claim 10, wherein the step of assigning is performed so as to reduce the instances that one of the processing elements is assigned to generate adjacent grid points.

12. The method of claim 10, wherein the step of assigning includes the steps of:

determining one or more factor sets of the number of available processing elements, each factor set containing a number of factors equivalent to the dimensions of the intermediate data set;

selecting from the factor sets a selected factor set in which a distance between the factors of the selected factor set is the least among the factor sets; and

assigning each grid point of the intermediate data set to the processing elements such that for each dimension of the intermediate data set each processing element calculates grid points at intervals equal to the factors of the selected factor set in each respective dimension.

13. The method of claim 10, wherein the step of determining the intermediate grid density is based at least in part upon the failure rate of the processing elements.

14. The method of claim 10, wherein the step of generating the output data set is performed by spatially regridding the intermediate data set.

15. The method of claim 10, wherein the step of generating the output data set is performed by a spectral decomposition and subsequent recomposition using a frequency transform.

16. The method of claim 10, wherein the step of generating the output data set is performed by a spectral decomposition and subsequent recomposition using a Fast Fourier Transform.

17. The method of claim 10, wherein the step of generating the output data set includes the steps of:

assigning each grid point of the output data set to at least one of the plurality of processing elements;

generating by one or more of the processing elements values for the grid points assigned to the processing elements and adjacent grid points; and

generating by one or more of the processing elements the output data set as the weighted sum of the values generated for each grid point of the output data set.

18. The method of claim 10, wherein the output data set is a 2-dimensional image and the step of generating the output image includes calculating each grid point of the output data set in accordance with the following equation:

$O_{\left(i,j\right)}=\frac{\sum <br><br>I_{\left(l,m\right)}<br><br>e^{-r}}{\sum <br><br>e^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m\right)},$

wherein;

O_(i,j) is the value of the output data set at location (i,j);

I_(l,m) is the value of the intermediate data set at location (l,m);

S_i and S_j are the strides in the dimensions corresponding to I and J, respectively; and

r is the vector distance between O_(i,j) and I_(l,m).

19. The method of claim 10, wherein the output data set is a 3-dimensional image and the step of generating the output image includes calculating each grid point of the output data set in accordance with the following equation:

$O_{\left(i,j,k\right)}=\frac{\sum <br><br>I_{\left(l,m,n\right)}<br><br>{\mathrm{e<br><br>}}^{-r}}{\sum <br><br>{\mathrm{e<br><br>}}^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt[3]{S_i^2+S_j^2+S_k^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m,n\right)},$

wherein;

O_(i,j,k) is the calculated value of the output data set 140 at location (i,j,k);

I_(l,m,n) is the value of the intermediate data set 120 at location (l,m,n);

S_i, S_j, and S_k are the strides in the dimensions corresponding to I, J, and K, respectively; and

r is the vector distance between O_(i,j,k) and I_(l,m,n).

20. An apparatus for generating an output data set of an imaged object, the apparatus comprising:

an input memory device for storing an input data set containing imaging data of the imaged object;

an intermediate memory device for storing an intermediate data set containing a gridded representation of the imaged object, the intermediate data set having a first grid density;

an output memory device for storing an output data set containing a gridded representation of the imaged object in a desired grid density, the desired grid density being greater than the first grid density;

a plurality of processing elements adapted for generating from the input data set the intermediate data set; and

a host computer adapted for generating from the intermediate data set the output data set.

21. The apparatus of claim 20, wherein the host computer is adapted for spatially regridding the intermediate data set to create the output data set.

22. The apparatus of claim 20, wherein the host computer is adapted for generating the output data set by spectral decomposition and subsequent recomposition using a frequency transform.

23. The apparatus of claim 20, wherein the host computer is adapted for generating the output data set by spectral decomposition and subsequent recomposition using a Fast Fourier Transform.

24. The apparatus of claim 20, wherein the processing elements are adapted for generating the output data set by performing the steps of:

assigning each grid point of the output data set to at least one of the plurality of processing elements;

generating by one or more of the processing elements values for the grid points assigned to the processing elements and adjacent grid points; and

generating by one or more of the processing elements the output data set as the weighted sum of the values generated for each grid point of the output data set.

25. The apparatus of claim 20, wherein the output data set is a 2-dimensional image and the host computer generates the output data set in accordance with the following equation:

$O_{\left(i,j\right)}=\frac{\sum <br><br>I_{\left(l,m\right)}<br><br>e^{-r}}{\sum <br><br>e^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m\right)},$

wherein;

O_(i,j) is the value of the output data set at location (i,j);

I_(l,m) is the value of the intermediate data set at location (l,m);

S_i and S_j are the strides in the dimensions corresponding to I and J, respectively; and

r is the vector distance between O_(i,j) and I_(l,m).

26. The apparatus of claim 20, wherein the output data set is a 3-dimensional image and the host computer generates the output data set in accordance with the following equation:

$O_{\left(i,j,k\right)}=\frac{\sum <br><br>I_{\left(l,m,n\right)}<br><br>{\mathrm{e<br><br>}}^{-r}}{\sum <br><br>{\mathrm{e<br><br>}}^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2+S_k^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m,n\right)},$

wherein;

O_(i,j,k) is the calculated value of the output data set 140 at location (i,j,k);

I_(l,m,n) is the value of the intermediate data set 120 at location (l,m,n);

S_i, S_j, and S_k are the strides in the dimensions corresponding to I, J, and K, respectively; and

r is the vector distance between O_(i,j,k) and I_(l,m,n).

27. The apparatus of claim 20, wherein the processing elements are further adapted for determining one or more factor sets of the number of available processing elements, each factor set containing a number of factors equivalent to the dimensions of the intermediate data set;

selecting from the factor sets a selected factor set in which a distance between the factors of the selected factor set is the least among the factor sets; and

assigning the processing elements such that for each dimension of the intermediate data set each processing element calculates grid points at intervals equal to the factors of the selected factor set in each respective dimension.

28. The apparatus of claim 20, wherein the host computer is one or more of the processing elements.

29. The apparatus for generating an output data set of an imaged object, the apparatus comprising:

an input memory device for storing an input data set containing imaging data of the imaged object;

an intermediate memory device for storing an intermediate data set containing a gridded representation of the imaged object, the intermediate data set having a first grid density;

an output memory device for storing an output data set containing a gridded representation of the imaged object, the output data set having a second grid density, the second grid density being less than or equal to the first grid density;

a plurality of processing elements adapted for generating from the input data set the intermediate data set; and

a host computer adapted for spatially regridding the intermediate data set to create the output data set.

30. The apparatus of claim 29, wherein output data set is a 2-dimensional image and the host computer generates the output data set in accordance with the following equation:

$O_{\left(i,j\right)}=\frac{\sum <br><br>I_{\left(l,m\right)}<br><br>e^{-r}}{\sum <br><br>e^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m\right)},$

wherein;

O_(i,j) is the value of the output data set at location (i,j);

I_(l,m) is the value of the intermediate data set at location (l,m,);

S_i and S_j are the strides in the dimensions corresponding to I and J, respectively; and

r is the vector distance between O_(i,j) and I_(l,m).

31. The apparatus of claim 29, wherein output data set is a 3-dimensional image and the host computer generates the output data set in accordance with the following equation:

$O_{\left(i,j,k\right)}=\frac{\sum <br><br>I_{\left(l,m,n\right)}<br><br>{\mathrm{e<br><br>}}^{-r}}{\sum <br><br>{\mathrm{e<br><br>}}^{-r}},\mathrm{for}<br><br><br><br>\mathrm{all}<br><br><br><br>r\le <br><br>\sqrt{S_i^2+S_j^2+S_k^2}<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{non}<br><br>\text{-}<br><br>\mathrm{NULL}<br><br><br><br>I_{\left(l,m,n\right)},$

wherein;

O_(i,j,k) is the calculated value of the output data set 140 at location (i,j,k);

I_(l,m,n) is the value of the intermediate data set 120 at location (l,m,n);

S_i, S_j, and S_k are the strides in the dimensions corresponding to I, J, and K, respectively; and

r is the vector distance between O_(i,j,k) and I_(l,m,n).

32. An apparatus of claim 29, wherein the processing elements are further adapted for determining one or more factor sets of the number of available processing elements, each factor set containing a number of factors equivalent to the dimensions of the intermediate data set;

selecting from the factor sets a selected factor set in which a distance between the factors of the selected factor set is the least among the factor sets; and

assigning the processing elements such that each processing element calculates grid points at intervals equal to the factors of the selected factor set in each respective dimension.

33. The apparatus of claim 29, wherein the host computer is one or more of the processing elements.

34. An apparatus for generating from collected imaging data an output data set representing an object, the apparatus comprising:

means for assigning a plurality of grid points of an intermediate data set to at least one of a plurality of processing elements, a resolution of the intermediate data set being greater than a desired resolution of the output data set;

means for receiving imaging data and generating a gridded representation of that data to be saved as the intermediate data set; and

means for receiving the intermediate data set and generating a gridded representation of that data to be saved as the output data set having the desired resolution.

35. The apparatus of claim 34, wherein the means for assigning includes means for reducing the instances that one of the processing elements is assigned to generate adjacent grid points.

36. The apparatus of claim 34, wherein the means for assigning includes:

means for determining one or more factor sets of the number of available processing elements, each factor set containing a number of factors equivalent to the dimensions of the intermediate data set;

means for selecting from the factor sets a selected factor set in which a distance between the factors of the selected factor set is the least among the factor sets; and

means for assigning the processing elements such that for each dimension of the intermediate data set each processing element calculates grid points at intervals equal to the factors of the selected factor set in each respective dimension.

37. A computer program product for generating from collected imaging data an output data set representing an object, the computer program product residing on a computer readable medium with a computer program embodied thereon, the computer program comprising:

computer program code for assigning a plurality of grid points of an intermediate data set to at least one of a plurality of processing elements, a resolution of the intermediate data set being greater than a desired resolution of the output data set;

computer program code for receiving imaging data and generating a gridded representation of that data to be saved as the intermediate data set; and

computer program code for receiving the intermediate data set and generating a gridded representation of that data to be saved as the output data set having the desired resolution.

38. The computer program product of claim 37, wherein the computer program code for assigning includes computer program code for reducing the instances that one of the processing elements is assigned to generate adjacent grid points.

39. The computer program product of claim 37, wherein the computer program code for assigning includes:

computer program code for determining one or more factor sets of the number of available processing elements, each factor set containing a number of factors equivalent to the dimensions of the intermediate data set;

computer program code for selecting from the factor sets a selected factor set in which a distance between the factors of the selected factor set is the least among the factor sets; and

computer program code for assigning the processing elements such that for each dimension of the intermediate data set each processing element calculates grid points at intervals equal to the factors of the selected factor set in each respective dimension.