Blelloch并行扫描算法

技术背景

由于现代计算机技术的发展，算法的并行能力越来越强大。所以当我们考虑计算复杂度时，不得不将并行计算考虑在内。例如本文我们要探讨的一个“累计求和“问题，简单来说，给定一个数组{1,2,3,4}，那么输出一个逐元素累计求和的结果：{1,3,6,10}，这里结果数组中的每一个元素，都是前面所有元素的总和。

在不考虑并行计算的情况下，这个计算的复杂度为O(n)，因为我们至少要把每一个元素都遍历计算一遍。但是考虑到并行技术的应用，其实可以通过用空间换时间的方法，降低其时间复杂度到O(log n)，也就是本文要介绍的Blelloch并行扫描算法。

Blelloch算法原理

算法流程示意如下图所示（图片来自于参考链接1）：

Blelloch算法大致分为两个步骤：

1. 通过递归的方法计算所有元素的总和，时间复杂度为O(log n)，同时也顺便完成了偶数位置的初步刷新。
2. 再通过换位和递归加和的方法，计算偶数位和剩下的奇数位的结果，得到最终结果。

这里以图片中的第一个数字为例，因为这个数字是所有数字中涉及到的操作数量最多的一个。在Upsweep阶段，第一个数字被加到第二个数字，然后是第四个数字、第八个数字中。在Downsweep阶段，第一个数字先是通过第四位数字中存储的信息加到第七位中，然后因为移位被加到第三位、第五位和第六位中（信息分别来自于第二位、第七位和第七位）。这样一来，最后输出的列表中，每一个元素就都包含了第一个元素的信息。例如这里是要计算加和，那么就相当于把1这个元素加到了后面的所有7个元素中。

代码实现

在参考链接1中给出了一个Python的List版本的实现方案，这里我们给出一个基于Numpy的Python版本实现方案。并且最终的输出结果通过使用numpy的cumsum函数来进行比对：

import numpy as npdef upsweep(arr):op_times = np.log2(arr.shape[0]).astype(np.int32)for i in range(op_times):arr[2**(i+1)-1::2**(i+1)] += arr[2**i-1::2**(i+1)]return arrdef downsweep(arr):last_num = arr[-1]arr[-1] = 0op_times = np.log2(arr.shape[0]).astype(np.int32)for i in range(op_times):arr[2**(op_times-i)-1::2**(op_times-i)], arr[2**(op_times-i-1)-1::2**(op_times-i)] = arr[2**(op_times-i-1)-1::2**(op_times-i)], arr[2**(op_times-i)-1::2**(op_times-i)].copy()arr[2**(op_times-i)-1::2**(op_times-i)] += arr[2**(op_times-i-1)-1::2**(op_times-i)]arr = np.roll(arr, -1)arr[-1] = last_numreturn arrdef blelloch_scan(arr):_arr = arr.copy()_arr = upsweep(_arr)_arr = downsweep(_arr)return _arrif __name__ == "__main__":test_arr = np.arange(2**25)print (np.sum(np.cumsum(test_arr)-blelloch_scan(test_arr)))# 0

最终输出的结果是0，也就是说两个算法的计算结果是一致的，那么也就是说明我们的算法实现没有问题。不过需要特别说明的是，虽然算法本身支持并行性，但是这里代码内容仅仅用于测试代码结果的正确性，并未实现其并行性的优势。因此从运算时间来说，可能速度还是会比numpy的原生实现满很多，但是这里是可以做并行化实现的，如果在CUDA中实现，预计会有较大的性能提升。

总结概要

本文介绍了一个可以用于并行化串行累计操作的Blelloch算法，可以通过用空间换时间+并行计算的方法，来降低特定计算的时间复杂度。这里我们给出了算法原理的大致介绍，以及基于Numpy的算法代码实现。

版权声明

本文首发链接为：https://www.cnblogs.com/dechinphy/p/Blelloch.html

作者ID：DechinPhy

更多原著文章：https://www.cnblogs.com/dechinphy/

请博主喝咖啡：https://www.cnblogs.com/dechinphy/gallery/image/379634.html

参考链接

1. https://moreality.net/posts/54261/