[發(fā)明專利]消除內(nèi)存訪問沖突的編譯裝置及其實現(xiàn)方法

無效

• 申請?zhí)枺?/td>: 201010577313.5
• 申請日: 2010-12-08
• 公開（公告）號: CN102043659A
• 公開（公告）日: 2011-05-04
• 發(fā)明（設(shè)計）人: 肖賀;孔吉;劉佩林
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06F9/45
• 分類號: G06F9/45;G06F9/50
• 代理公司: 上海交達(dá)專利事務(wù)所 31201
• 代理人: 王錫麟;王桂忠

技術(shù)領(lǐng)域

本發(fā)明涉及的是一種計算機(jī)技術(shù)領(lǐng)域的裝置及方法，具體是一種消除內(nèi)存訪問沖突的編譯裝置及其實現(xiàn)方法。

背景技術(shù)

編譯器是將高級語言轉(zhuǎn)換成機(jī)器可執(zhí)行語言的程序。編譯器在轉(zhuǎn)換過程中，需要對程序中的變量在內(nèi)存的存放位置進(jìn)行分配，以避免內(nèi)存指令在執(zhí)行過程中因內(nèi)存沖突而引發(fā)的流水線停頓，最終提高最終生成的機(jī)器可執(zhí)行程序的執(zhí)行效率。

在現(xiàn)有的處理器中，特別是DSP處理器，指令集通常會支持內(nèi)存操作數(shù)以及多樣的尋址方式。由于在數(shù)據(jù)處理及其應(yīng)用中，內(nèi)存訪問操作是一個關(guān)鍵的環(huán)節(jié)，因此，如何進(jìn)行變量分配以最高效率地利用流水線是具有至關(guān)重要的意義的。另一方面，對于多數(shù)的DSP架構(gòu)，為了盡可能地提高內(nèi)存帶寬，通常支持多數(shù)據(jù)內(nèi)存架構(gòu)(一般是雙數(shù)據(jù)內(nèi)存架構(gòu))，即指令可以在同一個時鐘周期并行訪問多個不同的數(shù)據(jù)內(nèi)存，但是不能在同一個時鐘周期多次訪問一個數(shù)據(jù)內(nèi)存。

解決這種內(nèi)存沖突的方法有兩大類，一類是程序員手動安排變量的存儲位置，特別在嵌入式應(yīng)用中，手動分配變量是一種非常有效的內(nèi)存分配方法，它使得程序在數(shù)據(jù)結(jié)構(gòu)算法層面上消除了內(nèi)存沖突，但是當(dāng)程序結(jié)構(gòu)變得復(fù)雜時，人為分配變量的方法經(jīng)常會陷入局部最優(yōu)化的怪圈；另一類是通過編譯器進(jìn)行優(yōu)化，這種方法可以從全局角度進(jìn)行變量存儲空間分配，但是現(xiàn)階段編譯器對于多數(shù)據(jù)存儲器架構(gòu)的變量分配策略仍然不完善。

經(jīng)對現(xiàn)有技術(shù)的文獻(xiàn)調(diào)查發(fā)現(xiàn)，G.Grewal等在2006年IEEE?Congress?on?Evolutionary?Computation上采用遺傳算法并針對M56K這一類雙數(shù)據(jù)內(nèi)存的DSP結(jié)構(gòu)提出了一種內(nèi)存分配策略。但是這種分配策略對于多于雙通道的內(nèi)存結(jié)構(gòu)無能為力，且當(dāng)內(nèi)存訪問出現(xiàn)源操作數(shù)與目的操作數(shù)相同的情況，將不可避免地發(fā)生內(nèi)存沖突；同時，這種分配算法僅針對內(nèi)存變量為單一變量的情況有效，當(dāng)變量為數(shù)組等連續(xù)結(jié)構(gòu)時，這種分配算法將失效。

發(fā)明內(nèi)容

