A Novel Deterministic Sampling Scheme with Applications to Broadcast-Efficient Sorting on the Reconfigurable Mesh
| Autor: | Stephan Olariu, James L. Schwing |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Scheme (programming language)
Sorting algorithm Computer Networks and Communications business.industry Computer science Sorting Sampling (statistics) Control reconfiguration Broadcasting Theoretical Computer Science Parallel processing (DSP implementation) Artificial Intelligence Hardware and Architecture Data_FILES Bucket sort business computer Algorithm Software computer.programming_language |
| Zdroj: | Journal of Parallel and Distributed Computing. 32:215-222 |
| ISSN: | 0743-7315 |
| DOI: | 10.1006/jpdc.1996.0015 |
| Popis: | The main contribution of this work is to present a simple deterministic sampling strategy that, when used for bucket sorting, yields buckets that are remarkably well balanced, making costly balancing unnecessary. To the best of our knowledge, this is the first instance of a deterministic sampling strategy featuring this performance. Although the strategy is perfectly general, we illustrate its power by devising a VLSI-optimal,O(1) time sorting algorithm for the reconfigurable mesh. As a by-product of the inherent simplicity of our sampling and bucketing scheme, we show that our sorting algorithm can be implemented using only 35 broadcast operations, a substantial improvement over the previously best known algorithm that requires 59 broadcasts. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect