Lan based loosely coupled large grain parallel processing method
First Claim
Patent Images
1. A simulated parallel processing system, comprising:
- a common file server having a common shared memory containing system synchronization and queue controls;
a shared resource having the instructions for performing predetermined operations of a task and controlling means, comprising a logical partition control file including virtual identification generating means, for controlling and synchronizing the accesses of the shared resource, said task predeterminately subdivided into N individual subtasks and an unassigned compilation task, said task may be formed from N multiples of the same subtask operated on by different computers or from N different portions of said task, and each subtask assigned to a unique virtual identification, wherein said compilation task adds the N individual results of each of the subtasks to form one final result of the task, said resource stored in said common memory;
a plurality of copies of the instructions for performing the task, the copies being replicas of each other and available in said common file server;
a plurality of asynchronously and parallelly operative N computers not having a common internal bus, each computer having a local memory, each computer connected to the common file server for accessing the resource and copying one copy of said instructions into the local memory, each computer for individually performing the individual subtask assigned to that computer, in parallel, in accordance with the controlling means;
loosely coupled interconnection means for coupling each of said plurality of computers in a parallel network and coupling each computer to said common file server for providing each computer access to said plurality of copies of said instructions for performing the respective individual subtask;
said controlling means, coupled to said resource and responsive to performance by one of said computers on said resource of one of said instructions in a given copy, for preventing access of all other computers for preventing performance of said-- instruction until the instruction is performed by said one computer on the given copy to form a time-ordered sequence, for coordinating cooperation of said plurality of computers performing said predetermined operations, wherein the controlling means comprises;
a first semaphore file for assigning a unique virtual identification for each of said plurality of computers, immediately after each computer has copied one copy of said instructions and attempts to start performing said instructions, and for preventing processing of the same virtual identification for any two computers, wherein the assignment is processed in a time-ordered sequence depending on which computer accesses said first semaphore file first, wherein the first computer accessing said first semaphore file is assigned the virtual identification associated with being the first computer, the second computer accessing said first semaphore file is assigned the virtual identification associated with being the second computer, and so on in said time-ordered sequence, until the Nth computer accessing said first semaphore file is assigned the virtual identification associated with being the Nth computer;
memory allocation means for predeterminately apportioning said common memory into dedicated sub-memory portions each correspondingly associated with each of said unique virtual identification of each computer for storing the individual results performed by each computer;
said task predeterminately subdivided into subtasks present in each computer, wherein each computer has a copy of the instructions for performing the individual subtask-- assigns itself the unique virtual identification according to the virtual identification of each computer assigned as controlled by said first semaphore file, for later performance of said subtask, having the same corresponding unique virtual identification, by each computer in parallel with each other;
a second semaphore file for controlling the start of subtask processing of subtask result, of each of said plurality of computers, wherein the first computer, the second computer, and up to and including the N-1th computer each has to wait till the Nth computer has been assigned the virtual identification associated with being the Nth computer before allowing each of the computers to all synchronously with all other computers start performing its assigned subtask, in parallel, to generate the individual subtask result and ending performance by accessing said dedicated sub-memory portion to place the individual result of the predeterminately associated subtask onto said dedicated sub-memory portion; and
a third semaphore file for assigning said compilation task and controlling post-performance de-synchronization of said plurality of computers for allowing only the last computer accessing its dedicated sub-memory portion to complete performance of said task by compiling all of the individual results located individually in each dedicated sub-memory portion to form one final result for said task, on said file server, wherein the assignment is processed in the time-ordered sequence depending on which computer accesses its said dedicated sub-memory portion first, wherein the first computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the first computer, the second computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the second computer, and so on in said time-ordered sequence, until the second-to-last computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the second-to-last computer and the Nth computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the last computer, the first computer to complete its subtask and up to and including the second-to-last computer each terminates its subtask, and only the last computer is assigned said compilation task and said last computer completes both its assigned subtask and said compilation task.
1 Assignment
0 Petitions
Accused Products
Abstract
A parallel processing system (10) is provided to logically divide (68) a task into subtasks that can be performed simultaneously by a plurality of computers (1-4) loosely coupled in parallel via a loosely coupled interconnection (11). A file server (9) is connected to the loosely coupled interconnection (11) for sharing memory among the plurality of computers (1-4). For coordinating the cooperation of the plurality of computers (104) performing these subtasks, a controlling methodology (38) is taught.
95 Citations
12 Claims
-
1. A simulated parallel processing system, comprising:
-
a common file server having a common shared memory containing system synchronization and queue controls; a shared resource having the instructions for performing predetermined operations of a task and controlling means, comprising a logical partition control file including virtual identification generating means, for controlling and synchronizing the accesses of the shared resource, said task predeterminately subdivided into N individual subtasks and an unassigned compilation task, said task may be formed from N multiples of the same subtask operated on by different computers or from N different portions of said task, and each subtask assigned to a unique virtual identification, wherein said compilation task adds the N individual results of each of the subtasks to form one final result of the task, said resource stored in said common memory; a plurality of copies of the instructions for performing the task, the copies being replicas of each other and available in said common file server; a plurality of asynchronously and parallelly operative N computers not having a common internal bus, each computer having a local memory, each computer connected to the common file server for accessing the resource and copying one copy of said instructions into the local memory, each computer for individually performing the individual subtask assigned to that computer, in parallel, in accordance with the controlling means; loosely coupled interconnection means for coupling each of said plurality of computers in a parallel network and coupling each computer to said common file server for providing each computer access to said plurality of copies of said instructions for performing the respective individual subtask; said controlling means, coupled to said resource and responsive to performance by one of said computers on said resource of one of said instructions in a given copy, for preventing access of all other computers for preventing performance of said-- instruction until the instruction is performed by said one computer on the given copy to form a time-ordered sequence, for coordinating cooperation of said plurality of computers performing said predetermined operations, wherein the controlling means comprises; a first semaphore file for assigning a unique virtual identification for each of said plurality of computers, immediately after each computer has copied one copy of said instructions and attempts to start performing said instructions, and for preventing processing of the same virtual identification for any two computers, wherein the assignment is processed in a time-ordered sequence depending on which computer accesses said first semaphore file first, wherein the first computer accessing said first semaphore file is assigned the virtual identification associated with being the first computer, the second computer accessing said first semaphore file is assigned the virtual identification associated with being the second computer, and so on in said time-ordered sequence, until the Nth computer accessing said first semaphore file is assigned the virtual identification associated with being the Nth computer; memory allocation means for predeterminately apportioning said common memory into dedicated sub-memory portions each correspondingly associated with each of said unique virtual identification of each computer for storing the individual results performed by each computer; said task predeterminately subdivided into subtasks present in each computer, wherein each computer has a copy of the instructions for performing the individual subtask-- assigns itself the unique virtual identification according to the virtual identification of each computer assigned as controlled by said first semaphore file, for later performance of said subtask, having the same corresponding unique virtual identification, by each computer in parallel with each other; a second semaphore file for controlling the start of subtask processing of subtask result, of each of said plurality of computers, wherein the first computer, the second computer, and up to and including the N-1th computer each has to wait till the Nth computer has been assigned the virtual identification associated with being the Nth computer before allowing each of the computers to all synchronously with all other computers start performing its assigned subtask, in parallel, to generate the individual subtask result and ending performance by accessing said dedicated sub-memory portion to place the individual result of the predeterminately associated subtask onto said dedicated sub-memory portion; and a third semaphore file for assigning said compilation task and controlling post-performance de-synchronization of said plurality of computers for allowing only the last computer accessing its dedicated sub-memory portion to complete performance of said task by compiling all of the individual results located individually in each dedicated sub-memory portion to form one final result for said task, on said file server, wherein the assignment is processed in the time-ordered sequence depending on which computer accesses its said dedicated sub-memory portion first, wherein the first computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the first computer, the second computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the second computer, and so on in said time-ordered sequence, until the second-to-last computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the second-to-last computer and the Nth computer accessing its said dedicated sub-memory portion is re-assigned the virtual identification associated with being the last computer, the first computer to complete its subtask and up to and including the second-to-last computer each terminates its subtask, and only the last computer is assigned said compilation task and said last computer completes both its assigned subtask and said compilation task. - View Dependent Claims (2, 3, 4)
-
-
5. In a simulated parallel processing networked computer system having N asynchronously and parallelly operative computers, not having a common internal bus but sharing a common file server, each computer having a local memory, a method of controlling and synchronizing the accesses of the shared resource using semaphores, the method comprising:
-
providing a common shared memory in the common file server; storing a shared resource in the common shared memory; providing instructions for performing predetermined operations of a task and a semaphoric method in the shared resource; predeterminately subdividing the task into N individual subtasks and an unassigned compilation task, wherein the task may be formed from N multiples of the same individual subtask or from N portions of the task and the compilation task adds the N individual results of each of the individual subtasks to form one final result of the task; assigning a unique virtual identification to each subtask; copying the instructions for performing the task to provide a plurality of copies in the common file server; copying one copy of the instructions into the local memory of each computer, each computer individually performing the subtask assigned to that computer, in accordance with the semaphoric method, the semaphoric method comprising; assigning a unique virtual identification for each of the plurality of computers, immediately after each computer has copied one copy of the instructions and attempts to perform the instructions; preventing processing of the same virtual identification for any two computers, wherein the assignment is processed in a time-ordered sequence depending on which computer accesses the shared resource first, wherein the first computer accessing the shared resource is assigned the virtual identification associated with being the first computer, the second computer accessing the shared resource is assigned the virtual identification associated with being the second computer, and so on in the time-ordered sequence, until the Nth computer accessing the shared resource is assigned the virtual identification associated with being the Nth computer; predeterminately apportioning the common memory into dedicated sub-memory portions each correspondingly associated with each of the unique virtual identification of each computer for storing individual results performed by each computer; each computer assigning itself the unique virtual identification according to the virtual identification of each computer assigned as controlled by the shared resource, for later performance of the subtask, having a corresponding unique virtual identification; controlling the start of subtask processing of individual subtask result, of each of said plurality of computers, wherein the first computer, the second computer, and up to and including the N-1th computer each has to wait till the Nth computer has been assigned the virtual identification associated with being the Nth computer; determining when the Nth computer has been assigned its virtual identification and then allowing each of the computers to start performing synchronously with all other computers its assigned subtask, in parallel, to generate the individual subtask result and ending performance by accessing the dedicated sub-memory portion to place the individual result of the predeterminately associated subtask onto the dedicated sub-memory portion; and assigning the compilation task and controlling post-performance de-synchronization of the plurality of computers by allowing only the last computer accessing its dedicated sub-memory portion to complete performance of the task by compiling all of the individual results located in each dedicated sub-memory portion to form one final result for the task, on the file server, wherein the assignment is processed in the time-ordered sequence depending on which computer accesses its dedicated sub-memory portion first, wherein the first computer accessing its dedicated sub-memory portion is re-assigned the virtual identification associated with being the first computer, the second computer accessing its dedicated sub-memory portion is re-assigned the virtual identification associated with being the second computer, and so on in the time-ordered sequence, until the second-to-last computer accessing its dedicated sub-memory portion is re-assigned the virtual identification associated with being the second-to-last computer and the Nth computer accessing its dedicated sub-memory portion is re-assigned the virtual identification associated with being the last computer, the first computer up to and including the second-to-last computer each terminates its subtask processing, and only the last computer is assigned the compilation task and the last computer completes both its individual subtask and the compilation task.
-
-
6. A method for operating a parallel processing session by a plurality of computers loosely coupled to a common data storage system, comprising the steps of:
-
executing, by each of the plurality of computers, an initiation procedure, the initiation procedure for a particular computer including the steps of; securing access, by the particular computer, to a control resource on the common data storage system; determining that the particular computer is a parent processor when the particular computer is the first of the plurality of computers to access the control resource during the parallel processing session; designating as participating processors for the parallel processing session, the computers of the plurality of computers securing access to the control resource; executing, by each of the participating processors, a subtask of a particular task; determining that a particular participating processor is a post-work processor when the particular participating processor is the last to complete its subtask; and performing, by the post-work processor, any activity needed to complete the particular task for the parallel processing session. - View Dependent Claims (7, 8, 9, 10, 11, 12)
-
Specification