傅 杰 靳國(guó)杰 章隆兵* 王 劍*

(*中國(guó)科學(xué)院大學(xué) 北京 100049)(**計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100190)(***中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)(****龍芯中科技術(shù)有限公司 北京 100095)

?

基于軟硬件協(xié)同設(shè)計(jì)的解釋器指令分派方法①

傅 杰②******靳國(guó)杰****章隆兵*****王 劍*****

(*中國(guó)科學(xué)院大學(xué) 北京 100049)(**計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100190)(***中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)(****龍芯中科技術(shù)有限公司 北京 100095)

為了降低指令分派造成的運(yùn)行開(kāi)銷(xiāo)以提高解釋器的性能，提出了一種采用軟硬件協(xié)同設(shè)計(jì)的解釋器指令分派方法。其核心思想是在軟件層面通過(guò)對(duì)指令分派表進(jìn)行優(yōu)化以消除了代價(jià)較高的地址常量加載操作，在硬件層面通過(guò)擴(kuò)展處理器的訪(fǎng)存指令進(jìn)一步實(shí)現(xiàn)基于硬件支持的訪(fǎng)存加速。軟硬件協(xié)同設(shè)計(jì)可以最大限度地降低由指令分派引入的運(yùn)行時(shí)開(kāi)銷(xiāo)，從而提升解釋執(zhí)行的效率。試驗(yàn)結(jié)果表明，該方法能夠顯著提升解釋器的性能。對(duì)于SPECjvm98和DaCapo測(cè)試集，解釋器總體性能提升了11.5%，且單項(xiàng)性能的最大提升幅度高達(dá)15.4%。該方法通用性強(qiáng)，實(shí)現(xiàn)代價(jià)低，適用于現(xiàn)代主流處理器平臺(tái)上高性能解釋器的設(shè)計(jì)和優(yōu)化。

解釋器， 指令分派， 軟硬件協(xié)同設(shè)計(jì)， 虛擬機(jī)， 優(yōu)化

0 引 言

解釋器(interpreter)是一種處理計(jì)算機(jī)語(yǔ)言的系統(tǒng)軟件，常用于高級(jí)編程語(yǔ)言的實(shí)現(xiàn)[1-3]。從20世紀(jì)60年代著名的Lisp語(yǔ)言到新興的Java、Python及JavaScript等編程語(yǔ)言，均使用解釋器構(gòu)建其執(zhí)行引擎。由于具有結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)以及運(yùn)行時(shí)資源消耗少等優(yōu)勢(shì)[4]，解釋器被廣泛應(yīng)用于各種實(shí)際系統(tǒng)中。解釋器和即時(shí)(just-in-time, JIT)編譯器[5]通常以互補(bǔ)的形式共同組成Java等高級(jí)語(yǔ)言虛擬機(jī)[6-8]的執(zhí)行引擎。應(yīng)用程序由解釋器開(kāi)始執(zhí)行，JIT編譯器僅編譯程序中頻繁執(zhí)行的部分。因此，解釋執(zhí)行的速度直接影響系統(tǒng)的啟動(dòng)性能。對(duì)于客戶(hù)端瀏覽器中的JavaScript引擎，解釋器的性能在很大程度上決定了系統(tǒng)的響應(yīng)速度，直接影響用戶(hù)的使用體驗(yàn)。與此同時(shí)，在工業(yè)機(jī)器人和高檔數(shù)控機(jī)床等領(lǐng)域，控制指令和加工程序的執(zhí)行也普遍采用解釋器來(lái)實(shí)現(xiàn)。解釋器的性能決定了智能化控制的實(shí)時(shí)性和自動(dòng)化生產(chǎn)的效率。隨著人類(lèi)社會(huì)信息化的不斷發(fā)展，由解釋器運(yùn)行速度慢而導(dǎo)致的性能和效率等問(wèn)題將變得越來(lái)越普遍和突出。因此，進(jìn)行解釋器的優(yōu)化以改善其性能，對(duì)提高生產(chǎn)效率具有十分重要的意義。

解釋執(zhí)行的基本單位以字節(jié)碼最為常見(jiàn)。每個(gè)字節(jié)碼都對(duì)應(yīng)一段特定的本地指令序列。字節(jié)碼的解釋執(zhí)行最終由其所對(duì)應(yīng)的本地指令序列在硬件上的執(zhí)行來(lái)實(shí)現(xiàn)。解釋執(zhí)行分為取字節(jié)碼、指令分派、取操作數(shù)和執(zhí)行等四個(gè)步驟。其中，指令分派是指當(dāng)前字節(jié)碼執(zhí)行完畢后，查找并跳轉(zhuǎn)到下一個(gè)字節(jié)碼的本地指令序列入口的過(guò)程。指令分派的頻繁發(fā)生會(huì)引入大量額外的運(yùn)行時(shí)開(kāi)銷(xiāo)，嚴(yán)重影響解釋執(zhí)行的性能。因此，對(duì)指令分派進(jìn)行優(yōu)化是提升解釋器性能的有效途徑。本文研究了解釋器指令分派的優(yōu)化技術(shù)，提出了一種采用軟硬件協(xié)同設(shè)計(jì)的指令分派方法。實(shí)驗(yàn)結(jié)果表明，本文方法大幅降低了指令分派時(shí)查找本地指令序列入口地址的開(kāi)銷(xiāo)，顯著提升了解釋器的性能。

