The analysis and synthesis of a parallel sorting engine Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/f4752m11q

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • This thesis is concerned with the development of a unique parallel sort-merge system suitable for implementation in VLSI. Two new sorting subsystems, a high performance VLSI sorter and a four-way merger, were also realized during the development process. In addition, the analysis of several existing parallel sorting architectures and algorithms was carried out. Algorithmic time complexity, VLSI processor performance, and chip area requirements for the existing sorting systems were evaluated. The rebound sorting algorithm was determined to be the most efficient among those considered. The rebound sorter algorithm was implemented in hardware as a systolic array with external expansion capability. The second phase of the research involved analyzing several parallel merge algorithms and their buffer management schemes. The dominant considerations for this phase of the research were the achievement of minimum VLSI chip area, design complexity, and logic delay. It was determined that the proposed merger architecture could be implemented in several ways. Selecting the appropriate microarchitecture for the merger, given the constraints of chip area and performance, was the major problem. The tradeoffs associated with this process are outlined. Finally, a pipelined sort-merge system was implemented in VLSI by combining a rebound sorter and a four-way merger on a single chip. The final chip size was 416 mils by 432 mils. Two micron CMOS technology was utilized in this chip realization. An overall throughput rate of 10M bytes/sec was achieved. The prototype system developed is capable of sorting thirty two 2-byte keys during each merge phase. If extended, this system is capable of economically sorting files of 100M bytes or more in size. In order to sort larger files, this design should be incorporated in a disk-based sort-merge system. A simplified disk I/O access model for such a system was studied. In this study the sort-merge system was assumed to be part of a disk controller subsystem.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome, 24-bit Color) using ScandAll PRO 1.8.1 on a Fi-6670 in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Submitted by Katy Davis (kdscannerosu@gmail.com) on 2013-05-15T21:55:27Z No. of bitstreams: 1 AhnByoungchul1989.pdf: 2213929 bytes, checksum: 00bb00d9035175b281f7971b7d26145f (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-05-29T15:42:13Z (GMT) No. of bitstreams: 1 AhnByoungchul1989.pdf: 2213929 bytes, checksum: 00bb00d9035175b281f7971b7d26145f (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-05-30T15:31:15Z (GMT) No. of bitstreams: 1 AhnByoungchul1989.pdf: 2213929 bytes, checksum: 00bb00d9035175b281f7971b7d26145f (MD5)
  • description.provenance : Made available in DSpace on 2013-05-30T15:31:15Z (GMT). No. of bitstreams: 1 AhnByoungchul1989.pdf: 2213929 bytes, checksum: 00bb00d9035175b281f7971b7d26145f (MD5) Previous issue date: 1989-05-03

Relationships

In Administrative Set:
Last modified: 08/22/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items