US5742814A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Background memory allocation for multi-dimensional signal processing
Assignee: Imec
•
Filing: 1996-05-15
•
Granted: 1998-04-21
•
Expires: 2016-05-15
Abstract
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.
Inventors
- 👤 Florin Balasa
- 👤 Francky Catthoor
- 👤 Hugo De Man
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:12
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5011; G06F9/5016; H; H04; H04N; H04N19/00; H04N19/42; H04N19/43; Y; Y02; Y02D; Y02D10/00; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
90 words
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.
Claim 2
Independent Claim
90 words
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.
Claim 3
Dependent Claim
40 words
The method of claim 1, additionally comprising the steps of: extracting dependencies between the definition and operand domains from a behavioral specification of the processing system; and representing the domains as linearly bounded lattices and the dependencies as dependency relations.
Claim 4
Dependent Claim
21 words
The method of claim 1, wherein each arc includes a weight indicative of the number of dependency relations between connecting nodes.
Claim 5
Dependent Claim
13 words
The method of claim 1, wherein the data-flow graph comprises a polyhedral graph.
Claim 6
Dependent Claim
25 words
The method of claim 1, wherein the processing system includes nests of loops, the boundaries of each loop comprising affine functions of surrounding loop iterators.
Claim 7
Dependent Claim
26 words
The method of claim 1, wherein the processing system includes nests of loops, the signal indices of each loop comprising affine functions of surrounding loop iterators.
Claim 8
Dependent Claim
16 words
The method of claim 1, wherein the data-dominated processing system comprises a multi-dimensional signal processing system.
Claim 9
Dependent Claim
20 words
The method of claim 1, wherein the data-flow graph provides storage information for memory in an application specific integrated circuit.
Claim 10
Dependent Claim
21 words
The method of claim 1, wherein the data-flow graph provides storage information for a data cache memory in a predefined processor.
Claim 11
Dependent Claim
16 words
The method of claim 1, wherein the data-flow graph provides storage information for a non-electronic storage.
Claim 12
Dependent Claim
16 words
The method of claim 1, wherein the data-dominated processing system is represented by a behavioral specification.
Claim 13
Dependent Claim
13 words
The method of claim 11, wherein the behavioral specification comprises a nonprocedural specification.
Claim 14
Dependent Claim
14 words
The method of claim 11, wherein the behavioral specification comprises a single assignment form.
Claim 15
Dependent Claim
71 words
The method of claim 1, wherein the behavior of the data-dominated system is specified by manifest iterator bounds and indices, and wherein the partitioning step comprises the steps of: determining the size of each linearly bounded lattice; constructing an inclusion graph based on the presence of intersections between the linearly bounded lattices; and extracting the basic sets from the inclusion graph based on the determined sizes of the linearly bounded lattices.
Claim 16
Dependent Claim
24 words
The method of claim 1, wherein the deriving step includes the step of determining the number of dependencies between the partitioned linearly bounded lattices.
Claim 17
Dependent Claim
19 words
The method of claim 1, additionally comprising the step of modifying the data-flow graph to allow for delayed data.
Claim 18
Independent Claim
175 words
A method of analyzing the data-flow in a behavioral specification for a data-dominated processing system, wherein the system is specified with manifest iterator bounds and indices, comprising the steps of: representing the index space of the domains as a plurality of linearly bounded lattices; partitioning the linearly bounded lattices into a plurality of basic sets, the partitioning step comprising the steps of constructing inclusion graphs based on the presence of intersections between the lattices, and deriving the basic sets based on the inclusion graphs and the size computation of linearly bounded lattices; deriving the number of dependencies between the basic sets based on the dependence relations between the lattices; and constructing a weighted directed graph, representing the data-flow, each node in the graph representing one of the basic sets, each node weight in the graph representing the size of the one basic set, each arc of the graph representing a dependence relation between two of the basic sets, each arc weight of the graph representing the number of dependence relations between the two basic sets.
Claim 19
Independent Claim
175 words
A method of analyzing the data-flow in a behavioral specification for a data-dominated processing system, wherein the system is specified with manifest iterator bounds and indices, comprising the steps of: representing the index space of the domains as a plurality of linearly bounded lattices; partitioning the linearly bounded lattices into a plurality of basic sets, the partitioning step comprising the steps of constructing inclusion graphs based on the presence of intersections between the lattices, and deriving the basic sets based on the inclusion graphs and the size computation of linearly bounded lattices; deriving the number of dependencies between the basic sets based on the dependence relations between the lattices; and constructing a weighted directed graph, representing the data-flow, each node in the graph representing one of the basic sets, each node weight in the graph representing the size of the one basic set, each arc of the graph representing a dependence relation between two of the basic sets, each arc weight of the graph representing the number of dependence relations between the two basic sets.
Claim 20
Dependent Claim
13 words
The method of claim 17, wherein the data-flow graph comprises a polyhedral graph.
Claim 21
Dependent Claim
25 words
The method of claim 17, wherein the processing system includes nests of loops, the boundaries of each loop comprising affine functions of surrounding loop iterators.
Claim 22
Dependent Claim
26 words
The method of claim 17, wherein the processing system includes nests of loops, the signal indices of each loop comprising affine functions of surrounding loop iterators.
Claim 23
Dependent Claim
16 words
The method of claim 17, wherein the data-dominated processing system comprises a multi-dimensional signal processing system.
Claim 24
Dependent Claim
20 words
The method of claim 17, wherein the data-flow graph provides storage information for memory in an application specific integrated circuit.
Claim 25
Dependent Claim
21 words
The method of claim 17, wherein the data-flow graph provides storage information for a data cache memory in a predefined processor.
Claim 26
Dependent Claim
16 words
The method of claim 17, wherein the data-flow graph provides storage information for a non-electronic storage.
Claim 27
Dependent Claim
13 words
The method of claim 17, wherein the behavioral specification comprises a nonprocedural specification.
Claim 28
Dependent Claim
14 words
The method of claim 17, wherein the behavioral specification comprises a single assignment form.
Claim 29
Dependent Claim
19 words
The method of claim 17, additionally comprising the step of modifying the data-flow graph to allow for delayed data.
Claim 30
Independent Claim
96 words
A method of estimating the storage and port requirements of memory for a nonprocedural behavioral specification in single assignment form, based on a data-flow graph of signals, comprising the steps of: determining a partial computation ordering of the nodes in the data-flow graph based on storage cost and port cost, each node indicative of a group of signals; estimating the storage requirements of the memory compatible with the partial computation ordering; and estimating the port requirements of the memory based on the behavioral specification and the partial computation ordering and a cycle budget for memory accesses.
Claim 31
Independent Claim
96 words
A method of estimating the storage and port requirements of memory for a nonprocedural behavioral specification in single assignment form, based on a data-flow graph of signals, comprising the steps of: determining a partial computation ordering of the nodes in the data-flow graph based on storage cost and port cost, each node indicative of a group of signals; estimating the storage requirements of the memory compatible with the partial computation ordering; and estimating the port requirements of the memory based on the behavioral specification and the partial computation ordering and a cycle budget for memory accesses.
Claim 32
Dependent Claim
31 words
The method of claim 28, wherein the partial computation ordering is determined iteratively, starting from a non-ordered flow graph and iteratively ordering all of the signals based on a priority function.
Claim 33
Dependent Claim
20 words
The method of claim 28, wherein the data-flow graph provides storage information for memory in an application specific integrated circuit.
Claim 34
Dependent Claim
21 words
The method of claim 28, wherein the data-flow graph provides storage information for a data cache memory in a predefined processor.
Claim 35
Dependent Claim
16 words
The method of claim 28, wherein the data-flow graph provides storage information for a non-electronic storage.
Claim 36
Independent Claim
120 words
A method of memory allocation for a data-dominated signal processing system represented as a partial computation ordering of the nodes in a data-flow graph based on storage cost and port cost each node indicative of a group of signals, the method comprising the steps of: deriving a cost function based on memory area and a plurality of read-write memories, each memory indicative of a maximum number of simultaneous read-write operations of signals having a specified number of bits, the memories determined from the partial computation ordering; deriving a set of port constraints for the read-write memories; deriving a set of storage constraints for the read-write memories; and generating one or more port configurations, each port configuration matching the port constraints.
Claim 37
Independent Claim
120 words
A method of memory allocation for a data-dominated signal processing system represented as a partial computation ordering of the nodes in a data-flow graph based on storage cost and port cost each node indicative of a group of signals, the method comprising the steps of: deriving a cost function based on memory area and a plurality of read-write memories, each memory indicative of a maximum number of simultaneous read-write operations of signals having a specified number of bits, the memories determined from the partial computation ordering; deriving a set of port constraints for the read-write memories; deriving a set of storage constraints for the read-write memories; and generating one or more port configurations, each port configuration matching the port constraints.
Claim 38
Dependent Claim
27 words
The method of claim 33, additionally comprising the step of solving memory allocation modeled as an optimization problem based on the derived port constraints and storage constraints.
Claim 39
Dependent Claim
14 words
The method of claim 33, wherein the cost function is also based on power.
Claim 40
Dependent Claim
12 words
The method of claim 33, wherein the read-write memories include read-only memories.
Claim 41
Dependent Claim
16 words
The method of claim 33, wherein the port configurations satisfy constraints of the partial computation ordering.
Claim 42
Independent Claim
71 words
A method of signal to memory assignment for a data-dominated signal processing system represented as a partial computation ordering of the nodes in a data-flow graph based on storage cost and port cost, each node indicative of a group of signals partition, comprising the steps of: allocating memory units according to minimization of a criteria; and constructing an initial assignment of the partitions to the memory units without any port conflicts.
Claim 43
Independent Claim
71 words
A method of signal to memory assignment for a data-dominated signal processing system represented as a partial computation ordering of the nodes in a data-flow graph based on storage cost and port cost, each node indicative of a group of signals partition, comprising the steps of: allocating memory units according to minimization of a criteria; and constructing an initial assignment of the partitions to the memory units without any port conflicts.
Claim 44
Dependent Claim
11 words
The method of claim 38, wherein the partitions include basic sets.
Claim 45
Dependent Claim
13 words
The method of claim 38, wherein the partitions include disjoint linearly bounded lattices.
Claim 46
Dependent Claim
11 words
The method of claim 38, wherein the criteria comprises total area.
Claim 47
Dependent Claim
17 words
The method of claim 38, wherein the criteria comprises a combination of total storage and access costs.
Claim 48
Dependent Claim
17 words
The method of claim 38, wherein the memory units are implemented as an application specific integrated circuit.
Claim 49
Dependent Claim
20 words
The method of claim 38, wherein the memory units are implemented as a data cache memory in a predefined processor.
Claim 50
Dependent Claim
15 words
The method of claim 38, wherein the memory units are implemented as a non-electronic storage.
Claim 51
Dependent Claim
15 words
The method of claim 38, additionally comprising the step of iteratively improving on the assignments.
References Cited (Backward Citations)
US5553285A
Cited
US4964063A
Cited
US5327561A
Cited
US5454104A
Cited
US5485616A
Cited
US5664109A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-20 | 2001-10-20 | 2002-04-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-20 | 2005-10-20 | 2006-04-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-20 | 2009-10-20 | 2010-04-21 | $7700.00 | Window Closed / Lapsed |