1 相關(guān)工作

早期的解釋器大都采用Switch結(jié)構(gòu)來(lái)實(shí)現(xiàn)[9]。20世紀(jì)70年代，Bell[1]研究發(fā)現(xiàn)Switch結(jié)構(gòu)的解釋器在指令分派時(shí)存在二次跳轉(zhuǎn)和邊界檢查等冗余操作，嚴(yán)重影響解釋器的性能，從而提出了著名的線(xiàn)索化代碼(threaded code)結(jié)構(gòu)的解釋器[1]，以加速指令分派的過(guò)程。線(xiàn)索化代碼結(jié)構(gòu)的解釋器通過(guò)在本地指令序列的末尾獨(dú)立實(shí)現(xiàn)指令分派，消除了Switch結(jié)構(gòu)解釋器中的冗余操作，從而獲得了更高的性能。此后，線(xiàn)索化代碼結(jié)構(gòu)成為高性能解釋器設(shè)計(jì)的主流。

然而，線(xiàn)索化代碼結(jié)構(gòu)的解釋器進(jìn)行指令分派時(shí)依然存在較大開(kāi)銷(xiāo)。為了進(jìn)一步提升指令分派的速度，文獻(xiàn)[2]提出了超級(jí)指令(superinstruction)技術(shù)。該技術(shù)將頻繁執(zhí)行的連續(xù)字節(jié)碼序列等效替換為一條新定義的字節(jié)碼(稱(chēng)為“超級(jí)指令”)，以消除被替換的字節(jié)碼之間的指令分派。隨后，Casey等人[3]的研究表明，由于指令分派中用于實(shí)現(xiàn)跳轉(zhuǎn)功能的間接轉(zhuǎn)移指令存在多個(gè)跳轉(zhuǎn)目標(biāo)地址，導(dǎo)致處理器對(duì)間接轉(zhuǎn)移猜測(cè)的正確率下降，從而降低解釋器的性能。針對(duì)上述問(wèn)題，他們提出了指令冗余(instruction redundancy)技術(shù)，通過(guò)增加若干語(yǔ)義功能相同的冗余的字節(jié)碼，以減少間接轉(zhuǎn)移指令可能的跳轉(zhuǎn)目標(biāo)數(shù)目，從而提升分支預(yù)測(cè)的準(zhǔn)確性。但是，由于受字節(jié)碼中操作碼域編碼長(zhǎng)度的限制，實(shí)際能夠提供的超級(jí)指令或冗余字節(jié)碼的數(shù)量十分有限，因而其優(yōu)化空間較小。

文獻(xiàn)[10]設(shè)計(jì)了一種新型的分支預(yù)測(cè)器。該方法利用字節(jié)碼指針來(lái)區(qū)分不同的轉(zhuǎn)移場(chǎng)景，并在解釋器中插入引導(dǎo)指令來(lái)提升處理器對(duì)間接轉(zhuǎn)移猜測(cè)的正確率。然而該方法要求對(duì)處理器內(nèi)部的分支預(yù)測(cè)器進(jìn)行定制，硬件實(shí)現(xiàn)開(kāi)銷(xiāo)較大。此外，最新的研究結(jié)果表明[11]，隨著分支預(yù)測(cè)技術(shù)的不斷發(fā)展，在當(dāng)今主流的處理器上，間接轉(zhuǎn)移猜測(cè)已不再是制約解釋器性能最主要的因素，因而其優(yōu)化空間非常有限。

針對(duì)上述研究的不足，本文以降低獲取本地指令序列入口地址的開(kāi)銷(xiāo)為突破口，對(duì)解釋器指令分派進(jìn)行了優(yōu)化。本文首先對(duì)解釋器的性能瓶頸進(jìn)行分析，并在此基礎(chǔ)上，提出了一種軟硬件協(xié)同設(shè)計(jì)的解釋器指令分派方法。最后通過(guò)對(duì)比實(shí)驗(yàn)，分析和驗(yàn)證了本文方法的有效性。

2 解釋器性能瓶頸分析

本節(jié)以HotSpot虛擬機(jī)[7]的解釋器為代表，介紹了現(xiàn)代高性能解釋器設(shè)計(jì)的關(guān)鍵技術(shù)。隨后，又以MIPS架構(gòu)的處理器為例，深入分析了解釋器的性能瓶頸。

2.1 解釋器設(shè)計(jì)的關(guān)鍵技術(shù)

HotSpot的解釋器基于線(xiàn)索化代碼結(jié)構(gòu)進(jìn)行設(shè)計(jì)，模擬了一個(gè)基于棧式體系結(jié)構(gòu)的抽象處理器。它采用了棧頂緩存(stack caching)的優(yōu)化技術(shù)[12]，將操作數(shù)棧頂?shù)囊粋€(gè)元素緩存到一個(gè)通用寄存器中，從而減少取操作數(shù)時(shí)冗余的棧頂訪(fǎng)存操作。

