基于反饋的JCVM指令預(yù)調(diào)度方案

曹 曉，李 瑩

(1.浙江大學(xué)計算機科學(xué)與技術(shù)學(xué)院，杭州 310027；2.中國人民解放軍94816部隊，福州 350002)

1 概述

Java Card是一種能運行Java小應(yīng)用程序的智能卡，它以其多應(yīng)用的支持、良好的安全特性、面向?qū)ο蟮木幊汰h(huán)境、應(yīng)用程序動態(tài)下載等優(yōu)點得到快速發(fā)展，尤其是在金融領(lǐng)域中，隨著全球EMV(Europay MasterCard and VISA)遷移及國內(nèi)金卡工程的大力推動，到2015年，我國新發(fā)行銀行卡將全面升級為IC卡，而目前金融類IC卡中，90%以上都是Java Card，所以其增長空間巨大。

Java Card是一種嵌入式系統(tǒng)，在資源極其受限的智能卡上實現(xiàn)一個Java運行時環(huán)境[1]，是Java技術(shù)和IC卡技術(shù)相結(jié)合的產(chǎn)物，極大推動了IC卡的發(fā)展及應(yīng)用開發(fā)，但同時Java Card的性能較差，同等條件下Java Card應(yīng)用執(zhí)行速度要比C語言寫的程序慢10倍～20倍[2]。因此，本文針對Java Card解釋器展開優(yōu)化研究工作，提出一個基于反饋的Java Card虛擬機(Java Card Virtual Machine, JCVM)指令預(yù)調(diào)度方案，利用應(yīng)用執(zhí)行的指令流統(tǒng)計信息反饋，對熱點指令處理函數(shù)在目標(biāo)體系中的分布進(jìn)行重新編排，使得高頻連續(xù)指令處理函數(shù)順序排布，以提高解釋器運行時的代碼局部性，減少 cache失配次數(shù)，提升 Java Card運行效率。

2 相關(guān)工作

針對Java Card性能優(yōu)化的研究工作主要集中在其運行架構(gòu)和文件格式等方面，文獻(xiàn)[3]設(shè)計了一種利用 RAM 作為緩存的Java Card應(yīng)用下載和安裝方案。文獻(xiàn)[4]提出一種新的Java Card存儲架構(gòu)，將EEPROM(Electrically Erasable Programmable Read-Only Memory)中的持久性對象緩存到RAM中運行。文獻(xiàn)[5]使用RAM作為緩存，設(shè)計了一種新的事務(wù)處理模型。以上方案都充分考慮了Java Card架構(gòu)及其硬件平臺的關(guān)系，使用高速的RAM作為低速的EEPROM的緩存，從而減少低速設(shè)備的操作次數(shù)以提高性能。文獻(xiàn)[6]使用字典映射算法對CAP文件進(jìn)行了壓縮優(yōu)化，提高了應(yīng)用下載效率及卡內(nèi)空間利用率。

針對 Java Card解釋器的優(yōu)化研究相對較少，文獻(xiàn)[7]提出一種 Annotation-aware解釋器，使用 Super Operators(SOs)來執(zhí)行字節(jié)碼，運行時將高頻連續(xù)指令流合并為一條指令執(zhí)行。文獻(xiàn)[8]重組了Java Card中的高頻重復(fù)出現(xiàn)的連續(xù)指令流，并將其定義為宏指令。上述 2種優(yōu)化方案的共同缺點是需要依賴卡外配套編譯器的支持，破壞了 Java Card平臺的通用性標(biāo)準(zhǔn)，而線索化解釋器[9]等性能良好的優(yōu)化方法由于較大的內(nèi)存消耗，因此無法在Java Card這樣的平臺上實現(xiàn)。

3 基于反饋的JCVM預(yù)調(diào)度

3.1 Java Card解釋器運行架構(gòu)

