Roth, Moshovos, Sohi (HW)

PC-A: LOAD rdest, rsrc(14)

rsrc:

PC-B: LOAD rdest, rsrc(14)

rsrc:

Producer of b

Consumer of b/Producer of c

hold same value

Potential Producer Window

Memory

Value

Loaded

Producer

Instruction

Address

PC-A

Correlation Table

Producer

Instruction

Address

Consumer

Instruction

Address

PC-B

PC-A

Consumer

Instruction

Template

LOAD r,r(14)

Previous slide Next slide Back to first slide View graphic version

Notes:

Roth, Moshovos, and Sohi proposed a recursive prefetcher that is able to identify consumer and producer instructions. It generates prefetches for the consumer, when the corresponding producer is executed.

Their hardware scheme use two tables. The leftmost table is the potential producer window which holds the PCs of all memory instructions that are executed and it is maintained like a cache. This table is indexed by the data returned by the memory instruction which may be the base address of any consumers if they exist.

All memory instructions can also be consumers. So, while making a potential producer entry, the same table is also indexed by the base address of the current instruction. If a match is found, the current instruction is a consumer and the producer is identified by the matching table entry.

After a match is found, the PC of the producer and consumer is stored in the correlation table. Also stored in this table is the consumer memory instruction that is needed for generating prefetch addresses. This table is indexed by the producer PC, so that when a producer is executed, the table entry can be found and a prefetch issued for the consumer.

Producers can have multiple consumers as would be the case in a tree data structure where an element points to several other elements.

ata structure where an element points to several other elements.