ggaaooppeenngg

为什么计算机科学是无限的但生命是有限的

今天hack标准库里的debug/elf,里面有一段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// A Section represents a single section in an ELF file.
type Section struct {
SectionHeader

// Embed ReaderAt for ReadAt method.
// Do not embed SectionReader directly
// to avoid having Read and Seek.
// If a client wants Read and Seek it must use
// Open() to avoid fighting over the seek offset
// with other clients.
io.ReaderAt
sr *io.SectionReader
}

这个结构很特别的一点是为了能够只使用SectionReader的ReadAt方法而不使用其他方法防止Seek出现竞争问题把一个interface io.ReaderAt包含了进来.
io.ReaderAt是包含ReadAt方法的interface,以此目的来达到屏蔽其他方法的目的.如果真的要使用Read+Seek需要另外再调用Open函数.

1
2
3
// Open returns a new ReadSeeker reading the ELF section.
func (s *Section) Open() io.ReadSeeker { return io.NewSectionReader(s.sr, 0, 1<<63-1) }

这里可以看到就是new了一个SectionReader出来用,这样就防止了竞争的问题.

实现的基础就是私有结构的方法是不暴露的,而共有借口的方法是可以暴露的,这样怎么做到呢?
我把代码做了一个抽象,写了一个demo如下.

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

package main

import (
"fmt"
)

type S struct {
MethodsMask
i Implementer
}

func NewS() *S {
s := new(S)
s.MethodsMask = s.i
return s
}

type MethodsMask interface {
F1()
}
type Implementer struct {
}

func (i Implementer) F1() {
fmt.Println("F1")
}

func (i Implementer) F2() {
fmt.Println("F2")
}

func main() {
s := NewS()
s.F1()
}

这个程序运行的结果就是F1,注意最关键的部分就在于函数NewS.
把实现者赋值给了接口,因为接口是公开的,所以对应的方法就变成共有的了.
而除此之外的方法还是不能被调用.这样就把一个实现者裁剪了.
当然了,这样的裁剪主要还是为了Seek的竞争.

我觉得适用的场景就是两个借口的并集构成了一个结构体的方法,但是这两个借口泾渭分明的时候就可以这样做.
就像标准库里面分成了io.ReaderAtio.ReadSeeker一样.

很意外地在九月底结束了在阿里的实习,五个月的时间的确收获了很多.其中被实习离职然后惨淡度过十月份先按下不表.主要想总结一下自己第一次工作之后
对于整个过程的思考.

当初兴冲冲的来到内核组,的确是因为觉得搞内核很厉害,感觉很有前途,所以充满期待地就来了.

先对工作做一个总结吧.第一个任务就是在ksplice [1] 上面搭建一个热升级补丁的工具,当然通过这个主要是使用了一些RPC的调用,在多个主机上面制作热升级的补丁,完成了一个简单的小型分布式系统,当然很简单就是,完全是一个单点的架构.这当中看了一个MIT公开课的讲义,算是一个初体验吧,也算是揭开了分布式系统的面纱,不再感到那么神秘.之后开始接触Bcache [2] ,这个做在内核态中的块设备缓存,当然这个部分对于内核初学者来说的确很难看懂,其中C语言的知识也好,内核的知识也好都不得不恶补了很多,基本上市面上那些带缩写的内核的书籍我都看了个遍,然而深入度还是欠缺.这段时间基本没干什么活,主要是学习,也过得比较轻松.最后是参与到libvirt[3]/QEMU[4] 这一套东西里面,主要是做了一下IO路径的切换,从QEMU->分布式网络存储转化为了QEMU->vhost-blk->Bcache->分布式网络存储的一个热迁移方案的解决,这里面主要是做了一些C的用户态的工具,熟悉了一下C语言,也开始了解了虚拟化的一些内容,当我正在准备从最基础的 vring [5] 部分从里往外看的时候我离开了阿里.

