Tradeoff Analysis and Architecture Design of a Hybrid Hardware/Software Sorter

Bednara M, Beyer O, Teich J, Wanka R (2000)

Publication Type: Conference contribution

Publication year: 2000

Publisher: IEEE

Edited Volumes: Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors

Pages Range: 299-308

Conference Proceedings Title: Proc. ASAP'00, the Int. Conf. on Application Specific Systems, Architectures, and Processors, pp. 299-308, Boston, MA, U.S.A. IEEE Computer Society Press, July 2000Proc. ASAP'00, the Int. Conf. on Application Specific Systems, Architectures, and Processors

Event location: Boston, MA US

Abstract

Sorting long sequences of keys is a problem that occurs in many different applications. For embedded systems, a uniprocessor software solution is often not applicable due to the low performance, while realizing multiprocessor sorting methods on parallel computers is much too expensive with respect to power consumption, physical weight, and cost. We investigate cost/performance tradeoffs for hybrid sorting algorithms that use a mixture of sequential merge sort and systolic insertion sort techniques. We propose a scalable architecture for integer sorting that consists of a uniprocessor and an FPGA-based parallel systolic co-processor. Speedups obtained analytically and experimentally and depending on hardware (cost) constraints are determined as a function of time constants of the uniprocessor and the co-processor.

Authors with CRIS profile

Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Rolf Wanka Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

Related research project(s)

Dedizierte massiv parallele Systeme (PARO) Jan. 3, 2000 - Jan. 3, 2003

Involved external institutions

Universität Paderborn DE Germany (DE)

How to cite

APA:

Bednara, M., Beyer, O., Teich, J., & Wanka, R. (2000). Tradeoff Analysis and Architecture Design of a Hybrid Hardware/Software Sorter. In Proc. ASAP'00, the Int. Conf. on Application Specific Systems, Architectures, and Processors, pp. 299-308, Boston, MA, U.S.A. IEEE Computer Society Press, July 2000Proc. ASAP'00, the Int. Conf. on Application Specific Systems, Architectures, and Processors (pp. 299-308). Boston, MA, US: IEEE.

MLA:

Bednara, Marcus, et al. "Tradeoff Analysis and Architecture Design of a Hybrid Hardware/Software Sorter." Proceedings of the Int. Conf. on Application Specific Systems, Architectures, and Processors, pp. 299-308, Boston, MA, U.S.A. IEEE Computer Society Press, July 2000Proc. ASAP'00, the Int. Conf. on Application Specific Systems, Architectures, and Processors,, Boston, MA IEEE, 2000. 299-308.

BibTeX: Download