Method and apparatus for distributing work granules among processes based on the location of data accessed in the work granules

Claim 3

The method of claim 1 wherein: said computer system is a shared disk computer system; and said step of determining which location of said plurality of locations is most efficiently accessed by said process comprises determining whether data that must be accessed during execution of said plurality of work granules resides in a cache memory that is local relative to said node.

Claim 4

The method of claim 1 wherein: said computer system is a shared nothing computer system; and said step of determining which location of said plurality of locations is most efficiently accessed by said process comprises determining whether data that must be accessed during execution of said plurality of work granules resides on a local storage device or on a remote storage device.

Claim 5

The method of claim 1 wherein: said step of identifying a plurality of locations includes identifying devices that store the data that must be accessed during execution of said plurality of work granules; and said step of determining which location of said plurality of locations is most efficiently accessed by said process includes determining current usage of said devices.

Claim 6

The method of claim 1 further comprising the steps of: determining a size of at least two of said plurality of work granules; and assigning to said process a work granule of said at least two of said plurality of work granules based on the size of said work granule relative to the size of the other of said at least two of said plurality of work granules.

Claim 7

The method of claim 1 wherein: said plurality of work granules are work granules for performing a parent task; and the method comprises the step of dividing said parent task into said work granules based on said plurality of locations.

Claim 8

The method of claim 6 wherein the step of dividing said parent task into said work granules includes dividing said parent task into work granules that require access to data located at no more than one of said plurality of locations.

Claim 9

The method of claim 1 wherein the computer system is a shared nothing computer system and the step of identifying a plurality of locations comprises the steps of: issuing queries to a mechanism that provides shared disk functionality to said shared nothing computer system; constructing a virtual map of the computer system based on responses to said queries; and inspecting said virtual map of the computer system to determine where data that will be accessed during said plurality of work granule resides.

Claim 12

The method of claim 9 wherein: said plurality of storage locations include a plurality of cache memories; and the step of selecting a work granule includes the steps of determining whether a work granule of said at least two work granules accesses data stored in a cache memory that is local relative to said process; if a work granule of said at least two work granules accesses data stored in a cache memory that is local relative to said process, then selecting said work granule; if no work granule of said at least two work granules accesses data stored in a cache memory that is local relative to said process, then performing the steps of determining whether any work granule of said at least two work granules does not require access to data stored in a cache memory that is remote relative to said process; and if a work granule of said at least two work granules does not require access to data stored in a cache memory that is remote relative to said process, then selecting said work granule.

Claim 13

The method of claim 9 wherein: said plurality of storage locations include a plurality of static storage devices; and the step of selecting a work granule includes the steps of determining whether a work granule of said at least two work granules accesses data stored in a static storage device that is local relative to said process; if a work granule of said at least two work granules accesses data stored in a static storage device that is local relative to said process, then selecting said work granule.

Claim 14

The method of claim 11 further comprising the steps of: if no work granule of said at least two work granules accesses data stored in a static storage device that is local relative to said process, then performing the steps of determining current usage of static storage devices that contain data that must be accessed to perform said at least two work granules; and selecting said work granule based on current usage of said static storage devices.

Claim 15

The method of claim 9 wherein said step of selecting said work granule is further performed based on current usage of devices that contain data that must be accessed to perform said two or more work granules.

Claim 16

The method of claim 9 wherein said step of selecting said work granule is further performed based on relative sizes of said two or more work granules.

Claim 17

The method of claim 13 wherein said step of selecting said work granule is further performed based on relative sizes of said two or more work granules.

Claim 18

The method of claim 9 further comprising the step of repeatedly performing the following steps until all work granules have been assigned to processes: detecting when a process completes the work granule that is currently assigned to said process; and assigning to said process a work granule that has not yet been assigned to any process.

Claim 19

A computer system comprising: a plurality of storage devices including a plurality of dynamic storage devices; and a plurality of static storage devices; a plurality of nodes that includes a set of nodes selected to run processes to perform a parent task; a communication mechanism that allows processes on each node of said plurality of nodes to communicate with each static storage device of said plurality of static storage devices; a coordinator process executing on at least one node of said plurality of nodes, said coordinator process distributing a plurality of work granules to processes running on said set of nodes to cause said processes to perform said parent task; wherein execution of said work granules requires access to data stored on one or more of said plurality of storage devices; wherein said coordinator process is configured to distribute said plurality of work granules among processes on said set of nodes based on access rates between each process and the storage devices that contain data that must be accessed to perform said work granules; and wherein said coordinator process is configured to assign to a process a work granule that requires access to data stored on a storage device that is remote relative to said process when said process can access said storage device more efficiently than said process can access any other storage device that contains data that must be accessed to perform any other unassigned work granule.

Claim 20

A computer system comprising: a plurality of storage devices including a plurality of dynamic storage devices; and a plurality of static storage devices; a plurality of nodes that includes a set of nodes selected to run processes to perform a parent task; a communication mechanism that allows processes on each node of said plurality of nodes to communicate with each static storage device of said plurality of static storage devices; a coordinator process executing on at least one node of said plurality of nodes, said coordinator process distributing a plurality of work granules to processes running on said set of nodes to cause said processes to perform said parent task; wherein execution of said work granules requires access to data stored on one or more of said plurality of storage devices; wherein said coordinator process is configured to distribute said plurality of work granules among processes on said set of nodes based on access rates between each process and the storage devices that contain data that must be accessed to perform said work granules; and wherein said coordinator process is configured to assign to a process a work granule that requires access to data stored on a storage device that is remote relative to said process when said process can access said storage device more efficiently than said process can access any other storage device that contains data that must be accessed to perform any other unassigned work granule.

Claim 21

The computer system of claim 17 further including a tracking mechanism for detecting when data that must be accessed to perform a work granule resides in a dynamic storage device that is accessible to processes within a single node of said set of nodes, said coordinator process being configured to assign said work granule to a process on said single node when said tracking mechanism indicates that data that must be accessed to perform said work granule resides in said dynamic storage device that is accessible to processes within said single node.

Claim 22

The computer system of claim 17 wherein said coordinator process is further configured to distribute said plurality of work granules among processes on said set of nodes based on relative sizes of said plurality of work granules.

Claim 23

The computer system of claim 19 wherein said coordinator process is configured to assign a larger work granule before a smaller work granule when all other efficiency considerations are equal.

Claim 24

The computer system of claim 17 wherein said coordinator process is further configured to distribute said plurality of work granules among processes on said set of nodes based on current I/O usage of said storage devices that contain data that must be accessed to perform each of said work granules.

Claim 25

The computer system of claim 17 wherein said coordinator process is configured to assign to a process on first node a work granule that requires access to a static storage device that belongs a second node if no unassigned work granules require access to static storage devices that belong to said first node.

Claim 26

The computer system of claim 17 wherein said coordinator process is configured to assign to a process a first work granule that requires access to a first static storage device on a given node rather than a second work granule that requires access to a second static storage device on the given node when said first static storage device is currently less busy than said second static storage device.