Sorting Numbers

Although the MIPS processor seems to be simple, we still can do really neat stuff with it!!
In the following few posts, I’ll show you how to sort 4 numbers!

What are we going to encounter?!

1) we’ll start by drawing a scheme of the sorting algorithim
2) write a code in MIPS assembly
3) simulate the assembly code with PCspim
4) writing a VHDL code for the whole problem!

sounds interesting huh?!

Sorting algorithim

given 2 numbers in binary, how we should compare them?!
well, we’ll look at each 2 bits from both numbers starting from the MSB bit in respect to both numbers. if they are equal(both = ‘0’ or both = ‘1’) then we’ll pass to the next pair, and so on, until one bit is ‘1’ and the other is ‘0’. The bit with the value ‘1’ points at the large number, while the zero bit represent the small number.
Automata(FSM)  for the algorithim:
control

Thus, our next objective is building a circuit that compares 2 bits, and decides which number is the Max and which is the Min:

The logic behind this circuit is simple and effective, a quick look reveals that when the bits are equal the decoder is disabled and when the bits differ from each other, the decoder puts them in the correct order.
The logic behind this circuit is simple and effective, a quick look reveals that when the bits are equal the decoder is disabled and when the bits differ from each other, the decoder puts them in the correct order.

However, we must also concider the case of A=B, therefore, it’s not important what is the Max or the Min(signals of the output), thus we add 2 multiplexers:

in a given time, either the decoder or the muxes operate, but not both!, therefore, the device that does'nt work, its output is zero, therfore, we used AND gates to preserve the output.
in a given time, either the decoder or the muxes operate, but not both!, therefore, the device that does’nt work, its output is zero, therfore, we used AND gates to preserve the output.

after we designed the circuit that compares 2 numbers, we;ll use  it in order to compare 4 numbers. In the following circuit we exactly that:

using the circuit of comparing 2 numbers 5 times to sort 4 numbers
using the circuit of comparing 2 numbers 5 times to sort 4 numbers

Before carrying ahead to the assembly code, let’s implement the scheme above in vhdl, shall we? of course! so scroll down this page will you?!

1- Compare2:

library ieee;
use ieee.std_logic_1164.all;

entity Compare2 is
 generic (N : integer := 4);
 port (
 A : in std_logic_vector (N-1 downto 0);-- first number
 B : in std_logic_vector (N-1 downto 0);-- Second number
 Max : out std_logic_vector (N-1 downto 0);-- Larger number
 Min : out std_logic_vector (N-1 downto 0)-- Smaller number
 );
end entity;

architecture behavior of Compare2 is
signal A_greater : std_logic;
begin

process(A,B)
variable count : integer range N-1 downto -1;
begin
 count := N-1;
 while (count >= 0)loop --start from MSB
 if(A(count)= '1')then
 if(B(count)='0') then
 Max <= A;
 Min <= B;
 count := 0; 
 end if; 
 elsif(A(count)= '0')then
 if(B(count)='1') then
 Max <= B;
 Min <= A;
 count := 0; 
 end if; 
 end if;
 count := count-1;--update counter
 end loop;
end process;--end proc
end architecture;

Wave form for Compare2:

Real simple and straightforward implementation always leads to the anticipated results!
Real simple and straightforward implementation always leads to the anticipated results!

 2- ContComp:

right now, well try something cute, cascading 2 units of the Compare2 from above to make it possible to code the desing of sorting the 4 numbers with 5 Compare2:

library ieee;
use IEEE.std_logic_1164.all;

entity ContComp is
generic (N: integer := 4);
port (CLK : in std_logic; --Clock, active high
 RSTn : in std_logic; --Async. Reset, active low
 --input numbers
 in_A : in std_logic_vector(N-1 downto 0);
 in_B : in std_logic_vector(N-1 downto 0);
 in_C : in std_logic_vector(N-1 downto 0);
 in_D : in std_logic_vector(N-1 downto 0);
 --output signals:
 Out_A : out std_logic_vector(N-1 downto 0);
 Out_B : out std_logic_vector(N-1 downto 0);
 Out_C : out std_logic_vector(N-1 downto 0);
 Out_D : out std_logic_vector(N-1 downto 0)
 );
end entity;

architecture behavior of ContComp is
--defining component Compare2:
component Compare2 is
 generic (N : integer := 4);
 port (
 A : in std_logic_vector (N-1 downto 0);-- first number
 B : in std_logic_vector (N-1 downto 0);-- Second number
 Max : out std_logic_vector (N-1 downto 0);-- Larger number
 Min : out std_logic_vector (N-1 downto 0)-- Smaller number
 );
