Modified computer architecture having coordinated deletion of corresponding replicated memory locations among plural computers

• US 7,844,665 B2
• Filed: 04/22/2005
• Issued: 11/30/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): Srivastava; Vivek
• Assistant Examiner(s): MIRZA, ADNAN M
• Application Number:
  US11/111,946
• Publication Number:
  US 20050262313A1
• Time in Patent Office: 2,048 Days
• Field of Search: 709/203, 709/204, 709/205, 709/238, 717/130
• US Class Current: 709/205
• CPC Class Codes: G06F 9/44563 Sharing
• CPC Class Codes: G06F 9/44594 Unloading

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. In addition, the initialization of JAVA language classes and objects is disclosed (162, 163) so all memory locations for all computers are initialized in the same manner. The finalization of JAVA language classes and objects is also disclosed (162, 163) so finalization only occurs when the last class or object present on all machines is no longer required. During initial program loading (75), or similar, instructions which result in the application program (50) acquiring (or releasing) a lock on a particular asset (50A, 50X-50Y) (synchronization) are identified. Additional instructions are inserted (162, 163) to result in a modified synchronization routine with which all computers are updated.

Claims

1. In a multiple computer system including a plurality of single computers interconnected via a communications link, a method of operating an application program having code written to include a plurality of threads all intended to execute on and reference a single independent computer having a single central processing unit (CPU) or symmetric multiple processing units and a single independent local memory that is not shared with any other computer of said plurality of single computers, said method comprising the steps of:

(a) allocating said plurality of application program code threads amongst said plurality of interconnected single computers so that at least a portion of the application program including at least one first thread of said application program code is allocated a first particular one of said plurality of single computers for execution thereon and at least one second thread of said application program code is allocated a second particular one of said plurality of single computers for execution thereon;

(b) operating each single computer so that the memory locations of its single independent local memory are only addressable by the thread or threads allocated for execution thereon;

(c) executing said allocated application program code thread or threads by those single computers having an application program code thread or threads allocated thereto for execution;

(d) creating, either before or during said executing, a like plurality of memory locations each of the plurality of single computers and each having a name, wherein the initial memory location value contents of each of said named memory locations is the same when created;

(e) storing, during or after execution, by said single computer in its single independent local memory, an original version of each application memory value addressable by execution of said thread or threads allocated thereto;

(f) communicating an update via said communications link, a replica version of each new original version of each application memory value which has overwritten a previous corresponding application memory value as a consequence of execution of said thread or threads on any said single computer, to the single independent local memory of all other ones of said plurality of single computers; and

(g) storing in said single independent local memory of all of said plurality of single computers said communicated updated replica version of each and every application memory value;

(h) locking memory locations in each said single computer wherein any single computer wishing to utilize a memory location therein acquires an authorizing lock within the multiple computer system which permits said utilization of said memory location and which prevents all the other of the single computers from utilizing their corresponding memory location until said authorizing lock is relinquished;

(i) the stored application memory values, including said original versions and said replica versions, of all said single computers thereby remaining, subject to a communications link updating transmission delay, identical without any of said single computers addressing the independent local memory of any other one of said plurality of single computers during execution of their allocated thread or threads; and

(j) deleting all said original versions and replica versions of said identical memory locations collectively when all of said plurality of single computers no longer need to refer to their corresponding memory location.

2. The method as claimed in claim 1, comprising the further step of, if a portion of said application program running on one of said single computers creates a memory location in that single computer, then the created object is propagated to all of the other of said plurality of single computers via said communications network.

3. The method as claimed in claim 2 including the further step of:

modifying said application program before, during or after loading by inserting an initialization routine to modify each instance at which said application program creates a memory location, said initialization routine propagating every object created by one single computer to all said other single computers.

4. A method as claimed in claim 1, including the further step of:

providing each said single computer with a distributed run time means to communicate between said plurality of single computers via said communications network.

5. A method as claimed in claim 4 including the further step of:

providing a shared table accessible by each said distributed run time means and in which is stored the identity of any of said plurality of single computers which no longer requires to access a memory location, together with the identity of the memory location.

6. A method as claimed in claim 5 including the further step of:

associating a counter means with said shared table, said counter means storing a count of the number of said single computers which no longer require to access said memory location.

7. A method as claimed in claim 6 including the further step of:

providing an additional computer on which said shared program does not run and which hosts said shared table and counter, said additional computer being connected to said communications network.

8. A method as claimed in claim 4 including the further step of:

providing a shared table accessible by each said distributed run time means and in which is stored the identity of any or said single computers which currently has to access a memory location, together with the identity of the memory location.

9. A method as claimed in claim 8 including the further step of:

associating a counter means with said shared table, said counter means storing a count of the number of said single computers which seek access to said memory location.

10. A method as claimed in claim 9 including the further step of:

providing an additional computer on which said shared program does not run and which hosts said shared table and counter means storing said count, said additional computer being connected to said communications network.

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

12. The method as claimed in claim 11, 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.

13. The method as claimed in claim 12, wherein the updating communication is performed via a slow network communications link or path.

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

15. The method as claimed in claim 13, wherein the communications link includes a communications link over the Internet.

16. The method as claimed in claim 13, wherein the slow network is a 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.

17. The method as claimed in claim 11, wherein the communications between the single computers although routed through the single computer machine hardware are controlled by an individual distributed runtime (DRT) within each single computer, the distributed runtime coordinating particular communications between the plurality of single computers.

18. The method as claimed in claim 17, wherein the DRT coordinates communications between the single computers that is transport, protocol, and communications link independent.

19. The method as claimed in claim 11, wherein:

all reading of memory locations or data is satisfied locally from the single computer local independent memory because a current value of all (or some subset of all) 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 all (or some subset of all) 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.

20. A multiple computer system comprising:

a plurality of single computers interconnected via a communications link;

each of said plurality of single computers;

(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 is adapted to store and execute at least one thread of a similar copy of an application program having code written to operate only on a single computer system, the code including a plurality of threads all intended to execute in cooperation with a single memory;

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;

(i) means for allocating or receiving an allocation of 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) means for 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) a memory storage for 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;

(iv) means for 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, identical;

(v) lock means applicable to each said single computer wherein any single computer wishing to utilize a memory location therein acquires an authorizing lock from said lock means which permits said utilization of said memory location and which prevents all the other of said single computers from utilizing their corresponding memory location until said authorizing lock is relinquished; and

(vi) means for collectively deleting all of said identical memory locations when each of said plurality of computers no longer needs to refer to their corresponding memory location.

21. The system as claimed in claim 20, wherein said lock means includes an acquire lock routine and a release lock routine, and both said routines are included in modifications made to said application program running on all said computers.

22. The system as claimed in claim 21 wherein said lock means further includes a shared table listing said named memory locations in use by any said computer, a lock status for each said memory location, and a queue of any pending lock acquisitions.

23. The system as claimed in claim 22 wherein said lock means is located within an additional computer not running said application program and connected to said communications network.

24. The system as claimed in claim 20, wherein each said computer includes a distributed run time means with the distributed run time means of each said computer able to communicate with all other computers so that if a portion of said application program(s) running on one of said computers creates a memory location in that computer then the created memory location is propagated by the distributed run time means of said one computer to all the other computers.

25. The system as claimed in claim 20, wherein each said computer includes a distributed run time means with the distributed run time means of each said computer able to communicate with all other computers so that if a portion of said application program(s) running on one of said computers no longer needs to refer to a memory location in that computer then the identity of the unreferenced memory location is transmitted by the distributed run time means of said one computer to a shared table accessible by all the other computers.

26. The system as claimed in claim 20, wherein each said application program is modified before, during, or after loading by inserting an initialization routine to modify each instance at which said application program creates a memory location, said initialization routine propagating every object newly created by one computer to all said other computers.

27. The system as claimed in claim 26 wherein the application program is modified in accordance with a procedure selected from the group of procedures consisting of re-compilation at loading, pre-compilation prior to loading, compilation prior to loading, just-in-time compilation, and re-compilation after loading and before execution of the relevant portion of application program.

28. The system as claimed in claim 26 wherein said modified application program is transferred to all said computers in accordance with a procedure selected from the group consisting of master/slave transfer, branched transfer and cascaded transfer.

29. The system as claimed in claim 20, wherein the local memory capacity allocated to the, or each, said application program is identical and the total memory capacity available to the, or each, said application program is said allocated memory capacity.

30. The system as claimed in claim 29 wherein all said computers include a distribution update means each of which communicates via said communications link at a data transfer rate which is less than the local memory read rate.

31. The system as claimed in claim 30 wherein at least some of said computers are manufactured by different manufacturers and/or have different operating systems.

