-
lcs-parallel是指最长公共子序列的并行实现
资源介绍
##Longest Common Subsequence Parallelization with MPI, OpenMP, PThreads
###Design 每个线程/进程将处理 F 表的一列,并根据 DP 公式进行计算。 代码中略有变化,因为这里每个线程将负责一行,因为此矩阵加载到缓存中的方式。 对于每个线程,tow 和 column 被分成更小的切片用于计算和缓存重用,从而产生用于计算的子矩阵块。 由于 F 矩阵中的每个条目都依赖于正上方、左侧和左上角对角线位置的三个条目,因此相同的依赖关系将应用于每个子矩阵计算(取决于其他 3 个块,更具体地说:它需要上方块的最底行,左侧块的最右列,以及前一个对角块的右下方条目)。 由于这个限制,线程必须使用屏障同步,以对角线顺序,从整个 F 表矩阵的左上角位置开始到右下角。
PThreads 实现:
对于 PThreads 特定代码,m
- 上一篇: NOI/NOIP中的DP(动态规划)类型
- 下一篇: Meego 菜谱软件