成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	陳彥瑜 Chen, Yen-Yu
論文名稱：	仲裁器模型與架構之協同設計及自動產生 Model-Architecture Codesign of Arbiters and Its Automatic Generation
指導教授：	周哲民 Jou, Jer-Min
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	184
中文關鍵詞：	多功能架構模型、設計模型、非集中式、仲裁器、平行與自動產生、輪詢調度、尺度、設計議題
外文關鍵詞：	parallel and automatic generation., decentralized, multi-function, granularity, design model, architecture model, design issues, arbiter, round-robin
相關次數：	點閱：68 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

由於多核處理器SoC勃興與晶片內外高速網路通訊流行，以致仲裁動作(器)需求量極大，導致仲裁器設計此一古典問題如今顯得越來越重要。本論文針對仲裁器設計之各問題深入研究分析，進而發展一個多功能仲裁器之新設計模型，它整合各式仲裁器之設計模型於其中。運用此整體式新設計模型，我們更能掌握各式多功能仲裁器眾設計因素，了然其間之取捨，進而能設計簡潔又最適之特性的各仲裁器。此外，我們亦針對本整體式多功能仲裁設計模型，提出一系統模組化的各仲裁器之統一硬體架構模型，運用此統一硬體架構模型，我們可設計不同功能之仲裁器，它們可以同時或分別實現多種仲裁演算法如輪詢調度和可先佔或不可先佔之線性優先權機制，也可以針對仲裁器設計模型中的任一仲裁特性而設計單一功能之仲裁器。根據此仲裁器系統化統一硬體架構模型，在硬體電路實作時，我們發展出分散式平行仲裁硬體實作之樹狀結構；它極具規則性，且僅使用線性成本就能降低硬體實作仲裁器的執行延遲複雜度至O(logN)且其底數為4，達到極佳的仲裁效能及很小的面積成本。根據此規則性實作樹狀結構，最後，我們又研發設計一個仲裁器自動產生器，它可以快速地自動產生仲裁器，並能提供合成後之執行時間、面積成本、消耗功率等三方面的資訊。實驗結果顯示，用我們所提諸模型與架構所設計出的輪詢調度仲裁器，其效能及面積是現今世界所有仲裁器中最快且最小的。

Arbiter design is a classical problem, but it becomes more and more important because of the flourish of multi-processor system-on-a-chips (MPSoCs) and on- or off- chip high-speed networks. In the past, there were little or no work that thoroughly discussed the properties, design issues and usages of arbiters, which resulted in the inferior arbiter design and usages. In this thesis, we have aimed at analyzing issues of operating of arbiters, and develop an arbiter design model and an arbiter architecture model. With the arbiter design model, we could further know the key points of arbiter designs. With the multi-function arbiter architecture model, we could design a multi-function arbiter which has six arbitrating properties in it simultaneously. Furthermore, we could even design an arbiter targeting a single arbitrating property in the arbiter design model. In the aspect of hardware circuit, we proposed a decentralized and parallel arbitration tree structure suitable for hardware implementation with very little area incensement. Moreover, we design an arbiter generator that could automatically generate arbiters implemented with decentralized and parallel arbitration algorithm with any arbitrating property in the arbiter design model in it. The design results show that the arbitration performance of the arbiter implemented with the multi-function arbiter architecture and decentralized and parallel arbitration algorithm simultaneously is the fastest compared with all existing arbiters, and still has the smallest area.

CHAPTER 1	Introduction	1
1	Motivation and Goals	4
2	Thesis Architecture	5
CHAPTER 2	Related Works	6
1	Round-Robin Arbiters	6
1.1	Programmable Priority Encoder	7
1.2	Ping-Pong Arbiter	12
1.3	Switch Arbiter	15
1.4	Parallel Round-Robin Arbiter	19
2	BW-constraint Arbiter	24
2.1	Weighted Arbiter	25
2.2	LOTTERYBUS	28
2.3	Credit-Control Static-Priority Arbiter	31
CHAPTER 3	Issues of Arbiter Designs	33
1	The Issue about BW Request Ratio and Waiting Latency Tradeoff	34
2	The Issue about Resource Granularity and Arbitrating Latency Tradeoff	35
3	The Issue about Resource Granularity and Fairness Tradeoff	37
4	The Issue about Integrity	39
CHAPTER 4	Solutions to the Issues of Arbiter Designs	40
1	The Solution to the Issue about BW Request Ratio and Waiting Latency Tradeoff	40
2	The Solution to the Issue about Resource Granularity and Arbitrating Latency Tradeoff	42
3	The Solution to the Issue about Resource Granularity and Fairness Tradeoff	44
4	The Solution to the Issue about Integrity	44
CHAPTER 5	Arbiter Design Model and Architecture Model	46
1	Derivation of the Arbiter Design Model	48
1.1	An Example for Using the Arbiter Design Model	53
2	Derivation of the Multi-Function Arbiter Architecture Model	54
2.1	The Basic Arbiter Architecture Model	55
2.2	The Advanced Arbiter Architecture Model	57
2.3	The Full or Multi-Function Arbiter Architecture Model	59
CHAPTER 6	Modular Implementation of the Multi-Function Arbiter Architecture Model	64
1	Design of the Circuit of the PREEMPTION Module	65
2	Design of the Circuit of the TOKEN_GENERATION module	67
3	Design of the Circuit of the TOKEN_CONTROL Module	70
4	Design of the Circuit of the BANDWIDTH module	72
5	Design of Arbiters from the Arbiter Design Model	77
5.1	Equal-priority arbiter without BW Constraint (W’I)	78
5.2	Non-preemptive arbiter without BW Constraint (W’I’E’)	83
5.3	Preemptive arbiter without BW Constraint (W’I’E)	87
5.4	Equal-priority arbiter with BW Constraint (WI)	90
5.5	Non-preemptive arbiter with BW Constraint (WI’E’)	93
5.6	Preemptive arbiter with BW Constraint (WI’E)	95
CHAPTER 7	Decentralized and Parallel Realization of the Multi-Function Arbiter Architecture Model	99
1	Definition of the DPA-tree	101
2	State Representation of the DPA-tree	103
3	The DPA-TRACE Algorithm	104
4	Correctness of the DPA-tree	107
5	Hardware Implementation	113
5.1	Design of the Leaf Node	120
5.2	Design of the Internal Node	122
5.3	Design of the Root Nodes	124
5.4	Recursive Construction of DPA-tree	127
6	A Working Example	130
CHAPTER 8	Design and Development of the Arbiter Generator	132
1	Design of the Code Generation	133
1.1	The Operation Flow of the CG	134
1.2	Design of the Automatic Construction of the DPA-tree	140
2	Design of the Automatic Synthesis	146
CHAPTER 9	Design Results and Analysis	150
1	Arbiters of Arbiter Design Model	150
1.1	Timing-oriented Optimization	150
1.2	Area-oriented Optimization	155
2	Comparison of Round-Robin Arbiters	160
2.1	Timing Results	161
2.2	Area Results	162
3	Comparison of BW-constraint Arbiters	164
3.1	Timing	164
3.1.1	WA	164
3.1.2	LOTTERYBUS	166
3.1.3	CCSP	167
3.1.4	WI	168
3.2	Area	170
3.2.1	WA	170
3.2.2	LOTTERYBUS	170
3.2.3	CCSP	173
3.2.4	WI	173
CHAPTER 10	Conclusions and Future Works	177
1	Conclusions	177
2	Future Works	178
References ........	179
My Publications	183
                                    

[1] Najah A. Abu Ali, Pratik Dhrona, Hossam S. Hassanein, “A performance study of uplink scheduling algorithms in point-to-multipoint WiMAX networks,” Computer Communications 32(3), pp. 511-521, 2009.
[2] Yen-Yu Chen, Jer-Min Jou, Yun-Long Lee and Sih-Sian Wu, “A New Design Model for Arbiters”, Proceedings of the 2009 VLSI Design/CAD Symposium, Aug. 2009.
[3] Tong Li, Dan Baumberger, and Scott Hahn, “Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin,” In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 65-74, February 2009.
[4] Yen-Yu Chen, Jer Min Jou, Yun-Long Lee and Guan-Shiue Wu, “A High-Speed and Decentralized Arbiter Design for NoC”, Proceedings of the 2008 VLSI Design/CAD Symposium, Aug. 2008.
[5] Yun-Lung Lee, Jer Min Jou and Yen-Yu Chen, “A High-Speed and Decentralized Arbiter Design for NoC,” Proceedings of 7th ACS/IEEE International Conference on Computer Systems and Applications, 2008.
[6] Yun-Lung Lee, Jer Min Jou, Yen-Yu Chen and Sih-Sian Wu, “A Optimal Arbiter Design for NoC,” International Computer Symposium (ICS), pp. 288-293, 2008, Best Paper Award.
[7] Yun-Lung Lee, Jer Min Jou, Sheau-Fang Lei and Yen-Yu Chen, “A Fast Centralized Arbiter Design for NoC,” Proceedings of the 2008 VLSI Design/CAD Symposium, Aug. 2008.
[8] B. Akesson, K. Goossens, and M. Ringhofer, “Predator: A Predictable SDRAM Memory Controller,” In Proc. Int’l Conference on Hardware-Software Codesign and System Synthesis (CODES+ISSS), 2007.
[9] B. Akesson et al, “Real-Time Scheduling of Hybrid Systems using Credit-Controlled Static-Priority Arbitration,” Technical report, NXP Semiconductors, 2007. NXP-R-TN 2007/00119.
[10] Minje Jun, Kwanhu Bang, Hyuk-Jun Lee, Naehyuck Chang and Eui-Young Chung, “Slack-based Bus Arbitration Scheme for Soft Real-time Constrained Embedded Systems,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 159-164, 23-26, Jan. 2007.
[11] Bu-Ching Lin, Geeng-Wei Lee, Juinn-Dar Huang and Jing-Yang Jou, “A Precise Bandwidth Control Arbitration Algorithm for Hard Real-Time SoC Buses,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 165-170, 23-26, Jan. 2007.
[12] Haishan Li, Ming Zhang, Wei Zheng and Dongxiao Li, “An Adaptive Arbitration Algorithm for SoC Bus,” Proceedings of Networking, Architecture, and Storage International Conference on, pp. 245-246, 29-31, July 2007
[13] S. Q. Zhengy and Mei Yang, “Algorithm-Hardware Codesign of Fast Parallel Round-Robin Arbiters”, IEEE transactions on parallel and distributed systems, vol. 18, issue 1, pp. 84-95, Jan. 2007.
[14] Anderson, J.H., Calandrino, J.M. and Devi, U.C., “Real-Time Scheduling on Multicore Platforms,” Proceedings of Real-Time and Embedded Technology and Applications Symposium, IEEE, pp. 179-190, 04-07, April 2006.
[15] Chien-Hua Chen, Geeng-Wei Lee, Juinn-Dar Huang and Jing-Yang Jou, “A real-time and bandwidth guaranteed arbitration algorithm for SoC bus communication,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 6, 24-27, Jan. 2006.
[16] Ramabhadran, S. and Pasquale, J., “The Stratified Round Robin Scheduler: Design, Analysis and Implementation,” IEEE/ACM Transactions on Networking, vol. 14, no. 6, pp. 1362-1373, Dec. 2006.
[17] Gao Xiaopeng, Zhang Zhe and Long Xiang, “Round Robin Arbiters for Virtual Channel Router,” Proceedings of Computational Engineering in Systems Applications Multiconference on, pp. 1610-1614, 4-6, Oct. 2006.
[18] Hsiao-Hui Yao and Chih-Peng Fan, “Design and Implementation of A Lottery-based Bandwidth Guaranteed and Low Latency Arbiter for On-Chip Bus,” Proceedings of Workshop on Consumer Electronics and Signal Processing, Taiwan, Nov. 2006.
[19] Feng Wang and Mounir Hamdi, “Fast fair arbiter design in packet switches,” Proceedings of High Performance Switching and Routing, pp. 472-476, 12-14, May 2005.
[20] Mei Yang, Zheng S.Q., Bhagyavati B. and Kurkovskyt S., “Programmable weighted arbiters for constructing switch schedulers,” Proceedings of High Performance Switching and Routing Workshop, pp. 203-206, 2004.
[21] Lee, K.; Lee, S.-J.; Yoo, H.-J., “A high-speed and lightweight on-chip crossbar switch scheduler for on-chip interconnection networks,” Proceedings of European Solid-State Circuits Conference, pp. 453-456, 16-18, Sept. 2003.
[22] B.D. Theelen, A.C. Verschueren, Reyes, M.P.J. Stevens and A. Nunez, “A scalable single-chip multi-processor architecture with on-chip RTOS kernel,” Journal of Systems Architecture, vol. 49, no. 12, pp. 619-639, 2003.
[23] L. Benini and G. Micheli, “Networks on Chips: A New SoC Paradigm,” Computer Magazine, vol. 35, issue. 1, pp. 70-78, Jan. 2002.
[24] E.S. Shin, V.J. Mooney, and G.F. Riley, “Round-Robin Arbiter Design and Generation,” Proc. of Int. Symp. Sys. Syn. (ISSS), pp. 243-248, 2002.
[25] H. J. Chao, C. H. Lam, and E. Oki, Broadband Packet Switching Technologies, John Wiley & Sons, Inc., 2001.
[26] K. Lahiri, A. Raghunathan and G. Lakshminarayana, “LOTTERYBUS: a new high-performance communication architecture for system-on-chip designs,” Proceedings of Design Automation Conference, pp. 15-20, 2001.
[27] H. J. Chao, C. H. Lam, and X. Guo, “A Fast Arbitration Scheme for Terabit Packet Switches,” Proceedings of IEEE Global Telecommunications Conference, pp. 1236-1243, 1999.
[28] P. Gupta and N. McKeown, “Designing and Implementing a Fast Crossbar Scheduler,” IEEE Micro., vol. 19, no. 1, pp. 20-29, 1999.
[29] Shreedhar, M.; Varghese, G., "Efficient fair queuing using deficit round-robin," IEEE/ACM Transactions on Networking, vol. 4, no. 3, pp. 375-385, Jun 1996.
[30] S. Hosseini-Khayat and A.D. Bovopoulos, “A simple and efficient bus management scheme that supports continuous streams,” ACM Transactions on Computer Systems (TOCS), 13(2): pp. 122-140, 1995.
[31] M.J. Karol, M.G. Hluchyj, and S.P. Morgan, “Input vs. Output Queuing on a Space-Division Packet Switch,” IEEE Trans. Commun., vol. 35, no. 12, pp. 1347-1356, 1987.

校內：2012-08-18公開
校外：2012-08-18公開

簡易檢索 / 詳目顯示

相關論文