Go home now Header Background Image
Search
Submission Procedure
share: |
 
Follow us
 
 
 
 
Volume 23 / Issue 1

available in:   PDF (132 kB) PS (237 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
Links into Future

 

A Logical Reconstruction of Batcher's Mergers
Or: Bitonicity is a Red Herring

Ralf Hinze (Radboud University, The Netherlands)

Clare Martin (Oxford Brookes University, United Kingdom)

Abstract: Almost half a century after Batcher wrote his seminal paper on sorting networks, we revisit the key algorithmic design decisions for oblivious merging to re- discover his schemes in a disciplined way. The design space of sorting networks is ex- plored, resulting in a systematic reconstruction of schemes that appear in the literature in various guises.

Keywords: functional programming, hardware design, parallel algorithms

Categories: D.3.2, D.3.3