Patent
1998-03-27
2000-06-20
Elmore, Reba I.
395707, G06F 1206
Patent
active
060787457
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.
REFERENCES:
patent: 5794049 (1998-08-01), Lindholm
patent: 5805863 (1998-09-01), Chang
patent: 5848275 (1998-12-01), Maydan et al.
patent: 5872990 (1999-02-01), Luick et al.
patent: 5875340 (1999-02-01), Quarnstrom et al.
Lefebvre, Vincent, et al., "Storage Management in Parallel Programs," 5th Euromicor Workshop on Parrellel & Distributed Processing, pp. 1-8, Jan. 1997.
Feautrier, Paul, "Dataflow Analysis of Array and Scalar References," International Journal of Parallel Programming, 20(1), pp. 23-53, 1991.
Polychronopoulos, Constantine D., "Compiler Optimizations for Enhancing Parallelism and Their Impact on Architecture Design," IEEE Transactions on Computers, 37(8), pp. 991-1004, Aug. 1988.
Li, Wei, et al., "A Singular Loop Transformation Framework Based on Non-singular Matrices," Proceedings of the Fifth Annual Workshop on Language and Compilers for Parallelism, pp. 1-22, Aug. 1992.
Weijia, Shang, et al., "Generalized Cycle Shrinking," Algorithms and Parallel VLSI Architectures II, pp. 131-144, 1992.
Swaaij, Michael F.X.B. van, et al., "Automating High Level Control Flow Transformations For DSP Memory Management," Proceedings of the IEEE Workshop on VLSI Signal Processing, 11 pages, Oct. 1992.
Darte, Alain, et al., "Loop nest scheduling and transformations," Advances in Parallel Computing 6, pp. 1-24, 1993.
Lengauer, Christian, "Loop Parallelization in the Polytope Model," Proceedings of the Fourth International Conference on Concurrency Theory (CONCUR93), pp. 1-19, Aug. 1993.
Franssen, Frank H.M., et al., "Modeling Piece-wise Linear and Data dependent Signal Indexing for Multi-dimensional Signal Processing," Proceedings of the Sixth ACM/IEEE International Workshop on High Level Synthesis, pp. 245-255, Nov. 1992.
Balasa, Florin, et al., "Transformation of Nested Loops with Modulo Indexing to Affine Recurrences," Parrellel Processing Letters, 4(3), pp. 1-12, Dec. 1994.
Wilde, Dorna, et al., "Memory Reuse Analysis in the Polyhedral Model," Proceedings of Euro-Par '96, pp. 389-397, Aug. 1996.
Mumcuoglu et al. Accurate Geometric and Physical Response Modeling for Statistical Image Reconstruction in High Resolution PET. Nov. 1996. p. 1569-73. IEEE.
Catthoor Francky
De Greef Eddy
De Man Hugo
Elmore Reba I.
Siemens AG
LandOfFree
Method and apparatus for size optimization of storage units does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for size optimization of storage units, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for size optimization of storage units will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1861164