本發(fā)明針對現(xiàn)有技術(shù)存在的上述不足，提供一種消除內(nèi)存訪問沖突的編譯裝置及其實現(xiàn)方法，使得因內(nèi)存沖突而產(chǎn)生的額外開銷大大減小。

本發(fā)明是通過以下技術(shù)方案實現(xiàn)的：

本發(fā)明涉及一種消除內(nèi)存訪問沖突的編譯裝置，包括：前端語言分析單元、內(nèi)存變量分析單元、內(nèi)存沖突消除單元和轉(zhuǎn)換輸出單元，其中：前端語言分析單元與內(nèi)存變量分析單元和內(nèi)存沖突消除單元相連接并傳輸由源程序轉(zhuǎn)換的中間語言序列、內(nèi)存模型與內(nèi)存操作信息和源文件函數(shù)依賴樹，內(nèi)存變量分析單元與內(nèi)存沖突消除單元相連接并傳輸變量內(nèi)存分配和內(nèi)存塊操作信息，內(nèi)存沖突消除單元與轉(zhuǎn)換輸出單元相連接并傳輸經(jīng)過內(nèi)存分配優(yōu)化的中間語言信息，轉(zhuǎn)換輸出單元輸出最終的可執(zhí)行代碼。

所述的前端語言分析單元包括：內(nèi)存配置組件、語言分析組件和文件函數(shù)關(guān)系組件，其中：內(nèi)存配置組件與內(nèi)存變量分析單元相連接并通過內(nèi)存操作信息表和內(nèi)存模型描述表傳遞內(nèi)存操作信息和內(nèi)存模型，語言分析組件將源程序轉(zhuǎn)換為中間語言序列并分別傳遞給內(nèi)存變量分析單元和內(nèi)存沖突消除單元，文件函數(shù)關(guān)系組件分析源程序中各文件的函數(shù)依賴關(guān)系并以源文件函數(shù)依賴樹的形式傳遞給內(nèi)存沖突消除單元。

所述的內(nèi)存操作信息表包括：數(shù)學(xué)運算指令功能、操作數(shù)個數(shù)、操作數(shù)類型、尋址模式、數(shù)據(jù)寬度以及執(zhí)行開銷；

所述的內(nèi)存模型描述表包括內(nèi)存的總大小、內(nèi)存分區(qū)的個數(shù)、各個內(nèi)存分區(qū)的起始地址和大小。

所述的內(nèi)存變量分析單元讀取并分析記錄中間程序包含的所有的內(nèi)存變量及其操作，該內(nèi)存變量分析單元包括：內(nèi)存變量分配器和變量分析組件，其中：內(nèi)存變量分配器分析由前端語言分析單元生成的中間語言序列中的內(nèi)存變量信息并采用動態(tài)分配或靜態(tài)分配以變量內(nèi)存分配表的形式傳遞給變量分析組件，內(nèi)存變量分析單元通過變量內(nèi)存分配表來分析每一個程序基本塊中的內(nèi)存操作信息并記錄到內(nèi)存塊操作表中。

所述的動態(tài)分配是指：內(nèi)存變量分配器通過唯一確定且記錄到變量內(nèi)存分配表中的分配標(biāo)識以跟蹤記錄內(nèi)存變量的名稱以及生存周期信息；

所述的靜態(tài)分配是指：內(nèi)存變量分配器標(biāo)識該變量生存周期為全局并記錄到變量內(nèi)存分配表中；

所述的變量內(nèi)存分配表包括：變量標(biāo)識、變量名、變量尺寸、變量生存周期、變量分割以及內(nèi)存分配，其中：變量標(biāo)識是區(qū)別不同變量的唯一標(biāo)識；變量尺寸記錄變量的大小信息；變量生存周期記錄變量的生存周期，包括變量的分配時刻以及變量的釋放時刻，在初始階段對于全局變量來說，分配時刻即程序開始，釋放時刻是程序終止；變量分割記錄變量經(jīng)過變量分割變換模塊后的新信息，包括分割數(shù)量，每個分割的變量重命名，以及各分割的內(nèi)存分配；