公司内部的一些事情不是我想说的重点.然而失业的这段时间也是疲于奔命,一个是重新找实习还有一个就是做点兼职填补一下经济空白.之前工作的时候也是上完班就回来看看书补补内核的知识,或者看看B站虚度光阴.好像没有碰到一个契机来反思自己.

总结的说,实习的这段经历让我感到失落,工作本身磨灭了我对编程的热情,我不太能总结,但包括了一些因素.首先是工作本身很乏味,不管是作热升级补丁也好,参与热迁移的方案也好,都是在做工具,但是在我眼里,做工具只是一个时间问题,我希望这个过程有一定程度是个未知数,是一片可以探索和发现的领域,然后工作却让我感觉按部就班做完就好了的颓废感.这一点让我感觉工作本身成为了一件机械性的重复性的劳动.

其次是不管是libvirt也好QEMU也罢或者是Bcache这些东西,都是fork出来的,很多东西成为了组内的问题,不再变得open了,也就是说很多问题的确只能问组里人可能才能知道,因为组里的分支和上游还有蛮多区别的.我自己还是一个蛮有自信解决问题的人,但是这样导致一个很糟糕的情况是,当我们做的东西不open的时候,我们讨论问题的范围也会缩小,也就是说我问问题的话只能问组里的人,因为很多改动都是为了适应业务的需求,而且内部的代码拿出去问也的确不可能.而且组里的人都有工作都很忙,可能一些比较直接的问题比较好回答,具体的问题还是要靠我自己探索,这样我就感觉自己陷入了一个死循环.让我感觉自己的活动范围瞬间小了很多.当然这也跟我涉及东西的确有点复杂有关.

还有就是一些零碎的东西了,我记得有一次和师兄讨论问题,主要是在跟我讲分布式存储上加缓存的业务的时候,后面有个人说”讨论这么热烈,不就是个实习生么”,当时我听在耳里,嘴上没有说什么,心里却五味杂陈.当时我想,换句话说在大部分人眼里我只是个实习生罢了.写到这里也是感觉自己不够争气呀.

这是我实习的一些感受.我对比了一下我在学校的状态,感觉有些不同.

首先是我已经修完所有的课程了,有大把空余的时间钻研自己感兴趣的东西,这也是我为什么单独写了一个OJ,从头到尾自己维护的原因,而且我把写在我的简历最前面是因为这个过程是我觉得最有意思的一件事情,从未知到已知,不断地请教别人,不断地尝试和寻找解决方案,最开始做沙箱的那段时间我是快乐的,因为我编程的同时感觉收获很大,而且这个东西从头到尾都是我自己写的,所以我写起来也很舒服,不像上班的时候一样光看代码就要看半天.直到后来把上层的WEB的内容写了个大概我的热情就开始渐渐消减,然后我又开始寻找新的可以钻研的东西,做沙箱的过程中让我真正体会到真正了解操作系统多么重要,不是调用那些系统调用这么简单,我记得有一次发邮件和别人讨论,因为当时那个人是也做了一个类似的东西,但是没有那么完全,我借鉴了他的代码,后来发邮件和他聊,他也在做类似的东西,但是是闭源的不方便拿给我看.但是他跟我聊了一些他的手段提到了 docker [6] 也提到准备利用 namespace[7]/cgroup[8] 做一个类似 docker 的沙箱的想法,当时我就觉得”卧槽,确实牛逼,这些我都不懂,我还有很长的路要走呀”.

还有就是之前提到的,我可以自由地在segmenfault或者stackoverflow这些网站上面问问题,因为代码都在那,有问题就可以直接问就是了.我感觉大学学到东西最多的地方的确就是网络.这是说我自己写着玩的东西,如果一个项目和 upstream 越走越远的话,很产生很多的问题,而这些问题只会变得越来越私有,不再适合公开讨论了.

