Patent
1996-05-15
1998-04-21
Amsbury, Wayne
395615, 395709, G06F 1730
Patent
active
057428140
ABSTRACT:
Data storage and transfer cost is responsible for a large amount of the VLSI system realization cost in terms of area and power consumption for real-time multi-dimensional signal processing applications. Applications or this type are data-dominated because they handle a large amount of indexed data which are produced and consumed in the context of nested loops. This important application domain includes the majority of speech, video, image, and graphic processing (multi-media in general) and end-user telecom applications. The present invention relates to the automated allocation of the background memory units, necessary to store the large multi-dimensional signals. In order to handle both procedural and nonprocedural specification, the novel memory allocation methodology is based on an optimization process driven by data-flow analysis. This steering mechanism allows more exploration freedom than the more restricted scheduling-based investigation in the existent synthesis systems. Moreover, by means of an original polyhedral model of data-flow analysis, the novel allocation methodology can accurately deal with complex specifications, containing large multi-dimensional signals. The class of specifications handled by this polyhedral model covers a larger range than the conventional ones, i.e. the entire class of affine representations. Employing estimated silicon area or power consumption costs yielded by recent models for on-chip memories, the novel allocation methodology produces one, or optionally, several distributed multi-port memory architecture(s) with fully-determined characteristics, complying with a given clock cycle budget for memory operations.
REFERENCES:
patent: 4964063 (1990-10-01), Esch
patent: 5327561 (1994-07-01), Choi et al.
patent: 5454104 (1995-09-01), Steidlmayer et al.
patent: 5485616 (1996-01-01), Burke et al.
patent: 5553285 (1996-09-01), Krakauer et al.
patent: 5664109 (1997-09-01), Johnson et al.
"Allocation of Multiport Memories in Data Path Synthesis," Balakrishnan, et al., IEEE Trans. on Comp-Aided Design, vol. CAD-7, No. 4, pp. 536-540, Apr. 1988.
"Exact Evaluation of Memory Size for Multi-Dimensional Signal Processing Systems," Balasa, et al., Proc. IEEE Int. Conf. Comp-Aided Design, pp. 669-672, Nov. 1993.
"Transformation of Nested Loops with Module Indexing to Affine Recurrences," Balasa, et al., Parallel Processing L., vol. 4, No. 3, pp. 271-280, Dec. 1994.
"Background Memory Allocation in Multidimensional Signal Processing," Balasa, F., Ph.D. thesis, IMEC, Nov. 1995.
"Background Memory Area Estimation for Multidimensional Signal Processing Systems," Balasa, et al., IEEE Transactions on Very Large Scale Integration (VLSI) Systems , vol. 3, No. 2, pp. 157-172, 1995.
"Automatic Program Parallelization," Banerjee, et al., Proc. of the IEEE, vol. 81, No. 2, 1993.
"The Indefinite Zero-One Quadratic Problem," Carter, M.W., Discrete Applied Math. vol. 7, pp. 23-33, 1984.
"Integer Programming by Implicit Enumberation and Balas' Method," Arthur M. Geoffrion, Siam Review, vol. 9, No. 2, pp. 178-190, 1967.
"Fourier-Motzkin Elimination and its Dual," Dantizig, et al., J. of Combinatorial Theory (A), vol. 14, pp. 288-297, Aug. 1993.
"Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program," Glover, et al., Operations Research, vol. 22, No. 1, pp. 180-182, Jan. 1974.
"SMASH: A Program for Scheduling Memory-Intensive Application-Specific Hardware," Gupta, et al., Proc. 7th International Symposium on High Level Synthesis, May 1994.
"REAL: A Program for Register Allocation," Kurdahi, et al., Proc. 24th SCM/IEEE Design Automation Conference, pp. 210-215, Jun. 1987.
"Allocation of Multiport Memories for Hierarchical Data Streams," Lippens, et al., IEEE, 1993.
"PHIDEO: A Silicon Compiler for High Speed Algorithms," Lippens, et al., Proc. European Design Automation Conference, pp. 436-441, Feb. 1991.
"An Area Model for On-Chip Memories and its Application," Mulder, et al., IEEE J. Solid-State Circ., vol. SC-26, No. 2, pp. 98-105, Feb. 1991.
"Calculation of Minimum Number of Registers in Arbitrary Life Time Chart," Parhi, K.K., IEEE Trans. on Circuits and Systems II: Analog and Digital Signal Processing, vol. 41, No. 6, pp. 434-436, Jun. 1994.
"A Practical Algorithm for Exact Array Dependance Analysis," Pugh, W., Comm. of the ACM, vol. 35, No. 8, Aug. 1992.
"Accurate Layout Area and Delay Modeling for System Level Design," Ramachandran, et al., Proc. IEEE Int. Conf. Comp.-Aided Design, pp. 355-361, Nov. 1992.
"A New Method for the Minimization of Memory Area in High Level Synthesis," Rouzeyre, et al., Proc. Euro-ASIC Conf., pp. 184-189, May 1991.
"Foreground Memory Management in Data Path Synthesis," Stok, et al., Int. Journal on Circuit theory and Application, vol. 20, pp. 235-255, 1992.
"A Balasian-Based Algorithm for Zero-One Polynomial Programming," Taha, H.A., Management Science, Vo. 18, No. 6, pp. 328-343, Feb. 1972.
"Memory Estimation for High Level Synthesis," Verbauwhede, et al., Proc. 31st Design Automation Conference, pp. 143-148, Jun. 1994.
"Register Allocation and Assignment," Aho, et al., Compilers: Principles, Techniques, and Tools, pp. 540-546, 1986.
"Post-Processor for Data Path Synthesis Using Multiport Memories," Ahmad, et al., IEEE, pp. 276-279, 1991.
"DSP Specification Using the Silage Language," Genin, et al., IEEE, pp. 1057-1060, 1990.
"The Mimola Design System: Tools for the Design of Digital Processors," Peter Marwedel, IEEE, pp. 587-593, 1984.
"Synthesis of Intermediate Memories for the Data Supply to Processor Arrays," Schonfeld, et al., Algorithms andparallel VLSI Architectures II, pp. 365-370, 1992.
"Automated Synthesis of Data Paths in Digital Systems," Tseng, et al., IEEE, pp. 379-395, 1986.
"Architecture-Driven Synthesis Techniques for VLSI Implementation of DSP Algorithms," De Man, et al., IEEE, pp. 319-335, 1990.
"Modeling Data Flow and Control Flow for DSP System Synthesis," Swaaij, et al., IMEC, pp. 219-259.
"Line Search Without Using Derivatives," Bazaraa, et al., Non Linear Programming Theory and Algorithms, 267-281, 1993.
"Optimisation of Global Communication and Memory Organization for Decreased Size and Power in Fixed Rate Processing Systems," Catthor, et al., IMEC, pp. 1-14, 1995.
Balasa Florin
Catthoor Francky
De Man Hugo
Amsbury Wayne
IMEC vzw
LandOfFree
Background memory allocation for multi-dimensional signal proces does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Background memory allocation for multi-dimensional signal proces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Background memory allocation for multi-dimensional signal proces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2068220