畢業(yè)論文：數(shù)據(jù)密集型應(yīng)用訪存特征分析與優(yōu)化

大學(xué)2012屆本科畢業(yè)論文
數(shù)據(jù)密集型應(yīng)用訪存特征分析與優(yōu)化

Memory access feature analysis and optimization
on data-intensive applications
所 在 學(xué) 院： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院
所 學(xué) 專(zhuān) 業(yè)： 軟件工程

摘要
隨著移動(dòng)互聯(lián)網(wǎng)的到來(lái)，移動(dòng)終端作為移動(dòng)互聯(lián)網(wǎng)時(shí)代的主要信息設(shè)備載體也將成為人們的必然選擇。但是移動(dòng)終端靠電池驅(qū)動(dòng)，因此對(duì)能耗要求極其嚴(yán)格。因此對(duì)芯片功耗的優(yōu)化成為當(dāng)務(wù)之急。大部分研究表明片上存儲(chǔ)往往是芯片的主要能耗來(lái)源，而訪存與片上存儲(chǔ)的功耗與密集型數(shù)據(jù)訪存密切相關(guān)。
本研究的主要內(nèi)容包括對(duì)數(shù)據(jù)密集型應(yīng)用的訪存進(jìn)行分類(lèi)，并根據(jù)不同訪存分類(lèi)的特征進(jìn)行分析與優(yōu)化。重點(diǎn)是訪存分類(lèi)中對(duì)動(dòng)態(tài)堆數(shù)據(jù)（heap）的訪存行為特征的分析與優(yōu)化。
通過(guò)SimpleScalar模擬器來(lái)模擬系統(tǒng)cache訪存。包括對(duì)SimpleScalar源代碼中與訪存有關(guān)代碼的修改，獲取想要得到的cache具體訪存數(shù)據(jù)。用SimpleScalar運(yùn)行基準(zhǔn)測(cè)試程序mibench和SPEC2006獲取數(shù)據(jù)的訪存信息統(tǒng)計(jì)，分析其在時(shí)間和空間兩個(gè)維度上所表現(xiàn)出的特性、并結(jié)合Linu*性能剖視工具（如gprof），進(jìn)一步探索訪存特征與程序語(yǔ)法樹(shù)結(jié)構(gòu)的耦合關(guān)系，以此作為訪存與片上存儲(chǔ)優(yōu)化依據(jù)，從而有效降低功耗。



關(guān)鍵詞：訪存；動(dòng)態(tài)對(duì)數(shù)據(jù)；統(tǒng)計(jì)；優(yōu)化；功耗


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
……（新文秘網(wǎng)http://m.jey722.cn省略2495字，正式會(huì)員可完整閱讀）……　
源的重要性
如今對(duì)計(jì)算機(jī)功耗的節(jié)約要求越來(lái)越高，上至高性能的超級(jí)計(jì)算機(jī)下至嵌入式系統(tǒng)在對(duì)功耗節(jié)約方面的要求都在不斷提高。而且許多嵌入式系統(tǒng)不但要考慮性能的提高，同時(shí)還要考慮對(duì)功耗的節(jié)約。鑒于這些制約因素，系統(tǒng)架構(gòu)師們不得不重新考慮一般與特定系統(tǒng)結(jié)構(gòu)的設(shè)計(jì)�？紤]到內(nèi)存層次結(jié)構(gòu)，按照目前的標(biāo)準(zhǔn)是使用非常普遍的緩存結(jié)構(gòu)，將內(nèi)存分層次引用，分成指令訪存和數(shù)據(jù)訪存兩種類(lèi)型。然而不同類(lèi)型的數(shù)據(jù)有不同發(fā)訪存特征，表現(xiàn)出不同的訪存位置特性。即使給定的數(shù)據(jù)集在不同的程序階段也會(huì)表現(xiàn)出不同的特征。片上高速緩存會(huì)消耗占整個(gè)芯片40%的功耗[1]。針對(duì)具體數(shù)據(jù)的訪存情況對(duì)緩存設(shè)計(jì)進(jìn)行優(yōu)化可以更好的提高訪存性能同時(shí)降低功耗。
根據(jù)研究表明，平均35%的功耗在數(shù)據(jù)高速緩存中可以減少，此外，可以通過(guò)有選擇性的保存、多端口、語(yǔ)義預(yù)測(cè)等方式進(jìn)行優(yōu)化平均節(jié)約cache的46%的功耗[2]。
2.2 數(shù)據(jù)特征
根據(jù)傳統(tǒng)的編程語(yǔ)言來(lái)說(shuō)，一個(gè)特定的處理器體系結(jié)構(gòu)通常將虛擬地址空間分成數(shù)個(gè)非重復(fù)的語(yǔ)義地區(qū)：指令、靜態(tài)數(shù)據(jù)和動(dòng)態(tài)數(shù)據(jù)區(qū)域。如下圖所示虛擬內(nèi)存地址的分配情況，系統(tǒng)虛擬地址被劃分成三部分，global，heap，stack三部分分別存放在圖中Te*t，Data，Stack三個(gè)區(qū)域其中g(shù)lobal數(shù)據(jù)是不變的，heap部分主要是程序運(yùn)行過(guò)程中動(dòng)態(tài)申請(qǐng)的內(nèi)存空間運(yùn)行過(guò)程中隨著動(dòng)態(tài)數(shù)據(jù)的申請(qǐng)和釋放大小也是動(dòng)態(tài)變化的，Stack部分也是程序運(yùn)行時(shí)動(dòng)態(tài)變化的。

