Method and system for managing resource allocation in non-uniform resource access computer systems

• US 7,313,795 B2
• Filed: 05/27/2003
• Issued: 12/25/2007
• Est. Priority Date: 05/27/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chew, Jonathan, Berube, Robert L., Clarke, Kevin, Marsland, Tim, Saxe, Eric, Smaalders, Bart
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Wai, Eric C
• Application Number:
  US10/446,741
• Publication Number:
  US 20040243660A1
• Time in Patent Office: 1,673 Days
• Field of Search: 709/213
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/502 Proximity
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

A method and system of managing resource allocation in a non-uniform resource access computer system is disclosed. A method comprises determining access costs between resources in a computer system having non-uniform access costs between the resources. The method also includes constructing a hierarchical data structure comprising the access costs. The hierarchical data structure is traversed to manage a set of the resources.

Claims

1. A computer implemented method of managing resource allocation in a computer system having a plurality of resources coupled together through one or more paths, the plurality of resources including a first resource and a second resource, the computer implemented method comprising:

a) determining access costs of accessing the first resource from the second resource wherein each of the access costs represents cost of access of the first resource from the second resource through each of the paths therebetween and access costs of the second resource from the first resource are different from the access costs of the first resource from the second resource;

b) forming a hierarchical data structure comprising said access costs between each resource in the plurality of resources, the hierarchical data structure includes the paths connecting each of the resources, each of the paths having a number to represent an access cost, the hierarchical data structure is formed by nodes including access cost groups, the access cost groups having an access cost between pairs of the plurality of resources; and

c) traversing said hierarchical data structure to determine a path between the first resource and the second resource, the path having a least access cost and available to enable access to the second resource from the first resource.

2. The method of claim 1, wherein said b) comprises constructing said hierarchical structure to facilitate finding near resources of said resources to a selected resource of said resources in terms of said access costs.

3. The method of claim 1, wherein:

said a) comprises determining said access costs between at least two of said resources via a plurality of paths; and

said b) comprises forming said hierarchical data structure comprising multiple nodes defining said access costs via said plurality of paths.

4. The method of claim 1, wherein said c) comprises traversing said hierarchical structure to determine a resource of said resources near a selected resource of said resources in terms of said access costs.

5. The method of claim 4, further comprising:

d) allocating a resource based on said traversal in said c) and bandwidth considerations.

6. The method of claim 1, wherein said a) comprises determining access cost between pairs of said resources.

7. The method of claim 1, wherein the traversing further comprising allocating the second resource having the least access cost.

8. The method of claim 1, wherein the determining includes monitoring the plurality of resources for availability.

9. A computer readable medium having stored therein instructions for implementing a computer implemented method of managing resource allocation in a computer system having a plurality of resources coupled together through one or more paths, the plurality of resources including a first resource and a second resource, said computer implemented method comprising:

a) forming a plurality of access cost groups each defining a path between the first resource and the second resource, each of the plurality of access cost groups further defines an access cost between the first resource and the second resource wherein access costs of the second resource from the first resource are different from the access costs of the first resource from the second resource;

b) forming a hierarchical data structure having nodes comprising said access cost groups, the access cost group having an access cost between pairs of the plurality of resources, the hierarchical data structure includes the paths connecting each of the plurality of access cost groups, each of the paths having a number to represent an access cost; and

c) traversing said hierarchical data structure to determine a path between the first resource and the second resource, the path having a least access cost and available to enable, access to the second resource from the first resource.

10. The computer readable medium of claim 9, wherein said b) of method further comprises linking a child node in said hierarchical data structure to at least one parent node in said hierarchical data structure, wherein said parent node comprises an access cost that is a next best alternative to an access cost of said child node.

11. The computer readable medium of claim 9, wherein said access costs are based on latency between pairs of said resources.

12. The computer readable medium of claim 9, wherein said c) of said method comprises traversing said hierarchical structure to determine a resource of said resources near a selected resource of said resources in terms of said access costs.

13. The computer readable medium of claim 9, wherein said c) of said method comprises traversing said hierarchical structure and factoring in bandwidth to determine a near resource of said resources to a selected resource of said resources in terms of said access costs.

14. The computer readable medium of claim 9, wherein:

said a) of said method comprises forming said access cost groups for at least two of said resources for a plurality of paths between said at least two resources; and

said b) of said method comprises forming said hierarchical data structure having nodes comprising said access cost groups formed based on said plurality of paths.

15. The computer readable medium of claim 9, wherein the traversing further comprising allocating the second resource having the least access cost.

16. The computer readable medium of claim 9, wherein the forming includes monitoring the plurality of resources for availability.

17. A computer system comprising:

a plurality of resources having non-uniform access costs therebetween wherein the plurality of resources including a first resource and a second resource coupled together through one or more paths;

a processor; and

a computer readable medium having stored therein instructions that when executed on said processor implement a method of allocating said resources, said method comprising;

a) determining access costs of accessing the first resource from the second resource wherein each of the access costs represents cost of access of the first resource from the second resource through each of the paths therebetween and access costs of the second resource from the first resource are different from the access costs of the first resource from the second resource between pairs of said resources;

b) forming a hierarchical data structure that is formed by nodes including access cost groups, the access cost groups having an access cost between pairs of the plurality of resources, wherein the nodes with higher access costs are placed higher in hierarchy of said data structure; and

c) traversing said hierarchical data structure to determine a path between the first resource and the second resource, the path having a least access cost and available to enable access to the second resource from the first resource.

18. The computer system of claim 17, wherein said b) of said method further comprises ordering said nodes into levels and forming said hierarchical data structure according to said levels.

19. The computer system of claim 18, wherein said levels are based on hops taken between said pairs of said resources.

20. The computer system of claim 17, wherein child nodes in said hierarchical data structure have at least one parent node in said hierarchical data structure that defines a next best alternative access cost to access cost of the child node.

21. The computer system of claim 17, wherein said access costs are based on latency between said pairs of said resources.

22. The computer system of claim 17, wherein said method further comprises:

c) traversing said hierarchical structure to determine a resource of said resources near a selected resource of said resources in terms of said access costs.

23. The computer system of claim 17, wherein said a) of said method further comprises determining latencies between processors and memory resources.

24. The computer system of claim 23, wherein said a) of said method further comprises determining latencies via a plurality of paths between said processors and said memory resources.