Method for determining a storage bandwidth optimized memory organization of an essentially digital device

• US 6,421,809 B1
• Filed: 07/23/1999
• Issued: 07/16/2002
• Est. Priority Date: 07/24/1998
• Status: Expired due to Term

• Current Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International)
• Original Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International)
• Inventors: De Man, Hugo, Wuytack, Sven, Catthoor, Francky
• Primary Examiner(s): Niebling, John F.
• Assistant Examiner(s): Whitmore, Stacy
• Application Number:
  US09/360,140
• Time in Patent Office: 1,089 Days
• Field of Search: 716/2, 716/5
• US Class Current: 716/132
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A formalized method and a design system are described for part of the design decisions, related to memory, involved while designing an essentially digital device. The method and system determine an optimized memory organization starting from a representation of said digital device, the representation describing the functionality of the digital device and comprising data access instructions on basic groups, which are groups of scalar signals. The method and system determine optimized scheduling intervals of said data access instructions such that execution of said functionality with the digital device is guaranteed to be within a predetermined cycle budget, the determining of the optimized scheduling intervals comprising optimizing access conflicts with respect to an evaluation criterion related to the memory cost of said digital device. An optimized memory organization is selected in accordance with the optimized scheduling intervals and the optimized access conflicts.

Claims

1. A method of determining an optimized memory organization of an essentially digital device represented by a representation describing the functionality of said digital device, said representation comprising data access instructions on basic groups, being groups of scalar signals, the method comprising:

determining optimized scheduling intervals of said data access instructions such that execution of said functionality with said digital device is guaranteed to be within a predetermined cycle budget, said determining of said optimized scheduling intervals comprising optimizing access conflicts with respect to an evaluation criterion related to the memory cost of said digital device, wherein optimizing the access conflicts comprises optimizing an extended conflict graph with respect to the evaluation criterion, and wherein said evaluation criterion comprises at least an estimate of the chromatic number of a conflict graph that includes an extended conflict graph not having self-edges and hyper-edges;

determining the total amount of data accesses of each self-edge of sail extended conflict graph;

determining pair-wise basic group conflict costs of binary edges of said extended conflict graph; and

selecting an optimized memory organization in accordance with said optimized scheduling intervals and said optimized access conflicts, wherein the optimized memory organization is selected while satisfying at least the constraints depicted by said optimized extended conflict graph.

2. The method of claim 1, wherein said evaluation identifies which basic groups are being accessed in parallel.

3. The method of claim 1, wherein in said evaluation each conflict cost between basic groups is weighted separately.

4. The method of claim 1, wherein in said evaluation each self conflict cost of a basic group is weighted separately.

5. The method of claim 1, wherein said representation, describing the functionality of said essentially digital system, is a control data flow graph.

6. The method of claim 1, wherein the pair-wise basic group conflict cost of a binary edge of an extended conflict graph comprises:

a first term comprising a first sub-term combining the size of a first basic group of said binary edges with the total amount of data accesses of a second basic group of said binary edges and a second sub-term combining the total amount of data accesses of said first basic group of said binary edges with the size of said second basic group of said binary edges;

a second term combining the difference in bit width between said basic groups of said binary edges with the word size of the basic group of said binary edges with the smallest word size;

a third term being a function of the word size of the basic group of said binary edges with the smallest word size when said basic groups of said binary edges have non-overlapping life times and zero otherwise;

a fourth term being a predetermined positive value when the basic groups of said binary edges are preferably stored in the same memory; and

a fifth term making the pair-wise basic group conflict cost of all binary edges positive.

7. The method of claim 1, wherein each of said edges is associated with a triplet of numbers, the first number of said triplet defining the amount of simultaneous data accesses to said basic groups of said edges due to read instructions, the second number of said triplet defining the amount of simultaneous data accesses to said basic groups of said edges due to write instructions and the third number of said triplet defining the amount of simultaneous data accesses to said basic groups of said edges due to either read or write instructions, said triplet being characteristic for an at least partial scheduling of said data access instructions of said functional representation, wherein the partial scheduling comprises scheduling intervals.

8. The method of claim 1, wherein selecting an optimized memory organization satisfying at least the constraints depicted by said optimized extended conflict graph comprises assigning basic groups being in conflict either to different memories or assigning basic groups being in conflict to a multi-port memory having at least a number, defined by said third number, of ports;

wherein at least a number, defined by said first number, of said ports, have read capability, and wherein at least a number, defined by said second number, of ports, have write capability.

9. The method of claim 1, wherein determining optimized scheduling intervals of said data access instructions such that execution of said functionality with said digital device being guaranteed to be within a predetermined cycle budget and said determining of said optimized scheduling intervals comprising optimizing an extended conflict graph with respect to an evaluation criterion being related to the memory cost of said digital device comprises:

determining initial scheduling intervals for each of said data access instructions for each of said basic groups;

determining initial basic group conflict probabilities;

determining an estimate of the chromatic number of a conflict graph, being an extended conflict graph not having self-edges and hyper-edges, with basic group conflicts with a probability above a predetermined threshold value;

