International Business Machines Corporation

Robert James Ramirez

Sriram Srinivasan Mandyam

Kenneth Lee Wright

Brian Walter O'Krafka

Steven Robert Farago

Ramanathan Raghavan

Brett Adam St Onge

Archie Don Barrett, Jr

Miwako Tokugawa

Jason Raymond Baumgartner

Aaron C Brown

A method, system, and apparatus for placing and removing data elements into a bi-directionally growing first in last out data structure is provided. In one embodiment, in response to a request to place a data element into the data structure, a head pointer is advanced one memory location in a direction indicated by a state of a direction flag. The new data element is placed into the memory location indicated by the head pointer. The position of the head pointer and the base pointer are swapped in preparation for receiving a new data element and the state of the direction flag is reversed to indicate growth of the data structure in the opposite direction. In response to a request to remove a data element from the data structure, the head and base pointers are swapped and the state of the direction flag is reversed. The element indicated by the location pointed to by the head pointer is removed and the head pointer retreats one memory location position in a direction opposite the direction indicated by the direction flag.

Bi-directional stack in a linear memory array

A method, computer program product and data processing system for verifying cumulative ordering. In one embodiment of the present invention a method comprises the step of selecting a memory barrier instruction issued by a particular processor. The method further comprises selecting a first cache line out of a plurality of cache lines to be paired with one or more of the remaining of the plurality of cache lines. If a load memory instruction executed after the memory barrier instruction in the first cache line was identified, then the first cache line selected will be paired with a second cache line. If a load memory instruction executed before the memory barrier instruction in the second cache line was identified, then a pair of load memory instructions has been identified. Upon identifying the second load memory instruction, a first and second reload of the first and second cache lines are identified. Upon identifying the first and second reloads of the first and second cache lines, a determination may be made as to whether the first reload occurred after the second. If the first reload did not occur after the second reload, then a determination may be made as to whether the ownership transaction referencing the first cache line was initiated between the first and second reload. If the ownership transaction was initiated between the first and second reload, then a potential violation of cumulative ordering has been identified.

Verifying cumulative ordering of memory instructions

Apparatus and methods for dynamic simulation event triggering

One aspect of the invention relates to a method for detecting architectural violations in a multiprocessor computer system. In one version of the invention, the method includes the steps of generating a testcase instruction stream having a plurality of instructions, executable by the processors, which access a memory which is shared by the processors; detecting dependent instructions in the testcase instruction stream; and modifying the testcase instruction stream by inserting logging instructions in the testcase in the testcase instruction stream which cause data associated with observable instructions to be written to a logging memory by writing a first sequence of unique monotonically increasing values to the memory. Thereafter, a second sequence of values is read from the memory location and a window of observed values is defined, wherein the window has a highest observable value and a lowest observable value where the highest observable value is set to the highest value of the first sequence and the lowest observable value is set to the lowest value of the first sequence and wherein the lowest observable value is updated with a next observable value from the first sequence whenever the value of an individual read from the second sequence is higher than the lowest observable value so that a determination can be made whether individual values in the second sequence are within the window.

Hardware verification tool for multiprocessors

A multiprocessor data processing system includes a shared main memory and a plurality of processors connected to the memory utilizing a system bus. Data is transferred utilizing the system bus. The plurality of processors include a first processor and a second processor. The first processor includes a first cache, and the second processor includes a second cache. The multiprocessor data processing system executes a test program. During execution of the test program, a first and a second trace are generated. The first trace is generated by monitoring all events occurring at a first location within the system. The second trace is generated by monitoring all events occurring at a second location within the system. Each event is associated with a time of occurrence of that event. The first trace includes each event which was monitored at the first location and the time associated with each event. The second trace includes each event which was monitored at the second location and the time associated with each event. The first and second traces are stored and utilized to determine if the multiprocessor data processing system is operating correctly.

Method and system for testing a multiprocessor data processing system

One aspect of the invention relates to a method for detecting synchronization violations in a multiprocessor computer system having a memory location which controls access to a portion of memory shared by the processors, the memory location having at least one lock bit indicating whether the portion of memory is locked by one of the processors and a plurality of bits for storing a data value. The method comprises reading the memory location by an individual processor; testing the lock bit to determine whether the portion of memory is locked; if the portion of memory is not locked; asserting the lock bit to indicate the portion of memory is locked; incrementing the data value to represent a global access count; writing the lock bit and the data value back to the memory location; and incrementing a data value stored in a memory location associated with the individual processor to indicate an individual access count by the individual processor. The individual access counts for each processor are then summed and compared to the global access count to determine whether a synchronization violation has occurred.

Growing community of inventors

Chicago, IL, United States of America

Robert James Ramirez