圖2-1 系統(tǒng)虛擬地址空間不同類(lèi)型數(shù)據(jù)劃分情況

下面以MiBench中的dijkstra基準(zhǔn)測(cè)試程序?yàn)槔齺?lái)進(jìn)行講解：
在dijkstra函數(shù)的大概框架如下：
(1) _NODE，_QITEM結(jié)構(gòu)體變量的聲明
(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) 函數(shù)定義：print_path，enqueue，dequeue，qcount, dijkstra等函數(shù)的定義；其中在enqueue中有如下情況：
void enqueue (int iNode, int iDist, int iPrev)
{
QITEM *qNew = (QITEM *) malloc(sizeof(QITEM));
……
}
(4) 主函數(shù)main的定義；
int main(int argc, char *argv[])
……
現(xiàn)在對(duì)dijkstra程序的代碼進(jìn)行分析，程序的代碼部分保存在圖2-1中的Code模塊中，函數(shù)全局變量，即global變量保存在Initialized vars和Uninitialized vars模塊中，函數(shù)enqueue中的或其他函數(shù)中動(dòng)態(tài)申請(qǐng)的變量保存在heap塊中，而主函數(shù)調(diào)用其他函數(shù)時(shí)所需要的空間則分配在stack模塊中。其中heap模塊會(huì)隨著動(dòng)態(tài)數(shù)據(jù)的申請(qǐng)和釋放變化，stack也會(huì)隨著函數(shù)的調(diào)用和釋放動(dòng)態(tài)變化。
在編譯時(shí)分配的全局變量和只讀數(shù)據(jù)組成靜態(tài)數(shù)據(jù)，動(dòng)態(tài)數(shù)據(jù)可以進(jìn)一步分解成堆棧，存儲(chǔ)在運(yùn)行過(guò)程中創(chuàng)建子程序調(diào)用激活記錄堆動(dòng)態(tài)分配功能，如C語(yǔ)言中的malloc（），這些語(yǔ)義區(qū)域的創(chuàng)建根據(jù)不同的目的現(xiàn)實(shí)不同的特征，也可以利用專(zhuān)門(mén)的硬件來(lái)實(shí)現(xiàn)。
在訪存的數(shù)據(jù)區(qū)域（global，heap，stack）中heap數(shù)據(jù)占訪存次數(shù)比例最大[1][2]，即heap_data應(yīng)用最密集，因此我們對(duì)密集型數(shù)據(jù)訪存優(yōu)化的重點(diǎn)變放在對(duì)heap_data的分析和優(yōu)化上。

本章小結(jié)：
本章中通過(guò)閱讀大量文獻(xiàn)資料，了解前人所做的工作，進(jìn)而更加明確本次研究的研究對(duì)象及研究目的。站在前人的肩膀上去做下一步的研究創(chuàng)新。