棧頂緩存技術(shù)使得字節(jié)碼的本地指令序列存在多個(gè)不同的入口。在指令分派階段，解釋器根據(jù)下一個(gè)字節(jié)碼和當(dāng)前的棧頂緩存狀態(tài)查詢(xún)指令分派表，以獲取本地指令序列的入口地址。表1展示了所有的棧頂緩存狀態(tài)及其含義。從表1中可以看出，由于存在9種不同的棧頂緩存狀態(tài)，故字節(jié)碼本地指令序列的入口最多可以有9個(gè)。圖1展示了指令分派表的基本結(jié)構(gòu)，其中每列存儲(chǔ)一個(gè)字節(jié)碼的本地指令序列所有可能的入口地址。例如，圖1中陰影部分的表項(xiàng)存儲(chǔ)編碼為96的字節(jié)碼(iadd，表示整數(shù)加法)在棧頂緩存狀態(tài)為itos時(shí)的本地指令序列的入口地址。由于指令分派表在解釋執(zhí)行期間被頻繁訪(fǎng)問(wèn)，因此合理地設(shè)計(jì)指令分派表的結(jié)構(gòu)以加快指令分派時(shí)的查表操作，是提升解釋器性能的關(guān)鍵。

表1 解釋器棧頂緩存狀態(tài)

圖1 解釋器指令分派表

2.2 指令分派瓶頸分析

解釋執(zhí)行期間，指令分派的開(kāi)銷(xiāo)對(duì)解釋器的性能有著很大的影響。由于直接統(tǒng)計(jì)指令分派的執(zhí)行時(shí)間較為困難且存在較大誤差，本文使用指令的數(shù)量來(lái)間接反映指令分派的開(kāi)銷(xiāo)。圖2統(tǒng)計(jì)了指令分派部分的指令條數(shù)占本地指令序列指令數(shù)目的比例。統(tǒng)計(jì)結(jié)果表明，在絕大多數(shù)字節(jié)碼的本地指令序列中，用于指令分派的本地指令數(shù)目占本地指令總數(shù)的25%以上，幾何均值達(dá)到21.4%，最高可達(dá)68.8%。因此，解釋器運(yùn)行時(shí)，指令分派約占總執(zhí)行開(kāi)銷(xiāo)的20%，甚至更高。

圖2 指令分派在本地指令序列中所占比例

圖3展示了在MIPS架構(gòu)處理器的64位系統(tǒng)中，字節(jié)碼iadd的本地指令序列。為了更清晰地展示本地指令序列的結(jié)構(gòu)和語(yǔ)義，圖中省略了對(duì)分支指令延遲槽的優(yōu)化。由圖3可知，iadd的本地指令序列共有18條機(jī)器指令，其中用于指令分派的機(jī)器指令多達(dá)11條，占本地指令序列的61.1%。由于指令分派部分的指令總是全部執(zhí)行，并且指令分派頻繁發(fā)生，故指令分派在解釋執(zhí)行期間產(chǎn)生的額外開(kāi)銷(xiāo)很大，成為解釋器性能的瓶頸。

指令分派時(shí)，解釋器首先根據(jù)下一個(gè)字節(jié)碼和當(dāng)前的棧頂緩存狀態(tài)查詢(xún)指令分派表，以獲取本地指令序列的入口地址(記為Entry)，隨后跳轉(zhuǎn)到Entry處繼續(xù)執(zhí)行。設(shè)下一個(gè)待執(zhí)行的字節(jié)碼編碼為x(x∈[0, 255])，當(dāng)前棧頂?shù)木彺鏍顟B(tài)為s(s∈[0, 8])，則指令分派可進(jìn)一步細(xì)分為以下幾個(gè)步驟：

(1) 加載待查詢(xún)的指令分派表的行首地址到通用寄存器Reg中(即圖3中第8～13條指令)；

(2) 計(jì)算存儲(chǔ)Entry的表項(xiàng)在待查詢(xún)的行內(nèi)的偏移offset(即圖3中第14條指令)；

(3) 從指令分派表中地址為Reg+offset的位置加載Entry的值(即圖3中第15和16條指令)；

(4) 跳轉(zhuǎn)到Entry繼續(xù)執(zhí)行(即圖3中第17條指令)。

上述4個(gè)步驟中，前3步為獲取Entry的操作，最后一步執(zhí)行跳轉(zhuǎn)動(dòng)作。由于獲取Entry需要9條機(jī)器指令(即圖3中第8～16條)，占了指令分派的大部分執(zhí)行時(shí)間，故獲取Entry的操作構(gòu)成了指令分派的瓶頸。進(jìn)一步分析可知，第(1)步中加載待查詢(xún)的指令分派表的行首地址耗費(fèi)了6條機(jī)器指令(即圖3中第8～13條)，是導(dǎo)致獲取Entry值代價(jià)過(guò)高的主要原因。

