System for parallel processing that compiles a filed sequence of instructions within an iteration space

Abstract

An improved parallel processing apparatus and method executes an iterative sequence of instructions by arranging the sequence into subtasks and allocating those subtasks to processors. This division and allocation is conducted in such a manner as to minimize data contention among the processors and to maximize the locality of data to them. The improved apparatus and method have application to a variety of multiprocessor systems, including those which are massively parallel.

Claims

In view of the foregoing, what we claim is:

1. In a parallel processor digital data processing apparatus of the type having

a plurality of processing units, each for executing instructions,

memory means coupled to said processing units for storing at least one of data and instructions,

interprocessor communication means coupled to said processing units for transferring information therebetween,

the improvement for processing an iterative sequence of instructions wherein:

A. said memory means includes means for storing a tiled sequence of instructions representing the iterative sequence, and each of said plural processing units includes means for signalling its availability to execute said tiled sequence over a portion of an iteration space associated with said iterative sequence, said portion being referred to as a tile,

B. said apparatus includes next-tile means coupled to said processing units for responding to each of at least selected such signallings by those processing units for generating a signal representing boundaries of a tile over which to execute said tiled sequence, wherein each such tile does not overlap any other tile, wherein each such tile covers a portion less than a whole of said iteration space, and wherein all such tiles together cover said iteration space,

C. each said processing unit including means for responding to a boundary-representative signal generated in response to signalling by that processing unit for executing said tiled sequence over the corresponding tile.

2. In a digital data processing apparatus according to claim 1, the further improvement comprising

A. tile-build means for generating a tile-shape signal indicative of one or more dimensions of said boundary-representative signals, in view of dependency between the corresponding tiles,

B. wherein said tiled sequence includes one or more instructions for write-type access of a datum stored in said memory means,

C. said memory means includes

i) a plurality of memory elements, each for storing at least one of data and instructions, each said memory element being coupled to an associated one of said processing units, and

ii) memory management means coupled with said memory elements for selectively transferring information therebetween, and

D. said next-tile means includes means for generating said boundary-representative signals as a function of said tile-shape signal.

3. In a parallel processor digital data processing apparatus according to claim 2, the further improvement wherein said tile-build means includes means for generating said tile-shape signal indicative of dimensions of said boundary-representative signals that minimize the number of individual datum subject to write-type access during execution of different ones of corresponding tiles.

4. In a parallel processor digital data processing apparatus according to claim 2, the further improvement wherein said tile-build means includes means for generating a tile-shape signal indicative of dimensions of said boundary-representative signals that minimize the number of individual datum subject to write-type access by plural concurrently-executing ones of the processing units.

5. In a parallel processor digital data processing apparatus according to claim 2, wherein

A. first and second tiles include any of

i) an instruction in said first tile that accesses for write-type access a selected datum, and a instruction in said second tile that subsequently accesses for read-type access that same datum,

ii) an instruction in said first tile that accesses for read-type access a selected datum, and an instruction in said second tile that subsequently accesses for write-type access that same datum,

iii) an instruction in said first tile that accesses for write-type access a selected datum, and an instruction in said second tile that subsequently accesses for write-type access that same datum, and

B. said tile-build means includes means for generating a tile-shape signal indicative of dimensions of said boundary-representative signals that minimizes dependence of execution of said second tile upon execution of said first tile with respect to their respective accessing of said selected datum.

6. An apparatus according to claim 2, wherein said tile-build means includes means for generating an affinity signal representative of a tile execution sequence that minimizes a transfer of a data subject to any of read-type and write-type access during execution of successive tiles by different processing units.

7. In a digital data processing apparatus according to claim 2, the further improvement wherein said tile-build means comprises tile-shape means for generating said tile-shape signal as a function of at least one of

i) an affinity signal representing a tile execution sequence that minimizes a transfer of a data subject to any of read-type or write-type access by successive executions of said tiles by different ones of said processing units,

ii) a dependency direction of said tiled sequence,

iii) a processing cost associated with execution of said tiled sequence,

iv) a size of said iteration space,

v) a number of processing units available for execution of said tiled sequence, and

vi) an affinity region signal indicating that the tiled sequence is to be executed within an iteration space defined by a plurality of tile sequences.

8. In a parallel processor digital data processing apparatus according to claim 1, the further improvement wherein

A. said next-tile means includes means for generating successive ones of said boundary-representative signals as a function of at least one of

i) a tile-shape signal indicative of one or more dimensions of said boundary-representative signals,

ii) a tile-strategy signal indicative of at least one of a sequence and manner of assigning tiles to said processing units,

iii) an affinity region signal indicating that the tiled sequence is to be executed within an iteration space defined by a plurality of tile sequences,

B. said apparatus comprises tile-strategy means for generating said tile-strategy signal, and

C. wherein said iteration space is defined by a plurality of indices.

9. In a parallel processor digital data processing apparatus according to claim 8, the further improvement wherein said tile-strategy means includes selectively actuable slice means for

i) generating a tile-shape signal indicative of boundary-representative signals dividing the iteration space by a number of processing units allocated to said execution with respect to one of said indices and spanning the iteration space with respect to the others of those indices, wherein the number of respective tiles is equal to that a number of available processing units, wherein those tiles are substantially equal in size, and

ii) generating a tile-strategy signal indicative of generation of the respective tiles so as to cause one each of them to be executed by a respective one of the available processing units.

10. In a parallel processor digital data processing apparatus according to claim 9, the further improvement wherein said tile-strategy means includes means for actuating said slice means in instances in which

i) data subject to access during execution of any such tile does not depend on that modified during execution of any other such tile, and

ii) no substantial quantity of data subject to any of read-type and write-type access by one such tile is also subject to any of read-type and write-type access by another such tile.

11. In a parallel processor digital data processing apparatus according to claim 9, the further improvement comprising means for actuating said slice means in response to a user-supplied signal.

12. In a parallel processor digital data processing apparatus according to claim 8, the further improvement wherein said tile-strategy means includes selectively actuable modulo means for

i) generating boundary-representative signals to divide the iteration space in fixed-length increments along all of said indices, and

ii) generating a tile-strategy signal indicative of assignment of the respective tiles based on a modulus of a numerical identifier associated with each of the available processing units and a numerical identifier associated with each of the tiles.

13. In a parallel processor digital data processing apparatus according to claim 12, the further improvement wherein said tile-strategy means includes means for actuating said modulo means in instances in which

i) data subject to access during execution of any such tile does not depend on that modified during execution of any other such tile,

ii) no substantial quantity of data subject to any of read-type and write-type access by one such tile is also subject to any of read-type and write-type access by another such tile, and

iii) re-use of data subject to any of read-type or write-type access by a processing unit executing a plurality of tiles is maximized, even in the presence of a change of a size of said iteration space.

14. In a parallel processor digital data processing apparatus according to claim 12, the further improvement comprising means for actuating said modulo means in response to a user-supplied signal.

