跳到主要內容

臺灣博碩士論文加值系統

(52.203.18.65) 您好!臺灣時間:2022/01/19 15:08
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張隆昌
研究生(外文):Lung-Chung Chang
論文名稱:爪哇處理機之堆疊指令摺疊:模型建立與實作
論文名稱(外文):Stack Instruction Folding of Java Processors: Modeling and Realization
指導教授:鍾崇斌
指導教授(外文):Chung-Ping Chung
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:爪哇處理機爪哇虛擬機器堆疊運算摺疊資料相依性堆疊指令摺疊
外文關鍵詞:Java ProcessorJava Virtual MachineStack Operations FoldingData DependencyStack Instruction Folding
相關次數:
  • 被引用被引用:0
  • 點閱點閱:243
  • 評分評分:
  • 下載下載:26
  • 收藏至我的研究室書目清單書目收藏:1
爪哇 (Java) 語言由於其較安全、具有跨平台特性、且其程式碼較小 (每一指令平均約1.8 Bytes),被廣泛應用於Internet以及嵌入式控制器上。然爪哇處理機 (Java Processor) 受到其虛擬機器 (Virtual Machine) 資料相依性之特性影響,效能受到嚴重之限制。為了克服以上之問題,在本論文中介紹了靜態式 (Pattern-based) 及動態式 (Rule-based) 兩種指令摺疊方法。在靜態式摺疊中,可摺疊指令之組合型態必須事先找出,然後一一與目前指令串來比對。而在動態式摺疊中,指令將依其可摺疊屬性自動地被摺疊在一起。同時它可再分為連續性指令 (Continuous Instruction) 及非連續性指令 (Discontinuous Instruction) 摺疊。前者僅可摺疊一串連續之可摺疊指令,而後者可將被非堆疊指令或已被摺疊過指令隔開之指令摺疊在一起。本論文提出一連續動態摺疊方法─POC Folding,及其架構設計。初期模擬統計資料顯示,4-摺疊策略已接近摺疊上限,可省去84%之堆疊運算;且2-、3-及4-摺疊相對於無指令摺疊之效能比為1.22、1.32及1.34。此方法可以最簡單之硬體設計來完成。另外,一個非連續之動態摺疊模型,同時也是POC摺疊之擴充模型─Hybrid-EPOC Folding,在本論文中一併被提出。它可藉由軟體之重新安排,利用既有之簡單POC硬體額外增加一擴充指令 (P’ Bytecode) 來達成。其在4-摺疊策略下可省去94.8%之堆疊運算 (使用第二種測試程式─SPECjvm98 / s10 Data Set),較POC摺疊之80.1%多了14.7%,效能比高了13%;其IIPC (Issued Instructions Per Cycle) 在 2-、3-、4-摺疊策略下為1.60、1.70與1.71,其中1.71達到理論上限值1.77之96.6%。然而其所付出之額外P’ Bytecode程式碼少於原先虛擬機器總大小之8%。此種方法在ROM相對面積較小之高效能SoC設計中有其好處。昇陽之picoJava-II用靜態之摺疊方法,其可省去之堆疊運算僅為39.6%、IIPC為1.25。目前本研究為世界之首,無論在方法及架構上均有最佳之貢獻。不但獲得美國及中華民國專利,且被學術界其他研究所參考。如 Kim 之Advanced POC 摺疊模型即是參考本POC摺疊模型而來。
Java has been extensively adopted in Internet and embedded applications because of its robust, cross platform and small code size (every instruction is 1.8 bytes on average) characteristics. However, the performance of the Java processor is greatly limited by the true data dependency inherited from its virtual machine. Two kinds of folding models are introduced to overcome this problem. One is pattern-based folding and the other is rule-based folding. In the pattern-based folding model, folding patterns are identified first and then compared with incoming instructions. In the rule-based folding model, bytecode instructions are classified before the folding algorithm automatically perform folding checks based on the folding attributes of each bytecode instruction. Furthermore, the folding can be divided into continuous instruction and discontinuous instruction folding. The former can only fold sequentially ordered instructions. The latter folds instructions that may be blocked by non-stack instruction or may include folded instructions. A continuous rule-based folding model — POC folding — and its corresponding architecture are proposed. The first simulation shows that 4-foldable strategy that almost reaches the performance upper bound can eliminate 84% of all stack operations. The 2-, 3-, and 4-foldable strategies yield in an overall program speed-up of 1.22, 1.32 and 1.34 times, respectively, when compared to a stack machine without folding. This model can be implemented by simple hardware design. A discontinuous rule-based folding model that extends POC folding — Hybrid-EPOC folding — is also proposed. It can be implemented by software re-scheduling accompanied by simple POC folding hardware, with the support of an extra extended bytecode (P’ bytecode). A 4-foldable Hybrid-EPOC Folding model folds 94.8% of stack operations using the second benchmark program — SPECjvm98/s10 data set. The model exhibits a 14.7% increase and a 13% performance gain over the 80.1% of the POC folding model can fold. The IIPC (Issued Instructions Per Cycle) of the Hybrid-EPOC folding model for 2-, 3-, and 4-foldable strategies are 1.72, 1.73, and 1.74, respectively. 1.74 is 98.3% of the theoretical upper bound of 1.77. However, the increased code size of the P’ bytecode is less than 8% of that of the total virtual machine code. This model is suitable for the high performance and low ROM size of the system on a chip design. Sun Microsystem’s picoJava-II uses a pattern-based folding model, which can eliminate 39.6% of all stack operations and 1.25 of IIPC by the 4-foldable strategy. Our research leads this field, in both methodology and architecture. We have obtained US and ROC patents, and the research results has also been referenced by other research, including Kim’s Advanced POC model.

摘要 i
ABSTRACT iii
誌謝 v
TABLE OF CONTENTS vi
LIST of FIGURES viii
LIST of TABLES ix
CHAPTER 1 INTRODUCTION 1
1.1 Java Computing 1
1.2 Motivation 1
1.3 Objectives 5
1.4 Organization 7
1.5 Contributions 8
CHAPTER 2 FUNDAMENTALS AND BACKGROUND 9
2.1 Stack Operations Folding 10
2.2 Java Processor Model 12
2.2.1 Block Diagram and Pipeline Stages 12
2.2.2 Comparison of Forwarding and Folding 14
2.2.3 Examples of Instruction Folding and Forwarding 15
2.3 Pattern-based Folding 18
2.3.1 Tseng’s Pattern-based Folding Model 18
2.3.2 Sun’s Pattern-based Folding Model 21
2.3.3 Kim’s Pattern-based Folding Model 22
2.4 Rule-based Folding 24
2.4.1 Continuous Rule-based Folding 24
2.4.2 Discontinuous Rule-based Folding 25
2.5 Simulation Environment and Performance Metrics 26
2.5.1 Case of JDK Applets 26
2.5.2 Case of SPECjvm98 28
CHAPTER 3 CONTINUOUS RULE-BASED FOLDING MODEL 31
3.1 The POC Model 31
3.1.1 The Model 31
3.1.2 Illustrative Examples 34
3.2 POC Folding Algorithm and Its Transition Diagram 35
3.3 Performance of POC Folding Model 37
CHAPTER 4 DISCONTINUOUS RULE-BASED FOLDING MODEL 41
4.1 The Hybrid-EPOC Folding Model 42
4.1.1 Extended Folding Group 43
4.1.2 Extended POC Model — EPOC 44
4.2 Illustrative Example 45
4.3 Hybrid-EPOC Folding Algorithm 46
4.4 Characteristics and Performance of HYBRID-EPOC Folding Model 49
4.4.1 Extended Folding Group Characteristics 49
4.4.2 Performance of Extended Folding Model 52
CHAPTER 5 HARDWARE REALIZATION OF STACK INSTRUCTIONS FOLDING 55
5.1 Assumptions and Requirements 55
5.2 POC Model Realization 55
5.2.1 OP Code Checker (Sizer) 56
5.2.2 Folding Rule Checker & Address Assigner 58
5.2.3 Source/Destination Address Generation Units (AGUs) 61
5.3 Hybrid-EPOC Model Realization 62
5.4 Timing Assessment 63
5.4.1 Logic Design 63
5.4.2 Delay Calculation 66
CHAPTER 6 CONCLUSION 68
6.1 Continuous Rule-based Folding 68
6.2 Discontinuous Rule-based Folding 70
6.3 Future Work 70
REFERENCES 72
APPENDICES 74
A. Folding Attributes of Java Virtual Machine Instruction Set Sorted by Opcode Order 74
Non-Pseudo Opcodes: 74
Pseudo Opcodes: 80
Reserved Opcodes: 81
Unused Opcodes: 81
B. Java bytecodes distribution of the Applets of JDK 83
Sorted by op code sequence 83
Sorted by percentage of occurrence 85
C. Java bytecodes distribution of SPECjvm98 88
Sorted by op code sequence — Compress 88
Sorted by op code sequence — db 92
Sorted by op code sequence — jack 96
Sorted by op code sequence — javac 100
Sorted by op code sequence — jess 104
Sorted by op code sequence — mpeg 108
Sorted by op code sequence — raytracer 112

[1] Abhay Gupta, Chris Ferris, Yvonne Wilson and Katni Venkatasubramanian, “Implementing Java Computing: Sun on Architecture and Applications Deployment”, IEEE Internet Computing, March.April 1998.
[2] Austin Kim and Morris Chang, “An Advanced Instruction Folding Mechanism for a Stackless Java Processor”, Proceeding of the International Conference on Computer Design (ICCD), pp. 565-566, September 2000.
[3] Austin Kim and Morris Chang, “Advanced POC Model-based Java Instruction Folding Mechanism”, Proceedings of the 26th Euromicro Conference, vol. 1, pp. 332-338, September 2000.
[4] Brian Case, “Implementing the Java Virtual Machine”, Microprocessor Report, March 1996.
[5] Han-Min Tseng, Lung-Chang Chang, Lee-Ren Ton, Min-Fu Kao, Shi-Sheng Shang and Chung-Ping Chung, “Performance Enhancement by Folding Strategies of a Java Processor”, International Conference on Computer Systems Technology for Industrial Applications — Internet and Multimedia, April 1997.
[6] James Gosling, Bill Joy and Guy Steele, “The Java™ Language Specification”, Addison-Wesley Publisher Co., Inc. August 1996.
[7] Jim Turley, “Sun Reveals First Java Processor Core” Microprocessor Report. October 1996.
[8] John L Hennessy & David Patterson, “ Computer Architecture A Quantitative Approach”, Second Edition, Morgan Kaufmann.
[9] J. Michael O’Connor and Marc Tremblay, “picoJava-I: The Java Virtual Machine in Hardware”, IEEE Micro, vol. 17, no. 2. March/April 1997.
[10] L.-C.Chang, L.-R.Ton, M.-F.Kao and C.-P.Chung, “Stack operations folding in Java processors”, IEE Proceedings on Computer and Digital Techniques, vol. 145, no. 5. September 1998.
[11] Lee-Ren Ton, Lung-Chung Chang, Min-Fu Kao, Han-Min Tseng, Shi-Sheng Shang, Ryeu-Liang Ma, Dze-Chaung Wang and Chung-Ping Chung, “Instruction Folding in Java Processor”, International Conference on Parallel and Distributed Systems. December 1997.
[12] Mark Lentczner and Glyphic Technology, “Java’s Virtual World”, Microprocessor Report, March 1996.
[13] Philip Koopman, “Stack Computer”, http://www.cs.cmu.edu/.
[14] Robert Orfali, Dan Harkeyand Jeri Edwards, “Client/Server Survival Guide, Third Edition”, ISBN: 0471316156, John Wiley & Sons  1999, 762 pages.
[15] Sun Microsystems, “picoJava-I Microprocessor Core Architecture”, http:// www.sun.com/microelectronics/whitepapers/wpr-0014-01/index.html.
[16] Sun Microsystems, “picoJava™-II — Java Processor Core”, http://www.sun.com/micro electronics/datasheets/picoJava-II/.
[17] Sun Microsystems, “microJava™-701 Processor”, http://www.sun.com/micro electronics/microJava-701/.
[18] Tim Lindholm and Frank Yellin, September 1996, “The Java™ Virtual Machine Specification”, Addison-Wesley Publishing Co., Inc.
[19] Tndran Naick et al, “ Design Considerations: From Client/Server Application to a Business Applications”, ISBN: 0738414816, IBM Redbooks  1999, 352 pages.
[20] TSENG, H.M., CHANG, L.C., TON, L.R., KAO, M.F., SHANG, S.S. and CHUNG C.P.,“Performance enhancement by folding strategies of a Java processor”, International Conference on Computer Systems Technology for Industrial Applications — Internet and Multimedia, CSIA’97, April 1997, Hsinchu, Taiwan, R.O.C., pp. 286-293
[21] TURLEY, J., “Sun Reveals First Java Processor Core”, Microprocessor Report, October 1996.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top