并行,分布式还有通信题是最近xcpc兴起的很好玩的一系列题.
最近想看看怎么写cuda算子,可以的话顺带给青云悲贡献一个题.
本篇主题为并行计算.
并行计算
首先所有数据全部大于0,前缀和是单调递增的.
假设
,题目要求的式子即
如何并行计算前缀和:分块.
1024个内存,一次32条指令,就分成32组,先用31条指令每个小块内算出前缀和,然后每个大块加上上一个块的前缀和,总计62条指令.
而且这个并行不需要可逆性,也就是说max也能如此分块计算.
知道如何执行一个运算,以及如何写出这个算子,这个题就做完了.