Collision-based alternate hashing

Patent metadata

Field	Value
Publication number	US-9250913-B2
Application number	US-201213524139-A
Country	US
Kind code	B2
Filing date	Jun 15, 2012
Priority date	Jun 15, 2012
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

Embodiments relate to collision-based alternate hashing. An aspect includes receiving an incoming instruction address. Another aspect includes determining whether an entry for the incoming instruction address exists in a history table based on a hash of the incoming instruction address. Another aspect includes based on determining that the entry for the incoming instruction address exists in the history table, determining whether the incoming instruction address matches an address tag in the determined entry. Another aspect includes based on determining that the incoming instruction address does not match the address tag in the determined entry, determining whether a collision exists for the incoming instruction address. Another aspect includes based on determining that the collision exists for the incoming instruction address, activating alternate hashing for the incoming instruction address using an alternate hash buffer.

First claim

What is claimed is:

1. A computer system for collision-based alternate hashing, the system comprising:
a processor, the processor comprising a prefetch logic, a history table, and an alternate hash buffer, the system configured to perform a method comprising:
receiving, by the prefetch logic, an incoming instruction address;
determining whether an entry for the incoming instruction address exists in the history table based on a hash of the incoming instruction address;
based on determining that the entry for the incoming instruction address exists in the history table, determining whether the incoming instruction address matches an address tag in the determined entry;

based on determining that the incoming instruction address does not match the address tag in the determined entry, determining whether a collision exists for the incoming instruction address, wherein determining whether the collision exists for the incoming instruction address comprises:
decrementing a liveness counter in the determined entry;
incrementing a conflict counter associated with the determined entry;
determining whether the liveness counter is greater than a liveness threshold, and whether the conflict counter is greater than a conflict threshold; and
based on determining that the liveness counter is greater than the liveness threshold and that the conflict counter is greater than the conflict threshold, determining that the collision exists for the incoming instruction address; and
based on determining that the collision exists for the incoming instruction address, activating alternate hashing for the incoming instruction address using the alternate hash buffer.

2. The computer system of claim 1 , further comprising, based on the liveness counter being less than the liveness threshold, replacing the determined entry with a new history table entry for the incoming instruction address.

3. A computer implemented method for collision-based alternate hashing, the method comprising:
receiving, by prefetch logic in a processor of the computer, an incoming instruction address;
determining whether an entry for the incoming instruction address exists in a history table based on a hash of the incoming instruction address;
based on determining that the entry for the incoming instruction address exists in the history table, determining whether the incoming instruction address matches an address tag in the determined entry;
based on determining that the incoming instruction address does not match the address tag in the determined entry, determining whether a collision exists for the incoming instruction address, wherein determining whether the collision exists for the incoming instruction address comprises:
decrementing a liveness counter in the determined entry;
incrementing a conflict counter associated with the determined entry;
determining whether the liveness counter is greater than a liveness threshold, and whether the conflict counter is greater than a conflict threshold; and
based on determining that the liveness counter is greater than the liveness threshold and that the conflict counter is greater than the conflict threshold, determining that the collision exists for the incoming instruction address; and

based on determining that the collision exists for the incoming instruction address, activating alternate hashing for the incoming instruction address using an alternate hash buffer.

4. A computer program product for implementing a collision-based alternate hashing, the computer program product comprising:
a non-transitory tangible storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
receiving, by prefetch logic in a processor of a computer, an incoming instruction address;
determining whether an entry for the incoming instruction address exists in a history table based on a hash of the incoming instruction address;
based on determining that the entry for the incoming instruction address exists in the history table, determining whether the incoming instruction address matches an address tag in the determined entry;
based on determining that the incoming instruction address does not match the address tag in the determined entry, determining whether a collision exists for the incoming instruction address, wherein determining whether the collision exists for the incoming instruction address comprises:
decrementing a liveness counter in the determined entry;
incrementing a conflict counter associated with the determined entry;
determining whether the liveness counter is greater than a liveness threshold, and whether the conflict counter is greater than a conflict threshold; and
based on determining that the liveness counter is greater than the liveness threshold and that the conflict counter is greater than the conflict threshold, determining that the collision exists for the incoming instruction address; and

based on determining that the collision exists for the incoming instruction address, activating alternate hashing for the incoming instruction address using an alternate hash buffer.

Assignees

• Alexander Khary J
• Averbouch Ilia
• Birnbaum Ariel J
• Hsieh Jonathan T
• Shum Chung-Lung K
• IBM

Inventors

• Alexander Khary J
• Averbouch Ilia
• Birnbaum Ariel J
• Hsieh Jonathan T
• Shum Chung-Lung K

Classifications

• G06F9/3808 Primary

  for instruction reuse, e.g. trace cache, branch target cache · CPC title

• G06F9/3806 Primary

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/3804

  for branches, e.g. hedging, branch folding · CPC title

• G06F9/3814

  Implementation provisions of instruction buffers, e.g. prefetch buffer; banks · CPC title