JCVM 解釋器是一個循環(huán)封閉的結(jié)構(gòu)，內(nèi)部包含一個字節(jié)碼分派結(jié)構(gòu)，其外層循環(huán)不斷地從程序字節(jié)碼流中讀取新的字節(jié)碼指令，然后按照指令分派結(jié)構(gòu)調(diào)用相應(yīng)的指令處理函數(shù)，實現(xiàn)字節(jié)碼指令的功能性要求，其控制流圖(Control Flow Graph, CFG)如圖1所示，可以將解釋器的運行分為3個主要階段，即取指令(Fetching Bytecode)、指令分派及運行(Dispatching and Execution)、回跳(Branching)。在指令分派階段，解釋器根據(jù)取到的指令碼來調(diào)用相應(yīng)的指令處理函數(shù)，Java Card2.2.2版有185個標(biāo)準(zhǔn)指令，每個指令對應(yīng)一個指令處理函數(shù)。

圖1 JCVM解釋器控制流圖

3.2 解釋器預(yù)調(diào)度的動機

對于傳統(tǒng)的編譯器優(yōu)化來說，重排程序的匯編指令順序以優(yōu)化其執(zhí)行效率是一種重要的優(yōu)化方法[10]。文獻(xiàn)[11]中研究了基于運行時指令信息統(tǒng)計的代碼編排技術(shù)，將執(zhí)行頻率很高的熱點代碼集中存放，提高了程序的局部性，以減少運行時的cache失配及跳轉(zhuǎn)開銷。從體系結(jié)構(gòu)層面上來說，程序運行的目標(biāo)機的體系架構(gòu)是固定不變的，優(yōu)化方法是改變程序的結(jié)構(gòu)，挖掘程序的并行性及局部性等方法加速程序的執(zhí)行。

而對解釋器的優(yōu)化來說，可以將解釋器看作前面所述的目標(biāo)機體系架構(gòu)，其中應(yīng)用程序是固定的，而目標(biāo)機體系架構(gòu)則是可變的，可以對其體系架構(gòu)進(jìn)行優(yōu)化以適應(yīng)應(yīng)用程序的特點，相當(dāng)于在應(yīng)用程序不變的前提下改變其目標(biāo)機架構(gòu)。本文針對解釋器的運行架構(gòu)，將類似于文獻(xiàn)[11]中的代碼編排技術(shù)引入到解釋器的優(yōu)化中，提出了一個指令預(yù)調(diào)度算法，對解釋器的指令處理函數(shù)進(jìn)行調(diào)度，重新編排其代碼布局，使得在執(zhí)行某一類程序時，解釋器在運行過程中體現(xiàn)出高度的局部性，從而減少cache失配及跳轉(zhuǎn)開銷，提高運行效率。

3.3 解釋器預(yù)調(diào)度的形式化定義

針對JCVM指令預(yù)調(diào)度，下述公式給出了形式化定義和說明：

式(1)給出了一個解釋器指令集的形式化描述，JCVM解釋器 I中包含 n條指令i0i1…in，及其相應(yīng)的指令處理函數(shù)物理地址 a0a1…an；式(2)和式(3)給出了運行時指令執(zhí)行信息收集方法的形式化說明，其中，P是一個二元組的列表，用于記錄在解釋器運行期間執(zhí)行過的指令流信息，包括應(yīng)用運行過程中解釋器解釋執(zhí)行過的指令及其處理函數(shù)的地址，T是一個三元組列表，表示 P的統(tǒng)計信息，即應(yīng)用所運行指令的統(tǒng)計次數(shù)，H用于收集熱點指令集，類似于JIT中熱點代碼區(qū)域，H是T的子集，僅包含執(zhí)行頻率不小于閾值L的指令信息；式(4)給出了指令相對距離及整個應(yīng)用的指令距離開銷的計算方法，其中的S(Pi)及S(Pj)分別表示指令Pi及Pj的指令處理函數(shù)的二進(jìn)制大小，在應(yīng)用執(zhí)行產(chǎn)生的順序指令流中，將所有前一個指令和下一個指令之間的相對距離求和，即可得到該應(yīng)用程序執(zhí)行時的指令距離開銷。

至此，給出基于反饋的JCVM解釋器指令預(yù)調(diào)度的定義：為使得整個應(yīng)用的指令距離開銷最小，找到合適的指令處理函數(shù)重編排方案。采取基于應(yīng)用反饋的方案，即根據(jù)應(yīng)用的運行時指令流統(tǒng)計信息，得到適當(dāng)?shù)臒狳c指令集H，對 H中的指令處理函數(shù)采用指令預(yù)調(diào)度算法進(jìn)行重新編排，調(diào)整JCVM指令處理函數(shù)的地址分布，使得應(yīng)用的指令距離開銷最小。

