我是生物学家,我正在尝试学习计算机语言。但是,当我尝试学习lpthread库时,由于结果比顺序版本低,因此看起来很奇怪。
实际上,我仍在阅读Tanenbaum的书。但我的主要重点是学习RNA二级结构计算的基础知识。因此,我在一本书中找到了对nussinov算法的解释,并确实实现了它。但是,当我尝试制作并行版本时,我相信可能会遗漏所有要点,因为这是我第一次接触并行实现。
我的问题是:
1.如何为该算法实现数据并行版本?
2.为什么我的实现比顺序实现要慢一些?
该代码可用于:https://gist.github.com/drenge/6395472(每个文件是并行/顺序的不同版本)。
最佳答案
有两种方法可以使算法/程序并行化。
您研究算法并编写串行程序。然后,您开始对程序进行性能分析,以查看可以在何处获得速度提升。在那些地方,并行可能会派上用场(可能,而不是可能)。我称这种方法为“绝望的工具”。此方法很有用(!),但是在大多数情况下,下面的方法可以提供更好的性能。这种执行优化方法的方式仅考虑了编程和用户体验。
您采用该算法,然后尝试找出允许并行处理问题的其他算法。算法中是否有独立的计算或步骤,算法的某些部分可以在其他部分完全完成之前完成,...可以称为“理论方法”。请记住,每个线程都有其开销,并且您不希望开销大于您希望获得的收益。
实际上,两者的结合是最好的方法(如果确实需要并行性):首先专注于方法2(优化算法,使其在科学上保持正确,但可以在多线程中进行处理)。然后查看关键线程(可以在分析时找到)并开始优化该线程。
正如Kerrek SB所说:并行编程是一个非常复杂的话题,存在很多陷阱。在这条路的尽头,您应该问自己:值得付出努力。毕竟:浪费数周的学习时间和编程时间来获取一些时间是不值得的。
另一方面,如果您的程序将运行数千次,由于等待时间长或缺乏响应性而使用户沮丧,那么也许毕竟,制作性能更高的版本可能很有用。但是再说一遍:在没有并行混乱的情况下,您不能通过优化顺序版本来达到同一目标吗?很多算法的阶数为O(exp(x))或更糟,并且可以简化为O(x)甚至O(log(x))。
亲切的问候,
PB