Search

Modern processors implement a decoupled front-end in the form of Fetch Directed Instruction Prefetching (FDIP) to avoid front-end stalls. FDIP is driven by the Branch Prediction Unit (BPU), relying on the BPU's accuracy and branch target tracking structures to speculatively fetch instructions into the Instruction Cache (L1I). As data center applications become more complex, their code footprints also grow, resulting in an increase in Branch Target Buffer (BTB) misses. FDIP can alleviate L1I cache misses, but when it encounters a BTB miss, the BPU may not identify the current instruction as a branch to FDIP. This can prevent FDIP from prefetching or cause it to speculate down the wrong path, further polluting the L1I cache. We observe that the vast majority, 75%, of BTB-missing, unidentified branches are actually present in instruction cache lines that FDIP has previously fetched but, these missing branches have not yet been decoded and inserted into the BTB. This is because the instruction line is decoded from an entry point (which is the target of the previous taken branch) till an exit point (the taken branch). Branch instructions present in the ignored portion of the cache line we call them "Shadow Branches". Here we present Skeia, a novel shadow branch decoding technique that identifies and decodes unused bytes in cache lines fetched by FDIP, inserting them into a Shadow Branch Buffer (SBB). The SBB is accessed in parallel with the BTB, allowing FDIP to speculate despite a BTB miss. With a minimal storage state of 12.25KB, Skeia delivers a geomean speedup of ~5.7% over an 8K-entry BTB (78KB) and ~2% versus adding an equal amount of state to the BTB across 16 front-end bound applications. Since many branches stored in the SBB are unique compared to those in a similarly sized BTB, we consistently observe greater performance gains with Skeia across all examined sizes until saturation., Comment: 13 pages, 16 figures, Submitted to ASPLOS 2025

Modern OOO CPUs have very deep pipelines with large branch misprediction recovery penalties. Speculatively executed instructions on the wrong path can significantly change cache state, depending on speculation levels. Architects often employ trace-driven simulation models in the design exploration stage, which sacrifice precision for speed. Trace-driven simulators are orders of magnitude faster than execution-driven models, reducing the often hundreds of thousands of simulation hours needed to explore new micro-architectural ideas. Despite this strong benefit of trace-driven simulation, these often fail to adequately model the consequences of wrong path because obtaining them is nontrivial. Prior works consider either a positive or negative impact of wrong path but not both. Here, we examine wrong path execution in simulation results and design a set of infrastructure for enabling wrong-path execution in a trace driven simulator. Our analysis shows the wrong path affects structures on both the instruction and data sides extensively, resulting in performance variations ranging from $-3.05$\% to $20.9$\% when ignoring wrong path. To benefit the research community and enhance the accuracy of simulators, we opened our traces and tracing utility in the hopes that industry can provide wrong-path traces generated by their internal simulators, enabling academic simulation without exposing industry IP., Comment: 5 pages, 7 Figures, Submited to Computer Architecture Letters

To alleviate the performance and energy overheads of contemporary applications with large data footprints, we propose the Two Level Perceptron (TLP) predictor, a neural mechanism that effectively combines predicting whether an access will be off-chip with adaptive prefetch filtering at the first-level data cache (L1D). TLP is composed of two connected microarchitectural perceptron predictors, named First Level Predictor (FLP) and Second Level Predictor (SLP). FLP performs accurate off-chip prediction by using several program features based on virtual addresses and a novel selective delay component. The novelty of SLP relies on leveraging off-chip prediction to drive L1D prefetch filtering by using physical addresses and the FLP prediction as features. TLP constitutes the first hardware proposal targeting both off-chip prediction and prefetch filtering using a multi-level perceptron hardware approach. TLP only requires 7KB of storage. To demonstrate the benefits of TLP we compare its performance with state-of-the-art approaches using off-chip prediction and prefetch filtering on a wide range of single-core and multi-core workloads. Our experiments show that TLP reduces the average DRAM transactions by 30.7% and 17.7%, as compared to a baseline using state-of-the-art cache prefetchers but no off-chip prediction mechanism, across the single-core and multi-core workloads, respectively, while recent work significantly increases DRAM transactions. As a result, TLP achieves geometric mean performance speedups of 6.2% and 11.8% across single-core and multi-core workloads, respectively. In addition, our evaluation demonstrates that TLP is effective independently of the L1D prefetching logic., Comment: To appear in 30th International Symposium on High-Performance Computer Architecture (HPCA), 2024

This thesis finds its place in the interplay between algebraic and geometric combinatorics. We focus on studying two different families of lattices in relation to the weak order: the permutree lattices and the $s$-weak order. The first part involves the permutree quotients of the weak order. We define inversion and cubic vectors on permutrees which respectively give a constructive meet operation between permutrees and a cubical realization of permutreehedra. We characterize minimal elements of permutree congruence classes using automata that capture ${ijk}/{kij}$-pattern avoidances and generalize stack sorting and Coxeter sorting. The second part centers on flow polytopes. More specifically, we give a positive answer to a conjecture of Ceballos and Pons on the $s$-permutahedron when $s$ is a composition. We define the $s$-oruga graph whose flow polytope recovers the $s$-weak order with explicit coordinates. Finally, we introduce the bicho graphs whose flow polytopes describe permutree lattices., Comment: PhD thesis, 207 pages, 100 figures, 4 tables, included introductions in french and english

