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”
[Tomas] wanted to try building something mechanical with electronic control, and ended up with this sorter that organizes beads into one of two containers based on color. He built most of the structure from popular interlocking plastic bricks, then added a stepper motor salvaged from an old scanner and two plastic discs.
The two discs sit on top of each other. The bottom one is stationary and has two holes drilled in it, with a container sitting below each hole. The top disc has a smaller, bead-sized hole and rotates from its starting position—where it collects one bead—to a camera for analysis. After the camera determines the color of the bead, the disc rotates again to position itself over one of the two sorting holes in the disc below, and the bead falls into the awaiting container. The device is controlled by the MSP430 microcontroller on a FITKit (translated), which is the development platform of choice for [Tomas’s] school.
[Tomas] originally attempted to determine the color of beads by using 3 different color LEDs and a light-dependent resistor, but switched to using a webcam and a Java program to capture images and calculating average hues. You can find more details and the source code on his site, but first see the short video below.
Continue reading “Automatically Sorting Beads by Color”
In 1982, Van Halen had the biggest stage show around. Their rider – a document going over the requirements for the show – reflects this. In the middle of the requirements for the lighting and sound rigs, Van Halen placed a rather odd request; one (1) bowl of M&M, (ABSOLUTELY NO BROWN ONES). The theory being if the request for no brown M&Ms wasn’t followed, the lighting and sound rigs probably weren’t up to spec either.
It’s not M&Ms this time (they wouldn’t fit in the machine), but [egenriether] came up with a seriously clever solution for sorting Skittles by color. Why? We have no idea, other than, ‘just because.’
The build details are a little scant, but we know [egenriether] used a BASIC Stamp 2 for the electronics portion of the build. To sort the Skittles by color, a TAOS RGB color sensor reads the red, green, and blue values for each Skittle and actuates a servo that guides each piece of candy into its respective bowl.
It’s a very, very cool, if completely useless build. Still, we’re thinking it could be put to use if [egenriether] is ever backstage setting up before the band arrives.
Videos after the break. Thanks [Andrew] for sending this one in.
Continue reading “Skittles sorting machine sorts Skittles, keeps the band happy”
[Chris] is quite the devoted tinkerer. He recently wrote in to share what can only be described as a labor of love. His Quad Delta Robot system has been in the works for about six years now, split into periods of research, building, more research, and rebuilding until arriving at its current form.
The system is made up of four Lego NXT robots which are tasked with sorting Lego cubes by color as they come down a pair of conveyer belts. The robots were built to mimic commercially available pick and place robots which can be found on assembly lines all over the world.
Each robot operates independently, receiving signals via a light sensor which tells the robot where the next brick is located, as well as what color it is. This data is sent by the main NXT unit, which uses a lights sensor to determine brick color and position, relaying the information to the other bots via flashing LEDs. All of the robots receive the same signal, but much like NIC cards ignore frames not destined for their MAC, the bots ignore messages that are not addressed to them.
The machine is truly amazing to watch – it’s clear that all of [Chris’] research and planning has paid off. You have to check out the video embedded below to truly appreciate all of the work that went into this system. Also, be sure to swing by his site for a far more in-depth look at how the machines work, it is definitely worth the time.
Continue reading “Amazing quad pick and place system tirelessly sorts your Legos”