VHDL-Only Implementation

[bpadalino]

I saw your reddit post and thought it's a good task to try and make into a pure generic VHDL thing, especially with VHDL-2019 constructs. I've put together the following:

package sorting_pkg is
    -- elements indices for comparison
    type elements is (l, r) ;

    -- the indices that need to be compared
    type tuple_t is array(elements) of integer ;
    constant IGNORE : tuple_t := tuple_t'(-1, -1) ;

    -- the array of comparisons that need to happen based on the number of stages and the number of elements
    -- an array entry with both indices the same natural index, pass-through
    -- an array entry with both indices -1, ignore
    type comparisons_t is array(natural range <>, natural range <>) of tuple_t ;

    -- get the comparisons
    function get_comparisons(constant num_elements : in positive) return comparisons_t ;

    -- invalid entries
    constant NULL_COMPARISONS : comparisons_t(0 to -1, 0 to -1) := (others => (others => IGNORE)) ;

    type direction_t is (ASCENDING, DESCENDING) ;

end package ;

package body sorting_pkg is

    function init_comparisons(constant num_elements, num_stages : in positive) return comparisons_t is
        variable rv : comparisons_t(0 to num_stages-1, 0 to num_elements-1) := (others => (others => IGNORE));
    begin
        return rv ;
    end function ;

    function comparisons_2 return comparisons_t is
        variable rv : comparisons_t := init_comparisons(num_elements => 2, num_stages => 1) ;
    begin
        rv(0,0) := (0, 1) ; -- stage 0: 1 comparison
        return rv ;
    end function ;

    function comparisons_3 return comparisons_t is
        variable rv : comparisons_t := init_comparisons(num_elements => 3, num_stages => 3) ;
    begin
        rv(0,0) := (0,2); rv(0,1) := (1,1); -- stage 0: 1 comparison, 1 pass-through
        rv(1,0) := (0,1); rv(1,1) := (2,2); -- stage 1: 1 comparison, 1 pass-through
        rv(2,0) := (1,2); rv(2,1) := (0,0); -- stage 2: 1 comparison, 1 pass-through
        return rv ;
    end function ;

    function comparisons_4 return comparisons_t is
        variable rv : comparisons_t := init_comparisons(num_elements => 4, num_stages => 3) ;
    begin
        rv(0,0) := (0,2); rv(0,1) := (1,3);                   -- stage 0: 2 comparisons
        rv(1,0) := (0,1); rv(1,1) := (2,3);                   -- stage 1: 2 comparisons
        rv(2,0) := (1,2); rv(2,1) := (0,0); rv(2,2) := (3,3); -- stage 3: 1 comparison, 2 pass-through
        return rv;
    end function ;

    -- TODO: Create a function to make these entries for all possible networks
    function comparisons_8 return comparisons_t is
        variable rv : comparisons_t := init_comparisons(num_elements => 8, num_stages => 6) ;
    begin
        rv(0,0) := (0,2); rv(0,1) := (1,3); rv(0,2) := (4,6); rv(0,3) := (5,7);                                     -- stage 0: 4 comparisons
        rv(1,0) := (0,4); rv(1,1) := (1,5); rv(1,2) := (2,6); rv(1,3) := (3,7);                                     -- stage 1: 4 comparisons
        rv(2,0) := (0,1); rv(2,1) := (2,3); rv(2,2) := (4,5); rv(2,3) := (6,7);                                     -- stage 2: 4 comparisons
        rv(3,0) := (2,4); rv(3,1) := (3,5); rv(3,2) := (0,0); rv(3,3) := (1,1); rv(3,4) := (6,6); rv(3,5) := (7,7); -- stage 3: 2 comparisons, 4 pass-through
        rv(4,0) := (1,4); rv(4,1) := (3,6); rv(4,2) := (0,0); rv(4,3) := (2,2); rv(4,4) := (5,5); rv(4,5) := (7,7); -- stage 4: 2 comparisons, 4 pass-through
        rv(5,0) := (1,2); rv(5,1) := (3,4); rv(5,2) := (5,6); rv(5,3) := (0,0); rv(5,4) := (7,7);                   -- stage 5: 3 comparisons, 2 pass-through
        return rv;
    end function ;

    function get_comparisons(constant num_elements : in positive) return comparisons_t is
    begin
        case num_elements is
            when 2      => return comparisons_2 ;
            when 3      => return comparisons_3 ;
            when 4      => return comparisons_4 ;
            when 8      => return comparisons_8 ;
            when others => return NULL_COMPARISONS ;
        end case ;
    end function ;

