Method and apparatus for size optimization of storage units

• US 6,078,745 A
• Filed: 03/27/1998
• Issued: 06/20/2000
• Est. Priority Date: 03/29/1997
• Status: Expired due to Term

• Current Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International), Infineon Technologies AG
• Original Assignee: Siemens AG
• Inventors: De Greef, Eddy, Catthoor, Francky, De Man, Hugo
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US09/049,699
• Time in Patent Office: 816 Days
• Field of Search: 395/705, 395/709
• US Class Current: 717/151
• CPC Class Codes: G06F 8/4434 Reducing the memory space required by the program code

Abstract

The present invention provides a method and an apparatus for reducing the storage size required for temporary data by storage order optimization. Advantageously, the execution order optimization and the storage order optimization may be treated independently. The storage size optimization is preferably performed by determining an optimum intra-array and/or inter-array storage order based on a geometrical model. The geometrical model provides a representation of the address space occupied by an array as a function of time and allows the calculation of the window size of the occupied address/time domain of the array. Where calculations would be time-consuming, these may be shortened by making simplifying assumptions, e.g. calculation of upper and lower bounds of the window size of the occupied address/time domain of an array rather than an exact calculation. Further, heuristical simplifications are described to reduce run-times for the optimization process.

Claims

1. A method for optimizing before run-time the size of a storage unit for storing temporary data, comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometric model, wherein the intra-structure optimizing also includes selecting an at least piecewise affine storage order for the first data structure.

2. The method of claim 1, wherein each of said data structures occupy abstract addresses, and the abstract addresses occupied by a data structure at each time over a period of time is called the occupied address/time domain of that data structure and calculation of the window size of the first data structure includes calculating the maximum distance in address space between two abstract addresses in the occupied address/time domain of the first data structure.

3. The method of claim 2, wherein the occupied address/time domain of the first data structure includes a plurality of value based flow dependencies and the calculating the window size of that data structure includes calculating the window size of each pair of dependencies and selecting the window size for the first data structure from the pair of dependencies which generates the maximum window size.

4. The method of claim 1, further comprising:

selecting the intra-structure storage order for the first data structure which provides the minimum window size of the relevant data structure, and wherein the data structures has a plurality of dimensions and each dimension may have a storage order in at least one direction and the selecting the minimum window size includes determining upper and lower bounds of the window size for the relevant data structure when the position in the storage order and the storage order direction of a limited number of the dimensions are fixed.

5. The method of claim 4, wherein the determining includes:

calculating the upper and lower bounds of the window size for each direction/dimension combination generated by fixing one combination of one of the plurality of dimensions and one direction in turn;

discarding direction/dimension combinations which cannot lead to an optimum solution;

for each of the selected dimension/direction combinations calculating the upper and lower bounds of the window size for each of the direction/dimension combinations generated by fixing one further combination of one of the plurality of dimensions and one direction in turn;

discarding direction/dimension combinations which cannot lead to an optimum solution; and

repeating the above until all dimensions and directions are fixed.

6. The method of claim 5, wherein the discarding processes include discarding all direction/dimension combinations except the one which gives the smallest upper bound.

7. A method for optimizing before run-time the size of a storage unit for storing temporary data, comprising:

loading into a compiler a definition of at least a first data structure and a second data structure and execution commands, at least one of the execution commands requiring access to at least one of the first and second data structures;

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including inter-structure optimizing which optimizes an inter-structure storage order between the first and second data structures, the inter-structure optimizing being based on a geometric model;

intra-structure optimizing which independently optimizes an intra-structure storage order within each of the first and second data structures to form an abstract address equation for each data structure the intra-structure optimizing being based on a geometric model;

using the abstract address equations in the inter-structure optimizing.

8. The method of claim 7, wherein the inter-structure optimizing includes placement optimizing the placing of data structures in the storage unit to minimize the maximum distance in address space between two addresses being occupied at the same time but not necessarily in the same data structure.

9. The method of claim 8, wherein the abstract addresses occupied by a data structure at the same time over a period of time is called the occupied address/time domain of that data structure and the placement optimizing includes rearranging the occupied address/time domains within the address space without collisions, calculating a common window size for each arrangement of occupied address/time domains and selecting the arrangement with the minimum common window size.

10. The method of claim 9, further comprising calculating rectangular bounds for each occupied address/time domain and rearranging, the rectangular bounds within the address space to determine the minimum common window of the rectangular bounds.

11. The method of claim 9, wherein the folded occupied address/time domain is used instead of the occupied address/time domain of each data structure.

12. A compiler, comprising:

means for loading a definition of at least a first data structure and a second data structure and execution commands, at least one of the execution commands requiring access to at least one of the first and second data structures;

means for reducing the storage size of the temporary data required for the execution of the commands with a substantially given execution order, the reducing means including means for optimizing an inter-structure storage order between the first and second data structures, the inter-structure optimizing means being adapted to carry out the optimization based on a geometrical model, wherein the inter-structure optimizing means includes means for selecting the intra-structure storage order for at least one data structure which provides the minimum window size of the relevant data structure, and the data structures have a plurality of dimensions and each dimension may have a storage order in at least one direction and the selecting means includes means for determining upper and lower bounds of the window size for the relevant data structure and for fixing the position in the storage order and the storage order direction of a limited number of the dimensions.

13. The compiler of claim 12, wherein the inter-stricture optimizing means includes means for the placing of data structures in the storage unit to minimize the maximum distance between two addresses in address space being occupied at the same time but not necessarily in the same data structure.

14. The compiler of claim 13, wherein the abstract addresses occupied by a data structure at the same time over a period of time is called the occupied address/time domain of that data structure and the placement means includes means for rearranging the occupied address/time domains within the address space without collisions, means for calculating a common window size for each arrangement of occupied address/time domains and means for selecting the arrangement with the minimum common window size.

15. The compiler of claim 12, further comprising means for independently optimizing an intra-structure storage order within each of the first and second data structures based on a geometrical model to form an abstract address equation for each data structure.

16. A compiler, comprising:

means for loading execution commands and a definition of at least one data structure, at least one of the execution commands requiring access to at least one data structure; and

means for reducing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the reducing means including intra-structure optimizing means for optimizing an intra-structure storage order at least within the one data structure, the intra-structure optimizing means including means for calculating a window size for the one data structure, the intra-structure optimizing being based on a geometric model, wherein the at least one data structure occupies abstract addresses, and the abstract addresses occupied by the at least one data structure at each time over a period of time is called the occupied address/time domain of the data structure and the calculation means is adapted to calculate the maximum distance in address space between two abstract addresses in the occupied address/time domain.

17. The compiler of claim 16, wherein the occupied address/time domain of a data structure includes a plurality of value based flow dependencies and the calculating means is adapted to calculate the window size of each pair of dependencies and to select the window size for the data structure from the pair of dependencies which generates the maximum window size.

18. The compiler of claim 16, wherein the data structure has a plurality of dimensions and each dimension may have a storage order in at least one direction, the calculating means including means for fixing the position in the storage order and the storage order direction of a limited number of the dimensions and for then determining upper and lower bounds of the window size for the data structure.

19. A program storage device storing instructions that when executed by a computer perform the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model, wherein the intra-structure optimizing also includes selecting an at least piecewise affine storage order for the first data structure.

20. A program storage device storing instructions that when executed by a computer perform the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model, wherein the intra-structure optimizing which independently optimizes an intra-structure storage order within each of the first and second data structures forms an abstract address equation for each data structure, the intra-structure optimizing being based on a geometrical model; and

using the abstract address equations in inter-structure optimizing.

21. A program storage device storing instructions that when executed by a computer perform the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure;

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model; and

selecting an intra-structure storage order for at least one data structure which provides the minimum window size of the first data structure, and the at least one data structure has a plurality of dimensions and each dimension may have a storage order in at least one direction and the selecting includes determining upper and lower bounds of the window size for the at least one data structure and for fixing the position in the storage order and the storage order direction of a limited number of the dimensions.

22. A program storage device storing instructions that when executed by a computer perform the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model, wherein the abstract addresses occupied by the first data structure at each time over a period of time is called the occupied address/time domain of the first data structure and the calculation means is adapted to calculate the maximum distance in address space between two abstract addresses in the occupied address/time domain.

23. An executable computer program, wherein the size of a storage unit for storing temporary data of the computer program was optimized before run-time by the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure used by computer program, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model, wherein the intra-structure optimizing also includes selecting an at least piecewise affine storage order for the first data structure.

24. An executable computer program, wherein the size of a storage unit for storing temporary data of the computer program was optimized before run-time by the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure used by computer program, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model, wherein the inter-structure optimizing means includes means for selecting the intra-structure storage order for at least one data structure which provides the minimum window size of the relevant data structure, and the data structures have a plurality of dimensions and each dimension may have a storage order in at least one direction and the selecting means includes means for determining upper and lower bounds of the window size for the relevant data structure and for fixing the position in the storage order and the storage order direction of a limited number of the dimensions.

25. An executable computer program, wherein the size of a storage unit for storing temporary data of the computer program was optimized before run-time by the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure used by computer program, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometrical model, wherein the first data structure occupies abstract addresses, and the abstract addresses occupied by the first data structure at each time over a period of time is called the occupied address/time domain of the data structure and the calculation means is adapted to calculate the maximum distance in address space between two abstract addresses in the occupied address/time domain.

26. A method for optimizing before run-time the size of a storage unit for storing temporary data, comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including intra-structure optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing being based on a geometric model.

27. A method for optimizing before run-time the size of a storage unit for storing temporary data, comprising:

loading into a compiler a definition of at least a first data structure and a second data structure and execution commands, at least one of the execution commands requiring access to at least one of the first and second data structures; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the storage size optimizing including inter-structure optimizing which optimizes an inter-structure storage order between the first and second data structures, the inter-structure optimizing being based on a geometric model.

28. A compiler, comprising:

means for loading a definition of at least a first data structure and a second data structure and execution commands, at least one of the execution commands requiring access to at least one of the first and second data structures; and

means for reducing the storage size of the temporary data required for the execution of the commands with a substantially given execution order, the reducing means including means for optimizing an inter-structure storage order between the first and second data structures, the inter-structure optimizing means being adapted to carry out the optimization based on a geometrical model.

29. A compiler, comprising:

means for loading execution commands and a definition of at least one data structure, at least one of the execution commands requiring access to at least one data structure; and

means for reducing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the reducing means including intra-structure optimizing means for optimizing an intra-structure storage order at least within the one data structure, the intra-structure optimizing means including means for calculating a window size for the one data structure, the intra-structure optimizing being based on a geometric model.

30. A program storage device storing instructions that when executed by a computer perform the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the optimizing step including an intra-structure optimizing step for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing step being based on a geometrical model.

31. An executable computer program, wherein the size of a storage unit for storing temporary data of the computer program was optimized before run-time by the method comprising:

loading into a compiler execution commands and a definition of at least a first data structure used by computer program, at least one of the execution commands requiring access to the at least first data structure; and

optimizing the storage size of the temporary data in the storage unit required for the execution of the commands with a substantially given execution order, the optimizing step including an intra-structure optimizing step for optimizing an intra-structure storage order at least within the first data structure and the optimizing including calculating a window size for the first data structure, the intra-structure optimizing step being based on a geometrical model.