Advanced contention detection

• US 7,971,005 B2
• Filed: 10/05/2007
• Issued: 06/28/2011
• Est. Priority Date: 10/05/2006
• Status: Active Grant

• Current Assignee: Waratek Limited (Waratek Holdings Ltd.)
• Original Assignee: Waratek Pty Limited
• Inventors: Holt, John M.
• Primary Examiner(s): Thai; Tuan V.
• Application Number:
  US11/973,372
• Publication Number:
  US 20080140976A1
• Time in Patent Office: 1,362 Days
• Field of Search: 711/100, 711/147, 711/148, 711/154, 711/150
• US Class Current: 711/150
• 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 method of detecting contention in addressed memory updating in which a memory location having a specific location identifier can be updated substantially simultaneously from a plurality of sources, said method comprising the steps of:

(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 position of the updating message in the sequence of occasions on which the updating source has been updated inclusive of the current updating;

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

(iii) comparing the updating count presently resident at the receiving memory location with the updating count of any currently received updating signal or packet; and

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

2. The method as defined in claim 1, including the further steps of:

(v) if the currently received updating count is greater than the presently resident updating count, not actioning the incoming signal or packet;

or

(vi) if the currently received updating count is less than the currently resident updating count, actioning the incoming signal or packet;

or

(vii) if the currently received updating count is equal to the presently resident updating count, instituting a contention resolution.

3. A computer program product comprising a set of executable computer program instructions stored in a physical, non-transitory computer readable media, the executable computer program instructions being adapted for execution by at least one computer to modify the operation of the at least one computer;

the modification of operation including performing a method of detecting contention in addressed memory updating in which a memory location having a specific location identifier can be updated substantially simultaneously from a plurality of sources, said method comprising;

(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 position of the updating message in the sequence of occasions on which the updating source has been updated inclusive of the current updating;

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

(iii) comparing the updating count presently resident at the receiving memory location with the updating count of any currently received updating signal or packet; and

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

4. A system for detecting contention in addressed memory updating, said system comprising at least one memory location having a specific location identifier;

a plurality of sources each of which can update said memory location(s) and each of which utilizes 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 position of the updating message in the sequence of occasions on which the updating source has been updated inclusive of the current updating;

a storage means associated with each said memory location and in which the updating count of the previously received updating is stored;

comparison means to compare the previously stored updating count with the updating count of any currently received updating signal or packet; and

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

5. The system as in claim 4, wherein said contention indicating means is operable to indicate a contention situation if the compared updating counts are the same, to not act upon the currently received updating signal or packet if said comparison indicates that the currently received updating count is greater than the presently resident updating count, or to act upon the currently received updating signal or packet if said comparison indicates that the currently received updating count is less than the presently resident updating count, and contention resolution means connected with said contention indicating means to institute a contention resolution procedure.

6. A method of detecting contention in addressed memory updating in which a memory location having a specific location identifier can be updated substantially simultaneously from a plurality of sources, said method comprising:

(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 position of the updating message in the sequence of occasions on which the updating source has been updated inclusive of the current updating;

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

(iii) comparing the updating count presently resident at the receiving memory location with the updating count of any currently received updating signal or packet;

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

(v) if the currently received updating count is greater than the presently resident updating count, not actioning the incoming signal or packet;

or

(vi) if the currently received updating count is less than the currently resident updating count, actioning the incoming signal or packet;

or

(vii) if the currently received updating count is equal to the presently resident updating count, instituting a contention resolution.

7. The method of claim 6, further comprising:

(viii) following receipt of said updating signal or packet storing both the corresponding updated content and said updating count.

8. The method as defined in claim 7, including the further step of:

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

9. The method as defined in claim 8, including the further steps of:

(x) providing at least one further data bit in addition to, and associated with, each said memory location;

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

(xii) modifying the comparison of sequentially received updating messages or signals in accordance with the states of the associated further data bit of the sequentially received updating messages.

10. The method as defined in claim 9, including the further steps of:

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

(xiv) 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 the first transmission.

11. A system for detecting contention in addressed memory updating, said system comprising:

at least one memory location having a specific location identifier;

a plurality of sources each of which can update said memory location(s) and each of which utilizes 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 position of the updating message in the sequence of occasions on which the updating source has been updated inclusive of the current updating;

a storage means associated with each said memory location and in which the updating count of the previously received updating is stored;

comparison means to compare the previously stored updating count with the updating count of any 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,

wherein said contention indicating means is operable;

to indicate a contention situation if the compared updating counts are the same,

to not act upon the currently received updating signal or packet if said comparison indicates that the currently received updating count is greater than the presently resident updating count, or

to act upon the currently received updating signal or packet if said comparison indicates that the currently received updating count is less than the presently resident updating count; and

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

12. The system of claim 11, further comprising a storage means associated with each said memory location and in which the updating count of the previously received updating is stored.

13. The system as in claim 12, and including consolidation means connected to said data storage to from time to time, or on the occurrence of a predetermined condition consolidate the stored updating count.

14. The system as in claim 13, and including a finite counter and each said memory location includes a further data bit, said updating messages or signals include said further data bit, said further data bit 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 bits of sequentially received messages.

15. The system as in claim 14, wherein said updating count is increased by a predetermined number to indicate consecutive updating messages or signals, said comparison means determines which source was the last to update, and where the same source is to transmit sequentially in respect of the same memory location said updating count for the second transmission is incremented by more than for the first transmission.