DSP

并行算法设计基本原则

2019-07-13 16:11发布

并行算法是并行计算的基础,与实现技术相结合,为高效率使用并行计算机提供解决方案。其基本原则简述如下:

1 与体系相结合

常见的并行计算的硬件载体有FPGA、GPU、多核CPU(ARM、x86)、DSP等。FPGA硬件加速的思想是设计流水线和设计多个加速核。GPU和多核CPU通过多核运算来达到并行的目的,核与核之间的通信开销是不可忽视的因素。DSP采用了并行指令和专用指令,能在一个时钟周期内执行复杂操作,但通用性不强。

2 具有可扩展性

并行算法是否是随处理机个数增加而能够线性或近似线性的加速,这是评价一个并行算法是否有效的重要标志之一。也就是说,如果一个并行算法的加速比是Sp(q) = O(q) 或者Sp(q) = O(q=(1+log(q))),则可以称为具有可扩展性的并行算法。

3 粗粒度

通常情况下,粒度越大越好。这是因为在每个处理机中有很多需要计算的工作任务,如此可以充分发挥多处理机的作用。并行加速比对细粒度问题一般情况下是不会很高的,这也是为什么并行计算需要求解大规模问题的原因所在。

4 减少通信

一个高效率的并行算法,通信是至关重要的。提高性能的关键是减少通信量和通信次数,其中通信次数通常情况下是决定因素。

5 优化性能

一个算法是否有效,不仅依赖于理论分析的结果,也和在实现的过程中采用的技术息息相关。性能主要看单处理机能够发挥计算能力的百分比,然后是并行效率。 小结:
影响并行算法效率的因素可能很多,但是这里所给出的几条是主要因素。因此,在算法设计的过程中,如果能够将上述5 条加以仔细考虑,就能够取得非常好的效果。 原文见 迟学斌《高性能运算》