ggaaooppeenngg

之前一直小看了heap觉得这个数据结构比较简单,等串讲的时候发现其实并不是的,居然为了heap的插入删除争论了很久.
这里特地记录一下,heap的性质是递归的父结点比子节点大，说白了就是一个优先队列.
push,pop都只要分别做一次向上调整和向下调整.

但之前我的知识体系好像调整要有一次down再一次up.
这是在真正调整的时候用的比如替换任意一个元素或者删除任意一个元素.
替换很好理解就是引入一个元素可能很大也可能很小,要么向上要么向下.
而我卡住的地方是删除,老是觉得把最后一个结点换上来应该是不用向上调整只要向下的，
因为这个定义是递归的,但是不是的，虽然在删除处i下面的子树可以，但是如果最后一个结点不在i的子树下面,比如另外一个i的兄弟子树下面，整棵树都比i小的话（这里指最小堆），那么其实情况和替换是类似的，所以任意删除和替换才是会把down up两个函数都写入,但都是只执行一次.

之前用jekyll在Github上面搭建了一个博客，但是发现语法高亮什么的，并不完全是markdown格式的，而且迁移起来也奇奇怪怪的，于是决定换成hexo来搭建。另外一个原因是想在博客里面写一些数学公式等等，但是却发现没有什么主题是支持的，然后就想自己改一个，结果发现自己改的实在太丑，不想用,当然，作为工程师型的人，丑不丑倒是无所谓，主要是配来配置去把耐心给消耗了，最后决定用别人写好的主题，选择了next漂亮而且支持数学公式等等（当然数学公式的支持就是添加一个js库MathJax就可以搞定了，也不是什么难事）。

hexo的部署可以参考官网和一些网上的资料，已经有很多了。这里主要记录一下hexo的一些主要使用方法。

写作

1. 草稿

   通过hexo new [layout] <title>这样的命令就可以生成对应的文件，比如草稿，
   hexo draft “draft”（如果题目有空格，要带双引号，layout默认是post,这
   些layout都存在_scaffolds_下面。可以通过hexo设置是否在网站上显示草稿，我
   设置的是显示（设置*_config里面的render_drafts为true*即可)。

2. 发布

   发布可以选择草稿发布，也可以选择直接发布新文章,对应的命令分别是hexo publish [layout] <title>和hexo new [post] <title>，
   这个时候生成的静态文件里面就可以看到新的文章了。

3. 前缀

   tags和categories里面的内容,按照[content1,content2,…]的格式就可以分开显示在标签栏里面。

4. 特殊插入

   tag-plugins中可以找到一些特殊需要的插入，比如插入gist,twitter的引用或者youtube视频等等。

5. i18n

   支持国际化，在*_config.yml*下面设成

    language:
    - zh-CN
    - en
   

   设置*_config.yml里面的i18n_dir可以根据路径前缀判断对应的语言。
   在发布的时候带上–lang*选项设置语言，比如hexo new "Hello World" --lang tw就可以针对不同的语言产生对应目录。

6. 数学公式

   数学公式主要依赖于MathJax,在编辑文本的时候$$...$$和\[...\]用来表示数学公式，\\(...\\)用来表示行内数学公式，比如\\(a^2+b^2=c^2\\)的效果是\(a^2+b^2=c^2\)。而$$ a^2+b^2=c^2 $$,就会另起一行。

   $$ a^2+b^2=c^2 $$

   具体的使用可以在这里查看
   注意markdown的一些符号，需要在公式里面转义，省的被markdown语法误解。

• Peiyi Tang
• 计算机科学部
• 阿肯色州大学小石城分校

原论文

##概要

Go语言是一门新的并发编程语言.它的目标之一就是应对多核并行编程的挑战.在这篇论文里面,我们展示了两个多核并行的Go程序和他们在八核微处理器上的性能和并行Go代码的效率.

1 介绍

直到2000年,计算机架构都可以把并发运算封装在硬件中,每18个月微处理器的性能就可以翻倍,而不需要丝毫地改动串行编程模型(sequential programming model).但有三个问题日益凸显,处理器和内存的速度在跨越式增长,指令级别的并发存在限制,高性能的计算能力也被提高,综合这三个原因,在2000年所有的微处理器厂商都转向了多核微处理器的开发.

多核处理器展现了非常好的性能,为了能够充分发挥这样的性能,就需要通过并行编程来解决.运行串行的代码只能够发挥单个处理器的性能,而浪费了其他处理器的资源.

最早和多核并行编程有关的书是_”multi-thread programming”[1],然而在多线程模型上实现并行和并发程序是非常困难的.就像_Edward A.Lee[2]指出的,多线程编程的问题是,这样的方式是一种落后的方式,使得程序在一开始就变得不确定,然后通过使用信号量,锁机制还有监视器来减少不确定性.

最近Google推出了一门新语言Go(这里的最近是指2009年).Go是并发的并且具有垃圾回收的系统编程语言[3],目标之一就是迎合多核编程的挑战使得并发编程更加简便.Go不使用多线程模型,而是通过Go的routine（基于CSP的communication通道).任何Go语言中的函数,能够作为串行编程模型中的普通routine或者用关键字go在前端执行一个Goroutine,在运行时里面一个被调用的Goroutine是和调用者routine并发执行的，而不管他们是否运行在同一个CPU上.从编程这的角度来说,Go routine是并发的归宿,而且对比于之前的锁方式等等，有更加良好的确定性.Go在CSP的communication通道的基础上,扩展了无缓冲区大小的通道来实现异步发送(或写)操作.通道是Go语言的预定义类型(first-class),能够从一个routine传递到另一个routine.Goroutine和CSP通道的结合提供了一个强大的机制来来保证达到一个期望的确定性的并发计算。

在这篇论文中,我们将通过两个例子展示Go语言在并行编程方面体现的多核利用率.第一个例子在第二节中讨论,是没有同步和通道的并行积分问题.第二段程序在第三节中讨论,是一个并发动态规划的问题,需要在多个并发任务中实现同步,第四节总结这篇论文.

2 并行计算积分

计算积分是一个用来展示并发编程和它本身加速度(表示的是多处理器执行时间和单处理器执行时间的比值)的常见例子,例如一个函数\(f(x)\),在\([a,b]\)上的积分.

$$ \int_a^b f(x),dx $$

能够通过\(n\)个在曲线下方的长方形来求和估计计算\(f(x)\),

$$ \sum\limits^{n-1}_{i=0} hf(a+h(i+\frac{1}{2})) $$

因为\(h = \frac{a-b}{n}\)是小长方体的宽度.因为只有有限个\(np\),并且\(np << n\),所以只要创建\( np\)个计算组,每个计算组分配给一个处理器就可以得出结果.为了平衡处理器之间的计算,我们用阻塞公式(blocking formula)[5]来把n个矩形\(0,\cdots,n-1\)平均分配到\( np\)个计算组里.

$$ \lfloor \frac{i*n}{np} \rfloor,\lfloor \frac{i*n}{np} \rfloor + 1,\cdots,\lfloor \frac{(i+1)*n}{np} \rfloor - 1 $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func f(a float64) float64 {
	return 4.0/(1.0 + a * a)
}
func chunk(start, end int64, c chan float64) {
	var sum float64 = 0.0
	for i:= start; i < end; i++ {
		x := h * (float64(i) + 0.5)
		sum += f(x)
	}
	c <- sum * h
}
func main() {
	runtime.GOMAXPROCS(np);
	h = 1.0/float64(n)
	..//start timing
	c := make(chan float64, np)
	for i:=0; i < np; i++ {
		go chunk(int64(i)*n/int64(np),
		(int64(i)+1)*n/int64(np), c)
	}
	for i:=0; i < np; i++ {
		pi += <-c
	}
	...//end timing
}

代码1:计算Pi的代码.

通过循环触发Goroutine来实现np个子算组的并行运算,代码1显示了被省略的Go代码来计算Pi的积分:

$$ \pi=\int_0^1 \frac{4}{1+x^2},dx $$

计算一个计算组是通过 chunk(start,end int,c chan float64)这个函数实现的,这个函数计算从start到end之间的矩形面积.Channel c则是用来在结束的时候进行同步,并且把计算组的结果送到main routine.

图2:执行时间

主routine 通过建立运行时来开始所有在\(np\)个处理器上的Go routine,通过调用rutime.GOMAXPROCS(np)就可以实现.make语句构造了一个有np大小缓存的通道,第一个循环是通过chunk开始所有的routine,并且把通道传递进去.这些routine和main routine并发执行.

图3:积分的加速度

