Back to Search
Start Over
Deriving concentrators from binary sorters using half cleaners
- Source :
- ReConFig
- Publication Year :
- 2017
- Publisher :
- IEEE, 2017.
-
Abstract
- Many non-blocking and self-routing interconnection networks are based on the radix sorting paradigm which requires the design of concentrator modules to distribute the given inputs to subnetworks for the recursive calls. To that end, binary sorters are often used that sort the inputs in each recursive call by one bit of their destination addresses starting with the most significant bit down to the least significant one. It is well-known that the use of more general concentrators instead of binary sorters may lead to more efficient circuits. However, the design of concentrators turned out to be a challenging task for many decades. In this paper, we construct from any binary sorter a corresponding concentrator by means of Batcher's half cleaner circuit. This way, we can improve many interconnection networks that are based on binary radix sorting in that we replace their binary sorters by the corresponding concentrators obtained by our optimization. We have implemented various binary sorters and their corresponding concentrators and demonstrate by experimental results the improvements we achieved this way.
- Subjects :
- Binary tree
Computer science
Radix sort
Sorting
Binary number
0102 computer and information sciences
02 engineering and technology
Concentrator
01 natural sciences
Computer engineering
Most significant bit
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
sort
020201 artificial intelligence & image processing
Routing (electronic design automation)
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig)
- Accession number :
- edsair.doi...........b13576a475f760f8c99b0b4741de3555