32. The system as in claim 20, wherein the communications link comprises an Internet network communications link.

33. The system as claimed in claim 20, wherein the means for communicating includes means for executing an updating propagation routine.

34. The system as claimed in claim 33, wherein the means for executing the updating propagation routine includes means for 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.

35. The system as claimed in claim 34, wherein the means for updating communication is operative to perform the updating via a slow network communications link or path.

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

37. The system as claimed in claim 35, wherein the communications link includes a communications link over the Internet.

38. The system as claimed in claim 35, wherein the slow network is a 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.

39. The system as claimed in claim 33, wherein the communications between the single computers although routed through the single computer machine hardware are controlled by an individual distributed runtime (DRT) within each single computer, the distributed runtime coordinating particular communications between the plurality of single computers.

40. The system as claimed in claim 39, wherein the DRT coordinates communications between the single computers that is transport, protocol, and communications link independent.

41. The multiple computer system as claimed in claim 33, wherein:

all reading of memory locations or data is satisfied locally from the single computer local independent memory because a current value of all (or some subset of all) 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 all (or some subset of all) 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.

42. A computer program product stored on a tangible machine-readable medium and including executable instructions for, in a multiple computer system including a plurality of single computers interconnected via a communications link, implementing a method of operating an application program having code written to include a plurality of threads all intended to execute on and reference a single independent computer having a single central processing unit (CPU) or symmetric multiple processing units and a single independent local memory that is not shared with any other computer of said plurality of single computers, said executable instruction performing a method comprising:

(a) allocating said plurality of application program code threads amongst said plurality of interconnected single computers so that at least a portion of the application program including at least one first thread of said application program code is allocated a first particular one of said plurality of single computers for execution thereon and at least one second thread of said application program code is allocated a second particular one of said plurality of single computers for execution thereon;

(b) operating each single computer so that the memory locations of its single independent local memory are only addressable by the thread or threads allocated for execution thereon;

(c) executing said allocated application program code thread or threads by those single computers having an application program code thread or threads allocated thereto for execution;

(d) creating, either before or during said executing, a like plurality of memory locations each of the plurality of single computers and each having a name, wherein the initial memory location value contents of each of said identically named memory locations is the same when created;

(e) storing, during or after execution, by said single computer in its single independent local memory, an original version of each application memory value addressable by execution of said thread or threads allocated thereto;

(f) communicating an update via said communications link, a replica version of each new original version of each application memory value which has overwritten a previous corresponding application memory value as a consequence of execution of said thread or threads on any said single computer, to the single independent local memory of all other ones of said plurality of single computers; and

(g) storing in said single independent local memory of all of said plurality of single computers said communicated updated replica version of each and every application memory value;

(h) locking memory locations in each said single computer wherein any single computer wishing to utilize a memory location therein acquires an authorizing lock within the multiple computer system which permits said utilization of said memory location and which prevents all the other of the single computers from utilizing their corresponding memory location until said authorizing lock is relinquished; and

(i) the stored application memory values, including said original versions and said replica versions, of all said single computers thereby remaining, subject to a communications link updating transmission delay, identical without any of said single computers addressing the independent local memory of any other one of said plurality of single computers during execution of their allocated thread or threads; and

(j) deleting all said original versions and replica versions of said memory locations collectively when all of said plurality of single computers no longer need to refer to their corresponding memory location.

43. The computer program product as claimed in claim 42, wherein:

the communicating includes executing an updating propagation routine, 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, and the updating communication is performed via a slow Internet network communications link or path 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;

each of said plurality of single computers receiving an update communication from the network, writes the memory location value(s) received to the local independent memory location corresponding to the identified memory location received;

the communications between the single computers although routed through the single computer machine hardware are controlled by an individual distributed runtime (DRT) within each single computer, the distributed runtime coordinating particular communications between the plurality of single computers, and the DRT coordinates communications between the single computers that is transport, protocol, and communications link independent;

all reading of memory locations or data is satisfied locally from the single computer local independent memory because a current value of all (or some subset of all) 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 all (or some subset of all) memory locations is stored on the single computer carrying out the processing of the code threads which generates the demand to write to memory; and

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.

44. The computer program product as claimed in claim 42, wherein:

the code is written to include a plurality of threads all intended to execute on and reference a single independent computer having a single central processing unit (CPU) or symmetric multiple processing units and a single independent local memory that is not shared with any other computer of said plurality of single computers.