Sort Faster with FPGAs

Sorting. It’s a classic problem that’s been studied for decades, and it’s a great first step towards “thinking algorithmically.” Over the years, a handful of sorting algorithms have emerged, each characterizable by it’s asymptotic order, a measure of how much longer an algorithm takes as the problem size gets bigger. While all sorting algorithms take longer to complete the more elements that must be sorted, some are slower than others.

For a sorter like bubble sort, the time grows quadradically longer for a linear increase in the number of inputs; it’s of order O(N²).With a faster sorter like merge-sort, which is O(N*log(N)), the time required grows far less quickly as the problem size gets bigger. Since sorting is a bit old-hat among many folks here, and since O(N*log(N)) seems to be the generally-accepted baseline for top speed with a single core, I thought I’d pop the question: can we go faster?

In short — yes, we can! In fact, I’ll claim that we can sort in linear time, i.e a running time of O(N). There’s a catch, though: to achieve linear time, we’ll need to build some custom hardware to help us out. In this post, I’ll unfold the problem of sorting in parallel, and then I”ll take us through a linear-time solution that we can synthesize at home on an FPGA.

Need to cut to the chase? Check out the full solution implemented in SystemVerilog on GitHub. I’ve wrapped it inside an SPI communication layer so that we can play with it using an everyday microcontroller.

To understand how it works, join us as we embark on an adventure in designing algorithms for hardware. If you’re used to thinking of programming in a stepwise fashion for a CPU, it’s time to get out your thinking cap!

Continue reading “Sort Faster with FPGAs”

Need An Idea For Your Next Kickstarter? Check Out This Kickstarter!


Kickstarter has become the most powerful force in kickstarting new hardware projects, video games, documentaries, and board games, and now everyone wants a piece of the action. The problem obviously isn’t product development and engineering; you can just conjure that up with a little bit of Photoshop and some good PR. The only you really need for a good Kickstarter is an idea, and META is just the tool for the job. It’s the Arduino-powered Motivational Electronic Text Adviser, the perfect device to generate the next big idea in the world of crowdfunding.

The Arduino-powered META includes three buttons and an Arduino-controlled LCD display. Press a button, and the next big hardware project to wash across the blogs faster than the announcement of a campaign for a $300 3D printer will appear on the screen.

Because META is Arduino-compatible, it’s compatible with existing Arduino sketches. This makes turning the META into the next home automated Bluetooth low energy 4.0 internet of things a snap. Because this is open hardware the laser cut enclosure can easily be upgraded to an RGB LED 3D printer robotic drone bluetooth boombox.

If Kickstarters aren’t your thing, there’s also a cloud-based META that will generate ideas in the mobile app browser cloud. Bitcoin.