基于反饋的JCVM指令預調度方案

曹 曉，李 瑩

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

1 概述

Java Card是一種能運行Java小應用程序的智能卡，它以其多應用的支持、良好的安全特性、面向對象的編程環境、應用程序動態下載等優點得到快速發展，尤其是在金融領域中，隨著全球EMV(Europay MasterCard and VISA)遷移及國內金卡工程的大力推動，到2015年，我國新發行銀行卡將全面升級為IC卡，而目前金融類IC卡中，90%以上都是Java Card，所以其增長空間巨大。

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

2 相關工作

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

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

3 基于反饋的JCVM預調度

3.1 Java Card解釋器運行架構

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

圖1 JCVM解釋器控制流圖

3.2 解釋器預調度的動機

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

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

3.3 解釋器預調度的形式化定義

針對JCVM指令預調度，下述公式給出了形式化定義和說明：

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

至此，給出基于反饋的JCVM解釋器指令預調度的定義：為使得整個應用的指令距離開銷最小，找到合適的指令處理函數重編排方案。采取基于應用反饋的方案，即根據應用的運行時指令流統計信息，得到適當的熱點指令集H，對 H中的指令處理函數采用指令預調度算法進行重新編排，調整JCVM指令處理函數的地址分布，使得應用的指令距離開銷最小。

4 基于反饋的JCVM指令預調度

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

圖2 JCVM指令預調度模型

4.1 運行時指令信息收集

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

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

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

圖3 JavaPurse程序的運行加權控制流圖

4.2 指令預調度算法

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

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

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

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

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

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

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

在JavaPurse程序的指令流加權控制流圖上運行上述算法，可得其熱點指令處理函數的重配置方案如表 1所示。按照表 1中順序重新編排目標體系中的相關指令函數的二進制分布，即可得到本文算法的優化系統。

表1 JavaPurse程序解釋器指令預調度配置

5 實驗與方案評估

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

實驗(1)的結果如表 2、表 3所示，在使用本文算法進行優化后，系統運行JavaPurse應用程序的綜合性能提升了15.29%；而對Java Card平臺標準測試用例的綜合性能提升也達到了12.5%。

表2 系統優化前后JavaPurse執行時間對比

表3 系統優化前后的Java Card標準樣例執行時間對比

實驗(2)的結果如圖4所示，顯示了本文系統(MyCard)與5種常見的商用卡片執行JavaPurse應用的性能對比，由于本文系統運行于開發板上，實際掩膜卡的性能應當提升50%左右，因此圖4中數據已據此進行了縮放。

圖4 JavaPurse執行性能對比

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

6 結束語

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

[1]王 濤, 毛志剛, 葉以正.一種Java IC卡專用CPU結構研究[J].電子學報, 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虛擬機性能優化技術研究[J].小型微型計算機系統,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.