圖3 字節(jié)碼iadd的本地指令序列

3 軟硬件協(xié)同的指令分派設(shè)計(jì)

本文針對(duì)指令分派時(shí)獲取本地指令序列的入口地址代價(jià)過(guò)高的問(wèn)題，設(shè)計(jì)并實(shí)現(xiàn)了一種軟硬件協(xié)同的指令分派方法，主要包括軟件優(yōu)化的指令分派表訪(fǎng)問(wèn)技術(shù)和基于硬件支持的訪(fǎng)存加速策略。

3.1 指令分派表的優(yōu)化設(shè)計(jì)

指令分派期間，為了查找本地指令序列的入口地址，需加載待查詢(xún)的指令分派表的行首地址到寄存器中。由圖3可知，完成該操作需要6條機(jī)器指令，實(shí)現(xiàn)代價(jià)較高。本文設(shè)計(jì)了一種便于高效訪(fǎng)問(wèn)的指令分派表，其結(jié)構(gòu)如圖4所示，完全消除了加載操作的開(kāi)銷(xiāo)。本文從以下四個(gè)方面對(duì)指令分派表進(jìn)行了優(yōu)化。

(1)對(duì)指令分派表的行列進(jìn)行了轉(zhuǎn)置，為后文基于硬件支持的指令分派表的訪(fǎng)問(wèn)加速奠定了基礎(chǔ)。轉(zhuǎn)置前的指令分派表每行有256個(gè)表項(xiàng)。當(dāng)加載行中的某個(gè)表項(xiàng)時(shí)，行內(nèi)偏移的取值范圍較大。對(duì)于64位的系統(tǒng)，轉(zhuǎn)置前行內(nèi)偏移的范圍是[0, 211-8]?[-211, 211-1]，故要求訪(fǎng)存指令中偏移量編碼域的長(zhǎng)度不少于12位。但是由于精簡(jiǎn)指令集架構(gòu)的處理器通常采用固定長(zhǎng)度的指令編碼格式，訪(fǎng)存指令中所能提供的編碼偏移量的長(zhǎng)度非常有限。本文對(duì)原有指令分派表進(jìn)行了轉(zhuǎn)置，可以減少機(jī)器指令中偏移量編碼所需的長(zhǎng)度，使得通過(guò)硬件支持的方式加速指令分派表的訪(fǎng)問(wèn)成為可能。

圖4 優(yōu)化后的指令分派表結(jié)構(gòu)

(2)剔除了三類(lèi)無(wú)用表項(xiàng)，減少了解釋執(zhí)行時(shí)對(duì)系統(tǒng)資源的消耗。指令分派時(shí)，需根據(jù)當(dāng)前棧頂?shù)木彺鏍顟B(tài)確定下一個(gè)字節(jié)碼的本地指令序列的入口地址。由于HotSpot解釋器將緩存狀態(tài)為btos、ctos和stos的入口地址均映射到itos的入口地址，因此圖4中的指令分派表結(jié)構(gòu)在設(shè)計(jì)時(shí)，消除了btos、ctos和stos相關(guān)的表項(xiàng)，以進(jìn)一步減少解釋執(zhí)行對(duì)內(nèi)存等資源的消耗。

(3)添加了兩列填充表項(xiàng)，以減少查表的計(jì)算開(kāi)銷(xiāo)。指令分派表在添加填充表項(xiàng)前，需執(zhí)行一次乘法操作來(lái)計(jì)算待查表項(xiàng)的行偏移。由于乘法運(yùn)算的代價(jià)較高，在設(shè)計(jì)指令分派表時(shí)，每行的末尾均添加了兩個(gè)填充表項(xiàng)，如圖4中陰影部分所示，從而可通過(guò)一次快速的左移位操作計(jì)算出行偏移。因此，填充表項(xiàng)的引入可將代價(jià)較高的乘法運(yùn)算轉(zhuǎn)換為高效的移位操作，查表時(shí)計(jì)算代價(jià)明顯降低。

(4)合理設(shè)計(jì)指令分派表每列的順序，提高訪(fǎng)存效率。圖5展示了訪(fǎng)問(wèn)指令分派表時(shí)棧頂緩存狀態(tài)的頻率分布。從圖中可知指令分派表的訪(fǎng)問(wèn)集中在對(duì)vtos、itos、atos和ftos緩存狀態(tài)的查詢(xún)。因此在設(shè)計(jì)指令分派表時(shí)，將vtos、itos、atos和ftos這4個(gè)表項(xiàng)安排在相鄰的位置，以增強(qiáng)訪(fǎng)存的局部性，提高訪(fǎng)存效率。

圖5 指令分派表訪(fǎng)問(wèn)時(shí)棧頂緩存狀態(tài)的頻率分布

3.2 軟件優(yōu)化的指令分派表訪(fǎng)問(wèn)技術(shù)

