一種多線程動態(tài)制譯系統(tǒng)優(yōu)化設(shè)計

一種多線程動態(tài)制譯系統(tǒng)優(yōu)化設(shè)計

1mdos系統(tǒng)的主要貢獻動態(tài)二進制dbt的提取。由于動態(tài)二進制翻譯存在著翻譯速度慢、代碼膨脹冗余等問題,如何提升翻譯性能,使得二進制翻譯更好地為軟件跨平臺移植服務,成為一個熱點研究的問題.HsuChun-chen等人提出一種針對優(yōu)化熱路徑識別的EEG隨著多核處理器技術(shù)的不斷發(fā)展,研究人員設(shè)想通過多線程技術(shù),在二進制翻譯中充分利用多核處理器的并行運算能力,進而達到提升翻譯性能的目的.1999年KanemitsuOot-su在此背景下,本文遵循多線程的主體思路,基于用戶級QEMU開發(fā)了一種多線程的動態(tài)二進制翻譯優(yōu)化系統(tǒng)MDOS(Multi-threadedDynamicbinarytranslationOptimizationSystem).MDOS系統(tǒng)由前端翻譯執(zhí)行模塊和后端優(yōu)化模塊兩部分組成,前后端分別放置于不同的線程中,前端依據(jù)程序局部熱路徑預測算法進行熱路徑選擇識別,后端則通過超級塊處理本文工作的主要貢獻如下:1)開發(fā)了一款基于用戶級QEMU的動態(tài)二進制翻譯優(yōu)化系統(tǒng),系統(tǒng)利用多線程技術(shù),將翻譯執(zhí)行和優(yōu)化放置不同的線程中,避免了優(yōu)化加重翻譯執(zhí)行開銷等問題.2)依據(jù)程序局部性原理,系統(tǒng)前端運用熱路徑局部預測算法,較好地解決了循環(huán)體中熱路徑的識別問題.3)系統(tǒng)后端運用超級塊封裝和條件跳轉(zhuǎn)優(yōu)化,提升了本地生成碼的質(zhì)量和執(zhí)行速度.2反匯編破產(chǎn)QEMUQEMU進行二進制翻譯的關(guān)鍵是使用了TCG(TinyCodeGenerator)翻譯機制.TCG是由一個C語言編譯器后端簡化而來的動態(tài)代碼生成器,主要負責分析、優(yōu)化目標代碼以及生成本地碼.QEMU動態(tài)翻譯的方法是把每一條目標指令切分為若干條微操作,每條微操作由一段簡單的C語言函數(shù)組合實現(xiàn),運行時通過動態(tài)代碼生成器TCG對這些微操作進行組合.這種方法的原理是由于CPU指令規(guī)律性強,每條指令的長度、操作碼、操作數(shù)都有固定格式,并遵循不同平臺的指令規(guī)律,QE-MU僅需通過反匯編分析出指令的操作碼、輸入?yún)?shù)、輸出參數(shù)等信息,就可利用所獲取信息進行本地代碼編寫.QEMU基本結(jié)構(gòu)如圖1所示.QEMU通過控制中心(con-trollercenter)加載可執(zhí)行的ELF文件,并找到程序執(zhí)行的入口點,反匯編模塊根據(jù)目標平臺指令特征將二進制文件中的指令反匯編,分解成更小的指令,然后TCG通過微操作庫對應的中間指令將反匯編得到的指令分解成相應的微操作,鏈接器將微操作進行組裝生成本地執(zhí)行碼,再由核心控制中心提交到本地操作系統(tǒng)執(zhí)行,同時將翻譯完成的基本塊放入T-cache中以備下次使用查找.QEMU通過循環(huán)以上流程,進行基本塊的動態(tài)翻譯和存取,最終實現(xiàn)目標代碼的本地執(zhí)行.QEMU的設(shè)計目的在于順利完成平臺之間程序的翻譯執(zhí)行,在生成本地碼的優(yōu)化方面并未進行過多改進.QEMU翻譯執(zhí)行的基本單位是基本塊TB(TranslationBlock),在翻譯和調(diào)用基本塊時QEMU必須提取和保存現(xiàn)場寄存器快照,保持程序翻譯的上下文的連續(xù)性,但是由于QEMU一次只能執(zhí)行一個基本塊,反復地存取現(xiàn)場快照,不僅造成大量的冗余指令被留存在本地生成碼中,導致代碼膨脹率和冗余度過大,降低了代碼品質(zhì),也加重了翻譯系統(tǒng)本身的運行開銷,嚴重影響了翻譯效率.目前已有的針對QEMU的優(yōu)化手段,例如冗余指令消除、寄存器映射優(yōu)化、T-cache優(yōu)化等策略,也是基于串行模式進行,QEMU自身存在的性能缺陷問題并未得到有效解決.采用多線程手段,將翻譯執(zhí)行過程和優(yōu)化過程在運行時進行相對隔離,既不會增加二進制翻譯器本身在翻譯和執(zhí)行時的管理開銷,也達到了代碼優(yōu)化的目的,對于二進制翻譯性能的提升意義重大.本文依據(jù)這一思路進行了動態(tài)二進制翻譯優(yōu)化系統(tǒng)的研究與實現(xiàn).3mdos系統(tǒng)和cache分層協(xié)同過程中,mdos系統(tǒng)出現(xiàn)了較低和二元不轉(zhuǎn)為提高二進制翻譯性能,需要在翻譯過程中對生成碼進行優(yōu)化.在串行模式下,優(yōu)化過程需要嵌入到翻譯過程中,因此優(yōu)化產(chǎn)生的開銷屬于翻譯執(zhí)行開銷的一部分,顯然進行優(yōu)化的過程影響了翻譯執(zhí)行性能.當優(yōu)化帶來的性能提升不能抵消開銷所帶來的負面影響時,優(yōu)化對于二進制翻譯性能的提升沒有任何意義.因此,如何能在較低翻譯執(zhí)行開銷的基礎(chǔ)上提升翻譯性能,是二進制翻譯面臨的一個重要問題.為解決這一問題,本文基于多線程框架設(shè)計并實現(xiàn)了動態(tài)二進制翻譯系統(tǒng)MDOS.系統(tǒng)引入超級塊封裝和條件跳轉(zhuǎn)優(yōu)化,并采用cache分層管理機制,在盡可能不增加QEMU翻譯執(zhí)行開銷的基礎(chǔ)上提升二進制翻譯性能.3.1熱路徑局部預測算法MDOS系統(tǒng)熱路徑識別采用局部預測算法.采用局部預測算法的目的,是對現(xiàn)有翻譯平臺QEMU的功能進行拓展,實現(xiàn)熱路徑的識別和重定向,向后端優(yōu)化過程提供熱路徑源.程序局部性原理指出,程序在執(zhí)行過程中,20%的代碼占用了80%的執(zhí)行時間.遵循這一原理,算法的基本思想是采取“先熱先選擇”的策略,預測前提是一個熱度高的路徑頭則意味著其后的區(qū)域很可能是熱路徑,基本方法是識別出的熱度較高的基本塊作為起始點,預測其后緊跟的若干個基本塊屬于熱路徑域,將該域內(nèi)的基本塊組織連接形成熱路徑.在MDOS的設(shè)計中,局部預測算法的熱路徑熱度統(tǒng)計主要基于profiling理想狀態(tài)下熱路徑長度越長意味著更多的基本塊能夠被優(yōu)化,更有利于基本塊在執(zhí)行過程中的復用,從而縮減了基本塊的翻譯次數(shù),降低了翻譯開銷.但是由于緩存區(qū)大小等物理條件限制,對熱路徑的長度必須進行限制,因此算法規(guī)定了熱路徑識別的終止條件.由于熱路徑是反復翻譯執(zhí)行的基本塊序列,而程序中的循環(huán)體結(jié)構(gòu)由于多次執(zhí)行很容易成為熱路徑產(chǎn)生區(qū)域,因此,針對循環(huán)結(jié)構(gòu),算法依據(jù)回路終止的原則對循環(huán)體進行相應的處理,即:當前基本塊跳轉(zhuǎn)轉(zhuǎn)向熱路徑的頭部形成回路時,算法認定熱路徑識別終止.為防止熱路徑識別長度過長仍未找到回路的情況,算法規(guī)定:當熱路徑長度達到了算法規(guī)定的長度上限時,終止熱路徑識別.算法對循環(huán)結(jié)構(gòu)的熱路徑回路的終止處理,對于快速定位熱路徑區(qū)域,提升熱路徑識別命中率具有積極意義.算法具體實現(xiàn)如圖2所示,當翻譯開始后,首先判斷當前基本塊是否已處于已經(jīng)提取的熱路徑中,篩選出未被提取的熱路徑,防止熱路徑的重復提取.然后判斷當前基本塊的插樁參數(shù)profiling是否超過設(shè)定的熱度閾值,當超過這一閾值時,算法認定當前基本塊為預測熱路徑的頭部,并啟動熱路徑預測循環(huán),連續(xù)將下一個執(zhí)行的基本塊都作為熱路徑成員,當某一基本塊的轉(zhuǎn)向指向熱路徑頭部,或者熱路徑長度已經(jīng)達到上限時終止熱路徑識別.算法充分利用了程序局部性原理,在低的profiling管理開銷的條件下,實現(xiàn)了快速高效的熱路徑識別,特別是對于循環(huán)結(jié)構(gòu)的熱路徑回路識別處理效果明顯,提高了熱路徑識別的命中率.3.2后端優(yōu)化模塊MDOS系統(tǒng)結(jié)構(gòu)如圖3所示,系統(tǒng)主要由前端翻譯執(zhí)行模塊和后端優(yōu)化模塊兩部分構(gòu)成.前端翻譯執(zhí)行模塊以用戶級QEMU0.10.1為平臺,在QEMU本身代碼翻譯與執(zhí)行功能的基礎(chǔ)上,添加了熱路徑識別與輸出功能部件.后端優(yōu)化模塊主要負責對接收的熱路徑在新的線程中進行超級塊的生成和后端代碼的優(yōu)化.同時,cache采用了分層管理的緩存結(jié)構(gòu),即緩存由原來的QEMU自帶的緩存區(qū)和后段代碼優(yōu)化模塊新建的緩存區(qū)兩部分構(gòu)成,二者在查找優(yōu)先級上有先后之分,在第4節(jié)會進行詳細說明.系統(tǒng)引入了多線程機制,把前后端兩個模塊分別放置于不同的線程中,盡可能地減小了后端優(yōu)化對前端正常進行二進制翻譯執(zhí)行的影響.3.3熱路徑局部預測系統(tǒng)的局部預測前端翻譯執(zhí)行模塊的主要功能是進行正常的二進制翻譯執(zhí)行,同時為后端優(yōu)化模塊輸送查找到的熱路徑.前端基于用戶級QEMU,在完成QEMU本身的翻譯和執(zhí)行功能的基礎(chǔ)上,利用系統(tǒng)局部預測算法對熱路徑進行識別和輸送,擴展了熱路徑識別功能.當前端啟動翻譯執(zhí)行后,QEMU將識別出的熱路徑基本塊按順序依次放入熱路徑緩存區(qū)域中,當熱路徑識別終止后,開啟輸送控制開關(guān),將當前識別出的熱路徑送入后端進行優(yōu)化.前端也對QEMU在cache中的基本塊查找進行了功能擴展,這一部分將在第4節(jié)進行詳細說明.3.4前端熱路徑的開發(fā)方式從前端QEMU獲得的熱路徑重定向到后端優(yōu)化模塊,后端模塊在新的線程開辟子線程接收前端輸送的熱路徑,并對熱路徑進行進一步優(yōu)化.主要的優(yōu)化過程包括兩個方面:超級塊的生成和條件跳轉(zhuǎn)優(yōu)化.完成優(yōu)化后,后端將超級塊存入緩存區(qū)中供前端QEMU模塊查找調(diào)用,并關(guān)閉當前子線程.3.4.1后端優(yōu)化模塊優(yōu)化的第一步是將熱路徑封裝成超級塊.超級塊是單一入口和多出口的多個基本塊組成的超級代碼塊,擁有比單個基本塊更多的代碼量,不僅能夠有效減少對目標代碼寄存器的存取操作,而且有利于進行基本塊之間的代碼優(yōu)化,能有效提高代碼優(yōu)化的概率和效率.當后端優(yōu)化模塊接收到熱路徑暫存區(qū)中的熱路徑后,后端模塊開始生成超級塊.超級塊生成的目的是盡可能把熱路徑中的基本塊有序地組織在一起,形成整體的大塊,同時必須保證合并過程不能破壞基本塊之間的跳轉(zhuǎn)關(guān)系.遵循這一原則,首先將熱路徑頭作為超級塊的起始入口,然后判斷基本塊結(jié)尾是否是無條件跳轉(zhuǎn),如果是則直接插入下一個基本塊代碼,反之則保留跳轉(zhuǎn)出口信息,其后的熱路徑成員基本塊依次按照上述算法處理,直至完成超級塊的生成.3.4.2反復的跳轉(zhuǎn)碼當程序執(zhí)行跳轉(zhuǎn)時,動態(tài)二進制翻譯平臺需要存取當前寄存器狀態(tài),在多次跳轉(zhuǎn)的情況下,存取操作嚴重制約了二進制翻譯速度的提升.例如,在QEMU翻譯過程中,一次只能從cache中提取一個基本塊,而該基本塊對應的目標代碼寄存器的狀態(tài)也僅僅記錄在該基本塊的代碼段內(nèi),當遇到跳轉(zhuǎn)指令時,為了保證跳轉(zhuǎn)到下一個基本塊時寄存器狀態(tài)的一致性,就必須將當前跳轉(zhuǎn)的寄存器狀態(tài)預存入內(nèi)存中,而在下一個基本塊執(zhí)行時再將此信息提取出來.特別是對于程序中循環(huán)結(jié)構(gòu)來講,由于反復的跳轉(zhuǎn)所造成的存取操作對于二進制的翻譯的性能所產(chǎn)生的負面影響是巨大的.假設(shè)有三個個基本塊A,B,C.基本塊A和基本塊B均處在超級塊中,基本塊C處于超級塊之外,由于A,B處于熱路徑中,顯然A轉(zhuǎn)向B的概率大于轉(zhuǎn)向C的概率,因此在基本塊執(zhí)行過程中,每當A轉(zhuǎn)向B時,由于條件跳轉(zhuǎn),必然要從超級塊中跳出獲取上下文信息,然后再跳轉(zhuǎn)回超級塊中B,頻繁的跳入跳出對翻譯性能的影響不言而喻.具體在QEMU中,條件跳轉(zhuǎn)碼的格式是:Gotodst;其中的Brcond表示跳轉(zhuǎn)跳轉(zhuǎn),v1,v2是條件參數(shù),eq(ne)表示條件參數(shù)的關(guān)系相等(不相等),dst代表跳轉(zhuǎn)地址,goto代表跳轉(zhuǎn)向符合條件的基本塊,跳轉(zhuǎn)語句的意思是當條件v1,v2相等(不相等)時,跳轉(zhuǎn)至目標地址dst.優(yōu)化算法流程圖如圖4所示,當獲得跳轉(zhuǎn)條件碼時,首先判斷當前基本塊的下一個跳轉(zhuǎn)基本塊是否在超級塊中,如果是,則對將goto跳轉(zhuǎn)指令刪除.算法減少了基本塊從超級塊向外跳出獲取上下文信息的次數(shù),優(yōu)化了超級塊的跳轉(zhuǎn)結(jié)構(gòu).4mdos系統(tǒng)的cache管理策略cache是二進制翻譯系統(tǒng)的重要組成部分.在動態(tài)翻譯中,某些基本塊可能會被反復使用,為提高翻譯結(jié)果的重用性,減少不必要的重復翻譯工作,二進制翻譯器將翻譯完成的基本塊存放在cache中,當下次需要執(zhí)行該基本塊時,可以直接在cache進行查找,提取已經(jīng)完成的翻譯結(jié)果.cache機制能夠有效地提高翻譯速度,因此cache的有效管理對于二進制翻譯器整體性能的提升意義重大.為延長后端優(yōu)化產(chǎn)生的超級塊的利用周期,系統(tǒng)設(shè)計了分層管理的cache體系,即除原有QEMU自身的Tcache,在后端優(yōu)化模塊又增加了一個cache,命名為Ocache.后端優(yōu)化模塊產(chǎn)生的優(yōu)化超級塊存入Ocache中,當QEMU在查找基本塊時,首先查詢Ocache是否有所需的超級塊,如果沒有再進入Tcache進行查找.分層的管理結(jié)構(gòu)將系統(tǒng)的cache邏輯上分為兩個層次,Ocache為第一層級,系統(tǒng)前端對其擁有優(yōu)先查詢權(quán),Tcache則屬于第二層級.采用分層管理結(jié)構(gòu)的優(yōu)點主要有以下三點:1)不會增加前端QEMU存入基本塊的管理開銷.2)不會發(fā)生超級塊占用前端QEMU的Tcache空間的現(xiàn)象,避免QEMU的Tcache過快填滿、頻繁引發(fā)清空操作的問題.3)延長了超級塊的存活周期,提高了超級塊的命中率.具體實現(xiàn)代碼圖5所示:QEMU自身所帶的Tcache采用了全清空策略,這種策略的優(yōu)點是簡單,不會額外增加系統(tǒng)的管理開銷,但是缺點是容易將熱度較高的基本塊不加選擇的淘汰,影響了基本塊命中率.為了提高Ocache的管理效率,我們采用了FIFO(First-In-First-Out)管理策略.這是一種“先進先出”的管理策略,將存入的超級塊按照先后順序從地址低位向高位依次存放翻譯完成的代碼塊,當Ocache滿時,將先進入的超級塊淘汰.該策略實現(xiàn)簡單,和全清空策略相比,較好的提升了查找效率,延長了優(yōu)化后超級塊的存活時間.5性能評價5mosMDOS系統(tǒng)前端基于用戶級QEMU0.10.1,通過對正確性、基本塊跳出率和整體性能的測試,對系統(tǒng)性能進行實驗評估.5.1源平臺和目標平臺測試集:采用二進制翻譯測試常用的SPEC2006的13個例子作為測試集,QEMU版本為0.10.1;源平臺:32位X86平臺,Fedora11linux2.6.29.4,gcc4.4.0,硬盤500G;目標平臺:64位alpha平臺,Fedora13linux3.8.0,內(nèi)存4G,硬盤500G;將測試集在源平臺下進行編譯,生成可執(zhí)行的ELF文件,作為MDOS系統(tǒng)的輸入文件.5.2本地執(zhí)行結(jié)果及2種情況對比在X86平臺下編譯SPEC2006生成ELF可執(zhí)行文件,在目標平臺下啟動QEMU0.10.1直接運行,得到測試結(jié)果,然后將可執(zhí)行文件再次輸入MDOS系統(tǒng)進行運行,得到測試結(jié)果.對兩個測試結(jié)果進行對比,測試結(jié)果如表1所示.表1顯示,MDOS系統(tǒng)本地執(zhí)行結(jié)果和QEMU本地執(zhí)行結(jié)果一致,表明系統(tǒng)能夠正確的進行二進制翻譯,翻譯正確性可信度高.5.3熱路徑局部預測算法測試結(jié)果通過統(tǒng)計熱路徑局部預測算法識別的熱路徑所包含的基本塊總數(shù)占測試用例基本塊總數(shù)的比例,對算法的識別效果進行初步評估.測試結(jié)果如圖6所示,對于識別比例較大的h264ref和sjeng等測試用例,由于運行時間較長,提供了熱路徑識別的時間條件,從而更有可能達到熱路徑局部預測算法的預測效能.而對于gobmk等識別比例較低的測試用例,由于運行時間短,不利于算法的識別展開,算法效果不明顯.實驗結(jié)果初步說明,熱路徑局部預測算法在代碼量較大、運行時間較長的程序中效果明顯.5.4增強mdos社會管理下的跳標行為基本塊條件跳轉(zhuǎn)優(yōu)化的目的是減小基本塊上下文切換帶來的LOAD和STORE開銷.跳轉(zhuǎn)體現(xiàn)在本地生成碼中的指令主要是CALL和RET指令,因此在QEMU和MDOS生成碼的執(zhí)行過程中,采用插樁技術(shù)手段,加入基本塊的跳轉(zhuǎn)次數(shù)統(tǒng)計代碼.統(tǒng)計結(jié)果分別記作J如圖7所示,對于gobmk和h264測試得到的R值接近0,表示QEMU與MDOS上下文切換的次數(shù)大致相當,經(jīng)過分析可知系統(tǒng)Ocache中的超級塊并未被系統(tǒng)前端命中,但是總體來看,測試集R值平均水平達到6.7%以上,表明MDOS條件跳轉(zhuǎn)優(yōu)化對于減少基本塊跳轉(zhuǎn)次數(shù)效果良好.5.5分層管理策略