CUDA N-Body模拟

这学期的多核课简直爽,之前一直想玩的cuda也玩上了。真的是相见恨晚,我见识到什么叫吊。

CUDA:

CUDA就是Nvidia GPU自带的计算平台,它是为了克服GPGPU的弱点而诞生的。我不知道ATI有什么类似的,但CUDA肯定是Nvidia的杀手锏。因为他计算能力确实强,而且编程非常灵活简单。唯一的不足是需要对硬件有所了解。当然了解并行算法也是非常重要的。

简单说下CUDA的基本原理。CUDA是牺牲单个核的主频,以核的数量来取胜。比如我笔记本的GT540M就有96个CUDA core。也就是说最多96个线程同时运行。基于这点CUDA的自然运用就是大量线程,而在CUDA里,线程的切换基本不消耗资源。问题在于如何组织这些线程。可以看basics of cuda。CUDA每个任务称为一个kernel,一个kernel包含一个Grid,一个Grid可以有很多Block,Block中可以有很多线程。而且Grid和Block可以是3维的。考虑一维情况,一个kernel的总线程是GridDim*BlockDim。而CUDA的调度单元是一个warp,一个warp有32个线程。这的意思并不是32个线程同时执行一条指令。比如我有16个CUDA core,我是先执行前16个线程,然后后16个线程。而且最近CUDA还支持指令并行,比较复杂,详见simt-architecturestack overflow.

N-Body:

N-body说白了,就是万有引力。所以计算复杂度是O(N^2),(虽然有O(Nlog(N))的算法),1000个粒子,对CPU来说已经负担很大了。所以要使用GPU。所以算法很简单,关键是怎么优化。如果是最原始的方法,每一个线程中对都计算N个粒子对其作用力,那要读取N*N次内存。所以要采用分块的方式计算,P个线程协作,每次读取P个到共享内存,然后计算P个之间的作用力,那么只需N*N/P次内存读取(共享内存很快)。然后为了计算简单,这里没有碰撞,假定粒子能穿过粒子,其作用力为 sum(ri/(ri^2+eps^2)^(1.5)) ,eps为一个小量,防止作用力无穷大。

实现:

为了简单,画图用python的matplotlib,计算用CUDA。这里涉及接口问题,可以自己了解一下。最后的效果是模拟二维的。如下图的双星也是很漂亮(初始到一段时间后)。一共4096个粒子,30帧每秒,相当于(30*4096*4096*20 / 1024 / 1024 / 1024)  = 9GFLOPS,CPU顶不住。

1.two_cluster22.two_cluster3.two_cluster1

 

科学的在主机间传输文件

长久以来,一直被如何高效的传输文件困扰。比如说打印PDF啊,在主机间传输文件啊。去打印店的话用USB可以解决,但这样还好中毒,一不小心还会把U盘忘掉,还要插拔4次,真是麻烦。况且很多情况下用不了U盘。看了我下面的方法后,U盘就剩下在没网的情况下使用的价值了。

原始:

要复制另一台主机的一个小文件,而且现在正是ssh的状态,那么可以直接cat,然后选中内容,再粘贴到本机文件。但如果这个小文件是个zip,或者其他什么二进制文件就不能直接复制了,因为不可打印字符的存在。那就用base64。简单粗暴。

 Netcat:

顾名思义,就是联网的cat。netcat(nc)被称为Swiss Army Knife of networking.我还没有深入研究过,就使用的几个命令来看,确实很吊。他也能用来传输文件。下面是简单的例子,具体选项看man。这个方法很迅速,很干净。缺点是对方是windows怎么办?

临时Web服务器:

这tm总没问题了吧,只要有浏览器就能传输文件了。python,对,python就是这么方便。我就想说,U盘存在的意义在哪?据测试,python的SimpleHTTPServer能轻松胜任10M/s的传输速率传输3G文件。更高速率还没测过。

 安全:

有时候还有满足安全方面的考虑,以及复制目录的要求,前面的几种方法好像不是很难胜任。所以需要更专业的工具。scp和sftp之前在实用ssh已经提到过。使用起来也非常方便。而rsync则是更专业的工具,可以支持增量复制。相当于在本地和远程目录间保持同步。rsync也能使用ssh的别名,更加方便了。

一定还有更吊的,发现了再更新。

