應用於高速排序之移位暫存器陣列

Abstract

本篇論文敘述一個以移位暫存器陣列為基礎之高速硬體排序器架構，並提 出兩個製作於此架構上之排序器和一個實際的排序器ＡＳＩＣ。比較和資 料搬移是排序的兩個基本技術；舊有之硬體排序器的比較方式為平行之兩 兩相比，採多級式的架構來完成所有比較工作。而ＳＲＡ架構採平行之一 對多比較方式，大幅縮短單一輸入資料之比較延遲時間。在資料搬移方面 ，傳統的排序器是使用互換法或移動法來達成，ＳＲＡ架構則使用移位暫 存器的移位與載入動作來達成，可以減少硬體開關數目且無需額外之儲存 空間。在此架構中，輸入資料同時與已排序過的所有資料相比；移位暫存 器陣列內的資料可以移動到其臨近的暫存器中，但輸入資料則可任意移動 到任一位置。因此硬體排序器的瓶頸可以被打破。而這瓶頸就是即使剛排 好的資料只有一點變動，也須要Ｎ（最大排序量）個延遲才能重新產生新 的排序結果。 在本論文所提出的兩個排序器中， M-array 增減一個資料 的延遲時間是ＷＬ（資料位元數）， ODI 則只需一個延遲時間。原始的 M-array 演算法被轉換成長條圖似的演算法以製作於此架構上，並被作 成ＡＳＩＣ，此ＩＣ測試後證明其可以正常工作。 ODI 排序器是以插入 排序法為基礎，提供高處理速度且只須很少的晶片面積，與其他排序器比 較後證明其非常適合當作一般多用途的排序器。 In this thesis, an architecture style named shift register array (SRA) for high speed data sorting is represented. In addition, two architectures and an ASIC based on this architecture style are represented,too. In this architecture style, input sample is simultaneously compared with all sorted samples, where the former can be routed to any location, while the latter can only be routed to their neighborhoods. With this architecture, we achieve the minimum latency delay for sorting each input sample. The two architectures in this thesis show that the latency can be reduced to WL cycles (Here WL is the wordlength of input samples) in M-array architecture and 1 cycle in ODI architecture. The M-array algorithm is first transformed to a bar-chart like style which is then implemented on the SRA architecture, and finally an M-array ASIC is implemented. The test results show that the SRA architecture can perform the function of median filtering. The ODI sorter based on insertion-sort provides a fast and less area hardware solution for sorting. Evaluation shows that it is very suitable to be implemented as a high- speed general-purpose sorter.