Background memory allocation for multi-dimensional signal processing

• US 5,742,814 A
• Filed: 05/15/1996
• Issued: 04/21/1998
• Est. Priority Date: 11/01/1995
• Status: Expired due to Term

• Current Assignee: IMEC International
• Original Assignee: IMEC International
• Inventors: Balasa, Florin, Catthoor, Francky, De Man, Hugo
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/649,903
• Time in Patent Office: 706 Days
• Field of Search: 395/6, 395/70
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

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.

2. 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.

3. The method of claim 1, wherein each arc includes a weight indicative of the number of dependency relations between connecting nodes.

4. The method of claim 1, wherein the data-flow graph comprises a polyhedral graph.

5. 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.

6. 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.

7. The method of claim 1, wherein the data-dominated processing system comprises a multi-dimensional signal processing system.

8. The method of claim 1, wherein the data-flow graph provides storage information for memory in an application specific integrated circuit.

9. The method of claim 1, wherein the data-flow graph provides storage information for a data cache memory in a predefined processor.

10. The method of claim 1, wherein the data-flow graph provides storage information for a non-electronic storage.

11. The method of claim 1, wherein the data-dominated processing system is represented by a behavioral specification.

12. The method of claim 11, wherein the behavioral specification comprises a nonprocedural specification.

13. The method of claim 11, wherein the behavioral specification comprises a single assignment form.

14. 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.

15. The method of claim 1, wherein the deriving step includes the step of determining the number of dependencies between the partitioned linearly bounded lattices.

16. The method of claim 1, additionally comprising the step of modifying the data-flow graph to allow for delayed data.

17. 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.

18. The method of claim 17, wherein the data-flow graph comprises a polyhedral graph.

19. 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.

20. 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.

21. The method of claim 17, wherein the data-dominated processing system comprises a multi-dimensional signal processing system.

22. The method of claim 17, wherein the data-flow graph provides storage information for memory in an application specific integrated circuit.

23. The method of claim 17, wherein the data-flow graph provides storage information for a data cache memory in a predefined processor.

24. The method of claim 17, wherein the data-flow graph provides storage information for a non-electronic storage.

25. The method of claim 17, wherein the behavioral specification comprises a nonprocedural specification.

26. The method of claim 17, wherein the behavioral specification comprises a single assignment form.

27. The method of claim 17, additionally comprising the step of modifying the data-flow graph to allow for delayed data.

28. 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.

29. 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.

30. The method of claim 28, wherein the data-flow graph provides storage information for memory in an application specific integrated circuit.

31. The method of claim 28, wherein the data-flow graph provides storage information for a data cache memory in a predefined processor.

32. The method of claim 28, wherein the data-flow graph provides storage information for a non-electronic storage.

33. 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.

34. 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.

35. The method of claim 33, wherein the cost function is also based on power.

36. The method of claim 33, wherein the read-write memories include read-only memories.

37. The method of claim 33, wherein the port configurations satisfy constraints of the partial computation ordering.

38. 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.

39. The method of claim 38, wherein the partitions include basic sets.

40. The method of claim 38, wherein the partitions include disjoint linearly bounded lattices.

41. The method of claim 38, wherein the criteria comprises total area.

42. The method of claim 38, wherein the criteria comprises a combination of total storage and access costs.

43. The method of claim 38, wherein the memory units are implemented as an application specific integrated circuit.

44. The method of claim 38, wherein the memory units are implemented as a data cache memory in a predefined processor.

45. The method of claim 38, wherein the memory units are implemented as a non-electronic storage.

46. The method of claim 38, additionally comprising the step of iteratively improving on the assignments.