前言，下周开始将会开启新一段旅程，并行计算的领域。对未来的憧憬，都是假象；前期的技术累计，也不一定用的上。

当然，其实就是打算写一个系列出来，学习的内容还是刘工的并行计算加速，也是浅尝辄止，希望从宏观的角度去了解并行计算的领域。

1，为什么存在并行计算的概念？运算单元当然是越快越好，无论是CPU，GPU。并行计算的热起来，也差不多以下三个原因。1）CPU加速差不多到头了，接下去继续加速，成本和难度也会增加；2）多核技术普及；3）ANN应该也有点功劳。

2，什么是并行计算。我的理解，以前是一个人搬砖，现在是多个人一起搬砖。并行计算的目标是什么。并行或者向量化技术的首要任务是尽可能发挥硬件提供的全部算力，以减少延迟（更快地完成计算任务）或者提高吞吐量（在相同的时间内完成跟多的任务）。说白了，就是尽可能减少模块等待，谁也别闲着。

3，如何选择合适的算法。标准就是复杂度计算，常用的方法就是时间负责度，空间复杂度和实现复杂度。实现复杂度有计算复杂度,仿存负责度，指令复杂度。4，分析模块之间的相互关系计算机内部组成差不多就是类似上述描述的。其实就是多个多级别的流水线在数据搬运和数据计算的事情。现在就是遇到很核心的问题，哪些模块必须串行，哪些模块并行之类的问题。作者定义为依赖性分析，分为指令依赖和循环依赖，我到时觉得可以分为指令先后顺序依赖，和数据前后顺序的依赖。5，如何理解并行计算以及加速。从我目前的认知来说，可以从两个角度，一个是从指令集和数据调度方面来理解，一个是从算法和应用逻辑角度。6，指令集角度。Enmmm.这个问题，先建模。无论是并行计算还是串行计算，都是存储和运算单元之间相爱相杀。CPU负责的指令搬运，指令解析，指令执行，结果回写。硬件单元就是内存，运算逻辑单元。在冯诺依曼架构里面，L1，L2，内存这些都是存储单元，为了CPU的指令快速获取数据设计的。并行计算也是如此，系统内部存在指令集的流水线，数据搬运的问题。1）运算单元入手，把指令流水线拉长，把一个模块切分多个，这样一个小块在干活的时候，其他小模块也不用闲着。指令多发射，说白了，就是不停的下发任务，让硬件单元不闲着。2）减少指令等待。乱序执行，分支预测。3）缓存技术，文中主要还是阐述了CPU的缓存技术。估计不同的架构不一样吧4）SIMD6，从算法层面讲优化，从算法层面对应用程序抽象，数据流经过控制流之后，输出结果。划分策略：主要还是数据划分或者是任务划分两类，原则是数据流和任务不相关，减少数据流的内部通信。通信，因为通信是并行算法引入的额外开销消耗 ，如果能够减少这种消耗就能提高并行效率。各种方法各有千秋，具体可以看我之前写的关于锁的内容。结果归并 ，任务切分之后，最后执行的结果归一化，这个部分是额外的开销。应用场景实际应用中，我们需要考虑单核 多核，GPU等各个因素。

                    
设计准则
上面的章节中给出了三个并行编程的目标：性能、生产率和通用性。但是还需要更详细的设计准则来真正的指导真实世界中的设计，这就是本节将解决的任务。在真实世界中，这些准则经常在某种程度上冲突，这需要设计者小心的权衡得失。
这些准则可以被认为是设计中的阻力，对这些阻力进行恰当权衡，这就称为“设计模式”[Ale79]，[GHJV95]。
基于三个并行编程目标的设计准则是加速、竞争、开销、读写比率和复杂性。
加速：性能增加是花费如此多时间和精力进行并行化的主要原因。加速的定义是运行程序的顺序执行版本所需要的时间，比上执行并行版本所需时间的比例。
竞争：如果对于一个并行程序来说，增加更多的CPU并不能让程序忙起来，那么多出来的CPU是因为竞争的关系而无法有效工作。可能是锁竞争、内存竞争或者其他什么性能杀手的原因。
工作-同步比率：单处理器、单线程、不可抢占、不可中断版本的并行程序完全不需要任何同步原语。因此，任何消耗
在这些原语上（通信中的cache 
miss、消息延迟、加解锁原语、原子指令和内存屏障等）的时间都是对程序意图完成的工作没有直接帮助的开销。重要的衡量准则是同步开销与临界区中代码的
开销之间的关系，更大的临界区能容忍更大的同步开销。工作-同步开销比率与同步效率的概念有关。
读-写比率：极少更新的数据结构更多是复制而不是分割，并且用非对称的同步原语来保护，以提高写者同步开销的代价来降低读者的同步开销。对频繁更新的数据结构的优化也是可以的，详见第4章的讨论。
复杂性：并行程序比相同的顺序执行程序复杂，这是因为并行程序要比顺序执行程序维护更多状态，虽然这些状态在某些情况下（有规律并且结构化的）理解起来很容易。并行程序员必须考虑同步原语、消息传递、锁的设计、临界区识别以及死锁等诸多问题。
更大的复杂性通常转换成了更高的开发和维护代价。因此，代码预算可以有效限制对现有程序修改的数目和类型，因为原有程序在一定程度的加速只值这么多
的时间和精力。进一步说，还有可能对顺序执行程序进行一定程度的优化，这比并行化更廉价、更有效。并行化只是众多优化中的一种，并且只是一种主要应用于
CPU是瓶颈的优化。
这些准则合在一起，让程序达到了最大程度的加速。前三个准则相互交织在一起，所以本节剩下的部分将分析这三个准则的交互关系。
请注意，这些准则也是需求说明的一部份。必须，加速既是愿望（“越快越好”），又是工作负荷的绝对需求，或者说是“运行环境”（“系统必须至少支持每秒1百万次的web点击”）。
理解这些设计准则之间的关系，对于权衡并行程序的各个设计目标十分有用。
1. 程序在临界区上所花的时间越少，潜在的加速就越大。这是Amdahl定律的结果，这也是因为在一个时刻只能只有一个CPU进入临界区的原因。
2. 程序在某个互斥的临界区上所耗费的时间必须大大小于CPU数的倒数，因为这样增加CPU数目才能达到事实上的加速。比如在10个CPU上运行的程序只能在关键的临界区上花费小于1/10的时间，这样扩展性才好。
3. 竞争效应所浪费的多余CPU和/或者本来该是加速的墙上时间，应该少于可用CPU的数目。CPU数和实际的加速之间的差距越大，CPU使用的效率越低。同样，需要的效率越高，可以做到的加速就越小。
4. 如果可用的同步原语相较它们保护的临界区来说开销太大，那么加速程序运行的最佳办法是减少调用这些原语的次数（比如分批进入临界区、数据所有权、RCU或者使用粒度更粗的设计——比如代码锁）。
5. 如果临界区相较守护这块临界区的原语来说开销太大，那么加速程序运行的最佳办法是增加程序的并行化程度，比如使用读写锁、数据锁、RCU或者数据所有权。
6. 如果临界区相较守护这块临界区的原语来说开销太大，并且被守护的数据结构读多于写，那么加速程序运行的最佳办法是增加程序的并行化程度，比如读写锁或者RCU。
7. 各种增加SMP性能的改动，比如减少锁竞争程度，能改善响应时间。 



