Only Buffer When You Need To: Reducing On-chip GPU Traffic with Reconfigurable Local Atomic Buffers

<p><strong>Only Buffer When You Need To: Reducing On-chip GPU Traffic with Reconfigurable Local Atomic Buffers</strong></p>

<h2 id="introduction">INTRODUCTION</h2>

<ul>
  <li>GPU 的内存一致性协议
    <ul>
      <li>简单、由软件驱动</li>
      <li>导致内存一致性模型很复杂</li>
    </ul>
  </li>
  <li>不频繁的同步操作通常用原子操作实现
    <ul>
      <li>必须在共享排序点 (shared ordering point) 执行</li>
      <li>同一个线程块可以用 L1（shared memory） 同步</li>
      <li>不同线程块要用 L2 同步（代价昂贵）</li>
    </ul>
  </li>
</ul>

<ul>
  <li>GPU 正在变得更加通用（GP, general-purpose）
    <ul>
      <li>需要支持更多访存模式，如
        <ul>
          <li>ML 训练中随机梯度下降（SGD）等使用原子更新共享权重</li>
          <li>图形算法使用原子来执行边缘传播的更新</li>
        </ul>
      </li>
      <li>它们的原子操作都不够高效</li>
      <li>这些原子并不需要对周围的访问进行排序
        <ul>
          <li>因为它们是在“交换地”更新共享变量，可更松弛地执行</li>
          <li>但仍开销巨大！甚至可能被串行执行，成为程序中的瓶颈</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>先前的工作存在局限性
    <ul>
      <li>一部分主要关注 ML 推理
        <ul>
          <li>本文关注 ML 训练</li>
        </ul>
      </li>
      <li>着重于减少访存大小和数量、数据压缩或优化访存（如使用 shared memory）
        <ul>
          <li>然而还剩下很多原子操作，带来明显开销</li>
        </ul>
      </li>
      <li>关注提高（数据的）交换性能
        <ul>
          <li>然而需要修改一致性模型，添加额外的一致性状态或缓存</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>解决方案：软硬件协同</li>
  <li>软件方面：
    <ul>
      <li>利用算法特性，需要原子但执行顺序不重要</li>
      <li>因为所有更新完成之前不会访问其值</li>
    </ul>
  </li>
  <li>硬件方面
    <ul>
      <li>先在每个 SM 的局部原子缓冲区（LAB，Local Atomic Buffer）更新</li>
      <li>然后稍后将合并更新发送到共享 L2</li>
      <li>无需修改协议或者模型</li>
    </ul>
  </li>
</ul>

<h2 id="background">BACKGROUND</h2>

<ul>
  <li>GPU 应用
    <ul>
      <li>大规模数据并行</li>
      <li>粗粒度同步为主</li>
      <li>几乎没有数据重用</li>
    </ul>
  </li>
  <li>GPU 一致性协议：简单的、软件驱动
    <ul>
      <li>Valid-Invalid (VI)-style</li>
      <li>没有所有权请求、降级请求</li>
      <li>没有写者发起的无效、状态位、窥探总线或目录</li>
    </ul>
  </li>
</ul>

<ul>
  <li>由于同步不频繁
    <ul>
      <li>读时使缓存无效
        <ul>
          <li>以便后续读取不会读取过时的值</li>
        </ul>
      </li>
      <li>写入使用直写或写入不分配方法
        <ul>
          <li>指 L1 对 global memory 的写入</li>
          <li>为了提高性能，可能会被缓冲和合并</li>
        </ul>
      </li>
      <li>存储释放发生时（核函数结束或同步操作发生时）
        <ul>
          <li>写操作必须完成</li>
          <li>数据被写入下一级内存
            <ul>
              <li>通常在 SM 间共享</li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>细粒度同步，通常使用原子实现
    <ul>
      <li>提供对来自多个 SM 上的 TB 的数据和原子请求之间的排序
        <ul>
          <li>如，顺序一致 (SC) 原子对数据和原子访问进行排序</li>
        </ul>
      </li>
      <li>GPU 在内存层次结构的第一个共享级别执行所有全局原子
        <ul>
          <li>通常是 L2，单次访问超过 100 周期</li>
        </ul>
      </li>
      <li>有时可使用更宽松的原子
        <ul>
          <li>暗示对其他内存访问没有排序</li>
          <li>可与其他数据和原子访问重排</li>
          <li>仍然开销昂贵</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>GPU 一致性模型利用不同的 scope 来减少同步开销
    <ul>
      <li>基于异构无竞争 (SC-for-HRF) 的顺序一致性</li>
      <li>CPU 上的协议不适合 GPU
        <ul>
          <li>CPU 通常会获得写入数据和原子的所有权
            <ul>
              <li>全局同步开销低</li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>本文关注 GPU 一致性模型最广泛的两种情况
    <ul>
      <li>设备范围的原子
        <ul>
          <li>对 GPU 上的所有线程可见</li>
        </ul>
      </li>
      <li>局部范围的原子
        <ul>
          <li>只保证对同一 TB 中的其他线程可见，开销低得多
            <ul>
              <li>不会在获取时使所有有效的 L1 数据无效</li>
              <li>不会在发布时通过脏数据写入</li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<h2 id="proposed-design">PROPOSED DESIGN</h2>

<ul>
  <li>LAB 的硬件支持
    <ul>
      <li>放置在 GPU 内存层次结构中的 L1，见 Figure 2(a)</li>
      <li>需要增加一个 Cache/LAB Tag，以支持 LAB 大小的可配置性，见 Figure 2(b)</li>
    </ul>
  </li>
</ul>

<ul>
  <li>LAB 的运作
    <ul>
      <li>稳态行为</li>
      <li>驱逐操作</li>
      <li>合并读写</li>
      <li>处理不能合并的读写</li>
      <li>排序点行为</li>
      <li>原子序列化</li>
      <li>确定原子函数</li>
    </ul>
  </li>
</ul>

<ul>
  <li>稳态（Steady-State）行为
    <ul>
      <li>使用了“填充-写入-未命中”分配策略。
        <ul>
          <li>因为进入 LAB 的原子都是以交换方式更新共享的全局变量</li>
        </ul>
      </li>
    </ul>
  </li>
  <li>驱逐操作
    <ul>
      <li>LAB 满时，使用 LRU 替换策略</li>
    </ul>
  </li>
</ul>

<ul>
  <li>合并访存
    <ul>
      <li>与 shared memory 相同，同一个 warp 可以合并</li>
      <li>使用与 L1 相同数量的读写端口</li>
    </ul>
  </li>
  <li>处理不能合并的访存
    <ul>
      <li>与 shared memory 相同，不能合并的读写将被分解成多个读写</li>
    </ul>
  </li>
  <li>排序点行为
    <ul>
      <li>在核函数边界或强制排序点将 LAB 刷新到 L2
        <ul>
          <li>如 CUDA 的线程围栏或屏障、互斥锁和信号量</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>原子序列化
    <ul>
      <li>warp 内原子冲突
        <ul>
          <li>一个 warp 中的多个线程试图同时更新同一内存位置</li>
        </ul>
      </li>
      <li>warp 间和 TB 间原子冲突。
        <ul>
          <li>不同 warp（或不同 TB）的多个线程试图同时更新同一地址</li>
        </ul>
      </li>
      <li>发生这种情况时，必须先发出一个请求。</li>
      <li>LAB 减少了由于原子碰撞造成的序列化开销</li>
    </ul>
  </li>
</ul>

<ul>
  <li>确定原子函数
    <ul>
      <li>CUDA 支持多种类型、不到 16 种的原子
        <ul>
          <li>其中一些相互之间不可交换顺序。</li>
        </ul>
      </li>
      <li>LAB 在每条缓存 line 中使用 4 位来识别原子操作</li>
      <li>LAB 命中但原子函数不匹配时刷新缓冲行</li>
    </ul>
  </li>
</ul>

<ul>
  <li>相对于纯软件方案的优点
    <ul>
      <li>程序员可以使用 shared memory</li>
      <li>或者使用带有私有变量的一级数据缓存
        <ul>
          <li>数据可能很稀疏，需要大量空间</li>
        </ul>
      </li>
      <li>LAB 只保存频繁访问的原子地址及其值
        <ul>
          <li>不需要大量分配</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>一个示例
    <ol>
      <li>（Figure 3(a)）发布了一个 <code class="language-plaintext highlighter-rouge">atomicAdd(x,2)</code> 操作</li>
      <li>使用 tag 索引到 LAB，并检查是否命中（否）</li>
      <li>分配一个 LAB 条目并更新条目的值（2）</li>
      <li>（Figure 3(b)）在源地址发布了另一个 <code class="language-plaintext highlighter-rouge">atomicAdd(x,5)</code> 操作</li>
      <li>使用 tag 索引到 LAB，并检查是否命中（是），随后更新值（7）</li>
      <li>当 LAB 逐出条目（Figure 3(c)）时，会向 L2 发送合并的原子更新（<code class="language-plaintext highlighter-rouge">atomicAdd(x，7)</code>）。</li>
    </ol>
  </li>
</ul>

<ul>
  <li>LAB 的软件支持
    <ul>
      <li>LAB 依赖于确定哪些原子访问可以在本地（L1）缓冲
        <ul>
          <li>例如，交换原子</li>
        </ul>
      </li>
      <li>为了确定哪些访问是交换原子，本文利用最近提出的额外内存顺序的工作
        <ul>
          <li>使用 SC for HRF 一致性模型和额外的交换内存排序</li>
          <li>程序员或编译器可以在代码中指示硬件的可交换原子</li>
          <li>非 <code class="language-plaintext highlighter-rouge">mem_order_comm</code> 的原子操作会绕过 LAB</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1
2
3
</pre></td><td class="rouge-code"><pre><span class="n">loc</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">tid</span><span class="p">];</span>
<span class="c1">// atomicAdd(&hist[loc], 1);</span>
<span class="n">atomicAdd</span><span class="p">(</span><span class="o">&</span><span class="n">hist</span><span class="p">[</span><span class="n">loc</span><span class="p">],</span> <span class="mi">1</span><span class="p">,</span> <span class="n">mem_order_comm</span><span class="p">);</span>
</pre></td></tr></tbody></table></code></pre></div></div>

<ul>
  <li>对现有一致性模型的影响
    <ul>
      <li>调整了次序，可能导致浮点数舍入误差
        <ul>
          <li>可以接受，因为原子序本就不确定</li>
        </ul>
      </li>
      <li>LAB 只会聚合可交换、原子访问的全局地址的更新
        <ul>
          <li>不会影响 GPU 一致性协议</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<h2 id="methodology">METHODOLOGY</h2>

<ul>
  <li>将 LAB 添加到 GPGPU Sim v4 中</li>
  <li>ML training benchmarks: CUDA 8 + cuDNN v7
    <ul>
      <li>GPGPU-Sim 最高支持的 cuDNN 版本</li>
    </ul>
  </li>
  <li>Others: CUDA 11.2</li>
  <li>硬件参数：基于 NVIDIA Titan V</li>
</ul>

<table>
  <thead>
    <tr>
      <th style="text-align: left">GPU</th>
      <th style="text-align: right">Feature Configuration (Size, Access Latency)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td style="text-align: left">SMs</td>
      <td style="text-align: right">80</td>
    </tr>
    <tr>
      <td style="text-align: left"># Registers / SM</td>
      <td style="text-align: right">64 KB</td>
    </tr>
    <tr>
      <td style="text-align: left">LI Instruction Cache / SM</td>
      <td style="text-align: right">128 KB</td>
    </tr>
    <tr>
      <td style="text-align: left">LI Data Cache / SM</td>
      <td style="text-align: right">32 KB (max 128 KB), 28 cycles</td>
    </tr>
  </tbody>
