Wavefront algorithm Optimization

接触到了一种新的依赖解决算法问题,英文叫做wavefront algorithm,中文好像叫波前算法吧。大体思路是,对于一个X*Y数组结构的数据,当运算依赖关系是从西北角开始运算,直到覆盖所有的表项,得到最终结果的时候。每一个运算单元,都必须依赖其西,西北和北边相邻的数据才能开始运算时,其运算方式如同水波一样,逐层前进。

如下图模拟,数字增长,表示随着时间推移,运算的顺序:从1-》2-》3-》 -》7结束,完成整个数据的运算。

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

继续阅读“Wavefront algorithm Optimization”

Summary of this week

After reading the essays about recent research, the main parallelization schemes for optimization on Cell Processor are: optimize the DMA transfer (single buffering, double buffering and multi-way buffering), optimize the implementation models (how to divide the whole data block into different piece and how to connect each program structures) and optimize the get/put methods (using some prefetch mechanism such as pseudo-result, asynchronous unsafe cache and software cache).

通过几天阅读的论文情况,基本上发现了几种加速并行处理的方式:优化DMA传输方式,缓冲,双缓冲和多重缓冲;优化实现的模型,拆分程序流到不同的SPE,不同的计算模型,会得到不同的实现效果;优化数据读取的方式,比如利用预读取,虚拟结果,和异步多流水线缓存和程序缓存的方式。

继续阅读“Summary of this week”

IBM Cell SDK 装机总结

首先感慨一下这个新技术编程环境啊,是一个进入一个技术的大头,能配好环境,确实是一件不容易的事情啊。前前后后装了2-3天,才算差不多搞定了这个并行的编程环境。
具体这个东西是个啥,就不罗嗦了,google一下IBM CELL SDK就行了,下面就是总结一下配置的经验:
1.新电脑不一定都是好的,在台式机上先后尝试了CENT OS 5, FEDORA 9, FEDORA 12,都木有成功,首先是系统本身就有问题,一会检测不到声卡,1会检测不到网卡。这些问题解决完之后呢,开始装CELL SDK,又有各种依赖性的问题,各种包找不到,然后为了这个包,又去下另外一个包,然后又需要第N+1个包,折腾人啊。
2.网上的教程估计都是理想状态产生的吧?没有任何BUG?没有任何阻拦,全部都一气呵成,有点佩服。。。反正我是没有一次完全成功地按照教程弄好了的,都是查了无数的GUILD PDF和论坛才基本上弄明白的。
3.原来PS3也是可以用来编程的啊,在上面按照教程(这个教程是官方的PDF文档,还不错),装好了yellow dog linux,然后跑起来还算顺畅,可能是老PS3的缘故吧,速度不是很快,但是还是可以接受,特别是在命令行下面的时候。
4.版本统一是个很严重的问题,网上各种教程,各种版本,各种测试代码,搞得眼花缭乱,可能你按版本A装的东西,代码B就跑不起来,你还以为有问题。然后就是机器不同,装了的东西也不一样,笔记本是X86 32位的,台式是64位的,PS3算是PPC吧,真是稀奇古怪什么都有。
5.Linux还是一个必须要学的东西,特别是这几天配置环境,学会了用yum,很强大的命令,还有各种常用命令,哎。
先写这么多,有空再写