曹 晓，李 莹

(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.