Advanced contention detection

• US 20080126516A1
• Filed: 10/05/2007
• Published: 05/29/2008
• Est. Priority Date: 10/05/2006
• Status: Active Grant

• Current Assignee: Waratek Limited (Waratek Holdings Ltd.)
• Original Assignee: John M. Holt
• Inventors: Holt, John M.
• Granted Patent: US 8,086,805 B2
• Time in Patent Office: Days
• US Class Current: 709/218
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A multiple computer system is disclosed in which n computers (M1, M2 . . . Mn) each run a different portion of a single application program written to execute only on a single computer. The local memory of each computer is maintained substantially the same by updating all computers with every change made to addressed memory locations. Contention can arise when the same memory location is substantially simultaneously updated by two or more machines because of transmission delays and latency of the communications network interconnecting all the computers. Contention detection and resolution is disclosed. A count value (99) indicative of the cumulative number of times each memory location has been updated is utilized. Contention is indicated if the currently stored count value and the incoming updating count value are the same. A method of echo suppression and a method of echo rejection are disclosed. In particular incrementing the count value by two in the case of consecutive sequential transmission to the same memory location (D) is disclosed.

Claims

1. A multiple computer system including a multiplicity of computers, each of the multiplicity of computers interconnected via at least one communications network, and each executing a different portion of an application program written to execute substantially in its entirety on only a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory of said multiplicity of computers, and a system for handling contention in replica memory updating;

said system further comprising;

means for contention detection;

means for contention resolution coupled with or interoperable with said means for contention detection;

said contention detection and resolution utilizing a modified message format;

means for data consolidation;

means counter roll over; and

means performing said contention resolution with echo cancellation.

2. In a multiple computer system including a multiplicity of computers, each of the multiplicity of computers interconnected via at least one communications network, and each executing a different portion of an application program written to execute substantially in its entirety on only a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory of said multiplicity of computers;

a method for handling contention in replica memory updating comprising;

detecting contention;

resolving said detected contention;

using a modified message format and procedure in said detecting and resolving contention;

consolidating data;

operating a counter in a roll over manner; and

performing an echo cancellation procedure.

3. The method in claim 2, wherein said detecting contention comprises:

(i) utilizing an updating format for the signal or packet carrying out the updating, said format comprising the specific identifier of the memory location to be updated, the content with which said memory location is to be updated, and a resident updating count of the updating source, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating;

(ii) storing for each replicated memory location the updating count of the previously sent or received updating;

(iii) comparing the resident updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet; and

(iv) indicating a contention situation if the compared updating counts are the same.

4. The method in claim 2, wherein said resolving said detected contention comprises:

(a) utilizing an updating format for a signal or packet of information carrying out the updating, said updating format comprising a specific identifier of the replicated memory location to be updated, the content with which said replicated memory location is to be updated, a resident updating count of the updating source associated with the replicated memory location, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resident resolution value, and a resolution value of the updating source associated with the replicated memory location, said resolution value comprising a unique value to or of the updating source;

(b) storing for each receiving replicated memory location the updating count and resolution value of the previously received updating;

(c) comparing the presently resident updating count associated with the replicated memory location to be updated with the updating count of any currently received updating signal or packet; and

(d) actioning or not actioning the incoming signal or packet according to predetermined policies.

5. The method in claim 2, wherein said using a modified message format and procedure in said detecting and resolving contention comprises:

utilizing an updating format for the signal or packet carrying out the updating; and

said updating format comprising;

(i) the specific identifier of each memory location to be updated, (ii) the content with which said each memory location is to be updated, and (iii) at least one updating count of the updating source;

each said updating count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating; and

at least one resolution value of the updating source, each said resolution value comprising a unique value of the updating source.

6. The method in claim 2, wherein said consolidating data comprises:

(i) utilizing an updating signal/packet format comprising the specific address of the memory location to be updated, the content with which said memory location is to be updated, and an updating count indicative of the cumulative number of occasions on which said memory location will have been updated inclusive of the current updating;

(ii) storing for each said memory location the updating count of the previously received updating; and

(iii) from time to time on the occurrence of a predetermined condition, consolidating the stored updating count.

7. The method in claim 2, wherein said operating a counter in a roll over manner comprises:

(i) providing at least one further data bit in addition to, and associated with, each said counter;

(ii) changing the state of the further data bit of each counter if said counter reaches a predetermined maximum count value; and

(iii) modifying the comparison of the count values of sequentially received updating messages or signals in accordance with the state of the further data bit associated with each said received message and the state of the further data bit of the previously received message.

8. The method in claim 2, wherein said performing an echo cancellation procedure comprises:

(i) determining which source was the last to transmit in respect of a specific memory location; and

(ii) where the same source is to transmit sequentially in respect of the same memory location, incrementing said updating count for the second transmission by more than said predetermined number.

9. The method in claim 2, wherein said detecting contention comprises:

(i) utilizing an updating format for the signal or packet carrying out the updating, said format comprising the specific identifier of the memory location to be updated, the content with which said memory location is to be updated, and a resident updating count of the updating source, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating;

(ii) storing for each replicated memory location the updating count of the previously sent or received updating;

(iii) comparing the resident updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet; and

(iv) indicating a contention situation if the compared updating counts are the same.

10. The method in claim 9, wherein said resolving said detected contention comprises:

(a) utilizing an updating format for a signal or packet of information carrying out the updating, said updating format comprising a specific identifier of the replicated memory location to be updated, the content with which said replicated memory location is to be updated, a resident updating count of the updating source associated with the replicated memory location, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resident resolution value, and a resolution value of the updating source associated with the replicated memory location, said resolution value comprising a unique value to or of the updating source;