另外就是自由度上,在学校随便睡到几点,起来之后开会儿书,更新几段代码再打打球一天就过去了轻松无比.然而在学校我也感受到了一个瓶颈.那就是学而不精.
很多东西想深入却没有门道,就举 Bcache 这个例子吧,不在工业条件下根本没办法研究这些内容,好歹有两块硬盘吧,一块得是快点的SSD才有效果吧,又或者是简单的搭个集群,这件事一个笔记本很难体验到,开个虚拟机都卡的飞起.还有就是没有一个工业环境,很多时候不知道一个更大数量级的业务到底是什么情况,还是只能用一台服务器起个进程跑服务的状态.这都是制约,所以这也促使着我想去公司看看.因为我本身就打算本科毕业就工作,所以偏纯科研的内容我的确没有什么准备.特别是大数据现在这么火的时代,我反倒不太喜欢去搞数据挖掘什么的,我更对底层支撑的分布式服务,如何让整个分布式的服务器更好更快地支撑上面的运算需求更感兴趣.

除此之外,在学校经常在社区里面说话什么的, github也经常更新(当然进了公司以后才发现github很绿并没什么卵用).但是毕竟做程序员就是搞技术活的,口碑也很重要.光说不练假把式,代码亮出来几斤几两就知道了.当然这里面还有一层自我满足的东西在里面,自己写的东西有人观赏,甚至有人学习,更加的是有人用,都是很有成就感的一件事情.而且成就感这东西的确占了我对编程兴趣的一大半,这个东西在公司就感觉不到.那个时候就是一顿恶补,但是内核部分的代码还是不能很好的掌握,自己也懒得更新博客,因为一个模块都没有仔仔细细地搞明白,的确没什么好写的,写学习总结又太懒.更新github的代码更是别提了,基本没闲情了.

最后做一下总结,学校的自由让我保持着对编程的热情,但是有限的条件和机会让我感觉不到快速进步的空间.然而公司虽然给了很大的环境却让我陷入了一个枯燥和禁闭的状态.

在这里我对工作又有了一个新展望: 开放,探索,自由.

索引:

最大子数组之和问题是一道经典的面试题.
这里对这个问题的迭代解法做一个证明.