determining an initial value for said evaluation criterion by at least incorporating said chromatic number estimate and combining said initial basic group probabilities with said pair-wise basic group conflict cost;

determining an initial set of possible scheduling interval one cycle reductions, each of said reductions being related to a data access instruction having a scheduling interval of at least two cycles and having a scheduling interval overlapping with at least one other scheduling interval of a data access instruction;

(1) determining for each reduction of said set said evaluation criterion, taking into account changes in the basic group conflict probabilities and recalculating said chromatic number when due to said reduction at least one basic group conflict probability traverses said predetermined threshold value;

(2) selecting from said set a reduction with the best effect on said evaluation criterion;

(3) executing said selected reduction on at least said related data access scheduling interval; and

(4) modifying said set.

10. The method of claim 9, additionally comprising repeating (1) to (4) until no further reduction of said evaluation criterion is found.

11. The method of claim 9, wherein said determining of initial scheduling intervals for each of said data access instructions for each of said basic groups is performed with an ASAP-ALAP analysis for each of said data access instructions for each of said basic groups.

12. The method of claim 1, additionally comprising:

decomposing said representation in a plurality of disjunct blocks;

determining a block cycle budget for each of said disjunct blocks; and

wherein said determining of optimized scheduling intervals being such that execution of each of said blocks is guaranteed to be within its block cycle budget.

13. The method of claim 12, wherein determining a block cycle budget for each of said disjunct blocks comprises determining an allowed-conflicts graph with respect to an evaluation criterion for said allowed conflict graph being related to the memory cost of said digital device.

14. The method of claim 13, wherein determining of an allowed-conflicts graph comprises:

determining an empty allowed-conflict graph;

determining a set of conflicts;

(1) determining for each conflict in said set a conflict cost and the gain on the cycle budget of the application;

(2) adding the conflict with the highest gain-to-cost ratio to said allowed conflict graph;

(3) modifying said set of conflicts; and

repeating (1) to (3) until the cycle budget is below a predetermined value.

15. The method of claim 13, wherein said allowed conflict graph is an undirected hyper-graph, comprising of nodes representing said basic groups;

binary edges representing data access conflicts between the two basic groups connected by said binary edge; and

said evaluation criterion for said allowed conflict graph comprises at least an estimate of the chromatic number of said allowed conflict graph and pair-wise basic group conflict costs of binary edges of said allowed conflict graph conflict graph.

16. The method of claim 1, wherein said functionality is a multi-dimensional signal processing application and said basic groups,are parts of multi-dimensional arrays.

17. The method of claim 1, wherein said functionality is an application with dynamically allocated memory and said basic groups being parts of virtual memory segments.

18. An automated design system for determining an optimized memory organization of an essentially digital device represented by a representation describing the functionality of said digital device, said representation comprising data access instructions on basic groups, being groups of scalar signals, the design system comprising:

a first computing device for determining optimized scheduling intervals of said data access instructions such that execution of said functionality with said digital device is guaranteed to be within a predetermined cycle budget and said determining of said optimized scheduling intervals comprises optimizing access conflicts with respect to an evaluation criterion related to the memory cost of said digital device, wherein optimizing the access conflicts comprises optimizing an extended conflict graph with respect to the evaluation criterion, wherein said evaluation comprises at least an estimate of the chromatic number of a conflict graph that includes an extended conflict graph not having self-edges and hyper-edges, wherein the first computing device determines the total amount of data accesses of each self-edge of an extended conflict graph, and wherein the first computing devices determines pair-wise basic group conflict costs of binary edges of the extended conflict graph; and

a second computing device for selecting an optimized memory organization, wherein the optimized memory organization is selected while satisfying at least the constraints depicted by said optimized extended conflict graph.

19. A method of determining an optimized memory organization of an essentially digital device represented by a representation describing the functionality of the digital device, the representation comprising data access instructions on basic groups, begin groups of scalar signals, the method comprising:

determining optimized scheduling intervals of the data access instructions such that execution of the functionality with the digital device is guaranteed to be within a predetermined cycle budget, the determining of the optimized scheduling intervals comprising optimizing access conflicts with respect to an evaluation criterion related to the memory cost of the digital device, wherein optimizing the access conflicts comprises optimizing an extended conflict graph with respect to the evaluation criterion, wherein determining comprises;

determining initial scheduling intervals for each of the data access instructions for each of the basic groups;

determining initial basic group conflict probabilities;

determining an estimate of the chromatic number of a conflict graph, being an extended conflict graph without self-edges and hyper-edges, with basic group conflicts with a probability above a predetermined threshold value;

determining an initial value for the evaluation criterion by at least incorporating the chromatic number estimate and combining the initial basic group probabilities with the pair-wise basic group conflict cost;

determining an initial set of possible scheduling interval one cycle reductions, each of the reductions being related to a data access instruction having a scheduling interval of at least two cycles and having a scheduling interval overlapping with at least one other scheduling interval of a data access instruction;

(1) determining for each reduction of the set the evaluation criterion, taking into account changes in the basic group conflict probabilities and recalculating the chromatic number when due to the reduction at least one basic group conflict probability traverses the predetermined threshold value;

(2) selecting from the set a reduction with the best effect on the evaluation criterion;

(3) executing the selected reduction on at least the related data access scheduling interval; and

(4) modifying the set; and

selecting an optimized memory organization in accordance with the optimized scheduling intervals and the optimized access conflicts, and wherein the optimized memory organization is selected while satisfying at least the constraints depicted by the optimized extended conflict graph.

20. The method of claim 19, further comprising repeating (1) to (4) until no further reduction of the evaluation criterion is found.

21. The method of claim 19, wherein determining of initial scheduling intervals for each of the data access instructions for each of the basic groups is performed with an ASAP-ALAP analysis for each of the data access instructions for each of the basic groups.

22. The method of claim 19, further comprising:

decomposing the representation in a plurality of disjunct blocks;

determining a block cycle budget for each of the disjunct blocks; and

wherein determining optimized scheduling intervals is such that execution of each of the blocks is guaranteed to be within a block cycle budget.

23. The method of claim 22, wherein determining a block cycle budget for each of the disjunct blocks comprises determining an allowed-conflicts graph with respect to an evaluation criterion for the allowed conflict graph that is related to the memory cost of the digital device.

24. The method of claim 23, wherein determining of an allowed-conflicts graph comprises:

determining an empty allowed-conflict graph;

determining a set of conflicts;

(1) determining for each conflict in the set a conflict cost and the gain on the cycle budget of the application;

(2) adding the conflict with the highest gain-to-cost ratio to the allowed-conflict graph;

(3) modifying the set of conflicts; and

repeating (1) to (3) until the cycle budget is below a predetermined value.

25. The method of claim 19, wherein the allowed conflict graph is an undirected hyper-graph, comprising of nodes representing the basic groups;

binary edges representing data access conflicts between the two basic groups connected by the binary edge; and

the evaluation criterion for the allowed conflict graph comprises at least an estimate of the chromatic number of the allowed conflict graph and pair-wise basic group conflict costs of binary edges of the allowed conflict graph conflict graph.

26. The method of claim 19, wherein the functionality is a multi-dimensional signal processing application and the basic groups are parts of multi-dimensional arrays.

27. The method of claim 19, wherein the functionality is an application with dynamically allocated memory and the basic groups being parts of virtual memory segments.

28. An automated design system for determining an optimized memory organization of an essentially digital device represented by a representation describing the functionality of the digital device, the representation comprising data access instructions on basic groups, being groups of scalar signals, the design system comprising:

a first computing device for determining optimized scheduling intervals of the data access instructions such that execution of the functionality with the digital device is guaranteed to be within a predetermined cycle budget and the determining of the optimized scheduling intervals comprises optimizing access conflicts with respect to an evaluation criterion related to the memory cost of the digital device, wherein optimizing the access conflicts comprises optimizing an extended conflict graph with respect to the evaluation criterion, wherein determining comprises;

determining initial scheduling intervals for each of the data access instructions for each of the basic groups;

determining initial basic group conflict probabilities;

determining an estimate of the chromatic number of a conflict graph, being an extended conflict graph without self-edges and hyper-edges, with basic group conflicts with a probability above a predetermined threshold value;

determining an initial value for the evaluation criterion by at least incorporating the chromatic number estimate and combining the initial basic group probabilities with the pair-wise basic group conflict cost;

determining an initial set of possible scheduling interval one cycle reductions, each of the reductions being related to a data access instruction having a scheduling interval of at least two cycles and having a scheduling interval overlapping with at least one other scheduling interval of a data access instruction;

(1) determining for each reduction of the set the evaluation criterion, taking into account changes in the basic group conflict probabilities and recalculating the chromatic number when due to the reduction at least one basic group conflict probability traverses the predetermined threshold value;

(2) selecting from the set a reduction with the best effect on the evaluation criterion;

(3) executing the selected reduction on at least the related data access scheduling interval;

(4) modifying the set; and

a second computing device for selecting an optimized memory organization, wherein the optimized memory organization is selected while satisfying at least the constraints depicted by the optimized extended conflict graph.

29. A method of determining an optimized memory organization of an essentially digital device represented by a representation describing the functionality of the digital device, the representation comprising data access instructions on basic groups, being groups of scalar signals, the method comprising:

determining optimized scheduling intervals of the data access instructions such that execution of the functionality with the digital device is guaranteed to be within a predetermined cycle budget, the determining of the optimized scheduling intervals comprising optimizing access conflicts with respect to an evaluation criterion related to the memory cost of the digital device, wherein the determining of optimized scheduling intervals is such that execution of each of the blocks is guaranteed to be within its block cycle budget;

selecting an optimized memory organization in accordance with the optimized scheduling intervals and the optimized access conflicts;

decomposing the representation in a plurality of disjunct blocks; and

determining a block cycle budget for each of the disjunct blocks.