# US 2013/0155456 A1 · Dynamically adjusting the complexity of worker tasks in a 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 2013/0155456 A1 - Document ID: US20130155456A1 - Status: Published application - Kind: A1 - Application number: 13/712,805 - Filed: 2012-12-12 - Published: 2013-06-20 - Earliest claimed: 2011-12-14 - Assignees: Canon Kabushiki Kaisha - Inventors: Paul William MORRISON; Ekaterina STEFANOV - Web page: https://patentgrep.com/patent/US20130155456A1 ## CPC - G06F 3/1296: {Printer job scheduling or printer resource handling} - G06F 3/1214: {at the submitting node} - G06F 3/124: {Parallel printing or parallel ripping} - G06F 3/1288: {in client-server-printer device configuration} - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosed are methods of allocating tasks for a print job in a multi-threaded system. One method determines a utilisation measure of at least one of a plurality of intermediate data generating threads, and a complexity limit of a intermediate data generation task. The complexity limit is decreased if the determined utilisation measure of the intermediate data generating thread is under a predetermined threshold. The complexity limit limits a processing load of the intermediate data generation task to be allocated to the intermediate data generating thread. The method then compares the processing load of the intermediate data generation task to be allocated with the determined complexity limit, and allocates the intermediate data generation task to the intermediate data generating thread for processing in an event that the processing load of the intermediate data generation task satisfies the complexity limit. ## Claims ### Claim 1 A method of allocating tasks for rendering a page based on a print job in a multi-threaded system, the method comprising: (a) receiving at least one graphical object from the print job to produce an intermediate data generation task; (b) determining a utilisation measure of at least one of a plurality of intermediate data generating threads; (c) determining a complexity limit to limit a processing load of the intermediate data generation task to be allocated to the intermediate data generating thread, the complexity limit being decreased if the determined utilisation measure of the intermediate data generating thread is below a predetermined threshold; (d) comparing a processing load of the intermediate data generation task to be allocated with the determined complexity limit; and (e) allocating the intermediate data generation task to the intermediate data generating thread for processing in an event that the processing load of the intermediate data generation task satisfies the complexity limit. ### Claim 2 (depends on 1) A method according to claim 1 where, in the event that the processing load of the intermediate data generation task does not satisfy the complexity limit, the method comprises extracting a portion of the intermediate data generation task as a new task and assigning that new task to an intermediate data generation thread, and repeating steps (d) and (e) for the remaining portion of the intermediate data generation task to be allocated. ### Claim 3 (depends on 1) A method according to claim 1, wherein the processing load of the intermediate data generation task is determined based on a complexity value associated with a number of instructions required to execute an intermediate data generation task. ### Claim 4 (depends on 3) A method according to claim 3, wherein the complexity value is estimated from measures associated with complexity, the measures being one of time of execution of the intermediate data generation task, the number of CPU cycles taken to complete the intermediate data generation task, or the number of retired instructions (NRI) associated with the intermediate data generation task. ### Claim 5 (depends on 1) A method according to claim 1, further comprising: determining a task processing measure, where the utilisation measure is greater than the utilisation threshold; and using the determined task processing measure to one of maintain or increase the complexity limit. ### Claim 6 (depends on 1) A method according to claim 1, comprising: determining a task processing rate of producer tasks to produce the intermediate data generation tasks and a task processing rate of the intermediate data generation tasks; comparing a ratio of the worker rate to the producer rate with a predetermined rate threshold; and increasing the complexity limit where the ratio is less than the threshold. ### Claim 7 (depends on 1) A method according to claim 1, wherein the utilisation measure is determined by calculating one of an average, a median, or a weighted average, of the utilisation of individual intermediate data generating threads, where the utilisation of a single intermediate data generating thread is the percentage of time that the single thread has spent executing tasks over a period of time. ### Claim 8 (depends on 7) A method according to claim 7, wherein the utilisation of a single thread includes a predicted percentage of time that the single intermediate data generating thread spends executing tasks that are allocated to the thread during a pre-determined future period of time. ### Claim 9 (depends on 1) A method according to claim 1, further comprising a step of merging intermediate data generated from the intermediate data generation tasks if intermediate tasks are produced separately for a page. ### Claim 10 A method of allocating tasks for rendering a page based on a print job in a multi-threaded rendering system, the method comprising the steps of: receiving at least one graphical object from the print job to produce a worker task to be allocated; determining a utilisation measure of at least one of the plurality of worker threads; determining a complexity limit to limit a processing load of a worker task to be allocated to the worker thread, the complexity limit being decreased if the determined utilization measure of the worker thread is below a predetermined threshold; comparing a processing load of the worker task to be allocated with the determined complexity limit; and allocating the worker task satisfying the determined complexity limit to the worker thread in an event that the processing load of the worker task satisfies the determined complexity limit. ### Claim 11 (depends on 10) A method according to claim 10, comprising: determining a task processing rate of producer tasks to produce the worker tasks and a task processing rate of worker tasks; comparing a ratio of the worker rate to the producer rate with a predetermined rate threshold; and increasing the complexity limit where the ratio is less than the threshold. ### Claim 12 A computer readable storage medium having a program recorded thereon, the program being executable by a processor to implement a method of allocating tasks for rendering a page based on a print job in a multi-threaded system, the method comprising the steps of: (a) receiving at least one graphical object from the print job to produce an intermediate data generation task; (b) determining a utilisation measure of at least one of a plurality of intermediate data generating threads; (c) determining a complexity limit to limit a processing load of the intermediate data generation task to be allocated to the intermediate data generating thread, the complexity limit being decreased if the determined utilisation measure of the intermediate data generating thread is below a predetermined threshold; (d) comparing a processing load of the intermediate data generation task to be allocated with the determined complexity limit; and (e) allocating the intermediate data generation task to the intermediate data generating thread for processing in an event that the processing load of the intermediate data generation task satisfies the complexity limit. ### Claim 13 (depends on 12) A computer readable storage medium according to claim 12, further comprising: determining a task processing rate of producer tasks to produce the intermediate data generation tasks and a task processing rate of the intermediate data generation tasks; comparing a ratio of the worker rate to the producer rate with a predetermined rate threshold; and increasing the complexity limit where the ratio is less than the threshold. ### Claim 14 (depends on 12) A method according to claim 12, further comprising a step of merging intermediate data together if intermediate tasks are produced for a page separately. ### Claim 15 A computer readable storage medium having a program recorded thereon, the program being executable by a processor to implement a method of allocating tasks for rendering a page based on a print job in a multi-threaded rendering system, the method comprising the steps of: receiving at least one graphical object from the print job to produce a worker task to be allocated; determining a utilisation measure of at least one of the plurality of worker threads; determining a complexity limit to limit a processing load of a worker task to be allocated to the worker thread, the complexity limit being decreased if the determined utilization measure of the worker thread is below a predetermined threshold; comparing a processing load of the worker task to be allocated with the determined complexity limit; and allocating the worker task satisfying the determined complexity limit to the worker thread in an event that the processing load of the worker task satisfies the determined complexity limit. ### Claim 16 (depends on 11) A computer readable storage medium according to claim 11, further comprising: determining a task processing rate of producer tasks to produce the worker tasks and a task processing rate of worker tasks; comparing a ratio of the worker rate to the producer rate with a predetermined rate threshold; and increasing the complexity limit where the ratio is less than the threshold.