-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathUnionFind.vhd
184 lines (162 loc) · 6.37 KB
/
UnionFind.vhd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
------------------------------------------------------------
-- Title : Union find algorithm
------------------------------------------------------------
-- Description: ctrl: 000 - nothing
-- 001 - union
-- 010 - find
-- 011 - init (or reset)
-- 100 - are 2 nodes connected?
-- only the features stored in the root noded are important
-- we don't waste resources to keep the features of non-root
-- nodes up to date
------------------------------------------------------------
-- File : UnionFind
-- Author : Peter Samarin <peter.samarin@gmail.com>
------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.UFlib.all;
------------------------------------------------------------
entity UnionFind is
generic (
N : integer := 3);
port (
-- debug
all_nodes : out node_vector (0 to 2**N-1) := (others => (N-1, 1));
-- user interface
id1 : in std_logic_vector(N-1 downto 0) := (others => '0');
id2 : in std_logic_vector(N-1 downto 0) := (others => '0');
ctrl : in std_logic_vector(2 downto 0) := (others => '0');
ctrl_valid : in std_logic := '0';
-- outputs
root : out std_logic_vector(N-1 downto 0) := (others => '0');
is_connected : out std_logic := '0';
ready : out std_logic := '0';
-- other
clk : in std_logic := '0');
end UnionFind;
------------------------------------------------------------
architecture arch of UnionFind is
type state_type is (init, idle, find, union, connected);
-- signals
signal state : state_type := init;
signal nodes : node_vector (0 to 2**N-1) := (others => (N-1, 1));
signal id1_int, id2_int : integer range 0 to 2**N-1 := 0;
signal find_start_id1 : integer range 0 to 2**N-1 := 0;
signal find_start_id2 : integer range 0 to 2**N-1 := 0;
signal xRoot, yRoot : integer range 0 to 2**N-1 := 0;
signal xRoot_int : integer range 0 to 2**N-1 := 0;
signal yRoot_int : integer range 0 to 2**N-1 := 0;
signal counter : integer range 0 to 2**N-1 := 0;
-- output registers
signal ready_reg : std_logic := '0';
signal is_connected_reg : std_logic := '0';
begin
process (clk) is
begin
if rising_edge(clk) then
ready_reg <= '0';
is_connected_reg <= '0';
case state is
when init =>
if counter = 2**N-1 then
state <= idle;
ready_reg <= '1';
counter <= 0;
else
counter <= counter + 1;
end if;
nodes(counter).parent <= counter;
nodes(counter).weight <= 1;
when idle =>
if ctrl_valid = '1' then
case ctrl is
when "000" =>
state <= idle;
when "001" => -- union
state <= union;
xRoot <= nodes(id1_int).parent;
yRoot <= nodes(id2_int).parent;
-- path compression
find_start_id1 <= id1_int;
find_start_id2 <= id2_int;
when "010" => -- find
find_start_id1 <= id1_int;
state <= find;
xRoot <= nodes(id1_int).parent;
if id1_int = nodes(id1_int).parent then
state <= idle;
ready_reg <= '1';
end if;
-- save query node for later path compression
find_start_id1 <= id1_int;
when "011" => -- init
state <= init;
counter <= 0;
when "100" => -- connected
state <= connected;
xRoot <= nodes(id1_int).parent;
yRoot <= nodes(id2_int).parent;
-- save query node for later path compression
find_start_id1 <= id1_int;
find_start_id2 <= id2_int;
when others => null;
end case;
end if;
when union =>
if xRoot = nodes(xRoot).parent and yRoot = nodes(yRoot).parent then
state <= idle;
ready_reg <= '1';
-- path compression
nodes(find_start_id1).parent <= xRoot;
nodes(find_start_id2).parent <= yRoot;
-- union node, and update weight
if nodes(xRoot).parent /= yRoot then
if nodes(xRoot).weight < nodes(yRoot).weight then
nodes(xRoot).parent <= yRoot;
nodes(yRoot).weight <= nodes(yRoot).weight + nodes(xRoot).weight;
else
nodes(yRoot).parent <= xRoot;
nodes(xRoot).weight <= nodes(xRoot).weight + nodes(yRoot).weight;
end if;
end if;
end if;
xRoot <= nodes(xRoot).parent;
yRoot <= nodes(yRoot).parent;
when connected =>
if xRoot = nodes(xRoot).parent and yRoot = nodes(yRoot).parent then
state <= idle;
ready_reg <= '1';
if xRoot = yRoot then
is_connected_reg <= '1';
end if;
-- path compression
nodes(find_start_id1).parent <= xRoot;
nodes(find_start_id2).parent <= yRoot;
end if;
xRoot <= nodes(xRoot).parent;
yRoot <= nodes(yRoot).parent;
when find =>
xRoot <= nodes(xRoot).parent;
if xRoot = nodes(xRoot).parent then
state <= idle;
ready_reg <= '1';
nodes(find_start_id1).parent <= xRoot;
end if;
when others => null;
end case;
end if;
end process;
-- convenience signals
id1_int <= to_integer(unsigned(id1));
id2_int <= to_integer(unsigned(id2));
root <= std_logic_vector(to_unsigned(xRoot, N));
----------------------------------------------------------
-- Outputs
----------------------------------------------------------
ready <= ready_reg;
is_connected <= is_connected_reg;
-- debug
all_nodes <= nodes;
end arch;