15. In a parallel processor digital data processing apparatus according to claim 8, the further improvement wherein said tile-strategy means includes selectively actuable wavefront means for

i) generating boundary-representative signals dividing the iteration space along one or more of said indices, wherein data subject to access during execution of at least selected tiles depends on that modified during execution of another tile, and wherein those tiles have a dependency direction,

ii) generating a tile-strategy signal indicative of a sequence of generation of the respective tiles in accord with that dependency direction.

16. In a parallel processor digital data processing apparatus according to claim 15, the further improvement wherein said tile-strategy means includes means for actuating said wavefront means wherein data subject to access during execution of at least one such tile depends on that modified during execution of another such tile.

17. In a parallel processor digital data processing apparatus according to claim 15, the further improvement comprising means for actuating said wavefront means in response to a user-supplied signal.

18. In a parallel processor digital data processing apparatus according to claim 8, the further improvement wherein said tile-strategy means includes selectively actuable modulo/wavefront means for

i) generating boundary-representative signals to divide the iteration space in fixed-length increments along all of said indices, wherein data subject to access during execution of at least a selected tile depends on that modified during execution of one or more other tiles, and wherein said tiles have a dependency direction, and

ii) generating a tile-strategy signal indicative of assignment of the respective tiles based on a modulus of a numerical identifier associated with each of the available processing units and a numerical identifier associated with each of the tiles, and on that dependency direction.

19. In a parallel processor digital data processing apparatus according to claim 18, the further improvement wherein said tile-strategy means includes means for actuating said modulo/wavefront means in instances in which

i) data subject to access during execution of at least one such tile depends on that modified during execution of one or more other such tiles, and

ii) re-use of data subject to any of read-type or write-type access by a processing unit executing a plurality of tiles is maximized, even in the presence of a change of a size of said iterative space.

20. In a parallel processor digital data processing apparatus according to claim 18, the further improvement comprising means for actuating said modulo/wavefront means in response to a user-supplied signal.

21. In a parallel processor digital data processing apparatus according to claim 8, the further improvement wherein said tile-strategy means includes selectively actuable grab means for

i) generating boundary-representative signals to divide the iteration space in fixed-length increments along all of said indices, and wherein data subject to access during execution of any tile does not depend on that modified during execution of any other tile, and

ii) generating a tile-strategy signal indicative of a sequence of generation of the respective tiles, in response to said signalling for availability by said processing units, on a first-come-first-serve basis.

22. In a parallel processor digital data processing apparatus according to claim 21, the further improvement wherein said tile-strategy means includes means for actuating said grab means

i) to facilitate load-balancing among processing units executing said tiles, and in instances when

ii) no substantial quantity of data is subject to any of read-type and write-type access by one such tile is also subject to any of read-type and write-type access by another such tile.

23. In a parallel processor digital data processing apparatus according to claim 21, the further improvement comprising user-responsive means for actuating said wavefront means.

24. In a parallel processor digital data processing apparatus according to claim 1, the further improvement comprising

A. means for providing an affinity region signal representative of one or more iteration sequences that access the same data,

B. affinity region-build means for generating one or more of

i) a signal representative of an iteration space in which one or more tiled sequences within the affinity region are to be executed,

ii) a tile-shape signal representative of one or more dimensions of a boundary-representative signal,

iii) a tile-strategy signal indicative of at least one of a sequence and manner of assigning tiles to said processing units, and

iv) a team signal representative of a set of processing units by which the tiled sequences within the affinity region are to be executed to minimize a transfer of a data subject to any of read-type and write-type access during such execution.

25. In a parallel processor digital data processing apparatus according to claim 24, the further improvement wherein said affinity region-build means includes means for defining said iteration space to encompass one or more of the iteration spaces of the tile sequences in said affinity region.

26. In a parallel processor digital data processing apparatus according to claim 1, the improvement wherein said next-tile means includes means for generating said boundary-representative signals so as to maximize a locality of data subject to access during execution of one or more corresponding tiles, and to minimize contention for access to such data during such execution.

27. In a compiler of the type for translating program signals representative of a program, including an iterative sequence, in source code format into a code sequence of instructions in an object code format suitable for loading for execution by a plurality of parallel digital data processing units,

the improvement comprising

tiling means for responding to said iterative sequence in source code format

for generating a tiled sequence of instructions representative thereof in object code format, and

for further responding to that iterative sequence and to zero, one or more user-specified signals for generating one or more signals representing a framework for generating boundaries for plural tiles over which said tiled sequence is to be executed by said plurality of parallel digital data processing units, each such tile comprising a portion less than a whole of an iteration space associated with said iterative sequence.

28. In a compiler according to claim 27, wherein said compiler includes dependency means for determining a dependency direction of said iterative sequence and for generating a signal representative thereof, the further improvement comprising parallelization means for responding to instructions in said iterative sequence and to said dependency direction-representative signal for generating signals representative of one or more indexes in said iteration space over which to execute said tiled sequence.

29. In a compiler according to claim 28, the further improvement comprising

A. input means for accepting signals representative of a user-specified indexing of said iteration space, and

B. means coupled with said input means and said parallelization means includes means for comparing said user-specified indexing signals with those generated by said parallelization means, and for generating a notification signal in the event of at least selected disagreement thereof.

30. In a compiler according to claim 28, the further improvement comprising optimizing means coupled to said parallelization means for generating one or more signals for use at runtime in optimizing parallel execution of said tiled sequence.

31. In a compiler according to claim 30, the further improvement wherein said optimizing means comprises means for generating an affinity signal representative of a tile execution sequence that minimizes a transfer of data subject to any of read-type or write-type access during execution thereof in plural tiles.

32. In a compiler according to claim 30, the further improvement wherein said optimizing means comprises means for generating an affinity region signal representative of one or more iteration sequences that access the same data.

33. In a compiler according to claim 32, the further improvement comprising

A. input means for accepting signals representative of a user-specified affinity region signal, and

B. means coupled with said input means and said optimizing means includes means for comparing said user-specified affinity region signal with that generated by said optimizing means, and for generating a notification signal in the event of at least selected disagreement thereof.

34. In a compiler according to claim 30, the further improvement wherein said optimizing means comprises means for generating a signal representative of an estimate of a processing cost associated with execution of said tiled sequence.

35. In a compiler according to claim 27, the improvement comprising call-generating means for replacing said iterative sequence in said source code format with an instruction representative of a call to a code-dispatching subroutine.

36. In a compiler according to claim 35, the improvement comprising run-time means for executing said call-representative instruction for initiating execution of said tiled sequence by said processing units.

37. In a method of operating a parallel processor digital data processing apparatus of the type having

a plurality of processing units, each for executing instructions,

memory means coupled to said processing units for storing at least one of data and instructions,

interprocessor communication means coupled to said processing units for transferring information therebetween,

the improvement for processing an iterative sequence of instructions comprising the steps of:

A. storing a tiled sequence of instructions representing the iterative sequence,

B. signalling, for each of said plurality of processing units, its availability to execute said tiled sequence over a portion of an iteration space associated with said iterative sequence, said portion being referred to as a tile,

C. responding to each of at least selected such signallings by those processing units for generating a signal representing boundaries of a tile over which to execute said tiled sequence, wherein each such tile does not overlap any other tile, wherein each such tile covers a portion less than a whole of said iteration space, and wherein all such tiles together cover said iteration space, and

D. each said processor responding to a boundary-representative signal generated in response to signalling by that processing unit for executing said tiled sequence over the corresponding tile.

38. In a method according to claim 37, the further improvement comprising the steps of

A. generating a tile-shape signal indicative of one or more dimensions of said boundary-representative signals, in view of dependency between the corresponding tiles,

B. wherein said tiled sequence includes one or more instructions for write-type access of a datum stored in said memory means,

C. providing a plurality of memory elements, each for storing at least one of data and instructions, each said memory element being coupled to an associated one of said processing units, and selectively transferring information between said memory elements, and

D. generating said boundary-representative signals as a function of said tile-shape signal.

39. In a method according to claim 38, the further improvement comprising generating said tile-shape signal indicative of dimensions of said boundary-representative signals that minimize the number of individual datum subject to write-type access during execution of different ones of corresponding tiles.

40. In a method according to claim 38, the further improvement comprising generating a tile-shape signal indicative of dimensions of said boundary-representative signals that minimize the number of individual datum subject to write-type access by plural concurrently-executing ones of the processing units.

41. In method according to claim 38, wherein

A. first and second tiles include any of

i) an instruction in said first tile that accesses for write-type access a selected datum, and a instruction in said second tile that subsequently accesses for read-type access that same datum,

ii) an instruction in said first tile that accesses for read-type access a selected datum, and an instruction in said second tile that subsequently accesses for write-type access that same datum,

iii) an instruction in said first tile that accesses for write-type access a selected datum, and an instruction in said second tile that subsequently accesses for write-type access that same datum, the further improvement comprising the step of

B. generating a tile-shape signal indicative of dimensions of said boundary-representative signals that minimizes dependence of execution of said second tile upon execution of said first tile with respect to their respective accessing of said selected datum.

42. In a method according to claim 38, the further comprising generating an affinity signal representative of a tile execution sequence that minimizes a transfer of a data subject to any of read-type and write-type access during execution of successive tiles by different processing units.

43. In a method according to claim 38, the further improvement comprising the step of generating said tile-shape signal as a function of at least one of

i) an affinity signal representing a tile execution sequence that minimizes a transfer of a data subject to any of read-type or write-type access by successive executions of said tiles by different ones of said processing units,

ii) a dependency direction of said tiled sequence,

iii) a processing cost associated with execution of said tiled sequence,

iv) a size of said iteration space,

v) a number of processing units available for execution of said tiled sequence, and

vi) an affinity region signal indicating that the tiled sequence is to be executed within an iteration space defined by a plurality of tile sequences.

44. In a method according to claim 37, the further improvement comprising the steps of

A. generating successive ones of said boundary-representative signals as a function of at least one of

i) a tile-shape signal indicative of one or more dimensions of said boundary-representative signals,

ii) a tile-strategy signal indicative of at least one of a sequence and manner of assigning tiles to said processing units,

iii) an affinity region signal indicating that the tiled sequence is to be executed within an iteration space defined by a plurality of tile sequences,

B. generating said tile-strategy signal, and

C. wherein said iteration space is defined by a plurality of indices.

45. In a method according to claim 44, the further improvement comprising selectively actuable slice means for executing the steps of

i) generating a tile-shape signal indicative of boundary-representative signals dividing the iteration space by a number of processing units allocated to said execution with respect to one of said indices and spanning the iteration space with respect to the others of those indices, wherein the number of respective tiles is equal to that a number of available processing units, wherein those tiles are substantially equal in size, and

ii) generating a tile-strategy signal indicative of generation of the respective tiles so as to cause one each of them to be executed by a respective one of the available processing units.

46. In a method according to claim 45, the further improvement comprising the step of actuating said slice means in instances in which

i) data subject to access during execution of any such tile does not depend on that modified during execution of any other such tile, and

ii) no substantial quantity of data subject to any of read-type and write-type access by one such tile is also subject to any of read-type and write-type access by another such tile.

47. In a method according to claim 45, the further improvement comprising means actuating said slice means in response to a user-supplied signal.

48. In a method according to claim 44, the further improvement comprising providing selectively actuable modulo means for executing the steps of

i) generating boundary-representative signals to divide the iteration space in fixed-length increments along all of said indices, and

ii) generating a tile-strategy signal indicative of assignment of the respective tiles based on a modulus of a numerical identifier associated with each of the available processing units and a numerical identifier associated with each of the tiles.

49. In a method according to claim 48, the further improvement comprising the steps of actuating said modulo means in instances in which

i) data subject to access during execution of any such tile does not depend on that modified during execution of any other such tile,

ii) no substantial quantity of data subject to any of read-type and write-type access by one such tile is also subject to any of read-type and write-type access by another such tile, and

iii) re-use of data subject to any of read-type or write-type access by a processing unit executing a plurality of tiles is maximized, even in the presence of a change of a size of said iteration space.

50. In method according to claim 48, the further improvement comprising actuating said modulo means in response to a user-supplied signal.

51. In a method according to claim 44, the further improvement comprising providing selectively actuable wavefront means for executing the steps of

i) generating boundary-representative signals dividing the iteration space along one or more of said indices, wherein data subject to access during execution of at least selected tiles depends on that modified during execution of another tile, and wherein those tiles have a dependency direction,

ii) generating a tile-strategy signal indicative of a sequence of generation of the respective tiles in accord with that dependency direction.

52. In a method according to claim 51, the further improvement wherein said tile-strategy means includes means for actuating said wavefront means wherein data subject to access during execution of at least one such tile depends on that modified during execution of another such tile.

53. In method according to claim 51, the further improvement comprising actuating said wavefront means in response to a user-supplied signal.

54. In a method according to claim 44, the further improvement comprising providing selectively actuable modulo/wavefront means for executing the steps of

i) generating boundary-representative signals to divide the iteration space in fixed-length increments along all of said indices, wherein data subject to access during execution of at least a selected tile depends on that modified during execution of one or more other tiles, and wherein said tiles have a dependency direction, and

ii) generating a tile-strategy signal indicative of assignment of the respective tiles based on a modulus of a numerical identifier associated with each of the available processing units and a numerical identifier associated with each of the tiles, and on that dependency direction.

55. In a method according to claim 54, the further improvement comprising the steps of actuating said modulo/wavefront means in instances in which

i) data subject to access during execution of at least one such tile depends on that modified during execution of one or more other such tiles, and

ii) re-use of data subject to any of read-type or write-type access by a processing unit executing a plurality of tiles is maximized, even in the presence of a change of a size of said iterative space.

56. In a method according to claim 54, the further improvement comprising means for actuating said modulo/wavefront means in response to a user-supplied signal.

