我是个“低调”的人，总不喜欢表达出来，对异性如此，对工作也是如此。在翔哥的鼓励下，决定把自己工作的一些经验和思考写下来，和同道们一起分享。
 
 
 
ASIC设计中一种通用型并行设计方法：
 
 
 
1）流水网的概念提出
 
    IC设计中的控制有串行和并行两种思想。状态机方法反应了串行控制思想，有软件的思路，比较好理解，新手比较喜欢用。流水线方法是并行处理的思想，比较抽象，因为其效率高，老手喜欢用。从“流水线“的名字就容易知道，它只是一维的一条线，一个设计中可以有很多条。小设计中可能很容易设计，但对于大设计，流水线会很多条，条与条之间还有交叉，给同步带来很大的麻烦。显然还用流水线的思想去考虑并行的硬件设计显然就力不从心了。因而我们提出二维的流水网的概念，以完善并行设计思想。
 
 
 
2）流水级的概念提出及实现
 
   一条流水线就像一个产品代理线。例如我是一件产品中间的一级代理，我有我的上级代理，我也有我的下级代理。对于很大的一个代理系统中，我只需要和我的上级和下级打交道就可以了，而不会跨级（例如我的上上级或者下下级）。只有我仓库有货，我就可以往下出货，出货成功的条件是刚好下级也要货。一方面只要仓库没有满，我就可以向上级要货，另一方面，即使我的仓库满了，但现在刚好会出货，我也可以向上级要货，入货成功的条件是刚好上级也有货。入货和出货同时进行，正是并行系统的体现。这是典型的互联网分布式设计思想。因而我们可以提出流水级的概念。在流水级中，我们用upen表示上级可以出货，uprdy本级可以入货，dnen表示本级可以出货，dnrdy表示下级可以入货。本级入货成功的条件是上级可以出货并且本级可以入货（upen&uprdy），本级出货成功的条件是本级可以出货，下级可以入货（dnen&dnrdy）。
 
 
 
3）流水节点的概念的提出及实现
 
   一条流水线里面的流水级的上下级都只有一个，但在两端的流水级则可能有多个在其他流水线上的上下级。流水节点实现他们之间的同步，从而形成流水网络。需要同步的每个流水级都有一组输入和输出信号（可能是upen和uprdy的一组信号，也可以dnen和dnrdy的一组信号），本组输出信号就是除本组输入信号外的所有输入信号求与。
 
 
 
4）流水级，流水线，流水节点流水网的关系
 
流水级是一个点，多个流水级首尾相连可以形成流水线，多条流水线通过流水节点同步形成流水网。流水网可以实现任何的并行任务。

串行算法的直接并行
 
最直接，最易于理解的设计方法，发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。
 
Case 1：快速排序
 
​ 快速排序的串行算法思想为随机选取主元进行划分，之后递归排序。直接并行化思路即每次划分后将子任务分配给新的处理器。不过由于划分操作还是由单个处理器串行执行的，因此平均时间复杂度为$T(n)=T(n/2)+n=O(n)$。
 
​ 为了使Partition可以并行处理，重新考虑归并排序：划分操作可以看做是构造一个二叉树结构。选取的主元即为子树的根节点，且左子树小于右子树，因此可以将每个处理器看作一个节点，保存着A[i]的数值。
 
​ 引入新的数组LC[1…n]和RC[1…n]，其中LC[i]和RC[i]分别表示第i个处理器的左右子树根节点，这样n个处理器即构成一个二叉树。并且每个处理器保存父节点在LC的下标fi。初始时，设置第一个处理器的值为根节点，并通知所有处理器。在接下来的每轮中：
 
如果自己的值小于等于父节点，则应该在左子树中，将自己的下标填入LC[fi]中，直到所有左子树的节点都完成上述操作。此时最后一个填写的处理器i即被选为划分依据，该处理器退出计算，其余所有节点都将i更新为自己的父节点。
如果自己的值大于父节点的值，则应该在右子树中，将自己的下标填入RC[fi]中，更新父节点。
 
伪代码如下：
 