根據(jù)3.1節(jié)中指令分派表結(jié)構(gòu)的設(shè)計(jì)，指令分派表的訪(fǎng)問(wèn)技術(shù)也做了相應(yīng)的軟件優(yōu)化。其核心思想是將指令分派表的起始地址緩存到一個(gè)可以高速訪(fǎng)問(wèn)的部件中，以消除優(yōu)化前代價(jià)較高的行首地址加載操作。

圖6具體展示了基于軟件優(yōu)化的指令分派表查找本地指令序列入口地址的方法。本文選擇了一個(gè)通用寄存器作為指令分派表的高速緩存部件，該寄存器稱(chēng)為指令分派寄存器(記為gpr)。解釋器初始化時(shí)，將指令分派表的起始地址(即圖6中標(biāo)“0”的箭頭所指向的位置)保存到指令分派寄存器中。設(shè)下一個(gè)待執(zhí)行的字節(jié)碼編碼為x(x∈[0, 255])，當(dāng)前棧頂?shù)木彺鏍顟B(tài)為s(s∈[0,5])，待查找的本地指令序列的入口地址為Entry，則獲取Entry的步驟如下：

圖6 優(yōu)化的指令分派表訪(fǎng)問(wèn)方法

(1) 根據(jù)字節(jié)碼x的編碼，計(jì)算待訪(fǎng)問(wèn)表項(xiàng)的行偏移row_offset(即圖6中標(biāo)“1”的箭頭所指向的位置)：

row_offset=8×AddressLength×x

(1)

其中AddressLength表示系統(tǒng)中一個(gè)指針?biāo)嫉淖止?jié)數(shù)目，為一個(gè)固定的常量。row_offset保存在一個(gè)通用寄存器中。它的值將在解釋執(zhí)行的過(guò)程中實(shí)時(shí)計(jì)算。具體實(shí)現(xiàn)時(shí)，上述乘法操作可以轉(zhuǎn)換為對(duì)x的快速左移位操作，需要左移的位數(shù)為log2(8×AddressLength)。

(2) 根據(jù)當(dāng)前的棧頂狀態(tài)s(s∈[0, 5])，計(jì)算待訪(fǎng)問(wèn)表項(xiàng)的列偏移col_offset(即圖6中標(biāo)“2”的箭頭所指向的位置)：

col_offset=AddressLength×s

(2)

由于AddressLength≤8，故col_offset∈[0,40]，為一個(gè)較小的立即數(shù)。其值在解釋器初始化時(shí)確定。

(3) 從指令分派表中地址為gpr+row_offset+col_offset的表項(xiàng)(即圖6中標(biāo)“3”的箭頭所指向的表項(xiàng))中加載Entry的值。

圖7展示了采用圖6中的方法實(shí)現(xiàn)的指令分派方案。行偏移row_offset的值在第1條左移位指令dsll中完成計(jì)算，結(jié)果存于寄存器t2中。在第2條加法指令daddu中，指令分派寄存器gpr與t2相加得到待查詢(xún)的指令分派表的行首地址，并將其保存到寄存器t3中。隨后，第3條訪(fǎng)存指令ld實(shí)現(xiàn)從地址為t3+col_offset的指令分派表中加載Entry的值。最后，通過(guò)第4條間接轉(zhuǎn)移指令jr跳轉(zhuǎn)到入口為Entry的本地指令序列中繼續(xù)執(zhí)行，從而完成一次指令分派。

圖7 純軟件優(yōu)化的指令分派

對(duì)比圖3可以看出，優(yōu)化前用于加載指令分派表待查詢(xún)的行首地址的6條機(jī)器指令已全部消除，指令分派部分的機(jī)器指令數(shù)目由原來(lái)的11條減少為5條。通過(guò)對(duì)SPECjvm98和DaCapo等測(cè)試集的分析知，解釋執(zhí)行期間指令分派的次數(shù)可高達(dá)數(shù)百億次。因此優(yōu)化后，可以減少千億條數(shù)量級(jí)機(jī)器指令的執(zhí)行，從而大幅度提高指令分派的效率。

3.3 基于硬件支持的訪(fǎng)存加速策略

由3.2節(jié)中的分析可知，為了獲取Entry的值，需要訪(fǎng)問(wèn)地址為gpr+row_offset+col_offset的內(nèi)存單元。其中g(shù)pr為基址寄存器，保存指令分派表的起始地址；row_offset為索引寄存器，保存待查詢(xún)的行的索引；col_offset為一個(gè)較小的立即數(shù)，表示目標(biāo)單元在行內(nèi)的偏移。由于MIPS等精簡(jiǎn)指令集的處理器僅支持“基址+偏移”的尋址方式，故上述操作需要兩條機(jī)器指令(圖7中第2、3條)才能完成。

