c - 单线程模式下并行合并非常慢

Question

我有两组已排序的元素，并希望以某种方式将它们合并在一起，以便稍后可以并行化它。我有一个简单的合并实现，它具有数据依赖性，因为它使用最大值函数和可并行合并的第一个版本，该版本使用二分搜索来查找排名并计算给定值的索引。

getRank 函数返回低于或等于给定needle 的元素数量。

#define ATYPE int

int getRank(ATYPE needle, ATYPE *haystack, int size) {
    int low = 0, mid;
    int high = size - 1;
    int cmp;
    ATYPE midVal;

    while (low <= high) {
        mid = ((unsigned int) (low + high)) >> 1;
        midVal = haystack[mid];
        cmp = midVal - needle;

        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid; // key found
        }
    }

    return low; // key not found
}

合并算法对两个排序集 a、b 进行操作，并将结果存储到 c 中。

void simpleMerge(ATYPE *a, int n, ATYPE *b, int m, ATYPE *c) {
    int i, l = 0, r = 0;

    for (i = 0; i < n + m; i++) {
        if (l < n && (r == m || max(a[l], b[r]) == b[r])) {
            c[i] = a[l];
            l++;
        } else {
            c[i] = b[r];
            r++;
        }
    }
}

void merge(ATYPE *a, int n, ATYPE *b, int m, ATYPE *c) {
    int i;
    for (i = 0; i < n; i++) {
        c[i + getRank(a[i], b, m)] = a[i];
    }
    for (i = 0; i < m; i++) {
        c[i + getRank(b[i], a, n)] = b[i];
    }
}

当有很多元素时，合并操作非常慢，并且仍然可以并行化，但是 simpleMerge 总是更快，即使它不能并行化。

所以我现在的问题是，你知道并行合并有什么更好的方法吗？如果是的话，你能给我指出一个方向还是我的代码太糟糕了？

Answer 1

simpleMerge 函数的复杂性:

O(n + m)

merge 函数的复杂性:

O(n*logm + m*logn)

在没有考虑太多的情况下，我对并行化的建议是找到每个函数中间的单个值，使用类似于 getRank 函数的东西，并从那里使用简单的合并。这可以是O(n + m + log m + log n) = O(n + m)(即使你做了一些但恒定数量的查找来找到中间的值) .