超算队内培：为啥老拿第三

<p><strong>为啥老拿第三</strong></p>

<h2 id="ipcc21-preliminary-time-line">IPCC’21-Preliminary Time Line</h2>

<ul>
  <li>赛题公布，06-15</li>
  <li>给赛题各部分插入计时代码，吴坎，06-18</li>
  <li>第一次分锅，07-31</li>
</ul>

<ul>
  <li>使用 mkl cbrt 优化 RGB 转换：37ms->21ms，三金，08-01</li>
  <li>EnforceLabelConnectivity：117ms->30ms，吴坎，08-02
    <ul>
      <li>无锁并查集</li>
    </ul>
  </li>
  <li>核心的十轮 iter 优化：5500ms->253ms，吴坎，08-05
    <ul>
      <li>交换 n 循环与 y 循环</li>
    </ul>
  </li>
  <li>RGB 转换查表优化，21ms->7ms，三金，08-05</li>
</ul>

<ul>
  <li>调整 OMP 绑核环境变量，轩轩，08-05
    <ul>
      <li>十轮 iter：253ms->188ms</li>
      <li>并查集：30ms->25ms</li>
    </ul>
  </li>
  <li>进一步调整代码局部性，去掉锁，轩轩，08-07
    <ul>
      <li>十轮 iter：188ms->120ms</li>
    </ul>
  </li>
</ul>

<ul>
  <li>进一步调整代码局部性，轩轩，08-10
    <ul>
      <li>十轮 iter：120ms->90ms</li>
      <li>总时间（Case1）：130ms</li>
    </ul>
  </li>
  <li>优化 detect edge，轩轩，08-11
    <ul>
      <li>10ms->1ms</li>
      <li>总时间：126ms</li>
    </ul>
  </li>
</ul>

<ul>
  <li>case2，case3 数据发布，08-26</li>
  <li>做 PPT，吴坎，08-29
    <ul>
      <li>发现 case3 结果不对，紧急喊群友 debug</li>
    </ul>
  </li>
  <li>用 mkl 数学库代替自己的查表 RGB 转换，三金，08-29
    <ul>
      <li>6ms->7ms</li>
    </ul>
  </li>
</ul>

<ul>
  <li>最终结果：rk3</li>
  <li>和 rk1 比较：
    <ul>
      <li>RGB 转换部分更快（7ms vs 14ms）</li>
      <li>十轮 iter 与并查集部分慢
        <ul>
          <li>使用原子操作等导致效率下降</li>
          <li>先各个线程内部规约，保留各自结果再合并</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>总结：问题不大，进决赛就行</li>
</ul>

<h2 id="cpc21-final-time-line">CPC’21-Final Time Line</h2>

<ul>
  <li>赛题公布，08-25</li>
  <li>代码公布，获得账号，08-27</li>
  <li>开始分锅，08-28
    <ul>
      <li>推导 transformer 前向/后向算法，吴坎</li>
      <li>新神威（海洋之光？）microbench，轩轩</li>
      <li>研究 swGEMM，天翔</li>
    </ul>
  </li>
</ul>

<ul>
  <li>开躺（封培），轩轩，09-04</li>
  <li>移植到本地环境（x86），以便调试算法，吴坎，09-04</li>
  <li>搓完 swTransformer_forward，吴坎，09-05
    <ul>
      <li>开始研究 backward，做 cs231 实验</li>
    </ul>
  </li>
  <li>搓完 Add2bias，吴坎，09-06
    <ul>
      <li>200+batch 后开始出现偏差（后发现为浮点累加顺序不一致）</li>
    </ul>
  </li>
  <li>搓 LayerNorm_forward 和 LayerNorm_backward，吴坎，09-07
    <ul>
      <li>8+batch 后开始出现偏差（后发现 pytorch 对精度有提升手段）</li>
    </ul>
  </li>
</ul>

<ul>
  <li>Case A Checker 公布，09-08</li>
  <li>搓完 swTransformer_backward，吴坎，09-08</li>
  <li>移植回神威（用 CPP 代替所有 Python），吴坎，09-09</li>
  <li>第二次视频会议，09-09
    <ul>
      <li>先做答辩 PPT（决赛思路已经确定），吴坎</li>
      <li>swGEMM，天翔</li>
      <li>矩阵乘以外的其他访存密集算子，轩轩</li>
    </ul>
  </li>
</ul>

<ul>
  <li>做完 PPT，09-11</li>
  <li>公布 Case B，09-13
    <ul>
      <li>开始看 PYTorch 多节点训练，吴坎，09-14</li>
    </ul>
  </li>
  <li>搓完从核 LinearAddLayerNorm，LinearRelu 不含矩阵乘法部分，吴坎，09-15</li>
  <li>第三次分锅，09-16
    <ul>
      <li>GEMMrcr，吕天翔</li>
      <li>GEMMrrr，GEMMcrr，轩轩</li>
      <li>剩余所有，吴坎</li>
    </ul>
  </li>
</ul>

<ul>
  <li>swdSoftmax、swdAdd2Bias 等除了 matmul 与 bmm 以外的所有部分上从核，吴坎，09-16（通宵）
    <ul>
      <li>只剩矩阵乘（mm，bmm）了</li>
    </ul>
  </li>
  <li>搓完从核 GEMMrcr，天翔，09-16
    <ul>
      <li>性能负优化，比 baseline 还弱</li>
    </ul>
  </li>
</ul>

<ul>
  <li>搓完 bmm，吕天翔，09-17</li>
  <li>第四次重新分锅
    <ul>
      <li>GEMMrcr，轩轩</li>
      <li>GEMMrrr，GEMMcrr，天翔</li>
      <li>其他，吴坎</li>
    </ul>
  </li>
</ul>

<ul>
  <li>再卷一波其他函数，吴坎，09-19</li>
  <li>搓完 GEMMrcr，轩轩，09-19</li>
  <li>搓完 GEMMrrr，天翔，09-19</li>
  <li>搓完 GEMMcrr，天翔，09-20</li>
  <li>搓完向量化 expf，轩轩，09-21
    <ul>
      <li>开躺</li>
    </ul>
  </li>
</ul>

<ul>
  <li>开始看 CaseB，吴坎，09-22（通宵）
    <ul>
      <li>Adam 从核化（成功）</li>
      <li>ViT 从核化
        <ul>
          <li>不收敛！</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>去无锡前的状态：
    <ul>
      <li>CaseA 勉强能看，性能严重受限于 Linear 中的矩阵乘</li>
      <li>CaseB 几乎不收敛，且其他算例未公布</li>
      <li>心态爆炸！</li>
    </ul>
  </li>
  <li>答辩前夜：
    <ul>
      <li>通宵卷 GEMM，天翔</li>
      <li>通宵卷 ViT，吴坎</li>
    </ul>
  </li>
  <li>答辩：提前在 PPT 中放了卫星 TAT
    <ul>
      <li>答辩反馈：CaseA 跑的非常快</li>
      <li>caseB 只交了 baseline（因为不收敛）</li>
    </ul>
  </li>
</ul>

<ul>
  <li>交卷前最后一搏（通宵）：
    <ul>
      <li>试图将 PYTorch 中部分代码上从核（约 2k 行），减少 loss.backward()的 5s 固定开销
        <ul>
          <li>失败，只能训一个 batch，随后段错误！</li>
        </ul>
      </li>
      <li>回滚 ViT 代码，只替换其中的矩阵乘部分</li>
      <li>case BX 根本没跑过（最大失误）
        <ul>
          <li>为求稳下调了其中的 batchsize 到 768</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>最终结果：rk3</li>
  <li>compare with rk2：
    <ul>
      <li>case A 更优（19sample/s vs 16sample/s）</li>
      <li>case B1、B2 略慢</li>
      <li>case BX（差很多）</li>
    </ul>
  </li>
</ul>

<ul>
  <li>总结：不要躺
    <ul>
      <li>因为一直在救火，case B 几乎没做，被严重拉分</li>
    </ul>
  </li>
</ul>

<h2 id="ipcc21-final-time-line">IPCC’21-Final Time Line</h2>

<ul>
  <li>赛题发布，10-25</li>
  <li>跑通 baseline，完成一键运行脚本，吴坎，10-25</li>
  <li>收集热点，轩轩，10-26</li>
  <li>删去冗余代码（如不用的<code class="language-plaintext highlighter-rouge">clean()</code>），吴坎，10-27
    <ul>
      <li>5.7s->4.7s</li>
    </ul>
  </li>
</ul>

<ul>
  <li>调整循环顺序，三金，10-28
    <ul>
      <li>4.7s->4.2s</li>
    </ul>
  </li>
  <li>继续删冗余代码（如简化不用的<code class="language-plaintext highlighter-rouge">memset</code>），吴坎，10-29
    <ul>
      <li>4.2s->3.7s</li>
    </ul>
  </li>
  <li>调整分块，JB，10-30
    <ul>
      <li>3.7s->3.3s</li>
    </ul>
  </li>
</ul>

<ul>
  <li>第一次视频会议+分锅，10-30
    <ul>
      <li>优化 IO，吴坎</li>
      <li>奇偶预处理，JB</li>
      <li>向量化等其他硬件相关优化，轩轩&三金</li>
    </ul>
  </li>
</ul>

<ul>
  <li>mmap 优化 IO，吴坎，11-01</li>
  <li>第二组数据发布，11-02</li>
  <li>奇偶预处理实现但是不收敛，暂时放弃，JB，11-05</li>
  <li>实现混合精度（float 存储，double 计算），负优化，吴坎，11-05
    <ul>
      <li>2.1s->4.5s</li>
    </ul>
  </li>
  <li>混合精度，先用单精度计算至 1e-3，再用双精度，吴坎，11-06
    <ul>
      <li>2.1s->1.7s</li>
    </ul>
  </li>
</ul>

