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

Question

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

我认为缓存局部性是功能语言中多核并行的一大障碍.函数式编程涉及创建许多短期对象; 破坏这些对象可能会破坏CPU缓存的一致性.我已经看到很多建议如何改进命令式语言中的缓存局部性,例如,这里和这里.但是我不清楚如何在函数式编程中完成它们,特别是对于经常出现的递归数据结构(如树等).

是否有任何技术可以改进不纯函数语言(特别是F#)中的缓存局部性？任何建议或代码示例都非常受欢迎.

Answer 1

据我所知,缓存局部性(多线程或其他)的关键是

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

为此 ;

• 尽可能避免使用物体
  • 对象在堆上分配,并且可能会在整个地方喷洒,具体取决于堆碎片等.
  • 您基本上无法控制对象的内存放置,以至于GC可能随时移动它们.
• 使用数组.大多数编译器将数组解释为连续的内存块.
  • 其他集合数据类型可能会在所有地方分发内容 - 例如,链接列表由指针组成.
• 使用基元类型的数组.对象类型在堆上分配,因此对象数组只是指向可遍布堆的对象的指针数组.
• 如果不能使用基元,请使用结构数组.结构的字段按顺序排列在内存中,并由.NET编译器视为基元.
• 计算出你将要执行它的机器上的缓存大小
  • CPU具有不同大小的L2缓存
  • 设计代码以使用不同的缓存大小进行扩展可能是谨慎的做法
  • 或者更简单地说,编写适合您的代码将运行的最低公共缓存大小的代码
• 找出需要靠近每个数据的内容
  • 实际上,您不会将整个工作集放入L2缓存中
  • 检查(或重新设计)您的算法,以便您使用的数据结构保存"下一步"所需的数据,接近以前需要的数据.

在实践中,这意味着您可能最终使用的数据结构在理论上并不是计算机科学的完美例子 - 但没关系,计算机在理论上也不是计算机科学的完美例子.

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