Array Sorter Solution

Problem Statement

Implement an integer sorter. Verify your design by sorting a list of N M-bit
vectors where N=10 and M=4.

Objective
To i) generate array structure and ii) mapping algorithm to signal flow graph
Deliverable
Ten Processing-Element (PE) Array Sorter

Specification
The array can be serially loaded with unsorted M-bit unsigned integers (e.g.,
M=4) from the switches and serially displays the sorted integers to SRAM.
The array comprises N processing elements and completes sorting N integers
in N clock cycles. The processing element consists of M-bit register and state
machine in coordinating a bubble sort algorithm.

Synopsis
entity array_sorter is
generic (N: natural);
port (x : in std_logic_vector(N-1 downto 0);
z: out std_logic_vector(N-1 downto 0);
type_sel, reset, scan_mode, ck: in std_logic);
end array_sorter;
The array_sorter requires the "for generate" construct to generate N Processing
Elements (PE) connected in an array. We first design the PE then generate an
array of N PEs (e.g., N=10). The PE has left and right input ports to be connected
to its adjacent neighbors. The M-bit vector input (e.g., M=4) from the left neighbor
of the left most PE can be multiplexed to the switches on the board during the
"scan" mode. The M-bit vector content of the right most PE is connected to the
LEDs. First user selects the scan mode. In this mode the PEs are connected in a
cascading fashion. User can serially scan (shift) in the vectors from the switches
into the array. A single-step mechanism is required for manually changing of the
switches. After N steps, the contents of the PEs are the vectors to be sorted.
User selects the computing mode. After N steps the LEDs show the maximum number. User selects the scan mode and verifies the outputs (LEDs) for descending order of vectors.
PE Description
entity PE is
generic (N: natural);
port (L_in, R_in : in std_logic_vector(N-1 downto 0);
L_out, R_out : out std_logic_vector(N-1 downto 0);
type_sel, reset, scan_mode, ck: in std_logic);
end PE;

The PE consists of a register initially storing a vectors in the list to be sorted. During the computing mode, the PE alternates between two states, S1 and S2. In S1 it compares its content to the left input, L_in. if it is less then the input it updates its content with the left input. Similarly, in S2 it compares its content to the right input, R_in. if it is greater than the input it updates its content with the right input. To get the greater numbers to "bubble" toward the left PEs, the PEs pair in an alternate configuration. Initially, the even number PEs compare themselves to their left neighbors and the odd number PEs compare themselves to their right neighbors. In the next step, the even number PEs compare themselves to their right neighbors and the odd number PEs compare themselves to their left neighbors. These configurations alternate as the array performs the bubble sort. In N steps the sorted list are the contents of the PEs. The even type PEs start in the state S1 and the odd type in S2. The PE is labeled as even or odd type by the type_sel input port. This can be done in the for generate loop e.g.,
G1: for i in 0 to N-1 loop
G2: if i mod 2 = 0 and i0 and i<N-1generate -- excluding the left and right most PE
U1: PE port map(..., type_sel='0', ...); -- type_sel = '0' for even number PE
end generate G2;
G3: if i mod 2 = 1 generate
U1: PE port map(..., type_sel='1', ...); -- type_sel = '1' for odd number PE
end generate G3;
...
end generate G1;

Future Work
We will generate a large array of PEs (e.g., N=100) when we use embedded system platform. The embedded processor runs a C code to generate random list of 32-bit integers. The array sorter will be the peripheral of the embedded processor. The processor verifies the sorted list from the sorted.