Linear-Time Sorter for FPGAs

a parallel approach to a familiar problem, nicely wrapped up as an SPI slave

Similar projects worth following
Sorting Algorithms might be an old hat for computer scientists, but running times on the fastest of these algorithms is usually O(Nlog(N)) on a single core. I thought, with an FPGA, why not try a parallel approach in hardware to bring the running time down to O(N)?

A few head-scratching evenings later–behold–the Linear-Time-Sorter was born! I’m jazzed to mock this up as an SPI-peripheral for a microcontroller. Feel free to make use of the source files as you need.

The algorithm boils down to two questions asked in parallel across all cells. For each cell, we must answer the questions:

  1. am I empty or occupied?
  2. If occupied, is my current value pushed by either the previous cell value or the new value to be sorted?

Simultaneously, each cell also needs the answer to both of these questions from the previous cell.

Hence, we can build a logical block designed for this specific purpose that answers these questions within a single clock cycle:

Afterwards, we can specify a parameter in the SystemVerilog source files that specify just how many of these cells we want for our particular application. A Sorter with N cells can sort lists of length up to length N in linear time!

For more details, and a full walkthrough of how these cells talk to each other as they sort new inputs, check out the step-by-step example on my webpage

View project log

Enjoy this project?



Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates