The Art of FPGA Design - Post 35

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;

       I:in T_VECTOR;

       O:out T_VECTOR);

end DELAY;

architecture TEST of DELAY is

begin

  i0:if SIZE=0 generate

       O<=I;

     end generate;

  il:if SIZE>0 generate

       type T_MATRIX is array(INTEGER range <>) of T_VECTOR(O'range);

       signal D:T_MATRIX(1 to SIZE):=(others=>(others=>T_ZERO));

       attribute keep:STRING;

       attribute keep of D:signal is "TRUE";

     begin

       process(CLK)

       begin

         if rising_edge(CLK) then

           for K in D'range loop

             if K=D'low then

               D(K)<=I;

             else

               D(K)<=D(K-1);

             end if;

           end loop;

         end if;

       end process;

       O<=D(D'high);

     end generate;

end TEST;

and a generic BDELAY block for BOOLEAN signals:

library ieee;

use ieee.std_logic_1164.ALL;

entity BDELAY is

  generic(SIZE:INTEGER:=1);

  port(CLK:in STD_LOGIC:='0';

       I:in BOOLEAN;

       O:out BOOLEAN);

end BDELAY;

architecture TEST of BDELAY is

begin

  i0:if SIZE=0 generate

       O<=I;

     end generate;

  il:if SIZE>0 generate

       type BOOLEAN_VECTOR is array(INTEGER range <>) of BOOLEAN;

       signal D:BOOLEAN_VECTOR(1 to SIZE):=(others=>FALSE);

     begin

       process(CLK)

       begin

         if rising_edge(CLK) then

           for K in D'range loop

             if K=D'low then

               D(K)<=I;

             else

               D(K)<=D(K-1);

             end if;

           end loop;

         end if;

       end process;

       O<=D(D'high);

     end generate;

end TEST;

Now that we have a complete set of source files for the generic sorting network design we only need a top level test module, which defines the size N of the network (remember that the basic type is also user definable in the SORTER_PKG package). We will use for a test a sorting network of size N=16, sorting UNSIGNED(7 downto 0) elements:

library IEEE;

use IEEE.STD_LOGIC_1164.ALL;

use work.SORTER_PKG.all;

-- MERGE_SORT takes an array as argument and returns the sorted array as a result

-- if N is even the array is divided into two equal parts

-- if N is odd the first part is one element longer than the second part

entity TEST_MERGE_SORT is

  generic(CE_LATENCY:INTEGER:=1;

          SIZE:INTEGER:=16);

  port(CLK:in STD_LOGIC:='0';

       I:in T_VECTOR(1 to SIZE);

       VI:in BOOLEAN:=TRUE;

       O:out T_VECTOR(1 to SIZE);

       VO:out BOOLEAN);

end TEST_MERGE_SORT;

architecture TEST of TEST_MERGE_SORT is

  signal RI:T_VECTOR(I'range);

  signal RVI:BOOLEAN;

begin

  process(CLK)

  begin

    if rising_edge(CLK) then

      RI<=I;

      RVI<=VI;

    end if;

  end process;

  ms:entity work.MERGE_SORT generic map(CE_LATENCY=>CE_LATENCY)

                            port map(CLK=>CLK,

                                     I=>RI,

                                     VI=>RVI,

                                     O=>O,

                                     VO=>VO);

end TEST;

The registered inputs RI and RVI are not part of the design itself and are there just as placeholders for the logic driving the sorting network inputs so that we can get an accurate timing estimate, we will subtract these registers from the utilization numbers.

The implemented design for N=16 uses 757 LUTs and 1281 FFs, which is really insignificant, even for the smallest FPGA. More importantly, this is a very fast design, it will close timing in the fastest speed grade Ultrascale+ FPGA at 967 MHz, which is more then the maximum allowed clock speed of 891 MHz for this device family. What this means is that we can sort a new set of 16 8-bit unsigned numbers every 1.1 ns. We are achieving something that is not even remotely possible with a software based algorithm running on a CPU, while using well less than 1% of even a small FPGA.

Yes, N=16 is actually a very small test case, so what about a larger sorting network, say N=64? All we have to do is change the SIZE generic in TEST_MERGE_SORT and re-implement. The design is using now 6997 LUTs and 10753 FFs and closes timing at 934 MHz, still over the maximum possible frequency of 891MHz.

Let's raise the bar even higher now for a really big test case, for example N=1024? This is again very easy to test, just by changing the value of the SIZE generic to 1024. We can see here the power of recursive component instantiations, the N=1024 design has now 66052 sub-components, all generated from less than 200 lines of VHDL code! This is a big design, the size has increased significantly to 352366 LUTs and 450561 FFs which is 83% of a medium size FPGA like ZCU17EG and the clock speed also got lower at 503MHz but keep in mind that we are sorting a new set of 1024 8-bit unsigned values every 2.0 ns and we could instantiate multiple such sorting networks in a larger FPGA, all of them running in parallel if we need to increase throughput even further. So this is still a tremendous amount of computations done in parallel at a very high rate.

We are close to the end of this sorting network saga, I will conclude it next week with the answer to a really important question - how do we know this design actually does what it is supposed to do? How do you verify a sorting network of size 1024?

Back to the top: The Art of FPGA Design