论文研究 降低函数调用分支别名的神经网络预测器.pdf

通过对程序调用过程中分支预测空间特性的分析，发现传统神经网络算法在不同函数调用相同子函数时容易出现别名效应，进而提出了一种基于子函数权重索引离散的神经网络分支预测器。该预测器通过调用信息堆栈记录函数调用中的父函数的路径信息，并用该信息离散子函数权重索引，有效降低了由于不同父函数调用相同子函数造成的别名效应。实验结果显示，基于该方法的神经网络分支预测器的预测错误率降低1%。第6期沙子岩,等:降低函数调用分支别名的神经网络预测器2049表如下entry[ func_ptr]=informationAND:1&1=1,1&0=0,0&0=0,0&1=0/函数返回时,执行出栈操作,栈顶指针减1OR:01=1,110=1,010=0,11=1if( fiXOR:1A0=10A1=11A1=00A0=0fune_plr =fun-1: kinfunctionA:0+1=11+0=10+0=01+1=(1)0由真值表可见,A\D逻辑存在0与任何值运算都是0的lew_index old_index mix entry[ func_ptr性质,导致混合后的新索引信息的各位是0的可能性加大。假weight weight_entry new_index设所有位在信息混合前的状态完全随机,这样新的索引方式在endtunction索引预测信息时会倾向于访问少数信息空间,从而引人新的别其中: Inc_plr为函数指针,表示调用信息堆栈的栈顶指针;数名效应,所以AND逻辑不是最佳的信息混合函数。基丁同样组mny表示洞用信息堆栈的信息存放入口; weight_entry为的原理,OR逻辑,由于存在1与任何值运算都是1的性质,也权重信息的存放入口。在系统初始化时栈顶指针复位,每次函同样不适于成为信息混合函数。根据真值表的结果,全加器和数调用时指针加1并存储空间信息,在函数返回时清除函数对应的空间信息,指针减1。其中,预测中父函数特征信息与原按位异或运算不会产生额外的别名效应,因而均满足信息混合有索引向量进行信息混合,得到新的权重索引向量函数的基本要求,但是全加器的位数也会随着分支预测历史长改进后的path-base预测器的权重索引机制硬件实现如图度的加长而相应增长,在硬件上造成电路的复杂度提高,时序2所示。性能的逐渐变差;而按位异或逻辑则不会岀现分支历史变长造凶数函数词用返回权重堆成的种种弊端,所以在硬件实现上相对全加逻辑更有优势。基于以上分析,本文将重点研究比较以地址或路径作为父函数特征信息,以XOR和FA作为混合函数的子函数离散算法。OO ADDR特征信息aDDR3算法实现LADDR基木ADDR索引函数为了实现子函数离散算法,个文对传统的path-base神经数调用难栈图2信息调用堆栈和信息混合的使件结构络分支预测算法的权重索引机制进行基于」两数权重索引离散算法的改造,在原有算法屮加入了父函数特征信息储存和4实验与结论索引信息混合(产生新的权重索引向量)的关键逻辑用于产生新的权重索引向量。4.1实验环境介绍为∫记录函数调用的父函数特征信息,并且在预测中进行本文选择嵌入式基准程序 PowerStone进行算法的模拟实有效的管理,本文在原来的算法模块中加入了调用信息堆栈。验,研究采用不同离散算法下的分支预测准确率和基于了函数用信息堆栈在昞数调用时进行压栈操作,将特征信息加以记权重索引离散的神经网络分支预测器的预测准确率。表1给录。在函数返回时,恢复原有特征信息。其中,函数调用和返出了PwSo所包含的测试程序的总指令条数及其分支的回的相关信息来自处理器本身对函数调用和返回相关指令的比例识别。本文采用 CKCORE指令集架构,函数调用采用jsni和表1 PowerStone测试基准简介jsr指令,两数返回采用 jmp rl5指令。处理器在 sh\st指令执测试总指条条件跳转测试总指令条件跳转数指令条数程序条数指令条行完毕后,则通知分支预测器的调用信息堆栈进行了函数调用jpg9071462234152 engine74978533692操作。执行jprl5指令后,通知调用信息堆栈执行响数返回V42530592336649mprs2837514806操作3fax2775967168251在预测过稈中,调用信息堆栈取出当前指针所指地址的信息作为本次预测对应的函数调用特异信息,与原有索引信息进实验首先利用 CKCORE工具链和 CKCORE处理器行为模行信息混合后,成为新权重索引向量用于索引当前预测过程的型(ISA)编译运行相关 BenchMark,记录输出分支跳转信息,然权重。信息调用堆栈的功能用仍代码描述如下:后编写相关分支预测器软件模型,在分支预测器仿真模拟中读function fuction_ call_return_manage;取分支跳转信息对分支顶测算法进行仿真。4.2四种离散算法的结果比较/初始化时通过系统复位信号,使栈顶指针复位为了更加有效地进行子函数离散,本文通过实验对特征信initiall息和混合函数进行进一步分析。备选的父函数特征信息有分func ptr=0/函数调用时,执行入栈操作,栈顶指针加1支地址(ADDR)和分支路径(PATH两种,备选的信息混合函f( function_call,数何括XOR和FA。实验中分别采用四种离散子函数分支预func_ptr= func_ptr+1测算法,四种算法的特征信息和混合函数分别是(ADDR,2050计算机应用研究OR)、(PATI,XOR)、(ADDR,FA)、(PATI,FA)。关系复杂度不一样,其性能改进也不一样,如调用关系简单的使用分支地址作为特征信息时,采用函数调用指令的指令jpeg,每个子函数都被一个父函数调用,其改进也越小(它们的pe;使用分支路径作为特征信息时,由于各个分支地址的位数降低来自于库函数的调用);与此相对的qut应用中,qurt子函较多,考虑到程序执行过程中高位地址不易改变,可以截取低数被多个函数调用,其采用改进后的预测算法对于性能提升也位拼成特征信息。夲文采用相同的硬件开销(感受器冇储空就越明显。通常情况下,函数调用关系越复杂,应用本文提出间32KB,历史长度32bt)进行模拟,四种算法在 PowerStone的降低函数调用分支别名神经网络感受器顶测准确率也就下预测失误率如图3所示。越高。LADDR+XORADDR+FA105结束语本文通过对稈序执行过稈的分析,发现了函数调用中出现的别名效应,提出了离散子函数索引的分支预测算法,并对算法中的离散函数和父数特征信息进行了理论和实验两个层jpeg v42 fir engine compress qurt次上的深入研究。离散子函数索引算法的相关实验结果表明,图3不同离散算法下的预测失误率采用ⅩOR算法和路径信息可以有效地解决数用过程中产从图3结果显示,采用分支路径信息与采用分支地址信生的别名效应,使分支预测的失误率明显下降,取得了预期的息作为父函数特征信息效果相当,囚而出于硬件设计简单的原效果。因可以采用地址作为父函数特征信息。结果还显示在信息混参考文献合函数中FA逻辑比ⅹOR逻辑略好。这是由于按位异或逻11 PATTY N, PATEL S J, FRIENDLY D H,cal. One billion tran是简化的无进位的全加逻辑,离散效果比全加逻辑略差;但是sis tars, one uniprocessor, one chip[ C]//Proe of IEEE ComputerXOR的硬件实现简单,仍然是信息混合函数的理想选择1997:51-5[2] SMITH JE. A sludy of braith predic Lion stralegies[ C]//Prve uf the4.3分支预测准确率分析8th International Symposium. Computer Architecture. 1981对path-base分支预测算法进行改造,加入调用信息堆栈3]PANs,sOK, RAHMEH J T. Improving the accuracy of dynamic管理父函数特征信息(地址),并使用XOR函数离散子函数索branch prediction using branch correlation[ C ]//Proc of the 5th In引,与原来的pth-base算法预测准确率对比如表2所示(硬件ternational Conference on Architectural Support for Programming Languages and Operating Systems. 1992: 76-8开销32KB,历史长度32bit)。4 YEH T Y, PATT Y N. Two-level adaptive branch prediction[ C]//表2预测钴误率模拟比较结果Proc of the 24th ACM/IEEE International Symposium Microarchitec-传统预测改进后预测预测错误率ture. 199 1稈序错误率/%错误率/%降低比例/[5 YEH TY, PATT Y N. Alternative implementations of two-level adap0.89tive branch prediction C]//Proc of the 19th Annual InternationalSymposium. Computer Architecture. 1992: 124-1347.197.10engine2.25I 6 JIMENEZ D A, LIN C. Neural methads for dynamic branch prediccor press8.938.218.06tion[J]. ACM Trans on Computer Systems, 2002, 20(4): 369-10.0512.07397表2结果显示,在算法中加入离散相关功能后,通过对子[7] JIMENEZ D A. Fast path-based neural branch prediction[C]//Procof the 36th International Symposium on Microarchitecture. 2003函数权重索引的离散实现子函数在不同的调用中具有不同的[8] TARJAN D, SKADRON D. Merging path and gshare indexing in per-感受器索引,消除函数调用过程中的别名效应。从数据来看,ception branch prediction[ J]. ACM Trans on Architecture and分支预测失误率大概下降了1%~10%。不同函数由丁调用Code Optimization, 2005, 2(3): 280-300.上接第2039页)机器人传感器的探测范围进行局部规划,很难the 3rd International Conference on Machine Learning and Cybernet-保证机器人所走的路径全局最优或较优,甚至易引起死锁和振ts.2004:2473-2478荡等。本文将蚂蚁算法、模拟退火算法、滚动规划和遗传算法[4]梁晓辉,吴威,赵沁大规模真实地形数据中的仝局路径规划方相结合,充分利用机器人实时探测到的局部环境信息,在滚动法——基于遗传算法的研究[冂].计算机研究与发展,2002.39窗口内局部快速规划,取得∫较好的效果。仿直实验表明该算51 KOENING S, LIHACHEV M, Fast replanning for navigati法可行有效,对不同复杂度的环境均具有较好的适应能力。known terrain[ J]. IEEE Trans on Robotics, 2005, 21(3): 354参考文献:[Il]张純刚,席裕庾.全局环境未知时基于滚动窗口的机器人路径规6]王雪松,高阳,程玉虎,等,知识引导遗传算法实现机器人路径规」划[冂].中国科学(E辑),2001,31(1):51-5划[J].控制与决策,2009,24(7):1043-10492]朱庆保。全局夫知腻境下多机器人运动妈蚁导毓算法[冂.软学[7] MAHIOUBI H, BAHRAMI E, LUCAS C. Path planning in an envi报,2006,19(9):1890-1898ronment with static and dynamic obstacles using genetic algorithm[3] QIN Yuan-qing. SUN De-bao. Path planning for mobile robot using[C]//Prue of IEEE Congress on Evolutionary Compu laLion. 2006: 16the particle swarm optimiz ation with mutation operator[ C]//Proc of21