DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA090192
Title:
Parallel Record-Sorting Methods for Hardware Realization.
Descriptive Note:
Technical rept.,
Corporate Author:
OHIO STATE UNIV COLUMBUS COMPUTER AND INFORMATION SCIENCE RESEARCH CENTER
Report Date:
1980-07-01
Pagination or Media Count:
47.0
Abstract:
In this report, we demonstrate methods for implementing a fast hardware sorter in DBC. Given the trend towards cheaper processors and block-oriented access memories, we are especially interested in methods that utilize multiple processors with large-capacity block-oriented access memories in a parallel fashion. Many parallel sorting methods are already available. Most of these methods use P processors to sort P records. Even though these methods are fast, they suffer from the fact that groups of records larger than P in number will have to be sorted in separate batches and then merged. Batching and merging defeats the intent of parallelism for high performance. Our methods, therefore, attempt to use P processors to sort more than P records without the need for batching and merging. Furthermore, our methods employ block-oriented access memories such as magnetic bubbles and charge-coupled devices. Three sorting methods are described in this report. The first one, called the odd-even sort, uses P processors, each of which utilizes its own block-access memory to accommodate M records and has two processor-to-processor interconnections. This method sorts MP records in 0M log M MP time. There is no restriction on either P or M. More importantly, since each processor needs to be connected to only two others, we can increase the number of processors in the sorter without having to increase the number of connections per processor. Author
Distribution Statement:
APPROVED FOR PUBLIC RELEASE