4 基于反饋的JCVM指令預(yù)調(diào)度

本文給出一個基于反饋的JCVM解釋器指令預(yù)調(diào)度的具體實施方案，模型如圖 2所示，實線箭頭流程表示了原JCVM 系統(tǒng)的編譯運行及指令信息收集和指令預(yù)調(diào)度算法的工作過程，虛線箭頭表示了調(diào)度算法的反饋及新系統(tǒng)的編譯生成過程。首先使用原始JCVM系統(tǒng)運行程序進(jìn)行運行時指令信息收集，然后在此基礎(chǔ)上使用相關(guān)算法得到指令處理函數(shù)的重配置方案，最后按此方案重新編譯原始系統(tǒng)即完成優(yōu)化工作。該方案的核心在于應(yīng)用的運行時指令信息收集和指令預(yù)調(diào)度算法，即如何統(tǒng)計得出熱點指令集H和基于此指令集的預(yù)調(diào)度配置的生成。

圖2 JCVM指令預(yù)調(diào)度模型

4.1 運行時指令信息收集

由于Java Card在金融領(lǐng)域應(yīng)用潛力巨大，因此本文選擇Java Card電子錢包應(yīng)用JavaPurse作為反饋應(yīng)用進(jìn)行指令執(zhí)行信息收集，JavaPurse是Sun公司為Java Card平臺提供的標(biāo)準(zhǔn)金融卡程序，與現(xiàn)實使用的銀行卡應(yīng)用程序在代碼邏輯上具有很大的相似之處，作為金融類應(yīng)用也比較有代表性。

操作中需要修改 JCVM 解釋器以追蹤指令流執(zhí)行情況，在程序運行期間共執(zhí)行字節(jié)碼指令211641個，在Java Card2.2.2版的185條標(biāo)準(zhǔn)指令中，有94條指令得到運行，剩余指令在本程序中未運行過，統(tǒng)計執(zhí)行次數(shù)超過2000次的前29條指令可得出，其執(zhí)行頻率達(dá)到總指令執(zhí)行次數(shù)的87.74%，這個結(jié)果比較符合標(biāo)準(zhǔn)版Java指令的執(zhí)行統(tǒng)計規(guī)律，因此，將這29條指令定義為熱點指令集H。

將指令執(zhí)行流程以控制流圖的方式展現(xiàn)出來，由于解釋器的控制流圖比較特殊，不能提供程序運行時動態(tài)數(shù)據(jù)，因此本文提出加權(quán)控制流圖(Weighted Control Flow Graph,WCFG)的概念，利用運行時收集到的動態(tài)指令流信息構(gòu)建一個帶權(quán)重的雙向有向圖，將指令的動態(tài)執(zhí)行流程描述到一個控制流圖中，構(gòu)建JavaPurse程序的執(zhí)行WCFG如圖3所示，圖中頂點表示指令名稱，箭頭表示指令流執(zhí)行順序，權(quán)重表示執(zhí)行次數(shù)，為了清晰起見，圖 3中僅顯示了權(quán)重大于3000的邊。

圖3 JavaPurse程序的運行加權(quán)控制流圖

4.2 指令預(yù)調(diào)度算法

在得到程序的加權(quán)控制流程圖后，找到一個最佳的指令重編排方案就變成了一個圖論問題。本文試圖找到一個頂點遍歷過程，使得權(quán)重的遍歷代價最高，類似于非對稱性旅行商[12]問題，但由于WCFG是不完備圖，又類似于漢密爾頓路徑問題，但又都不相同，因此給出一個遍歷算法，具體如下：

(1)令JavaPurse程序的指令流加權(quán)控制流圖為G，遍歷G，建立一個鏈表resource，鏈表元素為29個指令節(jié)點，首先按節(jié)點的加權(quán)出度和降序排列resource，然后從resource的第 2個元素開始按照節(jié)點的加權(quán)入度和降序排列，對加權(quán)入度和相等的節(jié)點元素，如有邊相連則按其指向關(guān)系排列；建立一個空鏈表 goal，其元素為指令節(jié)點，用來保存算法調(diào)度結(jié)果。

(2)取resource鏈表中第一個元素，并在resource中將其刪除，檢查其中包含的指令節(jié)點是否存在于鏈表goal中，如果不存在，則將此指令節(jié)點插入鏈表goal的表尾，繼續(xù)步驟(3)，否則重復(fù)步驟(2)。

(3)令鏈表goal中的表尾節(jié)點元素為P，查找節(jié)點P的后繼節(jié)點S，在圖G中定位到節(jié)點P，將P所指向的節(jié)點按權(quán)重降序排列，記為set。

(4)從set中依次取出節(jié)點，令其為T，判斷T是否可以作為P的后繼節(jié)點S：如果T已存在于鏈表goal中，則重復(fù)步驟(4)；如果T不存在于鏈表goal中，則繼續(xù)步驟(5)；如果set集合為空，則重復(fù)步驟(2)。

(5)將T插入鏈表goal的表尾，重復(fù)步驟(3)。

算法總是從出度最大的節(jié)點開始，類似于經(jīng)典的最近鄰居貪心算法，不斷地尋找當(dāng)前節(jié)點執(zhí)行頻率最高的后繼節(jié)點。算法的特殊性在于：(1)可以重復(fù)地遍歷某個節(jié)點；(2)基于WCFG的不完備性，算法可能到達(dá)一個死節(jié)點，此時算法從 resource列表中取得新節(jié)點并繼續(xù)運行；(3)算法的搜索順序保證了直接可達(dá)節(jié)點擁有更高的優(yōu)先級。這就保證了WCFG遍歷的權(quán)重代價最高，且符合反饋應(yīng)用的指令執(zhí)行統(tǒng)計特性。

在JavaPurse程序的指令流加權(quán)控制流圖上運行上述算法，可得其熱點指令處理函數(shù)的重配置方案如表 1所示。按照表 1中順序重新編排目標(biāo)體系中的相關(guān)指令函數(shù)的二進(jìn)制分布，即可得到本文算法的優(yōu)化系統(tǒng)。

表1 JavaPurse程序解釋器指令預(yù)調(diào)度配置

5 實驗與方案評估

為了對基于反饋的JCVM指令預(yù)調(diào)度算法性能做出直觀分析，將實驗分為兩部分：(1)Java Card系統(tǒng)在應(yīng)用本文算法前后的運行性能對比測試；(2)選取目前5種典型的商用Java Card產(chǎn)品，與本文算法優(yōu)化過的系統(tǒng)做性能對比測試。系統(tǒng)運行于上海華虹公司SHC1302N開發(fā)板，采用ARM SC100內(nèi)核，源碼由SUN Java Card 2.2.2參考實現(xiàn)移植，并實現(xiàn)了本文優(yōu)化算法。

實驗(1)的結(jié)果如表 2、表 3所示，在使用本文算法進(jìn)行優(yōu)化后，系統(tǒng)運行JavaPurse應(yīng)用程序的綜合性能提升了15.29%；而對Java Card平臺標(biāo)準(zhǔn)測試用例的綜合性能提升也達(dá)到了12.5%。

表2 系統(tǒng)優(yōu)化前后JavaPurse執(zhí)行時間對比

表3 系統(tǒng)優(yōu)化前后的Java Card標(biāo)準(zhǔn)樣例執(zhí)行時間對比

實驗(2)的結(jié)果如圖4所示，顯示了本文系統(tǒng)(MyCard)與5種常見的商用卡片執(zhí)行JavaPurse應(yīng)用的性能對比，由于本文系統(tǒng)運行于開發(fā)板上，實際掩膜卡的性能應(yīng)當(dāng)提升50%左右，因此圖4中數(shù)據(jù)已據(jù)此進(jìn)行了縮放。

圖4 JavaPurse執(zhí)行性能對比

