Method for determining an optimized memory organization of a digital device

• US 6,449,747 B2
• Filed: 03/30/2001
• Issued: 09/10/2002
• Est. Priority Date: 07/24/1998
• Status: Expired due to Fees

• Current Assignee: IMEC International
• Original Assignee: IMEC International
• Inventors: Catthoor, Francky, De Man, Hugo, Wuytack, Sven
• Primary Examiner(s): Niebling, John F.
• Assistant Examiner(s): Whitmore, Stacy
• Application Number:
  US09/823,409
• Publication Number:
  US 20010052106A1
• Time in Patent Office: 529 Days
• Field of Search: 716/2, 717/151
• US Class Current: 716/135
• 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 system and method for determining optimized scheduling intervals and optimized access conflicts and for determining an optimized memory organization of an essentially digital device. The system includes an optimizer for determining an optimized scheduling of the data access instructions for a plurality of disjunct code blocks, wherein each of the code blocks include part of the data access instructions. The system performs an iterative process of successively reducing the cycle budget for selected blocks and modifying the scheduling of the selected blocks until a cumulative cycle budget for all of the blocks is met.

Claims

1. A method of determining optimized scheduling intervals and optimized access conflicts useful for determining an optimized memory organization of an essentially digital device, the method comprising:

determining an initial scheduling of the data access instructions for a plurality of disjunct blocks, wherein each of the blocks include part of the data access instructions, and wherein at least one of the blocks is executed a plurality of times that is defined by an iteration count;

deriving from the initial scheduling an initial block cycle budget for each block;

while the overall cycle budget for performance of the digital device is larger than a predetermined overall cycle budget, repeating the method comprising;

(a) for substantially all of the blocks, performing the method comprising;

temporarily reducing a block cycle budget for a selected block by a predetermined amount;

determining optimized scheduling intervals of the data access instructions such that the performance of the digital device is guaranteed to be within the block cycle budgets, wherein determining the optimized scheduling intervals comprises optimizing access conflicts with respect to an evaluation criterion related to the memory cost of the digital device;

computing the overall cycle budget resulting from the optimized scheduling intervals; and

(b) reducing the block cycle budget for at least one selected block, the selection of the block being based at least in part upon the memory cost and an overall cycle budget reduction.

2. The method of claim 1, wherein the initial scheduling is such that no access conflict exists between the data access instructions within each block.

3. The method recited of claim 1, wherein the initial scheduling comprises a sequential ordering.

4. The method of claim 1, wherein the predetermined amount is at least 1.

5. The method of claim 1, additionally comprising:

before repeating the acts (a) and (b), determining an empty set of re-usable access conflicts for at least one of the blocks;

while optimizing access conflicts, utilizing re-usable access conflicts within the sets of re-usable access conflicts that are not related to the selected block; and

updating the set of re-usable access conflicts of the selected block in act (b).

6. The method of claim 5, wherein scheduling intervals of blocks from which access conflicts within the set of re-usable access conflict are not re-used are not modified while optimizing access conflicts.

7. The method of claim 1, additionally comprising selecting an optimized memory organization.

8. A method of determining a cost-cycle budget curve for an essentially digital device that is represented by a digital representation describing the functionality of the digital device, the representation comprising data access instructions on basic groups of scalar signals, the data access instructions having scheduling intervals, the representation comprising a plurality of disjunct blocks, each block including part of the data access instructions, at least one block being executed at least a plurality of times that is indicated by an iteration count, the method comprising:

generating a cost-cycle budget curve that compares the cost of a memory organization of the digital device versus the cycle budget, wherein the cost-cycle budget curve is incrementally generated.

9. The method of claim 8, wherein the cost-cycle budget curve is near Pareto-optimal.

10. The method of claim 8, wherein generating a cost-cycle budget curve comprises:

determining an initial scheduling of the data access instructions such that between the data access instructions within each block no access conflict exists in each block and deriving therefrom for each block an initial block cycle budget;

computing a first overall cycle budget resulting from the initial schedule and a first memory organization in accordance with the initial scheduling of the data access instructions, the first overall cycle budget and the cost of the digital device with the first memory organization defining a first point on the cost-cycle budget curve;

while the overall cycle budget for execution of the functionality with the digital device is reducible, repeating the acts;

(a) for substantially all the blocks, performing the method comprising;

temporarily reducing the block cycle budget by a predetermined amount;

determining optimized scheduling intervals of the data access instructions such that execution of the functionality with the digital device is guaranteed to be within block cycle budgets, the determining of the optimized scheduling intervals comprising optimizing access conflicts with respect to an evaluation criterion that is related to the cost; and

computing an overall cycle budget resulting from the optimized scheduling, wherein computing utilizes at least in part the iteration count of the blocks;

(b) reducing the block cycle budget for at least one selected block; and

(c) adding the overall cycle budget and related cost to the cost-cycle budget curve.

11. The method of claim 10, wherein the initial scheduling is a sequential ordering.

12. The method of claim 10, wherein the predetermined amount is at least one.

13. The method recited of claim 10, additionally comprising:

before repeating the acts (a), (b), and (c), determining an empty set of re-usable access conflicts for at least one of the blocks;

while optimizing access conflicts, utilizing re-usable access conflicts within the sets of re-usable access conflicts not related to the selected block; and

updating the set of re-usable access conflicts of the selected block in act (b).

14. The method of claim 13, wherein scheduling intervals of blocks from which access conflicts within the blocks set of re-usable access conflict are not re-used and are not modified while optimizing access conflicts.

15. The method of claim 8, wherein the cost is selected from the group comprising:

memory area/size cost, memory related power consumption of the digital device, latency of the digital device, area cost of the digital device, and combinations thereof.

16. The method of claim 8, wherein generating the cost-cycle budget curve initially generates high cycle budgets and progressively generates lower cycle budgets, wherein generating the lower cycle budget exploits the results from high cycle budget computations.

17. The method of claim 16, wherein the exploitation of higher cycle budget computations in lower cycle budget computations comprises re-using access conflicts.

18. A method of determining an optimized memory organization of an essentially digital device, wherein an optimized memory organization is determined based on the cost-cycle budget curve generated by the method of claim 8.

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 of scalar signals, the data access instructions having scheduling intervals, the representation comprising a plurality of disjunct blocks, each block including part of the data access instructions, at least one block being executed at least a plurality of times, the optimized memory organization being such that execution of the functionality with the digital device is guaranteed to be within a predetermined overall cycle budget, the method comprising:

determining block cycle budgets while optimizing scheduling intervals.

20. The method of claim 19, wherein determining the block cycle budget while optimizing the scheduling interval comprises, interleaving of determining block cycle budgets and optimizing scheduling intervals.

21. The method of claim 19, wherein the block cycle budgets are determined substantially simultaneously while the scheduling intervals are optimized.

22. The method of claim 19, wherein optimizing scheduling intervals comprises optimizing a global conflict graph that is shared by each of the blocks.

23. 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 of scalar signals, the data access instructions having scheduling intervals, the representation comprising a plurality of disjunct blocks, each block including part of the data access instructions, at least one block being executed at least a plurality of times, the optimized memory organization being such that the performance of the digital device is guaranteed to be within a predetermined overall cycle budget, the method comprising:

(a) determining initial block cycle budgets such that no access conflict exists between the data access instructions within each block;

(b) temporarily reducing, in an iterative process, a block cycle budget by a predetermined amount, and computing the access conflict cost and overall cycle budget reduction of such reduced block cycle budget;

(c) reducing the block cycle budget for at least one selected block; and

(d) returning to act (b) if the overall cycle budget for execution of the functionality with the digital device is larger than the predetermined overall cycle budget.

24. A method optimizing the scheduling of data instructions, the method comprising:

determining a scheduling of data instructions for a plurality of blocks;

determining a cycle budget for substantially all of the blocks, wherein the cycle budget is determined based at least in part upon the determined initial scheduling of a block;

identifying one of the blocks for a cycle budget reduction;

reducing the cycle budget of the identified block;

modifying the scheduling of at least one of the blocks;

calculating a cumulative cycle budget for the blocks; and

repeating the identifying, reducing and modifying, wherein the modifying includes modifying a modified scheduling until the cumulative cycle budget for substantially all of the blocks satisfies a predetermined cycle budget.

25. The method of claim 24, wherein the reducing the cycle budget of the identified block only modifies the scheduling of the identified block.

26. The method of claim 24, wherein the reducing the cycle budget of the identified block modifies the scheduling of instructions for substantially all of the blocks.

27. The method of claim 24, wherein the initial scheduling are determined such that no access conflict exists in any of the blocks.

28. The method of claim 24, wherein the modifying the scheduling of at least one of the blocks increases the amount of access conflicts in at least one block when compared with the initial scheduling.

29. The method of claim 24, wherein the modifying the scheduling of at least one of the blocks results in an equal amount or more access conflicts when compared to the initial scheduling.

30. A system for optimizing the scheduling of data instructions, the system comprising:

means for determining a scheduling of data instructions for a plurality of blocks;

means for determining a cycle budget for substantially all of the blocks, wherein the cycle budget is determined based at least in part upon the determined initial scheduling of a block;

means for identifying one of the blocks for a cycle budget reduction;

means for reducing the cycle budget of the identified block; and

means for modifying the scheduling and cycle budget of at least one of the blocks until a cumulative cycle budget for substantially all of the blocks satisfies a predetermined cycle budget.

31. The system of claim 30, wherein the means for reducing only modifies the scheduling of the identified block.

32. The system of claim 30, wherein the means for reducing modifies the scheduling of instructions for substantially each of the blocks.

33. The system of claim 30, wherein the means for determining an initial scheduling enforces that no access conflict exists in any of the blocks.

34. The system of claim 30, wherein the means for modifying the scheduling increases the amount of access conflicts in at least one block when compared with the initial scheduling.

35. The system of claim 30, wherein the means for modifying scheduling results in an equal amount or more access conflicts when compared with the initial scheduling.

36. A digital device having an optimized memory organization, wherein the design of the memory organization is generated by the method comprising:

determining an initial scheduling of data instructions for a plurality of blocks, wherein the data instructions are to be executed by the digital device;

determining a cycle budget for substantially each of the blocks, wherein the cycle budget is determined based at least in part upon the determined initial scheduling of the block;

identifying one of the blocks for a cycle budget reduction;

reducing the cycle budget of the identified block;

modifying the scheduling of at least one of the blocks;

repeating the identifying, reducing and modifying acts, wherein the modifying act includes modifying a modified scheduling, until a cumulative cycle budget for substantially all of the blocks satisfies a predetermined cycle budget, and wherein the modified scheduling is used to define the design of a memory organization for the digital device.