EP0232509A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for balancing the workload in a multiprocessing system
Assignee: International Business Machines Corp
•
Filing: 1986-12-09
•
Granted: —
•
Expires: 2006-12-09
Abstract
Abstract A multiprocessing processing system is dedicated to working on a single problem. The system has a plurality of processors interconnected with each other and with a like plurality of local memories. During the course of working on the problem, old tasks that have not yet been executed are stored in the local memories. New tasks, created as a result of executing old or previous tasks, are initially stored in the associated local memories. One processor acts as an executive processor and stores in its local memory information about the workload of each processor. Tasks are transferred to idle or underloaded processors from overloaded processors to achieve a balanced workload within the system. An example of the type of problem being worked on is string reduction encountered in the field of computer aided design.
Inventors
- 👤 Sumit Dasgupta
- 👤 John Michael Hancock
- 👤 James Herbert Kukula
- 👤 Roger Edwin Peo
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-08 17:51
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5083; G06F9/5088
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
164 words
Multiprocessing apparatus for executing a single problem by creating a multiplicity of tasks in response to execution of at least one initial task,each task thus created requiring execution on a single processor, said apparatus comprising a plurality of processing systems each having a processor and a local memory, and means interconnecting said processing systems, characterized in that one of said processing systems is an executive processing system and the remaining ones are working processing systems, said local memories in said working processing systems storing a plurality of tasks awaiting execution, said newly created tasks being stored in said local memories associated with the ones of said processing systems which created such tasks, said local memory associated with said executive processing system storing information about the workload of said working processing systems, said executive processing system being operative to monitor said workload information and initiate transference of tasks from working processing systems having greater workloads to working processing systems having lesser workloads for execution thereby.
Claim 2
Dependent Claim
164 words
Multiprocessing apparatus for executing a single problem by creating a multiplicity of tasks in response to execution of at least one initial task,each task thus created requiring execution on a single processor, said apparatus comprising a plurality of processing systems each having a processor and a local memory, and means interconnecting said processing systems, characterized in that one of said processing systems is an executive processing system and the remaining ones are working processing systems, said local memories in said working processing systems storing a plurality of tasks awaiting execution, said newly created tasks being stored in said local memories associated with the ones of said processing systems which created such tasks, said local memory associated with said executive processing system storing information about the workload of said working processing systems, said executive processing system being operative to monitor said workload information and initiate transference of tasks from working processing systems having greater workloads to working processing systems having lesser workloads for execution thereby.
Claim 3
Dependent Claim
32 words
Apparatus in accordance with claim 1 wherein said working processing systems having a lesser workloads are idle and said working processing systems having greater workloads have a backlog of tasks awaiting execution.
Claim 4
Dependent Claim
23 words
Apparatus in accordance with claim 1 wherein said workload information includes data representing the backlog of work items for each working processing system.
Claim 5
Dependent Claim
57 words
Apparatus in accordance with claim 1 comprising message transferring means interconnecting all of said processing systems for transferring messages between said processing systems, said messages including a first type indicating when a working processing system needs work and a second type for sending a task from an overloaded working processing system to an idle working processing system.
Claim 6
Dependent Claim
46 words
Apparatus in accordance with claim 1 wherein said local memory in said executive processing system comprises work table means storing workload information relative to each working processing system, and means to access said work table means and determine the workload status of each working processing system.
Claim 7
Independent Claim
131 words
The method of operating a multiprocessing system having a plurality of interconnected processing systems which method involves concurrently executing a plurality of old tasks in said processing systems to dynamically create a plurality of new tasks, characterized by the steps comprising: storing each new task immediately after it is created in the same one of said data processing systems which created such new task to thereby form an old task, arranging a plurality of old tasks in each processing system to create a backlog, monitoring said processing systems to determine which ones have backlogs and which ones are without backlogs, and transferring old tasks from processing systems having backlogs to processing systems without backlogs for execution thereby, so as to concurrently execute a maximum number of tasks within said multiprocessing system.
Claim 8
Independent Claim
131 words
The method of operating a multiprocessing system having a plurality of interconnected processing systems which method involves concurrently executing a plurality of old tasks in said processing systems to dynamically create a plurality of new tasks, characterized by the steps comprising: storing each new task immediately after it is created in the same one of said data processing systems which created such new task to thereby form an old task, arranging a plurality of old tasks in each processing system to create a backlog, monitoring said processing systems to determine which ones have backlogs and which ones are without backlogs, and transferring old tasks from processing systems having backlogs to processing systems without backlogs for execution thereby, so as to concurrently execute a maximum number of tasks within said multiprocessing system.
Claim 9
Dependent Claim
70 words
The method in accordance with Claim 6 comprising: operating one of said processing system as an executive processing system and operating other processing systems as working processing systems for executing said old tasks; said monitoring step comprises generating information about the backlogs of said working processing systems and storing such information in said executive processing system; and operating said executive processing system to initiate said step of transferring old tasks.
Claim 10
Dependent Claim
39 words
The method in accordance with Claim 7, comprising: storing in said executive processing system a work list containing said information about said backlogs, said information including for each processor an indication of whether or not such processor needs work.
Claim 11
Dependent Claim
76 words
The method in accordance with Claim 6 wherein said transferring step comprises sending a first message to a first processing system having a backlog which message directs the transferrence of a task, and sending a second message from said first processing system receiving said first message to a second processing system to which such task is to be transferred, said second message indicating to said second processing system the location of said task to be transferred.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.