[Solved] Array Sorter Solution

5/5 – (1 vote)

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

ObjectiveTo i) generate array structure and ii) mapping algorithm to signal flow graph

DeliverableTen Processing-Element (PE) Array Sorter

SpecificationThe 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.

Synopsisentity array_sorter isgeneric (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 acascading 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 Descriptionentity PE isgeneric (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 loopG2: if i mod 2 = 0 and i0 and i<N-1generate excluding the left and right most PEU1: PE port map(, type_sel=0, ); type_sel = 0 for even number PEend generate G2;G3: if i mod 2 = 1 generateU1: PE port map(, type_sel=1, ); type_sel = 1 for odd number PEend generate G3;end generate G1;