Hardware prefetchers are mostly undocumented micro-architectural components of the cache hierarchy, with performance and security implications. Intel CPUs feature four named prefetchers whose behaviors are generally unknown. We build CacheObserver, a generic framework to study prefetchers on Intel CPUs and the first to use the Flush+Flush primitive, unlike previous studies using Flush+Reload. We apply this framework to characterize the L2 Stream prefetcher on the Intel Whiskey and Coffee Lake micro-architectures and uncover the behavior of the L2 Stream prefetcher upon the first few accesses in a page. We also uncover interactions at the L2 level between the Stream and the Adjacent Cache Line prefetchers.

Generating smooth surfaces of arbitrary topology is a major challenge in geometric modeling, computer graphics, and scientific visualization. Subdivision surfaces have emerged as a powerful and useful technique in modeling free-form surfaces. Recursive subdivision techniques generate visually pleasing smooth surfaces through the repeated application of a fixed set of subdivision rules. Given a control mesh, a Catmull-Clark Subdivision Surface (CCSS) is generated by iteratively refining (subdividing) the control mesh to form new control meshes. CCSS implementations do not perform well and suffer from low CPU utilization because they are often waiting for data to be transferred from memory due to the repeated pointer indirections. Rapid Evaluation of CCSS is an approach that focuses on achieving maximum performance by carefully addressing caching issues. However, this approach is designed with primary target being single core machines. In this paper, we implement the Rapid Evaluation of Catmull-Clark Subdivision Surfaces (RECCSS) algorithm in C++ and measure its achieved performance. We then redesign RECCSS to leverage the potential of parallel computation on widely available multicores machines and show that Parallelized RECCSS (PRECCSS) achieves noticeable speedup when run on diverse set of machines compared to the original RECCSS implementation. In addition, we conduct a study about the data value predictability of PRECCSS load instructions using Pin dynamic binary instrumentation tool, and conclude that 93.25% prediction accuracy can be achieved with existing value prediction techniques.

Modern wideband receivers must be able to slice and dice a large band of the spectrum in real time, while available receivers are increasingly faced with the challenges of providing flexible operations on large number of channels simultaneously. We present in this paper a comprehensive review of major channelizer algorithms available in the literature that are compatible with Software Defined Radio platforms. We employ analytical models to evaluate and compare various channelizer algorithms. Moreover, we implement and simulate the Polyphase Fast Fourier Transform (PFFT) channelizer using MATLAB software. We show using the reported results that PFFT computation complexity is about four times lower than any other channelizer. We also contribute the first hardware implementation of PFFT using Vivado High Level Synthesis. In addition, we provide a clear and practical manipulation of the PFFT structure to enable real-time streaming support taking into account system optimization in terms of hardware resources and latency.

An indirect branch specifies where the address of the next instruction to execute is located. The address to be jumped to is not known until the instruction is executed. Indirect branches can incur a significant fraction of branch misprediction overhead even though they remain less frequent than the more predictable conditional branches. Indirect branch instructions implement multiway branch statements and virtual function calls in object-oriented languages. Multiple targets indirect branch instructions are difficult to predict. We employ dynamic slicing to categorize indirect branches and use the most convenient predictor for each category. We also propose Dynamic Slicing directed Indirect Branch (DSIB) predictor, a profiling based target address prediction technique for indirect branch instructions. We compare the proposed predictor to VBBI and ITTAGE predictors. DSIB enhances prediction accuracy by 13% and 9% over VBBI and ITTAGE respectively. DSIB also results in IPC improvement of 11%, 4.2% and 3.55% over BTB, VBBI and ITTAGE respectively.

Value prediction is a technique to increase parallelism by attempting to overcome serialization constraints caused by true data dependences. By predicting the outcome of an instruction before it executes, value prediction allows data dependent instructions to issue and execute speculatively, hence increasing parallelism when the prediction is correct. In case of a misprediction, the execution is redone with the corrected value. If the benefit from increased parallelism outweighs the misprediction recovery penalty, overall performance could be improved. Enhancing performance with value prediction therefore requires highly accurate prediction methods. Most existing general value prediction techniques are local, that is, future outputs of an instruction are predicted based on outputs from previous executions of the same instruction. In this article, we investigate leveraging strength-based dynamic information flow analysis to enhance data value prediction. We use dynamic information flow analysis (DIFA) to determine when a specific value predictor can perform well and even outperform other predictors. We apply information theory to mathematically prove the validity and benefits of correlating value predictors. We also introduce the concept of the linear value predictors, a new technique that predicts a new value from another one using a linear relation. We finally present a variant of stride predictor that we call update stride . We then conduct an empirical analysis using Pin , a dynamic binary instrumentation tool, and DynFlow , a dynamic information flow analysis tool, that we apply to programs from the SPECjvm2008 and Siemens benchmarks. Our empirical measurements support our mathematical theory and allow us to make important observations on the relation between predictability of data values and information flow. Our analysis and empirical results show that the values of a set of selected variables can be predicted with a very high accuracy, up to 100%. Such prediction is based on the previous history and/or the values of one or more other source variables that have strong information flow into the predicted variable. Using our selection criteria, we show that a DIFA-directed predictor outperforms hardware value prediction for all subject programs, and sometimes by a significant margin. This was observed even when using an ideal tagged hardware value prediction table that does not suffer from aliasing or capacity misses.

Value prediction is a technique to increase parallelism by attempting to overcome serialization constraints caused by true data dependences. By predicting the outcome of an instruction before it executes, value prediction allows data dependent instructions to issue and execute speculatively, hence increasing parallelism when the prediction is correct. In case of a misprediction, the execution is redone with the corrected value. If the benefit from increased parallelism outweighs the misprediction recovery penalty, overall performance could be improved. Enhancing performance with value prediction therefore requires highly accurate prediction methods. Most existing general value prediction techniques are local and future outputs of an instruction are predicted based on outputs from previous executions of the same instruction.