拥有一个例如4个整数的数组,如何以最快的方式确定它的非零最小值？
解决方法
这个问题有一个平行的解决方案,但它可能不值得努力.
首先,我们在数组a上定义一个操作xchg(m,n)：
xchg(m,n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n])
如果两个元素’m’和’n’都包含非零值,则它们按升序排序两个元素’m’和’n’,如果’m’元素中的值为零,则交换它们.
接下来,我们执行一组五个这样的操作,如下所示：
xchg(0,2) xchg(1,3) xchg(0,1) xchg(2,3) xchg(1,2)
配对的xchg操作可以并行执行,与严格的顺序执行相比,时间成本降低了40％.当我们完成时,数组中的任何非零元素将按升序排序.最小值元素将在[0]中.如果该值为零,则数组中不存在非零值.
该解决方案利用了排序网络(http://en.wikipedia.org/wiki/Sorting_network)提供的固有并行性,但是4个元素的顺序扫描也使用了不超过三个比较操作,并且至关重要地需要平均一半的存储写入：
顺序扫描
int v = a[0]
for (n = 1; n < 4; n++) {
if ((a[n] < v && a[n] != 0 ) || v == 0) v = a[n]
}