(b) storing for each receiving replicated memory location the updating count and resolution value of the previously received updating;

(c) comparing the presently resident updating count associated with the replicated memory location to be updated with the updating count of any currently received updating signal or packet; and

(d) actioning or not actioning the incoming signal or packet according to predetermined policies.

11. The method in claim 10, wherein said using a modified message format and procedure in said detecting and resolving contention comprises:

utilizing an updating format for the signal or packet carrying out the updating; and

said updating format comprising;

(i) the specific identifier of each memory location to be updated, (ii) the content with which said each memory location is to be updated, and (iii) at least one updating count of the updating source;

each said updating count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating; and

at least one resolution value of the updating source, each said resolution value comprising a unique value of the updating source.

12. The method in claim 11, wherein said consolidating data comprises:

(i) utilizing an updating signal/packet format comprising the specific address of the memory location to be updated, the content with which said memory location is to be updated, and an updating count indicative of the cumulative number of occasions on which said memory location will have been updated inclusive of the current updating;

(ii) storing for each said memory location the updating count of the previously received updating; and

(iii) from time to time on the occurrence of a predetermined condition, consolidating the stored updating count.

13. The method in claim 12, wherein said operating a counter in a roll over manner comprises:

(i) providing at least one further data bit in addition to, and associated with, each said counter;

(ii) changing the state of the further data bit of each counter if said counter reaches a predetermined maximum count value; and

(iii) modifying the comparison of the count values of sequentially received updating messages or signals in accordance with the state of the further data bit associated with each said received message and the state of the further data bit of the previously received message.

14. The method in claim 11, wherein said performing an echo cancellation procedure comprises:

(i) determining which source was the last to transmit in respect of a specific memory location; and

(ii) where the same source is to transmit sequentially in respect of the same memory location, incrementing said updating count for the second transmission by more than said predetermined number.

15. A system for handling contention in replica memory updating for a multiple computer system comprising a multiplicity of computers, each or the a multiplicity of computers interconnected via at least one communications network, and each executing a different portion of an application program written to execute on a only a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, said system for resolving contention in replica memory updating for a multiple computer system comprising:

at least one memory location having a specific location identifier;

a plurality of sources each of which can update said replicated memory location(s) and each of which utilizes an updating format for the signal or packet carrying out the updating, said updating format comprising;

(i) the specific identifier of each replicated memory location to be updated, (ii) the content with which said each replicated memory location is to be updated, and (iii) at least one updating count of the updating source, the or each said updating count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and (iv) at least one resolution value of the updating source, each said resolution value comprising a unique value of the updating source;

a storage means associated with each said replicated memory location and in which the updating count and resolution value of the previously received updating is stored, and storing the specific address of each memory location to be updated, for each said address the content thereof which is overwritten by any received updated content, and an updating count indicative of the cumulative number of occasions on which each said memory location has been updated inclusive of any current updating, and consolidation means connected to said data storage to from time to time on the occurrence of a predetermined condition consolidate the stored updating count;

comparison means to compare the previously stored updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet;

contention indicating means connected with said comparison means and operable to indicate a contention situation if the compared updating counts are the same;

contention resolution means connected with said contention indicating means to institute a contention resolution procedure;

means for broadcasting an addressed memory updating signal or packet over said communications network using said updating format;

for each said address the content thereof which is overwritten by any received updated content, and an updating count indicative of the cumulative number of occasions on which each said memory location has been updated inclusive of any current updating, and consolidation means connected to said data storage to from time to time on the occurrence of a predetermined condition consolidate the stored updating count;

at least one finite counter each having at least one corresponding memory location and comparison means to compare sequentially received updating messages or signals from different sources each of which can update said memory locations, wherein said updating messages or signals include a further data bit, which changes state if said counter reaches a predetermined maximum count value, and said comparison means modifies the comparison of sequentially received updating messages or signals in accordance with the states of said further data bit of said sequentially received messages;

means for overcoming memory updating echoes in a memory system where at least one memory location is replicated at different memory stores and is able to be substantially simultaneously updated from a number of sources.

16. A system for handling contention in replica memory updating for a multiple computer system as in claim 15, wherein said means for overcoming memory updating echoes further comprises:

means for overcoming memory updating echoes in a memory system where at least one memory location is replicated at different memory stores and is able to be substantially simultaneously updated from a number of sources, each source transmitting an updating message including the address of the location, the new content for the location, and an updating count indicative of the position of the updating message in a sequence of updating messages, said updating count being incremented by a predetermined number to indicate consecutive updating messages, said means for overcoming memory updating echoes further comprising;

(i) means for determining which source was the last to transmit in respect of a specific memory location; and

(ii) means for incrementing said updating count for the second transmission by more than said predetermined number where the same source is to transmit sequentially in respect of the same memory location.

17. A computer program stored in a computer readable media, the computer program adapted for execution in a processor within a computer or information appliance and a memory coupled with the processor to modify the operation of the computer or information appliance, for modifying the operation of a multiple computer system including a multiplicity of computers or of any one or more of said computers, each of the multiplicity of computers interconnected via at least one communications network, and each executing a different portion of an application program written to execute substantially in its entirety on only a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory of said multiplicity of computers, the modification including performing a method handling contention in replica memory updating comprising:

detecting contention;

resolving said detected contention;

using a modified message format and procedure in said detecting and resolving contention;

consolidating data;

operating a counter in a roll over manner; and

performing an echo cancellation procedure.