Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-04-15
2003-06-17
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06581089
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a parallel processing apparatus capable of flexibly solving at a high speed the problem of synchronization wait when a plurality of tasks are generated and a method of the same.
2. Description of the Related Art
For example, known in the art is a multiple instruction multiple datastream (MIMD) type multi-processor system in which a plurality of processor elements (PE) have independent program counters and execute the processing while mutually communicating via a common bus.
Such a multi-processor system is predicated on performing concurrent (parallel) multi-tasking and communicates between a processor element executing a main program trying to generate a task and a processor element at which a new task is generated. At this time, there are cases where the program which called up (generated) the task waits for synchronization until the called (generated) task is ended.
FIG. 15
is an overall view of the configuration of a general multi-processor system
1
.
As shown in
FIG. 15
, the multi-processor system
1
is comprised of four processor elements PE
12
, PE
13
, PE
14
, and PE
15
and an arbiter
16
for managing the synchronization of tasks connected via a common bus
11
.
The common bus
11
acts as a control line for transferring commands and other control signals among the processor elements PE
12
to PE
15
.
Further, in the multi-processor system
1
, the processor elements PE
12
, PE
13
, PE
14
, and PE
15
and a common or shared memory
17
are connected via a main bus
19
.
The common memory
17
is connected to an external memory (main memory) via an external terminal
18
.
Note that, as the configuration of the multi-processor system for realizing synchronization of multi-tasking, there are various types other than the configuration shown in FIG.
15
.
For example, in the example shown in
FIG. 15
, a case where the synchronization of tasks is centrally managed by the arbiter
16
was shown, but it is also possible to not provide the arbiter
16
and impart a function for managing the synchronization of tasks to individual processor elements PE
12
to PE
15
.
FIG. 16
is a view for explaining a procedure for a program generating a task (i.e. program
25
) to wait for synchronization.
In the example shown in
FIG. 16
, the main program
25
operating on the processor element PE
12
generates a task
26
on the processor element PE
13
.
The processor elements PE
12
and PE
13
operate by executing commands described by the machine language inherent to the individual processors.
It may be noted that it is also possible to generate the task and solve the synchronization even by using hardware sequential circuits.
It may also be note that, in the present specification, a case where the synchronization function is realized by commands will mainly be explained.
Turning to the problem to be solved by the invention, in the multi-processor system of the related art, it has been difficult to generate a plurality of tasks from the main program
25
shown in
FIG. 16
in the exact number desired for following reasons.
Namely, the multi-processor system executes the concurrent multi-tasking, but in this multi-task method, it is necessary to allocate a plurality of programs (tasks) to a plurality of processor elements PE.
Here, with multi-tasking assuming a single processor, the most general practice is to allocate a plurality of tasks to one processor element PE by time division such as by a time sharing system (TSS). Accordingly, it is sufficient to prepare only one task management table for the one processor element PE.
In many cases where this TSS method is adopted, an operating system such as Unix (Trade Mark of MIT) having a task switching mechanism is used.
Usually, the processor element PE frequently is not provided with a synchronization command particularly conscious of multi-tasking. Rather than a synchronization command, therefore a method is often adopted in which exception handling is generated through a timer or other external interruption event and as a result the tasks are switched. Further, in order to execute the switching of the tasks at a higher speed, hardware support is frequently provided inside the processor element PE, but basically the task switching function is realized by software.
Contrary to this, in the multi-processor system, when adopting the TSS method, it becomes necessary to provide a plurality of task management tables. Further, it is necessary to prepare a program for comprehensively managing these plurality of task management tables at a higher level than the programs for managing individual processor elements PE, so the operating system becomes considerably complex. For this reason, in the multi-processor system of the related art, it has been difficult to generate exactly the desired number of tasks from the main program
25
shown in FIG.
16
.
It is noted that, the operating system loaded in a multi-processor system is usually determined by the user using that multi-processor system.
There are also methods for realizing multi-tasking other than the TSS method. Applications to somewhat special purposes, for example, use of specific processor elements PE as co-processors, can be considered. Other than this, a method of permanently providing programs to be executed by co-processors, even if not fixing specific processor elements PE as co-processors, is very effective in certain fields. In any case, a mechanism for synchronization of tasks is necessary for a multi-processor system.
In the multi-processor systems in the research and prototype stage, in general, operating systems the same as that of a single processor are loaded in every processor element PE. By communicating among these processor elements PE, multi-tasking is achieved as a whole in many cases. In this case, the synchronization mechanism is used in part of the function of communication among the processor elements PE. Alternatively, a synchronization mechanism using a semaphore or other memory can be adopted.
However, in actuality, when it comes to the generation of tasks and the synchronization wait of the tasks, since in the end processing is performed by software in all cases, the response is bad, therefore this is applied at most to a case of executing rough parallel programs. Further, even in a system that can sufficiently generate a plurality of tasks, there is no decisive means for a solution to be found in these methods of waiting for tasks to end (i.e., a synchronization wait).
All combinations of conditions set, such as which task among the plurality of tasks generated from a main program is to be waited for, are possible if programming by software, but the overhead of time spent for judging these conditions becomes considerably large, so a high speed synchronization is not possible.
On the other hand, the conditions set are sometimes determined by hardware.
For example, a handshake synchronization wait system has been established between the microprocessor 8086 developed by Intel Co. of the U.S. and the coprocessor 8087 designed exclusively for that processor. When executing a command for an arithmetic operation of the main program on the processor 8086, the coprocessor 8087 automatically starts processing interpreting that command. Usually, a plurality of clock cycles has been considered necessary for the execution of an arithmetic operation. Accordingly, during this time, the processor 8086 sequentially executes the commands after that related command.
The main program contains a synchronization command after an appropriate number of commands from the task generation command. If the related arithmetic operation has been ended before the synchronization command is executed, the processor 8086 regards that the arithmetic operation is synchronized and proceeds with the execution of commands as it is. Alternatively, if the related arithmetic operation has not been ended before the synchronization command is executed, synchronization is waited for until the operation of the coproc
Donaghue Larry D.
Kananen, Esq. Ronald P.
Sony Corporation
LandOfFree
Parallel processing apparatus and method of the same does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel processing apparatus and method of the same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel processing apparatus and method of the same will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3110326