Bounding the WCET of a GPU Thread Block with a Multi-Phase Representation of Warps Execution

Figure 5 shows the overall architecture described in the GPGPU-Sim 4.X performance model employed in Accel-Sim. At the highest level, the GPU contains a number of SMs depending on the simulated hardware. All the SMs share an L2 cache supplied by the global memory (HBM/GDDR). Each SM contains an instruction cache shared by an arbitrary number of sub-cores. A sub-core comprises a warp scheduler, a register file and a set of functional units of different types and count. The sub-cores of an SM also share a constant cache as well as an L1 data cache and shared memory. All these elements constituting the GPU can be modified through simulator configuration or directly by tempering with the source code.
In Accel-Sim, when a GPU program is initiated by the CPU, a Thread Block Scheduler is in charge of dispatching the thread blocks to the available SMs. A thread block is dispatched to an SM if its available resources are sufficient for the execution. Limiting resources can be of different nature : amount of free shared memory, number of unoccupied registers or constant cache space. Once a block has successfully been dispatched to an SM, its warps are allocated to the SM’s sub-cores. Inside a sub-core, it is the job of the warp scheduler to select ready instructions belonging to its attributed warps from the instruction buffer. The selected instruction is then issued and dispatched to its functional unit.

Accel-sim can be modified indirectly through a configuration file, or by directly changing the source code. For the configuration file, the starting point was a file shipped with the simulator describing the Nvidia RTX3070, which is under the Ampere architecture. The use of this specific configuration is motivated by the fact that the Jetson Orin Series were produced under the same architecture, for the embedded systems market. This file was changed so the simulated GPU contains only one SM, itself containing a single sub-core as only one thread block is considered in this paper. L1 and L2 cache were disabled since data cache analysis is out of the scope of this work. GPUs present a feature called dual-issue that allows a warp to issue two instructions at the same cycle if they are both ready and not targeted at the same functional unit. This feature was disabled to comply with Simplifying assumption 1. The instruction buffer was configured so it always holds available instructions to enforce Simplifying assumption 4. Further modifications were made to the source code of the simulator. Bank conflicts for shared memory were removed and a new functional unit was implemented to handle global memory accesses, in compliance with Simplifying assumption 2.

We applied our approach to the Rodinia Benchmark Suite. Rodinia is a collection of benchmarks targeted at heterogeneous calculators, comprising at least one CPU and one GPU. Therefore, it contains multiple programs executing on CPU and calling for GPU procedures to execute kernels. It is also, at the time, the most documented and maintained GPU benchmark suite. It contains a diversity of applications, making it suitable to find potential edge cases for the model. The benchmark suite was modified so that each kernel be limited to a single thread block and thus executes on a single SM. Rodinia contains 23 programs totaling 58 different kernels and 583 different calls to these kernels with varied call contexts.

In order to assess the impact of our simplifying assumptions and of the corresponding modifications of the simulator on the performance of the target GPU, we conducted an ablation study, the results of which are depicted in Table 4.1. We started with the standard version of the simulator, configured to mimic a single SM from the GPU of the Jetson Orin. We call this version baseline in the ablation study. From this baseline, we incrementally remove components and features, until we obtain the configuration that complies with our simplifying assumptions and that was used for the experiments of Section 4.2. Each step of this simplification corresponds to a column in Table 4.1. In each column, two variants of the architecture are compared: for each kernel instance in the benchmark, we compute the speedup (by dividing the number of execution cycles) obtained by variant A compared to variant B, in percent, and then display the mean speedup, as well as the standard deviation and the minimum and maximum speedups across the set of benchmarks. A speedup lower than 100% means that variant B incurs a longer execution time than variant A.

The first column of Table 4.1 shows the comparison between the baseline and a variant in which accesses to the instruction cache always result in a hit. This is how we enforced Simplifying assumption 4 in our version of the simulator. As we can see, on average, this modification only incurs a speedup of 11% compared to the baseline, on the Rodinia benchmarks. In some cases, the modified version is close to 5 times faster than the baseline. Some benchmarks for which all the code holds in the instruction cache execute slightly faster in the baseline configuration, due to some timing anomalies in the memory subsystem.

In the second column, we compare a variant with four sub-cores to a variant in which only one sub-core of the SM is active (both with an instruction cache that always hits). The performance of using only one sub-core, compared to the original 4 sub-cores of the baseline, has a negligible impact on the performance (less than 6% on average). This is explained by the fact that most of the benchmarks of Rodinia are not optimized to efficiently mask the latencies induced by memory accesses in a single block. The maximum speedup of 101%, which means that the variant with one sub-core is faster than the baseline by 1%, is unexpected. After investigation, it is due to a timing anomaly related to concurrent memory accesses.

The third column compares a variant with dual instruction issue to a single issue variant (both with an instruction cache that always hits and a single sub-core). Indeed, most current commercial GPUs implement a dual-issue mechanism that allows each sub-core to issue up to two instructions per cycle, with certain restrictions. We disabled this mechanism in order to comply with Simplifying assumption 1. The ablation study shows that for the Rodinia benchmarks, the dual-issue mechanism yields a negligible impact on performance.

The fourth column compares a variant with a data cache to a variant in which the data cache has been disabled to comply with Simplifying assumption 3 (both with an instruction cache that always hits, a single sub-core and single-issue). On average, considering that there is no data cache in the architecture only slows down the execution by 9% (with a standard deviation of 13%). This is coherent with benchmarks in which either there is not much re-use of the loaded data, or the data that needs to be re-used is explicitly loaded in the shared memory. In the worst case, the performance is decreased by 65%. Some benchmarks are running faster on the cache-less variant (up to 25% faster). This happens with benchmarks in which nearly all memory accesses result in a cache miss. Indeed a cache miss takes longer than a direct access to the memory, because the cache incurs a few cycles of additional delay to determine whether the access is a hit or a miss.

Finally, the last column compares a variant with a memory coalescing mechanism with our variant, in which all memory accesses are considered coalesced and pipelined, to comply with Simplifying assumption 2 (both with an instruction cache that always hits, a single sub-core, a single-issue and no data cache). Note that our variant thus complies with all simplifying assumptions. This last variant is on average 2.3 times faster than the previous variant, with a peak at nearly 3 times faster on certain benchmarks. This is not a surprise as coalescing accesses reduces the number of memory requests and thus of cycles spent waiting for the memory to reply. Since we assume that all accesses can be coalesced, which is not true in practice, the number of transactions is significantly (and artificially) reduced, and so is the execution time.

This ablation study shows that as expected, our simplifying assumptions have an impact on the performance of the GPU. However, taken separately, three out of four of these assumptions have an average impact inferior to 12% on the execution time of the considered benchmarks. The last assumption, regarding the memory coalescence mechanism has a major impact, which tells us that relaxing this assumption should be our priority in future work.

The simulator allows the user to execute workloads either from PTX or from SASS code. As mentioned earlier, SASS is the mISA and PTX the vISA, both from Nvidia. However, SASS instructions are often poorly documented and require a huge work of reverse engineering in order to understand it properly. Moreover an Nvidia SASS program is strongly related to a particular architecture, which is not the case for PTX. For these reasons, PTX assembly is used for the simulation of kernels. The Nvidia vISA is not constrained to a particular architecture and its well documented nature allows for precise understanding of instructions behaviour and mapping to functional units.

We executed GPU workloads on our modified version of Accel-sim. Execution traces of the GPU payloads are extracted from the simulations. We call kernel instance the trace resulting from a single execution of the kernel in question. This trace contains information about the order in which instructions are executed, as well as the identifier of the warp that issued them. We developed an analyzer that is able to process the trace for each warp following the procedure described in Algorithm 1. It takes as input a warp execution trace and a simulator configuration file that specifies the timing data of the FUs. From those, it produces a timed execution profile corresponding to the execution of the warp in isolation. When all the execution profiles of a thread block have been generated, the GUB can be calculated, giving an upper-bound for the WCET of the block. Some kernels contain thread synchronization barriers that temporarily pause the execution of threads until all of them have reached the barrier. From the point of view of the upper bound calculation, sections separated by thread synchronization are processed independently. Then the upper-bounds of all the sections are summed together to give the upper bound for the block. We decided to work on simulation traces to retrieve the execution path of the warps as, to the best of our knowledge, there exists no analysis that derives the worst possible path (or an abstraction of such a path) for a given GPU kernel. Yet, our approach can be used in conjunction with such an analysis when one will exist.

We start with the evaluation of the accuracy of the multi-phase models extracted using Algorithm 1. We generated a separate multi-phase model for each of the 583 kernel calls, using a configuration file from Accel-sim and the simulated traces. During the construction of the model, the procedure checks that the computed time of issue (resp. time of dispatch, time of writeback) for each instruction matches the actual issue time (resp. time of dispatch, time of writeback) in the trace. Once the multi-phase profile is created, the end time of the last phase is compared to the end time of the last instruction in the trace. Table 3 provides the results of the comparison of the end times, in the rows labeled S.w. (Single warp). For 60% of the kernel calls, the constructed profile matches every single instruction issue, dispatch, write-back and overall end times when compared to the timings from the simulator. The rest of the kernel calls make use of the $setp$ instruction to generate predicates. We observed that the execution time of this instruction can vary by 1 latency cycle depending on the execution context. In order to keep our analysis conservative, the instruction is considered to always take its worst-case duration. This explains the slight overestimations (always less than 1.5%) in Table 3.

We now evaluate the accuracy of the approach as a whole, by comparing the end time obtained by computing the GUB for a given block with the end time we measure by simulating the execution of the block in Accel-sim. Multiple simulations of the Rodinia benchmark have been carried out with various global memory latencies and using both the GTO and LRR scheduling policies. A realistic value for the global memory latency would be around 200 cycles. However, considering shorter and longer latencies allows better understanding the behavior of our model. Table 3 displays the overestimation induced by the GUB compared to the actual simulation time of the blocks, for the 583 kernel calls. We display the mean of the overestimation across all kernel calls along with the associated standard deviation. We also display the maximum overestimation computed on each individual kernel call, and a weighted mean that combines the overestimations with the length of the corresponding kernels. The overestimations result from two distinct factors. First, the multi-phase model does not allow to take into account the fine-grained intertwining of initiations for instructions from separate warps. This is the abstraction cost of this model, that on the other hand simplifies the computation of the upper bound on the execution time. Second, the GUB fails to account for the masking of instruction latencies by the initiation of other phases, which is one of the principles of GPU execution. Put in terms of execution and idle phases, the inaccuracy of the GUB peaks when the combined durations of the idle phases of one warp match the combined durations of the execution phases of all the other warps in the block. Indeed, in practice the initiations corresponding to the execution phases are likely to mask the latencies corresponding to the idle phases, while the GUB sums their durations to remain conservative. Once again, this results from a trade-off between the accuracy of the method and its simplicity. The maximum overestimation (72.47%) occurs for an individual kernel scheduled with the LRR policy and with a memory latency of 25 cycles. However, the mean overestimation for the LRR scheduling policy varies between 8.21% and 26%, with a value of 12.31% when the memory latency is 200 cycles, which remains acceptable. For GTO the overestimations are slightly higher. However, since our method is agnostic about the scheduling policy, the GUB is in fact the same in both cases. The variation between LRR and GTO simply results from the fact that on average, the GTO policy yields shorter execution times on our benchmarks.

On top of the Rodinia benchmarks, we propose a case study on two implementations of the SGEMM (Single-precision GEneral Matrix Multiplication) algorithm. This algorithm is particularly relevant as it is likely to be used to accelerate machine learning applications such as Deep and Convolutional Neural Networks for embedded computer vision applications and autonomous driving. Basically, the objective of SGEMM is to compute the product of two input matrices.

The first implementation, labeled naive, is a direct implementation of the SGEMM algorithm, that is likely to work only on small matrices. The second implementation is an optimisation of the direct algorithm that relies on a double buffering mechanism to hide the latencies of memory copies. It is able to undertake more important workloads.

In the algorithm, the product matrix is computed using multiple thread blocks, each being is responsible for computing a tile of the product matrix. To do so, the warps composing a block need data contained in multiple tiles from both the input matrices (a row of tiles from one matrix and a column of tiles from the other). The algorithm thus works in the following fashion: a) the warps copy a tile from each of the input matrices from the (slow) global memory to a (fast) SRAM scratchpad called shared memory; b) the warps synchronize using a barrier to make sure that all the data composing the tiles is available in the shared memory; c) the warps perform the tiles multiplication and accumulate it in the result tile; d) the same sequence is performed with the two next input tiles. In the remainder of the section, we call $Repeatedsequence$ the sequence composed of a), b) and c). Figure 6 depicts the timing of a single warp performing this algorithm. For space reasons, the global memory latency and the data processing time (the multiplication and accumulation) are reduced to 6 cycles each in the figure, which is not the case in our experiments. At cycle 0 a load from the global memory is issued and initiated, then undergoes its 6 cycles of latency. Once the load is completed at cycle 8, the data is stored into the shared memory in order to be accessible from all the warps of the block. At this point, a block level synchronization barrier prevents warps from reading segments of the shared memory before all the data has been loaded. Once all the warps have reached this barrier, they begin processing the data. Once a warp has performed its multiplications and accumulations for the current input tiles, another synchronization barrier prevents it from starting to copy data from new tiles, in case other warps are still reading data from the current tiles. This sequence then repeats until the all the input tiles attributed to the thread block have been processed. The issue with this naive implementation of the SGEMM algorithm is that for each pair of input tiles that the block processes, the duration of the copy of the data between the global and the shared memories is not hidden by computations, which degrades the overall performance of the block.

Our second SGEMM implementation, inspired by [10], uses a double buffering technique in order to mitigate the impact of global memory latency. Figure 7 gives the intuition behind this mechanism. The first part of the algorithm (up until the synchronization barrier at cycle 10) is the same as in the first version. We call this first portion of the execution $prologue$ in the remainder of the section. After this first synchronization, this implementation differs from the last. The algorithm still proceeds iteratively, but now, the warps start each iteration $i$ by launching an asynchronous copy of the data of the input tiles that will be processed in iteration $i+1$. While the copy is ongoing, the warps execute their multiply and accumulate operations on the data that was copied in the previous iteration (for iteration 1, the data that was copied during the prologue). When their computations are over, the warps synchronize using a barrier to ensure that the asynchronous copies are completed before moving to the next iteration. To support this optimization, the data from 4 input tiles must reside in the shared memory at once (2 for the current iteration, 2 for the copies for the next iteration). The advantage of this version over the naive one is that except for the prologue, the latency of the memory copies between the global and shared memories is hidden by the latency of the multiplication operations.

These two implementation strategies show two main differences. Firstly, the $Repeated$ $sequence$ for the naive version comprises two synchronization barriers while there is only one in each iteration of the double buffered version. Secondly, the double buffered version is able to hide most or all of the global memory latency, apart from the $prologue$, and thus yields better GPU occupancy and execution time performance.

We implemented both versions, and simulated and analyzed them for different configurations of memory latencies and number of warps. Our implementations compute the product of a matrix of size 1024*$number\mathrm{\_}of\mathrm{\_}threads$ by a matrix of size $number\mathrm{\_}of\mathrm{\_}threads$*1024, thus computing a result matrix of size 1024*1024. Table 4 provides the overestimation between the GUB and the measured execution times of the thread blocks obtained on the simulator. The GUB is consistently more accurate for the naive version than for the double buffering version. We explain this by the fact that in the naive version, the memory transfer latencies between the global and the shared memories are only very partially hidden by the execution of the instructions that perform the accesses. As discussed before one of the two sources of imprecision of our approach is that the GUB fails to account for latency hiding. When the memory latency is high, the percentage of this latency being hidden by the initiation of the copy instructions is low, which yields a high precision of the GUB. As we decrease the memory latency, the initiation of the copy instructions is able to hide a larger proportion of the copy latencies, resulting in a degradation of the precision of the GUB.

In practice, for the experiments with 32 warps, the average overestimation yielded by the GUB is around 8%, with a peak at 11.15% for the double buffering version with a memory latency of 400 cycles, which remains acceptable. The most likely case in practice corresponds to the experiment with 32 warps and a global memory latency of 200 cycles, which results in an overestimation of 8.51%. As the number of warps is decreased, the instruction execution latencies of each warp occupy a larger proportion of the execution time, relative to the overall amount of initiations. For the same reason as before, this explains why the precision of the GUB worsens as the number of warps decreases.