# US 2010/0251257 A1 · Method and system to perform load balancing of a task-based multi-threaded application

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0251257 A1
- Document ID: US20100251257A1
- Status: Published application
- Kind: A1
- Application number: 12/414,322
- Filed: 2009-03-30
- Published: 2010-09-30
- Earliest claimed: 2009-03-30
- Assignees: Intel Corporation
- Inventors: Wooyoung Kim; Michael Joseph Voss
- Web page: https://patentgrep.com/patent/US20100251257A1

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 2209/5017: Task decomposition
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and system to balance the load of a task-based multi-threaded application on a platform. When the work required by the multi-threaded application is represented as a task with a computational requirement that is proportional to the amount of the work, embodiments of the invention control the recursive binary task division of the task using auxiliary partitions to create subtasks of balanced loads to enhance resource utilization and to improve application performance. The task is binary partitioned recursively into a plurality of subtasks until the plurality of subtasks is equal to the plurality of resources available on the platform to execute the subtasks.

## Claims

### Claim 1

A method comprising:
determining a plurality of resources available to perform a received task, the received task having a computational requirement; and
binary partitioning the received task recursively into a plurality of subtasks, each subtask having a partitioning ratio of the computational requirement and a corresponding portion of the computational requirement, until the plurality of subtasks is equal to the plurality of resources determined to be available.

### Claim 2 (depends on 1)

The method of claim 1, wherein the corresponding portion of the computational requirement of each subtask is substantially equal.

### Claim 3 (depends on 1)

The method of claim 1, wherein the received task is the received task of an application and further comprising:
receiving the task; and
performing each subtask using a respective one of the plurality of resources determined to be available.

### Claim 4 (depends on 3)

The method of claim 3, wherein the application is to be executed using a plurality of processors, and wherein the respective one of the plurality of resources is to be executed using a respective one of the plurality of processors.

### Claim 5 (depends on 1)

The method of claim 1, wherein each subtask is independent of an execution result of another subtask of the plurality of subtasks.

### Claim 6 (depends on 1)

The method of claim 1, wherein the computational requirement comprises at least one of computational time, processor execution cycles, and iteration cycles of the received task.

### Claim 7 (depends on 1)

The method of claim 1, wherein each subtask is associated with an auxiliary partition, the auxiliary partition comprising a parent load factor and a load factor, and wherein the partitioning ratio of each subtask is a ratio of the load factor to the parent load factor.

### Claim 8 (depends on 7)

The method of claim 7, wherein the parent load factor associated with each subtask is a load factor associated with a respective parent task of each subtask.

### Claim 9 (depends on 8)

The method of claim 8, wherein the load factor associated with each subtask is one of a largest integer not greater than a first result of multiplying the load factor associated with the respective parent task of each subtask with 0.5, and a smallest integer not lesser than a second result of multiplying the load factor associated with the respective parent task of each subtask with 0.5.

### Claim 10

A system comprising:
a plurality of processors;
an operating system (OS) to be executed on at least one of the plurality of processors; and
a library operable on the OS to:
determine a plurality of resources available to perform a received task, the received task having a computational requirement; and
binary partition the received task recursively into a plurality of subtasks, each subtask having a partitioning ratio of the computational requirement and a corresponding portion of the computational requirement, until the plurality of subtasks is equal to the plurality of resources determined to be available.

### Claim 11 (depends on 10)

The system of claim 10, wherein the library to binary partition the received task recursively into a plurality of subtasks is to:
replicate the received task to create a left and a right subtask of the plurality of subtasks; and
split a partition associated with the received task into a left and a right partition associated with the left and right subtask respectively, wherein the partition, the left partition and the right partition each comprises a parent load factor and a load factor.

### Claim 12 (depends on 11)

The system of claim 11, wherein the partitioning ratio of the left subtask is a ratio of the load factor to the parent load factor of the left partition, and wherein the partitioning ratio of the right subtask is a ratio of the load factor to the parent load factor of the right partition.

### Claim 13 (depends on 10)

The system of claim 10, wherein the received task is the received task of a multi-threaded application and wherein the library is further to:
receive the task; and
perform each subtask using a respective one of the plurality of resources determined to be available.

### Claim 14 (depends on 10)

The system of claim 10, wherein the library is part of the OS.

### Claim 15 (depends on 10)

The system of claim 10, wherein the computational requirement of the received task comprises at least one of computational time, processor execution cycles, and iteration cycles of the received task.

### Claim 16 (depends on 11)

The system of claim 11, wherein the library is an Intel® Threading Building Blocks (TBB) library.

### Claim 17

A machine readable storage medium having instructions stored thereon which, when executed, cause a plurality of processors to perform the following method:
determining a plurality of threads available to perform a received task, the received task having a computational requirement; and
binary partitioning the received task recursively into a plurality of subtasks, each subtask having a partitioning ratio of the computational requirement and a corresponding portion of the computational requirement, until the plurality of subtasks is equal to the plurality of threads determined to be available.

### Claim 18 (depends on 17)

The medium of claim 17, wherein the corresponding portion of the computational requirement of each subtask is substantially equal.

### Claim 19 (depends on 17)

The medium of claim 17, wherein the received task is the received task of an application and further comprising:
receiving the task; and
performing each subtask using a respective one of the plurality of threads determined to be available.

### Claim 20 (depends on 17)

The medium of claim 17, wherein each subtask is associated with an auxiliary partition, the auxiliary partition comprising a parent load factor and a load factor, and wherein the partitioning ratio of each subtask is a ratio of the load factor to the parent load factor.

### Claim 21 (depends on 20)

The medium of claim 20, wherein the parent load factor associated with each subtask is a load factor associated with a respective parent task of each subtask.

### Claim 22 (depends on 21)

The medium of claim 21, wherein the load factor associated with each subtask is one of a largest integer not greater than a first result of multiplying the load factor associated with the respective parent task of each subtask with 0.5, and a smallest integer not lesser than a second result of multiplying the load factor associated with the respective parent task of each subtask with 0.5.