文章转自 并发编程网-ifeve.com

        
        
                
    

【计算机组成原理】 Verilog语言编写32位并行加法器的理解
近日，为了完成本学期的计算机组成原理课程大作业的要求，我开始学习利用verilog语言编写的一套32位并行加法器以完成在整个项目中提高运算速度的基本要求。考虑到verilog语言和硬件设计的关联性，我们需要从结构上完成对并行加法器的理解。

32位加法器注重逻辑结构的顺序，本文主要简单介绍了加法器的逻辑顺序并附上代码说明，较为简单。
加法器结构
首先，并行加法器的特点基本决定了其组成结构，每一位均由对应的一位全加器确定输出结果，且每一位的对应进位输入将由超前进位加法器（CLA）在本位的运算开始前计算得到。

CLA基本功能：输入各位级的值，在全加器计算之前先行计算出各位级对应的进位输入，便于全加器计算并得到输出的值。
整个代码的流程框架为：

基础-1位全加器模块add；4位CLA模块cla

进阶1-使用1位全加器和4位CLA构成4位全加器

进阶2-使用4位CLA模块构成16位CLA模块

应用-使用16位CLA模块构成32位并行加法器
代码展示与理解
下文附上整理为逻辑顺序架构的32位超前进位加法器的整体代码，语句的基本注释已经附在代码块中。
//基础-设置一位全加器模块
module add(X,Y,Cin,F,Cout);

  input X,Y,Cin;
  output F,Cout;
  
  assign F = X ^ Y ^ Cin;
  assign Cout = (X ^ Y) & Cin | X & Y;
endmodule 
//一位全加器输入x，y，Cin；输出F，Cout；


//基础-设置4位超前进位加法器CLA
module CLA(c0,c1,c2,c3,c4,p1,p2,p3,p4,g1,g2,g3,g4);
   
	 input c0,g1,g2,g3,g4,p1,p2,p3,p4;
	 output c1,c2,c3,c4;
	 //直接采取超前进位方式，完成相应的进位的计算
	 assign   c1 = g1 ^ (p1 & c0),
	          c2 = g2 ^ (p2 & g1) ^ (p2 & p1 & c0),
			  c3 = g3 ^ (p3 & g2) ^ (p3 & p2 & g1) ^ (p3 & p2 & p1 & c0),
			  c4 = g4 ^ (p4 & g3) ^ (p4 & p3 & g2) ^ (p4 & p3 & p2 & g1) ^(p4 & p3 & p2 & p1 & c0);
	 
endmodule 
//4位CLA输入本级的基本参数，输出对应的各位级上的进位输入值


//进阶1-在一位全加器基础上设置四位并行进位加法器
module add_4(x,y,c0,c4,F,Gm,Pm);  //定义4位加法器模块
      input [4:1] x;  // 设置4位二进制输入x,y
	  input [4:1] y;
	  input c0;      //设置二进制输入进位c0
	  output c4,Gm,Pm; //设置二进制输出进位c4
	  output [4:1] F; //设置二进制输出4位数F
	  	  
	  wire p1,p2,p3,p4,g1,g2,g3,g4;  //设置wire类型线变量用于过程中计算
	  wire c1,c2,c3;
      //分四级完成单位上的一位全加器输出
	  add add1(
	             .X(x[1]),
					 .Y(y[1]),
					 .Cin(c0),
					 .F(F[1]),
					 .Cout()
				);
		
	  add add2(
	             .X(x[2]),
					 .Y(y[2]),
					 .Cin(c1),
					 .F(F[2]),
					 .Cout()
				);	
		
	 add add3(
	             .X(x[3]),
					 .Y(y[3]),
					 .Cin(c2),
					 .F(F[3]),
					 .Cout()
				);
			
	add add4(
	             .X(x[4]),
					 .Y(y[4]),
					 .Cin(c3),
					 .F(F[4]),
					 .Cout()
				);		
		
		CLA CLA(
			.c0(c0),
			.c1(c1),
			.c2(c2),
			.c3(c3),
			.c4(c4),
			.p1(p1),
			.p2(p2),
			.p3(p3),
			.p4(p4),
			.g1(g1),
			.g2(g2),
			.g3(g3),
			.g4(g4)
		);
				
		
	  
  assign   p1 = x[1] ^ y[1],	  
           p2 = x[2] ^ y[2],
		   p3 = x[3] ^ y[3],
		   p4 = x[4] ^ y[4];

  assign   g1 = x[1] & y[1],
           g2 = x[2] & y[2],
		   g3 = x[3] & y[3],
		   g4 = x[4] & y[4];

  assign Pm = p1 & p2 & p3 & p4,  //Pm和Gm分别为进位传递输出和进位产生输出
         Gm = g4 ^ (p4 & g3) ^ (p4 & p3 & g2) ^ (p4 & p3 & p2 & g1);

