Title page for etd-0831109-115655


[Back to Results | New Search]

URN etd-0831109-115655
Author Chien-jung Fu
Author's Email Address m953040077@student.nsysu.edu.tw
Statistics This thesis had been viewed 5334 times. Download 9 times.
Department Computer Science and Engineering
Year 2008
Semester 2
Degree Master
Type of Document
Language zh-TW.Big5 Chinese
Title Design of Various VLSI Sorting Accelerator Architectures
Date of Defense 2009-06-15
Page Count 61
Keyword
  • Sorter
  • Odd-Even merge sort
  • Abstract In this thesis, various designs of VLSI sorter architectures are proposed. This thesis first presents a baseline serial sorter architecture built on a central memory module equipped with a single compare-and-swap (C&S) functional unit. A dedicated low-cost address generation circuit which controls the order of data accesses and C&S operation in order to support sorting of data sequences with any length is proposed. By exploring the bit-permutation technique to create the access orders suitable for different C&S steps, the address generator can be built by only two adders and three shifters plus some control circuits, and consumes only about 1K gates. Next, this thesis also proposes a two-bank memory architecture to reduce the required memory ports from four to two such that the sorter memory can be realized by on-chip SRAM blocks. Our experimental results show that the overall silicon cost can be reduced by more than 56% for the sorter circuit which can sort the data sequence of length up to 1024.
    In addition to the serial sorter architecture, this thesis further proposes three possible parallel sorter architectures including the pipeline sorter, cascade sorter, and block sorter. Among these three architectures, the pipeline sorter can deliver the best throughput although it can be used only for fixed-length data sequences. On the other hand, the block sorter is the most flexible design suitable for sequences with variable length. It is designed based on the block-level even-odd merge sort algorithm. It significantly outperforms the previous block sorter design by using more efficient algorithm, architectural pipelining, and better block C&S(BC&S) unit which can realize separate pre-sort and merge processes efficiently. Our implementation results show that by using the 0.18um technology, the core size of the proposed sorter with block-size of four is about 0.509mm2, and can sorting a 1024-point sequence within 32.84us.
    Advisory Committee
  • Chuen-Yau Chen - chair
  • Shiann-Rong Kuang - co-chair
  • Yun-Nan Chang - advisor
  • Files
  • etd-0831109-115655.pdf
  • indicate in-campus access in a year and off_campus not accessible
    Date of Submission 2009-08-31

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys