1

至少从标题搜索来看，似乎没有任何预先存在的问题。我正在寻找外部合并的最佳通行证数量。因此，如果我们有 1000 个数据块，那么一次将是 1000 路合并。两遍可能是 5 组 200 个块，然后是 1 组 5 个块的最终合并。等等。我做了一些数学运算，这肯定有缺陷，因为看起来两次传球永远不会胜过一次传球。不过，这很可能是对如何读取数据的误解。

首先，一个数值示例：

数据：100 GB
内存：1 GB

由于我们有 1GB 内存，我们可以一次加载 1GB 以使用快速排序或合并排序进行排序。现在我们有 100 个要排序的块。我们可以进行 100 路合并。这是通过制作RAM/(chunks+1)大小桶 = 1024MB/101=来完成的10.14MB。10.14MB100个块中的每一个都有 100 个桶，并且一个输出桶的大小也为10.14MB. 当我们合并时，如果任何输入存储桶为空，我们会执行磁盘搜索以重新填充该存储桶。同样，当输出桶装满时，我们写入磁盘并将其清空。我声称“磁盘需要读取的次数”是(data/ram)*(chunks+1). 我从我们已经确定了输入桶大小的事实中得到了这一点，ram/(chunks+1)我们必须为给定的 pass 读取整个数据，所以我们读取(data/bucket_size)次。换句话说，每次输入桶清空时，我们都必须重新填充它。我们在这里做了 100 多个块，所以numChunks*(chunk_size/bucket_size)=datasize/bucket_size或100*(1024MB/10.14MB). BucketSize = ram/(chunks+1)so 100*(1024/10.14)= (data/ram) * (chunks+1)= 1024*100MB/1024MB * 101= 10100 次读取。

对于两遍系统，我们执行 A 组 B #chunks，然后最终合并 1 组 A #chunks。使用前面的逻辑，我们有 numReads = A*( (data/ram)*(B+1)) + 1*( (data/ram)*(A+1))。我们也有A*B= Data/Ram。例如，10 个组，每组 10 个块，其中每个块是一个 GB。这里，A = 10 B = 10。10*10 = 100/1 = 100，即Data/Ram。这是因为Data/Ram是原始的块数。对于 2 次通过，我们想要Data/Ram分成 A 组 B #chunks。

我将尝试在这里分解公式，让 D = 数据，A = #groups，B = #chunks/group，R = RAM

A*(D/R)*(B+1) + 1*(D/R)*(A+1)- 这是 A 乘以 B #chunks 上的外部合并的读取次数加上 A #chunks 上的最终合并。

A = D/(R*B) => D^2/(B*R^2) * (B+1) + D/R * (D/(R*B)+1)

(D^2/R^2)*[1 + 2/B] + D/R是 2 次通过外部合并的读取次数。对于 1 遍，我们有(data/ram)*(chunks+1)where chunks = data/ram for 1 pass。因此，对于一次通行证，我们有D^2/R^2 + D/R. 我们看到，只有当块大小 B 变为无穷大时，第 2 遍才达到这一点，即使如此，额外的最终合并也给了我们D^2/R^2 + D/R. 所以一定有一些关于我错过的阅读，或者我的数学有缺陷。感谢任何花时间帮助我的人！

4

2 回答 2

3

您忽略了这样一个事实，即从磁盘读取数据块所需的总时间是

  • 旋转硬盘驱动器的访问时间大致恒定，大约为几毫秒。
  • 传输时间取决于数据块的大小和传输速率。

随着块数量的增加，输入缓冲区（您称它们为桶）的大小会减小。输入缓冲区越小，恒定访问时间对填充缓冲区的总时间的影响就越明显。在某个时刻，填充缓冲区的时间几乎完全由访问时间决定。因此，合并过程的总时间开始随着缓冲区的数量而不是读取的数据量而增加。

这就是额外的合并通道可以加速该过程的地方。它允许使用更少和更大的输入缓冲区并减轻访问时间的影响。

编辑：这是一个快速的粗略计算，可以让您了解盈亏平衡点在哪里。

总传输时间可以很容易地计算出来。每次通过时，所有数据都必须读取和写入一次：

total_transfer_time = num_passes * 2 * data / transfer_rate