為了進(jìn)一步加快指令分派的速度，本文對(duì)處理器的訪(fǎng)存指令進(jìn)行了擴(kuò)展，新引入了一種支持“基址+索引+偏移”的尋址方式的訪(fǎng)存指令，使得對(duì)Entry值的加載操作僅由一條指令即可完成，從硬件層面直接加速指令分派時(shí)對(duì)內(nèi)存地址gpr+row_offset+col_offset的訪(fǎng)問(wèn)速度。其硬件實(shí)現(xiàn)原理如圖8所示。擴(kuò)展指令的實(shí)現(xiàn)主要涉及對(duì)處理器流水線(xiàn)中指令譯碼器、寄存器重命名單元和訪(fǎng)存部件的擴(kuò)展。由于擴(kuò)展的訪(fǎng)存指令使用了新定義的指令操作碼，指令譯碼器需增加對(duì)擴(kuò)展指令的譯碼功能。同時(shí)，由于擴(kuò)展指令中編碼了基址寄存器、索引寄存器和結(jié)果寄存器，故在流水線(xiàn)的寄存器重命名階段需要對(duì)三個(gè)寄存器進(jìn)行重命名，從而將指令中編碼的三個(gè)寄存器分別映射到物理寄存器堆中相應(yīng)的物理寄存器上。此外，由于訪(fǎng)存的有效地址計(jì)算需要對(duì)“基址+索引+偏移”進(jìn)行求和運(yùn)算，故訪(fǎng)存部件中原有的雙操作數(shù)地址運(yùn)算單元也需要進(jìn)行簡(jiǎn)單的擴(kuò)展，以支持3操作數(shù)的求和運(yùn)算。最后，根據(jù)有效地址完成相應(yīng)的訪(fǎng)存操作，并將訪(fǎng)存結(jié)果寫(xiě)回結(jié)果寄存器中。擴(kuò)展指令的硬件邏輯簡(jiǎn)單，實(shí)現(xiàn)代價(jià)低，很容易在各種處理器中實(shí)現(xiàn)。

圖8 擴(kuò)展訪(fǎng)存指令的硬件實(shí)現(xiàn)原理

在MIPS架構(gòu)中，指令編碼長(zhǎng)度固定為32位。原有的訪(fǎng)存指令(如ld指令等)最大僅支持16位的偏移量。而擴(kuò)展的訪(fǎng)存指令中需要額外使用5位用于對(duì)新增的索引寄存器進(jìn)行編碼，故無(wú)論擴(kuò)展的訪(fǎng)存指令如何設(shè)計(jì)，其所支持的偏移量最大不能超過(guò)16-5 = 11位。由3.1節(jié)中的分析可知，優(yōu)化前的指令分派表要求訪(fǎng)存指令中的偏移量不少于12位，因此，本文對(duì)原有指令分派表的行和列進(jìn)行了轉(zhuǎn)置。轉(zhuǎn)置后，即使對(duì)于64位的系統(tǒng)，指令分派表行內(nèi)偏移的取值范圍是[0, 40]?[-26, 26-1]，故偏移量的編碼只需要7位，滿(mǎn)足了硬件擴(kuò)展的約束。

基于上述分析，我們總共實(shí)現(xiàn)了12條擴(kuò)展的訪(fǎng)存指令，包含8條定點(diǎn)指令和4條浮點(diǎn)指令，尋址方式均為“基址+索引+偏移”的訪(fǎng)存模式。上述擴(kuò)展指令分別為存取字節(jié)(gssbx/gslbx)、存取半字(gsshx/gslhx)、存取字(gsswx/gslwx)、存取雙字(gssdx/gsldx)、存取單精度浮點(diǎn)數(shù)(gsswxc1/gslwxc1)和存取雙精度浮點(diǎn)數(shù)(gssdxc1/gsldxc1)。這些指令均支持長(zhǎng)度為8位的訪(fǎng)存偏移量，完全滿(mǎn)足優(yōu)化后指令分派表訪(fǎng)問(wèn)時(shí)對(duì)7位偏移的需求。

圖9展示了添加了硬件支持后，指令分派的實(shí)現(xiàn)方案。圖中使用了一條擴(kuò)展訪(fǎng)存指令gsldx，用于從內(nèi)存中加載一個(gè)64位的雙字。對(duì)比圖7可以看出，加載Entry的操作由圖7中的兩條機(jī)器指令減少為圖9中的一條gsldx指令即可完成。由于gsldx與原有64位訪(fǎng)存加載指令ld所需的執(zhí)行周期相同，故擴(kuò)展指令的引入可以消除一條加法指令daddu，從而進(jìn)一步提高指令分派的效率。

圖9 軟硬件協(xié)同的指令分派

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)平臺(tái)

為了驗(yàn)證本文方法的有效性，本研究在OpenJDK8[13]HotSpot虛擬機(jī)的解釋器上,采用業(yè)界廣泛使用的SPECjvm98和DaCapo-9.12-bach測(cè)試集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中，SPECjvm98和DaCapo的輸入規(guī)模分別設(shè)為最大值100和默認(rèn)大小。由于DaCapo中batik和eclipse引用了與OpenJDK8不兼容的低版本類(lèi)庫(kù)，因此本文將這兩個(gè)測(cè)試項(xiàng)排除在外。

實(shí)驗(yàn)中使用的硬件平臺(tái)為MIPS兼容的龍芯3號(hào)處理器，主頻900MHz，內(nèi)存4G，操作系統(tǒng)為64位的CentOS 6.4。本研究進(jìn)行了以下3組對(duì)比試驗(yàn)：