endmodule 

//进阶2-在4位CLA的基础上设置16位CLA模块
module CLA_16(A,B,c0,S,px,gx);
    input [16:1] A;
	input [16:1] B;
	input c0;
	output gx,px;
	output [16:1] S;
	
	wire c4,c8,c12;
	wire Pm1,Gm1,Pm2,Gm2,Pm3,Gm3,Pm4,Gm4;
	//同理分四级完成对应位数上的累加和超前进位计算
	add_4 add1(
	     .x(A[4:1]),
		  .y(B[4:1]),
		  .c0(c0),
		  .c4(),
		  .F(S[4:1]),
		  .Gm(Gm1),
		  .Pm(Pm1)
	);
	add_4 add2(
	     .x(A[8:5]),
		  .y(B[8:5]),
		  .c0(c4),
		  .c4(),
		  .F(S[8:5]),
		  .Gm(Gm2),
		  .Pm(Pm2)
	);
   add_4 add3(
	     .x(A[12:9]),
		  .y(B[12:9]),
		  .c0(c8),
		  .c4(),
		  .F(S[12:9]),
		  .Gm(Gm3),
		  .Pm(Pm3)
	);
   add_4 add4(
	     .x(A[16:13]),
		  .y(B[16:13]),
		  .c0(c12),
		  .c4(),
		  .F(S[16:13]),
		  .Gm(Gm4),
		  .Pm(Pm4)
	);
	assign   c4 = Gm1 ^ (Pm1 & c0),//计算各个分级位进位输出取值
	         c8 = Gm2 ^ (Pm2 & Gm1) ^ (Pm2 & Pm1 & c0),
			 c12 = Gm3 ^ (Pm3 & Gm2) ^ (Pm3 & Pm2 & Gm1) ^ (Pm3 & Pm2 & Pm1 & c0);
 
   assign  px = Pm1 & Pm2 & Pm3 & Pm4,//Pm和Gm分别为16进位传递输出和进位产生输出
	       gx = Gm4 ^ (Pm4 & Gm3) ^ (Pm4 & Pm3 & Gm2) ^ (Pm4 & Pm3 & Pm2 & Gm1);
	       
endmodule 


//进阶3-由16位CLA直接设置32位CLA
module add32(A,B,S,C32);
    input [32:1] A;
	input [32:1] B;
	output [33:1] S;
	output C32;
	 
	wire px1,gx1,px2,gx2; //设置中间操作变量
    wire c16;
//将32位数分为两个16位操作数带入16位CLA模块完成并行计算过程
  CLA_16 CLA1(
      .A(A[16:1]),
		.B(B[16:1]),
		.c0(0),
		.S(S[16:1]),
		.px(px1),
		.gx(gx1)
	);
  
  CLA_16 CLA2(
        .A(A[32:17]),
		.B(B[32:17]),
		.c0(c16),
		.S(S[32:17]),
		.px(px2),
		.gx(gx2)
	);

  assign c16 = gx1 ^ (px1 && 0), //默认AB相加时c0 = 0
         C32 = gx2 ^ (px2 && c16); //确定32位输出进位为c32
         S[33]=C32


endmodule 
//32位并行加法器输入为32位二进制数A，B；最终的输出为33位二进制数S(将整体进位整合到二进制数当中成为第33位）；

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