Resource interconnection patterns in a customized memory organization context

• US 6,889,275 B2
• Filed: 04/22/2002
• Issued: 05/03/2005
• Est. Priority Date: 04/23/2001
• Status: Active Grant

• Current Assignee: IMEC International
• Original Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International)
• Inventors: Vandecappelle, Arnout, van Meeuwen, Tycho, Catthoor, Francky, van Zelst, Allert
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US10/128,629
• Publication Number:
  US 20030041128A1
• Time in Patent Office: 1,107 Days
• Field of Search: 710/100, 710/300, 710/107, 710/316, 716/2, 716/5, 716/16, 716/17, 709/214, 709/220, 711/148, 711/149, 711/100, 370/257
• US Class Current: 710/107
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A system and method are provided that include determining optimum memory organization in an electronic device, wherein further determined are optimum resource interconnection patterns. One aspect of the system and method includes determining resource, e.g., memories and data paths, interconnection patterns of complex bus structures with switches using system-level information about the data-transfer conflicts. The quantity of memories within an electronic device, the size of the memories and the interconnection between the memories, including the interconnection of the memories with one or more data paths, defines a memory organization of an electronic device. Another aspect of the system and method relates to selecting an optimized memory organization, including selecting an optimized interconnection pattern between the memories and between the memories and the data paths.

Claims

1. A method of determining an optimized resource interconnection pattern within an essentially digital device, the method comprising:

determining an optimized labeling of a transfer conflict graph that is determined at least in part from a plurality of scheduling intervals, wherein the transfer conflict graph comprises transfer nodes representing transfers and further comprises transfer edge representing a conflict between the transfers, wherein the transfer are designated to be in conflict when the transfers have partially overlapping scheduling intervals, and determining the optimized labeling of the transfer conflict graph comprises labeling an endpoint of each edge such that each edge endpoint has a different label, while using a minimum amount of labels; and

selecting an optimized interconnection pattern that satisfies at least the constraints determined by the optimized labeling of the transfer conflict graph.

2. The method of claim 1, wherein the essentially digital device comprises a plurality of resources and is represented by a representation describing the functionality of the essentially digital device, the representation comprising transfers and the scheduling intervals for the transfers, the transfers being defined by a source resource and a destination resource that are selected from the plurality of resources.

3. The method of claim 2, wherein the plurality of resources comprises a plurality of memory devices.

4. The method of claim 2, wherein determining the optimized labeling of the transfer conflict graph comprises labeling each endpoint such that each edge endpoint has a different label when the transfer nodes connected by the edge represent transfers involves the same resources.

5. The method of claim 2, further comprising:

defining buses for connecting the resources, wherein at least a part of the source and destination resources have a plurality of ports;

determining the optimized labeling of an access conflict graph, wherein accesses are defined by the transfers, and wherein the access conflict graph is determined from the scheduling intervals; and

selecting an optimized bus port assignment satisfying at least the constraints determined by the optimized access conflict graph labeling.

6. The method of claim 1, wherein selecting an optimized interconnection pattern comprises:

defining a plurality of buses; and

associating with each of the buses a source resource and a destination resource that are selected from the plurality of resources.

7. The method of claim 6, wherein at least one of the buses facilitates two transfers having non-overlapping transfer scheduling intervals.

8. The method of claim 6, wherein at least one bus facilitates two transfers having non-overlapping transfer scheduling intervals or temporarily facilitates two transfers having partially overlapping scheduling intervals.

9. The method of claim 6, wherein the source and destination resources are uniquely placed in hierarchy layer sets, wherein the transfer nodes are located within hierarchy transfer sets, wherein boundaries between the hierarchy layer sets define the hierarchy transfer sets, wherein the transfer nodes belong to a hierarchy transfer set when the related transfers proceed from a resource in one hierarchy layer set to the resource in another hierarchy layer set, wherein the hierarchy transfer sets are ordered, and wherein determining the optimized labeling of the transfer conflict graph comprises:

labeling hierarchy transfer set per hierarchy transfer set; and

starting with the first ordered hierarchy transfer set, such that each edge endpoint within a single one of the hierarchy transfer sets has a different label while using a minimal amount of labels.

10. The method of claim 9, wherein the labels of edges connecting transfer nodes within the single one of the hierarchy transfer sets identify at least one of the buses, and wherein the appearance of the same label on edges connecting transfer nodes within different single hierarchy transfer sets identifies a switch within the bus.

11. The method of claim 1, wherein endpoint labels identify at least one of the buses.

12. An essentially digital device comprising:

a plurality of resources; and

an optimized interconnection pattern between the resources, the optimized interconnection pattern comprising a plurality of buses, each of the buses interconnecting a portion of the resources;

wherein the essentially digital device is represented by a representation describing the functionality of the essentially digital device, the representation comprising;

a plurality of transfers that are defined by a source resource and a destination resource that are selected from the plurality of resources; and

a plurality of scheduling intervals for the transfers; and

wherein the essentially digital device is represented by the optimized interconnection pattern such that at least one bus facilitates a plurality of transfers with non-overlapping transfer scheduling intervals, and wherein the optimized interconnection pattern satisfies at least the constraints determined by an optimized labeling of a transfer conflict graph comprising transfer nodes representing transfers and further comprising conflicting transfer edges representing a conflict between the transfers, wherein the transfer conflict graph is determined at least in part from the scheduling intervals, and wherein determining the optimized labeling of the transfer conflict graph comprises labeling an endpoint of each edge such that each edge endpoint has a different label, while using a minimum amount of labels.

13. The method of claim 12, wherein the plurality of resources comprises a plurality of memory devices.

14. The essentially digital device of claim 12, wherein the number of buses is at most equal to the number of edges of a hyper-edge having the most edges found in the transfer conflict graph, and wherein the edges represent a conflict between the transfers having partially overlapping scheduling intervals.

15. The essentially digital device of claim 14, wherein the resources are placed in hierarchy layer sets, wherein the transfer nodes are located within hierarchy transfer sets, wherein boundaries between the hierarchy layer sets define the hierarchy transfer sets, wherein the transfer nodes belong to a hierarchy transfer set when the related transfers proceed from a resource in one hierarchy layer set to a resource in another hierarchy layer set, the number of buses being at most equal to the number of edges, wherein connecting transfer nodes within a single hierarchy transfer set of the hyper-edge having the most edges found in the transfer conflict graph, wherein edges represent a conflict between the transfers, and wherein the transfers have partially overlapping scheduling intervals.

16. The essentially digital device of claim 15, wherein the labels of edges connecting transfer nodes within a single one of the hierarchy transfer sets identify at least one of the buses, and wherein the appearance of the same label on edges connecting transfer nodes within a different single one of the hierarchy transfer sets identifies a switch within the bus.

17. An essentially digital device comprising:

a plurality of resources; and

an optimized interconnection pattern between the resources, the optimized interconnection pattern comprising a plurality of buses, each of the buses interconnecting at least a portion of the resources;

wherein the essentially digital device is represented by a representation describing the functionality of the digital device, the representation comprising;

a plurality of transfers defined by a source resource and a destination resource that are selected from the plurality of resources; and

a plurality of scheduling intervals for the transfers; and

wherein the digital device is represented by the optimized interconnection pattern such that at least one of the buses facilitates a plurality of transfers with non-overlapping transfer scheduling intervals or temporarily facilitates a plurality of transfers with partially overlapping scheduling intervals, and wherein the optimized interconnection pattern satisfies at least the constraints depicted by an optimized labeling of a transfer conflict graph, wherein the transfer conflict graph is determined from at least the scheduling intervals, wherein said transfer conflict graph comprises transfer nodes representing transfers and further comprises conflicting transfer edges representing a conflict between the transfers, and wherein determining the optimized labeling of the transfer conflict graph comprises labeling an endpoint of each edge such that each edge endpoint has a different label, while using a minimum amount of labels.

18. The method of claim 17, wherein the plurality of resources comprises a plurality of memory devices.

19. The essentially digital device of claim 17, wherein the number of buses is at most equal to the number of edges of a hyper-edge having most edges found in the transfer conflict graph comprising transfer nodes representing transfers, and wherein the edges represent a conflict between the transfers having partially overlapping scheduling intervals.

20. The essentially digital device of claim 19, wherein the resources are placed in hierarchy layer sets, wherein the transfer nodes are located within hierarchy transfer sets, wherein boundaries between the hierarchy layer sets define the hierarchy transfer sets, wherein the transfer nodes belong to a hierarchy transfer set when the related transfers proceed from a resource in one hierarchy layer set to a resource in another hierarchy layer set the number of buses being at most equal to the number of edges, wherein connecting transfer nodes within a single hierarchy transfer set of the hyper-edge having most edges found in the transfer conflict graph comprising transfer nodes representing transfers, and wherein edges represent a conflict between the transfers, wherein the transfers have partially overlapping scheduling intervals.

21. The essentially digital device of claim 20, wherein the labels of edges connecting transfer nodes within a single one of the hierarchy transfer sets identify at least one of the buses, and wherein the appearance of the same label on edges connecting transfer nodes within a different single one of the hierarchy transfer sets identifies a switch within the bus.

22. A method of manufacturing an essentially digital device, the method comprising:

determining at least from a plurality of scheduling intervals an optimized labeling of a transfer conflict graph, wherein the transfer conflict graph comprises transfer nodes representing transfers and further comprises conflicting transfer edges representing a conflict between the transfers, and wherein determining the optimized labeling of the transfer conflict graph comprises labeling an endpoint of each edge such that each edge endpoint has a different label, while using a minimum amount of labels; and

selecting an optimized interconnection pattern that satisfies at least the constraints determined by the optimized labeling of the transfer conflict graph.

23. The method of claim 22, wherein the essentially digital device comprises a plurality of resources and is represented by a representation describing the functionality of the essentially digital device, the representation comprising a plurality of transfers and a plurality of scheduling intervals for the transfers.

24. The method of claim 23, wherein selecting the optimized interconnection pattern comprises:

defining a plurality of buses; and

associating with each of the buses a source resource and a destination resource that are selected from the plurality of resources.

25. The method of claim 24, wherein at least one of the buses facilitates two transfers having non-overlapping transfer scheduling intervals.

26. The method of claim 24, wherein at least one of the buses facilitates two transfers having non-overlapping transfer scheduling intervals or temporarily facilitates two transfers having partially overlapping scheduling intervals.

27. A design system for designing an essentially digital device, the system comprising:

means for generating a representation describing the functionality of the essentially digital device, the representation comprising transfers and scheduling intervals for the transfers;

means for determining an optimized labeling of a transfer conflict graph that is determined from the scheduling intervals, the determining comprising uniquely labeling endpoints of transfer edges; and

means for selecting an optimized interconnection pattern that satisfies at least the constraints depicted by the optimized labeling of the transfer conflict graph.

28. A method of determining an optimized resource interconnection pattern within an essentially digital device, the method comprising:

determining a transfer conflict graph, wherein the transfer conflict graph comprises transfer nodes representing transfers and further comprises conflicting transfer edges representing a conflict between the transfers;

determining an optimized labeling of the transfer conflict graph that is determined at least in part from a plurality of scheduling intervals, wherein determining the optimized labeling of the transfer conflict graph comprises labeling an endpoint of each edge such that each edge endpoint has a different label, while using a minimum amount of labels;

selecting an optimized interconnection pattern for at least one of a plurality of partial digital devices that satisfies at least the constraints determined by the optimized labeling of the transfer conflict graph;

determining at least one bus for interconnection of the plurality of partial digital devices;

determining an access conflict graph representing the interconnection of the plurality of partial digital devices;

determining an optimized labeling of the access conflict graph that is determined at least in part from a plurality of conflicts between accesses to a plurality of resources for the plurality of partial digital devices; and

selecting an optimized interconnection pattern for the plurality of partial digital devices that satisfies at least the constraints determined by the optimized labeling of the access conflict graph.