.ZIP

# Array Sorter

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.

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.

You'll get a 1.5KB .ZIP file.