[摘要] 随着大规模集成电路的迅速发展，计算机的核心CPU也得到性能的提升，无论是PC还是嵌入式的CPU都已经发展为体积小、功耗低、性能高、可靠性强架构。并且高性能应用也越来越广泛，如目前一些计算密集性的应用：音视频信号的处理、视频图像的处理、3D游戏等。这些应用对多媒体数据进行高效率、高比例的压缩，计算频度和复杂度都非常高。在多核体系时代，需要选择合适的微处理器，根据具体的平台进行改进个优化，降低运算的复杂度。本文运用posix pthread线程库对bzip2进行优化，通过对结果进行分析，和ipp库的应用比较，可以得出并行化的优越性，和理想的加速比相近。
[关键词] bzip2；多线程；intel工具；优化
1．Bzip2的概述
Bzip2 是Julian Seward开发并按照自由软件/开源软件协议发布的数据压缩算法及程序。Seward 在 1996年7月第一次公开发布了Bzip2 0.15版，在随后几年中这个压缩工具稳定性得到改善并且日渐流行，Seward在 2000年晚些时候发布了1.0版。
Bzip2比传统的gzip或者ZIP的压缩效率更高，但是它的压缩速度较慢。从这点来说，它非常类似于最近出现的其它一些压缩算法。与RAR或者ZIP等其它不同的是，Bzip2只是一个数据压缩工具，而不是归档工具，在这一点上它与gzip类似。程序本身不包含用于多个文件、加密或者文档切分的工具，相反按照 UNIX的传统需要使用如tar或者GnuPG这样的外部工具。
在有些情况下，按照绝对压缩效率来讲Bzip2不如7z和RAR格式。根据摩尔定律的持续效应，计算时间越来越少并且也变得越来越不重要，所以类似的压缩方法变得越来越流行。根据作者的说法，在目前所有已知的压缩算法中，Bzip2可以排到百分之十到十五这样最好的一类算法中（PPM），尽管它在压缩速度时大致快两倍，而解压速度有六倍快。
1.1．Bzip2基本原理
Bzip2使用 Burrows-Wheeler transform 将重复出现的字符序列转换成同样字母的字符串，然后用move-to-front transform 进行处理，最后使用哈夫曼编码进行压缩。在Bzip2中所有的数据块都是大小一样的纯文本数据块（100k-900k），它们可以用命令行变量进行选择，然后用从π的十进制表示得到的一个任意位序列标识成压缩文本。如图1。
1.2 Bzip2的应用
命令格式：
bzip2 [ -cdfkqstvzVL123456789 ] [ filenames ... ]
参数说明：
-c或–stdout将压缩与解压缩的结果送到标准输出。
-d或–decompress执行解压缩。
-f或–force bzip2在压缩或解压缩时，强制覆盖相同文件名。默认不覆盖现有文件。
-k或–keep bzip2在压缩或解压缩后，会删除原始的文件。若要保留原始文件，请使用此参数。
-q或—quiet压制不重要的警告信息。
-s或–small降低程序执行时内存的使用量。
-t或–test 测试.bz2压缩文件的完整性。
-v或–verbose压缩或解压缩文件时，显示详细的信息。
-z或–compress强制执行压缩，而不管执行的是哪个程序。
-L,-V,–license显示软件版本，许可证条款及条件。
-1 to -9 设置压缩时的区块大小。
2．基于Intel vtune的分析
提高软件性能不仅可以从提高编译执行代码入手，更多时候需要分析程序性能，找出性能瓶颈着重进行优化。Intel VTune可视化性能分析器便是Intel为众多开发者们提供的专门针对寻找软硬件性能瓶颈的一款分析工具。
统计表明，程序在运行中80%的时间都在执行20%的代码。而这20%的代码中，活动相对密集的区域便被称为HotSpot。Hot Spot不仅耗费大量时间，它也经常在以下事件中被发现：缓存不中，内存缺页，误预测分枝。这类错误往往非常隐蔽，难以发现。但只要能找出并优化这些Hot spot，便能够达到事半功倍的效果。VTune主要通过以下一系列可视化分析方案来帮助软硬件开发者们寻找Hot spot。
1.采样
以图形化方式显示程序执行的指令地址直方图，帮助确定代码中的性能瓶颈。采样数据采集完毕之后，可以按进程、线程、模块、函数或指令地址进行查看。采样只需极低的性能开销，并且不需要修改代码。通过采样图，可以方便地了解到哪些代码是处于活动密集区，如图中是按模块划分，最长的紫红色区域所对应的代码模块，代表的就是HotSpot，在开发中需要着重优化。
2.调用图
调用图包含以下信息：
（1）函数被调用次数及调用它的函数
（2）在每个函数或方法上耗费的时间
（3）函数耗费在阻塞或等待上的时间
（4）经过调用层次结构的关键路径
（5）耗费时间占总时间n%以上的函数，其中n 由用户指定。
3.计数器监视器：
“计数器监视器”可实时查看应用程序的性能。可监视200个以上可用操作系统计数器中的任何一个。用户可创建自定义的性能监视器，来监视软、硬件性能。
计数信息包括：重定向网络错误率，内存占用量，上下文切换率，CPU时间等。
看过以上三种可视化分析方案，你一定对如何使用VTune找到性能瓶颈有了自己的想法。
2.1 运用Intel Vtune分析结果
2.1.1 CALL GRAPH
本文使用Intel的工具对未优化bzip2开源软件进行分析，为了找出热点函数，以及他们函数之间调用图关系。 从图2中可以得出热点函数为mainsort函数。
2.1.2 SAMPLING
2.2 理论加速比
根据Amdahl定律
S = Ws + Wp/ (Ws + (Wp/p))
= 1/(1- 0.5186 +(0.5186/4))
= 2.5700
由计算得出，在4cpu cores上对Bzip2进行优化，理想中可以得到2.6倍左右的提高，接下来对Bzip2运用posix pthread线程库进行优化。
3．Bzip2解压缩的优化
3.1 可能的技术方法分析
对热点函数的修改、优化；应用POSIX Pthreads线程库进行多线程编程，对任务进行分解；OpenMp
Intel IPP库的应用。
3.2 对程序进行优化
(1)blocksort.c 对的 mainSort()
// for (i = 65536; i >= 0; i--) ftab[i] = 0;
/* 运用memset() 代替for循环 */
memset(&ftab[0], 0, 262148); // 4*65537
解析：memset在一段内存块中填充某个给定的值，对较大的结构体或数组进行清零操作的一种最快方法。
(2)/*-- Complete the initial radix sort --*/
//for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
/*展开循环，减少循环，进行优化 */
for (i = 1; i <= 65536; i+=4) {
ftab[i] += ftab[i-1];
ftab[i+1] += ftab[i];
ftab[i+2] += ftab[i+1];
ftab[i+3] += ftab[i+2];
3.3 POSIX Pthread线程的应用
(1)线程的创建和终止:
int pthread _create(pthread_t * pthread,const pthread _attr_t *attr,void *(*start_routine(*void)),void *arg);调用此函数可以创建一个新的线程，新线程创建后执行start_routine 指定的程序。其中参数attr是用户希望创建线程的属性，当为NULL时表示以默认的属性创建线程。arg是向start_routine 传递的参数。当成功创建一个新的线程时，系统会自动为新线程分配一个线程ID号，并通过pthread返回给调用者。
void pthread _exit(void *value_ptr);调用该函数可以退出线程，参数value_ptr是一个指向返回状态值的指针。
(2)线程控制函数
pthread _self(void);为了区分线程，在线程创建时系统为其分配一个唯一的ID号，由pthread _create()返回给调用者，也可以通过pthread _self()获取自己的线程ID。
Int pthread _join (pthread - t thread , void * *status);这个函数的作用是等待一个线程的结束。调用pthread _join()的线程将被挂起直到线程ID为参数thread 指定的线程终止。
int pthread _detach(pthread _t pthread);参数pthread代表的线程一旦终止，立即释放调该线程占有的所有资源。
(3)线程间的互斥
互斥量和临界区类似，只有拥有互斥量的线程才具有访问资源的权限，由于互斥对象只有一个，这就决定了任何情况下共享资源（代码或变量）都不会被多个线程同时访问。使用互斥不仅能够在同一应用程序的不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。Linux中通过pthread _mutex_t来定义互斥体机制完成互斥操作。具体的操作函数如下：
pthread _mutex_init(pthread _mutex_t *mutex,const pthread _mutexattr_t *attr);初使化一个互斥体变量mutex，参数attr表示按照attr属性创建互斥体变量mutex，如果参数attr为NULL，则以默认的方式创建。
pthread _mutex_lock(pthread _mutex_t *mutex);给一个互斥体变量上锁，如果mutex指定的互斥体已经被锁住，则调用线程将被阻塞直到拥有mutex的线程对mutex解锁为止。
pthread _mutex_unlock(pthread _mutex_t *mutex);对参数mutex指定的互斥体变量解锁。
(4)线程间的同步
同步就是线程等待某一个事件的发生，当等待的事件发生时，被等待的线程和事件一起继续执行。如果等待的事件未到达则挂起。在linux操作系统中是通过条件变量来实现同步的。
pthread _cond_init(pthread _cond_t *cond,const pthread _cond_t *attr);这个函数按参数attr指定的属性初使化一个条件变量cond。
pthread_cond_wait(pthread_cond_t *cond, pthread _mutex_t *mutex);等待一个事件（条件变量）的发生，发出调用的线程自动阻塞，直到相应的条件变量被置1。等待状态的线程不占用CPU时间。
pthread_cond_signal(pthread_cond_t *cond);解除一个等待参数cond指定的条件变量的线程的阻塞状态。
通过建立FIFO QUEUE，使得输入数据进行分块时，按序放入在队列中，数据的一致性，而cpu在对每个block进行bwt算法时，可以并行进行。如消费者和生产者的关系，当某cpu运行完某block后，便继续从queue中读取block，而cpu运行完bwt后，便把压缩好的block按序写入另个队列中，从而保持前后数据的一致性。从图中可以看出并行算法的实现思想，通过posix pthread线程库进行多线程编程，使程序并行化，提高了程序的解压缩效率。
3.4 优化结果
bzip2 pbzip2
实际加速比：3.453/1.466 = 2.357
1.591/0.697 = 2.283
3.5 Intel profile分析
3.5.1 Intel profile简介
英特尔线程档案器有助于调整并提高多线程应用程序的运行速度，从而使代码在英特尔多核处理器上的性能得到优化。线程档案器可同时显示并发视图和时间轴视图，这有助于查看哪部分代码适合并行处理以及应用性能问题源于何处。
3.5.2 Intel profile运行结果
运用profile进行分析，可以得出线程的负载基本平衡，充分利用了cpu的资源。如图9，图10。
3.6 Ipp库的应用和比较
（1）Intel ipp 简介
IPP（Integrated Performance Primitives）是Intel公司推出一个跨平台、高性能的多媒体函数库，发展至今已经发展到6.0版本。他提供的函数功能调用可广泛应用于多媒体领域，包括信号处理、图像处理(如JPEG)、视频编解码(例如MPEG-4、H.263)、音频编解码、语音识别和计算机视觉等。
（2）Ipp_bzip2的运行结果
ipp_bzip2加速比： 3.453/2.398 = 1.440
1.591/1.302 = 1.222
通过对ipp的应用，以及结果相应比较，可以看出优化的效果的优越性。
4．结束语
本文通过对Bzip2解压缩程序进行应用和分析，应用Intel Vtune工具对bzip2进行采样分析，得到热点函数和相应的调用关系。从而对bzip2的hot pot进行优化，通过串行和并行的优化，运用posix pthread线程库进行多线程编程，对解压缩任务进行分解、从而提高cpu资源的利用率，并运用Intel profile工具对负载平衡进行测试。最后应用Intel ipp的sample中的ipp_bzip2程序，和优化结果进行比较，得到该程序优化的优越性。
参考文献
[1] 多核系列教材编写组 著 多核程序设计[M]. 北京: 清华大学出版社, 2007.
[5]M. Burrows and D.J. Wheeler .A Block-sorting Lossless Data Compression Algorithm[J]. 1994
[6]《多核课程的教学指导手册》
|
