可擴充性排序電路架構設計

Extensible Sorting Hardware Architecture Design

羅立平(Li-Ping Luo)

指導教授 ： 吳章銘

中原大學/工學院/電子工程研究所/碩士(2013年)

https://doi.org/10.6840/cycu201300556

摘要

本論文提出一種可擴充的排序電路架構，此電路利用奇偶傳遞排序法(Odd-Even Transposition Sort)的規律性，將排序電路模組化，使用硬體描述語言設計出可擴充的排序電路基本模組，藉由組合任意數量的基本模組，可完成能排序任何輸入資料數量的排序電路，此排序電路能應用在如FlexRay需要排序資料的通訊系統中。FlexRay是一種高速傳輸、時間觸發且具容錯能力的車載網路通訊協定，本論文以硬體描述語言設計FlexRay的通訊控制器(Communication Controller)電路，在通訊控制器電路中，需要使用依數值大小排序資料的功能且輸入數值資料數在固定筆數內，基於電路重複使用及關閉無用基本模組之構想，我們設計一個適用於通訊控制器的排序電路以符合上述之要求，並可依排序資料數量調整運作模組的數量，以節省能源。最後將通訊控制器電路進行模擬與合成，驗證其功能，最後在FlexRay進行節點互通的實驗，以證明設計出的通訊控制器電路與排序電路是能正常運作的。

關鍵字

FlexRay ； 排序電路 ； 可擴充 ； 奇偶傳遞排序法

並列摘要

In our thesis, we propose an extensible sorting hardware architecture circuit. Analyzing the repetition of the Odd-Even Transposition Sort method, we design a basic sorting cell by the hardware description language. We can apply several basic sorting cells to build as the extensible sorting hardware circuit and satisfy the required input numbers of the sorting data. The extensible sorting hardware circuit can be applied to the FlexRay communication controller circuit for adjustment of the several cases of the sorting input data numbers. FlexRay is a specification of vehicle network communication which provides high speed, timing trigger, and fault tolerance. In our thesis, we also implement the circuit of the FlexRay communication controller with the Verilog hardware description language. We demand a sorting circuit to sort the timing table data in the communication controller circuit to correct the global time. The basic sorting cell circuit can be re-used and convenient to other applications. The sorting circuit has a function to save energy by turning off the not-use modules. Finally, we verify the circuit of communication controller to simulate and synthesize the circuit on the FPGA. We experiment the field try to confirm our design of the communications controller and extensible sorting circuit working correctly.

並列關鍵字

Sorting circuit ； Extensible ； Odd-Even Transposition Sort ； FlexRay

參考文獻

[1] Marcos Moecke and Rui Seara, “Sorting Rates in Video Encoding Process for Complexity Reduction,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, pp. 88-101, Jan. 2010.

[2] Wen-Ping Chen, Wen-Fong Wang, and Wen-Shyang Hwang, “Adaptive Dynamic Bandwidth Allocation Algorithm with Sorting Report Messages for Ethernet Passive Optical Network,” IET Communications, vol. 4, pp. 2230-2239, Dec. 2010.

[3] D. Taniar and J. W. Rahayu, “Sorting in Parallel Database Systems,” in Proc. of The Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, New Zealand, pp. 830 – 835, May. 2000.

[4] Y. Chao, C. Guoliang, Z. Cheng, and S. Yifei, “Sorting Networks on a Nanocomputing Architecture,” in Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Applications and Technologies, Chengdu, China, pp. 784-788, Aug. 2003.

[5] Feng Hao, John Daugman, and Piotr Zielin´ski, “A Fast Search Algorithm for a Large Fuzzy Database,” IEEE Transactions on Information Forensics and Security, vol. 3, pp. 203-212, Jun. 2008.