What the best way to store data of size ( 90,000 * 32) bit (taken from a text file) using VHDL?

Status
Not open for further replies.
A RAM based search can only read and compare one RAM location per clock cycle. Respectively the search process can't be implemented in a function.
 
MSAKARIM said:
I tried to describe the Binary Search algorithm as follows, and it also takes a very long time while the synthesis. Is there any advice in the way of describing the code?
Click to expand...
Hello,

try Vivado HLS (Hihg Level Syntthessis) and let the tool to convert this algorithm (C sources) into HDL version. The tool should make it parallel (as much as it is posssible).

Best Regards
 
TrickyDicky said:
The problem is yyou are trying to search the entire "ram" (this cannot now actually be a ram) in a single clock cycle. I suggest you draw out your intended circuit before you write any code for this. VHDL is not like writing software.
Click to expand...

Thanks for all suggestions, I think that it is solved.

Code: 
process (clk,rst)

Variable L,R,M :  integer;
begin
if (rst ='1') then
L:= 0;
R:=3871;
    
elsif (clk'event and clk = '1') then

 if (L <= R) then
 M:= integer((L+R)/2);
 
 if(ram(M) < din) then
 L:= M+1;
 elsif ( ram(M) > din) then
  R:= M-1;
 else
  Location <= M;
 end if;
 
 else
  Location <= -1;
end if;

end if;
end process;

end Behavioral;
 

This will still have problems on the read side. You are doing asynchronous ram reads with no registered read address. It also does match the template provided. I suggest the ram read is done in another process and the ram read data is a separate register
 
Also don't use variables. Those variables will end up as combinational logic not registered logic as they are assigned immediately when reached.

Using variables usually makes for poorly performing pipelined designs.
 

I tried but it failed

Code: 
process (clk,M)

begin

if (clk'event and clk = '1') then

Read_M <= M;

end if;

d_ram <= RAM(Read_M);

end process;



process (clk,rst)

begin

if (rst ='1') then

L<= 0;

R<=3871;

    

elsif (clk'event and clk = '1') then



 if (L <= R) then

 M<= integer((L+R)/2);

 

 if(d_ram < din) then

 

 L<= M+1;

 

 elsif ( d_ram > din) then

  R<= M-1;

 else

  Location <= Read_M;

 end if;

 

 else

  Location <= -1;

end if;



end if;

end process;

end Behavioral;
 

Did you read the synthesis guidelines yet? did you read how to write code to infer ram? have you also separately created a diagram showing the ram in your circuit with the appropraite address and control signals connected? It still feels like you are trying to write VHDL like software and just wrapped "if rising_edge(clk) then" around it. You need to think in terms of circuit elements and have a circuit diaram using known components in mind before you write any VHDL.
 
did you read how to write code to infer ram?
Click to expand...
Yes, I read this tutorial: **broken link removed**

Okay, I will try to study my problem again, thanks for the advice.
 

IMO, it is best practice to put inferred RAM in it's own hierarchical block instead of in the middle of your code. This allows for inserting synthesis directives and attributes on the block to force synthesis to implement the type of RAM block you want. It also allows you to change the underlying code to match another vendors template if different. You can also just instantiate a vendor's IP block instead of inferring the RAM.

I think you should go back and look at the link in post #13 and find a inferred RAM that matches the behavior you want and place that code in a separate module, which you then instantiate in your code.
 

    M

    MSAKARIM

    Points: 2
    Helpful Answer Positive Rating

I read the tutorial and do a try:
Code: 
entity BS is
Port ( clk,we,rst: in STD_LOGIC;

Target : in STD_LOGIC_VECTOR (31 downto 0);


Location : out integer range -1 to 3871);

end BS;

architecture Behavioral of BS is

component BRAM_1 is
Port ( clk,we: in STD_LOGIC;
addr : in STD_LOGIC_VECTOR (11 downto 0);
din : in STD_LOGIC_VECTOR (31 downto 0);
dout : out STD_LOGIC_VECTOR (31 downto 0));
end component;
signal Ram_Out :STD_LOGIC_VECTOR (31 downto 0);
signal L,R,M: INTEGER RANGE 0 TO 3871;
signal M_addr:STD_LOGIC_VECTOR (11 downto 0);
begin

M_addr <=std_logic_vector(to_unsigned(M,12));

BRAM: BRAM_1 port map (clk,we,M_addr,Target,Ram_out);

process (clk,rst,L,R,M)
begin
if (rst ='1') then
L<= 0;
R<=3871;
    
elsif (clk'event and clk = '1') then

 if (L <= R) then
 M<= integer((L+R)/2);
 
 if(Ram_out< Target) then
 
 L<= M+1;
 
 elsif ( Ram_out > Target) then
  R<= M-1;
 else
  Location <= M;
 end if;
 
 else
  Location <= -1;
end if;

end if;
end process;


end Behavioral;

I tried to describe what I want in the attached image


 

You have translated a sequential binary search example like below
Code: 
...
       m := floor((L + R) / 2)
        if A[m] < T then
...
to VHDL without considering that Ram_out is delayed by one or more clock cycles. This can't work.
 

Yes, this is right, it doesn't work properly.
should I add a delay element (F.F) after RAM out?
 

You surely don't want more delay for Ram_out. The evalution of Ram_out must be delayed against setting RAM address (new M value). For the intended simple binary search this ends up in a state machine that sets M, waits some clock cycles, evaluates Ram_out and repeats.
--- Updated ---

For a more performant solution, google "pipelined binary search".
 
I try this, but also it doesnt work properly.
It remains at the first M_Calc

Code: 
architecture Behavioral of BS_SM is
-------BRAM-------
component BRAM_1 is
Port ( clk,we: in STD_LOGIC;
addr : in STD_LOGIC_VECTOR (11 downto 0);
din : in STD_LOGIC_VECTOR (31 downto 0);
dout : out STD_LOGIC_VECTOR (31 downto 0));
end component;
signal we : std_logic;
signal Ram_Out,data_comp :STD_LOGIC_VECTOR (31 downto 0);
signal M_addr:STD_LOGIC_VECTOR (11 downto 0);
------------------
------States------------
TYPE State_type IS (Start,Not_Found,Wait_memory,Read_Memory,M_calc,Compare);
SIGNAL State : State_Type;
signal L,R,M: INTEGER RANGE 0 TO 3871;
            
begin

BRAM: BRAM_1 port map (clk,we,M_addr,Target,Ram_out);

process (clk,rst,State)

begin
if (rst='1') then
L<=0;
R<= 3871;
State <= Start;

elsif (clk'event and clk ='1') then

case State is

when Start =>
if (L<= R) then
State <= M_calc;
else
State <= Not_Found;
end If;

When Not_Found =>   
Location <=-1;

When M_calc =>
M<= integer (L + R)/2;
State <= Read_memory;

when Read_Memory =>
   M_addr <=std_logic_vector(to_unsigned(M,12));
   we <= '0';
   state <= Wait_Memory;
    
when Wait_memory =>
   data_comp <= Ram_out;
   State <= Compare;

When Compare =>
if(data_comp < Target) then
 R<=R;
 L<= M+1;
 State <= M_calc;
 
 elsif (data_comp > Target) then
 L<=L;
 R<= M-1;
 State <= M_calc;
 else
 Location <=M;

 State <= Start;
 end if;
 
end case;
end if;
end process;

end Behavioral;
 

FvM said:
Setup a testbench, watch the timing of state machine and RAM signals.
Click to expand...

Code: 
architecture Behavioral of BS_SM is
-------BRAM-------
component BRAM_1 is
Port ( clk,we: in STD_LOGIC;
addr : in STD_LOGIC_VECTOR (11 downto 0);
din : in STD_LOGIC_VECTOR (31 downto 0);
dout : out STD_LOGIC_VECTOR (31 downto 0));
end component;
signal we : std_logic;
signal Ram_Out,data_comp :STD_LOGIC_VECTOR (31 downto 0);
signal M_addr:STD_LOGIC_VECTOR (11 downto 0);
------------------
------States------------
TYPE State_type IS (Start,Not_Found,Wait_memory,Read_Memory,M_calc,Compare);
SIGNAL State : State_Type;
signal M: INTEGER RANGE 0 TO 3871;
signal L: INTEGER RANGE 0 TO 3871 :=0;
signal R: INTEGER RANGE 0 TO 3871 :=3871;
            
begin

BRAM: BRAM_1 port map (clk,we,M_addr,Target,Ram_out);

process (clk,rst,State)

begin
if (rst='1') then
L<=0;
R<= 3871;
--State <= Start;

elsif (clk'event and clk ='1') then

case State is

when Start =>
if (L<= R) then
State <= M_calc;
else
State <= Not_Found;
end If;

When Not_Found =>   
Location <=-1;

When M_calc =>
M<= integer (L + R)/2;
State <= Read_memory;

when Read_Memory =>
   M_addr <=std_logic_vector(to_unsigned(M,12));
   we <= '0';
   state <= Wait_Memory;
    
when Wait_memory =>
   data_comp <= Ram_out;
   State <= Compare;

When Compare =>
if(data_comp < Target) then
 R<=R;
 L<= M+1;
 State <= Start;
 
 elsif (data_comp > Target) then
 L<=L;
 R<= M-1;
 State <= Start;
 else
 Location <=M;
 end if;
 
end case;
end if;
end process;

end Behavioral;

it stops at State "Not_found" although L <R and it should go to state "Calc_M"

 

Too coarse time scale. I guess there are multiple state transitions not visible in the wave. Zoom in to the first clocks after reset deassertion.
 

    M

    MSAKARIM

    Points: 2
    Helpful Answer Positive Rating
Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…