2

这更像是一个算法问题，而不是编程问题。我想知道是否可以修改前缀和（或任何）并行算法以完成以下操作。我想在不到 O(N) 的时间内从 GPU 上的两个输入列表生成结果。

规则是：从数据中取出第一个数字，直到键中的相同索引包含较小的值。

每当我尝试将其映射到并行扫描时，它都不起作用，因为我无法确定要在上行扫描中传播哪些数据值，因为无法知道哪些先前的数据可能已经传播到足以与当前键进行比较. 这个问题让我想起了我们需要考虑当前指数和所有过去指数的涟漪进位。

同样，不需要代码进行并行扫描（尽管那会很好），更希望了解如何完成或为什么不能完成。

int data[N] = {5, 6, 5, 5, 3, 1, 5, 5};
int keys[N] = {5, 6, 5, 5, 4, 2, 5, 5};
int result[N];

serial_scan(N, keys, data, result);
// Print result.  should be {5, 5, 5, 5, 3, 1, 1, 1, }

串行扫描的代码如下：

void serial_scan(int N, int *k, int *d, int *r)
{
  r[0] = d[0];
  for(int i=1; i<N; i++) 
    {
      if (k[i] >= r[i-1]) {
        r[i] = r[i-1];
      } else if (k[i] >= d[i]) {
        r[i] = d[i];
      } else {
        r[i] = 0;
      }
    }
}
4

1 回答 1

0

可以在此处找到并行扫描的一般技术，在功能语言标准 ML 中进行了描述。这可以为任何关联运算符完成，我认为您的符合要求。

一个直觉泵是，您可以通过递归计算数组两半的总和并将它们加在一起来计算 O(log(n)) 跨度（无限处理器的运行时间）中的数组总和。在计算扫描时，您只需要知道当前点之前的数组总和。

我们可以计算一个数组的扫描并行执行两半：使用上述技术计算第一半的总和。然后依次计算两半的扫描；前半部分从 0 开始，后半部分从您之前计算的总和开始。完整的算法有点棘手，但使用了相同的想法。

这是一些用于以不同语言进行并行扫描的伪代码（对于整数和加法的特定情况，但对于任何关联运算符的逻辑都是相同的）：

//assume input.length is a power of 2

int[] scanadd( int[] input) {
  if (input.length == 1)
    return input 
  else { 
    //calculate a new collapsed sequence which is the sum of sequential even/odd pairs 
    //assume this for loop is done in parallel

    int[] collapsed = new int[input.length/2]
    for (i <- 0 until collapsed.length) 
      collapsed[i] = input[2 * i] + input[2*i+1]

    //recursively scan collapsed values
    int[] scancollapse = scanadd(collapse)

    //now we can use the scan of the collapsed seq to calculate the full sequence

    //also assume this for loop is in parallel
    int[] output = int[input.length]
    for (i <- 0 until input.length) 
      //if an index is even then we can just look into the collapsed sequence and get the value
      // otherwise we can look just before it and add the value at the current index

      if (i %2 ==0) 
        output[i] = scancollapse[i/2]
      else 
        output[i] = scancollapse[(i-1)/2] + input[i]

    return output
  } 
}
于 2013-01-04T19:57:00.463 回答