57. In a method according to claim 44, the further improvement comprising providing selectively actuable grab means for

i) generating boundary-representative signals to divide the iteration space in fixed-length increments along all of said indices, and wherein data subject to access during execution of any tile does not depend on that modified during execution of any other tile, and

ii) generating a tile-strategy signal indicative of a sequence of generation of the respective tiles, in response to said signalling for availability by said processing units, on a first-come-first-serve basis.

58. In a method according to claim 57, the further improvement wherein said tile-strategy means includes means for actuating said grab means

i) to facilitate load-balancing among processing units executing said tiles, and in instances when

ii) no substantial quantity of data is subject to any of read-type and write-type access by one such tile is also subject to any of read-type and write-type access by another such tile.

59. In a method according to claim 57, the further improvement comprising actuating said wavefront means in response to a user-supplied signal.

60. In a method according to claim 37, the further improvement comprising the steps of

A. providing an affinity region signal representative of one or more iteration sequences that access the same data,

B. generating one or more of

i) a signal representative of an iteration space in which one or more tiled sequences within the affinity region are to be executed,

ii) a tile-shape signal representative of one or more dimensions of a boundary-representative signal,

iii) a tile-strategy signal indicative of at least one of a sequence and manner of assigning tiles to said processing units, and

iv) a team signal representative of a set of processing units by which the tiled sequences within the affinity region are to be executed to minimize a transfer of a data subject to any of read-type and write-type access during such execution.

61. In method according to claim 60, the further improvement wherein said affinity region-build means includes means for defining said iteration space to encompass one or more of the iteration spaces of the tile sequences in said affinity region.

62. In a method according to claim 37, the improvement comprising the step of generating said boundary-representative signals so as to maximize a locality of data subject to access during execution of one or more corresponding tiles, and to minimize concentration for access to such data during such execution.

63. In a method for operating a compiler of the type for translating program signals representative of a program, including an iterative sequence, in source code format into a code sequence of instructions in an object code format suitable for loading for execution by a plurality of parallel digital data processing units,

the improvement comprising the steps of

responding to said iterative sequence in source code format for generating a tiled sequence of instructions representative thereof in object code format, and

further responding to that iterative sequence and to zero, one or more user-specified signals for generating one or more signals representing a framework for generating boundaries for plural tiles over which said tiled sequence is to be executed by said plurality of parallel digital data processing units, each such tile comprising a portion less than a whole of an iteration space associated with said iterative sequence.

64. In a method according to claim 63, wherein said compiler includes dependency means for determining a dependency direction of said iterative sequence and for generating a signal representative thereof, the further improvement comprising responding to instructions in said iterative sequence and to said dependency direction-representative signal for generating signals representative of one or more indexes in said iteration space over which to execute said tiled sequence.

65. In a method according to claim 64, the further improvement comprising the steps of

A. accepting signals representative of a user-specified indexing of said iteration space, and

B. comparing said user-specified indexing signals with those generated by said method, and for generating a notification signal in the event of at least selected disagreement thereof.

66. In a method according to claim 64, the further improvement comprising generating one or more signals for use at runtime in optimizing parallel execution of said tiled sequence.

67. In a method according to claim 66, the further improvement comprising generating an affinity signal representative of a tile execution sequence that minimizes a transfer of data subject to any of read-type or write-type access during execution thereof in plural tiles.

68. In a method according to claim 66, the further improvement wherein said optimizing means comprises means for generating an affinity region signal representative of one or more iteration sequences that access the same data.

69. In a method according to claim 68, the further improvement comprising

A. accepting signals representative of a user-specified affinity region signal, and

B. comparing said user-specified affinity region signal with that generated by said method, and for generating a notification signal in the event of at least selected disagreement thereof.

70. In a method according to claim 66, the further improvement comprising generating a signal representative of an estimate of a processing cost associated with execution of said tiled sequence.

71. In a method according to claim 63, the improvement comprising replacing said iterative sequence in said source code format with an instruction representative of a call to a code-dispatching subroutine.

72. In a method according to claim 71, the improvement comprising executing said call-representative instruction for initiating execution of said tiled sequence by said processing units.

Description

BACKGROUND OF THE INVENTION

The invention relates to digital data processing and, more particularly, to methods and apparatus for executing programs on parallel processing computers.

Early computers typically relied on a single processing unit, or CPU, to perform processing functions. Source code programs written for those computers were translated into a sequence of machine instructions which were then executed one-by-one by the CPU. Where repetitive sequences of steps, or loops, existed in the original program, the single processor would take up each instruction in the loop, one at a time, and repeat those same instructions for each iteration of the loop.

A later advance made it possible to execute some sets of instructions "in parallel" with one another. This advance, referred to as co-processing, provided alongside the CPU a special purpose processor. Execution of programs on such a machine was thus divided between the coprocessor and the CPU.

With the advent of computers with multiple processors, it became possible to allocate entire tasks to separate concurrently operating CPU's. A special class of these multiprocessors, referred to as parallel processors, are equipped with special synchronizing mechanisms and thus are particularly suited for concurrently executing portions of the same program.

"Parallelizing" execution of computer programs so that they can be run efficiently on parallel processors is a daunting task. First, the data-flow and control-flow of the program must be understood and, then, rearranged to define a set clearly divisible tasks. The most significant gains attained to date have been in the rearrangement of loop execution, i.e., "loop interchange," synchronization and (to a limited degree) tiling.

Although much parallelization work is done by hand, recent inroads have been made into automating that task. This is typically performed in connection with the compilation process, which converts the source code program into machine code. One commercially available product, the KAP/KAI Preprocessor available from Kuck and Associates, Inc., of Illinois, performs some of these functions. Particularly, that preprocessor provides capabilities for loop interchange and synchronization.

In view of the foregoing, an object of this invention is to provide improved digital data processing apparatus and methods.

More particularly, an object is to provide an improved mechanism for executing programs on parallel processing computers, including those which are massively parallel.

Still another object is to provide an improved compiler for facilitating parallelization of computer programs.

Yet another object is to provide a computer run-time mechanism for parallelizing and executing a computer program on a multiprocessor system.

SUMMARY OF THE INVENTION

These objects are attained by the invention which provides an improved parallel processor for executing an iterative sequence of instructions by arranging the sequence into subtasks and allocating those to the processors. This division and allocation is conducted in such a manner as to minimize data contention among the processors and to maximize locality of data to the processors which access that data.

In one aspect, the invention provides an improved parallel processor of the type having a plurality of processing units, each for executing instructions; a memory for storing data and instructions; and a mechanism for facilitating communication between the processors. The memory can itself include a plurality of memory elements, each capable of storing data and instructions. The communication mechanism can be, for example, a signalling protocol using common areas of memory.

The improvement is characterized, in part, by storing a tiled sequence of instructions, representing the iterative sequence, in memory. Further, each processor signals its availability to execute a portion of the tiled sequence. Still further, a next-tile element responds to that signalling by generating a signal representing the boundaries of a "tile"--that is, a portion of an iteration space associated with the iterative sequence. The signalling processor then executes the tiled sequence over that tile.

