Distributed Concurrent Batch Processing

Patent metadata

Field	Value
Publication number	US-2026099356-A1
Application number	US-202418907069-A
Country	US
Kind code	A1
Filing date	Oct 4, 2024
Priority date	Oct 4, 2024
Publication date	Apr 9, 2026
Grant date	—

Abstract

Methods for efficiently performing large sets of computational tasks are provided that include receiving a command to perform a plurality of independent computational tasks within a time period; based on the plurality of independent computational tasks, the time period, and an indication of available computational threads, identifying a subset of the available computational threads; allocating the plurality of independent computational tasks to the subset of the available computational threads, wherein each computational thread of the subset of the available computational threads is allocated a number of the plurality of independent computational tasks; and performing the plurality of independent computational tasks via the subset of the available computational threads in accordance with the allocation. Allocating the tasks non-uniformly across fewer than all of the available computational threads can reduce the power and computational costs to perform the tasks, including allowing the computational threads to efficiently perform other activities.

First claim

What is claimed is:

1 . A method comprising:
receiving a command to perform a plurality of independent computational tasks within a time period; based on the plurality of independent computational tasks, the time period, and an indication of available computational threads, identifying a subset of the available computational threads; allocating the plurality of independent computational tasks to the subset of the available computational threads, wherein each computational thread of the subset of the available computational threads is allocated a respective number of the plurality of independent computational tasks; and performing the plurality of independent computational tasks via the subset of the available computational threads in accordance with the allocation.

2 . The method of claim 1 , wherein identifying the subset of the available computational threads comprises determining a number of computational threads in the subset within 10% of ┌J/(Wτ/T)┐+1, wherein J is the number of independent computational tasks in the plurality of independent computational tasks, W is the number of available computational threads, τ is the duration of the time period, and T is an average amount of time a single one of the computational threads takes to perform a single one of the plurality of independent computational tasks.

3 . The method of claim 2 , wherein allocating the plurality of independent computational tasks to the subset of the available computational threads comprises:
determining a task batch size within 10% of J/(ω(ω+1)/2), wherein ω is the number of computational threads in the subset; and allocating, to each computational thread in the subset, a respective multiple of the task batch size of the plurality of independent computational tasks.

4 . The method of claim 2 , wherein determining the number of computational threads is performed responsive to determining that the number of independent computational tasks in the plurality of independent computational tasks is greater than a threshold number of tasks.

5 . The method of claim 2 , wherein determining the number of computational threads
comprises determining the number of computational threads in the subset within 5% of ┌J/(Wτ/T)┐+1.

6 . The method of claim 2 , wherein determining the number of computational threads is performed responsive to determining that the number of independent computational tasks in the plurality of independent computational tasks is greater than 2(τ/T).

7 . The method of claim 1 , wherein identifying the subset of the available computational threads comprises:
determining a target number of computational threads in the subset within 10% of ┌J/(Wτ/T)┐+1, wherein J is the number of independent computational tasks in the plurality of independent computational tasks, W is the number of available computational threads, τ is the duration of the time period, and T is an average amount of time a single one of the computational threads takes to perform a single one of the plurality of independent computational tasks; determining that the target number of computational threads exceeds the number of available computational threads; and responsively identifying the subset of the available computational threads as all of the available computational threads.

8 . The method of claim 1 , wherein identifying the subset of the available computational threads comprises:
determining that the number of independent computational tasks in the plurality of independent computational tasks is less than a threshold value, wherein the threshold value is within 10% of 2(τ/T); and responsively identifying the subset of the available computational threads as a single one of the available computational threads.

9 . The method of claim 1 , wherein allocating the plurality of independent computational tasks to the subset of the available computational threads comprises:
determining a task batch size within 10% of J/(ω(ω+1)/2), wherein ω is the number of computational threads in the subset; and allocating, to each computational thread in the subset, a respective multiple of the task batch size of the plurality of independent computational tasks.

10 . The method of claim 1 , wherein the available computational threads are distributed across two or more computational nodes, wherein identifying the subset of the available computational threads based on the plurality of independent computational tasks, the time period, and the indication of available computational threads is performed responsive to determining that the number of independent computational tasks in the plurality of independent computational tasks is greater than a threshold number of tasks, and wherein the method further comprises:
receiving an additional command to perform an additional plurality of independent computational tasks within an additional time period; determining that the number of independent computational tasks in the additional plurality of independent computational tasks is less than the threshold number of tasks; responsively identifying an additional subset of the available computational threads based on the additional plurality of independent computational tasks, the additional time period, and a number of available computational threads within a single one of the two or more computational nodes; allocating the additional plurality of independent computational tasks to the additional subset of the available computational threads, wherein each computational thread of the additional subset of the available computational threads is allocated a respective number of the additional plurality of independent computational tasks; and performing the additional plurality of independent computational tasks via the additional subset of the available computational threads in accordance with the allocation.

11 . The method of claim 1 , wherein the plurality of independent computational tasks comprise tasks to create, within a database, respective database entries about an event for respective entities associated with a managed network environment.

12 . The method of claim 1 , wherein the plurality of independent computational tasks comprise tasks to update a network security functionality of respective computer systems of a managed network environment.

13 . The method of claim 1 , wherein the plurality of computational tasks are sufficiently independent of each other such that performance of a given one of the computational tasks is not dependent on completed performance of any other of the computational tasks.

14 . A system comprising:
at least one processor; and a memory in which are stored program instructions that, upon execution by the at least one processor, cause the at least on processor to perform operations comprising: receiving a command to perform a plurality of independent computational tasks within a time period; based on the plurality of independent computational tasks, the time period, and an indication of available computational threads, identifying a subset of the available computational threads; allocating the plurality of independent computational tasks to the subset of the available computational threads, wherein each computational thread of the subset of the available computational threads is allocated a respective number of the plurality of independent computational tasks; and performing the plurality of independent computational tasks via the subset of the available computational threads in accordance with the allocation.

15 . The system of claim 14 , wherein identifying the subset of the available computational threads comp

Assignees

• Servicenow Inc

Inventors

• Kadam Vaibhav
• Mishra Ram Krushna

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title