毕业论文：数据密集型应用访存特征分析与优化

大学2012届本科毕业论文
数据密集型应用访存特征分析与优化

Memory access feature analysis and optimization
on data-intensive applications
所 在 学 院： 计算机科学与技术学院
所 学 专 业： 软件工程

摘要
随着移动互联网的到来，移动终端作为移动互联网时代的主要信息设备载体也将成为人们的必然选择。但是移动终端靠电池驱动，因此对能耗要求极其严格。因此对芯片功耗的优化成为当务之急。大部分研究表明片上存储往往是芯片的主要能耗来源，而访存与片上存储的功耗与密集型数据访存密切相关。
本研究的主要内容包括对数据密集型应用的访存进行分类，并根据不同访存分类的特征进行分析与优化。重点是访存分类中对动态堆数据（heap）的访存行为特征的分析与优化。
通过SimpleScalar模拟器来模拟系统cache访存。包括对SimpleScalar源代码中与访存有关代码的修改，获取想要得到的cache具体访存数据。用SimpleScalar运行基准测试程序mibench和SPEC2006获取数据的访存信息统计，分析其在时间和空间两个维度上所表现出的特性、并结合Linu*性能剖视工具（如gprof），进一步探索访存特征与程序语法树结构的耦合关系，以此作为访存与片上存储优化依据，从而有效降低功耗。



关键词：访存；动态对数据；统计；优化；功耗


Abstract
With the arrival of the Mobile Internet，mobile terminal as Mobile Internet’s main information equipment carrier will also be the inevitable choice of people. However mobile device are mostly battery-powered, so it is very strict in energy consumption. So the optimization of the chip power consumption has become a top priority. Most studies indicate that the on-chip store and memory accesses are always the main energy consumption of the chip. However the on-chip store and memory accesses power consumption is closely related with intensive data.
This research mainly include the classification of data-intensive application for memory access , and do some analysis and optimization according to the different characteristics .We focus on the dynamic data in memory access ,such as heap data, analysis and optimize its memory access behavior and characteristics.
We use the SimpleScalar to simimulate the system cac
……（新文秘网https://www.wm114.cn省略2495字，正式会员可完整阅读）……　
源的重要性
如今对计算机功耗的节约要求越来越高，上至高性能的超级计算机下至嵌入式系统在对功耗节约方面的要求都在不断提高。而且许多嵌入式系统不但要考虑性能的提高，同时还要考虑对功耗的节约。鉴于这些制约因素，系统架构师们不得不重新考虑一般与特定系统结构的设计。考虑到内存层次结构，按照目前的标准是使用非常普遍的缓存结构，将内存分层次引用，分成指令访存和数据访存两种类型。然而不同类型的数据有不同发访存特征，表现出不同的访存位置特性。即使给定的数据集在不同的程序阶段也会表现出不同的特征。片上高速缓存会消耗占整个芯片40%的功耗[1]。针对具体数据的访存情况对缓存设计进行优化可以更好的提高访存性能同时降低功耗。
根据研究表明，平均35%的功耗在数据高速缓存中可以减少，此外，可以通过有选择性的保存、多端口、语义预测等方式进行优化平均节约cache的46%的功耗[2]。
2.2 数据特征
根据传统的编程语言来说，一个特定的处理器体系结构通常将虚拟地址空间分成数个非重复的语义地区：指令、静态数据和动态数据区域。如下图所示虚拟内存地址的分配情况，系统虚拟地址被划分成三部分，global，heap，stack三部分分别存放在图中Te*t，Data，Stack三个区域其中global数据是不变的，heap部分主要是程序运行过程中动态申请的内存空间运行过程中随着动态数据的申请和释放大小也是动态变化的，Stack部分也是程序运行时动态变化的。

图2-1 系统虚拟地址空间不同类型数据划分情况

