Java:将大量二维数组分割成机器页面大小的倍数的 block

Question

我这样做的原因是，各种不同的线程可以同时执行特定的计算，同时从同一个二维数组接收信息并写入另一个大小相同的信息。

现在，我了解了如何简单地将数组分解为多个部分并将每个部分分配给一个线程。例如，我有 8 个线程和一个 8x8 2D 数组。每个线程负责从一个 2D 数组中收集所需的信息，然后写入另一个 2D 数组中其各自的列。由于没有对第一个 2D 数组进行写入，因此没有理由对那里的线程设置限制，但有必要对线程正在写入的数组设置限制。对我来说这一切都没有问题。

我正在做一项作业，程序的运行时间很重要。我的导师建议我们“让 block 成为一个处理页面大小倍数的线程。”

我们正在使用两个 10 000 x 10 000 2D 数组，机器页面大小为 4Kib 或 4096 字节。我的问题是我不知道如何在我的程序中使用这些信息。现在我只是使用 boolean 数组，但稍后我将使用字符数组来实现它。

我是否只计算有多少列等于 4096 字节的倍数，然后将其分配给我的 8 个线程？如何计算二维数组的大小？

编辑:到目前为止，我的程序运行良好，只是速度非常慢。我应该每秒创建 30-60 代，即对完整的 10 000 x 10 000 阵列进行 30-60 次完整写入。不幸的是我每秒只能写入约 8 次。现在每个线程(共 8 个)都在 12 500 x 10 000 个相同大小的 block 上写入。

Answer 1

最佳布局实际上取决于您的处理所展示的访问模式。一般来说，您应该致力于使内存访问模式尽可能保持线性。

首先要注意的是java将多维数组视为数组的数组的方式；这意味着访问局部性最好通过迭代最内循环中最右边的维度来实现。取出循环不变量也有助于降低复杂性。你会得到这样的结果:

 int[][][] threeD = new int[10][10][10];
 for (int x=0; x<threeD.length; ++x) {
     int[][] twoD = threeD[x];
     for (int y=0; y<twoD.length; ++y) {
          int[] oneD = twoD[y];
          for (int z=0; z<oneD.length; ++z) {
              oneD[z] = // whatever
          }
      }
 }

由此可见，您希望的目标不是在“ block ”中分配工作，而是在连续的切片中分配工作，例如对于 int[y=10000][x=10000] 和 4 个工作单位，您可以将外部维度划分为 4 个工作单位，而不是将两个维度各划分为两个:

  Bad way to slice work:       More cache-friendly:
       111222                   111111
       111222                   222222
       333444                   333333
       333444                   444444

TLB 大小(页面大小)在像这样的方案中大多无关紧要。通过尽可能保持数据访问线性，无论 TLB 条目数和页面大小如何，您都可以自动最大限度地减少 TLB 缺失。这里的目的是最大限度地提高突发内存访问和/或推测数据预取的效率。