利用分支与数据聚集优化容错GPU应用：控制与内存分歧减缩策略
28 浏览量
更新于2024-08-25
收藏 1.11MB PDF 举报
"Branch and Data Herding是一项针对具有错误容忍性的GPU应用程序的优化技术，旨在减少控制和内存分歧，从而提升GPU性能。该研究发表于2012年的IEEE TRANSACTIONS ON MULTIMEDIA上，作者是John Sartori和Rakesh Kumar。论文的核心概念在于，许多GPU应用在面对错误时表现出一定的容错能力，这为通过控制路径统一（branch herding）和数据块共享（data herding）来优化执行提供了可能。
控制分歧指的是在同一执行束（warp）内的线程在执行流程上的不同分支决策，这可能导致计算资源的浪费和性能瓶颈。通过branch herding，所有的线程被强制遵循相同的控制路径，避免了控制指令的随机性，从而减少了控制分歧带来的影响。这种策略有助于保持处理器资源的利用率，提高并行执行效率。
另一方面，数据分歧是指同一warp中的线程访问不同的内存地址，这会引发额外的内存读取和一致性问题。数据herding通过确保所有线程加载数据来自同一内存块，消除了数据分歧，提高了内存访问的效率和一致性。然而，为了支持这样的优化，论文提出了静态分析和编译器框架，它们旨在检测并预防在引入控制和数据错误时可能出现的问题。
此外，文中还介绍了一个性能监控框架，目标是在维持可接受的输出质量的同时，最大化应用的执行速度。硬件层面的优化也包括，这些优化旨在通过利用错误容忍性，更有效地利用branch and data herding的优势，进一步提升性能。
论文的软件实现展示了如何将这些理论转化为实际操作，通过综合运用控制和数据的集中策略，研究人员不仅解决了性能问题，还展示了如何在处理潜在错误的同时，实现了高效的并行计算。这项工作对于提高GPU应用程序的性能和错误处理能力具有重要的实用价值，对于现代高性能计算和多媒体处理等领域具有重要意义。"
. 3
-40
-30
-20
-10
0
10
20
30
40
0 10 20 30 40 50 60 70 80 90 100
% forced uniform branches
% runtime reduction .
Performance increase (no software overhead)
Performance increase (software overhead)
Fig. 3. The performance of Mandelbrot can be increased by forcing
uniformity for more branches. However, if software overhead is added to
ensure branch uniformity, increasing the number of affected branches increases
overhead and can even result in degraded performance.
0
1
2
3
4
5
6
7
8
9
10
0 10 20 30 40 50 60 70 80 90 100
% forced uniform branches
% mismatched output bytes .
Mandelbrot Output Quality Degradation
Julia Output Quality Degradation
Fig. 4. While eliminating control divergence can increase performance,
blindly forcing branch uniformity can result in degraded output quality.
significant. Figure 3 shows the potential performance increase
(runtime reduction) if control divergence can be eliminated for
a fraction of the static branches in Mandelbrot (from 0% to
100% of branches). The branches are chosen uniformly ran-
domly when the fraction is less than 100%. Control divergence
is preempted by changing the source code to vote within a
warp on the condition of a branch and forcing all threads in
the warp to take the same (majority) direction at the branch
(details in Section III). Experiments were run natively on a
NVIDIA GeForce GTX 480 GPU (details in Section VI).
While only 10% of dynamic instructions in Mandelbrot are
branches, and less than 1% of branches diverge, performance
can potentially be increased by 31% by eliminating control
divergence. As the no software overhead performance series in
Figure 3 demonstrates, performance increases for Mandelbrot
as control divergence is eliminated for more branches. Figure 4
shows that the quality of the Mandelbrot output set degrades
by less than 2%, even when divergence has been eliminated
for all static branches. This shows that for certain error-
tolerant applications, it may be possible to get significant
performance benefits from eliminating control divergence for
minimal output quality degradation. A quick look at the
Julia output set, however, also suggests that an indiscriminate
selection of branches for herding may result in significant
output quality degradation for several applications. Therefore,
any implementation of branch herding needs to carefully select
the branches to target. Figure 5 shows visual representations
of the Mandelbrot and Julia output sets as the percentage
of forced uniform branches increases from 20% to 100% in
increments of 40%.
The software overhead performance series of Figure 3
demonstrates another important consideration for any tech-
nique that eliminates control divergence. Since the fraction of
Fig. 5. Progression of Mandelbrot (top) and Julia (bottom) images from 20%
to 100% forced branch uniformity in 40% intervals.
divergent branches in a program may be small (in this case,
less than 1%), an indiscriminate application of a technique
to all branches may result in significant overhead that dimin-
ishes or even eliminates performance gains that result from
reduced divergence. This result reinforces the conclusion that
care should be exercised in selecting the branches to target
for elimination of control divergence. Also, a low-overhead
mechanism for eliminating control divergence may enable
significantly more benefits. The result also confirms that na¨ıve
implementations of techniques to eliminate control divergence
may actually decrease performance in some scenarios.
B. Memory Divergence
Like control divergence, memory divergence occurs when
threads in the same warp exhibit different behavior. In the
GPU, a load operation for a warp is implemented as a
collection of scalar loads, where each thread potentially loads
from a different address. When a load is issued, the SM
sets up destination registers and corresponding scoreboard
entries for each thread in the warp. The load then exits the
pipeline, potentially before any of the individual thread loads
have finished. When all the memory requests corresponding
to the warp load have finished, the destination vector register
is marked as ready. Instructions that depend on the load must
stall if any lanes of the destination vector register are not ready.
Memory divergence occurs when the memory requests for
some threads finish before those of other threads in the same
warp [9]. Individual threads that delay in finishing their loads
prevent the SM from issuing any dependent instructions from
that warp, even though other threads are ready to execute.
Memory divergence may occur for two reasons. (1) The time
to complete each memory request depends on several factors,
including which DRAM bank the target memory resides in,
contention in the interconnect network, and availability of
resources (such as MSHRs) in the memory controller. (2)
Since the target data for a collection of memory requests
made by a warp may reside in different levels of the memory
hierarchy, the individual memory operations may complete in
different lengths of time.
Most GPU architectures do not implement out-of-order
execution due to its relative complexity and hardware cost.
Rather, GPUs cover long latency stalls by multithreading
instructions from a pool of ready warps. Providing each SM
with plenty of ready warps ensures that long latency stalls will
not be exposed. Memory divergence delays the time when
a warp may execute the next dependent instruction, cutting
into the pool of ready warps and potentially exposing stalls
剩余11页未读，继续阅读
2021-03-21 上传
2021-05-15 上传
2021-05-20 上传
2021-05-12 上传
2021-04-24 上传
2021-05-13 上传
2021-06-10 上传
2021-06-10 上传
