Data merging method and apparatus for shared memory multiprocessing computer systems

A method for sharing a memory among multiple processors, comprising:

• storing shared data in a global memory, the shared data including a plurality of data blocks and a global write bitmask having one bit for each data element of said data blocks;
• for each processor accessing data in one of the data blocks
• storing a local copy of said data block in the local memory of the processor,
• transmitting the local copy to the global memory when the local copy is flushed from the local memory and
• merging the local copy and the data block in the global memory by
• associating a plurality of local copy write flags in the local memory in a one-to-one relationship with a plurality of first sized data elements in the local copy, each of the local copy write flags initially set to a not written value,
• for each of the first sized data elements of the local copy which is modified by the processor, setting its associated local copy write flag to a written value,
• transmitting the local copy write flags to the global memory when the local copy is flushed from the local memory, and
• for each of the local copy write flags set to a written value, storing the first sized data element associated with such local copy write flag in the data block;
• and
• when multiple processors access the data block concurrently
• comparing said local copy write flags to said global write bitmask, and
• identifying the occurrence of a write/write data race condition when said comparison indicates that at least two processors have sent local copy write flags both set to the written value and associated with first sized data elements in corresponding positions of their respective local copies.

A method for sharing a memory among multiple processors, comprising:

• storing shared data in a global memory, the shared data comprising a plurality of data blocks;
• for each processor accessing data in one of the data blocks
• storing a local copy of said data block in the local memory of the processor,
• transmitting the local copy to the global memory when the local copy is flushed from the local memory, and
• merging the local copy and the data block in the global memory by
• associating a plurality of data block write flags in the global memory with a plurality of first sized data elements in the data block, each of the data block write flags initially set to a not written value,
• associating a special merger flag with the data block in the global memory, the special merger flag initially set to a first value,
• for each local copy stored while the data block is partially merged
• storing in said global memory a duplicate copy of the partially merged data block in a table entry for the local copy, and
• setting the special merger flag to a second value, and
• when storing data from the local copy into a corresponding data block in said global memory
• if the special merger flag is set to the first value, storing those data elements of the local copy that differ from correspondingly positioned, first sized data elements of the data block whose associated data block write flag is set to the not written value into the data block,
• if the special merger flag is set to the second value and the local copy was stored while the data block was not partially merged, storing those data elements of the local copy that differ from correspondingly positioned first sized data elements of the data block whose associated data block write flag is set to the not written value into the data block, and
• if the special merger flag is set to the second value and the local copy was stored while the data block was partially merged, storing those data elements of the local copy which differ from correspondingly positioned elements of the duplicate copy in the table entry for the local copy into the data block;
• and
• when multiple processors access the data block concurrently
• comparing said local copy write flags to said global write bitmask, and
• identifying the occurrence of a write/write data race condition when said comparison indicates that at least two processors send local copy write flags both set to the written value and associated with first sized data elements in corresponding positions of their respective local copies.

A shared memory multiprocessing computer system comprising:

• one or more global memory units, each global memory unit comprising a global memory for storing a plurality of data blocks of shared data, each data block comprising a plurality of multi-bit data elements;
• a plurality of processing units interconnected with the one or more global memory units, each of the processing units comprising a processor and a local memory for storing a write bitmask and a local copy of one of the data blocks when access to data in the data block is requested by the processor, the write bitmask comprising a plurality of flags associated in a one-to-one relationship with data elements of the local copy, the flags being initially set to a not written value when the local copy is stored in the local memory;
• each of the processing units further comprising a local memory controller, each local memory controller being operative to set those write bitmask flags which are associated with data elements written by the processor to a written value, and, when the local copy is replaced with other data in the local memory, to send the write bitmask and written data elements to the global memory unit if any of the data elements have been written by the processor;
• a global memory controller in the global memory unit being operative to merge a local copy received from one of the processing units by storing in the data block each of the data elements whose associated write bitmask flag is set to the written value.