Computer architecture and method of operation for multi-computer distributed processing with replicated memory

• US 7,860,829 B2
• Filed: 03/02/2009
• Issued: 12/28/2010
• Est. Priority Date: 04/23/2004
• Status: Active Grant

• Current Assignee: Waratek Limited (Waratek Holdings Ltd.)
• Original Assignee: Waratek Pty Limited
• Inventors: Holt, John M.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Badawi; Sherief
• Application Number:
  US12/396,446
• Publication Number:
  US 20090235033A1
• Time in Patent Office: 666 Days
• Field of Search: 707/610, 707/617, 707/623, 707/615, 707/620
• US Class Current: 707/617
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

The present invention discloses a modified computer architecture (50, 71, 72) which enables an applications program (50) to be run simultaneously on a plurality of computers (M1, . . . Mn). Shared memory at each computer is updated with amendments and/or overwrites so that all memory read requests are satisfied locally. During initial program loading (75), or similar, instructions which result in memory being re-written or manipulated are identified (92). Additional instructions are inserted (103) to cause the equivalent memory locations at all computers to be updated.

Claims

1. A method of operating, on a multiple computer system comprising a plurality of computers, a stored application program having code written to operate only on a single computer system comprising a single computer having a single CPU or a single computer having symmetric multiple processors, said code including a plurality of threads all intended to execute in cooperation with a single memory, wherein:

all of said plurality of computers are interconnected via a communications link;

each one of said plurality of computers is independent of the other ones of said plurality of computers, has a single independent local memory which is not shared with any other computer of said plurality of computers and accessible only by the corresponding portion of said application program executing on that single computer, has a substantially similar copy of said application program code stored therein, and has at least one thread;

each said single independent local memory has memory locations only addressable and accessible by the thread or threads of the corresponding computer executing the corresponding copy of said application program code, and each said independent local memory has stored therein all application memory values arising from the execution of all said threads of all said plurality of computers;

said method of operating comprising the steps of;

(i) allocating said plurality of threads of said stored application program code amongst said multiple computers so that at least a portion of the application including at least one thread of said application program code is allocated to a corresponding one of said multiple computers for execution thereon by one or more threads of that one of said multiple computers;

(ii) substantially simultaneously executing said application program code thread or threads by those ones of said multiple computers having an application program code thread or threads allocated thereto;

(iii) storing in said single independent local memory of each said computer a replica of each and every application memory value addressable by each and every said thread of each and every one of said plurality of computers; and

(iv) communicating via said communications link each new application memory value which has overwritten a previous corresponding value as a consequence of execution of said application program code on any one of said single computers, to the independent local memory of all other ones of said computers, whereby the values of said replica application memory values of all said computers remain, subject to an updating transmission delay, substantially identical;

(v) modifying each said copy of said application program code prior to storing same in each said single independent local memory;

wherein said modifying step (v) further comprises;

(a) detecting instructions which share memory records utilizing one of said single computers;

(b) listing all such shared memory records and providing a naming tag for each listed memory record;

(c) detecting those instructions which write to, or manipulate the contents of, any of said listed memory records; and

(d) generating an updating propagation routine corresponding to each said detected write or manipulate instruction, said updating propagation routine forwarding the re-written or manipulated contents and name tag of each said re-written or manipulated listed memory record to all of the others of said single computers.

2. The method as claimed in claim 1, further comprising the step of:

(v) during execution of said substantially similar copy of said application program code by each said single computer, satisfying all read requests from each said single computer from the corresponding single independent local memory of that computer.

3. The method as claimed in claim 1, further comprising the step of:

(v) reading in each said single computer said substantially similar copy of said application program code from said single independent local memory of each said computer.

4. The method as claimed in claim 1, further comprising the step of:

(v) storing said substantially similar copy of said application program code in a compiled object code format.

5. The method as claimed in claim 1, further comprising the step of:

(v) storing said substantially similar copy of said application program code in an uncompiled source code format.

6. The method as claimed in claim 1, further comprising the step of:

(v) modifying each said copy of said application program in the same way for each said single computer.

7. The method as claimed in claim 1, further comprising the step of:

(x) modifying each said copy of said application program in a different way for each said single computer.

8. The method as claimed in claim 1, wherein the substantially similar copy of the application program comprises a copy of the application program with the same or substantially the same or similar modifier applied to the copy of the application program.

9. A multiple computer system comprising a plurality of computers and on which is executed an application program having code written to operate only on a single computer system comprising a single computer having a single CPU or a single computer having symmetric multi-processors, said code including a plurality of threads all intended to execute in cooperation with a single memory, wherein:

all of said plurality of computers are interconnected via a communications link;

each one of said plurality of computers is independent of the other ones of said plurality of computers, has a single independent local memory which is not shared with any other computer of said plurality of computers, has a substantially similar copy of said application program code stored therein, and has at least one thread;

each said single independent local memory has memory locations only addressable and accessible by the thread or threads of the corresponding computer executing the corresponding copy of said application program code, and each said independent local memory has stored therein all application memory values arising from the execution of all said threads of all said plurality of computers;