<ul>
  <li>mmap 需要热启动，担心赛会不允许，引入 vmtouch 建立文件缓存，吴坎，11-07</li>
  <li>奇偶预处理卡在最后一步，暴力绕过导致计算量翻倍，JB，11-08
    <ul>
      <li>迭代轮数 120 轮下降至 50 轮</li>
      <li>时间：1.7s->1.1s</li>
    </ul>
  </li>
  <li>武大群里 po 出截图，发现同样 50 轮即收敛，11-08
    <ul>
      <li>猜测完全实现了奇偶预处理</li>
    </ul>
  </li>
</ul>

<ul>
  <li>重新实现奇偶预处理，发现收敛，JB，11-09
    <ul>
      <li>1.1s->0.55s</li>
    </ul>
  </li>
  <li>尝试挣扎拆实部虚部向量化，三金，轩轩，11-09
    <ul>
      <li>失败</li>
    </ul>
  </li>
  <li>做 PPT，吴坎+三金+JB，11-09</li>
  <li>11-10 上午，交卷+答辩顺序抽签</li>
</ul>

<ul>
  <li>最终结果：rk3</li>
  <li>compare with rk1：慢 20%
    <ul>
      <li>暂不知 rk1 思路</li>
    </ul>
  </li>
  <li>总结
    <ul>
      <li>决赛题对数学要求较高，JB FMVP</li>
      <li>代码本身并行度高，优化空间有限</li>
      <li>向量化捞了</li>
      <li>如果不是在前一天写出奇偶预处理就寄了！</li>
    </ul>
  </li>
</ul>

<h2 id="pac21-preliminary-time-line">PAC’21-Preliminary Time Line</h2>

<h2 id="pac21-final-time-line">PAC’21-Final Time Line</h2>

<ul>
  <li>所有参赛同学（轩轩、天翔、景润、天皓）躺到决赛前一天晚上</li>
  <li>轩轩、天翔卷一个晚上</li>
  <li>最终结果：rk9，历年最差，不评价</li>
</ul>

<h2 id="杂谈参加比赛的一些-tips">杂谈：参加比赛的一些 tips</h2>

<ul>
  <li>参赛之前——组队：
    <ul>
      <li>优化「前端」-算法手（我）
        <ul>
          <li>数据结构、局部算法优化</li>
        </ul>
      </li>
      <li>优化「前端」-数学手（JB）
        <ul>
          <li>数值计算优化</li>
        </ul>
      </li>
      <li>优化「后端」（三金、轩轩）
        <ul>
          <li>熟悉机器特性</li>
          <li>大力写向量化</li>
        </ul>
      </li>
      <li>队长（我）：
        <ul>
          <li>了解每个人的状态和进度</li>
          <li>适度 push</li>
          <li>定期开会<del>甩</del>分锅</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>开始比赛
    <ul>
      <li>建立代码仓库</li>
      <li>编写代码一键编译与一键运行脚本
        <ul>
          <li>非常重要，后续节省大量时间</li>
        </ul>
      </li>
      <li>视比赛集群资源决定是否要移植到本地进行调试</li>
      <li>观察代码，找到代码热点，决定后续工作方向
        <ul>
          <li>手动插入计时代码（直观，但 log 可能很长）</li>
          <li>借助 vtune、nvprof 等工具</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>比赛中
    <ul>
      <li>尝试理解代码逻辑——局部的、全局的
        <ul>
          <li>不强求全局理解</li>
        </ul>
      </li>
      <li>是否可以更换算法？
        <ul>
          <li>高效数据结构 or 查表？</li>
        </ul>
      </li>
      <li>计算理论算力和内存带宽
        <ul>
          <li>程序的不同部分，是计算密集还是访存密集？</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>比赛中
    <ul>
      <li>是否可以混合精度？
        <ul>
          <li>访存密集：低精度存储，高精度计算</li>
          <li>计算密集：高精度存储，低精度计算</li>
          <li>迭代类：先低后高？</li>
        </ul>
      </li>
      <li>增加代码局部性
        <ul>
          <li>循环融合</li>
          <li>循环次序调整</li>
          <li>算子融合</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>比赛中
    <ul>
      <li>掌握硬件特性
        <ul>
          <li>是否绑核？物理核到线程的分配是怎样的？</li>
          <li>编译选项是否贴合硬件架构？</li>
        </ul>
      </li>
      <li>从编译器中获得灵感
        <ul>
          <li>不同的编译器对代码各部分的影响是什么？</li>
          <li>为什么？可以在其他编译器上手动复现吗？</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

<ul>
  <li>比赛中
    <ul>
      <li>定期同步进度！定期分锅！</li>
      <li>态度<strong>端正</strong>即可有不错的名次</li>
      <li><strong>不要躺！</strong>不要想着靠队友 Carry！</li>
      <li><strong>躺的比赛不要挂我名字</strong></li>
    </ul>
  </li>
</ul>

<ul>
  <li>比赛后：
    <ul>
      <li>在 wiki 写参赛总结，或在内培分享参赛经历</li>
    </ul>
  </li>
</ul>