Resource scheduling methods using positive and negative caching, and resource manager implementing the methods

A resource scheduling method for a plurality of nodes mapped on a coordinate space defining a plurality of leaf buckets, each leaf bucket having one or more coordinates in one or more dimensions in the coordinate space, the method comprising:

• mapping the plurality of nodes on the leaf buckets, each node having an identity, each node also having one or more resource values corresponding to the one or more coordinates of the leaf bucket on which the node is mapped;
• receiving a request for a first task, the first task specifying one or more requested resource values corresponding to the one or more dimensions on the coordinate space, the first task also specifying a list of candidate nodes;
• scanning at least one of the plurality of leaf buckets in the coordinate space to select a first node among the list of candidate nodes in which each of the one or more resource values is at least equal to the one or more requested resource values, the at least one of the plurality of leaf buckets being scanned in a first direction in the coordinate space;
• recording in a negative cache entry zero or more nodes of the list of candidate nodes within scanned leaf buckets that have less than the one or more requested resource values;
• assigning the first node to the first task in a resource schedule;
• reducing the one or more resource values of the first node by the one or more requested resource values;
• and
• repositioning the first node among the plurality of leaf buckets according to the reduced one or more resource values of the first node.

A resource manager, comprising:

• a memory device adapted to store:
• a coordinate space defining a plurality of leaf buckets, each leaf bucket having one or more coordinates in one or more dimensions in the coordinate space,
• a mapping of a plurality of nodes on the leaf buckets, each node having an identity, each node also having one or more resource values corresponding to the one or more coordinates of the leaf bucket on which the node is mapped, and
• one or more positive cache entries;
• an input/output device adapted to receive a request for a first task, the first task specifying one or more requested resource values corresponding to the one or more dimensions on the coordinate space, the first task also specifying a list of candidate nodes;
• a processor operatively connected to the memory and to the input/output device, the processor being configured to:
• receive the request for the first task from the input/output device,
• scan, in the memory device, at least one of the plurality of leaf buckets in the coordinate space to select a first node among the list of candidate nodes in which each of the one or more resource values is at least equal to the one or more requested resource values, the at least one of the plurality of leaf buckets being scanned in a first direction in the coordinate space;
• record, in a positive cache entry of the memory device, the leaf bucket containing the first node,
• assign the first node to the first task in a resource schedule,
• reduce, in the memory device, the one or more resource values of the first node by the one or more requested resource values,
• reposition, in the memory device, the first node among the plurality of leaf buckets according to the reduced one or more resource values of the first node, and
• cause the input/output device to transmit the assignment of the first node to the first task.

A resource manager, comprising:

• a memory device adapted to store:
• a coordinate space defining a plurality of leaf buckets, each leaf bucket having one or more coordinates in one or more dimensions in the coordinate space, the coordinate space also defining a plurality of child buckets, each child bucket being defined by a coordinate vector including a first coordinate for a first one of the one or more dimensions of the coordinate space, each leaf bucket being associated to one of the child buckets, a first coordinate of the leaf bucket being equal to the first coordinate of the child bucket to which it is associated,
• a mapping of a plurality of nodes on the leaf buckets, each node having an identity, each node also having one or more resource values corresponding to the one or more coordinates of the leaf bucket on which the node is mapped, and
• one or more negative cache entries;
• an input/output device adapted to receive a request for a first task, the first task specifying one or more requested resource values corresponding to the one or more dimensions on the coordinate space, the first task also specifying a list of candidate nodes;
• a processor operatively connected to the memory and to the input/output device, the processor being configured to:
• receive the request for the first task from the input/output device,
• scan, in the memory device, at least one of the plurality of leaf buckets in the coordinate space to select a first node among the list of candidate nodes in which each of the one or more resource values is at least equal to the one or more requested resource values, the at least one of plurality of leaf buckets being scanned in a first direction in the coordinate space,
• record, in a negative cache entry of the memory device, zero or more nodes of the list of candidate nodes within scanned leaf buckets that have less than the one or more requested resource values,
• assign the first node to the first task in a resource schedule,
• reduce, in the memory device, the one or more resource values of the first node by the one or more requested resource values,
• reposition, in the memory device, the first node among the plurality of leaf buckets according to the reduced one or more resource values of the first node, and
• cause the input/output device to transmit the assignment of the first node to the first task.