Home / FPGA / Sorting – Pipelined Even-Odd

Sorting – Pipelined Even-Odd

One of my thoughts was to use an even-odd approach. This is typically done when using GPUs in a sequential fashion. I decided to do this pipelined. This approach turned out to be extremely inefficient in retrospect. In a future post, I’ll do a state machine based approach which will be good for area and power conscious designs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
module compare
  #
  (
   parameter                 DWIDTH = 32
   )                        
  (                          
   input                     clk,
                             
   input [DWIDTH-1:0]        a_in,
   input [DWIDTH-1:0]        b_in,
   input [DWIDTH-1:0]        c_in,
   input [DWIDTH-1:0]        d_in,

   output logic [DWIDTH-1:0] a_out,
   output logic [DWIDTH-1:0] b_out,
   output logic [DWIDTH-1:0] c_out,
   output logic [DWIDTH-1:0] d_out
   );

  logic [DWIDTH-1:0]      a_reg;
  logic [DWIDTH-1:0]      b_reg;
  logic [DWIDTH-1:0]      c_reg;
  logic [DWIDTH-1:0]      d_reg;
  logic [DWIDTH-1:0]    a_odd;
  logic [DWIDTH-1:0]    b_odd;
  logic [DWIDTH-1:0]    c_odd;
  logic [DWIDTH-1:0]    d_odd;
  logic [DWIDTH-1:0]    a_even;
  logic [DWIDTH-1:0]      b_even;
  logic [DWIDTH-1:0]      c_even;
  logic [DWIDTH-1:0]      d_even;
  logic [DWIDTH-1:0]    a_odd1;
  logic [DWIDTH-1:0]    b_odd1;
  logic [DWIDTH-1:0]    c_odd1;
  logic [DWIDTH-1:0]    d_odd1;
 
  always_ff @(posedge clk) begin
    a_reg <= a_in;
    b_reg <= b_in;
    c_reg <= c_in;
    d_reg <= d_in;
    // First stage, compare odds
    a_odd <= (a_reg < b_reg) ? a_reg : b_reg;
    b_odd <= (a_reg < b_reg) ? b_reg : a_reg;
    c_odd <= (c_reg < d_reg) ? c_reg : d_reg;
    d_odd <= (c_reg < d_reg) ? d_reg : c_reg;
    // Sort evens
    a_even <= a_odd;
    b_even <= (b_odd < c_odd) ? b_odd : c_odd;
    c_even <= (b_odd < c_odd) ? c_odd : b_odd;
    d_even <= d_odd;
    // Sort odds again - we are now guaranteed to be sorted
    a_odd1 <= (a_even < b_even) ? a_even : b_even;
    b_odd1 <= (a_even < b_even) ? b_even : a_even;
    c_odd1 <= (c_even < d_even) ? c_even : d_even;
    d_odd1 <= (c_even < d_even) ? d_even : c_even;

    a_out <= a_odd1;
    b_out <= (b_odd1 < c_odd1) ? b_odd1 : c_odd1;
    c_out <= (b_odd1 < c_odd1) ? c_odd1 : b_odd1;
    d_out <= d_odd1;
  end
 
endmodule

Fmax: > 800 Mhz
LUT: 410
FF: 640

About admin

Check Also

Sorting – Completely parallel approach

The first approach I attempted was a completely parallel approach as shown in the diagram …

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.