Advanced I-cache prefetcher design for Out-of-Order superscalar processors

id191930   ADVANCED I-CACHE PREFETCHER DESIGN FOR OUT-OF-ORDER SUPERSCALAR PROCESSORS ADRIAN RIOS LOPEZ Thesis supervisor OSCARPALOMARPÉREZ(BARCELONASUPERCOMPUTINGCENTER-CENTRONACIONALDE SUPERCOMPUTACION) Thesis co-supervisor MIQUELROSETJULIA(BarcelonaSupercomputingCenter) Tutor:MIQUELMORETÓPLANAS(DepartmentofComputerArchitecture) Degree Bachelor'sDegreeinInformaticsEngineering(ComputerEngineering) Bachelor's thesis Facultat d'Informàtica de Barcelona (FIB) Universitat Politècnica de Catalunya (UPC) - BarcelonaTech  Abstract This Bachelor’s thesis focuses on the design and evaluation of an advanced Instruction Cache (I-cache) Fetch Directed Prefetcher (FDP) to address the memory wall challenge in Out-of-Order Superscalar processors. The memory wall arises due to the disparity in the performance of memory systems relative to processors. FDP leverages branch predictor outputs to anticipate instruction blocks and preload them into the I-cache, reducing cache miss penalties and improving fetch efficiency. The research includes designing the microarchitecture of the Fetch Target Queue (FTQ), implementing its RTL in SystemVerilog, and developing a clock-accurate reference model for validation. Verification was conducted using Cocotb, with performance benchmarks highlighting FDP’s ability to reduce instruction-fetch latency and enhance overall processor throughput. This work contributes to advancing high-performance computing by optimizing prefetching strategies and enabling their integration into future European-made RISC-V processor designs. Resumen Esta tesis de grado se centra en el dise˜no y evaluaci´on de un prefetcher dirigido por la b´usqueda de instrucciones (I-cache Fetch Directed Prefetcher, FDP) avanzado para abordar el desaf´ıo del muro de memoria en procesadores superscalares fuera de orden. El muro de memoria surge debido a la disparidad en el rendimiento de los sistemas de memoria en relaci´on con los procesadores. El FDP aprovecha las salidas del predictor de saltos para anticipar bloques de instrucciones y precargarlos en la I-cache, reduciendo las penalizaciones por fallos de cach´e y mejorando el rendimiento de fetch. La investigaci´on incluye el dise˜no de la microarquitectura de la cola de objetivos de obtenci´on (FTQ), la implementaci´on de su RTL en SystemVerilog y el desarrollo de un modelo de referencia preciso en cuanto a los ciclos de reloj para la validaci´on. La verificaci´on se llev´o a cabo utilizando Cocotb, con benchmarks de rendimiento que destacan la capacidad del FDP para reducir la latencia de obtenci´on de instrucciones y mejorar el rendimiento general del procesador. Este trabajo contribuye al avance de la computaci´on de alto rendimiento al optimizar las estrategias de prefetching y permitir su integraci´on en futuros dise˜nos de procesadores RISC-V fabricados en Europa. Resum Aquesta tesi de grau se centra en el disseny i avaluaci´o d’un prefetcher dirigit per la cerca d’instruccions (I-cache Fetch Directed Prefetcher, FDP) avan¸cat per abordar el repte de la paret de mem`oria en processadors superscalar fora d’ordre. La paret de mem`oria es produeix a causa de la disparitat en el rendiment dels sistemes de mem`oria respecte als processadors. El FDP aprofita les sortides del predictor de salts per anticipar blocs d’instruccions i precarregar-los a la I-cache, reduint les penalitzacions per fallades de mem`oria i millorant l’efici`encia del fetch. La recerca inclou el disseny de la microarquitectura de la cua d’objectius d’obtenci´o (FTQ), la implementaci´o del seu RTL en SystemVerilog i el desenvolupament d’un model de refer`encia prec´ıs pel que fa als cicles de rellotge per a la validaci´o. La verificaci´o es va dur a terme utilitzant Cocotb, amb benchmarks de rendiment que destaquen la capacitat del FDP per reduir la lat`encia d’obtenci´o d’instruccions i millorar el rendiment global del processador. Aquest treball contribueix a l’aven¸c de la computaci´o d’alt rendiment optimitzant les estrat`egies de prefetching i permetent la seva integraci´o en futurs dissenys de processadors RISC-V fabricats a Europa. Contents 1. Background 3 1.1. Introduction................................ 3 1.1.1. Context .............................. 4 1.1.2. Stakeholders............................ 4 1.2. Concepts.................................. 5 1.2.1. Branch predictors . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2. Superscalar processor . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3. Out of Order processor . . . . . . . . . . . . . . . . . . . . . . 7 1.2.4. I-cache Prefetchers . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.5. Fetch Directed Prefetching . . . . . . . . . . . . . . . . . . . . 10 1.2.6. Non-blocking Caches . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.7. Design Verification . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.8. UVM................................ 11 1.3. Problem identification . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1. Justification............................ 13 1.4. Scope ................................... 15 1.4.1. Objective ............................. 15 1.4.2. Additional objectives . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.3. Requirements ........................... 16 1.4.4. Obstacles and Risks . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.5. Methodology ........................... 17 2. Proposal 18 2.1. Fetch Target Queue microarchitectural design . . . . . . . . . . . . . 18 2.1.1. Design introduction . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.2. Features Requirements . . . . . . . . . . . . . . . . . . . . . . 19 2.1.3. Module Functionality . . . . . . . . . . . . . . . . . . . . . . . 20 2.2. Fetch Target Queue implementation . . . . . . . . . . . . . . . . . . . 28 2.2.1. Environment Setup and Tools . . . . . . . . . . . . . . . . . . 28 2.2.2. Design implementation . . . . . . . . . . . . . . . . . . . . . . 29 2.2.3. Module signals interface . . . . . . . . . . . . . . . . . . . . . 31 2.2.4. Fetch Target Queue verification . . . . . . . . . . . . . . . . . 33 2.2.5. Integration considerations . . . . . . . . . . . . . . . . . . . . 36 3. Evaluation 39 3.1. FTQ Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . 39 3.1.1. Performance testbench . . . . . . . . . . . . . . . . . . . . . . 39 3.1.2. Requests parallelism . . . . . . . . . . . . . . . . . . . . . . . 41 3.1.3. Branch predictor accuracy impact . . . . . . . . . . . . . . . . 45 1 4. Further work and Conclusions 48 4.1. Furtherwork ............................... 48 4.1.1. Confidence Estimator Optimization . . . . . . . . . . . . . . . 48 4.2. Conclusions ................................ 50 A. Temporal Planning 51 A.1.Descriptionoftasks............................ 51 A.1.1. Estimates and the Gantt . . . . . . . . . . . . . . . . . . . . . 53 A.1.2.Ganttdiagram .......................... 54 A.1.3. Risk management . . . . . . . . . . . . . . . . . . . . . . . . . 55 B. Budget 56 B.0.1. Staffcosts............................. 56 B.0.2. Development tools costs . . . . . . . . . . . . . . . . . . . . . 58 B.0.3. Contingency............................ 60 B.0.4. Unexpected issues . . . . . . . . . . . . . . . . . . . . . . . . . 60 B.0.5. Totalcost ............................. 60 B.1.Managmentcontrol............................ 61 C. Sustainability report 62 2 Chapter 1 Background 1.1. Introduction One of the greatest challenges that the computer architecture field is facing is, undoubtedly, the memory wall problem. This issue arises because memory performance has not been able to keep up with processors’ performance, resulting in a bottleneck due to the high latency of memory access. In Figure 1.1, we can see how this problem has evolved from the early stages of processor design up to the present day. Figure 1.1: Evolution of the memory wall, comparing memory bandwidth to processor’s performance [6] Since memory technologies are not keeping up with processors’ performance, we have to seek alternatives, focusing on microarchitecture. One of the greatest improvements to break the memory wall has been the implementation of cache memories. These caches are SRAM, which are faster and smaller than main memory. They store data that is likely to be accessed later, due to programs’ properties of temporal and spatial locality. These properties refer to the likelihood that contiguous memory data, or the same data, will be accessed in the near future. The system must access the data for the first time or retrieve data that was replaced, this operation, in the worst case, incurs the full latency cost. However, this may not always be the case, as the data could still be stored in the upper levels of the cache hierarchy. Nevertheless, there will always be some latency involved. 3 One of the two types of data stored in caches is the instructions that the processor will execute. In fact, there is a dedicated cache for them called the Instruction Cache (I-cache). By separating instruction data from other data, it reduces the number of cache misses during instruction fetching, as there is far less interference from non-instruction data. This is an excellent improvement in regard to having non separated caches, but we still have to bring the data from the memory, now by using prefetchers we can improve this time-consuming operations, by predicting ahead of time which block will be used and requesting it to the cache. Then when the fetch stage requests, it is a hit in cache. 1.1.1. Context This Bachelor’s Thesis is part of the Informatics Engineering Degree, specializing in Computer Engineering, offered by the Facultat d’Inform`atica de Barcelona at the Universitat Polit`ecnica de Catalunya. The research was conducted at the Barcelona Supercomputing Center—Centro Nacional de Supercomputaci´on, within the Computer Sciences—RTL Design Department. The project focuses on designing an advanced I-cache prefetcher aimed at significantly enhancing the performance of Out-of-Order superscalar processors. The module will be used later on many of the BSC processors designs. 1.1.2. Stakeholders The project will be conducted at the Barcelona Supercomputing Center (BSC), with a focus on research rather than commercial applications. Its primary goal is to develop RTL (Register-Transfer Level) modules that the BSC will use in the design and manufacturing of advanced processors. These processors are intended to showcase the capabilities of the RISC-V architecture in handling supercomputing tasks. Additionally, the project aims to contribute to the development of a European-made processor, promoting technological sovereignty in high-performance computing. 4 1.2. Concepts 1.2.1. Branch predictors Branch predictors are components in a processor microarchitecture that aim to improve performance by guessing the outcome of a branch/control instruction before it is known for certain. A branch instruction is a point in a program where the CPU must decide whether to continue executing the next instruction in sequence or jump to a different part of the program, the program is addressed in memory, and this address is what we call the Program Counter (PC). These branches tend to block the processor for some cycles. Essentially, this will be our main prediction mechanism in our fetch directed prefetcher design. Dynamic branch predictors are the standard in HPC hardware; this is due to their high prediction accuracy performance. This kind of predictor can adapt their prediction structures dynamically to effectively predict the output of a branch. One common type of branch predictor is the Global History Register predictor. This predictor combines the use of a register containing the n last branches taken/not taken information, then indexes a table where we can find the last direction taken by that specific pattern. Furthermore, we need a way to know where to jump. Branch Target Buffers (BTB) offer a solution for this specific problem by essentially making a cache of the instruction pointers of each previous branch. Hence, we do not actually need to wait by stalling the pipeline until the branch executes it to get the value of the next PC. This information is updated after the execution of each branch instruction. An example of this branch prediction scheme can be found at [15], where the following figure is presented: Figure 1.2: Global History Predictor Structure We should also have a BTB that takes as request the current PC and outputs the next target, if it is not a valid entry, then it will show it by marking it as a miss. It behaves just as a cache would do, we can even add multiple levels, but that’s out of the scope of this thesis. Then by checking if we hit and the branch is taken, we will take the result or not. Variations of this branch predictor arise, such as the Gshare predictor. The Gshare predictor is a subtype of global predictor such as the Global History Register (GHR) in terms of maintaining and utilizing global branch history. However, it 5 1.3. Problem identification In modern processor architectures, performance relies heavily on minimizing latency when fetching instructions. A poorly designed or underperforming I-cache prefetcher can lead to significant delays because it cannot anticipate which instructions will be needed next. Without timely and accurate instruction prefetching, the CPU pipeline might stall while waiting for instructions to be fetched from higher levels of the memory hierarchy (e.g., L2 cache or main memory). These stalls degrade overall system performance. Latest academia trends show how CPUs are trending towards executing larger instruction footprints. That superscalar out-of-order processors can execute faster thanks to the use of techniques described previously, effectively increasing the instructions executed per cycle (IPC) by doing this we will proportionally decrease the execution time of many workloads. But if we do not have the instruction data ready to be read, then it will be useless to have these kinds of optimizations at the back end of our processor. Because despite having the ability to perform such operations, we can’t execute them. This can be quantified with the fetching bandwidth metric, and with the ability to commit instructions by the backend is the main bottleneck of any microarchitecture, you will never be able to execute more instructions than the instructions you are fetching. However, over many years, researchers focused on creating or modifying existing prefetching prediction techniques. These techniques are always somewhat related to memorizing the access patterns of the program in execution. Essentially, up to some degree they were replicating the branch predictor, these prediction techniques have high area requirements. Since we need to store copious amounts of prediction data. Therefore, researchers focused on creating smaller prediction structures even though this approach will cause more frontend stalls, due to the inability to make accurate predictions. This issue is exacerbated in multiprocessor systems, where multiple cores or processors share memory resources and interconnection networks. Here, instruction cache misses slow down individual processors and impact system-wide performance. When an I-cache miss occurs, the processor sends a memory request over the shared interconnection network to fetch the required instruction. If the prefetcher is ineffective, the frequency of these misses increases, which causes congestion in the network due to additional memory transactions. This network congestion—or pollution—affects all processors, creating delays that ripple across the system. To mitigate these issues, one effective technique is fetch-directed prefetching, which is designed specifically to improve the efficiency of the I-cache by intelligently predicting the future instructions the processor will need. Unlike general prefetchers that may rely on simple heuristics (e.g., sequential prefetching), fetch-directed prefetchers use the actual instruction fetch stream to guide prefetching decisions. This allows the system to more accurately anticipate instruction access patterns, significantly reducing cache misses and improving cache hit rates. By reducing the number of cache misses, fetch-directed prefetching alleviates the congestion in the interconnection network. It decreases the number of avoidable 12 Figure 1.8: One of the first-ever FDP designs [16] memory requests, freeing up bandwidth for essential data transfers. This can significantly enhance the performance of multiprocessor systems, where the efficiency of the interconnection network is crucial for maintaining high throughput and low latency. 1.3.1. Justification For many years, I-cache prefetcher designs have been evolving, driven by the need to reduce instruction cache (I-cache) miss penalties and improve overall processor performance. I initially thought I was onto something novel when I came up with the idea of using the branch predictor as the prediction mechanism for prefetching instructions. The logic seemed sound, since branch predictors provide accurate control flow predictions, which could theoretically guide instruction prefetching. However, I later discovered that I was not the first to think along these lines. In fact, Fetch Directed Prefetchers (FDPs) and similar approaches have been around since the late 1990s [4] [5]. These designs leverage the branch predictor’s output to guide prefetching decisions, ensuring that the next instructions are fetched ahead of time, based on predicted program flow. This concept, while not new, remains a critical area of research and development, with modern processors continuing to optimize branch predictor-guided I-cache prefetching techniques for improved accuracy and reduced latency. What really struck me was why researchers stopped using Fetch Directed Prefetchers (FDPs) over the years. Perhaps this was due to branch predictors having lower accuracy at the time, or maybe it was because caches hadn’t reached the high levels of performance they have today. Regardless of the reasoning, one thing became clear by 2021 when researchers launched an instruction prefetching competition: ARM engineers decided to revisit FDPs. In a pivotal paper [9], they explained why FDP outperformed any other method they could come up with. And indeed, it proved superior—achieving a 1.4x speed-up while simultaneously reducing the amount of SRAM needed by several kilobytes. This renewed interest in FDPs shows that advancements in branch prediction accuracy and cache performance have made them more viable in modern architectures. What was once perhaps impractical due to the limitations of hardware has now become a competitive and efficient approach, as demonstrated by the impres13 sive gains in performance and memory efficiency achieved by ARM engineers. From this paper onwards is where I decided to implement the module. The paper does not provide an implementation, just the main idea behind FDP prefetching and an interface proposed to interact with the I-cache, which I will need to change, and another one with the branch predictor. As I have previously justified, this is the most cutting edge prefetching technology that I could implement. It does not exist any open-source implementation that I would be able to replicate or improve. 14 1.4. Scope 1.4.1. Objective The objective behind this project is to design, implement, verify the functionality and test the performance of an I-cache Fetch Directed Prefetcher module, hence proving that an FDP can be implemented and have promising performance characteristics. Since it is a critical step towards the development of an HPC processor, it must be as efficient as the technology allows it to be and bug free. Regarding the verification process, a reference model in C should be created to test the implementation with how we actually expect it to work. Another important characteristic it must have is that it should be properly documented, allowing other BSC engineers to improve the module or the I-cache in a near future. The integration of the module is more of a sub objective, since the processor we plan instantiating it on is currently under development. Even though we will most likely not be ready to integrate the module onto the superscalar, out-of-order core, there will be detailed steps about the constraints for this integration to happen consisting on detailed documentation. Summing up, the objective is to design, implement and verify functionality and performance for the FDP module regardless of the CPU microarchitecture, thus proving the effectiveness of using such prefetching techniques showcasing the benefits and constraints of using this type of prefetchers and document the whole process. Figure 1.9: FDP prefetcher schematic proposed at the 2021 IPC [9] 15 1.4.2. Additional objectives I would say there are 2 additional objectives that branch from this project: 1. UVM testbench: Implementing a UVM test bench to verify the prefetcher module it is not the main objective of this project. But it is a great element to have, since we could reuse it to test other hardware models. With the components that will generate signals to stimulate the DUT accordingly to a module or submodule behavior (UVM agents) that I will develop for this project. I will ensure the reusability of the environment. This way, we will catch far more errors in the design phase and leave more bandwidth for the verification team to verify other projects. 2. Module Integration The integration of the module is not the main objective of this project, and it will depend on the development of the RISC-V core done by BSC. 1.4.3. Requirements The requirements I would say are to have a well-defined interface with the core and other components, to be able to run the project coded in SystemVerilog without compiler errors or warnings. And for the non-functional ones, is having a great documentation enabling for further development and integration. 1.4.4. Obstacles and Risks We have been able to identify a main obstacle for this project, and it is that there are no past references we can sustain that a real implementation with great performance can be achieved. Another minor obstacle is that since there was a time when the developing of these FDPs was held on standby, there is a lack of public research available, although this could also be an opportunity. There are not any important risks to consider, maybe the most important is the time and deadlines. 16 1.4.5. Methodology An Agile methodology is proposed for the implementation and verification of the Fetch Directed Prefetcher (FDP) in this thesis due to its adaptability and suitability for managing complex research-based projects. The project will be divided into iterative sprints, with each sprint focusing on specific aspects such as designing, optimizing, and verifying the FDP. This incremental approach will facilitate continuous progress, allowing for regular delivery of functional components throughout the development cycle. Frequent feedback loops will be integral to the process, enabling constant refinement and adjustments based on early testing results. Agile’s flexibility will help address unforeseen challenges, such as potential bottlenecks in prediction accuracy or performance, by allowing for dynamic reprioritization and experimentation with alternative solutions. Regular sprint reviews and retrospectives will ensure that issues are identified and resolved promptly. Clear milestones will be established at the end of each sprint to ensure structured progress tracking, helping to maintain alignment with project goals and timelines. Agile will also facilitate regular collaboration through check-ins with advisors and stakeholders, ensuring that feedback is consistently incorporated into the development process. Continuous integration and testing phases will be embedded within each sprint to ensure that the FDP’s functionality and performance are verified incrementally. By delivering working components early and refining them iteratively, the Agile approach is expected to minimize risks related to incomplete or unverified work. This methodology will provide the necessary structure, flexibility, and responsiveness to manage the complexities of FDP implementation and verification, ensuring the project remains on track to achieve its objectives efficiently and effectively. [19] 17 Chapter 2 Proposal 2.1. Fetch Target Queue microarchitectural design 2.1.1. Design introduction The Fetch Target Queue is an implementation of the well-known Fetch Target Queue (FTQ) [16] with the additional support of Fetch Directed Prefetching (FDP). The main purpose of this module is to use the predicted instruction blocks from the branch predictor to prefetch them into the L1 I-cache, therefore when the instruction is fetched by the fetch engine we already have them available in the I-cache, and it does not generate a miss for that access. As it was early stated by [16], opposed to a traditional fetch engine that couples the branch predictor with the instruction cache, the FTQ architecture is what enables to provide a decoupled front-end. The branch predictor in a typical coupled front end effectively produces the next fetch address, obviously this would not give us any kind of prefetching advantage because it is not running ahead from fetch. Furthermore, by not having a decoupled front-end we are causing the instruction fetch operation to stop whenever we have an instruction cache stall, as well as stopping the branch predictor operations until the cache miss that caused the stall resolves. Another important consideration is that the use of the so-called Fetch Target Buffer described at [17], which nowadays is used interchangeably with the BTB. This FTB concept differs from the traditional BTB by using instruction pointers blocks instead of predicting smaller targets (sometimes even just a single instruction, depending on the architecture) this showed a great performance improvement of a 25% at the time. In the rest of the document, we will use FTB and BTB terms interchangeably, but it was important to define this term due to the scalability benefits that it provides. The FTQ is the front-end decoupling mechanism that we will be using in this implementation. The branch predictor will produce every cycle a start address of a cache block, which will be buffered into the FTQ, where it will make the request to the I-cache, effectively making branch predictor and cache operations totally independent. Therefore, the branch predictor can run ahead from the instruction cache when it is stalled in a miss. The branch predictor producer interface is pretty clear, but how will we update its entries to make correct predictions, and other 18 relevant integration constraints in the pipeline, will be further discussed in section 2.2.5. The FTQ has to store the predicted blocks in a FIFO way. The data structures that we will store are defined in section 2.1.3. We have also noticed that we will need some kind of control mechanism per FTQ entry, this shall be done through the use of a Finite State Machine (FSM), thanks to this mechanism we will be able to know when an entry has been already requested to the I-cache and when it has been allocated, the definition of this FSM can be found in figure 2.2. The most critical FTQ design feature will be to have two head pointers and a common tail, unlike a common FIFO controller where there is just one of each, later on in section 2.1.3, it will be explained why. 2.1.2. Features Requirements The features required for this module aim to provide the interfaces necessary for both, the Fetch engine, and the Instruction Memory. A minimum feature is the creation of a credit interface for the producer of the FIFO, be it the Fetch Engine, this interface shall be capable of writing into the Fetch Target Queue whenever the branch predictor is ready for this operation to happen as well as the FTQ, also we should provide the FTQ with some mechanism to reset the queue and flush the controllers in case a mispredict happens. The full process is described at 2.2.5. Secondly, an implementation of a tagged interface to resolve I-TLB/I-cache tag lookup and gather the data array position (way) as a confirmation for the success of the operation. This interface has a ready/valid handshake for the way request with an identification ID/tag, and an additional response channel with a valid handshake, which can come out-of-order with the corresponding ID. Thirdly, we must Track I-TLB/I-cache tag lookup completion within valid FTQ entries, using a head hardware pointer, so that whenever it is marked as allocated it can fire a signal to let the consumer know that the data is available and update the branch predictor. Fourthly, implementing a valid handshake for the read operation of the Instruction memory data array, this process should be controlled by the I-cache, basically because most of the information needed is in the cache controller, but we will provide the necessary information and a detailed interface on how to do it. There is only one desired optional feature, and it is to parametrize the number of ports of the FIFO producer, this could improve the run ahead capabilities of the module, by basically having a higher bandwidth communication with the branch predictor. 19 Furthermore, a parametrization for the two following parameters must be done, later on, we will specify in section 2.1.3 how the data structures of each entry should be parametrized. Field Type Description WR PORTS int Number of write ports to the FTQ. SIZE int Number of entries of the FTQ. Table 2.1: FTQ Configuration Parameters 2.1.3. Module Functionality The functionality of this module is based on the work from [9]. More precisely, the flow of instructions through the FTQ, the concept of decoupling from the frontend, as well as how we update the branch predictor. In Figure 2.1 we can see a high-level abstraction of the final design. We will explain how the basic concepts of the design work, before deep diving into the control logic and detailed data flow. Figure 2.1: Fetch Target Queue module abstracted We can notice at the design the FIFO queue which holds the instruction blocks written through the producer write ports (ftq wr entry i), that are then requested to the cache. The entries after being written will be requested to the cache will be performed through the request Data port, the response will be received by the Way tagged interface. Finally, these entries are consumed through the read port (ftq rd entry o). The 4 stages that the Fetch Target Queue module will need to implement are called FTQ 0, FTQ 1, FTQ 2 and FTQ 3 respectively. As it would be expected from a regular FIFO queue, pointers are needed to perform the write and read operations, also unlike a typical FIFO this design needs to have 2 head pointers and a common tail. 20 At first, it may seem quite odd to have three pointers in a FIFO queue, but once we explain the module functionality, it will be cleared out. The three pointers are described as follows: 1. Tail pointer: The tail pointer keeps track of the next position to insert data at the “end” of the queue. It ensures that elements are inserted in the order they arrive and removed in the same order, following the FIFO principle 2. FDP (Fetch Directed Prefetching) pointer: The FDP pointer is the one in charge of reading each entry and the necessary data to make the I-cache request, as long as the entry read meets the necessary conditions. 3. Head pointer: Lastly, we have the head pointer, it will be constantly reading the information from the oldest written entry to the FTQ, and once it is marked as allocated it will fire a signal to mark it as valid, so the consumer can read it. FTQ Entry Each FTQ entry needs to store the data needed to make the requests to the Icache and later on update be consumed. Every field’s width is fully parametrizable, to adapt to any design. In Table 2.2 we can see how each field is defined and its corresponding size. Field Size Start address Vaddr I-cache way log2(I-cache associativity) State 2-bit Metadata METADATA SIZE Table 2.2: FTQ Entry data structure and sizes We only need to hold 4 data fields for each FTQ entry to have a functional module, we will see the size implications later on. Each field is defined as follows: Start address: It is the virtual address of the fetch block being fetched. In this case, it is the virtual address instead of the physical address because the cache is virtually indexed. It could also be changed to the physical address size thanks to the highly parametrizable capabilities of the module. I-cache way: it is the way where the prefetched block has been allocated at the I-cache, to be used as the confirmation. State: This filed stores the state of the FTQ entry. A detailed FSM diagram is provided in figure 2.2. It uses 2 bits because we need 3 states, Invalid, Valid and Read Ready. Metadata: This field is implementation-independent. This means that the information necessary to store depends on the context in which the FTQ is used instead of this implementation. If this information were to be used in the context of predictors, the minimum information required would be the one necessary to communicate the decisions made in the prediction stage, mainly for correction purposes. 21 2.2. Fetch Target Queue implementation This section discusses how the FTQ module design was implemented in RTL. We will first introduce the technologies used, as well as the submodules and logic implemented, passing by the final module interface and finally a practical example of how it operates. 2.2.1. Environment Setup and Tools The implementation and verification (later to be explained in Section 2.2.4) tools that I used for the development of the project can be summarized into 4. 1. Docker: A containerization platform that provides a consistent and reproducible environment for development and testing. By encapsulating all dependencies within a Docker container, it was possible to streamline the setup process and maintain compatibility across different systems. 2. Verilator: A containerization platform that provides a consistent and reproducible environment for development and testing. By encapsulating all dependencies within a Docker container, it was possible to streamline the setup process and maintain compatibility across different systems. 3. HLIB: A System Verilog Hardware Library of highly parametrized standard usage modules developed at BSC. There are many ways to approach an RTL design, and often, it is not necessary to start from scratch because some modules have already been designed; the missing part was to identify and organize those modules of common use and that motivation is what gives life to this library that aims to contribute with the parameterization of these modules and thus reduce the overhead of micro-architectural hardware design. 4. Cocotb: A Python-based coroutine testbench framework designed for verifying HDL designs. Cocotb enabled high-level, flexible test writing, allowing Python to interface with the RTL module through a simulation backend, in our case Verilator. As you have may notice, I did not use QuestaSim or any other commercial EDA tools, this was an unexpected problem in which licenses of QuestaSim were temporarily unavailable at BSC. When licenses came back, the project was too advanced to switch infrastructure, so it was decided to carry the whole project with Verilatro and Cocotb. 28 2.2.2. Design implementation In this section, we will talk about how we managed to implement the design presented in the previous sections. Foremost, the greatest challenge of this module was to create a FIFO queue with two head pointers and a common tail pointer. Making a whole new module to just manage two heads and a common just did not make sense, specially when we already got a FIFO controller module. Maybe in a nearby future, the FTQ module will be improved with this 2 headed FIFO controller. Moreover, considering the tight schedule of this project, and the possible improvements would not be worth of spending that precious time on implementing and, more important, verifying the module. Therefore, it was decided to use the already existing module, the FIFO controller. This module implements the control system for a highly parametrizable circular buffer FIFO, allowing users to define the parameters of the queue. Communication with the module is facilitated through write and read requests, to which the module responds by granting these requests and providing indexes for operations in the actual memory. I managed to connect two of these FIFO controller modules in a single module, the queue in itself is just a highly parametrizable logic array of the defined structure in Section 2.1.3. Moreover, a reset array was defined by setting all elements to 0, flushing the queue. If there was a reset, the FIFO controllers would flush and reset both pointers. FIFO controllers usage Once we got both FIFO controllers instances defined inside the FTQ module, we need to comprehend how they work to understand future problems that may arise from this operation. The most difficult problem is, undoubtedly, synchronizing both pointers, to ensure a correct operation. First, it should be made clear that the FIFO controller module is a module which gives us two pointers, or rather indexes, these indexes tell us which array position we should write to or read from. Furthermore, it is important to ensure that it is possible to do the operation, this is called grant. A write operation will be granted in a port whenever the port is free and the queue is not full. A read will be granted when the port is not being accessed by another component and the queue is not empty, to avoid reading invalid data. For FTQ 0 stage, the only time when we should synchronize is whenever there is a write operation into the FTQ by the producer, since this operation is fully transparent to the other controller. The best solution that I was able to find was that the FDP head would also receive the same write enable signal, therefore both tails are now in sync. Then we go through FTQ 1, in this stage we should read with the FDP head each entry. However, the read should only be performed whenever the cache is ready to receive a request. Essentially, the read enable signal is the cache ready signal. 29 We can read the data by just assigning the output to the array position indicated by the index. By doing this we can save logic, improve readability and keep it simple. In this stage, there is the so called tagged interface, this interface provides just the current read index from the FDP head to the cache, by doing this simple mechanism we let the cache handle it, which has already existing structures that could add an extra field to manage it, instead of elaborating complex logic or tables. Now the only thing that is left is when should we trigger the request, or in other words, when is the data that we are reading valid. Well, to answer this question, we should think how this pointer moves, the head pointer will advance until it reaches the tail pointer, so it will only read data in the valid state, since in this implementation cannot come back to previous accessed positions (this is a critical point that was avoided thanks to the tagged interface), at some point the tail will be reached and this is the only case where the data is not valid. This case is the same as considering the queue as empty, then the valid data signal will be the not empty signal. In FTQ2, we receive the way assigned to the instructions block from the cache and the tag belonging to that request. When we receive the response, we just need to index the array with the tag and set overwrite the way as well as the state (set to Read Ready). Finally, we have the FTQ3 stage, the data read port is always assigning the value of the entry pointed by the head, by indexing the memory array. The valid data depends on the read enable signal, whenever we read we should have the entry in a Read Ready state and the consumer as ready. These conditions are checked in an always comb statement, then it is assigned to a valid data signal that will trigger the action. I would also like to reiterate that this was all made with the intention that every single stage could happen at once for different entries, also known as segmented or pipelined design. Thanks to this feature, the performance of the module will increase, allowing us to mask some added latency to the pipeline At the following Subsection 2.2.3 it is possible to find the final module interface signals as well as the parameters to configure it. 30 2.2.3. Module signals interface Now we are going to name each signal from the interface to refer properly to them from now on. Parameters Parameter Description FIFO SIZE Number of elements (entries) in the list. START ADDRESS SIZE Width of the start address in bits. TAG SIZE Size of the tag field in bits. STATE SIZE Size of the state field in bits. METADATA SIZE Size of metadata associated with each entry. WORD WIDTH Number of bits per word in the FIFO. WR PORTS Number of parallel write ports. RD PORTS Number of parallel read ports. RPTR INIT VALUE Initial value of the read pointer. WPTR INIT VALUE Initial value of the write pointer. FULL OFFSET Number of slots that define FIFO full. WR WHEN FULL AND RD Allow writes even when FIFO is full and a read is happening at the same cycle. RST DATA VALUE Reset value of all FIFO slots. UNORDERED READS Allow unordered parallel reads. UNORDERED WRITES Allow unordered parallel writes. PARALLEL FLUSH WR Allow flush and write simultaneously. PTR BITS Bits needed to index a pointer for FIFO SIZE. PTR COUNT BITS Bits needed to represent the number of slots in the FIFO. Table 2.3: Parameters of the Fetch Target 31 Inputs Input Port Description clk i System clock signal. rstn i System reset signal (active low). flush i Flush FIFO, prioritizing flush over reads and writes. overwrite rd req i Request to overwrite read pointer. overwrite rd ptr i Value to overwrite the read pointer. overwrite wr req i Request to overwrite write pointer. overwrite wr ptr i Value to overwrite the write pointer. ftq0 valid data i Valid data signal for producer. ftq0 start address i Start address for producer data. ftq0 metadata i Metadata for producer data. ftq1 cache ready i Cache ready signal. ftq2 cache valid i Valid data signal from cache. ftq2 way assigned i Cache way assignment. ftq2 tag i Queue position tag. ftq3 consumer ready i Consumer ready signal. assertions enabler i (Simulation only) Assertion enable signals. Table 2.4: Input Signals of the Fetch Target Queue Outputs Output Port Description wr grants o Write grants array for ports. rd grants o Read grants array for ports. current wr ptr o Current value of the write pointer. current rd ptr o Current value of the read pointer. consumed slots o Number of elements stored in the FIFO. available slots o Number of free slots in the FIFO. fifo full o Indicates when the FIFO is full. fifo empty o Indicates when the FIFO is empty. ftq0 fifo not available o Indicates FIFO is not available. ftq1 req valid o Cache request valid signal. ftq1 req addr o Cache request address. ftq1 req tag o Tag for cache request. ftq3 data o Data for consumer. ftq3 valid data o Valid data signal for consumer. Table 2.5: Output Signals of the Fetch Target Queue 32 2.2.4. Fetch Target Queue verification An essential step in the design and implementation pipeline is the design verification. This will tell us if the design works or not, it will also light up the bugs that our design could potentially have. A UVM environment was decided to not be created, unlike it was planned in Section 1.4.2. This decision was taken because at the end it would have meant to have replicated work, and this work could have not been reused for other projects. Moreover, the lack of QuestaSim licenses made a great impact since we could not run any UVM simulations, this was the final deterrent to making a UVM environment. Let’s elaborate on what I mean by replicated work. The HLIB library is an RTL library created and maintained by RTL engineers, they decided to use cocotb for verifying their work, which is a very valid option for only doing unit verification, but lacks of functionalities that make UVM great, such as its reusability, complicates connections to other modules, lack of a well-defined testing software architecture that could induce errors, it is very slow and has poor scalability . . . These are only some reasons of why UVM is the verification industry standard, but this is really not needed for unit verification, or rather it can be easier to use cocotb in this case, to not replicate work and since Cocotb capabilities as UVM for this use case. Cocotb was the only one that was decided to be used and keep consistency within the existing repository. The other reason to use UVM was due to reusability, but in this context the UVM made would be probably far too much specific, thus most of the UVM would probably need to be changed to use it with other modules. The interesting part would be to reuse the FTQ agent, which redoing it could be a tedious work for someone who has not worked before on the module. The solution I came up with was to make a reference model in C which can substitute the UVM agent in case it is needed for other projects, including integrating it in a UVM environment, as well as using it for the cocotb unit verification. 33 In the following figure, you can see the proposed schematic for the UVM, just to look at how the reference model interacts. Figure 2.10: UVM proposal Reference model The FTQ reference model must be written in C, to ensure portability to a UVM that could be written for another module, and should be able to interact with the Cocotb testbench written in python. In this case, I have chosen to use ctypes, which is a python API that enables to interact with the C code compiled as a shared object. Another reason to choose this one is due to the great support from the community as well as the extensive documentation. However, the use of this API is only temporal and for simplicity purposes, in the near future it would be useful to port it to dpi-c. Which is another library that enables to interface SystemVerilog with foreign languages, in this case C. This port should not take that much time, but I did not do it because I would also need to use ctypes, so it would add an extra step where things can fail. Additionally, depending on which HDL simulator is being used, data definitions such as structs can change its order. 34 Finally, the most important detail about the reference model is that it is clock accurate. This means that when the function is called from the testbench it emulates exactly all the signals after one clock, as well as the FTQ entries, of course. Unit verification testbench The test bench, as we mentioned before, was made in python using the cocotb library. In this testbench we do not need to have a precise cache model because we are looking for corner cases that could cause a bug. The connections to the DUT are made through the cocotb API with SystemVerilog, now we should emulate the reset as well as the clock operations. These are done through special cocotb API calls. We have a reference model, but if we do not compare the results, then it is useless. Since I decided that it was going to be a clock accurate model, I could compare each entry every cycle to the DUT and if it is different from the expected value, raise an exception. First I did a simple test that would go through the simple operations, in this case it was decided to first write into FTQ, and simulate a read from the FDP pointer as well as the response and consume operations. When I got these simple operations working, I started testing every stage in parallel by raising all valid signals at the same time. After working on some conditions that should have been handled by the producer, consumer and the I-cache, that were emulated by the test bench, I got it working. The next step would be to use fully randomized tests, these tests also needed to guarantee that impossible situations could not happen. For example, a response to a non-requested address could interfere with the tag interface. To accomplish this, I needed to keep track of the requests that had been made. With the use of a simple python code, by pushing into an array and doing a pop of the data, I was able to emulate the cache behavior. Now, by fully randomizing the inputs, in a constraint manner, we can compare the results. Random tests results After some debugging iterations, the design was capable of execution 100k random iterations successfully without any assertion failing. 35 2.2.5. Integration considerations Eventually, the FTQ (Fetch Target Queue) module will need to be integrated into a processor core. This integration necessitates careful consideration of several aspects that differ from the scenario where a fetch-directed prefetcher is not present. The FTQ inherently modifies how instruction fetch and prediction interact, as it introduces an additional layer of complexity in managing fetch targets and ensuring high bandwidth utilization. Additionally, when we are adding such a new element that changes the pipeline it does not come as cost free, this impact is quantified in Figure 2.11 and tested against experimental results in section 3.1. Added pipeline latency The FTQ is essentially a buffer and a buffer adds extra cycles to the pipeline, considering how the write and request operations have to be carried whenever the FTQ is empty. Thankfully, these cycles are masked when either the program flow has not started yet and is a miss, then the significant latency will be the request and not the cycles from writing and requesting, also if the following requests are misses it will not impact the performance since the previous requests are also misses, and they are being resolved in parallel. The other case is when the program is running and hitting, without the branch predictor sending flush requests thinking of a false mispredict, thanks to the proven run ahead capabilities of the FTQ it will compensate for the delay. The penalty incurred by flushing the FTQ every time a recovery event is triggered by the fetch engine cannot be avoided by any means. This penalty cannot be masked in any way, but this penalty is much lower than the one it would have if it were due to a Cache error. Since we have a segmented pipeline, once the data path starts filling up again, the performance would be the same as not having a prefetcher in the pipeline. One clear case where we can see the impact of this latency is whenever the program is hitting, but the recovery event triggers a flush request, this will make the difference noticeable, and we will be able to quantify the FTQ delay. 36 We can represent and quantify the impact of this added latency in the following figure, where the pipeline is represented. Figure 2.11: Added pipeline latency compared to previous pipeline As we can see, we now add 2 extra penalty cycles whenever a recovery operation triggers a flush of the FTQ. We can see that no extra requests to the I-cache are made, even though the recovery operation comes 2 cycles later than we expected. In conclusion, we have quantified the total penalty, in the worst case, to be 4 cycles, 2 more than the previous pipeline without the prefetcher. In section 3.1 we will experimentally prove that it does not surpass this number. 37 And we can also see its speed-up to not prefetching: Figure 3.4: Speed-up achieved using 8 MSHRs for each FTQ size Finally, the question that we might ask ourselves is for a certain number of MSHRs which is the ideal FTQ size, the following figure answers this question: Figure 3.5: Ideal FTQ number of entries per number of MSHRs We can see for this workload that up to a number of MSHRs (32 in this case) we no longer obtain greater improvement, this can be one of the reasons of why I-caches rarely have more than 32 MSHRs, or it also could be that the number of accesses is low. In fact, what we are actually seeing is the maximum latency of 30 cycles mentioned above. So there is no more advantage of having more requests nor MSHRs. 44 3.1.3. Branch predictor accuracy impact The Fetch Target Queue depends solely on the branch predictor accuracy. Besides the obvious reason for prefetching the correct block, there is also another reason for which the predictor accuracy is important. As I explained in section 2.2.5 whenever there is a mispredict it needs to flush the FTQ, which in the worst case adds a bubble of 4 cycles in which the pending stages will be discarded by the flush triggered by the recovery operation. For this reason, we will measure the number of cycles wasted by the recovery operation to ensure that it does not surpass the expected maximum latency. To do this first, we need to calculate the expected worst-case total added latency. To do so, we need to determine the number of accesses to execute, which all of them should be hit to avoid mixing the results with the latency due to misses, after some testing I found that the average of the results (selecting between recovery or not) matched the expected value of the accuracy of the branch predictor set to 90% which can be easily achieved by modern branch predictors. This number was 5120 accesses. First let’s calculate the result for a 100% of accuracy Latency = (1 ∗1 + 0 ∗3) ∗ 5120 + 4 = 5124cycles, the 4 extra cycles are for the first 4 cycles account for the cold start. Now we just need to calculate the total cycles value, to accomplish this, we need to calculate the following formula. Latency = (0.9∗1 +0.1∗3)∗5120+ 4 = 6144cycles This is the expected value of our implementation. It is in fact 2 cycles of penalty only, since the design in this test does not need a cycle to produce the value, and it can actually perform the FTQ 1 request and FTQ 2 response in the same cycle. Since the access is a hit, it will respond in the same cycle and the operations needed to change the state can be performed near the end of the cycle. After executing it 10 times, we got the upper value to be 5972 cycles and the lower value to be 5667, with an average of 5753, this variance can be accounted for the moment where the flush arrives to the FTQ, for instance consecutive flushes where the latency in between is smaller than the penalty. Furthermore, the random module from python is not perfect and in total is accounting for a 4% difference in this case 45 Then it is also interesting to see how by increasing the branch predictor accuracy the cycles taken to execute the test evolution, starting at an 85% and ending at the 100%. Figure 3.6: Cycles taken to execute the workload vs. the accuracy of the branch predictor In this case, as we expected, we can see how the cycles taken to execute the workload decrease proportionally to the branch predictor precision. This shows that our module behaves correctly and has great performance, specially when increasing the accuracy of the branch predictor. Another metric we are eagerly awaiting to extract with this test it the blocks fetched per cycle, depending on the branch predictor accuracy. We should expect this number to go up as we increase the branch predictor accuracy. We will still keep the 5120 accesses. If we do so, we will see the following figure: Figure 3.7: Fetched blocks per cycle vs. the accuracy of the branch predictor 46 We can see how it increases proportionally to the accuracy of the branch predictor. In conclusion, this test has shown that the module implemented is capable of having a good performance when we are comparing it to the alternative non-prefetch, despite the added latency to the pipeline. It also strongly suggests that having a high branch predictor accuracy such as the ones we can find at modern branch predictors. Moreover, it has proven that the prefetching bandwidth is high enough, despite the misses, to still run ahead of the program flow. 47 Chapter 4 Further work and Conclusions 4.1. Further work Besides the integration of the FTQ module to working modern superscalar and out of order CPU, there is one more optimization that could help to improve the performance of the execution. Specially in multiprocessor designs, where network and cache pollution due to incorrect or too aggressive prefetching can become a problem. 4.1.1. Confidence Estimator Optimization Fetch Directed Prefetching leverages prefetching entirely to decisions made by the branch predictors. However, branch predictors despite having high accuracy, some of them reaching 98%, according to probability after n decisions the probability of predicting the correct branch would be 0.9nif we tried predicting correctly 6 consecutive branches we would have a success probability of around 0.53, which is really low for the workload that we are executing. Occasionally, it can be beneficial to not prefetch with such low probability, since inaccurate prefetches can lead to cache pollution, wasted memory bandwidth, and increased energy consumption. Specially in multicore systems where bandwidth and network pollution are essential for good performance. Prefetch filtering addresses these challenges by selectively allowing only highconfidence prefetch requests. This method is not common and not much research has been done, on the prefetching side, but in [12] there is a method proposed for data caches fetch directed prefetching. Confidence estimators are critical tools in speculative microarchitectural techniques, enabling processors to assess the reliability of predictions, such as branch directions or speculative values. In [10], confidence estimators are defined as mechanisms that classify predictions as either high or low confidence, balancing the trade-off between incorrect speculations and missed opportunities. Key metrics used to evaluate their performance include specificity (SPEC)—the probability of correctly identifying mispredictions as low-confidence—and predictive value of negatives (PVN)—the likelihood that low-confidence predictions are indeed incorrect. These metrics are inversely related, requiring careful tuning of confidence thresholds to optimize performance for specific applications. By combining multiple estimators 48 into composite confidence estimators, Jim´enez demonstrates an enhanced ability to finely control speculation, achieving higher accuracy and flexibility compared to standalone estimators. These advancements are particularly impactful in applications like pipeline gating and eager execution, where speculation control directly influences energy efficiency and overall processor performance. Going back to the prefetching side, this confidence estimators were applied in The prefetch filtering mechanism in B-Fetch is centered on dynamically assessing the confidence of prefetch requests to minimize unnecessary operations. It employs a per-load confidence estimation process, where each memory load instruction is associated with a confidence score derived from its historical prefetch accuracy. This is achieved using three skewed sampling tables, each containing 3-bit up/down saturating counters. The counters are incremented when a prefetch is successful (i.e., the data is used by the program) and decremented otherwise. During execution, the confidence scores from these tables are aggregated to form a per-load confidence value. If this value falls below a predefined threshold, prefetch requests for that load instruction are filtered out, preventing low-confidence prefetches from polluting the cache. The mechanism operates in parallel with the path confidence estimator, which determines the reliability of the predicted execution path. Together, these components ensure that only prefetches with both high path and per-load confidence are issued, optimizing cache utilization and reducing unnecessary memory traffic. In conclusion, we think that a similar mechanism could be implemented for the FTQ, this mechanism would enable to adapt the prefetching aggressiveness based on workload characteristics and observed cache behavior. Moreover, for multicore processors, more strict filtering could be applied to minimize the impact of prefetching requests. We expect that it will reduce cache pollution by eliminating low confidence prefetches and increase energy efficiency and performance, also from there could be improvements on the branch predictor side, for example in metapredictors selectors as well. Although, benchmarks will need to be run and a microarchitecture will need to be defined. 49 4.2. Conclusions In conclusion, we have been able to design, implement and verify the fetch target queue as well as extracting performance results proving that the main advantages due to the use of Fetch Directed Prefetchers (FDPs) have been achieved. As well as relating them to the results obtained by [9], where similar approaches demonstrated significant gains in performance and resource utilization. A module has been implemented that only needs no more than 32 entries to achieve its maximum performance, which in size would be 211 bytes. Compared to IPC-1 winners [18] using 128 KB of storage for their prediction mechanism is an excellent improvement in both area and energy efficiency. This now freed resources can be used to improve other parts of the processor or make each manufactured processor cheaper. The performance tests also show that the FTQ mitigates the negative impact of I-cache misses by maintaining high prefetch accuracy and reducing non-covered misses (NCs). This was achieved even under the additional pipeline latency introduced by the FTQ, which was shown to incur only a minor penalty compared to the benefits of sustained prefetching throughput. The results further underscore that modern branch prediction methods are essential to the effectiveness of FDPs, as initially proposed in [9]. By leveraging the GHR (Global History Register) and BTB (Branch Target Buffer), the FTQ enables precise prefetching, even in complex pipeline scenarios, ultimately contributing to the overall performance improvements. This work contributes to advancing processor design by optimizing instruction fetch mechanisms and paving the way for future enhancements, such as confidence estimator optimization and further modular integration within superscalar processors. 50 Appendix A Temporal Planning A.1. Description of tasks The tasks for implementing a fetch-directed prefetcher using Agile methodology involve iterative development, where each sprint focuses on delivering functional increments that progressively build toward the final system. In this approach, Agile sprints are designed to gradually break down the complex process of designing, implementing, optimizing, and verifying the prefetcher. Each sprint includes specific goals, such as basic functionality, performance optimization, and final deployment, with verification tasks using UVM (Universal Verification Methodology) running in parallel to ensure correctness and performance validation at each stage. UVM verification tasks are integrated into each sprint to ensure that the design meets both functional and performance requirements early on and throughout development. The use of UVM provides a structured and scalable way to test the prefetcher under various scenarios, catching potential issues in an automated fashion and ensuring thorough coverage of all key features and corner cases. This task breakdown helps maintain flexibility, adaptability, and continuous feedback, which are essential in both hardware design and verification. Sprint1: Planning, Research and Setup Research fetch-directed prefetching techniques and select an algorithm. Define system requirements and success metrics (cache hit rate, latency). Set up Agile tools (Jira/Trello) and version control (GitHub/GitLab). Development environment configuration. Verification Plan creation. UVM environment design and documentation. Meetings with tutor and RTL team. Sprint2: Design Architecture and Interfaces Design the Fetch Directed Prefetcher architecture. Define communication interfaces with the I-cache, Producer and consumer. 51 Select the most efficient data structures for each case. Develop UVM testbench architecture. Plan basic functionality tests. Sprint 3: Initial Prefetcher Implementation Implement the prefetcher module. Write unit tests for functional validation. Run simulations for early performance analysis. Write UVM test sequences to validate basic functionality. Plan basic functionality tests. Sprint 4: Performance Tuning and Optimization Write a complete UVM environment supporting performance evaluation. Run experiments based on the previously obtained results. Optimize the prefetcher module. Sprint 5: Module validation and performance Run random regressions in UVM to catch every bug. Run the SPEC2017 tests to compare the performance obtained with real applications. Extract conclusions. 52 A.1.1. Estimates and the Gantt Number Description Duration Dependencies Roles S1.1 Research fetch-directed prefetching techniques and select an algorithm 40 None E, LE S1.2 Define system requirements and success metrics 20 S1.1 LE, DD S1.3 Set up Agile tools (Jira/Trello) and version control (GitHub/GitLab) 10 None E S1.4 Development environment configuration 20 None E S1.5 Verification Plan creation 30 S1.1 E , LE S1.6 UVM environment design and documentation 40 S1.5 E, LE S1.7 Meetings with tutor and RTL team 10 Continuous, None LE, DD Sprint 1 170 S2.1 Design the Fetch Directed Prefetcher architecture 60 S1.1 LE, E S2.2 Define communication interfaces with I-cache, Producer, Consumer 40 S2.1 LE, E S2.3 Select the most efficient data structures 30 S2.1 LE S2.4 Develop UVM testbench architecture 30 S1.6 E, LE S2.5 Plan basic functionality tests 20 S2.4 E Sprint 2 180 S3.1 Implement the prefetcher module 80 S2.1 E, LE S3.2 Write unit tests for functional validation 30 S3.1 E S3.3 Run simulations for early performance analysis 30 S3.1 E S3.4 Write UVM test sequences to validate basic functionality 30 S2.4 E, LE S3.5 Plan basic functionality tests 10 S3.1 E Sprint 3 180 S4.1 Write a complete UVM environment supporting performance evaluation 40 S2.4 E, LE S4.2 Run experiments based on the previously obtained results 40 S4.1 E S4.3 Optimize the prefetcher module 40 S4.2 E Sprint 4 120 S5.1 Run random regressions in UVM to catch every bug 20 S4.1 E S5.2 Run SPEC2017 tests to compare performance with real applications 20 S4.3 E S5.3 Extract conclusions 10 S5.2 LE Sprint 5 50 Total 600 53 B.0.3. Contingency As with any project, it is important to include a contingency to cover obstacles and unforeseen circumstances. In this case, while the project involves research with innovative technologies, the likelihood of encountering problems during development is not excessively high. Therefore, it has been decided to set a 20% contingency to ensure that any eventualities can be addressed. Cost Contingency Laptop 120€ Staff 1971€ QuestaSim license 16.8€ Table B.4: Contingency table B.0.4. Unexpected issues In this project, the likelihood of encountering unexpected issues is relatively low due to the nature of the tasks and the stability of the tools involved. Most problems that could arise during the development process would be manageable and could be resolved quickly with minimal disruption. For example, minor hardware or software issues can typically be addressed with straightforward fixes or replacements, causing little to no delays. The only area where a higher risk might exist is in relation to the QuestaSim licenses. Since QuestaSim is a specialized tool used for verification, any issues with licensing—such as unexpected expiration, limitations on usage, or delays in renewal—could potentially result in project delays or additional costs. To quantify the likelihood of these issues, the table below provides an estimation of the percentage probability of encountering different types of unexpected problems, based on project analysis. Item Failure probability cost Laptop 5% 10€ QuestaSim license 10% 200€ Table B.5: Unexpected issues costs B.0.5. Total cost Cost Total cost Staff 9855€ Development tools 684€ Total 10539€ Table B.6: Total cost 60 B.1. Managment control Once the initial budget is defined, the necessary control mechanisms are established to avoid deviations, as well as numerical indicators that aid in monitoring. During the weekly meetings, every time a task is completed, the budget will be updated with the actual hours spent and compared to the estimated hours. To manage unforeseen expenses, upon completion of a task, any extra costs that have occurred will also be recorded and compared with the contingency and unforeseen expense forecast. This way, any deviation can be quickly detected, and it can be predicted whether it is necessary to cut tasks or increase the budget. Below are the numerical indicators for control: Deviation in personnel cost per task: (estimated cost −actual cost) ×actual hours Deviation in task completion: (estimated hours −actual hours) ×actual cost Total deviation in task completion: total estimated cost −total actual cost Total deviation in resources (software, hardware, space, or personnel): total estimated cost −total actual cost Total deviation in unforeseen costs: estimated unforeseen costs −actual unforeseen costs Total deviation in hours: estimated hours −actual hours 61 Appendix C Sustainability report This sustainability report evaluates the project ”Advanced I-cache Prefetcher Design for Out-of-Order Superscalar Processors” from the perspective of three key sustainability dimensions: economic,environmental, and social. These dimensions provide a framework for understanding how the project contributes to sustainable development and its long-term impact. The report considers the resource efficiency, environmental footprint, and social implications of the project. 1. Economic Sustainability The economic sustainability of this project is measured by its ability to optimize resource utilization while providing long-term economic benefits. Several factors contribute to this dimension: Resource Efficiency The design of an advanced I-cache prefetcher enhances processor performance by minimizing instruction-fetching latency. By improving the accuracy and timeliness of prefetching, the project reduces the processor’s idle time and dependency on slower memory operations. This increases computational throughput and efficiency, which translates into reduced operational costs, particularly in high-performance computing environments like data centers. Cost Management Efficient prefetching mechanisms reduce the need for frequent access to higher memory levels (e.g., L2 cache or main memory), thereby lowering the energy and monetary costs associated with high-latency memory transactions. The prefetcher design focuses on using the available hardware resources optimally, thus preventing the need for costly upgrades in memory or processor subsystems. By using existing infrastructure more efficiently, the project helps to avoid unnecessary capital expenditure. Long-Term Viability The implementation of the prefetcher aligns with the goal of developing more efficient processors that can meet the growing demands of computational tasks without 62 requiring frequent hardware changes. This ensures that investments in supercomputing infrastructure are protected, as the improved performance from the prefetcher will extend the useful life of existing systems. In this way, the project contributes to the long-term economic sustainability of organizations relying on high-performance computing. 2. Environmental Sustainability The environmental sustainability of this project reflects its potential to reduce energy consumption, minimize electronic waste, and lower the environmental impact of processor manufacturing. Energy Consumption One of the primary goals of the I-cache prefetcher is to reduce processor stalls caused by instruction cache misses. By anticipating instruction fetches more accurately, the processor can operate more efficiently, reducing the power wasted during idle cycles. As processors become more efficient, the overall energy consumption in systems such as data centers or large-scale computing facilities decreases. This energy reduction is especially critical in environments where supercomputers consume vast amounts of power. Environmental Impact of Manufacturing Although the focus of the project is on design and verification rather than hardware manufacturing, it indirectly influences the environmental impact of future processors. A well-designed prefetcher reduces the need for larger caches or additional memory, allowing for smaller and more efficient processor designs. This could lead to a reduction in the raw materials and energy required for manufacturing, contributing to lower carbon footprints associated with hardware production. E-waste Reduction The project’s emphasis on enhancing processor performance through architectural improvements (rather than hardware upgrades) helps extend the lifespan of existing systems. By improving the efficiency of processors through software and hardware design rather than replacing entire systems, the project reduces the turnover of obsolete equipment. This contributes to a decrease in electronic waste (e-waste), which is a significant environmental concern globally. 3. Social Sustainability Social sustainability considers the project’s contribution to society through technological innovation, education, and broader societal benefits. Technological Sovereignty This project is part of the broader initiative to develop European-made processors, promoting technological independence and reducing reliance on external 63 technologies. By contributing to the research and development of processors optimized for supercomputing tasks, this project helps strengthen Europe’s position in the global high-performance computing market. The advancement of independent technology fosters job creation, economic growth, and innovation within the region. Educational Impact As a Bachelor’s thesis project conducted at the Barcelona Supercomputing Center (BSC), the work has significant educational value. It provides hands-on experience in designing and verifying advanced microarchitectural components, thereby enhancing the skills of future engineers and researchers. The project also adds to the academic body of knowledge in computer engineering, specifically in processor design and performance optimization, contributing to the academic growth of both the student and the institution. Societal Benefits The long-term impact of this project on society is substantial, especially in areas where high-performance computing is critical. For example, faster and more efficient processors enable advancements in scientific research, climate modeling, healthcare simulations, and artificial intelligence. These improvements contribute to solving global challenges, such as climate change, disease prevention, and innovation in technology, thereby benefiting society as a whole. Conclusion The sustainability assessment of the Advanced I-cache Prefetcher Design for Outof-Order Superscalar Processors project reveals a strong alignment with the principles of economic, environmental, and social sustainability. The project optimizes resource usage, minimizes energy consumption, and reduces the need for frequent hardware upgrades, thereby contributing to economic and environmental sustainability. Furthermore, by advancing technological sovereignty, promoting education, and enabling societal benefits through high-performance computing, the project demonstrates its commitment to social sustainability. In summary, this project represents a valuable contribution to sustainable development in the field of computer architecture. 64 Bibliography [1] IEEE standard for universal verification methodology language reference manual. pages 1–458. Conference Name: IEEE Std 1800.2-2020 (Revision of IEEE Std 1800.2-2017). [2] RRZE-HPC/kerncraft. original-date: 2014-12-15T12:35:40Z. [3] Samson Belayneh and David R Kaefi. A discussion on non-blocking/lockup-free caches. [4] I.-Cheng K. Chen, Chih-Chieh Lee, and T.N. Mudge. Instruction prefetching using branch prediction information. In Proceedings International Conference on Computer Design VLSI in Computers and Processors, pages 593–601. ISSN: 1063-6404. [5] J. C. Chiu, R. M. Shiu, S. A. Chi, and C. P. Chung. Instruction cache prefetching directed by branch prediction. 146(5):241–246. Publisher: The Institution of Engineering and Technology. [6] A. Danesh. Breaking through the memory wall. https://www.asteralabs. com/breaking-through-the-memory-wall/. Accessed: Sep. 25, 2024. [7] Adi Fuchs and Ruby Lee. Disruptive prefetching: Impact on side-channel attacks and cache designs. [8] C´esar Fuguet. HPDcache: Open-source high-performance l1 data cache for RISC-v cores. In Proceedings of the 20th ACM International Conference on Computing Frontiers, CF ’23, pages 377–378. Association for Computing Machinery. [9] Y. Ishii, J. Lee, K. Nathella, and D. Sunwoo. Re-establishing fetch-directed instruction prefetching: An industry perspective. In 2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 172–182, Mar 2021. [10] Daniel A. Jimenez. Composite confidence estimators for enhanced speculation control. In 2009 21st International Symposium on Computer Architecture and High Performance Computing, pages 161–168. ISSN: 1550-6533. [11] Norman P Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. [12] David Kadjo, Jinchun Kim, Prabal Sharma, Reena Panda, Paul Gratz, and Daniel Jimenez. B-fetch: Branch prediction directed prefetching for chipmultiprocessors. In 2014 47th Annual IEEE/ACM International Symposium on Microarchitecture, pages 623–634. ISSN: 2379-3155. 65 [13] David Kroft. Lockup-free instruction fetch/prefetch cache organization. In 25 years of the international symposia on Computer architecture (selected papers), pages 195–201. ACM. [14] Sheng Li, Ke Chen, Jay B Brockman, and Norman P Jouppi. Performance impacts of non-blocking caches in out-of-order processors. [15] Scott McFarling. Combining branch predictors. [16] G. Reinman, B. Calder, and T. Austin. Fetch directed instruction prefetching. In MICRO-32. Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture, pages 16–27, Nov 1999. [17] Glenn Reinman, Todd Austin, and Brad Calder. A scalable front-end architecture for fast instruction delivery. [18] Alberto Ros and Alexandra Jimborean. The entangling instruction prefetcher. 19(2):84–87. [19] K. Schwaber and M. Beedle. Agile Software Development with Scrum. Prentice Hall, 2002. 66