网站 二维码的作用,钟祥网站建设,桂林象鼻山在哪,网站开发合同注意事项C17 并行化STL算法 文章目录 C17 并行化STL算法概念环境准备工具类 并行算法 - 使用并行算法 - 执行策略总览选择标准详细介绍顺序执行 seq并行化顺序执行 par并行化乱序执行 par_unseq 并行算法 - 异常处理可以不使用并行算法并行算法 - 限制并行算法有哪些原有算法17引入新算…C17 并行化STL算法 文章目录 C17 并行化STL算法概念环境准备工具类 并行算法 - 使用并行算法 - 执行策略总览选择标准详细介绍顺序执行 seq并行化顺序执行 par并行化乱序执行 par_unseq 并行算法 - 异常处理可以不使用并行算法并行算法 - 限制并行算法有哪些原有算法17引入新算法 概念
为了从现代的多核体系中受益C17标准库引入了并行 STL算法允许使用多个线程并行处理元素。
C17为许多算法扩展了一个新的参数来指明是否要并行运行算法。并且新增了一些专为并行编程补充的新算法。
环境准备
并行算法在 linux上使用 gcc 或者 clang进行编译需要
安装 tbb库—— 线程构建模块 (TBB) Thread Building Blocks链接时指定-ltbb选项
否则
tbb库链接结果安装指定-ltbb选项可正常使用并行算法安装未指定编译错误未安装指定编译错误未安装未指定正常编译但并行算法会串行化变得和串行算法一样
# 编译选项
g ‐stdc17 ‐ltbb main.cpp ‐o a.out工具类
有时需要计时器来测量算法的速度。因此引入一个简单的辅助类。
初始化一个计时器提供 printDiff()来打印出消耗的毫秒数 并 重新初始化计时器
#include iostream
#include string
#include chrono
/********************************************
* timer to print elapsed time
********************************************/
class Timer {
private:std::chrono::steady_clock::time_point last;
public:Timer() : last{std::chrono::steady_clock::now()} {}void printDiff(const std::string msg Timer diff: ) {auto now{std::chrono::steady_clock::now()};std::chrono::durationdouble, std::milli diff{now ‐ last};std::cout msg diff.count() ms\n;last std::chrono::steady_clock::now();}
};并行算法 - 使用
怎么让现有算法并行运行和使用新的并行算法
包含头文件 execution
#include execution C17之后一般来说可以向并行 STL算法传递不同的 执行策略 (execution policies) 作为第一个参数。 cpprefrence上看看STL算法支不支持一般是添加执行策略到第一个参数即可。例如std::execution::par 使用参数 传递/修改 执行策略 的好处可在运行时更改策略时顺序执行/并行执行不需要再修改调用方式。
所有的并行算法要求迭代器至少是前向迭代器。
#include execution // for 执行策略
#include algorithmstd::vectorstd::string coll {a, b, c};sort(coll.begin(), coll.end());
sort(std::execution::seq, coll.begin(), coll.end());
sort(std::execution::par, coll.begin(), coll.end());
sort(std::execution::par_unseq, coll.begin(), coll.end());// 并行计算平方根
for_each(std::execution::par,coll.begin(), coll.end(),[] (auto val) {val.sqrt std::sqrt(val.value);});并行算法 - 执行策略
总览 以下执行策略分别是定义在 namespace std中的新类sequenced_policy、parallel_policy、parallel_unsequenced_policy的 constexpr对象。 执行策略含义std::execution::seq顺序执行std::execution::par并行化顺序执行std::execution::par_unseq并行化乱序矢量化执行
标准库提供了新的类型特征 std::is_execution_policy在泛型编程中检查模板参数是否是执行策略。
并行化乱序执行需要编译器/硬件的特殊支持从而检测如何矢量化。
非并行化/并行化
并行化——多个线程执行非并行化——单一线程
顺序、乱序 乱序允许矢量化执行不保证顺序地对元素执行操作。 即存在可能 某个线程在执行完某一个元素的处理之前可能会切换到其他的元素。 某个线程先执行多个元素的第一步处理再回过头来对这些元素执行下一步处理。 顺序不允许矢量化执行顺序地对元素执行操作 当某个线程对新的元素进行操作之前它会先处理完它之前处理过的其他元素。
选择标准
benchmark测试结果主要依赖于硬件、使用的 C编译器、使用的 C库并行算法实际运行的方式是实现特定的
没有通用的方法来判断什么场景什么时间值得使用并行算法。不能说多线程就一定比顺序执行好启动和控制多线程也会消耗时间。
从理论上讲如下判断依据可以作为参考 简单算法每个元素计算耗时短元素数量少。并行执行永远会更慢建议顺序执行 std::execution::seq 或 默认版本。 复杂算法每个元素计算耗时长元素数量多。适合使用并行算法 处理过程需要独立于其他元素的处理 —— 并行化顺序执行 std::execution::par处理过程不需要独立于其他元素的处理 —— 并行化乱序执行 std::execution::par_unseq
详细介绍
顺序执行 seq
std::execution::seq 指定顺序执行 策略本身 单一线程执行单个线程对所有元素逐个执行操作。不允许矢量化执行顺序地对元素执行操作——当某个线程对新的元素进行操作之前它会先处理完它之前处理过的其他元素。 与非并行化版本进行对比 实际上该策略非常类似不接受执行策略参数的非并行化版本但多一些约束条件例如 for_each()不能返回值所有的迭代器必须至少是前向迭代器 提供该策略的目的 可只修改一个参数来要求顺序执行而不是换用一个签名不同的函数。
并行化顺序执行 par
std::execution::par 指定并行化顺序执行 策略本身 多个线程执行顺序执行允许矢量化 提供该策略的目的 比非并行化顺序执行可能要快一些 避免在以下情况中出现死锁或其它bug与 par_unseq不同 执行了某个元素的第一步处理后必须在执行另一个元素的第一步处理之前执行这个元素接下来的处理步骤。
并行化乱序执行 par_unseq
std::execution::par_unseq 指定并行化乱序执行
策略本身 多个线程执行乱序执行允许矢量化 提供该策略的目的 比非矢量化 顺序执行可能要快一些
并行化乱序执行需要编译器/硬件的特殊支持来检测哪些操作如何矢量化。
并行算法 - 异常处理
当指定了执行策略后 处理元素的函数因未捕获的异常而退出时会调用 std::terminate() 注意即使选择了顺序执行策略也会这样。
注意存在并行算法本身抛出异常的可能性 例如申请并行执行所需的临时内存资源时失败了会抛出 std::bad_alloc 异常。从而直接 std::terminate() 所以使用非并行化版本的算法有时是更好的选择。
可以不使用并行算法
使用非并行算法可以提供以下好处
可以使用输入和输出迭代器。算法不会在遇到异常时 std::terminate()算法可以避免因为意外使用元素导致的副作用。算法可以提供额外的功能例如 for_each()会返回传入的可调用对象我们可能会需要该对象最终的状态
并行算法 - 限制
有限制的并行 STL算法
限制返回类型 void、前向迭代器 for_each() 限制前向迭代器
for_each_n() all_of(), and_of(), none_of()
find(), find_if(), find_if_not()
find_first_of()
count(), count_if()
mismatch()
equal()
is_partitioned()
partial_sort_copy()
includes()
lexicographical_compare()
fill_n()
generate_n()
reverse_copy()
rotate_copy()
copy(), copy_n(), copy_if()
move()
transform()
replace_copy(), replace_copy_if()
remove_copy(), remove_copy_if()
unique_copy()
partition_copy()
merge()
set_union(), set_intersection()
set_differrnce(), set_symmetric_difference()
inclusive_scan(), exclusive_scan()
transform_inclusive_scan(), transform_exclusive_scan()并行算法有哪些
原有算法
C17之前标准中不需要修改就可以并行运行的算法
find_end(), adjacent_find()
search(), search_n()和“搜索器”一起使用时除外
swap_ranges()
replace(), replace_if()
fill()
generate()
remove(), remove_if(), unique()
reverse(), rotate()
partition(), stable_partition()
sort(), stable_sort(), partial_sort()
is_sorted(), is_sorted_until()
nth_element()
inplace_merge()
is_heap(), is_heap_until()
min_element(), max_element(), min_max_element()无并行版本的算法
为了并行地运行 accumulate()使用reduce() 或者transform_reduce()。为了并行地运行 partial_sum()使用…scan()算法。为了并行地运行 inner_product()使用transform_reduce()。
accumulate()
partial_sum()
inner_product()
search()和“搜索器”一起使用时
copy_backward(), move_backward()
sample(), shuffle()
partition_point()
lower_bound(), upper_bound(), equal_range()
binary_search()
is_permutation()
next_permutation(), prev_permutation()
push_heap(), pop_heap(), make_heap(), sort_heap()17引入新算法