链接:

  1. nc transfer file
  2. rsync

Freebase 数据库实践

Freebase是一个知识库,由人提交对现实事物的描述组成这个庞大的知识库。由于Freebase有结构化的性质(不像搜索引擎),可以通过Freebase进行知识推理。详见Wikipedia。类似的有Yago,Cyc等,我感觉还是Freebase最完善。Freebase用的是MQL来进行读写数据库。但是不清楚他们用的什么数据库架构,我觉得肯定不是简单的关系型数据库。

数据库课程的实践任务是通过Freebase的dump data用关系型数据库重新构建,当然没有在线的那么完善的功能。这些数据为24G,解压缩后大概300G。所以可以看出总共的信息量不超过24G。从数据描述也可以看出有很多重复。如下是文件的数据格式。

Topic:

理清建模的思路,必须了解freebase到底是什么。通过google的api wiki和freebase的wiki,我知道其中的节点就是Entity(Topic)。然后根据freebase的主页可以看到目前有46,236,787个Topic。所以地一件事就是找出所有Entity,通过Topic wiki,可以知道每个Topic都有一个GID和MID,GID已经不用了。所以找MID即可,如m.045c7b。这大概有8千万个,但是不是每个mid都是topic,还要满足是common.topic的type,因此去掉不满足条件的剩下4千多万个,符合实际。这也大大降低了难度。有了这些mid后,我觉得不能用字符串来作为数据库的主键,因此根据wikimid,这些mid都是32进制的数,很容易就转换为Int型,索引和空间效率都大大提高。(yt同学直接压缩字符的长度,也是吊,可以通过用户输入的部分MID,预测要输的完整MID)

Description:

有了Topic的MID,就可以以此为中心来开展工作了。首先是看看freebase里的Topic的schema。我感兴趣的是Description,Image(这里只有一个链接,还需要手动通过google取得图片,如google,后来发现Image很少,因此放弃)。通过sed直接过滤即可。

Name:

每个object在freebase里都有name,而且是各种各样的name。我们只关心type.object.name,同样用sed可以完成这个工作。大概90%的Topic都有英文name。要求是要根据输入的来查询相关的topic。这里我们要做的就是fulltext。幸运的是InnoDB,已经支持fulltext (最后解释为什么用InnoDB)。在这里我们做的一个主要优化是把这个表放到SSD上,速度就提高了10倍以上,只能说SSD吊。

Entity Relation:

不管老师的实际要求是什么,我觉得要做就得牛X。老师的几个要求意义不大,不有趣。比如找出跟Entity相关的所有object,完全没有意义,不过就是增大了数据库大小。其他要求也不提了,我就说说我们组的比较吊的一点:找出所有和指定Topic相关的Topic,并给出是什么关系。这个的挑战有两个,一个是得到所有有两个MID的元组后,去掉不是Topic的元组。二是如何表现这个联系。

第一个问题解决方法:全部找出来后,先按第一个topic的mid排序,与所有topic的排好序的mid比较,去掉不是topic的元组。再按第二个topic的mid排序,与所有topic的排好序的mid比较,去掉不是topic的元组。相当于两次sort-merge-join,复杂度为2Nlog(N)+log(M)+2(N+M)。还是能接收的,事实也证明linux的sort命令很吊。

第二个问题解决方法:采用d3.js库。可视化查询,本来想做到,按一下topic,自动平滑的扩展相关的topic,但是还是太弱,没有完成,只能不平滑的进行跳转。如下的效果。

baidu
baidu topic in freebase

Final:

根据要求和一些自己的想法,我们构建的数据库模型如下。为了存储效率,我们牺牲了一点查询效率,很多查询都需要join3个表。另外我们采用InnoDB,不可否认这在批量插入的时候确实比较慢, 比较是行级锁,但InnoDB是未来,必须好好了解其特性,而且InnoDB支持外键,为了完美,果断InnoDB。另外为了适应InnoDB和要求,还得修改一下my.cnf,可以提高缓存和排序效率。

freebase
freebase relation

最后的数据库,共935,874,169条记录,共72.1GB。各表分布如下。在这过程中,走了不少弯路,因此也产生不少中间文件,只能说多亏了linux简单的命令如sort、grep、 sed、awk、 split,在windows真不知道怎么搞,只能自己写c处理。data