algorithm - 关于任务并行化的问题

Question

我有一个关于并行化的问题:

我有两个数据集。 Dataset1 有 m 行和 k 列，Dataset2 有 n 行和 k 列。(m > n) 我的程序从文件中读取这些数据集并将它们存储在内存中。任务是获取 Dataset1 的每个实例(让我们称之为查询实例)并与 Dataset2 的所有实例进行比较。

现在我的问题是:

• (选项 1)我是否应该将数据集 2 分成 x 个分区，并将这些分区分配给数据集 1 的每个查询中的 x 个工作线程(这意味着，与数据集 2 中的查询实例进行比较) 或
• (选项 2)我是否应该从数据集 1 中获取 x 个实例，分配 x 个工作线程同时查询数据集 2。

哪个效率更高？//顺便说一句，我现在正在使用 PThreads 库。

Answer 1

我会选择选项 1，即分区数据集 2。

理由:

数据集 1 可能太大而无法放入缓存，这就是为什么您要扫过它一次并将每个条目与数据集 2 中的所有条目进行比较。

现在，我们假设数据集 2 也太大而无法完全放入单个处理器的缓存中，但如果它被划分为 x 个分区并且每个处理器的缓存包含其中一个分区，则它足够大以适合缓存。在这种情况下，如果您选择选项 1，每个处理器的高速缓存将大到足以包含其中一个分区。如果您选择选项 2，则每个处理器都需要处理整个数据集 2，该数据集太大而无法放入其缓存中，因此会发生抖动。

如果数据集 2 小到足以完全放入缓存，那么您选择哪个选项可能在很大程度上无关紧要。