用于基于获取并添加的队列的可爱技巧

主要观点:在基于 fetch-and-add(FAA)的典型并发队列中,两个并发的入队操作会在两个缓存行上竞争,先竞争队列头,然后在入队位置也可能产生伪竞争,通过填充可避免假共享但浪费空间,理想情况是按特定顺序(按列而非行遍历缓存行)入队,这是一种易实现的存储虚拟化,可插入现有队列;此技术对缓存行对齐不敏感,在某些有相邻行预取器的 CPU 上可视为三维结构,通过选择合适遍历顺序可调整对同一行和行对的访问间隔,还可设计与缓存行大小无关的遍历顺序(反转索引位序),此技术虽不能解决 FAA 队列的根本扩展问题,但复杂度低。
关键信息:

  • 两个并发入队操作在缓存行竞争。
  • 避免假共享需填充但浪费空间。
  • 理想入队顺序按列遍历缓存行。
  • 对缓存行对齐不敏感。
  • 可视为三维结构并调整访问间隔。
  • 可设计缓存无关遍历顺序。
    重要细节:
  • 假设 64 字节缓存行、8 字节队列元素。
  • 正常 FAA 队列遍历顺序及改进后的顺序。
  • 不同 CPU 情况及对访问间隔的影响。
阅读 9
0 条评论