在std_logic_vector [vhdl]上实现VHDL二进制搜索 [英] Implementing a VHDL binary search on a std_logic_vector [vhdl]
问题描述
我正在尝试为ASIC(它必须是ASIC的一部分)创建可综合的VHDL(函数或过程)，它将在standard_logic_vector中查找第一个"1"并输出"1"所在的向量位置例如，我有一个8位slv，为"10001000"(位置3和7中为"1").如果使用此slv，则输出应为4(基于1的输出).
I'm attempting to create synthesizable VHDL (function or procedure) for an ASIC (it must be part of the ASIC) that will look for the first '1' in a standard_logic_vector and output which vector position that '1' was in. For example, I have an 8-bit slv of "10001000" (a '1' in position 3 and 7). If I use this slv, the output should be 4 (the output is 1 based).
实际的VHDL将搜索一个最大长度为512位的slv.我尝试实现二进制搜索功能，但是出现综合错误，指出无法合成非恒定范围值.[CDFG-231] [详细说明] 非恒定范围值在第61行的文件"..."中，我在下面的代码中指出了该问题.我不确定如何在不具有非恒定范围的情况下实现二进制搜索算法值.我将如何修改此代码以使其可综合?
The actual VHDL will be searching a large slv, up to 512 bits in length. I tried implementing a binary search function but I get synthesis errors that states "Could not synthesize non-constant range values. [CDFG-231] [elaborate] The non-constant range values are in file '...' on line 61" I indicated in the code below where it complains. I'm not sure how to implement a binary search algorithm without having non-constant range values. How would I modify this code so it's synthesizable?
我尝试搜索HDL的二进制搜索算法，以查找潜在的代码并查找错误，但是我什么都没找到.
I have attempted to search for binary search algorithms for HDL for potential code to look at and for my error, but I didn't find anything.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_misc.all;
entity bin_search is
generic (
constant NREGS : positive := 16 -- number of registers
);
port (
clk_i : in std_logic; -- clock
bin_i : in unsigned( NREGS-1 downto 0 ); -- input
en_i : in std_logic; -- input enable
addr_o : out natural range 0 to NREGS -- first binary location
);
end bin_search;
architecture rtl of bin_search is
function f_bin_search( input: unsigned; nob: positive ) return natural is
constant nbits : positive := 2**nob;
variable lower : natural range 0 to 1 := 0;
variable upper : natural range 0 to 1 := 0;
variable idx : natural range 0 to nob := 4;
variable cnt : natural range 0 to nbits := 0;
variable mid : positive range 1 to nbits := nbits/2; --
variable ll : natural range 0 to nbits := 0;
variable ul : positive range 1 to nbits := nbits; --
begin
if input = 0 then
cnt := 0;
return cnt;
else
loop1: while ( idx > 0 ) loop
if ( input( mid-1 downto ll ) > 0 ) then -- <===WHERE SYNTH COMPLAINS
lower := 1;
else
lower := 0;
end if;
if ( input( ul-1 downto mid ) > 0 ) then
upper := 1;
else
upper := 0;
end if;
if ( idx = 1 ) then
if ( lower = 1 ) then
cnt := mid;
else
cnt := ul;
end if;
elsif ( lower = 1 ) then
ul := mid;
mid := ( ( ll+ul )/2 );
elsif ( upper = 1 ) then
ll := mid;
mid := ( ll+ul )/2;
else
cnt := 0;
exit loop1;
end if;
idx := idx-1;
end loop loop1;
return cnt;
end if;
end f_bin_search;
begin
test_proc: process ( clk_i )
begin
if rising_edge( clk_i ) then
if en_i = '1' then
addr_o <= f_bin_search( bin_i, 4 );
end if;
end if;
end process test_proc;
end rtl;
这是一个简单的测试台，其中输入以'1'递增. addr_o应该是输入lsb的位置(从1开始).
Here's a simple test bench where the input is inc'd by '1'. The addr_o should be the location (1 based) of the input lsb with a '1'.
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_misc.all;
use ieee.numeric_std.all;
entity bin_search_tb is
end bin_search_tb;
architecture behavior of bin_search_tb is
constant NREGS : positive := 16;
signal clk : std_logic;
signal input : unsigned( NREGS-1 downto 0 );
signal start : std_logic;
signal addr : natural range 0 to NREGS;
constant clk_per : time := 1 ns;
signal row : natural range 0 to 2**NREGS-1;
begin
bin_search_inst: entity work.bin_search( rtl )
generic map (
NREGS => NREGS
)
port map (
clk_i => clk, -- master clock
bin_i => input, -- captured events
en_i => start, -- start binary search
addr_o => addr -- addr where the first '1' appears
);
-- master clock process
clk_proc: process
begin
clk <= '0';
wait for clk_per / 2;
clk <= '1';
wait for clk_per / 2;
end process clk_proc;
--
stim1_proc: process
begin
input <= ( others => '0' );
start <= '0';
row <= 1;
wait until clk'event and clk = '1';
loop
wait until clk'event and clk = '1';
input <= to_unsigned( row, input'length );
start <= '1';
wait until clk'event and clk = '1';
start <= '0';
wait for 4*clk_per;
row <= row+1;
end loop;
end process stim1_proc;
end architecture behavior;
感谢您的协助！ -杰森
Thanks for your assistance! -Jason
编辑代码并添加测试台
推荐答案
您的设计无疑将取决于延迟和其他性能要求，但是，您可以使用or-reduction排序器的某种组合(用于切片矢量的多路复用选择) )，移位寄存器和计数器.我绘制了一个简单的电路，应该在大约30个时钟周期内找到您的lsb实例"1"
Your design will most certainly depend on latency and other performance requirements, but, you could use some combination of or-reduction, sequencers (for mux selection of sliced vectors), shift register, and counters. I drew up a simple circuit that should find your lsb instance of "1" in ~30 clock cycles
实现此设计的RTL转换应该简单明了.
The RTL translation that implements this design should be straight forward.
这篇关于在std_logic_vector [vhdl]上实现VHDL二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
