模块篇-数据结构

要点:

    理清数据流和控制流,确定模块的瓶颈,选择更优的算法,设计局部性和并行性友好的数据结构.

讨论:

    这里谈到的模块是系统中相对独立的一个模块,如Player中的视频解码器.对模块的全局思考与架构的全局思考类似,都是先要理清数据流和控制流,确定性能瓶颈,以局部性与并行性为基本的优化指导原则.所不同的是架构级的全局思考主要集中在模块间的高效协作,合理分配资源,使得系统总体的perforamnce(表现)最好.而模块级的全局思考则聚焦于如何设计高效的数据结构和算法,使得模块的perforamance(性能)最好,具有更少的资源使用或者更快的运行效率.

    以H.264 decoder为例,基本上解码流程分为几个子模块.1,bitstream parsing,2,VLD,3,Inverse Inteage Transform,4,motion compensation,5,deblock.这个流程看起来简单,但是还是涉及很复杂的运算量,尤其是motion compenstaion和deblock这两个子模块.

我们首先要把整个的数据流和控制流弄清楚.然后用全局的思维思考各个子模块的局部性,在数据结构的设计上就是要体现cache friendly.考虑合并子模块,减少不必要的计算,提高运算的重用性,精减内存,同时内存布局要考虑时间局部性和空间局部性的折中与平衡.这是个说来容易做来难的问题.因为嵌入式平台多种多样,各个CPU的结构,特别是cache的结构差别很大,没有哪一种数据结构的设计可以放之四海而皆准.所以在实际开发中,一般的做法是用宏定义多种数据结构和算法,在具体平台上再做具体测试.比方说如果用到表格驱动,在cache较小的系统上,要考虑压缩表格大小,用时间换空间.

    在数据结构的设计上的并行性的考虑主要是对SIMD的考虑,SIMD友好的数据结构使得当模块移植到有SIMD支持的CPU上时,可以容易的写出SIMD的汇编指令.ARM的趋势和PC上x86的发展历程一样,SIMD将来会成为标准配置.目前我们知道ARMv6已经支持32位的SIMD,XSCALE的WMMX支持64位的SIMD,而ARMv7的NEON指令更是支持到128位,这是不是很象MMX/SSE/SSE2的发展过程?.也许过5年后,我们也要讨论嵌入式平台的多核技术了:).到那时,并行的重要性也许超过了局部性.整个数据结构

和算法实现都要做彻底改变.让我们拭目以待吧.