Systems and methods for allocating data structures to memories

• US 20060149914A1
• Filed: 12/30/2004
• Published: 07/06/2006
• Est. Priority Date: 12/30/2004
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Doris, Tom F.
• Application Number:
  US11/027,759
• Publication Number:
  US 20060149914A1
• Time in Patent Office: Days
• US Class Current: 711/172
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

Systems and methods allocate data structures to memories coupled to a processor. The allocation may be based on system aspects such as memory size constraints, bandwidth constraints, and memory latency. Further aspects that may be included in the allocation decision are minimization of wasted bandwidth and task priorities. A constraint satisfaction algorithm with an objective function may be used to determine a desirable allocation.

Claims

1. A method comprising:

determining a memory access bandwidth for each of a plurality of data structures, each of the data structures having a data structure size;

determining a storage size constraint for each of a plurality of memories, each of the memories having a memory size;

determining a bus bandwidth constraint for each bus accessing the plurality of memories, each bus having a bus bandwidth; and

determining an allocation of the data structures to the plurality of memories using the storage size constraint and the bus bandwidth constraint in a constraint satisfaction algorithm having an objective function to determine allocation fitness.

2. The method of claim 1, wherein the storage size constraint comprises determining if a sum of the data structure sizes for data structures allocated to a memory exceeds the memory size for the memory.

3. The method of claim 1, wherein the bus bandwidth constraint comprises determining if a sum of the memory access bandwidths for data structures allocated to the memory exceeds the bus bandwidth.

4. The method of claim 1, wherein the objective function includes determining a latency associated with a data structure allocation.

5. The method of claim 1, wherein the objective function includes determining a wasted bandwidth associated with a data structure allocation.

6. The method of claim 1, wherein determining memory access bandwidth includes determining an interference data structure associating the plurality of data structures to a plurality of tasks.

7. The method of claim 1, wherein the plurality of memories includes a scratch-pad memory.

8. The method of claim 1, wherein the plurality of memories includes an external memory.

9. An apparatus comprising:

a processor and a plurality of memories, each of the memories having a memory size;

at least one task executable on the processor; and

a plurality of data structures associated with the at least one task, each of the data structures having a data structure size;

wherein data structures are allocated to a memory of the plurality of memories in accordance with a storage size constraint, a bus bandwidth constraint and an objective function.

10. The apparatus of claim 9, wherein the storage size constraint comprises determining if a sum of the data structure sizes for data structures allocated to a memory exceeds the memory size for the memory.

11. The apparatus of claim 9, wherein the bus bandwidth constraint comprises determining if a sum of the memory access bandwidths for data structures allocated to the memory exceeds the bus bandwidth.

12. The apparatus of claim 9, wherein the objective function includes determining a latency associated with a data structure allocation.

13. The apparatus of claim 9, wherein the objective function includes determining a wasted bandwidth associated with a data structure allocation.

14. The apparatus of claim 9, wherein the plurality of memories includes a DRAM (Dynamic Random Access) memory.

15. The apparatus of claim 9, wherein the plurality of memories includes a scratch-pad memory.

16. The apparatus of claim 9, wherein the plurality of memories includes an off-chip memory.

30. The apparatus of claim 9, wherein the plurality of memories includes a scratch-pad memory.

17. A machine-readable medium having machine readable instructions for executing a method, the method comprising:

determining a memory access bandwidth for each of a plurality of data structures, each of the data structures having a data structure size;

determining a storage size constraint for each of a plurality of memories, each of the memories having a memory size;

determining a bus bandwidth constraint for each bus accessing the plurality of memories, each bus having a bus bandwidth; and

determining an allocation of the data structures to the plurality of memories using the storage size constraint and the bus bandwidth constraint in a constraint satisfaction algorithm having an objective function to determine allocation fitness.

18. The machine-readable medium of claim 17, wherein the storage size constraint comprises determining if a sum of the data structure sizes for data structures allocated to a memory exceeds the memory size for the memory.

19. The machine-readable medium of claim 17, wherein the bus bandwidth constraint comprises determining if a sum of the memory access bandwidths for data structures allocated to the memory exceeds the bus bandwidth.

20. The machine-readable medium of claim 17, wherein the objective function includes determining a latency associated with a data structure allocation.

21. The machine-readable medium of claim 17, wherein the objective function includes determining a wasted bandwidth associated with a data structure allocation.

22. The machine-readable medium of claim 17, wherein determining memory access bandwidth includes determining an interference data structure associating the plurality of data structures to a plurality of tasks.

23. The machine-readable medium of claim 17, wherein the plurality of memories includes a memory selected from the group consisting of a scratch-pad memory, an off-chip memory, and an external memory.

24. The machine-readable medium of claim 17, wherein determining the memory access bandwidth includes weighting the memory access bandwidth according to a task associated with the data structure.

25. A system comprising:

an SRAM (Static Random Access) memory;

at least one task having a plurality of data structures allocatable to a plurality of memories, said plurality including the SRAM memory, each of the memories having a memory size; and

an allocation analysis tool operable to;

determine a memory access bandwidth for each of a plurality of data structures, each of the data structures having a data structure size;

determine a storage size constraint for each of a plurality of memories, each of the memories having a memory size;

determine a bus bandwidth constraint for each bus accessing the plurality of memories, each bus having a bus bandwidth; and

determine an allocation of the data structures to the plurality of memories using the storage size constraint and the bus bandwidth constraint in a constraint satisfaction algorithm having an objective function to determine allocation fitness.

26. The system of claim 25, wherein the storage size constraint comprises determining if a sum of the data structure sizes for data structures allocated to a memory exceeds the memory size for the memory.

27. The system of claim 25, wherein the bus bandwidth constraint comprises determining if a sum of the memory access bandwidths for data structures allocated to the memory exceeds the bus bandwidth.

28. The system of claim 25, wherein the objective function includes determining a latency associated with a data structure allocation.

29. The system of claim 25, wherein the objective function includes determining a wasted bandwidth associated with a data structure allocation.