(1)傳統(tǒng)的實(shí)現(xiàn)方案，即圖3中的方法；

(2)純軟件的優(yōu)化方案，即圖7中的方法；

(3)軟硬件協(xié)同的優(yōu)化方案，即圖9中的方法。

為了減小實(shí)驗(yàn)誤差，每個(gè)測(cè)試程序均運(yùn)行10次，取其均值作為最終的實(shí)驗(yàn)結(jié)果，并以傳統(tǒng)方案的結(jié)果為基準(zhǔn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了歸一化處理。

4.2 實(shí)驗(yàn)結(jié)果與分析

圖10展示了解釋器在三種方案下的總體性能。從圖中可以看出，相對(duì)于傳統(tǒng)方案，采用純軟件的優(yōu)化方案，解釋器總體性能提升幅度已高達(dá)8.3%。而增加硬件支持后，解釋器總體性能進(jìn)一步提升約3.2%，最終達(dá)到11.5%的總體性能提升。

圖10 三種方案下的解釋器總體性能

圖11展示了解釋器在三種方案下，SPECjvm98和DaCapo測(cè)試集的性能。圖中的數(shù)據(jù)表明，軟硬件協(xié)同的優(yōu)化使得絕大多數(shù)的測(cè)試項(xiàng)目獲得10%以上的性能提升，最高性能提升幅度高達(dá)15.4%。此外，從圖11中還可以看出，使用硬件支持，解釋器的性能可在純軟件優(yōu)化的基礎(chǔ)上進(jìn)一步提升約2%～5%的性能，故硬件支持是純軟件優(yōu)化的重要補(bǔ)充。因此，軟硬件協(xié)同設(shè)計(jì)的指令分派對(duì)解釋器性能的提升具有非常好的效果。

圖11 解釋器在SPECjvm98和DaCapo測(cè)試集上的性能

為了進(jìn)一步揭示解釋器性能提升的原因，本文從靜態(tài)和動(dòng)態(tài)兩個(gè)方面進(jìn)行分析。從靜態(tài)角度看，字節(jié)碼本地指令序列中，指令分派部分機(jī)器指令數(shù)目的減少是解釋器性能提升的根本原因。圖12展示了軟硬件協(xié)同優(yōu)化前后，指令分派在字節(jié)碼的本地指令序列中所占的比例。圖中的結(jié)果表明，優(yōu)化后指令分派的比例顯著下降。對(duì)于絕大多數(shù)字節(jié)碼，該比例下降幅度超過(guò)了50%，所有字節(jié)碼指令分派部分所占比例的幾何均值由原來(lái)的21.4%下降為9.9%，下降幅度高達(dá)53.7%。此外，指令分派部分機(jī)器指令數(shù)目的減少，使得所有字節(jié)碼的本地指令序列中機(jī)器指令的總數(shù)減少了6.7%，解釋執(zhí)行所需的存儲(chǔ)空間進(jìn)一步降低。指令分派中機(jī)器指令數(shù)目的大幅減少，從理論上證明了軟硬件協(xié)同設(shè)計(jì)對(duì)解釋器指令分派優(yōu)化的良好效果，并且預(yù)示著動(dòng)態(tài)執(zhí)行的機(jī)器指令數(shù)目的大幅減少。

圖12 軟硬件協(xié)同優(yōu)化前后指令分派在字節(jié)碼的本地指令序列中所占比例

從動(dòng)態(tài)角度看，運(yùn)行時(shí)實(shí)際執(zhí)行的機(jī)器指令數(shù)目的減少是解釋器性能提升的直接原因。表2展示了軟硬件協(xié)同優(yōu)化后，在SPECjvm98和DaCapo測(cè)試集上，解釋器運(yùn)行時(shí)減少執(zhí)行的機(jī)器指令數(shù)目。由表2的數(shù)據(jù)知，軟硬件協(xié)同優(yōu)化后，解釋器減少執(zhí)行的機(jī)器指令數(shù)目高達(dá)千億條的數(shù)量級(jí)，平均下降幅度為優(yōu)化前的16.67%，最高優(yōu)化幅度高達(dá)22.87%。實(shí)驗(yàn)結(jié)果與理論預(yù)期相符。由于軟硬件協(xié)同的優(yōu)化可以大幅度減少指令分派所執(zhí)行的機(jī)器指令數(shù)目，故能充分地優(yōu)化解釋器的性能。

表2 軟硬件協(xié)同優(yōu)化后減少執(zhí)行的機(jī)器指令

5 結(jié) 論

解釋器指令分派一直是影響解釋器性能最關(guān)鍵的因素。本文對(duì)解釋器指令分派的開(kāi)銷(xiāo)進(jìn)行了分析，指出對(duì)字節(jié)碼本地指令序列入口地址的獲取構(gòu)成了指令分派的瓶頸，并且有針對(duì)性地提出了一種采用軟硬件協(xié)同設(shè)計(jì)的指令分派優(yōu)化方案。該方案具體包括優(yōu)化的指令分派表設(shè)計(jì)、軟件優(yōu)化的指令分派表訪(fǎng)問(wèn)技術(shù)和基于硬件支持的訪(fǎng)存加速策略。試驗(yàn)結(jié)果表明，本文的方案大幅降低了指令分派的開(kāi)銷(xiāo)，有效提升了解釋器的性能。本文的方法通用性強(qiáng)，實(shí)現(xiàn)代價(jià)低，對(duì)于現(xiàn)代高性能解釋器的設(shè)計(jì)和優(yōu)化具有很好的借鑒意義。未來(lái)的工作將從軟硬件協(xié)同設(shè)計(jì)的角度出發(fā)，對(duì)高級(jí)語(yǔ)言虛擬機(jī)的動(dòng)態(tài)編譯系統(tǒng)和數(shù)組越界檢查等運(yùn)行時(shí)機(jī)制做進(jìn)一步的分析和優(yōu)化。

[1] Bell J R. Threaded code.CommunicationsoftheACM, 1973,16(6):370-372

[2] Casey K, Gregg D, Ertl M A, et al. Towards superinstructions for java interpreters. In: Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems, Vienna, Austria, 2003. 329-343

[3] Casey K, Ertl M A, Gregg D. Optimizingindirect branch prediction accuracy in virtual machine interpreters.ACMTransactionsonProgrammingLanguagesandSystems, 2007, 29(6):1-36

[4] Brunthaler S. Virtual-machine abstraction and optimization techniques.ElectronicNotesinTheoreticalComputerScience, 2009, 253(5):3-14

[5] Kulkarni P A. JIT compilation policy for modern machines. In: Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, New York, USA, 2011. 773-788

[6] Arnold M, Fink S J, Grove D, et al. A survey of adaptive optimization in virtual machines.ProceedingsoftheIEEE, 2005, 93(2):449-466

[7] Kotzmann T, Wimmer C, M?ssenb?ck H, et al. Design of the Java HotSpotTMclient compiler for Java 6.ACMTransactionsonArchitectureandCodeOptimization, 2008, 5(1):1-32

[8] Jantz M R, Kulkarni P A. Exploring single and multilevel JIT compilation policy for modern machines.ACMTransactionsonArchitectureandCodeOptimization, 2013, 10(4):1-29

[9] Mccandless J, Gregg D. Compiler techniques to improve dynamic branch prediction for indirect jump and call instructions.ACMTransactionsonArchitectureandCodeOptimization, 2012, 8(1):1-24

[10] 黃明凱, 劉先華, 譚明星等. 一種面向解釋器的間接轉(zhuǎn)移預(yù)測(cè)技術(shù). 計(jì)算機(jī)研究與發(fā)展, 2015, 52(1):66-82

[11] Rohou E, Swamy B N, Seznec A. Branch prediction and the performance of interpreters: Don’t trust folklore. In: Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, Washington, DC, USA, 2015. 103-114

[12] Ertl M A. Stack caching for interpreters. In: Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, New York, USA, 1995. 315-327

[13] Oracle. OpenJDK8. http://openjdk.java.net/projects/jdk8/: Oracle Corporation, 2014

An instruction dispatch approach using hardware-software co-design for interpreters

Fu Jie******, Jin Guojie****, Zhang Longbing*****, Wang Jian*****

(*University of Chinese Academy of Sciences, Beijing 100049)(**State Key Laboratory of Computer Architecture, Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100190)(***Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)(****Loongson Technology Corporation Limited, Beijing 100095)

To reduce the overhead caused by instruction dispatch to improve the performance of interpreters, an instruction dispatch approach based on hardware and software co-design is proposed. Its main idea is to eliminate the expensive operation of constant address loading by optimizing the instruction dispatch table in the aspect of sofware, and to acceleratethe speed of memory access under the support of hardware by enhancing the processor’s instruction set in the aspect of hardware. The hardware-software co-design can minimize the runtime overhead of instruction dispatch, thus improving the performance of interpreters. The experimental results showed that the proposed approach significantly improved the performance of interpreters. For benchmarks of SPECjvm98 and DaCapo, the overall performance of interpreters was improved by 11.5%, and the highest performance boost was up to 15.4%. The approach is highly versatile, easy to implement and can be applied to the design and implementation of high performance interpreters on mainstream processors.

interpreter, instruction dispatch, hardware and software co-design, virtual machine, optimization

10.3772/j.issn.1002-0470.2016.03.002

①?lài)?guó)家“核高基”科技重大專(zhuān)項(xiàng)課題(2009ZX01028-002-003， 2009ZX01029-001-003， 2010ZX01036-001-002， 2012ZX01029-001-002-002， 2014ZX01020201， 2014ZX01030101)，國(guó)家自然科學(xué)基金(61221062， 61133004， 61173001， 6123009， 61222204， 61432016)和863計(jì)劃(2012AA010901， 2013AA014301)資助項(xiàng)目。

2015-11-16)

②男，1987年生，博士生；研究方向：虛擬機(jī)，計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)；聯(lián)系人，E-mail: fujie@ict.ac.cn(