先给出C的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int max_sub_array(int* arr, int len
{
int temp = 0, max = arr[0];
int i;
for(i = 0; i < len; i++) {
temp += a[i];
if(temp < 0) {
temp = 0;
}
if(temp > max) {
max = temp;
}
}
return int
}

算法的思路是这样的:

所以用\(temp\)存储\(A[p..r]\),只要\(A[p..r]\)求和是负数的话,那么下一个\(A[r+1]\)开始,\(temp\)重新清零开始求和,只要\(temp\)比和大,就更新这个和.

这个算法的思路证明如下:

对于\(A[p..r]\),如果\(A[p..r]\)求和为负数的话,那么数组\(A[p..r+1]\)的最大子数组肯定不会是\(A[p..r+1]\)
因为\(A[p..r] + A[r+1] < A[r+1]\)的.

对数组的所有元素进行一个划分,对于\(A[i]\),如果能够使得 \(temp>0 and temp+A[i]<0\),那么这个元素就是一个划分的边界.
这样就会形成很多个区间.

接下来要证明

  1. 最大子数组一定在划分块内
  2. 一定存在首元素是划分块的首元素的最大子数组

对于第一个点,假设有一个元素\(A[i]\)在划分区间\(A[p..r]\)内,那么\(A[p..i-1] > 0 and A[i..r] < 0\)一定成立,这个可以用反证法.

如果一个最大子数组横跨了这些区域假设这个最大子数组为\(A[i..j]\),并且\(A[r]\)最大子数组中最后一个处于分界的元素.
那么\(A[i..r] < 0\)一定成立,所以最大子数组不可能有这段部分,因此最大子数组只会处于划分内.

对于第二点,假设\(A[i..j]\)处于划分\(A[p..q]\)当中,那么\(A[p..i-1]+A[i..j] >= a[i..j]\)一定成立,所以最大子数组
的开始元素也是划分的开始元素.

综合起来就能证明这个算法的正确性.

实际上抽象地理解就是把数组划分成了恰好多加一个元素和就变负数的N个划分,而最大子数组不可能超过这个划分,
因此在计算划分当中的最大值就能得到最大子数组.产生一个新的划分的时候如果碰到负数肯定是独自成立了一个划分,如果碰到正数
就会作为新的划分的开始,所以这个划分的第一个元素会成为最大子数组的第一个元素,然后遍历每次包含一个元素以后的和就能确定最大值,最终获得最大子数组.

普通配置

安装 arp-scan,可以通过ARP扫描获得IP到MAC的映射表.

执行 arp-scan --interface wlan0 --localnet(需要root权限),interface对应的是接入的网卡,这里我连接的是WIFI,所以选择wlan0.
结果是一堆表

1
2
3
4
5
6
7
8
9
Interface: wlan0, datalink type: EN10MB (Ethernet)
Starting arp-scan 1.8.1 with 256 hosts (http://www.nta-monitor.com/tools/arp-scan/)
192.168.0.1 50:bd:5f:5f:02:be (Unknown)
192.168.0.100 8c:21:0a:7f:1a:bf (Unknown)
192.168.0.102 74:e5:43:db:f4:81 (Unknown)
192.168.0.107 74:51:ba:c5:6f:4f (Unknown)
192.168.0.103 8c:be:be:9f:c7:ec (Unknown) 192.168.0.114 b8:27:eb:63:d8:74 (Unknown)
192.168.0.108 f8:a4:5f:ef:a4:b2 (Unknown)

在里面没有看到名字,但是树莓派的MAC都是b8:27:eb开头的.
所以可以执行arp-scan --interface wlan0 --localnet | grep b8:27:eb就可以看到树莓派对应的IP.

ssh在树莓派上是默认开启了的,这个时候可以通过ssh pi@ipssh到树莓派上,密码是默认的__raspberry__.

这是在没有配置静态IP的情况下,如果不想每次都通过动态IP登陆的话,可以设置树莓派的静态IP。

通过编辑 /etc/network/interfaces 可以看到这样一行iface eth0 inet dhcp,这表示以太网的ip是动态分配的,
现在把这行换成iface eth0 inet static然后再进行我们的IP配置.

1
2
3
4
5
6
7
8
9
10
11
12
13
...省略
iface eth0 inet static
#my static IP
address 192.168.0.118 // 自己设置的静态IP
#my gateway IP
gateway 192.168.0.1 // 网关 netstat -nr 可以通过路由表查看网关.
netmask 255.255.255.0 // 子网掩码 可以通过ifconfig 查看子网掩码,一般都是255.255.255.0
#my network address "family"
network 192.168.0.0 // 表示网段. netstat -nr 也可以看到.
broadcast 192.168.0.255 // 表示广播网络. ifconfig可以查看,最后一项一定是255.

...省略

比如我不想记住这个IP,可以编辑/etc/hosts文件,来给IP绑定一个名字.

1
192.168.0.118 pi

这样以后就可以通过 ssh pi@pi 来登陆树莓派了.

高潮来了:

之前配置树莓派的时候把静态IP设置了,然后来北京实习之后没有带显示屏,所以只能通过一根网线来操作,网线还是我从公司上拔下来的.
其实奇淫巧计还是蛮多了,一种是直接把SD卡拔下来在电脑上改文件,但是之前我以为是操作系统崩掉了,所以傻逼一直想连接上去,最后发现这个地址: (http://embeddedday.com/projects/raspberry-pi/basics/direct-connection-to-pc

真是たすかた呀,boot/下面的cmdline.txt最后添加一段ip设置,可以设置一个静态IP(当时只是想连接上去,其实直接改网络配置文件就好了)然后把网线和树莓派直连ssh上去,最后连接上去了,然后果断把我的静态IP配置回去,我又买了一个USB无线网卡,记录一下无线配置.

1
2
3
4
5
6
7
8
allow-hotplug wlan0
auto wlan0
iface wlan0 inet static
address 192.168.99.226
netmask 255.255.255.0
gateway 192.168.99.1
wpa-ssid "id"
wpa-psk "password"

之前一直小看了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_draftstrue*即可)。

  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)这个函数实现的,这个函数计算从startend之间的矩形面积.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.