Memory address collision detection of ordered parallel threads with bloom filters

Patent metadata

Field	Value
Publication number	US-9542193-B2
Application number	US-201213730704-A
Country	US
Kind code	B2
Filing date	Dec 28, 2012
Priority date	Dec 28, 2012
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

A semiconductor chip is described having a load collision detection circuit comprising a first bloom filter circuit. The semiconductor chip has a store collision detection circuit comprising a second bloom filter circuit. The semiconductor chip has one or more processing units capable of executing ordered parallel threads coupled to the load collision detection circuit and the store collision detection circuit. The load collision detection circuit and the store collision detection circuit is to detect younger stores for load operations of said threads and younger loads for store operations of said threads.

First claim

What is claimed is:

1. A semiconductor chip comprising:
first and second inputs to respectively receive an address of a load operation and a store operation of an accessing thread and said accessing thread's order number;
a load bloom filter circuit coupled to said first input to receive the address of the load operation and a store bloom filter circuit coupled to said second input to receive the address of the store operation, the load bloom filter circuit and the store bloom filter circuit each having storage locations that individually identify whether they have been previously accessed and provide an order number of a previous accessing thread if so; and
a circuit to:
for the store operation, record the address of the store operation in a storage location of the store bloom filter circuit and present the address of the store operation to the load bloom filter circuit to determine if any younger thread performed a load from the address, and
for the load operation, record the address of the load operation in a storage location of the load bloom filter circuit and present the address of the load operation to the store bloom filter circuit to determine if any younger thread performed a store to the address.

2. The semiconductor chip of claim 1 further comprising one or more processing units to execute parallel ordered threads, said accessing thread and any younger accessing threads being members of said parallel ordered threads.

3. The semiconductor chip of claim 2 further comprising a queue between said one or more processing units and the load bloom filter circuit and the store bloom filter circuit.

4. The semiconductor chip of claim 1 wherein the circuit is to generate a flag when:
for the store operation, if any younger thread performed the load from the address, and for the load operation, if any younger thread performed the store to the address.

Assignees

• Intel Corp

Inventors

• De Lucas Enrique
• Marcuello Pedro
• Ben-Kiki Oren
• Pardo Ilan
• Yosef Yuval

Classifications

• G06F9/3834 Primary

  Maintaining memory consistency · CPC title

• G06F9/30043 Primary

  LOAD or STORE instructions; Clear instruction · CPC title

• G06F9/3009

  Thread control instructions · CPC title

• G06F9/3867

  using instruction pipelines · CPC title

• G06F9/3857

  Physics · mapped topic