Contention detection
First Claim
1. A multiple computer system adapted for memory contention detection, the multiple computer system comprising:
- 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 on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, and a system for detecting contention in replica memory updating;
said multiple computer system further comprising;
at least one memory location having a specific location identifier and replicated on at least two machines, and updated to remain substantially similar upon occasion of a machine modifying its replica value;
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 sequence of occasions on which the updating source has been updated inclusive of the current updating;
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 the 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.
1 Assignment
0 Petitions
Accused Products
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. In particular a method of detecting contention is disclosed which utilizes a count value indicative of the number of the sequence of occasions on which each memory location has been updated. Contention is indicated if the currently stored count value and the incoming updating count value are the same.
111 Citations
15 Claims
-
1. A multiple computer system adapted for memory contention detection, the multiple computer system comprising:
-
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 on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, and a system for detecting contention in replica memory updating;
said multiple computer system further comprising;at least one memory location having a specific location identifier and replicated on at least two machines, and updated to remain substantially similar upon occasion of a machine modifying its replica value; 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 sequence of occasions on which the updating source has been updated inclusive of the current updating; 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 the 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. In a multiple computer system including a multiplicity of computers, each interconnected via at least one communications network, and each of the multiplicity of computers executing a different portion of an application program written to execute only on a single computer, each of the multiplicity of computers having an independent local memory with at least one memory location being replicated in each said local memory of each said multiplicity of computers, and a method of detecting contention in replica memory updating in which a memory location having a specific location identifier and replicated on at least two computers, can be updated substantially simultaneously from a plurality of sources, said method of detecting contention in replica memory updating 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 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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. 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 the computer or information appliance in multiple computer system that includes 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 applications program written to execute on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, the modification including performing a method of detecting contention in replica memory updating in which a memory location having a specific location identifier and replicated on at least two computers, can be updated substantially simultaneously from a plurality of sources, said method of detecting contention in replica memory updating 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 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.
-
-
14. A memory location update contention detector comprising:
-
a storage that stores an updating count of a previously sent or previously received updating information; a comparator for comparing a resident updating count associated with a replicated memory location to be updated with an updating count of a currently received updating information; and a contention detector that indicates a memory contention situation if the compared updating counts are equal.
-
-
15. A replica memory updating data structure for use in replica memory updating in a multiple computer system, said replica memory updating data structure comprising:
-
a specific identifier of the memory location to be updated; a content with which said memory location is to be updated; and a resident updating count of an updating source, said resident updating count comprising an identifier indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating.
-
Specification