第3章 實(shí)驗(yàn)平臺(tái)
在上一章中主要介紹了實(shí)驗(yàn)前的相關(guān)工作，通過(guò)閱讀大量的文獻(xiàn)，了解了很多當(dāng)前的研究情況。明確了實(shí)驗(yàn)?zāi)康�，在前人的基礎(chǔ)上做進(jìn)一步挖掘創(chuàng)新。了解目前科研情況明確目的之后下一步就要開(kāi)始我們的具體工作了，本章主要介紹本次實(shí)驗(yàn)的實(shí)驗(yàn)平臺(tái)，例如SimpleScalar的安裝以及其他實(shí)驗(yàn)平臺(tái)的詳細(xì)介紹，通過(guò)實(shí)驗(yàn)平臺(tái)對(duì)整個(gè)實(shí)驗(yàn)有個(gè)大致的了解。
3.1 SimpleScalar
本次研究中，SimpleScalar是我們的重要實(shí)驗(yàn)平臺(tái)之一，在本次研究中我們通過(guò)SimpleScalar來(lái)對(duì)程序進(jìn)行模擬和數(shù)據(jù)統(tǒng)計(jì)。
3.1.1 SimpleScalar介紹
SimpleScalar是美國(guó)威斯康星大學(xué)的Todd M. Austin開(kāi)發(fā)的一個(gè)用于構(gòu)建處理器模擬的open source系統(tǒng)軟件框架，它是一個(gè)提供用于模擬存儲(chǔ)器分層體系，CPU和緩存等計(jì)算機(jī)體系結(jié)構(gòu)的工具集。它也可以模擬一個(gè)程序在某種體系結(jié)構(gòu)機(jī)器上的具體執(zhí)行過(guò)程，給出該體系結(jié)構(gòu)的功能和性能參數(shù)[9]。
SimpleScalar 被廣泛應(yīng)用于研究和教學(xué)，在2000 年，全球頂級(jí)計(jì)算機(jī)架構(gòu)會(huì)議中有超過(guò)1/3 的論文都使用了SimpleScalar 作為實(shí)驗(yàn)的評(píng)估工具[9]。在本實(shí)驗(yàn)中我們同樣也是以SimpleScalar作為實(shí)驗(yàn)評(píng)估工具來(lái)對(duì)密集型數(shù)據(jù)展開(kāi)研究的。所以在進(jìn)行研究之前我們要先要能夠?qū)impleScalar熟練使用，以及完成對(duì)SimpleScalar進(jìn)行大量修改以達(dá)到我們的實(shí)驗(yàn)要求。
計(jì)算體系結(jié)構(gòu)研究者和處理器設(shè)計(jì)者需要在真正的硬件實(shí)現(xiàn)前對(duì)其設(shè)計(jì)進(jìn)行性能及功耗的驗(yàn)證評(píng)測(cè)。SimpleScalar工具集滿足了這種需求，為計(jì)算機(jī)系統(tǒng)性能及功耗分析、軟硬件協(xié)同驗(yàn)證、處理器微體系結(jié)構(gòu)建模提供了有效的支持。SimpleScalar既提供了簡(jiǎn)單的功能模擬器，同時(shí)也提供了模擬超標(biāo)量處理器微體系結(jié)構(gòu)的亂序(OutofOrder)執(zhí)行的性能模擬器。其亂序模擬器支持動(dòng)態(tài)指令調(diào)度、指令的亂序執(zhí)行、指令的預(yù)測(cè)執(zhí)行和分支預(yù)測(cè)等現(xiàn)代微處理器的特性，而且還提供了一系列的工具，包括CrossCompiler(交叉編譯器)、基準(zhǔn)測(cè)試（Benchmark）、調(diào)試工具、流水線（pipeline）跟蹤器等，為計(jì)算機(jī)體系結(jié)構(gòu)研究提供了全面的支持。目前它已經(jīng)支持ARM、*86、PISA等指令集.由于SimpleSalar是開(kāi)源(opensource)的，所以目前許多體系結(jié)構(gòu)的研究和軟件開(kāi)發(fā)人員都選擇使用它作為研究平臺(tái)并不斷拓展其功能。
通過(guò)分析SimpleScalar軟件架構(gòu)圖，可以知道SimpleScalar模擬器采用了分層次模塊化結(jié)構(gòu)[8]。
SimpleScalar提供的是一個(gè)建�？蚣�，其模塊化和源程序可改寫(xiě)使得應(yīng)用其建模具有很大的靈活性。不僅提供了簡(jiǎn)單的功能模擬器Sim-Safe，而且還提供了基于超標(biāo)量處理器微體系結(jié)構(gòu)的亂序性能模擬器Sim-outorder。下面是simulator的結(jié)構(gòu)圖[8]：