Repeat for each processor i!=root do
if(A[i]<A[fi] or A[i]=A[fi] and i<fi) then
	LC[fi]=i
	wait()
	if(i=LC[fi])
		exit
	else
		fi=LC[fi]
	endif
else
	RC[fi]=i
	wait()
	if(i=RC[fi])
		exit
	else
		fi=RC[fi]
	endif
EndReqeat
 
在算法执行后，根据LC和RC即可构造出一棵二叉树，通过前序遍历即可完成排序。此算法每一层树的构造用时为$O(1)$，平均树高为$O(logn)$，因此平均时间复杂度为$O(logn)$，最坏情况时树高为n，时间复杂度为$O(n)$。
 
Case2：枚举排序
 
​ 枚举排序为最简单的排序算法，每个数通过一次遍历比较出有多少排在自己前面的数作为自己的下标，之后通过一次遍历利用下标排序。串行时间复杂度为$O(n^2)$
 
​ 最直接的思维即为每个数并行的计算下标，这样每个数的时间开销为$O(n)$，并行算法时间复杂度为$O(n)$，由于每个处理器都需要读取整个数组，因此通讯复杂度为$O(n^2)$。
 
从问题描述开始设计算法
 
​ 即从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。
 
Case1：串匹配算法
 
​ 串行算法中著名的串匹配算法是KMP算法，算法时间复杂度为$O(m+n)$当模式串为常数级时算法具有线性时间复杂度。其核心思想为提前计算出next数组，记录当匹配失败时后移的长度，因此通过避免回溯去除了重复比较。
 
​ 不过KMP算法显然无法直接并行化，因此需要按照其思路重新设计算法。字符串是否具有周期性对后续算法的选择非常关键，因此首先对待匹配串P做周期性判断。定义失效见证函数(Witness Function)表征周期性，其定义如下：
 
 
对于$j(1\le j\le m/2)$，如果$P[j:m]̸=P[1:m-j+1]$，则存在$w(1\le w\le m-j+1),s=j-1+2,s.t.P(w)̸=P(s)$，则WIT(j)=w。
 
 
否则WIT(j)=0
 
 
显然当字符串不具有周期性时，$WIT(j)̸=0,2\le j\le m/2$。
 
非周期算法举例
 
​ 按照指数次序，P分割为大小为$(2^1,2^2,...)$的小块，并行和T的前缀匹配，淘汰失配的位置，最后对所有剩余位置进行全串T匹配。
 
借用已有算法求解新问题
 
矩阵乘法
 
​ 许多算法都需要矩阵乘法运算，这里记一下矩阵乘法的并行算法。待求矩阵$C=AB$，其中B为列向量，则可通过分割矩阵A计算C：
 
$AB=\left[\begin{array}{c}{A}_1\\ A_2\\ ⋮\\ A_m\end{array}\right]B=\sum A_{i}B$，其中$A_{i}B$可并行计算。
 
​ 如果B不是列矩阵，同样可以通过列分解计算。

欢迎转载，转载请注明：本文出自Bin的专栏blog.csdn.net/xbinworld。 技术交流QQ群：433250724，欢迎对算法、技术、应用感兴趣的同学加入。
 

 
 
并行编程的需求是显而易见的，其最大的难题是找到算法的并行功能，同时必须处理数据的共享和同步。但是，因为每一个算法都是不一样的，很难有通用的并行功能——粒度都有可能是不一样的。OpenCL提供了很多并行的抽象模型，因此算法开发人员可以在不同粒度上开发并行的算法，以及数据的共享和同步。
 

 
 
 

 一般来说，并行编程有两种大类型——分散收集（scatter-gather）与分而治之（divide-and-conquer）。
 
 
 
分散收集（scatter-gather）：数据被分为子集，发送到不同的并行资源中，然后对结果进行组合，也就是数据并行；
 
分而治之（divide-and-conquer）：问题被分为子问题，在并行资源中运行，也就是任务并行。
 
 
 

  
 
 
 
 

 看一个最简单数据并行实例：
 

 
 
 
 
 

 
 

 
 

 
 
理想情况是，所有的乘法都可以并行执行，而不是串行执行。
 
任务并行的示意图：
 

 
 
比如多CPU系统，每个CPU执行不同的线程。还有一类流水线并行，也属于任务并行：
 

 
 
流水线的每一个任务会处理不同的数据，这里不是串行的！而是流水线并行的，数据从一个任务传送到另外一个任务中，同时前一个任务又处理新的数据。
 

 
 
 
数据共享与同步
 

 这个大概是并行编程最难的部分，一般来说，下面两种情况需要有数据的同步：（1）一个子任务的输入依赖于另一个子任务的输出；（2）中间结果需要汇总合并。在OpenCL中，提供了两种数据同步机制（mechanism）：
 
 
 
锁（Locks）：在一个资源被访问的时候，禁止其他访问；
栅栏（Barriers）：在一个运行点中进行等待，直到所有运行任务都完成；（典型的BSP编程模型就是这样）
 
 

  
 
 
 
 

 （1）
 shared memory
 

 
 
 

 当任务要访问同一个数据时，最简单的方法就是共享存储shared memory（很多不同层面与功能的系统都有用到这个方法），大部分多核系统都支持这一模型。
 shared memory可以用于任务间通信，可以用flag或者互斥锁等方法进行数据保护，它的优缺点：
 
 
 
优点：易于实现，编程人员不用管理数据搬移；
缺点：多个任务访问同一个存储器，控制起来就会比较复杂，降低了互联速度，扩展性也比较不好。
 
 

  
 
 
 
 

 
 
 

 
 
 

 （2）message passing
 

 数据同步的另外一种模型是消息传递模型，可以在同一器件中，或者多个数量的器件中进行并发任务通信，且只在需要同步时才启动。
 
 
 
优点：理论上可以在任意多的设备中运行，扩展性好；
缺点：程序员需要显示地控制通信，开发有一定的难度；发送和接受数据依赖于库方法，因此可移植性差。
 
 

 
 

 
 
OpenCL并行执行内核
 
opencl可以有很多工作条目work-item，每一个item都有一个id，类似于线程的概念；看下面的例子：
 

 
 
左边是一般的编程写法，对数组元素递增；右边是opencl的写法，建立N个独立的work item，并行执行。这是最典型的opencl编程模型，用于数据并行任务，那么在真实的硬件中，又是如何完成并行任务的呢？实际上，这一块并不由opencl管，因为opencl只是一个编程标准，它提供了统一的编程接口和模型，而真正实现这些并行功能的是硬件支持厂商。比如intel对于CPU，NVIDIA对于GPU，Altera对于FPGA。正是因为有了opencl，才使得跨平台和跨硬件体系结构编程的可移植性成为可能。
 

 
 
由于性能是opencl编程的核心，而不是易用性，因此编程人员需要找到算法本身的并行部分，用kernel的方式来实现它们。工作条目就是一个最小的执行单元，工作条目可以组成工作组（work group）。这样的划分也与存储器有关，在opencl中，存储分为三大类：Global memory，Local memory，以及Private memory。Global是可以让所有的工作组和工作条目都可见，Local是只有当前工作组中的工作条目可见，而Private是只有单独一个工作条目可见。这样的存储访问控制，可以有效利用高速缓存提高效率，而不是每一次数据访问都需要外部DDR。
 

 
 

 
 
来简单看看GPU和FPGA的实现架构，GPU的体系结构是高度并行的，高级的GPU有非常多的运算单元，有很高的存储器总线，较高的吞吐量，但是存储访问的延迟也比较大。因此针对GPU的程序设计，存储器的管理和访问是很关键的。GPU一般有小容量高速缓存，并使用PCIe与主机进行通信（当然，现在也有一些新的技术不用PCIe）。见下图：
 

 
 

 
 

 
 
而FPGA是针对定制硬件进行设计，并行度非常高，现代FPGA通常有上百万个逻辑单元，每一个单元可以实现一个逻辑功能；有数千个片内存储器模块，用于快速访问数据；有数千个专用DSP模块，用于加速计算数学函数（比如浮点乘法）。如下图：
 

 
 

 
 
当面向FPGA编译opencl时，执行不受固定数据通路和寄存器限制，实际上是根据运算把逻辑组织到函数单元中，然后将其连接起来形成专用的数据通路，实现特殊的内核功能，如下图
 

 
 