end component;
--defining signals:
--signals for the input numbers:
signal tmp_inA, tmp_inB, tmp_inC, tmp_inD : std_logic_vector (N-1 downto 0);
--signals for the output first stage compare:
--signal max1, min1, max2, min2 : std_logic_vector (N-1 downto 0);
begin
-- in this section we'll implement the first stage of the sorting process:
--define components:
comp1 : Compare2 generic map (N=>N)
 port map (A=>tmp_inA,B=>tmp_inB,Max=>Out_A,Min=>Out_B);
 
comp2 : Compare2 generic map (N=>N)
 port map (A=>tmp_inC,B=>tmp_inD,Max=>Out_C,Min=>Out_D);

process(RSTn,CLK)
 begin
 if RSTn = '0' then --initialize singnals to 0's:
 tmp_inA <= (others =>'0');
 tmp_inB <= (others =>'0');
 tmp_inC <= (others =>'0');
 tmp_inD <= (others =>'0');

 elsif rising_edge(CLK) then
 tmp_inA <= in_A;
 tmp_inB <= in_B;
 tmp_inC <= in_C;
 tmp_inD <= in_D;
-- max1 <= Out_A;
-- min1 <= Out_B;
-- max2 <= Out_C;
-- min2 <= Out_D;
 end if;
end process;
end behavior;

there is no need for a wave form here, since this is a helping tool not more, therefore, let’s move ahead!

3-Top

here is the final stage of the sorting process, gathering what we already coded and designed into one mighty code!

library ieee;
use ieee.std_logic_1164.all;

entity Top is
 generic (N : integer := 4);
 port (CLK : in std_logic; --Clock, active high
 RSTn : in std_logic; --Async. Reset, active low
 A : in std_logic_vector (N-1 downto 0);-- first number
 B : in std_logic_vector (N-1 downto 0);-- Second number
 C : in std_logic_vector (N-1 downto 0);-- third number
 D : in std_logic_vector (N-1 downto 0);-- fourth number
 First : out std_logic_vector (N-1 downto 0);-- smallest number
 Second : out std_logic_vector (N-1 downto 0);-- mid1 number
 Third : out std_logic_vector (N-1 downto 0);-- mid2 number
 Fourth : out std_logic_vector (N-1 downto 0) -- largest number
 );
end entity;

architecture behavior of Top is
--defining components:
component Compare2 is
 generic (N : integer := 4);
 port (
 A : in std_logic_vector (N-1 downto 0);-- first number
 B : in std_logic_vector (N-1 downto 0);-- Second number
 Max : out std_logic_vector (N-1 downto 0);-- Larger number
 Min : out std_logic_vector (N-1 downto 0) -- Smaller number
 );
end component;
component ContComp is
 generic (N : integer := 4);
 port (CLK : in std_logic; --Clock, active high
 RSTn : in std_logic; --Async. Reset, active low
 --input numbers
 in_A : in std_logic_vector(N-1 downto 0);
 in_B : in std_logic_vector(N-1 downto 0);
 in_C : in std_logic_vector(N-1 downto 0);
 in_D : in std_logic_vector(N-1 downto 0);
 --output signals:
 Out_A : out std_logic_vector(N-1 downto 0);
 Out_B : out std_logic_vector(N-1 downto 0);
 Out_C : out std_logic_vector(N-1 downto 0);
 Out_D : out std_logic_vector(N-1 downto 0)
 );
end component;
----------------------------------------------------
signal Ato2,Bto2,MinFrom2,MaxFrom2 : std_logic_vector (N-1 downto 0);
signal Cto2,Dto2 : std_logic_vector (N-1 downto 0);

begin
--first level comparasion:
U1 : ContComp
 port map (CLK=>CLK,RSTn=>RSTn,
 in_A=> A, in_B=> B, in_C=>C, in_D=>D,
 Out_A=>Ato2 ,Out_B=>Bto2 ,Out_C=>Cto2 ,Out_D=>Dto2 );

--ContComp outputs:
--Out_A = max{A,B}
--Out_B = min{A,B}
--Out_C = max{C,D}
--Out_D = min{C,D}

U0 : Compare2 generic map (N=>N)
 port map (A=>Ato2,B=>Cto2,Max=>Fourth,Min=>MinFrom2);
U01 : Compare2 generic map (N=>N)
 port map (A=>Bto2,B=>Dto2,Max=>MaxFrom2,Min=>First);
U2 : Compare2 generic map (N=>N)
 port map (A=>MinFrom2,B=>MaxFrom2,Max=>Third,Min=>Second);
end architecture;

waveform:

as promised, the largest number is the Fourth signal line and the lowest number is the First signal line
as promised, the largest number is the Fourth signal line and the lowest number is the First signal line. notice that it takes 1 cycle of the clock to sort a set of 4 numbers

in the next post, I’ll will cover the assembly code and explain how to use PCspim and how to simulate the code of the assembly.
if you got questions, post a comment bellow!

~ to be continued!

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: