Managing peripheral device address space resources using a tunable bin-packing/knapsack algorithm

• US 7,243,167 B2
• Filed: 09/19/2003
• Issued: 07/10/2007
• Est. Priority Date: 09/19/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zimmer, Vincent J., Rothman, Michael A.
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): MARTINEZ, DAVID E
• Application Number:
  US10/664,623
• Publication Number:
  US 20050066108A1
• Time in Patent Office: 1,390 Days
• Field of Search: None
• US Class Current: 710/10
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration

Abstract

Methods and systems for allocating address space resources to resource requesting peripheral devices in an efficient manner. Resource requests are gathered for enumerated peripheral devices host by a computer platform. A map containing resource alignment requirements is built, and a virtual resource allocation map is computed based on aggregated resource requests and the alignment requirements. The resource aggregations are, in turn, based on a hierarchy of the peripheral devices. A bin-packing algorithm is employed to determine allocation of the resource requests so as to minimize resource address space allocations. The virtual resource map is then used to perform actual resource allocations. The resources include peripheral device I/O address allocation and peripheral device memory address allocations.

Claims

1. A method for allocating address space for a computer platform, comprising:

gathering resource requests for a plurality of PCI (Peripheral Component Interconnect) peripheral devices hosted by the computer platform;

determining a resource allocation scheme to support the resource requests of the peripheral devices, the scheme to minimize an amount of allocated address space, the resource allocation scheme implemented via operations including

aggregating the resource requests for PCI devices at a given level of a PCI hierarchy for the computer platform into respective resource request objects, each resource request object having a size corresponding to the aggregated resource requests of the PCI devices to which it corresponds,

defining a bin size comprising an address space aperture corresponding to a resource type of the resource requests, and

sorting, via a bin-packing algorithm, the resource request objects into appropriate bins to minimize the number of bins required to support the resource requests for all of the PCI devices hosted by the computer platform; and

allocating address space for respective peripheral devices based on the resource allocation scheme that is determined.

2. The method of claim 1, wherein the bin-packing algorithm is the Kth approximation knapsack algorithm.

3. The method of claim 1, wherein the resource requests are aggregated at the PCI root bridge level.

4. The method of claim 1, wherein the resource requests pertain to peripheral device input/output (I/O) address requests.

5. The method of claim 4, wherein the peripheral device I/O address requests are allocated to a portion of platform address space containing virtual addresses.

6. The method of claim 1, wherein the resource requests pertain to memory onboard peripheral devices that is requested to be mapped into the computer platform address space.

7. The method of claim 1, further comprising determining resource alignment requirements for the resource allocation.

8. The method of claim 1, further comprising performing legacy aliasing, wherein resources are mapped to the address space in a manner that accounts for legacy device addressing considerations.

9. The method of claim 1, further comprising allocating a reserved portion of address space for hot-plug devices.

10. The method of claim 9, wherein the allocation of the reserved portion of address space for hot-plug devices enables dynamic reallocation of resources in response to the removal or addition of a hot-plug device to the computer platform.