在磁盘上转置大型numpy矩阵

Question

在磁盘上转置大型numpy矩阵

6

我有一个相当大的矩形（>1G行，1K列）Fortran风格的NumPy矩阵，我想将其转置为C风格。

到目前为止，我的方法相对简单，使用以下Rust代码片段，使用源矩阵和目标矩阵的MMAPed切片，其中original_matrix和target_matrix都是MMAPPed PyArray2，并且使用Rayon处理并行化。

由于target_matrix必须由多个线程修改，因此我将其包装在一个UnsafeCell中。

let shared_target_matrix = std::cell::UnsafeCell::new(target_matrix);

original_matrix.as_ref().par_chunks(number_of_nodes).enumerate().for_each(|(j, feature)|{
    feature.iter().copied().enumerate().for_each(|(i, feature_value)| unsafe {
        *(shared_target_matrix.uget_mut([i, j])) = feature_value;
    });
});

这种方法可以对形状为（~1G，100）的矩阵进行转置，在HDD磁盘上需要大约120GB且需要3小时。然而，对于形状为（~1G，1000）， ~1200GB的矩阵来说，它并不像天真地预期的那样线性扩展到30个小时，而是会爆炸式增长到数周的时间。目前为止，我已经在2天内成功地转置了大约100个特征，并且速度仍在变慢。

有一些方面，例如所使用的文件系统、HDD碎片整理以及MMAPed处理页面加载的方式，我的解决方案目前正在忽略这些问题。

是否已知有更全面的解决方案考虑了这些问题？

关于顺序和并行方法的说明

尽管直觉上，这种操作可能仅受IO限制，因此不受任何并行化的好处，但我们实验上观察到，并行方法比顺序方法快约三倍（在具有12个核心和24个线程的机器上），当转置一个形状为（1G，100）的矩阵时。我们不确定为什么会出现这种情况。

使用两个HDD的说明

我们还尝试使用两个设备，一个提供Fortran风格的矩阵，另一个用于写入目标矩阵。两个HDD通过SATA电缆直接连接到计算机主板。我们期望至少可以将性能提高一倍，但实际表现并没有改变。

- Luca Cappelletti

1

考虑到操作可能受到HDD速度的限制，我怀疑rayon在这里并没有帮助。事实上，它甚至可能通过强制更复杂的HDD访问模式来减慢速度，而单线程程序则可以拥有更规律（因此更快）的访问。 - Jmb

1

嗨@Jmb！虽然这也是我的直觉，但测试顺序和并行方法的实验表明，在具有24个线程的机器上，并行方法大约快三倍。我对为什么会出现这种情况有一些粗略的想法，但我不确定。我已经将这个观察结果添加到问题中，因为它非常合理。当我在实验中观察到相反的情况时，它让我感到困惑。 - Luca Cappelletti

高效的转置算法被阻塞，以使访问的局部性达到最佳状态。当在内存中进行转置时（尽量避免缓存未命中），这一点是正确的，而当在磁盘上进行转置时（尽量避免页面错误），这一点甚至更为关键。您的方法是否针对访问的局部性进行了优化？ - PierU

为什么并行版本更快可能是因为不同的线程倾向于访问存储器中相同的页面上的数据。如果是这样，实际上这将表明该方法的访问模式在一开始就相当糟糕。关于非线性，可能存在一个阈值效应，取决于可用RAM的数量，同样是由于糟糕的访问模式：在某个特定大小之前，操作系统可以保持足够多的页面在RAM中以缓解糟糕的访问模式，而超过该大小后则无法再做到。 - PierU

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- the8472 · Accepted Answer

“直觉上，这种操作应该仅受IO限制，因此不会从任何并行化中受益。但是，实验表明，并行方法确实快了大约三倍。”

“这可能是由于IO队列利用不佳所致。如果您没有预取的完全顺序工作负载，那么您将在设备在工作和空闲之间交替。如果您保持多个操作处于活动状态，则它将一直工作。”

“使用并行化是实现最佳HDD利用率的次优方法，因为它可能会导致不必要的寻道次数。”

“我们还尝试了使用两个设备，一个提供Fortran风格的矩阵，第二个设备用于写入目标矩阵。这两个HDD都通过SATA电缆直接连接到计算机主板上。我们预计性能至少会提高一倍，但它们保持不变。”

“这可能是由于操作系统的写缓存，这意味着它可以非常有效地批量写入，并且您主要受制于读取。再次使用iostat进行检查。”

“我的解决方案目前忽略了一些方面，比如所使用的文件系统、硬盘碎片化以及MMAPed如何处理页面加载。是否有已知的更全面的解决方案，考虑到这些问题？”

是的，如果底层文件系统支持，您可以使用FIEMAP来获取磁盘上数据的物理布局，然后优化读取顺序以遵循物理布局而不是逻辑布局。您可以使用filefrag CLI工具手动检查碎片数据，但也有rust绑定用于该ioctl，因此您也可以以编程方式使用它。

另外，您可以使用madvise(MADV_WILLNEED)来通知内核预取下一些循环迭代的数据。对于硬盘驱动器，最好每次以几兆字节为单位批量处理。当您完成当前批处理的一半时应该开始下一批次。

批量发出它们可最小化系统调用开销，并在当前批次的中间启动下一批次可以确保有足够的时间实际完成IO操作，然后到达当前批次的末尾。

由于您将按物理而非逻辑顺序手动发出预取，因此还可以通过madvise(MADV_RANDOM)禁用默认的预读取启发式算法（可能会妨碍性能）。

如果您有足够的空闲磁盘空间，也可以尝试更简单的方法：在操作文件之前对其进行碎片整理。但即使如此，您仍应使用madvise确保始终有IO请求在运行。