Multi-processor system

• US 6,049,817 A
• Filed: 09/30/1996
• Issued: 04/11/2000
• Est. Priority Date: 07/23/1993
• Status: Expired due to Term

• Current Assignee: Nokia Solutions and Networks GmbH & Co. KG (Nokia Corporation)
• Original Assignee: Siemens AG
• Inventors: Petersen, Volker, Matz, Christine, Schoen, Hans-Ulrich, Siegwart, Bernd
• Primary Examiner(s): Banankhah, Majid A.
• Assistant Examiner(s): LAO, SUE X
• Application Number:
  US08/723,288
• Time in Patent Office: 1,289 Days
• Field of Search: 395/677, 395/672, 395/706, 395/200.78, 395/676, 709/102, 709/107, 709/106, 709/248
• US Class Current: 718/102
• CPC Class Codes: G06F 8/458 Synchronisation, e.g. post-wait, barriers, locks synchronisation among tasks G06F9/52
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/522 Barrier synchronisation

Abstract

A multiprocessor system is disclosed wherein optimum utilization of all active processors is achieved for processing of static task packets. Active processors in a multiprocessor system independently fetch tasks from a central task control table of common memory for processing. The processors wait at a synchronization point until the conditions determined by the synchronization point have been satisfied.

Claims

1. A system for simultaneously processing a plurality of tasks comprising:

a plurality of processors for simultaneously processing said tasks;

a common memory containing a task control table, said task control table having a plurality of task entries accessible to said processors for fetching corresponding tasks indicated in the task entries and processing the tasks, each of the task entries having information about a type of task and whether the task has already been fetched by a processor; and

a synchronization point in the task control table having a parameter list of at least one selected task entry which must be completed before any of the processors access a task entry subsequent to the synchronization point, and information whether the parameter list has been completed;

wherein the task entries subsequent to the synchronization point are accessible to the processors whether or not task entries prior to the synchronization point which are absent from the parameter list have been completed.

2. The system for simultaneously processing a plurality of tasks of claim 1, wherein the processor which completes a last task preceding the synchronization point sends a continuation message to any processors waiting at the synchronization point.

3. The system for simultaneously processing a plurality of tasks of claim 2, further comprising a means for controlling said processing for causing each of the processors to wait until selected tasks of the group of task entries which precede the synchronization point are complete wherein said means for controlling includes a means for monitoring the processing of said tasks by determining the length of a wait of any processor at a synchronization point waiting for said continuation message.

4. The system for simultaneously processing a plurality of tasks of claim 3, wherein said means for monitoring includes means for sending an error message when the duration of the wait state exceeds a predetermined interval.

5. The system for simultaneously processing a plurality of tasks of claim 4, wherein said means for sending also sends a continuation message to the remaining processors.

6. The system for simultaneously processing a plurality of tasks of claim 1, further comprising means for a dynamically initializing the task control table by calculating a region parameter based on the size of a parallel procedure and the number of available processors.

10. The system for simultaneously processing a plurality of tasks of claim 1, wherein the type of task comprises:

a serial task serially processed on one processor of the plurality of processors; and

a parallel task processed in parallel on more than one processor of the plurality of processors.

11. The system for simultaneously processing a plurality of tasks of claim 1, wherein the task entries are accessed sequentially from a top of the task control table, and each processor accesses a next free task entry from the task control table without prior assignment of any specific task entry to a specific processor.

7. A method for processing a task packet with a plurality of processors comprising the steps of:

processing a first group of tasks preceding a synchronization point in the order in which the tasks are listed in a task control table with a number of different processors;

identifying at least one task of the first group of tasks by a synchronization point parameter list which must be completed before any of the processors access a task subsequent to the synchronization point;

verifying that all tasks of the synchronization point parameter list have been completed before processing an additional task with a processor that has reached the synchronization point; and

processing a second group of tasks after the synchronization point with the number of different processors whether or not a task of the first group of tasks preceding the synchronization point which is absent from the synchronization point parameter list has been completed.

8. The method for processing a task packet with a plurality of processors of claim 7, comprising the additional step of:

determining whether a processor has failed during execution of a particular task with a checking processor; and

executing the particular task with the checking processor if the processor has failed.

9. A method or processing a plurality of tasks with a plurality of processors comprising the steps of:

generating a task control table;

processing a plurality of said tasks from said task control table with a plurality of processors;

while processing at least one of said tasks with a corresponding processor, repeating a step of assigning a next task from the task control table to a next available processor and processing said task with said processor;

for each task completed by a processor, updating the task control table to reflect completion of the task;

accessing a parameter list of a synchronization point in the task control table with one of the processors;

identifying at least one task by the parameter list which must be completed before any of the processors access a task entry subsequent to the synchronization point;

preventing the processors from accessing all tasks subsequent to the synchronization point until all of the tasks identified in the parameter list have been completed; and

allowing task entries subsequent to the synchronization point to be accessed by at least one of the processors whether or not task entries prior to the synchronization point which are absent from the parameter list have been completed.