article · Defense Technical Information Center (DTIC) · 1980

Parallel Record-Sorting Methods for Hardware Realization.

Cited by 5Abstract and details only

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 0(M 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)

Cite this paper

APA 7

Hsiao, D. K., & Menon, M. J. (1980). Parallel Record-Sorting Methods for Hardware Realization. Defense Technical Information Center (DTIC).

MLA 9

Hsiao, David K., and M. Jaishankar Menon. “Parallel Record-Sorting Methods for Hardware Realization.” Defense Technical Information Center (DTIC), 1980.

Chicago

Hsiao, David K., and M. Jaishankar Menon. 1980. “Parallel Record-Sorting Methods for Hardware Realization.” Defense Technical Information Center (DTIC).

Harvard

Hsiao, D.K. and Menon, M.J. (1980) ‘Parallel Record-Sorting Methods for Hardware Realization’, Defense Technical Information Center (DTIC).

BibTeX

@article{hsiao1980parallel,
  title = {{Parallel Record-Sorting Methods for Hardware Realization.}},
  author = {Hsiao, David K. and Menon, M. Jaishankar},
  journal = {Defense Technical Information Center (DTIC)},
  year = {1980}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.