VHDL Implementation - Biological Sequence Alignment

This post describes the VHDL implementation details and abstractions. Kindly look at the post on parallel prefix methodology to understand the context under which these VHDL modules work

NODE
The basic functional unit of the parallel prefix method is a node. It has two modes of operation namely operation and duplication. The node performs the binary operation on the two inputs given to it when it operates in the operation mode. When in the duplication mode, the output is the first input to the node. It is a combinational circuit. Its VHDL representation is as follows.

 -------------------------------------------------------------------------------  
 -- Parallel Prefix : Node .vhd  
 -- Abishek Ramdas  
 -- NYU Poly  
 -- date - 11/26/10  
 -------------------------------------------------------------------------------  
 library ieee;  
 use ieee.numeric_std.all;  
 use ieee.std_logic_1164.all;  
 use ieee.std_logic_signed.all;  
 entity node is  
 port (  
 x_input: in std_logic_vector(7 downto 0); -- input to the node from the same line  
 y_input: in std_logic_vector(7 downto 0); -- input to the nodefrom the previous level  
 dup_en: in std_logic; -- dup_en=1 node in duplicate mode, dup_en=0 node in operation mode  
 x_output: out std_logic_vector(7 downto 0)); -- stores result of operation into x array in next clock cycle  
 end node;  
 architecture behav of node is  
 signal x_2s_comp : std_logic_vector(7 downto 0); -- 2's complement of x_input incase it is negative  
 signal y_2s_comp : std_logic_vector(7 downto 0); -- 2's complement of y_input incase it is negative  
 begin -- behav  
 calc_proc : process(y_input, x_input, dup_en)  
 begin  
 if(dup_en='0')then --operation mode  
 if(x_input(7)='0' and y_input(7)='0')then --both the inputs are positive  
 if(x_input<y_input)then  
 x_output<=y_input;  
 else  
 x_output<=x_input;  
 end if;  
 elsif(x_input(7)='0' and y_input(7)='1')then --x input +, y input -  
 x_output <= x_input;  
 elsif(x_input(7)='1' and y_input(7)='0')then -- x input -, y input +  
 x_output <= y_input;  
 elsif(x_input(7)='1' and y_input(7)='1')then -- x input -, y input -  
 11  
 x_2s_comp <= not(x_input)+"00000001"; -- take twos complimnet of both the numbers to find bigger number  
 y_2s_comp <= not(y_input)+"00000001";  
 if(x_2s_comp<y_2s_comp)then  
 x_output<=x_input;  
 else  
 x_output<=y_input;  
 end if;  
 else  
 if(x_input<y_input)then  
 x_output<=y_input;  
 else  
 x_output<=x_input;  
 end if;  
 end if;  
 else --dupicate mode  
 x_output<=x_input;  
 end if;  
 end process;  
 end behav;  

As mentioned earlier, to calculate the values of x[j] from z[j] (j=1 to 8), 8 nodes are used so as to optimize time. Each node gets a z input and input from its previous stage. The modes of the different nodes follow the pattern shown in the table.

(couldnt make it smaller and still legible :))

A control logic is implemented which generates the signal corresponding to the mode of operation. This is described in the next post