下面以MiBench中的dijkstra基准测试程序为例来进行讲解：
在dijkstra函数的大概框架如下：
(1) _NODE，_QITEM结构体变量的声明
(2) 全局变量的定义：nt AdjMatri*[NUM_NODES][NUM_NODES];
int g_qCount = 0;
NODE rgnNodes[NUM_NODES];
int ch;
int iPrev, iNode;
int i, iCost, iDist;
(3) 函数定义：print_path，enqueue，dequeue，qcount, dijkstra等函数的定义；其中在enqueue中有如下情况：
void enqueue (int iNode, int iDist, int iPrev)
{
QITEM *qNew = (QITEM *) malloc(sizeof(QITEM));
……
}
(4) 主函数main的定义；
int main(int argc, char *argv[])
……
现在对dijkstra程序的代码进行分析，程序的代码部分保存在图2-1中的Code模块中，函数全局变量，即global变量保存在Initialized vars和Uninitialized vars模块中，函数enqueue中的或其他函数中动态申请的变量保存在heap块中，而主函数调用其他函数时所需要的空间则分配在stack模块中。其中heap模块会随着动态数据的申请和释放变化，stack也会随着函数的调用和释放动态变化。
在编译时分配的全局变量和只读数据组成静态数据，动态数据可以进一步分解成堆栈，存储在运行过程中创建子程序调用激活记录堆动态分配功能，如C语言中的malloc（），这些语义区域的创建根据不同的目的现实不同的特征，也可以利用专门的硬件来实现。
在访存的数据区域（global，heap，stack）中heap数据占访存次数比例最大[1][2]，即heap_data应用最密集，因此我们对密集型数据访存优化的重点变放在对heap_data的分析和优化上。

本章小结：
本章中通过阅读大量文献资料，了解前人所做的工作，进而更加明确本次研究的研究对象及研究目的。站在前人的肩膀上去做下一步的研究创新。


第3章 实验平台
在上一章中主要介绍了实验前的相关工作，通过阅读大量的文献，了解了很多当前的研究情况。明确了实验目的，在前人的基础上做进一步挖掘创新。了解目前科研情况明确目的之后下一步就要开始我们的具体工作了，本章主要介绍本次实验的实验平台，例如SimpleScalar的安装以及其他实验平台的详细介绍，通过实验平台对整个实验有个大致的了解。
3.1 SimpleScalar
本次研究中，SimpleScalar是我们的重要实验平台之一，在本次研究中我们通过SimpleScalar来对程序进行模拟和数据统计。
3.1.1 SimpleScalar介绍
SimpleScalar是美国威斯康星大学的Todd M. Austin开发的一个用于构建处理器模拟的open source系统软件框架，它是一个提供用于模拟存储器分层体系，CPU和缓存等计算机体系结构的工具集。它也可以模拟一个程序在某种体系结构机器上的具体执行过程，给出该体系结构的功能和性能参数[9]。
SimpleScalar 被广泛应用于研究和教学，在2000 年，全球顶级计算机架构会议中有超过1/3 的论文都使用了SimpleScalar 作为实验的评估工具[9]。在本实验中我们同样也是以SimpleScalar作为实验评估工具来对密集型数据展开研究的。所以在进行研究之前我们要先要能够对SimpleScalar熟练使用，以及完成对SimpleScalar进行大量修改以达到我们的实验要求。
计算体系结构研究者和处理器设计者需要在真正的硬件实现前对其设计进行性能及功耗的验证评测。SimpleScalar工具集满足了这种需求，为计算机系统性能及功耗分析、软硬件协同验证、处理器微体系结构建模提供了有效的支持。SimpleScalar既提供了简单的功能模拟器，同时也提供了模拟超标量处理器微体系结构的乱序(OutofOrder)执行的性能模拟器。其乱序模拟器支持动态指令调度、指令的乱序执行、指令的预测执行和分支预测等现代微处理器的特性，而且还提供了一系列的工具，包括CrossCompiler(交叉编译器)、基准测试（Benchmark）、调试工具、流水线（pipeline）跟踪器等，为计算机体系结构研究提供了全面的支持。目前它已经支持ARM、*86、PISA等指令集.由于SimpleSalar是开源(opensource)的，所以目前许多体系结构的研究和软件开发人员都选择使用它作为研究平台并不断拓展其功能。
通过分析SimpleScalar软件架构图，可以知道SimpleScalar模拟器采用了分层次模块化结构[8]。
SimpleScalar提供的是一个建模框架，其模块化和源程序可改写使得应用其建模具有很大的灵活性。不仅提供了简单的功能模拟器Sim-Safe，而且还提供了基于超标量处理器微体系结构的乱序性能模拟器Sim-outorder。下面是simulator的结构图[8]：