缓冲区读取的总访问时间为：

total_access_time = num_passes * num_buffer_reads * access_time

由于只有一个输出缓冲区，因此可以使其大于输入缓冲区而不会浪费太多内存，因此我将忽略写入的访问时间。缓冲区读取次数为data / buffer_size，缓冲区大小约为ram / num_chunks一次性方法，块数为data / ram。所以我们有：

total_access_time1 = num_chunks^2 * access_time

sqrt(num_chunks)对于两次通过的解决方案，使用缓冲区来最小化访问时间是有意义的。所以缓冲区大小是ram / sqrt(num_chunks)，我们有：

total_access_time2 = 2 * (data / (ram / sqrt(num_chunks))) * acccess_time
                   = 2 * num_chunks^1.5 * access_time

因此，如果我们使用transfer_rate = 100 MB/s, access_time = 10 ms, data = 100 GB, ram = 1 GB，则总时间为：

total_time1 = (2 * 100 GB / 100 MB/s) + 100^2 * 10 ms
            = 2000 s + 100 s = 2100 s
total_time2 = (2 * 2 * 100 GB / 100 MB/s) + 2 * 100^1.5 * 10 ms
            = 4000 s + 20 s = 4020 s

访问时间的影响仍然很小。因此，让我们将数据更改为 1000 GB：

total_time1 = (2 * 1000 GB / 100 MB/s) + 1000^2 * 10 ms
            = 20000 s + 10000 s = 30000 s
total_time2 = (2 * 2 * 1000 GB / 100 MB/s) + 2 * 1000^1.5 * 10 ms
            = 40000 s + 632 s = 40632 s

现在，一次性版本中的一半时间都花在了磁盘寻道上。让我们尝试 5000 GB：

total_time1 = (2 * 5000 GB / 100 MB/s) + 5000^2 * 10 ms
            = 100000 s + 250000 s = 350000 s
total_time2 = (2 * 2 * 5000 GB / 100 MB/s) + 2 * 5000^1.5 * 10 ms
            = 200000 s + 7071 s = 207071 s

现在两遍版本更快。

于 2013-03-23T13:10:20.310 回答
2

要获得最佳效果，您需要更复杂的磁盘模型。让填充块大小的S时间是寻道时间和读取速率。rS + kkr

如果将大小的 RAM 划分为大小的M缓冲区C+1，M/(C+1)则加载 RAM 一次的时间为(C+1) (r M/(C+1) + k)= rM + k(C+1)。因此，正如您所期望的，C通过消除寻道来缩短读取时间。在一个顺序块中读取所有内存是最快的，但合并不允许这样做。我们必须做出权衡。这就是我们需要寻找最佳的地方。

随着总数据大小乘以cRAM 大小，有c要合并的块。

在一次通过方案中C=c， 和总读取时间必须正好是填满 RAM 的c时间：c (rM + k(c+1)) = c(rM + kc + k).

在第一遍N数据的双向分割的双遍方案中，该遍具有C=c/N并且在第二遍中，C=N. 所以总成本是

c ( rM + k(c/N+1) ) + c ( rM + k(N+1) ) = c ( 2rM + k(c/N + N) + 2k )

请注意，此模型省略了写入时间。您最终应该填写它，除非您假设它在不同的设备上重叠 I/O，因此可以忽略。

在这里不难看出，如果c和k适当大，那么 2-pass 模型中的c/N+N项与 1-pass 中的项相比可以非常小c，2-pass 模型会更快。

我现在要停下来，但是您可以继续使用此逻辑来（可能）为任意次数的通过获得一个封闭的近似公式。这将需要求解一个无限级数。然后您可以将导数设置为零并求解最佳通过数的估计值。如果生活是美好的，您还可以N通过将 2d 函数的梯度设置为通道数和N为零来学习最佳值。我的直觉说N ~ sqrt(c)。

如果数学变得难以处理，您仍然可以在开始时使用上述简单代数模拟合理范围的传球次数，并以这种方式选择最优值。

这是一个有趣的问题，很抱歉我现在没有更多的时间来解决这个问题。我希望分析框架足以让你打出一个不错的结果。

于 2013-03-24T01:23:16.593 回答