pi+= <-c会执行np次,累加以获得pi的结果,在第一个chunck()调用的时候,通道为空,从空的通道读取会阻塞main routine.第二个循环在接受了所有routine的

结果之后终止,pi就会得到最终结果.

我们在一个八核AMD Opteron(tm) 2.8GHz 1024KB cache的处理器上.我们把问题的n从\(10^4\)调整到\(10^10\)然后把处理器个数从1提升到8.图2 展示了,并行Go计算pi的效率.对于小的问题规模\( (n = 10^4,10^5) \),使用多核不能增加的执行时间,这是因为过多的调度和初始化routine导致的,大部分时间没有执行并行计算.当问题规模n变大的时候\((n = 10^8,10^9,10^10)\),使用多处理器能够显著的增加执行时间.

为了能够体现并发执行的加速度(speedup),我们可以通过下面的式子计算速度:

$$ S_{np} = \frac{T_1}{T_{np}} $$

在这里 \(T_1\)和\(T_{np}\) 是1个处理器和np个处理器.他们对应的结果在图3中.注意,当问题规模非常大的时候,增长几乎就是线性的了,特别是问题规模达到\(n=10^9\)的时候,几乎能达到7.79,这个时候处理器的个数是8个.

3 并发的动态规划

现在我们转向第二个多核并发的例子,这个例子是一个动态规划问题.动态规划旨在存在最优子结构的问题的解决,并且动态规划还要解决重叠问题[6],只计算一次子问题,然后把结果存在备忘录中,也就是一个用来查询结果的表结构.这种方式很多时候能把时间复杂度从指数级降低到多项式的级别.我们使用优化二分搜索树问题来展示动态规划的多核并行方式.

给出n个key,\(k_1,\cdots,k_n\)和他们的概率分布\(p_1,\cdots,p_n\),优化二分树搜索问题是找到二分搜索树(BST)的key的最小平均时间.