由圖4可知，MyCard系統(tǒng)總體性能還是比較弱的，只是在密碼修改(Modify PIN)操作上表現(xiàn)最好，處于第1位；在密碼驗證(Verify PIN)、存錢(Credit)和取錢(Debit)操作上僅領(lǐng)先C5卡；而在應(yīng)用選擇(Select JavaPurse)、讀余額(Read Balance)、讀日志文件(Read Logfiles)這3個操作中均表現(xiàn)最差。從綜合性能上來說，MyCard處于倒數(shù)第2位，原因是成熟的商用卡片都采用了大量的優(yōu)化方法，尤其是許多針對硬件的優(yōu)化可以大幅提升性能，而MyCard僅是測試了基于反饋的JCVM指令預(yù)調(diào)度算法的效果，因此，單憑本文算法已經(jīng)使得MyCard具備了一定的市場競爭力，說明本文算法的效果較好。

6 結(jié)束語

應(yīng)用執(zhí)行的性能直接影響Java Card的用戶體驗，也是其進(jìn)一步發(fā)展的關(guān)鍵，傳統(tǒng)Java Card優(yōu)化方法對JCVM解釋器的研究較少，受制于卡內(nèi)資源，多數(shù)成熟的解釋器優(yōu)化方法無法在Java Card上實現(xiàn)。而本文提出的基于反饋的JCVM 指令預(yù)調(diào)度方案，不依賴于額外的體系開銷，可以很好地應(yīng)用于Java Card等資源受限的嵌入式系統(tǒng)中，有效地提高了解釋器的運行時的代碼局部性、cache命中率以及系統(tǒng)整體性能。

[1]王 濤, 毛志剛, 葉以正.一種Java IC卡專用CPU結(jié)構(gòu)研究[J].電子學(xué)報, 2000, 28(11): 77-80.

[2]Oestreicher M.Tramactiorm in Java Card[C]//Proc.of the 15th Annual Computer Security Application Conference.Phoenix,USA: [s.n.], 1999: 291-298.

[3]Choi Won-Ho, Oh Se-Won, Jung Gwang, et al.A Novel Scheme for Efficient Installation of Applets for Advanced Java Card System[C]//Proc.of 2009 World Congress on Computer Science and Information Engineering.Los Angeles, USA:[s.n.], 2009.

[4]Yang Yoon-Sim, Choi Won-Ho, Jin Min-Sik, et al.An Advanced Java Card System Architecture for Smart Card Based on Large RAM Memory[C]//Proc.of 2006 International Conference on Hybrid Information Technology.[S.l.]: IEEE Press, 2006.

[5]Loinig J, Steger C, Weiss R, et al.Java Card Performance Optimization of Secure Transaction Atomicity Based on Increasing the Class Field Locality[C]//Proc.of the 3rd International Conference on Secure Software Integration and Reliability Improvement.Washington D.C., USA: [s.n.],2009: 342-247.

[6]Kim Do-Woo, Jung Min-Soo.A Study on the Optimization of Class File for Java Card Platform[C]//Proc.of International Conference on Information Networking, Wireless Communications Technologies and Network Applications.London,UK: Springer-Verlag, 2002: 563-570.

[7]Azevedo A, Kejariwal A, Veidenbaum A, et al.High Performance Annotation-aware JVM for Java Cards[C]//Proc.of the 5th ACM International Conference on Embedded Software.New York, USA: ACM Press, 2005: 52-61.

[8]Jin Min-Sik, Jung Min-Soo.A Study on How to Reduce Time and Space by Redefining New Bytecode for Java Card[C]//Proc.of the 11th IEEE International Conference on Embedded and Real-time Computing Systems and Applications.Hong Kong, China: [s.n.], 2005: 551-554.

[9]李 允, 羅 蕾, 雷昊峰, 等.基于線索化方法的嵌入式Java虛擬機性能優(yōu)化技術(shù)研究[J].小型微型計算機系統(tǒng),2005, 26(3): 439-442.

[10]Franke B, O’Boyle M, Thomson J, et al.Probabilistic Source Level Optimization of Embedded Programs[C]//Proc.of 2005 ACM SIGPLAN/SIGBED Conference on Languages,Compilers, and Tools for Embedded Systems.Chicago, USA:[s.n.], 2005.

[11]Pettis K, Hansen R C.Profile Guided Code Positioning[C]//Proc.of ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation.New York, USA: ACM Press, 1990: 16-27.

[12]Mak V, Boland N.Polyhedral Results and Exact Algorithms for the Asymmetric Travelling Salesman Problem with Replenishment Arcs[J].Discrete Applied Mathematics, 2007,155(16): 2093-2110.