Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-07-18
2001-03-06
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06199093
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a processor allocating method and a processor allocating system used in a multiprocessor system for allocating processors to tasks executed in a parallel mode in this multiprocessor system, and also relates to a storage medium capable of storing a processor allocation program.
2. Description of the Related Art
In a multiprocessor system, a process operation of a single program is subdivided into a plurality of tasks, and then the plural tasks are executed by a plurality of processors in a parallel manner, so that turn around time of this program may be reduced. These tasks are called “parallel tasks”. To shorten the turn around time of the program constituted by the parallel tasks, it is important to allocate the processors to the respective tasks in a high efficiency.
On the other hand, when a process operation of a single program is subdivided into a plurality of tasks to be executed, communications must be carried out among the respective tasks. It is also important for improving process performances to reduce overheads required for these task communications.
Generally speaking, communication times established among these processors for constituting a multiprocessor are different from each other, depending upon connection types among processors and physical distances among processors.
For instance, in such a multiprocessor system arranged by coupling a plurality of nodes with each other via a network, which are constructed of plural processors coupled by shared memories, communication speeds among the processors connected via the network are very slower than those among the processors connected via the shared memories.
In a hipercube-connected multiprocessor system, when each of tasks for constituting parallel tasks is executed on a multiprocessor, one scheduling method is described in Japanese Kokai Patent Application No. 2-226358. That is, the respective tasks are allocated to the processors of the multiprocessor system in order to reduce the overhead of the communication process operations executed among the processors.
In this scheduling method, the tasks are allocated to the processors in such a manner that the coincident degrees between the structures of the task graphs for representing the relationship among the tasks and the structures of the hypercubes become maximum.
However, the multiprocessor system to which this conventional scheduling method can be applied is limited only to the hypercube-connected type multiprocessor system. Therefore, there is a problem that this scheduling method cannot be applied to any other types of multiprocessor systems.
As known in the art, the communication times would be greatly varied in accordance with the communication amounts executed among the processors. Since the processors are allocated to the tasks without considering the communication amounts among the tasks, there is another problem. That is, very lengthy communication time among the tasks is required when two processors whose communication times become very long are allocated to such two tasks that data communication amounts between these two tasks are very large.
SUMMARY AND OBJECTS OF THE INVENTION
An object of the present invention is to shorten turn around time of a program constituted by parallel tasks, and executed in a multiprocessor system.
Another object of the present invention is to allocate a processor to each task of the parallel tasks in a multiprocessor system in such a manner that communication time required to perform a data communication among the tasks becomes minimum.
A further object of the present invention is to allocate a processor to each task of the parallel tasks in a multiprocessor system in such a way that data communication time per unit data amount becomes the shortest time.
A still further object of the present invention is to realize such a multiprocessor system that an amount of data communicated among tasks can be automatically collected.
A first processor allocating apparatus of the present invention, in a multiprocessor system capable of executing a plurality of tasks in a parallel manner, is comprised of:
task schedule means for allocating such a processor to a task to which the processor has not yet been allocated, among said plural tasks executed in the parallel manner, in such a manner that data communication time between the processor to be allocated and another processor already allocated to any of the plural tasks becomes minimum.
A second processor allocating apparatus of the present invention, in a multiprocessor system capable of executing a plurality of tasks in a parallel manner, is comprised of:
task schedule means for allocating such a processor to a task to which the processor has not yet been allocated, among said plural tasks executed in the parallel manner, in such a manner that data communication time per unit data between the processor to be allocated and another processor already allocated to any of the plural tasks becomes minimum.
A third processor allocating apparatus of the present invention, in a multiprocessor system capable of executing a plurality of tasks in a parallel manner, is comprised of:
task schedule means for allocating such a processor to a task to which the processor has not yet been allocated, among said plural tasks executed in the parallel manner, in such a manner that data communication time per unit data between the processor to be allocated and another processor already allocated to any of the plural tasks is multiplied by an amount of data communicated between said task and another task to which any of the processors has already been allocated to calculate communication time required for the data communication, and then said communication time required for the data communication becomes minimum.
A fourth processor allocating apparatus of the present invention, in a multiprocessor system capable of executing a plurality of tasks in a parallel manner, is comprised of:
compile means for compiling a source program in which said plurality of tasks executed in the parallel manner in said multiprocessor are defined to thereby produce a object program; and
communication amount among tasks measuring object program means for storing therein an amount of data communicated between each of said plural tasks executed in the parallel manner and another tasks.
A fifth processor allocating apparatus of the present invention, according to a first processor allocating apparatus, is further comprised of:
compile means for compiling a source program in which said plurality of tasks executed in the parallel manner in said multiprocessor are defined to thereby produce a object program.
A sixth processor allocating apparatus of the present invention, according to a second processor allocating apparatus, is further comprised of:
compile means for compiling a source program in which said plurality of tasks executed in the parallel manner in said multiprocessor are defined to thereby produce a object program.
A seventh processor allocating apparatus of the present invention, according to a third processor allocating apparatus, is further comprised of:
compile means for compiling a source program in which said plurality of tasks executed in the parallel manner in said multiprocessor are defined to thereby produce a object program; and
communication amount among tasks measuring object program means for storing therein an amount of data communicated between each of said plural tasks executed in the parallel manner and another task.
An eighth processor allocating apparatus of the present invention, according to a fourth processor allocating apparatus is characterized by that:
said communication amount among tasks measuring object program means seeks a task communication command within each of said plural tasks executed in the parallel manner, and stores therein an amount of data communicated by said task with another task in response to said task communication command.
A ninth processor allocating apparatus of the present invention,
Banankhah Majid
NEC Corporation
Young & Thompson
LandOfFree
Processor allocating method/apparatus in multiprocessor... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processor allocating method/apparatus in multiprocessor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor allocating method/apparatus in multiprocessor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463271