The tiles generated by the next-tile element do not overlap one another; however, all the tiles together cover the iteration space. As noted above, these tiles are generated so as to minimize contention for data between the processors, while maximizing the locality of data to them.

A parallel processor as describe above can include a tile-builder that generates a tile-shape signal defining the dimensions within the iteration space of the tiles. For example, an iteration space may be defined by the indices (i) and (j); where (i) ranges from 1 to 100, and where (j) ranges from 1 to 25. A tile for such a space may be defined to cover 16 increments along (i) and 25 increments along (j). Thus, dividing the iteration space into 6 tiles of equal size (i.e., 16 increments), and one of smaller tile (i.e., of 4 increments) at the edge.

The tile-builder generates the tile-shape signal in view of the dependencies which will exist between the resultant tiles. Dependency in this regard is an inter-tile characteristic referring to the relationship between them with respect to the data they access so that the serial execution order is preserved whenever it matters. For example, if first tile must write a datum before it can be read by a second tile, then that second tile is said to depend on the first.

More particularly, data dependency exists between two tiles where

i) an instruction in the first tile writes a selected datum, which an instruction in the second tile subsequently reads,

ii) an instruction in the first tile reads a selected datum, which an instruction in the second tile that subsequently writes, or

iii) an instruction in the first tile writes a selected datum, which an instruction in the second tile also subsequently writes.

A more complete understanding of dependency itself may be obtained by reference to Wolfe, Optimizing Supercompilers for Supercomputers (The MIT Press, 1989).

The tile-builder optimizes, among other things, memory utilization. For example, it can choose a tile shape that minimizes the number of individual datum subject to write-type access by different ones of the tiles to minimize data movement. Further, to minimize contention, it can choose the tile shape that minimizes the number of individual datum subject to write-type access by plural concurrently-executing tiles.

In another aspect, the tile-builder of a parallel processor as described above generates an "affinity" signal (or "ssb") representing a sequence for tile execution that minimizes the transfer of a data between processors.

The tile shape is generated as a function of at least a dependency direction of the tiles; an affinity signal (ssb); an estimate of the cost (e.g., the number of machine cycles) of executing the tiles; the size of the iteration space; the number of processors available for execution of the tiled sequence; and whether the tiles lie within an "affinity region"--that is, a region of the program where the iteration space defined by a plurality of tile sequences, rather than by a single one.

In yet another aspect, a parallel processor according to the invention includes a tile-strategy element that selects a manner and sequence for generating tiles from among a set of strategies. The tile-strategy element generates a corresponding signal to which the next-tile element responds in producing tiles.

A "slice" strategy divides the iteration space by the number of available processors. One each of these tiles are assigned to a respective one of the processors. Thus, if there are 10 processors, there will be 10 tiles: the first tile will be assigned to the first processor, the second tile to the second processor, and so forth.

This strategy is chosen when there is no data dependency between the resultant tiles. As well as when there is little affinity between them--that is, when little data accessed (whether for reads or writes) by any one of them is also accessed by another.

A "modulo" strategy divides the iteration space into a number of tiles which can be greater than the number of available processors, and assigns the resulting tiles based on the modulus of the tile number. Thus, for example, if there are 3 available processors and 9 tiles, regardless of their timing of availability, the first processor will be assigned tiles 1, 4 and 7; the second processor, tiles 2, 5 and 8; and the third processor, tiles 3, 6 and 9

This strategy is also selected when there is no dependence and little affinity between the tiles. Additionally, the strategy is chosen where the resultant tiles and tile assignments will maximize the re-use of data by each of the processors, even if the size of the iteration space changes.

A "wavefront" strategy also divides the iteration space such that there can be more tiles than available processors. It is chosen where the resultant tiles exhibit data dependence and, accordingly, the tiles must be generated in a sequence determined by the dependency direction of the tiles.

By way of example, a first tile may be required to be executed before a second tile and a third tile. Under the wavefront strategy, even if three processors were simultaneously available to take those tiles, only one of them would be given a tile. Particularly, the first tile would be assigned for execution by one processor. Only when that completed could the second and third tiles be executed, relying on the results of execution of the first tile.

A modulo-wavefront strategy divides the iteration space and assigns the tiles in accord with both the modulo and wavefront strategies. This strategy is chosen where there is data dependence between the tiles and where data reuse by the processors can be maximized, again, even in the presence of a change of a size of the iterative space.

A grab strategy too divides the iteration space such that there are more tiles than available processors. The resultant tiles are assigned to requesting processors on a first-come-first-serve basis. Unlike the modulo and wavefront strategies, this strategy is employed where there is no dependence and little affinity between the tiles. It facilitates load-balancing between the processors.

In addition to the conditions discussed above, the tile strategy element can choose any of the foregoing strategies upon demand of the user.

A parallel processor as described above can include an affinity region-build element for defining an iteration space that includes more than one tiled sequence. In addition to generating a signal representing that region, this element can to generate a signal defining tile dimension; a signal defining a sequence and manner for generating tiles; and a signal defining which processors are to execute the tiles.

In yet another aspect, the invention provides an improved compiler of the type for translating a computer program into object code suitable for loading for execution by a plurality of parallel processors.

The improvement is characterized by a tiling element that generates a tiled sequence of instructions representing an iterative sequence in the source program. The tiling element also generates signals providing a framework for use in a parallel processor of the type described above for defining and generating tiles over which to execute the tiled sequence at run-time. In this regard, the tiling element is responsive to the iterative sequence, as well as to user-defined parameters.

In accord with this aspect of the invention, the tiling element can include a parallelizer responsive to the dependency direction of the iterative sequence, as well as to the sequence itself, for choosing indexes in the iteration space over which to execute the tiled sequence. The parallelizer can automatically choose the indices for tiling based on that. While the parallelizer can accept user-defined preferences for those indices, it compares them with the automatically identified ones to insure their viability.

A compiler as defined above can also include an optimizer for generating an affinity signal (ssb) representing a tile execution sequence that minimizes a transfer of data subject to any of read-type or write-type access during execution thereof in plural tiles.

The optimizer can also generate an affinity region signal identifying one or more iteration sequences in the source program that access the same data. While the optimizer too can accept user-defined affinity regions, it compares them with the automatically identified ones to check whether the user-defined regions are reasonable.

In another aspect, the optimizer can determine a cost associated with execution of a tiled sequence and generate a signal representative thereof.

A call-generating element within the compiler can replace the iterative sequence in the source code with an instruction representing a call to a code-dispatching subroutine. A run-time element can execute that call to initiate execution of the tiled sequence by the processors.

This and other aspects of the invention are evident in the drawings and in the description which follows.

BRIEF DESCRIPTION OF THE DRAWINGS

A more complete understanding of the invention may be attained by reference to the drawings, in which:

FIGS. 1 and 2 depict the structure of a multiprocessing system for use in a preferred practice of the invention;

FIG. 3 depicts the modules utilized for parallelization and execution of software programs including iterative sequences;

FIGS. 4A-4D depict loop tables generated by the preprocessor 60a of FIG. 3;

FIG. 5 presents preferred directives and assertions for preprocessor 60a of FIG. 3;

FIG. 6 depicts runtime environment parameters for use in execution of the system of FIG. 3;

FIG. 7 illustrates the transformation of a tile into a task-subroutine;

FIG. 8 depicts a partial tile ordering by the system of FIG. 3;

FIGS. 9A-9C depict work plans carried out by the system of FIG. 3 to execute a tiled sequence; and

FIG. 10 is a high level block-diagram of Runtime Library 66 of FIG. 3.

DETAILED DESCRIPTION OF THE ILLUSTRATED EMBODIMENT

FIG. 1 depicts a preferred multiprocessing system used to practice the invention. The illustrated system 10 includes three information transfer levels: level:0, level:1, and level:2. Each information transfer level includes one or more level segments, characterized by a bus element and a plurality of interface elements. Particularly, level:0 of the illustrated system 10 includes six segments, designated 12A, 12B, 12C, 12D, 12E and 12F, respectively. Similarly, level:1 includes segments 14A and 14B, while level:2 includes segment 16.

Each segment of level:0, i.e., segments 12A, 12B, . . . 12F, comprise a plurality of processing cells. For example, segment 12A includes cells 18A, 18B and 18C; segment 12B includes cells 18D, 18E and 18F; and so forth. Each of those cells include a central processing unit and a memory element, interconnected along an intracellular processor bus (not shown). In accord with the preferred practice of the invention, the memory element contained in each cells stores all control and data signals used by its associated central processing unit.

Certain cells of the processing system 10 are connected to secondary storage devices. In the illustrated system, for example, cell 18C is coupled with disk drive 19A, cell 18D is coupled with disk drive 19B, and cell 180 is coupled with disk drive 19C. The disk drives 19A-19C are of conventional design and can be selected from any of several commercially available devices. It will be appreciated that secondary storage devices other than disk drives, e.g., tape drives, can also be used to store information.

FIG. 2 illustrates in greater detail processing cells and their interconnection within the processing system of FIG. 1. In the drawing, plural central processing units 40A, 40B and 40C are coupled, respectively, to associated memory elements 42A, 42B and 42C. Communications between the processing and memory units of each pair are carried along buses 44A, 44B and 44C, as shown. Network 46, representing the aforementioned level segments and routing cells, transfers information packets (passed to the network 46 over buses 48A, 48B and 48C) between the illustrated processing cells 42A-42C.

In the illustrated embodiment, the central processing units 40A, 40B and 40C each include an access request element, labelled 50A, 50B and 50C, respectively. These access request elements generate requests for access to data stored in the memory elements 42A, 42B and 42C. Among access requests signals generated by elements 50A, 50B and 50C is the ownership-request, representing a request for exclusive, modification access to a datum stored in the memory elements. In a preferred embodiment, access request elements 50A, 50B and 50C comprise a subset of an instruction set implemented on CPU's 40A, 40B and 40C. This instruction subset is described below.

The central processing units 40A, 40B, 40C operate under control of an operating system 51, portions 51A, 51B and 51C of which are resident on respective ones of the central processing units. The operating system 51 provides an interface between applications programs executing on the central processing units and the system 10 facilities, and includes a virtual memory management system for managing data accesses and allocations.

A preferred operating system for controlling central processing units 40A, 40B and 40C is a UNIX-like operating system and, more preferably, OSF/1, modified in accord with the teachings herein.

The memory elements 40A, 40B and 40C include cache control units 52A, 52B and 52C respectively. Each of these cache control units interfaces a data storage area 54A, 54B and 54C via a corresponding directory element 56A, 56B and 56C, as shown. Stores 54A, 54B and 54C are utilized by the illustrated system to provide physical storage space for data and instruction signals needed by their respective central processing units.

A further appreciation of the structure and operation of the illustrated digital data processing system 10 may be attained by reference to the following copending, commonly assigned applications, the teachings of which are incorporated herein by reference:

1) U.S. patent application Ser. No. 07/136,930, filed Dec. 22, 1987, for "MULTIPROCESSOR DIGITAL DATA PROCESSING SYSTEM", now U.S. Pat. No. 5,055,999, Issued Oct. 8, 1991;

2) U.S. patent application Ser. No. 07/696,291, filed May 20, 1991, now U.S. Pat. No. 5,119,481, Issued Jun. 2, 1992;

3) U.S. patent application Ser. No. 07/370,325, filed Jun. 22, 1989, for "MULTIPROCESSOR SYSTEM WITH MULTIPLE INSTRUCTION SOURCES", abandoned May 21, 1993 in favor of U.S. patent application Ser. No. 066,334, filed May 21, 1993;

4) U.S. patent application Ser. No. 07/370,341, filed Jun. 22, 1989, for "IMPROVED MEMORY SYSTEM FOR A MULTIPROCESSOR", now U.S. Pat. No. 5,297,265;

5) U.S. patent application Ser. No. 07/370,287, filed Jun. 22, 1989, for "IMPROVED MULTIPROCESSOR SYSTEM", now U.S. Pat. No. 5,251,308, Issued Oct. 5, 1993;

6) U.S. patent application Ser. No. 07/499,182, filed Mar. 26, 1990, for "HIGH-SPEED PACKET SWITCHING APPARATUS AND METHOD", now U.S. Pat. No. 5,335,325;

7) U.S. patent application Ser. No. 07/521,798, filed May 10, 1990, for "DYNAMIC PACKET ROUTING NETWORK", now U.S. Pat. No. 5,282,201, Issued Jan. 25, 1994;

8) U.S. patent application Ser. No. 07/526,396, filed May 18, 1990, for "PACKET ROUTING SWITCH", now U.S. Pat. No. 5,226,039, Issued Jul. 6, 1993;

9) U.S. patent application Ser. No. 07/531,506, filed May 31, 1990, for "DYNAMIC HEIRARCHICAL ASSOCIATIVE MEMORY", now U.S. Pat. No. 5,341,483;

10) U.S. patent application Ser. No. 07/763,368, filed Sep. 20, 1991, for "DIGITAL DATA PROCESSOR WITH IMPROVED PAGING", now abandoned;

11) U.S. patent application Ser. No. 07/763,505, filed Sep. 20, 1991, for "DIGITAL DATA PROCESSOR WITH IMPROVED CHECKPOINTING & FORKING", issued as U.S. Pat. No. 5,313,647; and

12) U.S. patent application Ser. No. 07/763,132, filed Sep. 20, 1991, for "IMPROVED DIGITAL DATA PROCESSOR WITH DISTRIBUTED MEMORY SYSTEMS, now abandoned."

Code Parallelization & Execution