</table>

<table>
  <thead>
    <tr>
      <th style="text-align: left">GPU</th>
      <th style="text-align: right">Feature Configuration (Size, Access Latency)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td style="text-align: left">L2 Cache</td>
      <td style="text-align: right">4.6 MB, 148 cycles</td>
    </tr>
    <tr>
      <td style="text-align: left">MSHR</td>
      <td style="text-align: right">256 (L1) and 192 (L2) Entries</td>
    </tr>
    <tr>
      <td style="text-align: left">Shared Memory Size / SM</td>
      <td style="text-align: right">96 KB (max 128 KB), 19 cycles</td>
    </tr>
    <tr>
      <td style="text-align: left">Memory</td>
      <td style="text-align: right">16 GB HBM2, 248 cycles</td>
    </tr>
  </tbody>
</table>

<ul>
  <li>baseline
    <ul>
      <li>32KB L1</li>
      <li>96KB shared memory</li>
      <li>device-scoped atomics at L2</li>
    </ul>
  </li>
  <li>Cache-8KB
    <ul>
      <li>based on baseline</li>
      <li>8 KB less cache</li>
    </ul>
  </li>
</ul>

<ul>
  <li>Cache+8KB
    <ul>
      <li>based on baseline</li>
      <li>8 KB more cache</li>
    </ul>
  </li>
  <li>Cache*2
    <ul>
      <li>based on baseline</li>
      <li>double cache</li>
    </ul>
  </li>
</ul>

<ul>
  <li>LAB i
    <ul>
      <li>代表每个 SM 中有 $i\in \lbrace 8, 16, 32, 64, 256, \infty \rbrace$ 个 LAB 项</li>
      <li>64 项使用约 8KB SRAM</li>
      <li>对于除 $\infty$ 之外的所有 LAB，都从缓存中获取空间
        <ul>
          <li>应用程序对缓存大小不太敏感</li>
          <li>而更改 shared memory 大小会影响利用率</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>hLRC
    <ul>
      <li>Lazy Release Consistency for GPUs</li>
      <li>获得原子的所有权，使其能够在本地缓存原子</li>
      <li>由于 hLRC 尚未公开发布，本文在 GPGPU-Sim 中对其实现并验证</li>
    </ul>
  </li>
</ul>

<ul>
  <li>PHI
    <ul>
      <li>PHI: Architectural Support for Synchronization- and Bandwidth-Efficient Commutative Scatter Updates</li>
      <li>在写-分配 L1 缓存中缓冲原子操作，写时取</li>
      <li>PHI 原为类 MESI 的 CPU 一致性而设计，本文将其扩展到 GPU 上
        <ul>
          <li>乐观地忽略失效和降级开销，否则 PHI 会更糟</li>
          <li>对 PHI 扩展，读时懒取，带来 6%的差别，但不影响结论</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>一些其他尝试
    <ul>
      <li>增加了每个 SM 的共享内存大小（没有效果，文末讨论）
        <ul>
          <li>每个 SM 的 TBs 受到寄存器文件大小的限制，增加每个 SM 的共享内存并不会增加每个 SM 的 TBs</li>
          <li>cuDNN 闭源，尝试使用 CUTLASS（失败，不含相关功能）</li>
        </ul>
      </li>
      <li>实现了一个 LAB 变体，本地执行原子操作，但是没有 LAB
        <ul>
          <li>便于区分优化原子碰撞造成的序列化开销与访存合并的收益</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>Benchmarks（细节见论文）
    <ul>
      <li>Rodinia</li>
      <li>histogram
        <ul>
          <li>更大的 benchmark 难以应用与直方图类似的软件优化（文末讨论）</li>
        </ul>
      </li>
      <li>graph analytics
        <ul>
          <li>与输入相关，此处关注能跑满 GPU 的输入，不过不同大小的输入都跑了</li>
        </ul>
      </li>
      <li>ML training workloads</li>
    </ul>
  </li>
</ul>

<h2 id="results">RESULTS</h2>

<h2 id="discussion">DISCUSSION</h2>

<ul>
  <li>软件 VS 硬件
    <ul>
      <li>使用共享内存来利用可交换性中在直方图算例获得了显著的优化。然而，在较大的 graph analytics 与 ML training 负载上存在限制。</li>
      <li>因此只有在工作集足够小的情况下，使用软件优化（如共享内存）可以提高性能。
        <ul>
          <li>此外，对于图分析算法，顶点更新在编译时是不可预测的，因此很难使用共享内存来提高性能。</li>
          <li>相比之下，LAB 动态地保留了使用率最高的位置，从而提高了重用性，即使对于具有大工作集的程序也是如此。</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>软件 VS 硬件
    <ul>
      <li>还可以在软件中手动虚拟化和管理共享内存分配。
        <ul>
          <li>这使得需要大量共享内存的程序能够运行。</li>
          <li>然而这需要程序员处理诸如逐出、显著增加开销（尤其是线程分歧）等问题</li>
          <li>而之前的工作表明，这种方法为 CPU 提供的结果好坏参半。</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>对其他 ML 训练算法的适用性
    <ul>
      <li>本文的结果集中在 CNN 训练算法上。</li>
      <li>然而，LAB 也适用于其他 ML 训练算法：任何在训练迭代结束时原子地更新共享权重的 ML 训练算法（这在数据并行训练中很常见）都可以使用类似的方法。</li>
      <li>本文试图检查循环神经网络（RNN）训练，但发现 cuDNN 的当前版本在 RNN 训练中没有使用原子更新体重。</li>
      <li>然而，本文预计其他 ML 训练算法，如强化学习和 GANs，将获得与 CNN 类似的好处。</li>
    </ul>
  </li>
</ul>

<ul>
  <li>简单性
    <ul>
      <li>本文提出的添加相对简单，但 LAB 仍然通过智能地利用算法特性提供了显著的好处。</li>
      <li>此外，LAB 可以无缝地安装在现有的、每 SM 可重构 SRAM 中
        <ul>
          <li>这使得程序员可以在 LAB 有用时才能使用它（与以前的方法不同）。</li>
          <li>先前的方法（第七节）提供了与 LAB 相同的一些好处，但通常需要更具侵入性的一致性协议或一致性模型更改，或遭受缓存争用。</li>
        </ul>
      </li>
      <li>因此，LAB 的简单性是一种优势，它证明了先前方法的额外复杂性是不必要的，同时也提高了现有技术的效率。</li>
    </ul>
  </li>
</ul>

<h2 id="related-work">RELATED WORK</h2>

<ul>
  <li>略，建议阅读原论文</li>
</ul>

<h2 id="conclusion">CONCLUSION</h2>

<ul>
  <li>随着 GPGPU 应用程序越来越多地使用细粒度同步，改进设备范围的原子支持势在必行。
    <ul>
      <li>本文使用软硬件协同设计来解决这个瓶颈并提高可扩展性。</li>
    </ul>
  </li>
  <li>软件层面，本文利用最近对 GPU 一致性模型的扩展来识别原子更新，从而松弛原子排序。
    <ul>
      <li>例如，在一些算法中，原子更新是可交换的、宽松的。</li>
    </ul>
  </li>
</ul>

<ul>
  <li>在硬件层面，本文提出了一种缓冲机制（LAB），该机制扩展了每个 SM 的 L1 Cache。
    <ul>
      <li>通过在本地缓冲这些原子的局部更新，降低了原子序列化成本与开销。</li>
      <li>LAB 的大小是可配置的，无原子操作的程序不受影响</li>
    </ul>
  </li>
  <li>LAB 减轻了全局原子更新的影响
    <ul>
      <li>平均性能改进 28%，能耗节省 19%，网络流量提高 19%，性能优于 hLRC 和 PHI。</li>
    </ul>
  </li>
</ul>