在資料探勘、數位訊號處理、型態辨識或影像處理等的領域中，排序已廣泛的被使用且是不可或缺的一項運算，且在許多應用上，往往只需要使用到極值，故探討如何有效率的找到極值是十分重要的。此外，對於許多需要即時處理的應用來說，即時排序的硬體實現是不可或缺的。
在本論文中，我們針對排序單元提出一個有效的硬體架構，其電路架構使用索引值以及門檻值的機制，並使用模組化的方法設計，使得整個架構容易被重複使用與平行化，藉由以上設計來達到低功耗消耗的設計，最後，提出一個迭代的架構，使得整個設計能夠更有效率的被使用在不同應用上。
一般的排序方法，對於一些需要較大樣本寬度或較多輸入值的應用來說，在電路上可能需要更多的訊號傳遞，或是互相交換值，而造成更多的動態功率消耗。為了解決上述的問題，我們在電路架構設計上採用了較少位元所組成的索引值以及門檻值的概念，使儲存的樣本值不需要進行移動排序，而僅需改變索引值來完成排序。此外，進行較大輸入量的迭代運算時，利用門檻值來排除掉不必要的數值以降低重複運算的次數，如此就可有效減少電路中訊號的傳遞以及運算次數，藉此達到節省功率消耗的結果，此外，我們亦針對控制電路的設計以邏輯最佳化的化簡方法來實現，大幅改善整體硬體成本使用。實驗結果顯示我們和其他文獻電路架構相比，此電路的功率消耗平均僅約一半，但需要一些額外的面積代價。
此論文中，所有的硬體架構之實現是使用Verilog硬體描述語言，電路合成是利用Synopsys Design Vision以及TSMC的標準元件庫，最後採用Synopsys Power Compiler量測電路佈局後模擬的功率消耗。依據合成結果與功率消耗量測，我們所提出的電路架構設計在低功率消耗上具有極佳的競爭力。

Sorting is an important operation in a wide range of applications such as data mining, digital signal processing, pattern recognition or image processing. In many applications, only the max set value or the min set value need to be selected and researched, so it is very important to discuss how to find the max set value or the min set value in an efficient way. Moreover, a real-time sorting unit is indispensable for many applications.
In this thesis, an effective hardware architecture for sorting units is proposed. The architecture includes rank and threshold mechanisms and can easily be reused and pipelined due to its modular design and low power consumption. The combinational control unit was then implemented using a logic optimization method. Lastly, we propose an iterative architecture so the design can be used in different applications in an efficient way.
In general, for sorting methods in applications that process huge data strings or large amounts of data inputs, the electric circuits may require more signal transmissions, resulting in more dynamic power consumption. To solve this problem, the stored values were replaced with Rank and Threshold values with lower bit size, so that the stored values don’t need to be moved or sorted and the rank values are exchanged instead. Moreover, when iterative architectures are used, a threshold mechanism is implemented to exclude unnecessary repetitions and thus save power by reducing the number of signal transmissions and calculations inside the circuit. The experimental results indicate that the power consumption for our proposed method was successfully reduced at the mere expense of some area increase.
The VLSI architecture of the proposed design was implemented using Verilog HDL and synthesized by Synopsys Design Vision with the TSMC cell library. Finally, the total power consumption was measured by Synopsys Power Compiler, the synthesis results and total power consumption show that the proposed designs have the advantages of low cost and low power, respectively.

[1] K. E. BATCHER, “Sorting networks and their applications” Spring Joint Computer Conference, 1968.
[2] Mihai Florin Ionescu and Klaus E. Schauser, “Optimizing Parallel Bitonic Sort” Parallel Processing Symposium Proceedings., 11th International, 1997.
[3] Amin Farmahini-Farahani, Anthony Gregerson, Michael Schulte and Katherine Compton “Modular High-throughput and Low-latency Sorting Units for FPGAs in the Large Hadron Collider” IEEE 9th Symposium on Application Specific Processors (SASP), 2011. pp.38-45
[4] Amin Farmahini-Farahani, Henry J. Duwe III, Michael J. Schulte and Katherine Compton,“Modular Design of High-Throughput, Low-Latency Sorting Units” IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 7, JULY 2013.
[5] Robert Chen-Hao Chang, Ming-Fan Wei, Hung-Lieh Chen, Kuang-Hao Lin, Hou-Ming Chen, Yu-Ya Gao, and Shih-Chun Lin,“Implementation of a High-Throughput Modified Merge Sort in MIMO Detection Systems” IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS, pp. VOL. 61, NO. 9, September 2014.
[6] CIC技術論壇, “應用於數位積體電路的低功率設計技術 Low Power Techniques for Digital IC Design”.
[7] Miklós Ajtai, János Komlós and Endre Szemerédi,“Sorting in clogn parallel steps” Combinatorica, March 1983.
[8] Dirk Koch and Jim Torresen,“FPGASort: A High Performance Sorting Architecture Exploiting Run-Time Reconfiguration on FPGAs for Large Problem Sorting” Proc. Symp. Field Programmable Gate Arrays, pp. pp. 45-54, 2011.
[9] Joseph J´aJ´a, “An Introduction to Parallel Algorithms” Addison-Wesley, Reading, Mass, 1992.
[10] J. P. Agrawal, “Arbitrary Size Bitonic (ASB) Sorters and Their Applications in Broadband ATM Switching” Proc. IEEE Int’l Conf. Computers and Comm, pp. pp. 454-458, March 1996.
[11] K. Y. Yun, S. Chakraborty, K. W. James, R. Fairlie-Cuninghame, R. L. Cruz,“A Self-Timed Real-Time Sorting Network” IEEE Trans. Very Large Scale Integration Systems” vol. 8, no. 3, pp. pp. 356-363, June 2000.
[12] Alberto Colavita, Enzo Mumolo and Gabriele Capello,“A Novel Sorting Algorithm and Its Application to a Gamma-Ray Telescope Asynchronous Data Acquisition System” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 394, no. 3, pp. pp. 374-380, 1997.
[13] Donpaul C. Stephens, Jon C.R. Bennett and Hui Zhang,“Implementing Scheduling Algorithms in High-Speed Networks” IEEE J. Selected Areas in Comm, vol. 17, no. 6, pp. pp. 1145-1158, June 1999.
[14] Anthony Gregerson, Michael J. Schulte and Katherine Compton,“High-Energy Physics” Handbook of Signal Processing Systems Springer, pp. pp. 179-211, 2010.
[15] Ren-Der Chen, Pei-Yin Chen, and Chun-Hsien Yeh,“A Low-Power Architecture for the Design of a one-dimensional median filter” IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—II: EXPRESS BRIEFS, VOL. 62, NO. 3, March 2015.
[16] Stephan Olariu, M. Cristina Pinotti and Si Qing Zheng,“An Optimal Hardware-Algorithm for Sorting Using a Fixed-Size Parallel Sorting Device” IEEE Trans. Computers, vol. 49, no.12, pp. pp. 1310-1324, December 2000.