FIG. 3 depicts a preferred arrangement of software modules utilized in digital data processor for parallelization and execution of software programs including iterative sequences. A compilation system 60 translates source code input into object code. The source code can be of conventional format, e.g., Fortran 77 or Fortran 90, or C programming language source files, and typically includes iterative sequences or "loops." In addition to conventional programming statements, the source code can include user-specified directives for parallelization. Those directives are preferably provided as "comments," i.e., non-executable statements. To distinguish them from conventional comments (which are typically used as explanatory text) the directives preferably take a special format, as discussed further below.

The compilation system 60 includes a preprocessor 60a and a compiler 60b. The preprocessor 60a preforms preliminary analysis of iterative sequences in the source code to determine the dependency directions thereof, and performs certain loop interchanges. The preprocessor 60a also generates directives, of the type referred to above, for use by the compiler 60b. Techniques for dependency direction determination and loop interchanging are known. Modifications on those known techniques for improved parallelization of iterative sequences are described below.

The compiler 60b of the compilation system 60 translates program statements from the preprocessed source code format to object code format. In addition to translating conventional code, the compiler 60b converts iterative sequences in the preprocessed source code to "tiled" sequences for use in parallel execution. This procedure is referred to as "tiling" and is controlled, in part, by the directives generated by the preprocessor 60a, as well as those included in the source code 62 itself.

The object code output by the compilation system 60 is linked with a Runtime Library 66 by link editor 64 to produce code suitable for execution on the digital data processor 10.

Described below is a preferred preprocessor 60a. Although the techniques are applicable to a variety of software languages, such as the Fortran 77 or 90 and C programming languages, the discussion below concerns translation of Fortran 77 source code.

The techniques below can be adapted to operate in connection with previously known preprocessing systems--particularly, as adapted to determine the dependency direction of the source code iterative sequences in the manner described below. Such prior systems include the commercially available KAP/KAI preprocessor of Kuck and Associates, of Illinois, as well as preprocessors available from Pacific Sierra (e.g., the "Vast" preprocessor).

The Preprocessor

1. Overview

The main role of preprocessor 60a is to put annotations into a Fortran program that enable parallel execution; that is, to insert tiling directives. Preprocessor 60a also optionally performs some transformations of the code, such as loop interchanges, either to enable tiling or to optimize.

In the illustrated embodiment, the input to preprocessor 60a is a Fortran program source, and its primary output is also a Fortran program--albeit a "preprocessed" one--which includes the tiling directives. That second program is a valid and correct Fortran program, which when executed serially computes the same results as the original program. That second program is the input to the compiler 60b.

2. The Tiling Directives--Preprocessor Output

The tiling directives which preprocessor 60a puts into the code have the general form of:

    ______________________________________
            C*KSR* TILE(<tiling-args>)
            C*KSR* END TILE
    ______________________________________

    ______________________________________
    <tiling-args>:==<tile-index-list>
    [,<tiling-param>. . .]
    <tiling-param>:==<param-keyword> = <param-value>
    ______________________________________

    ______________________________________
    Syntax               Example
    ______________________________________
    order = <dep-list>   order=k
    lastvalue = (var-list>
                         smallest
    local = <var-list>   tmp or (t1, t2)
    reduction = <var-list>
                         sum
    ______________________________________

    ______________________________________
    C*KSR* TILE( <index>. . .
                     [,order = <dep-list>]
                     [,lastvalue=<variable-list>]
                     [,local=<variable-list)]
                     [,reduction=<variable-list>]
                     [,<extra-params>])
    . . .
    C*KSR* END TILE
    ______________________________________

    __________________________________________________________________________
    Formal syntax definition:
    __________________________________________________________________________
    <tiled-loop>
                is <tile-begin> <Fortran-do-loop> <tile-end>
    <tile-begin>
                is C*KSR* TILE ( <tiling-args>)
    <tile-end>  is C*KSR* TILE END
    <tiling-args>
                is <tile-index-list> [, <tiling-param-list>]
    <tile-index>
                is <loop-index-variable-name>
    <tiling-param>
                is ORDER    = <order-listing>
                or LASTVALUE
                            = <var-or-invelt-listing>
                or REDUCTION
                            = <var-or-invelt-listing>
                or PRIVATE  = <var-listing>
                or <extra-keyword>
                            = <easy-to-parse-string>
    <order-listing>
                is <order>
                or ( <order-list>)
    <order>     is [-] <loop-index-variable-name>
    <var-or-invelt-listing>
                is <var-or-invelt>
                or ( <var-or-invelt-list>)
    <var-or-invelt>
                is <a variable name or array element name;
                in the case of an array element name, all
                the subscript expressions must be
                invariant with respect to the tiled loop
                nest>
    <var-listing>
                is <var>
                or ( <var-list>)
    <var>       is <a variable name>
    <extra-keyword>
                is <a Fortran identifier>
    __________________________________________________________________________

    ______________________________________
    C*KSR* TILE ( <tile-index-list> [,<tiling-param>. . .] )
    ______________________________________

    ______________________________________
    do k = 1,n-1
    do j = k+1, n
    do i = 1, n-k
           a(k+i,j) = a(k+i,j) + t * a(k+i,k)
    enddo
    enddo
    enddo
    ______________________________________

    ______________________________________
    do k = 1, n
    C*KSR* TILE( J , I)
    DO 2 J=k+1,n-1
           DO 2 I=1,n-k
            A(K+I,J) = A(K+I,J) + T * A(K+I,K)
    2 CONTINUE
    C*KSR* END TILE
           enddo
    ______________________________________

    ______________________________________
    do i = 1,n
    do j = 1,m
    c(i,j) = 0
    do k = 1, l
           c(i,j) = c(i,j) + a(i,k) * b(k,j)
    enddo
    enddo
    enddo
    ______________________________________

    ______________________________________
    C*KSR* TILE (I,J)
    do i = 1,n
    do j = 1,m
    c(i,j) = 0
    do k = 1, l
           c(i,j) = c(i,j) + a(i,k) * b(k,j)
    enddo
    enddo
    enddo
    C*KSR* END TILE
    ______________________________________

    ______________________________________
           do 400 l = 1, nlev
            do 300 k = 1, nwaves
             ip = nmp(k)
              do 200 j = 1, nlats
               do 100 i = 1, nnp(k)
                sd(l,ip+i)=
                  sd(l,ip+i)+fsdl(l,k,j)*pnmd(ip+i)
                sq(l,ip+i)=
                  sq(l,ip+i)+fsql(l,k,j)*pnmd(ip+i)
           100      continue
           200     continue
           300    continue
           400   continue
    ______________________________________

    ______________________________________
    do 400 l = 1, nlev
    do 300 k = 1, nwaves
    do 200 j = 1, nlats
    do 100 i = 1, nnp(k)
    sd(l,nmp(k)+i)=
           sd(l,nmp(k)+i)+fsdl(l,k,j)*pnmd(nmp(k)+i)
    sq(l,nmp(k)+i)=
           sq(l,nmp(k)+i)+fsql(l,k,j)*pnmd(nmp(k)+i)
    100     continue
    200    continue
    300   continue
    400  continue
    ______________________________________

    ______________________________________
    C*KSR* TILE( L,K,J )
           do 400 l = 1, nlev
            do 300 k = 1, nwaves
             do 200 j = 1, nlats
              do 100 i = 1, nnp(k)
               sd(l,nmp(k)+i)=sd(l,nmp(k)+i)+
                 fsdl(l,k,j)*pnmd(nmp(k)+i)
               sq(l,nmp(k)+i)=sq(l,nmp(k)+i)+
                 fsql(l,k,j)*pnmd(nmp(k)+i)
    100          continue
    200         continue
    300        continue
    400       continue
    C*KSR* END TILE
    ______________________________________

    ______________________________________
    C*KSR* TILE (<tile-index-list> [, <tiling-param>
    . . .])
    ______________________________________

    ______________________________________
    c*KSR* TILE (<tile-index-list>
    [, <tiling-param>. . .])
    c*KSR* END TILE
    ______________________________________

    ______________________________________
    C*KSR* TILE (l,k)
    ______________________________________

    ______________________________________
    C*KSR* TILE (1,k)
    do 400 l = 1, nlev
    do 300 k = 1, nwaves
           ip = nimp(k)
           do 200 j = 1, nlats
            do 100 i = 1, nnp(k)
             sd(l,ip+i) = sd(l,ip+i) +
               fsdl(l,k,j)*pnmd(ip+i)
             sq(l,ip+i) = sq(l,ip+i) +
               fsql(l,k,j)*pnmd(ip+i)
    100          continue
    200         continue
    300        continue
    400       continue
    ______________________________________

    ______________________________________
    C*KSR* TILE( L,K )
    do 400 l = 1, nlev
    do 300 k = 1, nwaves
           do 200 i = 1, nlats
            do 100 i = 1, nnp(k)
             sd(.omega.,nmp(k)+i) = sd(.omega.,nmp(k)+i) +
               fsdl(.omega.,k,j)*pnmd(nmp(k)+i)
             sq(.omega.,nmp(k)+i) = sq(.omega.,nmp(k)+i) +
               fsql(.omega.,k,j)*pnmd(nmp(k)+i)
    100          continue
    200         continue
    300        continue
    400       continue
    C*KSR* END TILE
    ______________________________________

    ______________________________________
    C*KSR* TILE( L,K )
    do 400 l = 1, nlev
    do 300 k = 1, nwaves
           do 200 j = 1, nlats
            do 100 i = 1, nnp(k)
             sd(l,nmp(k)+i)=sd(l,nmp(k)+i)+
               fsdl(l,k,j)*pnmd(nmp(k)+i)
             sq(l,nmp(k)+i)=sq(l,nmp(k)+i)+
               fsql(l,k,j)*pnmd(nmp(k)+i)
    100          continue
    200         continue
    300        continue
    400       continue
    C*KSR* END TILE
    ______________________________________

    ______________________________________
             C*KSR* TILE ( i, j)
                do 10 i = 1,n
                do 10 j = 1,m
                  a(i, j) = 0.0
              10 continue
             C*KSR* END TILE
    ______________________________________

    ______________________________________
             C*KSR* TILE ( i )
                do 10 i = 1,n
                do 10 i = 1,m
                  a(i,j) = 0.0
              10 continue
             C*KSR* END TILE
    ______________________________________

    ______________________________________
    C*KSR* AFFINITY REGION ( i,j, STRATEGY = MOD,
    NUMTHREADS = 8)
    do k
    C*KSR* TILE ( i,j)
    do i
    do j
           . . . .
    enddo
    enddo
    C*KSR* END TILE ( i,j,)
    enddo
    C*KSR* END AFFINITY REGION
    ______________________________________

    ______________________________________
                do 10 i=1,n
                do 10 j=1,n
    ______________________________________

    ______________________________________
                do 10 i=i1,i2
                do 10 j=j1,j2
    ______________________________________

    ______________________________________
                do 10 i=32, 47
                do 10 j=16, 31
                a(i,j) = 0.0
              10 continue
    ______________________________________

    ______________________________________
    do 10 i = 2,n-1
    do 10 j = 2,m-1
     a(i,j) = a( i-1 , j+1 ) + a ( i+1 , j-1)
    10 continue
    ______________________________________

    ______________________________________
    C*KSR* TILE ( i, j, ORDER = -J, I )
             do 10 i = 2,n-1
             do 10 j = 2,m-1
              a(i,j) = a(i-1,j+1) + a(i+1,j-1)
            10 continue
    C*KSR* END TILE
    ______________________________________

    ______________________________________
    do 10 i = 1,n
    do 10 i = 1,m
      a(i,j) = a(i-1, j+1) + a (i+1, j-1)
    10 continue
    ______________________________________

    ______________________________________
    C*KSR* TILE ( I,J,ORDER=( -J , I ))
    ______________________________________

    ______________________________________
                do i = 1, 100
                  do j = 1, 200
    ______________________________________

    ______________________________________
    (x) = don't care
                             User
                             Spec'ed
                             tile
           Number            size cuts
    User   of       User     n
    Spec'ed
           Indices  Spec'ed  ordered
                                    Chosen
    Strategy
           w/Order  tile size
                             indices
                                    strategy
    ______________________________________
    FALSE  0        x        x      MODULO/SLICE
    FALSE  1        FALSE    x      MODULO/SLICE
    FALSE  1        TRUE     0      MODULO/SLICE
    FALSE  1        TRUE     1      WAVEFRONT
    FALSE  >=2      FALSE    x      WAVEFRONT
    FALSE  >=2      TRUE     0      MODULO/SLICE:q
    FALSE  >=2      TRUE     1-2    WAVEFRONT
    FALSE  >=2      TRUE     >2     Error reported
    TRUE   0        x        x      User specified
                                    strategy
    TRUE   1        FALSE    x      User specified
                                    strategy
    TRUE   1        TRUE     0      User specified
                                    strategy
    TRUE   1        TRUE     1      Error if user
                                    strategy!=
                                    WAVEFRONT
    TRUE   >=2      FALSE    x      Error if user
                                    strategy!=
                                    WAVEFRONT
    TRUE   >=2      TRUE     0      User specified
                                    strategy
    TRUE   >=2      TRUE     1-2    Error if user
                                    strategy!=
                                    WAVEFRONT
    TRUE   >=2      TRUE     >2     Error reported
    ______________________________________

    ______________________________________
    tile-number MODULO number-of-allocated-
    threads = thread-id
    ______________________________________

    ______________________________________
    number of processors:
                         N
    tile-size:           a whole column
    strategy:            modulo
    ______________________________________

    ______________________________________
    number of processors:
                        N
    tile-size:          chunks of column
    strategy:           wavefront
    ______________________________________

    ______________________________________
    number of processor:   N
    tile-size:             columns
    strategy:              GRAB
    ______________________________________