F＃中多核并行机制中缓存局部性的最佳实践

 

我正在研究F＃中的多核并行机制。 我不得不承认，不变性确实有助于编写正确的并行实现。 但是，当内核数量增长时，很难实现良好的加速和良好的可扩展性。 例如，我使用快速排序算法的经验是，许多尝试以纯功能方式实现并行快速排序并使用List或Array作为表示失败。 对那些实现进行分析表明，与顺序版本相比，高速缓存未命中的数量显着增加。 但是，如果使用阵列内部的突变实现并行快速排序，则可以获得较好的加速比。 因此，我认为突变可能是优化多核平行度的一种好方法。

我认为缓存局部性是功能语言中多核并行的一大障碍。 函数式编程涉及创建许多短暂的对象; 销毁这些对象可能会破坏CPU高速缓存的一致性。 例如，在这里和这里，我看到了很多关于如何改进命令式语言中的缓存局部性的建议。 但是我不清楚他们在函数式编程中是如何完成的，尤其是对于经常出现的树等递归数据结构。

是否有任何技术来改善不纯功能语言（特别是F＃）中的缓存局部性？ 任何建议或代码示例都是值得欢迎的。

据我所知，缓存局部性（多线程或其他）的关键是

  • 将工作单元保存在适合缓存的连续RAM中

    • 为此 ;

  • 尽可能避免物体
  • 对象分配在堆上，并可能遍布整个地方，取决于堆碎片等。
  • 您基本上无法控制对象的内存放置，以至于GC可能随时移动它们。
  • 使用数组。 大多数编译器将数组解释为连续的内存块。
  • 其他收集数据类型可能会将所有内容分发 - 例如，链接列表由指针组成。
  • 使用基元类型的数组。 对象类型在堆上分配，所以对象数组只是指向可能分布在整个堆中的对象的指针数组。
  • 如果不能使用基元，则使用结构数组。 结构的字段按顺序排列在内存中，并被.NET编译器视为基元。
  • 计算出你要执行的机器上缓存的大小
  • CPU具有不同大小的L2高速缓存
  • 设计代码时可以谨慎使用不同的缓存大小
  • 或者更简单地说，编写适合您的代码运行的最低通用缓存大小的代码
  • 找出需要靠近每个数据的地方
  • 在实践中，你不会将整个工作集合放入L2缓存
  • 检查（或重新设计）您的算法，以便您使用的数据结构具有“接近”需要的数据，这些数据与先前需要的数据相近。

    • 实际上，这意味着你最终可能会使用不是理论上完美的计算机科学范例的数据结构 - 但没关系，计算机在理论上也不是理想的计算机科学范例。

    关于此主题的一篇很好的学术论文是使用复制的缓存高效字符串排序

    在F＃中的函数中允许可变性是一种幸福，但它应该只在优化代码时使用。 纯功能的风格通常会产生更直观的实现，因此是首选。

    以下是快速搜索的结果：Haskell中的并行Quicksort。 让我们继续关注性能的讨论。 选择一个处理器，然后用特定的算法进行处理。

    为了回答你的问题而没有具体的问题，我会说Clojure的实现STM的方法可能是一般情况下的一个教训，关于如何分离多核处理器上的执行路径并改善缓存局部性。 但只有当读取次数超过写入次数时才有效。

    我不是平行主义专家，但无论如何，这是我的建议。

  • 我期望一个局部可变的方法，其中每个核心都分配了一个既能读写又能被读写的内存区域，这将始终是一种纯粹的方法。
  • 尝试制定你的算法，以便它在连续的内存区域上顺序工作。 这意味着如果你正在使用图表，在处理之前可能需要将节点“压扁”到数组中，并用索引替换引用。 无论缓存局部性问题如何，这在.NET中总是一个很好的优化技术，因为它有助于避免垃圾收集。
    • 链接地址: http://www.djcxy.com/p/68787.html

    上一篇: Best Practices for cache locality in Multicore Parallelism in F#

    下一篇: The state of programming and compiling for multicore systems