Skip to main navigation Skip to search Skip to main content

Hardware Architecture for a Bit-Serial Odd-Even Transposition Sort Network with On-The-Fly Compare and Swap

  • Ghattas Akkad
  • , Rafic Ayoubi
  • , Ali Mansour
  • , Bachar ElHassan
  • University of Balamand
  • LAB-STICC
  • Lebanese University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

Sorting algorithms are computationally expensive routines frequently executed on modern computers and embedded systems. Implementing sorting algorithms on dedicated hardware can contribute significantly to the overall execution time of the processes and applications embodying them. However, such algorithms are known to suffer from a trade off between convergence time and computational complexity. Consequently, this causes performance degradation i.e. bottleneck, when implemented on dedicated hardware with limited resources. In this respect, this paper proposes a novel sequential hardware architecture for a bit-serial Odd-Even transposition sorting network with on-the-fly compare and swap, on field programmable gate array (FPGA). In contrast to the classical parallel-data architecture, which operates on N data bits, this implementation significantly minimizes resource utilization while offering higher clock frequency, on the fly compare and swap and preserving O(N) performance complexity. Simulation and synthesis results demonstrates that the proposed architecture is parallel, minimal in size, can operate on much larger arrays for a reference area size, can be easily expanded, and can achieve higher operating frequency.

Original languageEnglish
Title of host publicationApplications in Electronics Pervading Industry, Environment and Society - APPLEPIES 2019
EditorsSergio Saponara, Alessandro De Gloria
PublisherSpringer
Pages145-154
Number of pages10
ISBN (Print)9783030372767
DOIs
Publication statusPublished - 1 Jan 2020
EventInternational Conference on Applications in Electronics Pervading Industry, Environment and Society, ApplePies 2019 - Pisa, Italy
Duration: 11 Sept 2019 → 13 Sept 2019

Publication series

NameLecture Notes in Electrical Engineering
Volume627
ISSN (Print)1876-1100
ISSN (Electronic)1876-1119

Conference

ConferenceInternational Conference on Applications in Electronics Pervading Industry, Environment and Society, ApplePies 2019
Country/TerritoryItaly
CityPisa
Period11/09/19 → 13/09/19

Keywords

  • Bit-serial
  • Embedded systems
  • FPGA
  • Hardware architecture
  • Low latency
  • Median filter
  • Odd-Even transposition
  • Sorting

Fingerprint

Dive into the research topics of 'Hardware Architecture for a Bit-Serial Odd-Even Transposition Sort Network with On-The-Fly Compare and Swap'. Together they form a unique fingerprint.

Cite this