 |
|
|
|
|
|
 Title: |
US5742814:
Background memory allocation for multi-dimensional signal processing
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Balasa, Florin; Tustin Ranch, CA
Catthoor, Francky; Temse, Belgium
De Man, Hugo; Kessel-lo, Belgium
|
| Assignee: |
IMEC vzw, Leuven, Belgium
other patents from INTERUNIVERSITAIR MICRO-ELEKTRONICA CENTRUM (IMEC VZW) (749624) (approx. 301)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-04-21
/ 1996-05-15
|
| Application Number: |
US1996000649903
|
| IPC Code: |
Advanced:
G06F 9/50;
H04N 7/26;
Core:
G06F 9/46;
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F9/50A2M; H04N7/26L4;
|
| U.S. Class: |
Current:
707/102;
375/E07.1;
707/104.1;
717/155;
Original:
395/613;
395/615;
395/709;
|
| Field of Search: |
395/006,70
|
| Priority Number: |
| 1996-05-15 |
US1996000649903 |
| 1995-11-06 |
US1995000007288 |
| 1995-11-01 |
US1995000007160P |
|
| 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.
|
| Attorney, Agent or Firm: |
Knobbe, Martens, Olson & Bear, LLP ;
|
| Primary / Asst. Examiners: |
Amsbury, Wayne;
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 46 claims |
What is claimed:
1. A method of generating a data-flow graph representative of data to be stored in a data-dominated processing system, comprising the steps of:
- partitioning a plurality of linearly bounded lattices representative of data into partitioned linearly bounded lattices comprising basic sets and disjoint linearly bounded lattices;
- deriving a plurality of dependency relations between the partitioned linearly bounded lattices; and
- constructing a data-flow graph having a plurality of nodes, each node representing one of the partitioned linearly bounded lattices, and a plurality of arcs, each arc representing one of the dependency relations.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 29 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G1998-260882
DERABS G1998-260882
|
| Other References: |
"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.
(5 pages)
"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.
(16 pages)
[ISI abstract]
"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.
(22 pages)
"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.
(3 pages)
"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.
(9 pages)
Cited by 2 patents
[ISI abstract]
"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.
(3 pages)
[ISI abstract]
"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.
(21 pages)
[ISI abstract]
"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.
(17 pages)
Cited by 3 patents
"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.
|
|
 Nominate this for the Gallery...
|
|
