PIPS: Prefetching Instructions with Probabilistic Scouts

International audienceA new instruction prefetching method is proposed, called prob-abilistic scouting, based on the concept of Control Flow Graph (CFG). Each node of the CFG is a distinct memory line, and a directed edge from node X to node Y means that line Y is a possible successor of line X. Each edge is annotated with the probability for the edge to be taken. The hardware discovers the CFG progressively while the program executes, by monitoring instructions retiring from the processor in program order. CFG information is stored in a Line History Table (LHT). Starting from the line currently being fetched, aka front line, the prefetcher sends scouts to explore the CFG. A scout goes from node to node in a semi-random fashion, according to the edge probabilities stored in the LHT. The scout prefetches the nodes encountered along the followed path. A scout dies after a certain number of steps. After a scout dies, a new scout is sent from the front line. This process repeats indefinitely. For higher prefetch coverage and timeliness, several parallel scouts may be sent to explore the CFG simultaneously. This paper describes probabilistic scouting and a prefetcher using it, called PIPS, which is submitted to the championship. PIPS is tuned for the championship's simulated microarchitec-ture and public traces. Besides the 128 KB storage limit, the LHT of PIPS is ideal, as allowed by the championship rules