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”
One of the big problems in detecting malware is that there are so many different forms of the same malicious code. This problem of polymorphism is what led Rick Wesson to develop icewater, a clustering technique that identifies malware.
Presented at Shmoocon 2016, the icewater project is a new way to process and filter the vast number of samples one finds on the Internet. Processing 300,000 new samples a day to determine if they have polymorphic malware in them is a daunting task. The approach used here is to create a fingerprint from each binary sample by using a space-filling curve. Polymorphism will change a lot of the bits in each sample, but as with human fingerprints, patterns are still present in this binary fingerprints that indicate the sample is a variation on a previously known object.
Continue reading “Shmoocon 2016: GPUs and FPGAs to Better Detect Malware”
The Manchester Baby seems simple today. A 32-bit machine with 32 words of storage. It wasn’t meant to be a computer, though, but a test bed for the new Williams tube storage device. However, in 1948, it executed stored programs at about 1,100 instructions per second. The success of the machine led to a series of computers at Manchester University and finally to the first commercially available computer, the Ferranti Mark I.
[Dave] is lucky enough to volunteer to demonstrate the Baby replica at Machester’s Museum of Science Industry. He wanted his own Baby, so he used a Xilinx FPGA board to build a replica Baby named BabyBaby. Although it runs at the same speed as the original, it is–mercifully–much smaller than the real machine.
Continue reading “BabyBaby: A 1948 Computer on an FPGA”
When [iliasam] needed an Ethernet connection, he decided to see how much of the network interface he could put in the FPGA logic. Turns out that for 10 Base-T, he managed to get quite a bit inside the FPGA. His original post is in Russian, but automatic translation makes a passable attempt at converting to English.
This is a classic trade off all FPGA designers face: how much external logic do you use for a particular design. For example, do you add memory to the PCB, or use FPGA resources as memory? Each has its advantages and disadvantages (that’s why it is a trade off). However, if you are trying to keep things cheap, slashing external circuitry is often the way to go.
Continue reading “FPGA to Ethernet Direct”
[Clifford] presented a fully open-source toolchain for programming FPGAs. If you don’t think that this is an impressive piece of work, you don’t really understand FPGAs.
The toolchain, or “flow” as the FPGA kids like to call it, consists of three parts: Project IceStorm, a low-level tool that can build the bitstreams that flip individual bits inside the FPGA, Arachne-pnr, a place-and-route tool that turns a symbolic netlist into the physical stuff that IceStorm needs, and Yosys which synthesizes Verilog code into the netlists needed by Arachne. [Clifford] developed both IceStorm and Yosys, so he knows what he’s talking about.
What’s most impressive is that FPGAs aren’t the only target for this flow. Because it’s all open source and modifiable, it has also been used for designing custom ASICs, good to know when you’re in need of your own custom silicon. [Clifford]’s main focus in Yosys is on formal verification — making sure that the FPGA will behave as intended in the Verilog code. A fully open-source toolchain makes working on this task possible.
If you’ve been following along with [Al Williams]’s FPGA posts, either this introduction or his more recent intermediate series that are also based on the relatively cheap Lattice iCEStick development kit, this video is a must-watch. It’s a fantastic introduction to the cutting-edge in free FPGA tools.
[Kodera2t] wanted to experiment with programmable logic. Instead of going with an FPGA board, he decided to build his own CPLD (complex programmable logic device) board, with a built-in programmer. The CPLD is a Xilinx 9536 which is inexpensive and, though obsolete, still readily available. The programmer for the board uses an FT232RL and the total cost is very low ([kodera2t] says it is in the price range of a Raspberry Pi Zero or about $4).
From a user’s point of view, a CPLD is just a small FPGA. Internally, there is a significant difference in how they implement your design. Although there are differences between different product families, CPLDs usually use a sea of logic gates arranged as an AND/OR chain. By feeding inputs and inverted inputs into the AND gates and then ORing the results, you can build interesting logic circuits. However, modern CPLDs use Verilog or VHDL, so you describe what you want just like with an FPGA and the software figures out how to use the underlying circuits to give you what you want.
Continue reading “Not Ready for FPGAs? Try a CPLD”
When you think of developing with FPGAs, you usually think of writing Verilog or VHDL. However, there’s been a relatively recent trend to use C to describe what an FPGA should do and have tools that convert that to an FPGA. However, at least in the case of Xilinx parts, this capability is only available in their newest tool (Vivado), and Vivado doesn’t target the older lower-cost FPGAs that most low-cost development boards use.
[Sleibso] who blogs for Xilinx, has an answer. It turns out you can use the Vivado C compilation tools to generate code for older FPGAs; it just involves a less convenient workflow. Vivado (even the free version) generates unique files that the rest of the tool uses to pick up compiled C code. However, it also generates RTL (Verilog or VHDL) as a by-product, and you can import that into the older ISE tool (which has a perfectly fine free version) and treat it as you would any other RTL files.
There’s an example of using the Vivado tool in the video below. [Sleibso] points out that the video is three years old, and the talk about licensing on the video is out of date. The free tools now including this capability. [Sleibso] talks about using a Spartan 6, but the same split workflow should work with most devices ISE supports.
Continue reading “Xilinx FPGAs in C for Free”