图3-1 simulator的结构图[8]
SimpleScalar包括多个仿真模拟器，其中包括：
sim-safe,sim-cache,sim-cheetah,sim-bred,sim-profile,sim-eio,sim-outorder和sim-fast 八个仿真模拟器。
在本次实验中主要用到sim-safe和sim-cache两个模拟器，在修改SimpleScalar时一般先用sim-safe来调试，sim-safe是SimpleScalar所有仿真器中最简单的一个功能仿真器；它进行指令错误检查，再对数据进行具体统计。在这个仿真其中加入了cache，用户可以对cache及TLB 进行设置，支持两级的cache和一级的TLB，第一级cache和TLB均分为数据和指令两部分。由于SimpleScalar是开放源码(opensource)的，所以我们通过对模拟器的修改或功能的添加便可获取我们所需要的统计。
3.1.2 SimpleScalar安装调试
由于研究需要通过SimpleScalar获取大量数据，所以首要任务便是安装SimpleScalar。由于实验平台是在linu*操作系统上的，所以首先需要安装linu*，虚拟机真机都可以，本平台是在Ubuntu10.04系统上搭建的。 众所周知，SimpleScalar的安装时间非常让人头疼的事情，因为在编译过程中会出现许多意想不到的错误，而不同的电脑又会遇到不同的问题，网上的总结也有很多不适用，本次实验也是安装了五六遍才安装成功的，现将具体安装过程总结如下:
从SimpleScalar官方网站www.simplescalar.com上下载安装源文件Simpletools-2v0.tgz、Simplesim-3v0.tar.gz、Simpleutils-990811.tar.gz、Gcc-2.7.2.3.tar.gz。

第一步 设置环境：打开系统终端，设置临时环境变量e*port HOST=i386-pc-linu*, e*port SSS=/home/bruce,(在这里bruce为本次实验所用的电脑名称)， e*port TARGET=sslittle-na-sstri*。 在home里创建simplescalar文件夹，然后将安装文件放到该文件夹里。安装fle*、build-essential、bison三个文件包，安装命令：sudo apt-get install fle* build-essential bison 。
安装Simple tools：解压simpletools-2v0.tgz 然后删掉gcc-2.6.3,tar –z*vf simpletools-2v0.tgz, rm –rf gcc2.6.3 。

第二步 安装SimpleUtils：解压文件：tar –z*vf simpleutils-990811.tar。 进入simpleutils文件cd simlpeutils-990811 但是里面有很多源代码错误需要修改，否则编不能通过。在ld中找到ldle*.l这个文件，然后讲所有的yy_current_buffer都替换成YY_CURRENT_BUFFER。之后就是configure的配置：./configure –host=$HOST –target=$TARGET –with-gnu-as –with-gnu-ld –prefi*=$SSS 之后make， make install

第三步 安装Simulator：解压文件cd $SSS, tar –*zvf simplesim-3v0d.tgz， cd simplesim-3.0， make config-pisa， make。之后可以测试simplesim的安装，输入一下代码：./sim-safe tests/bin.little/test-math。

第四步 安装GCC Cross-Compiler：这一步非常重要，大部分人都在这步出问题。我也在这步重复了三遍才完成。首先进入simplescalar文件，解压gcc-2.7.3 tar –z*vf gcc-2.7.2.3.ss_.tar.gz 然后进入gcc-2.7.2.3文件设置PATH： e*port PATH=$PATH:/home/bruce/simplescalar/sslittle-na-sstri*-bin，然后进行配置：./configure –host=$HOST –target=$TARGET -with-gnu-as –with-gnu-ld –prefi*=$SSS。 但是在文件运行之前需要对文件代码进行一些改动，否则不能编译成功。(1)将Makefile的130行结尾换成: -I/usr/include。
(2) protoize.c的第60行中，将#include改成#include。(3)obstack.h第341行将*((void**)_o->ne*t_free)++((void*)datum);改成（注意括号）
*((void**)_o->ne*t_free++)=((void*)datum);
(4)将目录patched中的文件拷贝到其他文件中，可以输入命令：
cp ../sslittle-na-sstri*/lib/libc.a ../lib/
cp ./patched/sys/cdefs.h ../sslittle-na-sstri*/include/sys/cdefs.h
cp ../sslittle-na-sstri*/lib/crt0.o ../lib/
(5) 进入gcc2.7.2.3目录中cd $SSS/gcc-2.7.2.3 , make会遇到错误在insn-output.c
中第675，750，823行为加‘\’。（注意先获取文件的写权限）
(6) objc中的sendmsg.c文件中缺少ST ……（未完，全文共38968字，当前仅显示7009字，请阅读下面提示信息。收藏《毕业论文：数据密集型应用访存特征分析与优化》）