设\(BST_{i,j}\)为优化BST,存储了key,\(k_1,\cdots,k_n(j>=i-1)\),并且\(MST_{i,j}\)代表最小搜索时间(mean search time,MST),\(BST_{i,i}\)是一个只有root \(k_i(1 <= i <= n)\) 的单一节点，它的最小搜索时间是\(MST_{i,i}\),也就是\(p_i\).另外\(BST_{i,i-1}\)是一颗空树\((1 <= i <= n)\),并且它的最小搜索时间是\(MST_{i,i-1}=0\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

var (
	cost [n+1][n+1]float
	root [n+1][n+1]int
	prob [n]float
}

func mst(i,j int) {
	var bestCost float = 1e9 + 0.0
	var bestRoot int = -1
	switch {
		case i >= j:
			// 如果是空树,代价为0,没有根节点,注意i==j也是空的,j-1,j才是本结点
			cost[i][j] = 0.0
			root[i][j] = -1
		case i+1==j:
			// 如果是单结点,就是自己的概率
			cost[i][j] = prob[i]
			root[i][j] = i+1
		case i+1 < j:
			// 如果是非单结点树,这里要注意的是,如果子树增加了一个root深度就会+1
			// 所以每个子树的期望就会增加这个子树的所有结点的概率和,再加上一个根节本身的深度时1所以期望也就是概率的值
			// 所以整个增加的期望就是构成的整个树的结点的概率和,这就是为什么要算psum.
			psum := 0.0
			for k := i; k <= j-1; k++ {
				psum += prob[k]
			}
			// 计算出子树期望和最小的情况,这里利用了最优子结构.
			for r := i; r <= j-1; r++ {
				rcost := cost[i][r] + cost[r+1][j]
				if rcost < bestCost {
					bestCost = rcost
					bestRoot = r+1
			}
			cost[i][j] = bestCost + psum
			root[i][j] = bestRoot
		}
}
func main(){
	...// initialize prob[]
	for i:=n; i>=0; i-- {
		for j:=i; j <= n; j++ {
			mst(i,j)
		}
	}
}

代码4: 动态规划算法

如果优化二叉搜索树\(k_1,\cdots,k_n \),把\( k_r ( 1 <= r <= n) \)作为根节点,那么左子树\(k_1,\cdots,k_{r-1}\)和右子树\(k_{r+1},\cdots,k_n\)必须也是最优化的(这个用反证法可以证明).因此,\(MST_{i,j}\)能够递归定义成

$$ MST_{i,h} = \min_{i<=r<==j} (MST_{i,r-1} + MST_{r+1,h}) + \sum_{k=i}^jp_k $$

这个公式能够决定MST的最小子树的r对应的这棵树的根节点.

存储MST的结构是矩阵(n+1)X(n+1)的上三角部分,这个矩阵对应的是最小搜索时间MST的cost[n+1][n+1].特别地 MSTi,j 存储在cost[i-1][j].相似地,\(k_i,\cdots,k_j\)优化二叉搜索树的根节点存储在root[i-1][j],root是另外一个root[n+1][n+1]矩阵.时间的概率的分布存储在数组prob[n]中,\(p_i\)对应prob[i-1].

图5:任务间的数据依赖.

寻找最优二叉搜索树的串行动态规划算法[7]的代码在 代码4 中展示.总得来说,这个算法计算cost[i][j](0 <= i <= j <= n)时是需要递归使用cost[i][i],cost[i][i+1],…,cost[i][j-1]和cost[i+1][j],cost[i+2][j],…,cost[j][j]的值的.cost[i][j]的计算依赖于cost[i][j-1],cost[i+1][j]的依赖.
图5展示了用来计算cost[i][j]的数据结构.这是因为串行算法里面的嵌套循环从按照从下到上以及从左到右来计算cost[i][j]的,当并行化这个算法的时候,我们必须借助这个数据依赖.

原则上,我们可以构造(n+1)*(n+1)/2大小的矩阵,一个来记录cost,但是这个并行任务的粒度太小了,会使得调度和同步的代价过高,而挤占了并行计算的资源.为了能够控制并行计算的粒度,我们把任务空间切分成 vp(vp+1)/2 个块,并且把每个快分配给一个Goroutine作为一个运算单元.

在每个任务块内,Goroutine以自顶向下或者由下而上的顺序计算二维数组cost,root的一部分.为了能够实现数据块间的数据依赖,要使用channels进行同步.

图6展示了10个数据块,vp=4,数据规模n=11的一个用Gochannel同步的结果.每个点代表了数组cost的一个元素的计算称作point.任务块之间的箭头时Gochannel的同步.特别地,一个数据块左数据块和下数据块计算完毕才能够开始计算.每个任务块都有一个下标\((i,j)(0<=i<=j<=vp-1)\).Channels能够通过发送给通道的任务块来识别.特别的,title(i,j)通过水平线上的channel \(h_{i,j}\)把信号传送给右边的title(i,j+1)(如果不是在最上面),或者通过水平的通道把信号发送到上面的title(i-1,j).在对角线上的title(i,j)(i==j)能够开始计算,因为他们没有依赖于任何其他的任务块的计算.最右上角的(vp-1,vp-1)时最后一个计算的.为了能够发送结束的信号,有另外一个finish通道用来告知main routine计算的结束.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

var h,v [vp][vp] chan int
var finish chan int
..//declare other variables and constants
func creatChan() {
	for i:=0; i < vp; i++ {
		for j:=i; j < vp; j++ {
			if j < vp-1 {h[i][j] = make(chan int, 1)}
			if i > 0
			{v[i][j] = make(chan int, 1)}
		}
	}
}
func mst(i,j int) {
	... // the same as in the sequetial code
}
func chunk(i,j int) {
	var bb int
	il := (i * (n+1))/vp
	//block-low for i
	ih := ((i+1) * (n+1))/vp - 1
	//block-high for i
	jl := (j * (n+1))/vp
	//block-low for j
	jh := ((j+1) * (n+1))/vp - 1
	//block-high for j
	if i < j {
		// not a tile on the diagonal
		<-h[i][j-1] // receive from the left
		<-v[i+1][j] // receive from below
	}
	for ii:=ih; ii >= il; ii-- {
		if i==j { bb = ii } else { bb = jl }
		for jj:=bb; jj <= jh; jj++ {
			mst(ii,jj)
		}
	}
	if j < vp-1 {// not a tile on the right border
		h[i][j] <- 1
	}
	if i > 0 {
		// not a tile on the top border
		v[i][j] <- 1
	}
	if i==0 && j==vp-1 {//the last tile
		finish <- 1
	}
}
func main() {
	...//read flags
	runtime.GOMAXPROCS(np)
	... //start timing
	creatChan()
	finish = make(chan int, 1)
	for d:=0; d < vp; d++ {//sub-diagonal of j=i+d
		for i:=0; i+d<vp; i++ {
			go chunk(i, i+d)
		}
	}
	<-finish
	....//end timing
}

代码7 Go语言并行动态规划

图8 规模2000的执行时间

我们选择设定问题规模为2000来进行实验,来保证足够大的精确测量.我们需要在八核AMD Opteron(tm)微处理器运行图7中的并行代码,改变每个维度的block的数量,从1,2,4,8,…,1024和2001.当vp越大的时候,粒度越小.vp=1对应了粒度最大的情况,没有并行,只有一个数据块.这种情况只有一个Goroutine调用,一个channel finish.
执行时间几乎就像串行结果一样的,不管多少处理器被利用.vp=2001的时候对应粒度最小的最大任务块,每个点都有一个.
图8展示了不同的vp和不同处理器np的情况下并行执行时间.对于每种vp和np的组合,我们运行5次,用单用户模式,计算平均值并放入图8中.
注意np=1的时候执行时间.我们能够观察到执行时间会递减,当vp从1增加到32,这是因为vp的增加创造了更多的任务块并且增加了缓存的命中率.
当vp从32增加到2001的时候,执行时间却反而增加了,这是因为缓存命中率降低并且过多的创建和调度Goroutine的结果导致的.
我们运行另一个去除所有的channel和routine调用的串行但是分块的代码(这段代码没有展示),它的执行时间近似于图8 ¨seq-tile¨ 的曲线,这个时间真正的体现了没有goroutine的时候的缓存命中率的效果.因此¨seq-tile¨和¨np=1¨之间的距离就是Go调度和调用的代价.
对于vp=2001,右2,003,001 个Goroutine的调用,¨np=1¨和¨seq-title¨时62.318429-43.351857=18.966572秒.因此,创建和调度Goroutin的代价对于每个处理器来说平均时\( \frac{18.966572}{2003001} = 9.46*10^{-6}\)秒,也就时9.46us.
np>1时的多核并行执行时间是小于np=1时的运行时间.但是np=1时,有goroutine的调用和调度的开销,这在串行执行的时候并不是完全需要的.我们用分块的串行时间¨seq-time¨作为基础来计算并行计算加速度.特别的,np>=1的处理器

$$ S_{np}=\frac{T_{ts}}{T_{np}} $$

\(T_{ts}\)和\(T_{np}\)分别对应串行时间和使用np处理器的并行时间.图9 显示了不同任务块大小的并行运行时间和串行时间的比较.最好的加速度vp=128的时候.对于8个处理器的时候,加速度是7.70.当vp从128增加的时候,粒度减小而Goroutine调度和调用拖累了执行过程,降低了加速度.图9(a)当vp从128降低的时候,粒度增加而且没有足够的任务块,因此降低了并发度,也降低了加速度.图9(b)展示了降低了的加速度.

##4 总结

我们展示了Go的两个问题的并行代码,并行积分和并行动态规划问题.这些代码展示了Go在编写多核并行代码的简易性.我们同样测量了代码的性能.最高的加速度分别时7.79和7.70.初始化和调度Goroutine的代价在使用一个处理器的时候只有9.46us.因为并行计算倾向于计算大块的任务,Goroutine的量级如此之小,基本上可以忽略.

引用

• [1] Shameen Akhter and Jason Roberts. Mutli-Core Programming: Increasing Performance through Software Multi-threading. Intel Press, 2006.
• [2] Edward A. Lee. The problem with threads. IEEE Computer, 39(5):33–42, May 2006.
• [3] Go Team.The Go programming language specification.Technical Report http://golang.org/doc/doc/go spec.html,Google Inc., 2009.
• [4] C.A.R. Hoare. Communication Sequential Processes.Prentice Hall, 1985.
• [5] Michael J. Quinn. Parallel Programming in C with MPI and OpenMP. McGraw-Hill, 2004.
• [6] Thomas H. Corman, Charles E. Leiserson, Ronald L.Rivest, and Clifford Stein. Introductions to Algorithms,2nd Edition. McGraw-Hill Book Company, 2001.
• [7] Sara Baase and Allen Van Gelder. Computer Algorithms: Introduction to Design and Analysis (3rd Ed).Addison-Wesley, 2000.