臺灣博碩士論文加值系統

　　隨著USB介面日益地受到重視與應用，幾乎所有的PC主機週邊設備，以及消費性電子產品已逐漸將USB介面列為必備甚至是唯一的介面。由於USB2.0的擴充，傳輸的速率可以高達480Mb/s。USB簡化了主機硬體與周邊設備的聯結，且支援不同型態的資料傳輸，像是即時性、非即時性的資料交換。然而USB標準中只簡略的定義資料傳輸容量的限制，對於保證不同USB周邊的傳輸品質卻是比較少討論，也沒有一個有效的機制來加強傳輸頻寬的保留。在本篇論文中，將提出一個USB頻寬保留的演算法，針對同步傳輸以及中斷傳輸做排程，透過事先將USB頻寬有效的分配，可以提高USB周邊頻寬要求的接受率，且降低每一次傳輸系統需要尋找傳輸點的延遲性，進而達到即時性的傳輸。排程演算法實做在Linux上，最後利用USB喇叭以及USB螢幕來測試整體的效能。

　As the USB interface has been paid much attention to and been put to use day by day, almost all the peripheral equipments of personal computer and the consuming electronic products have gradually considered USB interface as indispensable or even the only interface for computer systems. With the extension of USB2.0, the transferring speed now can be up to 480MB/s. USB not only simplized the connections between host and peripherals, but also supported transferring for various types of data, such as real-time and non-real-time data communication. However, the USB specification defines approximately the limitations for the data transfer capacity. Little work has done to QoS for different peripherals and it also lack for an efficient mechanism to enforce transfer bandwidth guarantees. In this paper, I will propose an algorithm for USB bandwidth guarantee, and schedule the isochronous and interrupt transfers. Through effective allocation for USB bandwidth, we may raise the acceptance ratio of bandwidth demands of USB peripherals, lower the latency caused by the system finding nodes every transmission, and then achieve the real-time transfer. The scheduling algorithm will be implemented on Linux, and we will use USB speaker and USB LCD to evaluate the performance.

Chapter 1 Introduction ….……………………………………………………………………….1
1.1 Introduction……………………………………………………………………………………….1
1.2 Motivation………………………………………………………………………………………...1
1.3 Overview of This Thesis………………………………………………………………………….2
Chapter 2 Introduction to USB System………………………………………………………4
2.1 USB System Architecture………………………………………………………………………..4
2.1.1 About USB…………………………………………………………………………………..4
2.1.2 USB Physical Interface……………………………………………………………………...5
2.1.3 USB Logical Interface………………………………………………………………………6
2.1.2 Data Transfer Type……………………………………………………………………….....7
2.2 USB Host Controller……………………………………………………………………….…....8
2.2.1 Backward Compatible of USB1.1 Transfers………………………………………….….....9
2.2.2 Transfer Schedule………………………………………….………………………………..9
2.2.2.1 Periodic Schedule………………………………………….….....................................10
2.2.2.2 Asynchronous Schedule……………………………….…............................................11
2.3 USB Client Device……………………………….…..................................................................12
2.3.1 Cypress EZ-USB FX2 Hardware Architecture.....................................................................13
2.3.2 Cypress EZ-USB FX2 Firmware Framework.......................................................................15
Chapter 3 Relative Work.............................................................................................................17
3.1 USB System in Linux Kernel......................................................................................................17
3.1.1 USB Architecture in Linux Kernel.......................................................................................17
3.1.2 Scheduling in Linux Kernel..................................................................................................18
3.2 Period Modification Policy and Re-inserted Algorithm..............................................................19
3.2.1 Idea of the Algorithm............................................................................................................19
3.2.2 Scheduling Algorithm...........................................................................................................20
3.2.2.1 A Fixed-Rate Service Policy..........................................................................................20
3.2.2.2 A Workload Re-insertion Algorithm..............................................................................21
3.3 Packet Split Re-define.................................................................................................................23
Chapter 4 USB Task Scheduling Optimization Algorithm..............................................27
4.1 Idea of Optimization Algorithm..................................................................................................27
4.2 Optimization Algorithm..............................................................................................................31
4.3 Proposed USB Scheduling System Architecture........................................................................36
4.4 Implement Optimization Algorithm in Linux Kernel.................................................................37
4.4.1 Implementation of Optimization Algorithm..........................................................................37
4.4.2 Modification of Period Transfer.............................................................................................39
Chapter 5 USB Devices Implementation...............................................................................42
5.1 USB Speaker Implementation....................................................................................................42
5.1.1 USB Interface.......................................................................................................................42
5.1.2 FPGA DAC..........................................................................................................................43
5.2 USB LCD Implementation.........................................................................................................46
5.2.1 USB Interface......................................................................................................................46
5.2.2 FPGA Implementation ........................................................................................................47
Chapter 6 Performance Evaluation........................................................................................51
6.1 Task request accepted rate...........................................................................................................51
6.2 Bandwidth Reservation and Workload Distribution....................................................................57
6.2.1 Evaluation Environment.......................................................................................................57
6.2.2 Experiment Result................................................................................................................58
6.2.2.1 First Experiment............................................................................................................58
6.2.2.2 Second Experiment........................................................................................................60
6.2.2.3 Third Experiment...........................................................................................................62
Chapter 7 Conclusions and Future Works............................................................................65
Reference...........................................................................................................................................66
Appendix............................................................................................................................................68
Part I: USB Speaker Descriptors based on USB Audio Class...........................................................68
Part II: USB LCD Descriptors...........................................................................................................75

[1]C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment” JACM, Vol. 20, No. 1, pp. 46-61, January 1973
[2]Chih-Yuan Huang,Li-Pin Chang, and Tei-Wei Kuo. "A Cyclic-Executive-Based QoS Guarantee over USB." In IEEE 9th Real-Time and Embedded Technology and Applications Symposium, pp. 88 – 95, 2003
[3]Chih-Yuan Huang,Li-Pin Chang, and Tei-Wei Kuo . “QoS Support for USB 2.0 Periodic and Sporadic Device Requests.” In 25th Real-Time Systems Symposium, pp. 395 – 404, 2004.
[4]“Universal Serial Bus Specification, Revision 1.1” ，http://www.usb.org/
[5]“Universal Serial Bus Specification, Revision 2.0” ，http://www.usb.org/
[6]“Universal Host Controller Interface (UHCI) Design Guide, Revision 1.0” ，Intel，http://www.intel.com/
[7]“OpenHCI Open Host Controller Interface Specification for USB , Revision 1.0” ， Compaq， Microsoft， and National Semiconductor，
[8]“Enhanced Host Controller Interface Specification for Universal Serial Bus, Revision 1.0” ，Intel，http://www.intel.com/
[9]“Universal Serial Bus Device Class Definition for Audio Devices, Revision 1.0” ，http://www.usb.org/
[10]“Universal Serial Bus Device Class Definition for Terminal Types, Revision 1.0” ， http://www.usb.org/
[11]“Universal Serial Bus Device Class Definition for Audio Data Formats, Revision 1.0” ， http://www.usb.org/
[12]“EZ-USB FX Technical Reference Manual” ， Cypress Semiconductor ， http://www.cypress.com/
[13]“EZ-USB FX2 Technical Reference Manual”， Cypress Semiconductor ， http://www.cypress.com/
[14]“Anchor EZ-USB Frameworks” ， Cypress Semiconductor ， http://www.cypress.com/
[15]“EZ-USB General Purpose Driver Specification” ， Cypress Semiconductor ， http://www.cypress.com/
[16]“Nios Development Board Reference Manual, Stratix Edition” ， ALTERA ， http://www.altera.com/
[17]“Stratix II EP2S60 DSP Development Board” ， ALTERA ， http://www.altera.com/
[18]“3.3V CMOS Static RAM 4 Meg (256K x 16-Bit) IDT71V416S Data Sheet” ， IDT ， http://www.idt.com/
[19]“FMS3818 Triple Video D/A Converters” ， FAIRCHILD SEMICONDUCTOR ， http://www.fairchildsemi.com/