end package body ;

library ieee;
use ieee.std_logic_1164.all;

use work.sorting_pkg.all ;

entity sorting_network is
  generic (
    type a is array(natural range <>) of type is private;
    function "<"(l, r : in a'element) return boolean is <>;
    direction   : direction_t := ASCENDING ;
    comparisons : comparisons_t
  );
  port(
    clock       : in    std_logic;
    unsorted    : in    a ;
    sorted      : out   a
  );
end entity;

architecture arch of sorting_network is

    constant NUM_ELEMENTS   : natural := a'length ;
    constant NUM_STAGES     : natural := comparisons'length(1) ;

    -- Riviera PRO doesn't like this
    --subtype STAGES is comparisons'range(1) ;
    --subtype ELEMENTS is a'range ;

    subtype STAGES is natural range 0 to comparisons'length(1) ;
    subtype ELEMENTS is natural range 0 to a'length(1)-1 ;

    type data_array is array (natural range <>, natural range <>) of a'element ;
    signal data : data_array(STAGES, ELEMENTS) ;

begin

    process(clock) begin
        -- Input and output assignments
        for element in 0 to NUM_ELEMENTS-1 loop
            data(0, element) <= unsorted(element) ;
        end loop ;

        if (rising_edge(clock) ) then
            for stage in 0 to NUM_STAGES-1 loop
                for element in 0 to NUM_ELEMENTS-1 loop
                    if comparisons(stage,element)(l) = -1 then
                        -- Ignore the entry
                        null ;
                    else
                        -- Assume pass-through
                        data(stage+1, comparisons(stage, element)(l)) <= data(stage, comparisons(stage, element)(l)) ;
                        data(stage+1, comparisons(stage, element)(r)) <= data(stage, comparisons(stage, element)(r)) ;

                        if (direction = ASCENDING and (data(stage, comparisons(stage, element)(r)) < data(stage, comparisons(stage, element)(l)))) or
                           (direction = DESCENDING and (data(stage, comparisons(stage, element)(l)) < data(stage, comparisons(stage, element)(r)))) then
                            -- Swap
                            data(stage+1, comparisons(stage, element)(l)) <= data(stage, comparisons(stage, element)(r)) ;
                            data(stage+1, comparisons(stage, element)(r)) <= data(stage, comparisons(stage, element)(l)) ;
                        end if ;
                    end if ;
                end loop ;
            end loop ;
        end if ;
    end process ;

    -- Output assignments
    gen_output : for element in 0 to NUM_ELEMENTS-1 generate
        sorted(element) <= data(NUM_STAGES, element) ;
    end generate ;

end architecture ;

library ieee ;
use ieee.std_logic_1164.all ;
use work.sorting_pkg.all ;

entity sorting_tb is
end entity ;

architecture arch of sorting_tb is

    constant NUM_ELEMENTS : positive := 8 ;

    -- Get the sorting network based on the number of elements
    constant comparisons : comparisons_t := get_comparisons(num_elements => NUM_ELEMENTS) ;

    -- A couple of input data types
    type data_t is array(0 to NUM_ELEMENTS-1) of natural ;
    type data2_t is array(0 to NUM_ELEMENTS-1) of real ;

    -- Common clock
    signal clock    : std_ulogic := '1' ;

    -- Natural data type
    signal data     : data_t ;
    signal sorted   : data_t ;

    -- Real data type
    signal data2    : data2_t ;
    signal sorted2  : data2_t ;

    procedure nop(signal clock : in std_ulogic ; count : in natural) is
    begin
        for i in 1 to count loop
            wait until rising_edge(clock) ;
        end loop ;
    end procedure ;

begin

    -- Make sure we have a valid network
    assert comparisons'length(1) > 0 report "NULL sorting network" severity failure ;

    U_natural_network : entity work.sorting_network
      generic map (
        a           => data'subtype,
        comparisons => comparisons,
        direction   => ASCENDING
      ) port map (
        clock       => clock,
        unsorted    => data,
        sorted      => sorted
      ) ;

    U_real_network : entity work.sorting_network
      generic map (
        a           => data2'subtype,
        comparisons => comparisons,
        direction   => DESCENDING
      ) port map (
        clock       => clock,
        unsorted    => data2,
        sorted      => sorted2
      ) ;

    clock <= not clock after 1 ns ;

    tb : process
    begin
        data <= (80, 70, 60, 50, 40, 30, 20, 10) ;
        data2 <= (80.0, 70.0, 60.0, 50.0, 40.0, 30.0, 20.0, 10.0) ;
        nop(clock, 10) ;
        data <= (15, 85, 25, 75, 35, 65, 45, 55) ;
        data2 <= (15.0, 85.0, 25.0, 75.0, 35.0, 65.0, 45.0, 55.0) ;
        nop(clock, 10) ;
        std.env.stop ;
    end process ;

end architecture ;

It might be nice to fill it out to up to 64 inputs and add in the pipeline stages, but either way it might be nice to include a VHDL-only version instead of relying on rust to generate something.

What do you think?

[Chris44442]

hi, thanks for the suggestion.

A couple of things here:

• I only used Rust because I need to get better at it lol. This should've been done in Python for ease of use if I wanted this to reach as many people as possible. Oh well.
• One of my goals was to make the resulting VHDL code as simple (not necessarily easy) as possible. The reason being readability for as many users as possible but also portability, which VHDL 2019 is sadly a no-go still. I also considered using nested loops, but the way I did it rearranging the not-sorted parts of each stage were kind of messy. Your way looks cool though.
• I also wanted full control for the user over each pipeline stage. To modify your code to give the user this control would make it even more complex. Currently you only support to register every single stage. I wanted the user to have granular control and also make it possible to keep resources and latency at a minimum.
• One of the main features is to read the SorterHunter json files which already contain all the best currently known sorting networks. Apparently there is such a thing as JSON for VHDL library on Github, but this in turn brings in more dependencies - might as well just use Rust or Python. To manually write them down like you did may work for smaller networks, but for larger ones you need an automatism. Unless I am overlooking something, how would you create a network that sort 32 elements and has 14 stages and over a hundred comparisons?

[bpadalino]

The things I didn't like about your original approach:

• It's a new entity for every sorting network and type
• Every element is a new input/output pair

Understood it was an exercise in rust, but I think it was still a missed opportunity. The optimal networks have been identified and the JSON created. That JSON is never changing unless some new network is found. You'd be better off writing a translation from JSON -> VHDL function similar to what I have prototyped. You rely on the external program/JSON once instead of requiring it every time. If you want to make your own sorting network, make your own comparisons matrix and pass it into the sorting network all in VHDL - no need to get other tools involved. This is how I would have approached the problem for all the optimal input networks up to 64 elements that I saw on the linked pages. The package is then static and fixed, works for all data types, and uses the same entity for all sorting networks. This can even go into a single VHDL file so it's a super easy include for anyone.

Agreed about the pipelining, though I think an array of booleans that is the size that matches the number of stages is more clear than using an slv.

Agreed that VHDL-2019 is not very well supported, but if constructs like this are never written in it and not pushed to vendors they will never support it. Chicken and egg problems. On the other hand, generic types and generic subprograms were introduced in 2008 and are mostly supported by vendors.

I'm not sure I understand the comment about the VHDL code being as simple as possible.

[Chris44442]

I mean sure, we could only have one very generic VHDL file that reads the json files and then produce the entity we want. My main issue with this is that the resulting source file for the actual rtl would be this not-so-easy-to-read VHDL file (especially for others who might not be used to these language features). I chose to outsource the complexity and let the resulting .vhd file contain primitive elements only. Both are probably valid options.

Maybe you know these register map generator tools like Airhdl or Corsair. They also generate rather simple hdl code and let the generator contain the complexity. As a user I prefer that, because I don't want to deal with the details, how to get to the solution. I just want it to be as simple as possible and instantiate it, nothing more. If anyone has questions how the module works, they can easily inspect the generated code.

I'm not sure I understand the comment about the VHDL code being as simple as possible.

The sad reality is that many HDL coders, especially some of the older generations, don't trust the more fancy features of VHDL. And to a degree, I can't blame them. With all these compilers from different vendors and also FOSS, it is not always so easy to predict which language feature will lead to what outcome on hardware. There is also the question of simulators. I am not sure if every single one of those support these language features. Maybe they do. But I am sure that they support my version of it.

Also the reality is that other languages such as Python are vastly more popular than VHDL, which means that there is more support in terms of libraries, questions answered, advanced support in editors and so on. Meanwhile VHDL, let's face it, despite having been modernized in 2008 and 2019, let's just say, in order to write software modules I would probably choose 20 other languages over VHDL. Don't get me wrong, I generally like the language. But in the end, I choose it because I have to.