0%
0%

# Linear-Time Sorter for FPGAs

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

Similar projects worth following
851 views
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

• ### Digging into Parallel Sorting

Joshua Vasquez02/10/2016 at 06:43 0 comments

For a deeper walkthrough on how this one works, check out the Hackaday post. I received a lot of fantastic in the comments, including some great tips to research papers doing the exact same thing!

Here were a couple links where others have dug even deeper:

(A special thanks to the commenters on Hackaday and Hackernews for finding these!)

Share

## Similar Projects

Project Owner Contributor

### Free creation of objects

Michał

Project Owner Contributor

### C10

KnivD

Project Owner Contributor

### Protothreads helps GCC program organization

Bruce Land

Project Owner Contributor

nqtronix

# Does this project spark your interest?

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