Multi-adaptive processing systems and techniques for enhancing parallelism and performance of computational functions

• US 7,620,800 B2
• Filed: 04/09/2007
• Issued: 11/17/2009
• Est. Priority Date: 10/31/2002
• Status: Expired due to Term

• Current Assignee: FG SRC LLC (Freeman Capital Partners LP)
• Original Assignee: SRC Computers, Inc.
• Inventors: Huppenthal, Jon M., Caliga, David E.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US11/733,064
• Publication Number:
  US 20070204131A1
• Time in Patent Office: 953 Days
• Field of Search: 712/226, 712/15, 712/19, 712/215
• US Class Current: 712/226
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus

Abstract

Multi-adaptive processing systems and techniques for enhancing parallelism and performance of computational functions are disclosed which can be employed in a myriad of applications including multi-dimensional pipeline computations for seismic applications, search algorithms, information security, chemical and biological applications, filtering and the like as well as for systolic wavefront computations for fluid flow and structures analysis, bioinformatics etc. Some applications may also employ both the multi-dimensional pipeline and systolic wavefront methodologies disclosed.

Claims

1. A method for data processing in a reconfigurable computing system, the reconfigurable computing system comprising at least one reconfigurable processor, the reconfigurable processor comprising a plurality of functional units, said method comprising:

transforming an algorithm into a data driven calculation that is implemented by said reconfigurable computing system at the at least one reconfigurable processor;

forming at least two of said functional units at the at least one reconfigurable processor to perform said calculation wherein only functional units needed to solve the calculation are formed and wherein each formed functional unit at the at least one reconfigurable processor interconnects with each other formed functional unit at the at least one reconfigurable processor based on reconfigurable routing resources within the at least one reconfigurable processor as established at formation, and wherein lines of code of said calculation are formed as clusters of functional units within the at least one reconfigurable processor;

utilizing a first of said formed functional units to operate upon a subsequent data dimension of said calculation forming a first computational loop; and

substantially concurrently utilizing a second of said formed functional units to operate upon a previous data dimension of said calculation generating a second computational loop wherein said implementation of said calculation enables said first computational loop and said second computational loop execute concurrently and pass computed data seamlessly between said computational loops.

2. The method of claim 1 wherein said subsequent and previous data dimensions of said calculation comprise multiple vectors in said calculation.

3. The method of claim 1 wherein said subsequent and previous data dimensions of said calculation comprise multiple planes in said calculation.

4. The method of claim 1 wherein said subsequent and previous data dimensions of said calculation comprise multiple time steps in said calculation.

5. The method of claim 1 wherein said subsequent an previous data dimensions of said calculation comprise multiple grid points in said calculation.

6. The method of claim 1 wherein said calculation comprises a seismic imaging calculation.

7. The method of claim 1 wherein said calculation comprises a synthetic aperture radar imaging calculation.

8. The method of claim 1 wherein said calculation comprises a JPEG image compression calculation.

9. The method of claim 1 wherein said calculation comprises an MPEG image compression calculation.

10. The method of claim 1 wherein said calculation comprises a fluid flow calculation for a reservoir simulation.

11. The method of claim 1 wherein said calculation comprises a fluid flow calculation for weather prediction.

12. The method of claim 1 wherein said calculation comprises a fluid flow calculation for automotive applications.

13. The method of claim 1 wherein said calculation comprises a fluid flow calculation for aerospace applications.

14. The method of claim 1 wherein said calculation comprises a fluid flow calculation for an injection molding application.

15. The method of claim 1 wherein instantiating includes establishing a stream communication connection between functional units.

16. The method of claim 1 wherein said calculation is comprises a structures calculation for structural analysis.

17. The method of claim 1 wherein said calculation comprises a search algorithm for an image search.

18. The method of claim 1 wherein said calculation comprises a search algorithm for data mining.

19. The method of claim 1 wherein said calculation comprises a financial modeling application.

20. The method of claim 1 wherein said calculation comprises an encryption algorithm.

21. The method of claim 1 wherein said calculation comprises a genetic pattern matching function.

22. The method of claim 1 wherein said calculation comprises a protein folding function.

23. The method of claim 1 wherein said calculation comprises an organic structure interaction function.

24. The method of claim 1 wherein said calculation comprises a signal filtering application.

25. A method for data processing in a reconfigurable computing system, the reconfigurable computing system comprising at least one reconfigurable processor comprising a plurality of functional units, said method comprising:

transforming an algorithm into a data driven calculation that is implemented by said reconfigurable computing system at the at least one reconfigurable processor wherein linked lines of code of said calculation are fashioned as walls of functional units within the at least one reconfigurable processor;

defining a first wall comprising rows of cells forming a subset of said plurality of functional units;

computing at the at least one reconfigurable processor a value at each of said cells in at least a first row of said first wall substantially concurrently;

communicating said values between cells in said first row of said cells to produce updated values, wherein communicating said values is based on reconfigurable routing resources within the at least one reconfigurable processor;

communicating said updated values substantially concurrently to a second row of said first wall, wherein communicating said updated values is based on reconfigurable routing resources within the at least one reconfigurable processor; and

communicating said updated values substantially concurrently to a first row of a second wall of rows of cells in said subset of said plurality of functional units, wherein communicating said updated values is based on reconfigurable routing resources within the at least one reconfigurable processor and wherein said first wall of rows of cells and said second wall of rows of cells execute substantially concurrently and pass computed data seamlessly between said walls.

26. The method of claim 25 wherein said values correspond to vectors in a computation.

27. The method of claim 25 wherein said values correspond to planes in a computation.

28. The method of claim 25 wherein said values correspond to time steps in a computation.

29. The method of claim 25 wherein said values correspond to grid points in a computation.

30. The method of claim 25 wherein said step of communicating said updated values to a second row of said first wall is carried out without storing said updated values in an extrinsic memory.

31. The method of claim 25 wherein said values correspond to a seismic imaging calculation.

32. The method of claim 25 wherein said values correspond to a synthetic aperture radar imaging calculation.

33. The method of claim 25 wherein said values correspond to a JPEG image compression calculation.

34. The method of claim 25 wherein said values correspond to an MPEG image compression calculation.

35. The method of claim 25 wherein said values correspond to a fluid flow calculation for a reservoir simulation.

36. The method of claim 25 wherein said values correspond to a fluid flow calculation for weather prediction.

37. The method of claim 25 wherein said values correspond to a fluid flow calculation for automotive applications.

38. The method of claim 25 wherein said values correspond to a fluid flow calculation for aerospace applications.

39. The method of claim 25 wherein said values correspond to a fluid flow calculation for an injection molding application.

40. The method of claim 25 wherein defining includes establishing a stream communication connection between functional units and wherein only functional units needed to solve the calculations are instantiated.

41. The method of claim 25 wherein said values correspond to a structures calculation for structural analysis.

42. The method of claim 25 wherein said values correspond to a search algorithm for an image search.

43. The method of claim 25 wherein said values correspond to a search algorithm for data mining.

44. The method of claim 25 wherein said values correspond to a financial modeling application.

45. The method of claim 25 wherein said values correspond to an encryption algorithm.

46. The method of claim 25 wherein said values correspond to a genetic pattern matching function.

47. The method of claim 25 wherein said values correspond to a protein folding function.

48. The method of claim 25 wherein said values correspond to an organic structure interaction function.

49. The method of claim 25 wherein said values correspond to a signal filtering application.

50. The method of claim 25 wherein said reconfigurable computing system comprises at least one microprocessor.

51. A method for data processing in a reconfigurable computing system, the reconfigurable computer system comprising at least one reconfigurable processor comprising a plurality of functional units, said method comprising:

transforming an algorithm into a calculation implemented by said reconfigurable computing system at the at least one reconfigurable processor and driven by data propagation wherein lines of code of said calculation are linked based on said data propagation and fashioned as subsets of said plurality of functional units within the at least one reconfigurable processor forming columns of said calculation;

performing said calculation at the at least one reconfigurable processor by said subsets of said plurality of functional units to produce computed data;

exchanging said computed data between a first column of said calculation and a next column in said calculation, wherein said exchanging is based on reconfigurable routing resources within the at least one reconfigurable processor and wherein execution of said subsets of said plurality of function units occurs concurrently and said computed data is seamlessly passed between said first column of said calculation and said second column of said calculation;

evaluating a rate of change in at least one variable for each of said columns in said calculation;

continuing said calculation when said variable does not change for a particular column of said calculation; and

restarting said calculation at said column of said calculation where said variable does change.

52. The method of claim 51 wherein how many functional units comprise the subset and functional type of each functional unit in said subset is based on the calculation.