Memento: an adaptive, compiler-assisted register file cache for GPUs

Memento: An Adaptive, Compiler-Assisted Register File Cache for GPUs Mojtaba Abaie Shoushtary, Jose Maria Arnau, Jordi Tubella Murgadas, Antonio Gonzalez Polytechnic University of Catalonia, Spain Abstract—Modern GPUs require an enormous register file (RF) to store the context of thousands of active threads. It consumes considerable energy and contains multiple large banks to provide enough throughput. Thus, a RF caching mechanism can significantly improve the performance and energy consumption of the GPUs by avoiding reads from the large banks that consume significant energy and may cause port conflicts. This paper introduces an energy-efficient RF caching mechanism called Memento that repurposes an existing component in GPUs’ RF to operate as a cache in addition to its original functionality. In this way, Memento minimizes the overhead of adding a RF cache to GPUs. Besides, Memento leverages an issue scheduling policy that utilizes the reuse distance of the values in the RF cache and is controlled by a dynamic algorithm. The goal is to adapt the issue policy to the runtime program characteristics to maximize the GPU’s performance and the hit ratio of the RF cache. The reuse distance is approximated by the compiler using profiling and is used at run time by the proposed caching scheme. We show that Memento reduces the number of reads to the RF banks by 46.4% and the dynamic energy of the RF by 28.3%. Besides, it improves performance by 6.1% while adding only 2KB of extra storage per core to the baseline RF of 256KB, which represents a negligible overhead of 0.78%. I. INTRODUCTION AND MOTIVATION Modern GPUs implement fine-grain context switching by relying on a large register file (RF) that stores the context of a very large number of active threads. As the RF is huge and serves many read/write requests, it also contributes to a considerable share of dynamic energy consumption. For instance, NVIDIA V100 architecture has a 20MB RF, representing 56% of on-chip storage, [54] which consumes about 24% of the dynamic energy of the chip [27]. The RF must also deliver high bandwidth as well as large capacity. Therefore, it consists of enormous single-ported banks to avoid the area and energy overhead of many ports required for high throughput [72]. Read requests to the same bank are serialized, which affects read bandwidth and latency. Applications that are more sensitive to operand read bandwidth would be more penalized by bank conflicts. Conventionally, GPUs solve this issue by serving concurrently the operand read requests from different instructions to better utilize the banks’ read bandwidth. To implement this, the RF has several Operand Collector Units (OCUs) [39], each of which buffers source operands of one instruction before being dispatched to execution. Each OCU is responsible for fetching and storing the source operands of the allocated instruction. Although OCUs reduce the bank conflict’s detrimental effect, many of them are needed to overcome the severe bank conflict issue of modern GPUs. Modern GPUs suffer more 0% 20% 40% 60% 80% 100% rodinia_3.1 Deepbench 012345678910 greater than 10 Fig. 1: Reuse distance of register values used at least once from bank conflicts because their Streaming Multiprocessor (SM) is partitioned into sub-cores [11]. Each sub-core has private RF banks, OCUs, issue schedulers, and execution units (EUs) [11], [48], [49], [51]–[55]. Partitioning SM into sub-cores reduces the area and energy of the SM [50] but increases the chance of bank conflicts [11]. For instance, Volta architecture has only 2 RF banks per sub-core [23] which has a high probability of bank conflicts. A na¨ ıve solution to tackle severe bank conflicts in subcores is to increase the number of OCUs. However, scaling the number of OCUs has a high overhead. The overhead is due to requiring a bigger crossbar, which delivers read operands from banks to the OCUs, and more operand buffering storage of added OCUs. For example, increasing the number of OCUs per sub-core from 2 to 8 improves performance by 7.1% on average but increases the area and power of the RF by 1.74× and 2.83×respectively [11]. A recently proposed issue scheduler tackles the bank conflict problem in sub-cores and avoids the overhead of scaling OCUs [11]. However, it only addresses the bank conflict problem, not the high energy consumption of reading operands from the large RF banks. A possible solution that reduces both the bank conflicts and energy consumption of the RF is using an energy-efficient RF cache, that is small and closer to the Execution Units (EUs), and thus, more energy efficient than the large RF banks to serve read requests. It also reduces bank conflicts when a request is served directly from the cache since it does not need to be sent to the RF banks. Previous works, referred to as BOW [18], RFC [20], software RFC [21], and LTRF [63], propose a RF cache for GPUs that unlike modern GPUs do not have sub-cores and do not support Tensor Cores. Sub-cores have been the trend for SM architectures since their appearance in Maxwell architecture [48]–[54], [56]. Tensor cores are also an indispensable accelerator in modern GPUs for General Matrix Multiplication (GEMM) operations [48], [49], [52], [54], [56], the building block for modern machine learning and linear algebra computations. These previous proposals, as we will 1 © 2024 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. https://dx.doi.org/10.1109/ISCA59077.2024.00075 0.5 0.6 0.7 0.8 0.9 1 1.1 monolithic RFC monolithic software RFC sub-core RFC sub-core software RFC Fig. 2: IPC of two-level schedulers of RFC and software RFC in monolithic and sub-core based architectures normalized to their baseline show later in this paper, are rather inefficient or unfeasible in modern sub-core-based architectures with tensor cores. Memento overcomes these limitations in the following way. First, Memento implements the cache inside OCUs instead of adding a separate RF cache, unlike RFC, software RFC, and LTRF. Adding the RF cache apart from OCUs has the overhead of the RF cache itself, routing networks delivering the traffic into/out of the cache, and pipeline modifications to integrate the RF cache. Instead, Memento repurposes the OCUs to operate as both RF cache and OCU to avoid such overheads. OCUs already have storage space to buffer source operands of an instruction, but they do not function as a cache. By turning the OCUs into an RF cache, Memento reuses the values already stored in the OCU and seamlessly integrates the RF cache into the pipeline. Second, Memento time shares the RF cache storage among warps instead of having a private RF cache per warp, as BOW does. Having a dedicated RF cache per warp makes easy to implement compiler optimizations since the content of the cache is deterministic, as there are no conflicting access from other warps and GPUs issue instructions in-order. However, it has a high area and power overhead. Having a private RF cache, as BOW does, requires as many OCUs as the number of warps. It means that a GPU with 64 warps per SM and four sub-cores, similar to A100 [47], [48], requires 16 OCUs per sub-core. Even ignoring the overhead of the added cache storage, increasing the number of OCUs from 2 to 16 has a power overhead of 5.19×[11] in the RF. Third, Memento captures temporal locality through a fully associative cache with a very small number of entries, unlike BOW, which requires many more entries to support modern tensor core instructions. This is because BOW requires a buffer to store all sources and destinations of a few instructions within a sliding window. In that design, the more instructions in the sliding window or the more source and destinations per instruction, the larger the buffer must be. Tensor core instructions have both of these characteristics. They have a high number of source and destination registers and a relatively high reuse distance, which requires scaling the sliding window size significantly to capture locality. In particular, Fig. 1 depicts the reuse distance of register values for Deepbench [9] and Rodinia [13] compiled to Turing native ISA [46]. Deepbench has a high frequency of tensor core instructions, 65.6% for conv, and shows higher reuse distances. Fig. 1 also shows that more than 40% of reuses in Deepbench have a distance greater than 10. In addition, in Turing’s native ISA, tensor core instructions can have up to eight 4B source and destination registers [57], [60], [70]. Putting this all together, a buffer to store source and destination registers of 11 tensor core instructions for 32 threads in a warp requires 32 ×11 ×8×4B= 11KB. This overhead is avoided by Memento by using a much smaller number of entries and relying on more efficient cache management policies guided by reuse distances. Fourth, Memento uses a one-level scheduling policy, unlike RFC, software RFC, and LTRF, which use a two-level scheduler to reduce overhead. RF cache schemes using twolevel schedulers allocate the RF cache space only to a subset of warps called active set. Only the warps in the active set can issue instructions in each cycle. The performance of these two-level schedulers is highly sensitive to the policy that determines which and how many warps are active. In a modern architecture with sub-cores, the number of warps per sub-core is low, and thus, the number of warps in the active set is even lower and limits the capability to hide short latency stalls. A two-level scheduler causes unnecessary stalls in the issue cycle when a warp is ready yet not in the active set. Fig. 2 shows the IPC impact of the two-level schedulers proposed in RFC and software RFC for two different architectures with 32 warps and an active set of 8 warps per SM. In one architecture, monolithic, there is only one scheduler issuing one instruction per cycle common in early GPU architectures such as Tesla [37]. In another architecture, sub-core, warps are distributed on four sub-cores, each having one scheduler as it is the case in modern architectures such as Turing [56]. Each scheduler manages only 8 warps, 2 of which are in the active set. The results show a very important drop in performance of 12.9% for software RFC and 9.9% for RFC on average in the sub-core architecture. Some applications such as hotspot, suffer a 50% performance loss using software RFC in the sub-core architecture. Although the monolithic architecture experiences a small performance drop of 2.1% for RFC and 3.5% for software RFC on average, it is not negligible for some applications such as nn that suffer a 31.1% IPC drop using software RFC. In conclusion, previously proposed RF cache schemes that leverage a two-level scheduler incur in a very important performance loss, especially in modern architectures that use sub-cores, which outweighs any potential benefit in RF energy reduction. On the other hand, Memento not only does not cause any penalties, but also provides a significant performance improvement. To sum up, avoiding the above-mentioned inefficiencies 2 requires Memento not to increase the number of OCUs, minimally increase the entries in the RF cache and use a single-level scheduling policy. Dealing with such restrictions is challenging and requires highly effective management policies. To implement effective RF cache management policies, Memento leverages information about the reuse distance provided by the compiler and includes a dynamic scheme that delays the issue of some instructions when it is expected to increase the cache hit ratio but at the same time is not causing a performance penalty. We show that a simple approximation of the reuse distance is enough to exploit the full potential of the Memento caching scheme, achieving an average RF cache hit ratio of 46.4%. We also show that Memento’s single-level scheduler enhanced with the dynamic issue delay scheme is highly effective and not only does not incur any penalty but it provides an average 6.1% performance improvement. To the best of our knowledge, Memento is the first RF cache scheme designed to address the severe bank conflict and energy consumption of modern GPU architectures equipped with sub-cores and tensor cores. Memento targets both generalpurpose and modern machine-learning applications which extensively make use of tensor cores. In summary, the contributions of this paper are the followings: •Introducing a lightweight RF caching mechanism that leverages the already existing OCUs of modern GPU architectures equipped with sub-cores and support for tensor core instructions. •Proposing the design of novel caching and scheduling policies tailored to maximize energy-saving and performance. •Devising a practical approximation of the reuse distance of each register operand computed by the compiler and exploited by the hardware at run time. •Analyzing the overall energy saving and performance provided by the system. Results show 6.1% IPC improvement and 28.3% reduction in the dynamic energy of the RF on average. This paper is organized as follows. Section II covers the baseline RF architecture in GPUs. Section III describes Memento’s architecture and its ISA extension. Memento policies are explained in section IV. Section V explains the evaluation methodology. Section VI presents the evaluation results and analysis of the mechanism. The related work and their comparison to this work are done in section VII. This work is concluded in section VIII. II. BASELINE RF ARCHITECTURE Our baseline models a Turing SM architecture [55] with four sub-cores. Each sub-core has an RF with two banks [23], two OCUs [11], [39], an arbiter unit, and a dispatch scheduler, as depicted in Fig. 3. The crossbar delivers read register values to OCUs; the arbiter unit resolves the port conflicts, and the dispatch scheduler selects the ready instructions for dispatching to the SIMD EUs. Bank 1 Bank 2 SIMD EUs Dispatch Scheduler Reads Writes OCU 2 OCU 1 Arbiter Issued Instructions Fig. 3: RF microarchitecture in GPUs [1], [39] The banks are single-ported and serve only one read/write request per cycle. Writes always have priority and are granted access immediately but reads requiring the same port of the bank or OCU are conflicting. Conflicting reads are stored in a FIFO queue associated with each bank. Every cycle, the oldest request of each queue is granted access by the arbiter unit only if the port of the OCU and the bank it needs are available. Each OCU buffers the source operands of an instruction in up to 6 source operand slots to support tensor core instructions [57], [60], [70]. Each source operand slot contains a valid bit, a ready bit, and a data field. The valid bit is set if the source operand slot is used. The ready bit is set once the fetched data from the banks is delivered to the OCU and stored in the data field. The data field is a 128B vector register storing 4B data per thread for a warp with 32 threads. The issue scheduling and OCU allocation policies determine which instruction occupies which OCU. A free OCU will randomly be selected by the OCU allocation policy as soon as the issue scheduler selects a new instruction. Once the OCU is allocated to a new instruction, it generates the source operand read requests and pushes them into the RF bank queues. The instruction in the OCU will be a candidate for dispatch once all of its source operands are fetched from the RF banks, that is when the ready bit is set for all valid source operand slots. Once the dispatch scheduler dispatches the instruction of an OCU, the OCU will be released and reallocated later to another instruction. III. MEMENTO ARCHITECTURE AND ISA EXTENSTION Memento requires some small hardware support and an ISA extension to pass the register reuse distance information from the compiler to the hardware. Section III-A explains the calculation of reuse distance, while section III-B details the RF hardware architecture modifications. This includes the replacement of OCUs with Caching Collector Units (CCUs), as described in section III-C. A. Computing Reuse Distance The reuse distance is the number of dynamic instructions between a source or destination register and its immediate reuse. It is computed by the compiler, encoded in the instructions, and passed to the hardware. Thus, it may potentially increase the program size. To keep this potential overhead minimal, we propose to use a binary approximation. This binary approximation encodes reuse distances as just two 3 possible values: far and near. The reuse distances above a predefined threshold, RTHLD, are designated as far, and those lower than the threshold are considered as near. Therefore, the reuse distance used in Memento is only one bit. We used only one RTHLD during the whole execution and empirically found 12 provides the best results for our benchmarks. The exact reuse distance of each operand is unknown at compile time in general due to a twofold reason. First, the reuse distance of operands reused across multiple basic blocks depends on the actual control flow at run time. Second, For operands reused within a basic block, the reuse distance is not deterministic because modern GPUs support interleaved execution [54] which may interleave both paths of a branch during run time. A reuse in a basic block may be spaced by instructions of another independent path. To handle the above issue, the compiler collects profiling statistics for the reuse of each operand in a kernel regarding how many times its reuse is far and how many times is near. Then, it marks each operand’s reuse as the most common one encountered during profiling. Profiling is offline for the first few warps of each kernel. We verified that profiling only a few warps (around 0.01%) produces accurate results, very close to profiling the whole execution, so Memento adopted this lowoverhead partial profiling. B. Memento RF Microarchitecture The RF architecture in Memento has three main differences compared to the baseline, as depicted in Fig. 4. First, the OCUs are replaced by CCUs. A CCU is a unit that retrieves and stores all source operands of an instruction, like an OCU, and includes extensions to reuse them. Second, CCUs operands can be updated with the results of some instructions. This increases the reuse possibilities, but it may have significant energy and area overhead if done for all the results. This would require multiple write ports and a significantly bigger crossbar since multiple instructions of the same warp may simultaneously reach the write-back stage. We empirically verified that adding one single write-back port in each CCU provides almost the same benefit as an unbounded number of ports. To reduce energy consumption, Memento uses a write filtering policy to avoid writes that are unlikely to be reused. To filter writes, a new tri-state buffer 2beside buffer 1is added, which is controlled by the RF arbiter. The arbiter squashes some specific write requests based on their reuse distance. Third, information about the CCUs status is provided to the issue scheduler and the CCU allocator to improve their effectiveness, as described in detail in section IV-B. C. CCU Microarchitecture To exploit the temporal locality in the RF accesses, conventional OCUs are augmented with caching capabilities. The baseline OCUs already have storage to keep registers’ data and some metadata. Memento turns the OCU into a cache while keeping its previous functionality by adding extra fields and modifying the control logic. This new unit is called CCU, and Bank 1 Bank 2 Dispatch Scheduler Writes CCU 1 1 S D CCU 2 S D SIMD EUs Reads R R To Issue Scheduler & CCU allocator 2 Arbiter Fig. 4: Memento RF microarchitecture CCU CCU Control Logic Cache Table R To Issue Scheduler and CCU Allocator To Dispatch Scheduler Operand Collector Table 3 4 3 MUXs 55 55 Metadata Warp ID Instruction 3Data 8Tag 8 Lock 8 Reuse Distance 8 LRU 8 Data 3 Tag 3 Lock 3 Reuse Distance 3 LRU 3 Data 2Tag 2 Lock 2 Reuse Distance 2 LRU 2 Data 1 Tag 1 Lock 1 Reuse Distance 1 LRU 1 3334 S 4 D 5 3 3 Index 6Valid 6 Ready 6 Index 1Valid 1 Ready 1 Index 2Valid 2 Ready 2 Fig. 5: CCU microarchitecture its microarchitecture is shown in Fig. 5. The components in white color were already in the OCU; the rest are the new hardware required by Memento. Each CCU has three ports named by letters: a) port S for receiving the source operand values from the RF banks; b) port D to receive the value written to the instruction’s destination; and c) port R to communicate information between the CCU and the Issue scheduler and CCU allocator, i.e., Warp ID and the reuse distance of the live values in the CCU. In addition, each CCU contains five main parts that are described below. Metadata: The metadata contains information required to dispatch the instruction occupying the CCU and information needed in the following stages of the pipeline such as the Warp ID, target EU, etc. This metadata is the same as in the baseline architecture. Cache Table(CT): The CT is the component that provides the caching capability. The higher the number of CT entries, the greater its capability to reuse but also its overhead. Its cost is proportional to the number of entries, whereas its extra reuse potential increases in a sub-linear manner, and beyond a given size, it reaches a point of diminishing returns. Our analysis shows that eight entries is the sweet spot of this curve, and it is what we consider in this work. Note that the baseline OCU 4 has six entries so Memento simply adds two additional ones. The CT contains the data values and some information required to manage them as a cache: tags, lock bits, reuse distances, and Least Recently Used (LRU) priority information. Data fields store 128B register values, representing the largest area in each CCU. The tag is the register identifier. In CUDA [58] the maximum number of addressable registers per thread is 256; therefore, the tag is only one byte. The lock bit indicates that the register is allocated to one of the source operands of the instruction occupying the CCU, pending to be dispatched. It informs the replacement policy to avoid replacing this register since all the source operand values are required when the instruction in the CCU is dispatched to the corresponding EU. The reuse distance is computed by the compiler as explained in section III-A and shows how far the next reuse is. Information about the reuse distance of the values in each CCU and the warp id is made available to the issue scheduler and CCU allocator through port R. In particular, a single bit is sent indicating whether the CCU contains any near value in the CT or not. The LRU field represents the priority order needed for an LRU cache replacement policy. In our case, three bits are enough to show the order of replacement of eight blocks. Operand Collector Table (OCT): The OCT has 6 slots (to support tensor core instructions), one per source operand, to keep track of the status of the source operands of the instruction occupying the CCU. Each source operand slot has a valid and ready bit with the same functionality as the baseline, besides an index field. The index field stores a pointer to the CT entry containing the source operand’s data, thus implementing indirect indexing. This indirect indexing eliminates the need for redundant data values and improves the effective use of the available small cache space. Since, in our design, the CT is of size 8, the index field requires 3 bits. MUXs: Once an instruction has all its source operands ready and is selected to be dispatched to the corresponding execution unit, these MUXs are used to deliver its source operands to the input latches of the execution unit. The size of these MUXs is proportional to the number of entries in the CT. Therefore, keeping the CT size small reduces the MUXs overhead. CCU Control Logic: It is responsible for controlling the CCU to support the four operations detailed in section III-C1 below. 1) CCU Operations: Four operations are required in the CCU: 1) CCU allocation; 2) receiving a source operand value; 3) receiving a destination operand write request, and 4) dispatching the instruction occupying the CCU to the corresponding EU. CCU allocation: When a CCU is allocated to a new instruction, the fields denoted by 3will be used and updated as follows. First, the CT is flushed if the warp id of the new instruction is different from the warp id of the previous one, stored in metadata. This is necessary as warps have a private register set. Second, the metadata part will be updated with the information of the new instruction received over port R. Third, for all the source operands of the instruction, a tag check is performed to see whether they are already present in the CCU. In case of a miss, a new CT entry will be allocated for the operand, by replacing one of the entries according to the replacement policy. Fourth, Certain CT fields require updating, including setting the lock bit, updating the reuse distance with the new instruction’s reuse distances, and updating the LRU fields. While theoretically, the reuse distance field of all registers should be decreased for each new instruction, we propose to only update the reuse distance of the registers belonging to the new instruction. Our analysis confirms that this simplification is effective and avoids the overhead of updating the reuse distance of all the registers in the CT for every CCU allocation. Fifth, read requests to the RF banks for all the missed values are sent. Sixth, the OCT fields are updated. The valid bit is set, and the index field is updated to point to the corresponding CT entry for each source operand. The ready bit is set for the values found in the CT. For the remaining operands, the ready bit will be set once the value is received over port S. Receiving a source operand value: As soon as a requested source operand value arrives over port S, its corresponding ready bit in the OCT is set, and the data is stored in the data value field. The involved fields and ports are denoted by 4. Receiving a destination write request: The ports and the fields used in this operation are marked with 5. The register id is looked up in the CT to check whether the register is present. In case of a miss, an entry is replaced and allocated to this write. The data is copied and the reuse distance and LRU fields are updated. Unlike source operands, there is no need to set the lock bit, since the cache block can be replaced with no harm. To avoid cache pollution and use the small space of the cache efficiently, the cache block allocation for destinations is postponed to the cycle when the instruction reaches the writeback stage of the pipeline, unlike source operands that are allocated when the instruction is issued to the CCU. Dispatching an instruction to an execution unit: An instruction is ready to be dispatched as soon as all its source operands have been received, that is when all the valid source operands have the ready bit set. IV. MEMENTO POLICIES Memento uses efficient and lightweight management policies. A key aspect of these policies is that they leverage the reuse distance information provided by the compiler. Even though our baseline is limited to two OCUs, Memento supports systems with any number of OCUs. Our analysis demonstrates their efficacy as the number of OCUs increases. This section presents the policies for any number of OCUs. Section IV-A explains the RF cache policies, and section IV-B presents the issue scheduling/CCU allocation policy used by Memento. 5 A. RF Cache Policies Efficient RF cache management policies are crucial for maximizing Memento’s hit ratio and performance, given its small cache size of 8 blocks per CCU, and the need to support tensor core instructions. Tensor core instructions require up to 6 sources and 2 destinations and tend to have long reuse distances, which makes the design of effective policies more challenging. The cache policies should avoid cache pollution and suboptimal replacements to minimize unnecessary capacity misses. In addition, they must minimize issue stalls due to having all CCUs occupied. Section IV-A1 explains Memento’s replacement policy, and section IV-A2 elaborates on the write policy. 1) Replacement Policy: Memento’s cache replacement policy gives priority to keeping registers with near reuse distance. The policy first excludes all registers with the lock bit set, as they are source operands needed when the instruction is dispatched to the execution units. Among the remaining ones, it randomly selects one among those registers with a far reuse distance, if any exists. If there are no far registers, the replacement is chosen according to the LRU policy. This policy reduces the sub-optimal replacement of values with near reuse by LRU while maintaining its benefits. 2) Write Policy: In Memento, when a warp instruction completes execution and reaches the write-back stage, the destination register is updated in the RF banks if its data is not present in any CCU. This can occur if the CCU that originally contained the data was reallocated to another warp while the instruction was still in the EU pipelines, causing the data to be flushed. Otherwise, the data is also written in the CCU only if its reuse is near. Writes with far reuse distance are not cached to reduce cache pollution and energy waste caused by writes that may be replaced without being used. Multiple writes to the same CCU may arrive simultaneously since multiple instructions of the same warp with different latencies may reach the write-back stage simultaneously, even if they started execution in different cycles. To avoid the overhead of multiple write ports, Memento selects the one of the writes with near reuse distance, if any. We empirically verified that a single port provides benefits very close to an unbounded number of ports. Note that since the RF banks are always updated for all the write requests, any CCU’s cache can be flushed at any time with no additional action required. B. Issue Scheduling and CCU Allocation Policy The scheduling policy consists of two parts: one that selects a warp based on priority and another that uses a CCU allocation policy to choose the target CCU. Each scheduler issues an instruction only if there is a ready warp and a free CCU; otherwise, the issue stage is stalled. Moreover, Memento uses a lightweight waiting mechanism that stalls the issue sometimes, to enhance the effectiveness of the CCU allocation policy and maximize both IPC and hit ratio. Fig. 6 depicts these policies which are described in detailes in the next sections. In particular, section IV-B1 elaborates Warps with data in CCUs Rest of Warps Dynamic Algorithm → Stall Threshold (STHLD) Not allocate CCU Allocate same CCU Yes No Yes No Oldest Youngest Oldest Youngest No Same last warp 1 Yes Yes No Yes Any free CCU? Any free far CCU? Counter >= STHLD? Has data in CCUs? Its CCU is free? No For each warp check if... Randomly allocate one of them 0 CCU Allocation Policy Issue Scheduling Policy Warp Priorities GPU 1 2 Counter rst +1 3 4 5 6 7 89 Fig. 6: Memento issue scheduling policy definition and its interaction with the dynamic algorithm on Memento’s warp priorities, section IV-B2 details the CCU allocation policy, and section IV-B3 explains a dynamic algorithm to determine the waiting time. 1) Warp Priorities: The Greedy Then Oldest (GTO) warp priority scheme has been proven to effectively reduce contending memory accesses to the memory hierarchy in GPUs [61]. GTO prioritizes the warp that issued the most recent instruction and if it does not have a ready instruction, then it selects the oldest warp with a ready instruction. However, this scheme is agnostic to the state of the RF cache and results in a low RF hit ratio. Memento proposes a new warp priority denoted by 1in Fig. 6. Similar to GTO, the highest priority is to the same warp if it is ready. The remaining warps are then divided into two categories: those having data in CCUs and the rest. Within each category, they are prioritized by their age. This approach retains the benefits of GTO by prioritizing the last issued warp overall and respecting the warps’ ages in each category while it increases RF cache reuse by prioritizing warps with data in the CCUs. 2) CCU Allocation Policy: Memento CCU allocation policy is in box 2in Fig. 6 . In this graph, cases when a CCU is allocated are highlighted in green, while other cases, where no CCU is allocated, are highlighted in red. Memento allocates the same CCU to a warp that has data in a CCU only if the CCU is free 3. If the CCU is already occupied, no other CCU will be allocated 4. By using this approach, Memento can avoid the overhead of implementing a complex cache coherence protocol, as no warp can have data in more than one CCU. When none of the CCUs is allocated to the warp, Memento assigns a target CCU based on the reuse distance of values in the CCUs and flushes the cache. This flush reduces the potential hit ratio if the reuse distance of the flushed data is near, so Memento randomly selects a free CCU that contains 6 0.92 0.94 0.96 0.98 1 1.02 012345 bfs lud rnn_i2 (a) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 012345 bfs lud rnn_i2 (b) Fig. 7: IPC and hit ratio of benchmarks ran for 10000 cycles for different STHLD values: (a) Normalized IPC, (b) Hit ratio only values having far reuse (i.e. far CCU), if any exists 5. If all CCUs are occupied 6, no allocation is made. If some CCUs are free but they contain some values with near reuse, allocating any of them to the new warp would potentially harm the hit ratio but not making any allocation may harm performance. To deal with this trade-off, Memento employs a waiting mechanism that uses a per-core counter and a perGPU threshold, STHLD. If the counter is lower than STHLD, no CCU is allocated 7and the counter is increased 8. Otherwise, a randomly selected free CCU is allocated, and the counter will be reset 9. This waiting mechanism postpones the CCU allocation of CCUs that contain near values. During this time, an instruction of an ”old” warp having data in any of these CCUs may finish execution and reach the write-back stage, which may resolve a data dependence. After that, the warp currently using this CCU becomes ready and can issue instructions that may reuse the data in CCUs. Delaying the allocation of CCUs may cause a performance drop only if it lengthens the critical path of the application’s execution. However, Memento does not cause any performance penalty; in fact, it improves performance (as discussed in section VI-B1) since the RF cache reduces bank conflicts. 3) Dynamic Algorithm to set STHDL: Fig. 7 depicts the IPC and hit ratio of three applications when changing STHLD. Although all applications gain hit ratio from higher STHLD values, some sensitive applications, such as srad v1 start to lose performance even with small STHLD values, such as STHLD=1. The optimal STHLD is different for each application, and even for each different phase of the same application. Using a wrong STHLD may significantly penalize IPC or hit ratio or both. Because of this, Memento uses a dynamic algorithm to set the STHLD value. The higher STHLD is, the higher the chances of benefiting from reuse, so if we plot the curve of RF cache hit ratio versus STHDL, we will get a monotonic growing curve. On the other hand, higher STHLD values lead to more stalls generated by the CCU allocator, which may damage performance. We can expect that if we increase STHLD we will initially have small fluctuations, until a point when IPC starts dropping dramatically. This point is different for each different code and we will refer to it as the knee point. The region to the left will be called the flat region and the region to the right will de denoted as the steep region. Therefore, the optimal STHLD is at the knee point, since it provides the highest IPC and hit 1 2 3 4 5 6 S/+1 L/+1 S/+1 */+1 L/-2 S/+1 S/0 L/+1 L/-1 L/-1 S/+1 Fig. 8: Dynamic algorithm to set STHLD 2 1 STHLD IPC STHLD After 4 Steps (a) 6 3 4 5Large IPC Change 2 STHLD IPC (b) 6 3 4 5 Large IPC Change 2 IPC STHLD (c) 3 Large IPC Change 2 IPC STHLD (d) Fig. 9: Example of setting STHLD: (a) Initial curve and first four steps, (b) Next steps when staying in the same curve,(c) Next steps when transitioning to a curve with a narrower flat region, (d) Next steps when transitioning to a curve with a wider flat region. ratio. Most GPU applications are quite regular or have regular phases, therefore, the characteristics of the application remain similar for long intervals until the application phase changes. Motivated by that, Memento’s scheme partitions the execution into equal intervals and set the STHLD at the end of each interval. It uses the IPC measured in the previous and current intervals to modify the STHLD for the next interval. After several intervals, the STHLD converges to its optimum point. The dynamic algorithm adopted by Memento is described in Fig. 8 by a finite state machine. It has 6 states and the transitions among the states happen based on the relative difference in IPC of the current and the previous interval. A relative difference of less than 0.02 is considered small and is denoted by S. A relative difference of more than 0.02 is considered large and denoted by L. The value of 0.02 has been empirically set to provide a good performance and hit ratio trade-off. The asterisk symbol shows the transitions happening regardless of the relative IPC difference. Once a transition happens, the STHLD will be increased or decreased by a delta shown on the transition edges. The behavior of the dynamic algorithm is illustrated in Fig. 9. In this figure, the corresponding state is shown by a number, and the arrows showing steps taken in each state are colored the same as the circled number showing the corresponding state. Fig. 9 shows that the dynamic algorithm is designed to walk on the curve and, based on the IPC fluctuation, modify the STHLD until it converges near the knee point. The knee point is the optimum STHLD. 7 In this example, the algorithm started on the curve shown in Fig. 9a, and after four intervals with a small change in IPC, a large change is detected. The large change could be due to moving to the steep region of the same curve, Fig. 9b, or a change in the application phase that changes the curve to the curves shown in Fig. 9c or 9d for the following next intervals. The curve changes as the phase of the application changes because the characteristics of the application differ. The new curve may have a narrower (Fig. 9c) or wider (Fig. 9d) flat region. In case of moving to the curve with a narrower flat region, the current STHLD will be in a steep region and the adaptive algorithm will reduce it to reach the STHLD corresponding to the knee point of the IPC curve. On the other hand, in the case of moving to the curve with a long flat region, the current STHLD will be in the flat region, so the dynamic algorithm will increase the STHLD to approach the knee point of the new IPC curve. In case of a large change, the dynamic algorithm takes a speculative move by increasing STHLD to gain more hit ratio and moves to state 3. If the new phase corresponds to the curve shown in Fig. 9d, the speculative move was correct and we benefit from the increased IPC and hit ratio due to a higher STHLD in that interval. On the other hand, if the phase has the same curve, Fig. 9b, or the curve shown in Fig. 9c, we lose performance since the speculative move was in the steep region where performance decreases when STHLD is increased, but only for one interval. After realizing that this speculative step is detrimental, the scheme decreases STHLD and after some additional steps, it converges to the optimal point. The dynamic algorithm remains in state 6 when finding the knee point until a large IPC change is detected. We empirically found that an interval size of 10000 cycles provides a good trade-off between performance and hit ratio. V. METHODOLOGY We use Accel-sim [28] to model a GPU configuration based on the Geforce RTX 2060 [55] GPU with the parameters shown in Table I. We scaled down the number of SMs, the size of L2, and the number of memory channels by one-third to compensate for the fact that most of the available benchmarks are much shorter than real applications running on GPUs and to prove the dynamic algorithm’s effectiveness. The benchmarks are from Rodinia [13] and Deepbench [9] and are listed in Table II. The former suite is representative of general-purpose computing applications, whereas the latter consists of modern deep learning workloads. For Deepbench, various tensor dimensions are used for training and inference. This is shown in the charts by an underscore followed by t, for training, or i, for inference, followed by an id. We used accel-sim in trace mode and annotated the traces with precise reuse distances. Then we provided the simulator with the binary reuse distance to be used by Memento. To evaluate the dynamic energy of the RF, we extended the power model provided in Accelwattch [27] to model the CCUs. The model includes the arbiter, crossbar, RF banks, #SMs 10 #Threads/Warps per SM 1024 / 32 #sub-cores per SM 4 RF size per SM 256KB #Issue Schedulers per SM 4 Issue Scheduling Policy GTO L2 size 1MB L1/Shared Memory per SM 64KB TABLE I: Baseline GPU configuration used in this work B+tree [13] Backprop [13] nn [13] DWT2D [13] Gaussian [13] lud [13] Kmeans [13] LavaMD [13] gemm [9] srad v1 [13] particlefilter float (PTCLFF) [13] conv [9] Hotspot [13] particlefilter naive (PTLCFN) [13] rnn [9] BFS [13] pathfinder [13] TABLE II: Used benchmarks and CCUs. For the baseline model, instead of CCUs, the conventional OCUs were modeled. VI. EVALUATION A. Comparison with RFC, Software RFC, and LTRF RFC, software RFC, and LTRF use a two-level scheduler to keep the RF cache overhead reasonable. The scheduler divides warps into two sets: active and pending. Only active warps can issue instructions while pending warps need to become active before issuing instructions. A two-level scheduler can be in one of three states in each cycle: 1) it issues an instruction, 2) it does not issue an instruction but there is a ready warp in the pending set, or 3) it does not issue an instruction and there are no ready warps. The issue stalls in the second state are avoided by a one-level scheduler and cause a performance penalty. This penalty is significant when using a two-level scheduler in a modern sub-core-based architecture because the scheduler manages a few warps in a sub-core, and even fewer are active. When very few warps are active, they cannot hide short latencies, and the two-level scheduling policies fail to move warps to the active set soon enough, resulting in the scheduler being in state 2 very often. Fig. 10 depicts the average distribution of these states for the two-level schedulers proposed in RFC and software RFC. This experiment was conducted for all benchmarks running on an architecture with the baseline configuration, except that the two-level schedulers were implemented. Both schedulers had six pending and two active warps per sub-core (24 pending and 8 actives per SM). RFC and software RFC are in state 2 for 37.6% and 43.8% of the cycles respectively. This leads to an IPC loss of 9.9% for RFC and 12.9% for software RFC on average. The IPC drop can be very high in some applications, reaching 41.3% in RFC and 50.9% in software RFC for hotspot (Fig. 2). This important IPC loss outweighs the potential benefit of their RF cache scheme for a modern sub-core-based architecture. Moreover, in software RFC and LTRF, the compiler is responsible for statically allocating the registers of the cache to values. To correctly perform this allocation, the compiler must know in which order the instructions of each thread will 8 0% 20% 40% 60% 80% 100% RFC Software RFC Issued Not issued and no warp was ready Not issued but a ready warp was in pending set Fig. 10: Distribution of the state of RFC and software RFC twolevel schedulers in each cycle Forwarding Logic Source 1 Source 2 Source 6 Destination 1 Destination 2 Instruction 3 1KB 128B Bypassing Operand Collector Instruction 1 Instruction 2 Fig. 11: Bypassing Operand Collector (BOC) Architecture be executed. This was possible in early GPU architectures but it is not in recent architectures that interleave the execution of divergent paths of branches. This interleaving is decided at runtime and thus it is unknown to the compiler, which prevents it from performing this static allocation. B. Comparison with BOW The BOW scheme is the closest scheme to Memento. It captures reuses within a sliding window by replacing OCUs with Bypassing Operand Collectors (BOCs), Fig. 11. BOCs buffer sources and destinations of instructions within a sliding window and forward operand values found in the buffer to the next instruction, rather than requesting them from the RF banks. To support tensor core instructions, a BOC has to buffer 6 sources and 2 destinations per instruction, amounting to 3×8×128B= 3KB, for a sliding window of size 3. BOW uses private BOCs per warp to avoid the penalty of time sharing a BOC by multiple warps. This requires a 32 ×3 = 96KB BOC buffer, 4 crossbars of 2×81024 bits for an SM having 32 warps, and 4 sub-cores (our baseline). Time sharing a BOC among multiple warps increase the reuse distance in a nondeterministic way, as each warp has a private register set, and requires a bigger buffer in BOC to capture temporal locality. To make a fair comparison, we also evaluate a version of Memento having private CCUs per warp, Memento PR. Detailed comparisons can be found below. 1) Performance:Memento improves performance due to the high hit ratio and reducing bank conflicts but on the other hand, it may negatively impact performance when postponing CCU allocation. Fig. 12 shows that Memento has a negligible IPC loss of 0.8% in the worst case (b+tree) and for most applications sustains or significantly increases performance. It improves IPC by 6.1% on average and 28.4% at maximum for rnn i2. Compared to Memento, BOW offers a higher IPC of 2.43% on average and 18.8% in the best case (hotspot). However, achieving this requires a private BOC per warp, which needs 8 BOCs per sub-core amounting to 8×3KB = 24KB which is 12×the cache space of Memento, and a much bigger crossbar. Modern GPU architectures do not have a private OCU per warp to avoid this huge overhead because this would be too energy-hungry and not cost-effective [11], [23] so we conclude that Memento is a more costand energy-effective scheme. However, to make a fair comparison, we compare BOW with Memento PR, which also has private CCUs per warp. In Fig. 12 we can see that Memento PR provides an IPC 3.3% higher than BOW on average and 12.7% in the best case (rnn i2). It only provides a lower IPC for gemm t1 (1.7%) and rnn t2 (1.2%). Memento PR clearly outperforms BOW while requiring much lower cache storage, 33% of BOW’s, and a smaller crossbar for writes. Although a higher RF hit ratio leads to better performance for most applications, this is not always the case. For instance, PTCLFF has a higher RF hit ratio (Fig. 13) in BOW yet provides almost the same IPC as Memento (Fig. 12). This happens when there is a bottleneck in other stages of the pipeline which limits the IPC gain. In this benchmark, the memory pipeline is the bottleneck and restricts the IPC gains from BOW. Another case is lud, lud shows a 13% higher RF cache hit ratio for BOW (Fig. 13) but its performance is slightly worse (Fig. 12). This is because BOW and Memento have different numbers of BOCs and CCUs that are managed by different scheduling and cache policies which results in different nondeterministic runtime behaviors. This runtime behavior determines the performance. In this case, our analysis shows that the bottleneck is in the memory pipeline and lud does not benefit from a higher hit ratio in the RF cache in BOW (Fig. 13). However, in this case, Memento benefits from a higher hit ratio in the L1 data cache which is 2% higher than that of BOW. 2) RF Cache Hit Ratio:The hit ratio of the RF cache depends on its management policies. BOW proposes a private cache per warp to remove interleaving access from other warps, but this comes with significant overhead. BOW manages the cache as a sliding window, which requires a large buffer in each BOC to reuse far values. In modern architectures supporting tensor cores, register value reuse distances are long and nondeterministic due to the tensor cores API and control flow management policies. Fig. 1 shows that 36% of reuses in Rodinia and 50.2% in Deepbench have reuse distances farther than 3, requiring a BOC buffer storing more than 3 instructions to exploit these reuses, which would incur in a significant overhead. Memento leverages the runtime reuse distance provided by the compiler to guide the cache management policies and manages to exploit many reuses with a very tiny cache. Its 9