我正在尝试使用OpenMP API(或pthread)并行化以下代码,其时间复杂度为O(n)。我想知道是否可以将输入数组分成
这是一个非常经典的算法问题,到目前为止我没有看到任何人尝试实现并行化版本。
重要提示:简单的归约不能解决此问题,因为我仅从左到右读取数组。因此,并行化不是那么容易...
X
块(X
=线程数),并为每个块并行处理。这是一个非常经典的算法问题,到目前为止我没有看到任何人尝试实现并行化版本。
重要提示:简单的归约不能解决此问题,因为我仅从左到右读取数组。因此,并行化不是那么容易...
#include<stdio.h>
/* The function assumes that there are at least two
elements in array.
The function returns a negative value if the array is
sorted in decreasing order.
Returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for(i = 1; i < arr_size; i++)
{
if(arr[i] - min_element > max_diff)
max_diff = arr[i] - min_element;
if(arr[i] < min_element)
min_element = arr[i];
}
return max_diff;
}