said plurality of threads of said stored application program code being allocated amongst said multiple computers so that at least a portion of the application program including at least one thread of said application program code is allocated to a corresponding one of said multiple computers for substantially simultaneous execution thereon by one or more threads of that one of said multiple computers;

said single independent local memory of each said computer stores a replica of each and every application memory value addressable by each and every said thread and each and every one of said plurality of computers; and

each new application memory value which is written over a previous corresponding value that has a consequence of execution of said application program code of any one of said single computers, is communicated via said communications link to the single independent local memory of all other ones of said computers, so that the values of said replica application memory values of all said computers remain, subject to an updating transmission delay, substantially identical;

modifying each said copy of said application program code prior to storing same in each said single independent local memory;

wherein said modifying step further comprises;

(a) detecting instructions which share memory records utilizing one of said single computers;

(b) listing all such shared memory records and providing a naming tag for each listed memory record;

(c) detecting those instructions which write to, or manipulate the contents of, any of said listed memory records; and

(d) generating an updating propagation routine corresponding to each said detected write or manipulate instruction, said updating propagation routine forwarding the re-written or manipulated contents and name tag of each said re-written or manipulated listed memory record to all of the others of said single computers.

10. The system as claimed in claim 9, wherein each said single computer during execution of said substantially similar copy of said application program code satisfies all read requests from that single computer from the corresponding single independent local memory of that single computer.sub.

11. The system as claimed in claim 9, wherein each said substantially similar copy of said application program code is stored in a compiled object code format in the corresponding single independent local memory.

12. The system as claimed in claim 9, wherein each said substantially similar copy of said application program code is stored in an uncompiled source code format in the corresponding single independent local memory.

13. In a multiple computer system including a plurality of single computers interconnected via a communications link, wherein each single computer:

(a) has a single central processing unit (CPU) or symmetric multiple processing units, (b) a single independent local memory which is not shared with any other computer of said plurality of single computers, and (c) that is independent of the other ones of said plurality of single computers;

each one of said plurality of single computers has a substantially similar copy of an application program having code written to operate only on a single computer system stored therein, the code including a plurality of threads all intended to execute in cooperation with a single memory, and has at least one thread; and

each said single independent local memory has memory locations only addressable and accessible by the thread or threads of the corresponding single computer executing the corresponding copy of said application program code, and each said independent local memory has stored therein all application memory values arising from the execution of all said threads of all said plurality of computers;

a method of operating said stored application program comprising the steps of;

(i) allocating said plurality of threads of said stored application program code amongst said plurality of single computers so that at least a portion of the application program including at least one thread of said application program code is allocated to a corresponding one of said plurality of single computers for execution thereon by one or more threads of that one of said plurality of single computers;

(ii) substantially simultaneously executing said application program code thread or threads by those ones of said plurality of single computers having an application program code thread or threads allocated thereto;

(iii) storing in said single independent local memory of each said single computer a replica of each and every application memory value addressable by each and every said thread of each and every one of said plurality of computers; and

(iv) communicating via said communications link each new application memory value which has overwritten a previous corresponding value as a consequence of execution of said application program code on any one of said single computers, to the single independent local memory of all other ones of said plurality of single computers, so that the values of said replica application memory values of all said single computers remain, subject to an updating transmission delay, substantially identical;

(v) modifying each said copy of said application program code prior to storing same in each said single independent local memory;

wherein said modifying step (v) further comprises;

(a) detecting instructions which share memory records utilizing one of said single computers;

(b) listing all such shared memory records and providing a naming tag for each listed memory record;

(c) detecting those instructions which write to, or manipulate the contents of, any of said listed memory records; and

(d) generating an updating propagation routine corresponding to each said detected write or manipulate instruction, said updating propagation routine forwarding the re-written or manipulated contents and name tag of each said re-written or manipulated listed memory record to all of the others of said single computers.

14. The method as claimed in claim 13, wherein the communicating includes executing an updating propagation routine.

15. The method as claimed in claim 14, wherein executing the updating propagation routine includes communicating the identity of updated, changed, or manipulated memory location, and the updated, manipulated or changed value(s) or content(s) of the manipulated memory location.

16. The method as claimed in claim 14, wherein each of said plurality of single computers receiving an update communication from a network, writes the memory location value(s) received to the local independent memory location corresponding to the identified memory location received.

17. The method as claimed in claim 16, wherein the network is a slow network having a communications speed of operation that is an order of magnitude slower than the speed of operation of the bus on the single computers.

18. The method as claimed in claim 14, wherein:

all reading of memory locations or data is satisfied locally from the single computer local independent memory because a current value of at least a portion of memory locations is stored on the single computer carrying out the processing of the code threads which generates the demand to read from memory; and

all writing of memory locations or data is satisfied locally from the single computer local independent memory because a current value of at least a portion of memory locations is stored on the single computer carrying out the processing of the code threads which generates the demand to write to memory;

wherein the demand to write or rewrite memory being relatively lower than the demand to read from memory, so that memory locations can be continually updated at a relatively low speed via a slow and inexpensive commodity network, yet this sufficient to meet the application program demand for writing to memory.