畢業(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ī)科學(xué)與技術(shù)學(xué)院
所 學(xué) 專 業(yè)： 軟件工程

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



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

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

下面以MiBench中的dijkstra基準(zhǔn)測試程序為例來進(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)在對dijkstra程序的代碼進(jìn)行分析，程序的代碼部分保存在圖2-1中的Code模塊中，函數(shù)全局變量，即global變量保存在Initialized vars和Uninitialized vars模塊中，函數(shù)enqueue中的或其他函數(shù)中動態(tài)申請的變量保存在heap塊中，而主函數(shù)調(diào)用其他函數(shù)時所需要的空間則分配在stack模塊中。其中heap模塊會隨著動態(tài)數(shù)據(jù)的申請和釋放變化，stack也會隨著函數(shù)的調(diào)用和釋放動態(tài)變化。
在編譯時分配的全局變量和只讀數(shù)據(jù)組成靜態(tài)數(shù)據(jù)，動態(tài)數(shù)據(jù)可以進(jìn)一步分解成堆棧，存儲在運行過程中創(chuàng)建子程序調(diào)用激活記錄堆動態(tài)分配功能，如C語言中的malloc（），這些語義區(qū)域的創(chuàng)建根據(jù)不同的目的現(xiàn)實不同的特征，也可以利用專門的硬件來實現(xiàn)。
在訪存的數(shù)據(jù)區(qū)域（global，heap，stack）中heap數(shù)據(jù)占訪存次數(shù)比例最大[1][2]，即heap_data應(yīng)用最密集，因此我們對密集型數(shù)據(jù)訪存優(yōu)化的重點變放在對heap_data的分析和優(yōu)化上。

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


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

圖3-1 simulator的結(jié)構(gòu)圖[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來調(diào)試，sim-safe是SimpleScalar所有仿真器中最簡單的一個功能仿真器；它進(jìn)行指令錯誤檢查，再對數(shù)據(jù)進(jìn)行具體統(tǒng)計。在這個仿真其中加入了cache，用戶可以對cache及TLB 進(jìn)行設(shè)置，支持兩級的cache和一級的TLB，第一級cache和TLB均分為數(shù)據(jù)和指令兩部分。由于SimpleScalar是開放源碼(opensource)的，所以我們通過對模擬器的修改或功能的添加便可獲取我們所需要的統(tǒng)計。
3.1.2 SimpleScalar安裝調(diào)試
由于研究需要通過SimpleScalar獲取大量數(shù)據(jù)，所以首要任務(wù)便是安裝SimpleScalar。由于實驗平臺是在linu*操作系統(tǒng)上的，所以首先需要安裝linu*，虛擬機(jī)真機(jī)都可以，本平臺是在Ubuntu10.04系統(tǒng)上搭建的。 眾所周知，SimpleScalar的安裝時間非常讓人頭疼的事情，因為在編譯過程中會出現(xiàn)許多意想不到的錯誤，而不同的電腦又會遇到不同的問題，網(wǎng)上的總結(jié)也有很多不適用，本次實驗也是安裝了五六遍才安裝成功的，現(xiàn)將具體安裝過程總結(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)境：打開系統(tǒng)終端，設(shè)置臨時環(huán)境變量e*port HOST=i386-pc-linu*, e*port SSS=/home/bruce,(在這里bruce為本次實驗所用的電腦名稱)， e*port TARGET=sslittle-na-sstri*。 在home里創(chuàng)建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。 進(jìn)入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：這一步非常重要，大部分人都在這步出問題。我也在這步重復(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。 但是在文件運行之前需要對文件代碼進(jìn)行一些改動，否則不能編譯成功。(1)將Makefile的130行結(jié)尾換成: -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) 進(jìn)入gcc2.7.2.3目錄中cd $SSS/gcc-2.7.2.3 , make會遇到錯誤在insn-output.c
中第675，750，823行為加‘\’。（注意先獲取文件的寫權(quán)限）
(6) objc中的sendmsg.c文件中缺少ST ……（未完，全文共38968字，當(dāng)前僅顯示7009字，請閱讀下面提示信息。收藏《畢業(yè)論文：數(shù)據(jù)密集型應(yīng)用訪存特征分析與優(yōu)化》）