圖3-1 simulator的結(jié)構(gòu)圖[8]
SimpleScalar包括多個(gè)仿真模擬器，其中包括：
sim-safe,sim-cache,sim-cheetah,sim-bred,sim-profile,sim-eio,sim-outorder和sim-fast 八個(gè)仿真模擬器。
在本次實(shí)驗(yàn)中主要用到sim-safe和sim-cache兩個(gè)模擬器，在修改SimpleScalar時(shí)一般先用sim-safe來(lái)調(diào)試，sim-safe是SimpleScalar所有仿真器中最簡(jiǎn)單的一個(gè)功能仿真器；它進(jìn)行指令錯(cuò)誤檢查，再對(duì)數(shù)據(jù)進(jìn)行具體統(tǒng)計(jì)。在這個(gè)仿真其中加入了cache，用戶可以對(duì)cache及TLB 進(jìn)行設(shè)置，支持兩級(jí)的cache和一級(jí)的TLB，第一級(jí)cache和TLB均分為數(shù)據(jù)和指令兩部分。由于SimpleScalar是開(kāi)放源碼(opensource)的，所以我們通過(guò)對(duì)模擬器的修改或功能的添加便可獲取我們所需要的統(tǒng)計(jì)。
3.1.2 SimpleScalar安裝調(diào)試
由于研究需要通過(guò)SimpleScalar獲取大量數(shù)據(jù)，所以首要任務(wù)便是安裝SimpleScalar。由于實(shí)驗(yàn)平臺(tái)是在linu*操作系統(tǒng)上的，所以首先需要安裝linu*，虛擬機(jī)真機(jī)都可以，本平臺(tái)是在Ubuntu10.04系統(tǒng)上搭建的。 眾所周知，SimpleScalar的安裝時(shí)間非常讓人頭疼的事情，因?yàn)樵诰幾g過(guò)程中會(huì)出現(xiàn)許多意想不到的錯(cuò)誤，而不同的電腦又會(huì)遇到不同的問(wèn)題，網(wǎng)上的總結(jié)也有很多不適用，本次實(shí)驗(yàn)也是安裝了五六遍才安裝成功的，現(xiàn)將具體安裝過(guò)程總結(jié)如下:
從SimpleScalar官方網(wǎng)站www.simplescalar.com上下載安裝源文件Simpletools-2v0.tgz、Simplesim-3v0.tar.gz、Simpleutils-990811.tar.gz、Gcc-2.7.2.3.tar.gz。

第一步 設(shè)置環(huán)境：打開(kāi)系統(tǒng)終端，設(shè)置臨時(shí)環(huán)境變量e*port HOST=i386-pc-linu*, e*port SSS=/home/bruce,(在這里bruce為本次實(shí)驗(yàn)所用的電腦名稱(chēng))， e*port TARGET=sslittle-na-sstri*。 在home里創(chuàng)建simplescalar文件夾，然后將安裝文件放到該文件夾里。安裝fle*、build-essential、bison三個(gè)文件包，安裝命令：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。 進(jìn)入simpleutils文件cd simlpeutils-990811 但是里面有很多源代碼錯(cuò)誤需要修改，否則編不能通過(guò)。在ld中找到ldle*.l這個(gè)文件，然后講所有的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。之后可以測(cè)試simplesim的安裝，輸入一下代碼：./sim-safe tests/bin.little/test-math。

第四步 安裝GCC Cross-Compiler：這一步非常重要，大部分人都在這步出問(wèn)題。我也在這步重復(fù)了三遍才完成。首先進(jìn)入simplescalar文件，解壓gcc-2.7.3 tar –z*vf gcc-2.7.2.3.ss_.tar.gz 然后進(jìn)入gcc-2.7.2.3文件設(shè)置PATH： e*port PATH=$PATH:/home/bruce/simplescalar/sslittle-na-sstri*-bin，然后進(jìn)行配置：./configure –host=$HOST –target=$TARGET -with-gnu-as –with-gnu-ld –prefi*=$SSS。 但是在文件運(yùn)行之前需要對(duì)文件代碼進(jìn)行一些改動(dòng)，否則不能編譯成功。(1)將Makefile的130行結(jié)尾換成: -I/usr/include。
(2) protoize.c的第60行中，將#include改成#include。(3)obstack.h第341行將*((void**)_o->ne*t_free)++((void*)datum);改成（注意括號(hào)）
*((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) 進(jìn)入gcc2.7.2.3目錄中cd $SSS/gcc-2.7.2.3 , make會(huì)遇到錯(cuò)誤在insn-output.c
中第675，750，823行為加‘\’。（注意先獲取文件的寫(xiě)權(quán)限）
(6) objc中的sendmsg.c文件中缺少ST ……（未完，全文共38968字，當(dāng)前僅顯示7009字，請(qǐng)閱讀下面提示信息。收藏《畢業(yè)論文：數(shù)據(jù)密集型應(yīng)用訪存特征分析與優(yōu)化》）