Skip navigation
Sorting Networks - The Verification Problem   In the final post on this subject of parallel sorting using FPGAs I will talk about the difficult issue of how to verify that such a design actually works. That is when given a set of any N input numbers in any arbitrary order the design outputs them in ascending sorted order. There are two main verification strategies for hardware designs, based on formal proof and exhaustive testing. The first one uses logical mathematical methods to prove th ...
Sorting Networks - The results for the VHDL implementation of Batcher's sorting algorithm   So how good is this VHDL implementation of a parallel sorting network? Before we look at the results here are the two modules that were missing from the previous post, a generic DELAY module for elements to be sorted:   library ieee;   use ieee.std_logic_1164.ALL;   use work.SORTER_PKG.all;   entity DELAY is   generic(SIZE:INTEGER:=1);   port(CLK:in STD_LOGIC; ...
A couple of months back I received a ZC702 Xilinx development board from Randall after pitching an idea on how to build an embedded vision project. The board arrived a couple of weeks later (thank you Randall) and I started working on the required steps to build an embedded vision application that targets lane detection. The main idea was to build a vision system capable of automatic lane detection. In a nutshell,  I wanted to build a custom embedded vision app that would takes images from ...
Sorting Networks - The VHDL implementation of Batcher's sorting algorithm   OK, enough with the preliminaries, it's time now for the real deal, how do we implement in an FPGA this parallel sorting network thing. The main design goals are creating a generic, reusable and efficient implementation. We want to be able to implement a sorting network of any size N with a single piece of code, we want to be able to sort all kinds of data, not just integers and we want something close in size to ...
Sorting Networks - The Batcher or odd-even mergesort sorting algorithm   Now that we have defined the FPGA design engineering problem - parallel sorting of a set of N items in one clock, that is one new sorting operation starting every clock - we need to chose a sorting algorithm.While ideal in terms of performance (number of compare-exchange operations respectively latency) optimal sorting networks are irregular and more importantly they cannot be generated programmatically for an arbitr ...

Filter Blog

By date: By tag: