c - 合并排序大文件与内存限制并行(Linux)

Question

我需要使用 t 线程对大小为 M 的大型二进制文件进行排序。文件中的记录都是相同大小的。该任务明确指出我可以分配的内存量是 m，并且比 M 小得多。还保证硬盘驱动器至少有 2 * M 可用空间。这需要 merge sort ofc，但事实证明它并不那么明显。我在这里看到三种不同的方法:

一个。将文件 input、temp1 和 temp2 映射到内存中。执行合并排序 input -> temp1 -> temp2 -> temp1 ... 直到其中一个 temps 排序。线程只竞争选择下一部分工作，不竞争读/写。

B。每次打开 3 个文件 t 次，每个线程获得 3 个 FILE 指针，每个文件一个。同样，他们只争夺下一部分工作，读取和写入应该并行工作。

C。每次打开 3 个文件，将它们保持在互斥锁下，所有线程并行工作，但为了抓取更多工作或读取或写入它们锁定各自的互斥锁。

注意事项:

在现实生活中我肯定会选择A。但这不是破坏了缓冲有限的全部目的吗？ (换句话说，这不是作弊吗？)。通过这种方法，我什至可以在没有额外缓冲区的情况下对整个文件进行基数排序。此外，此解决方案是特定于 Linux 的，我认为 Linux 是从对话中隐含的，但在任务描述中并未明确说明。

关于 B，我认为它可以在 Linux 上运行但不可移植，请参阅上面的 Linux 注释。

关于 C，它是可移植的，但我不确定如何优化它(例如，m 足够小的 8 个线程只会在队列中等待轮到它们，然后读取/写入一小部分数据，然后立即对其进行排序并再次相互碰撞。IMO 的工作速度不太可能超过 1 个线程)。

问题:

1. 哪种解决方案更适合这项任务？
2. 哪种解决方案是现实生活中更好的设计(假设是 Linux)？
3. B 有效吗？换句话说，多次打开文件并并行写入(写入文件的不同部分)合法吗？
4. 任何替代方法？

Answer 1

你的问题有很多方面，所以我会试着把它分解一下，同时试着回答你几乎所有的问题:

• 给你一个存储设备上的大文件，它可能在 block 上运行，即你可以同时加载和存储许多条目。如果您从存储中访问单个条目，则必须处理相当大的访问延迟，您只能通过同时加载多个元素来尝试隐藏，从而分摊所有元素加载时间的延迟。

• 与存储相比，您的主内存非常快(尤其是对于随机访问)，因此您希望在主内存中保留尽可能多的数据，并且只在存储上读取和写入顺序 block 。这也是为什么 A 不是真正作弊的原因，因为如果您尝试使用您的存储进行随机访问，您将比使用主内存慢很多。

结合这些结果，您可以得出以下方法，该方法基本上是A，但包含一些通常在外部算法中使用的工程细节。

• 仅使用一个专用线程来读取和写入存储。这样一来，每个文件只需要一个文件描述符，理论上甚至可以在很短的时间范围内收集和重新排序来自所有线程的读写请求，以获得接近顺序的访问模式。此外，您的线程只需将写入请求排队并继续下一个 block ，而无需等待 IO 完成。

• 将 t block (来自 input )加载到最大大小的主内存中，这样您就可以在这些 block 中的每一个上并行运行 mergesort 。 block 排序后，将它们作为 temp1 写入存储中.
  重复此操作，直到文件中的所有 block 都已排序。

• 现在对已排序的 block 执行所谓的多路合并:每个线程从 temp1 加载一定数量 k 的连续 block 存入内存并使用优先级队列或锦标赛树合并它们以找到下一个要插入到结果 block 中的最小值。一旦你的 block 满了，你就把它写到你的存储中 temp2为下一个 block 释放内存。在这一步之后，概念上交换temp1和 temp2

• 您仍然需要执行几个合并步骤，但与您可能在 A log k 倍强>.在最初的几个合并步骤之后，您的 block 可能太大而无法放入主内存，因此您将它们分成更小的 block ，并且从第一个小块开始，仅当所有先前的元素都已经存在时才获取下一个 block 合并。在这里，您甚至可以进行一些预取，因为 block 访问的顺序是由 block 最小值预先确定的，但这可能超出了这个问题的范围。请注意，k 的值通常仅受可用内存的限制。

• 最后，您到达了需要合并在一起的 t 个大块。我真的不知道是否有一个很好的并行方法来解决这个问题，可能需要按顺序合并它们，所以您可以再次使用上面的 t-way 合并来生成单个排序文件。