# 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!

# Saving Old Voices By Dumping ROMs

Some people collect stamps. Others collect porcelain miniatures. [David Viens] collects voice synthesizers and their ROMs. In this video, he just got his hands on the ultra-rare Electronic Voice Alert (EVA) from early 1980s Chrysler automobiles (video embedded below the break).

Back in the 1980s, speech synthesis was in its golden years following the development of TI’s linear-predictive coding speech chips. These are the bits of silicon that gave voice to the Speak and Spell, numerous video game machines, and the TI 99/4A computer’s speech module. And, apparently, some models of Chrysler cars.

We tracked [David]’s website down. He posted a brief entry describing his emulation and ROM-dumping setup. He says he used it for testing out his (software) TMS5200 speech-synthesizer emulation.

The board appears to have a socket for a TMS-series voice synthesizer chip and another slot for the ROM. It looks like an FTDI 2232 USB-serial converter is being used in bit-bang mode with some custom code driving everything, and presumably sniffing data in the middle. We’d love to see a bunch more detail.

The best part of the video, aside from the ROM-dumping goodness, comes at the end when [David] tosses the ROM’s contents into his own chipspeech emulator and starts playing “your engine oil pressure is critical” up and down the keyboard. Fantastic.

# Robots And Crickets

If you watch science fiction movies, the robots of the future look like us. The truth is, though, many tasks go better when robots don’t look like us. Sometimes they are unique to a particular job or sometimes it is useful to draw inspiration from something other than a human being. One professor at Johns Hopkins along with some students decided to look at spider crickets as an inspiration for a new breed of jumping robots.