## 2 Background and Related Work
### State-of-The-Art Prefetching Methodologies  
Modern data intensive applications such as graph processing, scientific applications, and data mining programs are memory intensive and generate irregular memory streams. Therefore, a prefetching method should be more sophisticated than traditional fixed stride based prefetchers to find hidden patterns among various memory streams; this will allow it to predict memory access patterns much more accurately. Hence, some computer architects suggest several state-of-the-art prefetching methods to treat complex memory access patterns [1; 2; 3; 6; 7; 8; 9; 10; 11; 12; 13; 16]. [PERSON] et al. [1] suggest a structural methodology for prefetching. To provide more accurate prefetching, a prefetcher introduces a history table. Hence, the Global History Buffer (GHB) prefetcher suggests a management method for the history table. The GHB employs index tables and global history buffers to store and track recently requested physical addresses. Furthermore, the GHB structure can simply access the global history buffer by storing the memory access key from the index table. In addition, the GHB prefetcher manages the history table using the FIFO structure. Therefore, the prefetching operation can be activated based on the most recently accessed request. [PERSON] et al. [6] proposed the variable length delta prefetcher (VLDP) that is based on the delta history table and the history table. The VLDP generates prefetching candidates by considering the correlation of deltas of recently access streams. To predict the next demand requests more accurately, the VLDP tries to match the same delta chain across pages and refresh delta chains information in the delta history buffer. In addition, a delta prediction table is introduced to find the correlation among deltas, and the offset prediction table controls the aggressiveness of the prefetching. To generate more accurate candidates, the VLDP uses multi-level tables to find the most fitted chain of deltas, whose lengths range from 1 to 3. When the most appropriate delta pattern is found throughout stored delta chains information, the VLDP activates a prefetching operation. Generally, most prefetchers attempt to prefetch with a single approach, however, [PERSON] et al. [7] suggested a novel method that is based on combining multiple methodologies. This prefetcher analyzes memory access patterns by three aspects: the first module targets stride streams, the second module traces pointer traversal, and the last module targets memory streams showing high spatial locality. The prefetching controller manages these three sub prefetchers, and prefetching is conducted by selecting the module that seems to be the most fitting strategy for current memory access behaviors. And commercial off-the-shelves processor vendors apply hardware-based prefetcher for on-chip architecture, i.e., simple stride, next line, and adjacent lines prefetchers, as [PERSON] et al. surveyed [10]. However, many on-chip cache prefetcher research has tried to design lightweight and high coverage with high accuracy prefetchers as Bingo Spatial Data prefetcher and Domino Temporal Data prefetcher [11; 12]. Bingo spatial data prefetcher finds the most appropriate memory patterns through analyzing both short-term and long-term events with program counter, memory offset and memory address histories. Bingo prefetcher also uses a history table to find matched access patterns with using two key pairs as signatures (e.g., PC+Offset and PC_Address) for two-step lookup mechanisms [11]. Domino prefetcher, also suggested by the same authors of Bingo spatial data prefetcher, concentrated on finding temporal data patterns through memory sequences. Domino prefetcher predicts next demand memory requests by one or two consecutive previous accesses with the enhanced index table (EIT), and it exploits the correlation between history of demand requests and the index (pointer) information to match history table entries, when the same address in the history table has been accessed [12].