We introduce two generalizations of bracket vectors from binary trees to permutrees. These new vectors help describe algebraic and geometric properties of the rotation lattice of permutrees defined by Pilaud and Pons. The first generalization serves the role of an inversion vector for permutrees allowing us to define an explicit meet operation and provide a new constructive proof of the lattice property for permutree rotation lattices. The second generalization, which we call cubic vectors, allows for the construction of a cubic realization of these lattices which is proven to form a cubical embedding of the corresponding permutreehedra. These results specialize to those known about permutahedra and associahedra., Comment: 17 pages, 14 figures

Ceballos and Pons introduced the $s$-weak order on $s$-decreasing trees, for any weak composition $s$. They proved that it has a lattice structure and further conjectured that it can be realized as the $1$-skeleton of a polyhedral subdivision of a polytope. We answer their conjecture in the case where $s$ is a strict composition by providing three geometric realizations of the $s$-permutahedron. The first one is the dual graph of a triangulation of a flow polytope of high dimension. The second one, obtained using the Cayley trick, is the dual graph of a fine mixed subdivision of a sum of hypercubes that has the conjectured dimension. The third one, obtained using tropical geometry, is the $1$-skeleton of a polyhedral complex for which we can provide explicit coordinates of the vertices and whose support is a permutahedron as conjectured., Comment: 39 pages, 14 figures

Recent years have seen a dramatic increase in the microarchitectural complexity of processors. This increase in complexity presents a twofold challenge for the field of computer architecture. First, no individual architect can fully comprehend the complexity of the entire microarchitecture of the core. This leads to increasingly specialized architects, who treat parts of the core outside their particular expertise as black boxes. Second, with increasing complexity, the field becomes decreasingly accessible to new students of the field. When learning core microarchitecture, new students must first learn the big picture of how the system works in order to understand how the pieces all fit together. The tools used to study microarchitecture experience a similar struggle. As with the microarchitectures they simulate, an increase in complexity reduces accessibility to new users. In this work, we present ChampSim. ChampSim uses a modular design and configurable structure to achieve a low barrier to entry into the field of microarchitecural simulation. ChampSim has shown itself to be useful in multiple areas of research, competition, and education. In this way, we seek to promote access and inclusion despite the increasing complexity of the field of computer architecture.

Generalizing stack sorting and $c$-sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets $U$ and $D$ of $\{2, \dots, n-1\}$, the $(U,D)$-permutree sorting tries to sort the permutation $\pi \in \mathfrak{S}_n$ and fails if and only if there are $1 \le i < j < k \le n$ such that $\pi$ contains the subword $jki$ if $j \in U$ and $kij$ if $j \in D$. This algorithm is seen as a way to explore an automaton which either rejects all reduced expressions of $\pi$, or accepts those reduced expressions for $\pi$ whose prefixes are all $(U,D)$-permutree sortable., Comment: 18 pages, 5 figures

Classification and differentiation of small pathological objects may greatly vary among human raters due to differences in training, expertise and their consistency over time. In a radiological setting, objects commonly have high within-class appearance variability whilst sharing certain characteristics across different classes, making their distinction even more difficult. As an example, markers of cerebral small vessel disease, such as enlarged perivascular spaces (EPVS) and lacunes, can be very varied in their appearance while exhibiting high inter-class similarity, making this task highly challenging for human raters. In this work, we investigate joint models of individual rater behaviour and multirater consensus in a deep learning setting, and apply it to a brain lesion object-detection task. Results show that jointly modelling both individual and consensus estimates leads to significant improvements in performance when compared to directly predicting consensus labels, while also allowing the characterization of human-rater consistency., Comment: Accepted at MICCAI 2019

Extremely small objects (ESO) have become observable on clinical routine magnetic resonance imaging acquisitions, thanks to a reduction in acquisition time at higher resolution. Despite their small size (usually $<$10 voxels per object for an image of more than $10^6$ voxels), these markers reflect tissue damage and need to be accounted for to investigate the complete phenotype of complex pathological pathways. In addition to their very small size, variability in shape and appearance leads to high labelling variability across human raters, resulting in a very noisy gold standard. Such objects are notably present in the context of cerebral small vessel disease where enlarged perivascular spaces and lacunes, commonly observed in the ageing population, are thought to be associated with acceleration of cognitive decline and risk of dementia onset. In this work, we redesign the RCNN model to scale to 3D data, and to jointly detect and characterise these important markers of age-related neurovascular changes. We also propose training strategies enforcing the detection of extremely small objects, ensuring a tractable and stable training process.