面向多核CPU的高通量数据分析算法研究与实现开题报告

1. 研究目的与意义（文献综述）

高通量测序技术的发展对生物医学研究产生了重大影响，使得生物医学研究从试验驱动转变为数据驱动，然而海量的数据分析任务也为高通量技术广泛应用带来了新的挑战。[1][2]一台高通量测序仪一次运行可以测量600个人的全基因组信息，数据量达到1.8tb。目前常用的数据分析软件在8核cpu的服务器上处理这些数据需要10天左右的时间，无法满足实际应用需求。

由于散热技术和硬件生产技术无法满足提高处理器频率对功耗的设计要求，现代处理器的频率近似停滞。处理器硬件生产商主要通过多核[3]和向量化[4~5]等技术来提高处理器的性能。多核技术是采用在同一个芯片上集成多个核心的解决方案来提升cpu的处理性能。多核cpu的核相互独立，每一个核有独立的硬件单元，可以同时执行多条指令。[6]向量化技术指的是增加寄存器的宽度和指令的宽度来同时处理多个数据。多核和向量化技术的出现提升了处理器的执行能力。通过稍微降低频率，现在的散热技术能够满足处理器对功耗的需求。绝大多数现代处理器，如x86多核cpu、arm多核cpu、gpu及dsp等，都已经采用了多核技术和向量化技术。[7]多核和向量化的出现满足了应用对计算能力的需求。

虽然现代多核cpu都具有256位以上的指令宽度并利用流水线技术[8]在底层的指令上实现了并行，但是传统的高通量测序分析软件无法充分的利用指令宽度以及多核资源[9]。openmp [10-12]是一套适用于多核处理器的编程接口，旨在简化并行程序的开发。使用openmp开发并行程序无需关心线程的分配、同步、管理、调度、负载平衡等诸多并行化的细节问题[13]。使用openmp开发的并行程序在不支持openmp的平台上也能简单的转换成串行程序执行，具有良好的可移植性。[14]avx2（advanced vector extensions 2）是intel在haswell架构之后引入的对于sse[15]（streamingsimd extensions）和avx的扩充向量化指令集，可以通过其提供c/c 编程接口方便的实现simd（singleinstruction multiple data）达到数据并行，充分的利用现代cpu的指令宽度来提升程序的运行效率。

2. 研究的基本内容与方案

该研究的目的主要是针对高通量测序分析中使用的软件进行优化，提升数据分析的效率。现在使用的很多高通量测序分析软件并没有使用并行和向量化技术，在性能上还有很大的提升空间。使用OpenMP和AVX2对现有的高通量测序软件进行性能优化是本研究的主要内容。

目前拟采用的技术方案是先使用gprof、perf等性能分析工具对现有的高通量测序分析软件进行热点分析，找出时间开销大的代码段，针对语句读写依赖、会引起大量缓存不命中的数据结构以及开销大的除法等运算符进行优化。再使用OpenMP的预编译指令“#pragma omp parallel”将高通量测序分析软件中的热点for循环进行拆分，分配给多个线程同时执行，充分利用多核资源提高数据分析速度。再使用AVX2指令集提供的C/C 编程接口对热点的累加或累乘操作进行向量化优化。现代CPU进行一次整型加法需要4个时钟周期，而访问一次内存需要超过200个时钟周期，访问一次L3大概需要40个时钟周期，访问一次L2大概在二十个时钟周期内，访问一次L1大概需要不到十个时钟周期在具有256位指令宽度的CPU上使用SIMD指令可以将内存中8个整型数据一共256位一次性传输到CPU的寄存器内进行累加计算，大幅减少了访问内存和高速缓存的次数，能有效的提高程序运行速度。

3. 研究计划与安排

(1)2016/1/11—2016/1/22：查阅参考文献，明确选题；

(2)2016/1/23—2016/3/7：进一步阅读文献，并分析和总结；确定技术路线，完成并提交开题报告；

(3)2016/3/8—2016/4/26：需求分析，算法或系统设计，分析、比较或实现等；

4. 参考文献（12篇以上）

[1]宁康,陈挺. 生物医学大数据的现状与展望[j]. 科学通报,2015,z1:534-546.

[2]王兴春,杨致荣,王敏,李玮,李生才. 高通量测序技术及其应用[j]. 中国生物工程杂志,2012,01:109-114.