针对FPGA的opencl编程，大致有两种形式，一种是辅助加速器，软件在CPU中实现，使用FPGA来加速某些模块的运算，CPU和FPGA采用PCIe连接；另一种是SOC的方式，CPU是内嵌在FPGA版上的，这样的方式可以减小通信延迟：
 

 
 

 
 
到这里，对于opencl的并行编程大概有个了解了。我们先看一下opencl编程以及运行在FPGA和CPU上的大致流程，具体的过程会在后面的章节中描述，这里看个大概：
 

 
 

 
 
需要有两种编译器，一个是标准的C编译器，一个是opencl的编译器（因为我参考的资料是altera的，所以是altera的opencl编译器）。opencl编译器会生成比特流文件，下载到FPGA板上，然后host程序运行调用，通过PCIe连接在FPGA上启动内核执行。编译器会将整个电路构建完成，包括了算法逻辑，存储器结构，存储器访问控制与通路，内核主机间的通路等。如下图
 

 
 

 
 

 
 
最后比较一下各种硬件形态的开发效率与执行效率，而opencl在FPGA上作用就是绿色箭头的方向。
 

 
 

 
 

 
 

 
 

时间坐标：2017.06 大三下
 
MPI并行编程是在大数据处理中很有意义的方法，能够在串行的基础上提高程序运行的效率，并行的去计算海量的数据。
 这篇文章可能会随着学习的深入不断的更新~
 
 
Introduction to MPI
 学MPI的时候，老师首先给我们回顾了一下并行编程的一些模式：
 并行可以分为两种：一种是任务并行，另一种是数据并行，根据这两种性质可以分为以下4种模式：
 SIMD（Single Instruction Multiple Data）:单指令多数据模式
 SPMD（Single Program Multiple Data）:单程序多数据模式 （这种貌似是最常用的模式）
 MIMD（Multiple Instruction Multiple Data）:多指令多数据模式
 MPMD（Multiple Program Multiple Data）:多程序多数据模式
 
然后介绍到底什么是MPI：
 MPI——Message Passing Interface 信息传递接口
 这里直接把百度百科放过来：
 MPI是一个跨语言的通讯协议，用于编写并行计算机。支持点对点和广播。MPI是一个信息传递应用程序接口，包括协议和和语义说明，他们指明其如何在各种实现中发挥其特性。MPI的目标是高性能，大规模性，和可移植性。MPI在今天仍为高性能计算的主要模型。
 主要的MPI-1模型不包括共享内存概念，MPI-2只有有限的分布共享内存概念。 但是MPI程序经常在共享内存的机器上运行。在MPI模型周边设计程序比在NUMA架构下设计要好因为MPI鼓励内存本地化。
 尽管MPI属于OSI参考模型的第五层或者更高，他的实现可能通过传输层的sockets和Transmission Control Protocol (TCP)覆盖大部分的层。大部分的MPI实现由一些指定惯例集（API）组成，可由C,C++,Fortran,或者有此类库的语言比如C#, Java or Python直接调用。MPI优于老式信息传递库是因为他的可移植性和速度。
 
 
与OpenMP并行程序不同，MPI是一种基于信息传递的并行编程技术。消息传递接口是一种编程接口标准，而不是一种具体的编程语言。简而言之，MPI标准定义了一组具有可移植性的编程接口。
 
2.有关MPI的初始化和常用函数
 以下几个基本是MPI每个程序都会有的，
 ① MPI_Comm comm = MPI_COMM_WORLD;
 ② MPI_Comm_Init(&argc,&argv); //初始化MPI执行环境，建立多个MPI进程之间的联系，为后续通信做准备
 ③MPI_Comm_Rank(comm,&rank); //用来标识各个MPI进程，给出调用该函数的进程的进程号,返回整型的错误值。两个参数：MPI_Comm类型的通信域，标识参与计算的MPI进程组； &rank返回调用进程中的标识号
 ④ MPI_Comm_Size(comm,&size); //用来标识相应进程组中有多少个进程
 ⑤ MPI_Finalize(); //结束MPI执行环境