entity buf is generic ( Tpd : time := 1 ns ); port ( a : in bit; y : out bit ); end buf; ---------------------------------------------------------------- architecture behaviour of buf is begin y <= a after Tpd; end behaviour; ---------------------------------------------------------------- entity fanout_tree is generic ( h : natural; d : positive ); port ( input : in bit; output : out bit_vector (0 to d**h - 1) ); end fanout_tree; ---------------------------------------------------------------- architecture recursive of fanout_tree is component buf port ( a : in bit; y : out bit ); end component; component fanout_tree generic ( h : natural; d : positive ); port ( input : in bit; output : out bit_vector(0 to d**h - 1) ); end component; signal buffered_input : bit_vector(0 to d - 1); begin degenerate_tree : if h = 0 generate output(0) <= input; end generate degenerate_tree; compound_tree : if h > 0 generate subtree_array : for i in 0 to d - 1 generate the_buffer : buf port map ( a => input, y => buffered_input(i) ); the_subtree : fanout_tree generic map ( h => h - 1, d => d ) port map ( input => buffered_input(i), output => output(i * d**(h-1) to (i+1) * d**(h-1) -1) ); end generate subtree_array; end generate compound_tree; end recursive; ---------------------------------------------------------------- configuration recursive_fanout_tree of fanout_tree is for recursive for compound_tree for subtree_array for the_buffer : buf use entity work.buf(behaviour); end for; for the_subtree : fanout_tree use configuration recursive_fanout_tree; end for; end for; end for; end for; end recursive_fanout_tree; ---------------------------------------------------------------- architecture repetitive of fanout_tree is component buf port ( a : in bit; y : out bit ); end component; signal buffered_input : bit_vector(0 to (d**(h + 1) - 1) / (d - 1) - 1 ); begin buffered_input(0) <= input; levels : for k in 1 to h generate buf_array_array : for i in 0 to d**(k - 1) - 1 generate buf_array : for j in 0 to d - 1 generate the_buf : buf port map ( a => buffered_input( (d**(k - 1) - 1) / (d - 1) + i ), y => buffered_input( (d**k - 1) / (d - 1) + d * i + j ) ); end generate buf_array; end generate buf_array_array; end generate levels; output <= buffered_input( (d**h - 1) / (d - 1) to (d**(h + 1) - 1) / (d - 1) - 1 ); end repetitive; ---------------------------------------------------------------- configuration repetitive_fanout_tree of fanout_tree is for repetitive for levels for buf_array_array for buf_array for the_buf : buf use entity work.buf(behaviour); end for; end for; end for; end for; end for; end repetitive_fanout_tree; ---------------------------------------------------------------- entity tree_test is end tree_test; ---------------------------------------------------------------- architecture bench of tree_test is constant test_height : positive := 3; constant test_degree : positive := 2; signal clock : bit; signal recursive_result, repetitive_result : bit_vector(0 to test_degree**test_height - 1); component fanout_tree generic ( h : natural; d : positive ); port ( input : in bit; output : out bit_vector(0 to d**h - 1) ); end component; for recursive_dut : fanout_tree use configuration work.recursive_fanout_tree; for repetitive_dut : fanout_tree use configuration work.repetitive_fanout_tree; begin recursive_dut : fanout_tree generic map ( h => test_height, d => test_degree ) port map ( input => clock, output => recursive_result ); repetitive_dut : fanout_tree generic map ( h => test_height, d => test_degree ) port map ( input => clock, output => repetitive_result ); clock_gen : process begin clock <= '1' after 10 ns, '0' after 20 ns; wait for 20 ns; end process clock_gen; compare_results : assert recursive_result = repetitive_result report "Results differ"; end bench; ---------------------------------------------------------------- ---------------------------------------------------------------- use std.textio.line; package fat_tree_types is type coordinate is record k : positive; i, j : natural; end record; constant max_path_levels : positive := 5; constant max_path_hops : positive := 2 * max_path_levels - 1; type path_vector is array (1 to max_path_hops) of coordinate; type message_record is record source, destination : natural; id : natural; hops : natural; path : path_vector; end record; type connection_record is record message_waiting : boolean; message : message_record; end record; subtype acknowledge is boolean; constant default_connection : connection_record := ( message_waiting => false, message => ( source => 0, destination => 0, id => 0, hops => 0, path => (others => (1,0,0)) ) ); type connection_vector is array (natural range <>) of connection_record; type acknowledge_vector is array (natural range <>) of acknowledge; procedure write_message ( L : inout line; msg : message_record ); end fat_tree_types; ---------------------------------------------------------------- package body fat_tree_types is use std.textio.all; procedure write_message ( L : inout line; msg : message_record ) is begin write(L, string'("message ")); write(L, msg.id); write(L, string'(" from ")); write(L, msg.source); write(L, string'(" to ")); write(L, msg.destination); write(L, string'(" via ")); write(L, msg.hops); write(L, string'(" hop")); if msg.hops /= 1 then write(L, 's'); end if; write(L, string'(": ")); for index in 1 to msg.hops loop write(L, '('); write(L, msg.path(index).k); write(L, ','); write(L, msg.path(index).i); write(L, ','); write(L, msg.path(index).j); write(L, string'(") ")); end loop; end write_message; end fat_tree_types; ---------------------------------------------------------------- use work.fat_tree_types.all; entity switch is generic ( c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c - 1); send_ack_to_child : out acknowledge_vector(0 to c - 1); send_msg_to_child : out connection_vector(0 to c - 1); receive_ack_from_child : in acknowledge_vector(0 to c - 1); send_msg_to_parent : out connection_vector(0 to p - 1); receive_ack_from_parent : in acknowledge_vector(0 to p - 1); receive_msg_from_parent : in connection_vector(0 to p - 1); send_ack_to_parent : out acknowledge_vector(0 to p - 1) ); end switch; ---------------------------------------------------------------- architecture behavioural of switch is begin router : process variable msg : message_record; alias d : natural is msg.destination; variable child_msg_received, parent_msg_received : boolean; variable msg_received_from : natural; variable next_parent : natural := 0; begin child_msg_received := false; parent_msg_received := false; loop wait on receive_msg_from_child, receive_msg_from_parent; for index in 0 to c - 1 loop if receive_msg_from_child(index).message_waiting then msg := receive_msg_from_child(index).message; child_msg_received := true; msg_received_from := index; exit; end if; end loop; for index in 0 to p - 1 loop if receive_msg_from_parent(index).message_waiting then msg := receive_msg_from_parent(index).message; parent_msg_received := true; msg_received_from := index; exit; end if; end loop; exit when child_msg_received or parent_msg_received; end loop; msg.hops := msg.hops + 1; if msg.hops <= max_path_hops then msg.path(msg.hops) := coordinate'(k, i, j); end if; if d / c**k = j then send_msg_to_child( (d mod c**k) / c**(k - 1) ).message <= msg; send_msg_to_child( (d mod c**k) / c**(k - 1) ).message_waiting <= true; wait until receive_ack_from_child( (d mod c**k) / c**(k - 1) ); send_msg_to_child( (d mod c**k) / c**(k - 1) ).message_waiting <= false; wait until not receive_ack_from_child( (d mod c**k) / c**(k - 1) ); else send_msg_to_parent(next_parent).message <= msg; send_msg_to_parent(next_parent).message_waiting <= true; wait until receive_ack_from_parent(next_parent); send_msg_to_parent(next_parent).message_waiting <= false; wait until not receive_ack_from_parent(next_parent); next_parent := (next_parent + 1) mod p; end if; if child_msg_received then send_ack_to_child(msg_received_from) <= true; wait until not receive_msg_from_child(msg_received_from).message_waiting; send_ack_to_child(msg_received_from) <= false; end if; if parent_msg_received then send_ack_to_parent(msg_received_from) <= true; wait until not receive_msg_from_parent(msg_received_from).message_waiting; send_ack_to_parent(msg_received_from) <= false; end if; end process router; end behavioural; ---------------------------------------------------------------- use work.fat_tree_types.all; entity fat_tree is generic ( h : natural; c, p : positive ); port ( receive_msg_from_child : in connection_vector(0 to c**h - 1); send_ack_to_child : out acknowledge_vector(0 to c**h - 1); send_msg_to_child : out connection_vector(0 to c**h - 1); receive_ack_from_child : in acknowledge_vector(0 to c**h - 1); send_msg_to_parent : out connection_vector(0 to p**h - 1); receive_ack_from_parent : in acknowledge_vector(0 to p**h - 1) := (others => false); receive_msg_from_parent : in connection_vector(0 to p**h - 1) := (others => default_connection); send_ack_to_parent : out acknowledge_vector(0 to p**h - 1) ); end fat_tree; ---------------------------------------------------------------- use work.fat_tree_types.all; entity aux_fat_tree is generic ( h : natural; c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c**h - 1); send_ack_to_child : out acknowledge_vector(0 to c**h - 1); send_msg_to_child : out connection_vector(0 to c**h - 1); receive_ack_from_child : in acknowledge_vector(0 to c**h - 1); send_msg_to_parent : out connection_vector(0 to p**h - 1); receive_ack_from_parent : in acknowledge_vector(0 to p**h - 1); receive_msg_from_parent : in connection_vector(0 to p**h - 1); send_ack_to_parent : out acknowledge_vector(0 to p**h - 1) ); end aux_fat_tree; ---------------------------------------------------------------- architecture aux of fat_tree is component aux_fat_tree generic ( h : natural; c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c**h - 1); send_ack_to_child : out acknowledge_vector(0 to c**h - 1); send_msg_to_child : out connection_vector(0 to c**h - 1); receive_ack_from_child : in acknowledge_vector(0 to c**h - 1); send_msg_to_parent : out connection_vector(0 to p**h - 1); receive_ack_from_parent : in acknowledge_vector(0 to p**h - 1); receive_msg_from_parent : in connection_vector(0 to p**h - 1); send_ack_to_parent : out acknowledge_vector(0 to p**h - 1) ); end component; begin the_tree : aux_fat_tree generic map ( h, c, p, k => 1, i => 0, j => 0 ) port map ( receive_msg_from_child, send_ack_to_child, send_msg_to_child, receive_ack_from_child, send_msg_to_parent, receive_ack_from_parent, receive_msg_from_parent, send_ack_to_parent ); end aux; ---------------------------------------------------------------- architecture bottom_up_recursive of aux_fat_tree is subtype subtree_range is natural range 0 to p - 1; subtype switch_range is natural range 0 to c**(h - 1) - 1; subtype subtree_connection_vector is connection_vector(switch_range); subtype subtree_acknowledge_vector is acknowledge_vector(switch_range); type subtree_connection_vector_array is array (subtree_range) of subtree_connection_vector; type subtree_acknowledge_vector_array is array (subtree_range) of subtree_acknowledge_vector; signal subtree_receive_msg_from_switch, subtree_send_msg_to_switch : subtree_connection_vector_array; signal subtree_receive_ack_from_switch, subtree_send_ack_to_switch : subtree_acknowledge_vector_array; subtype switch_connection_vector is connection_vector(subtree_range); subtype switch_acknowledge_vector is acknowledge_vector(subtree_range); type switch_connection_vector_array is array (switch_range) of switch_connection_vector; type switch_acknowledge_vector_array is array (switch_range) of switch_acknowledge_vector; signal switch_receive_msg_from_subtree, switch_send_msg_to_subtree : switch_connection_vector_array; signal switch_receive_ack_from_subtree, switch_send_ack_to_subtree : switch_acknowledge_vector_array; component switch generic ( c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c - 1); send_ack_to_child : out acknowledge_vector(0 to c - 1); send_msg_to_child : out connection_vector(0 to c - 1); receive_ack_from_child : in acknowledge_vector(0 to c - 1); send_msg_to_parent : out connection_vector(0 to p - 1); receive_ack_from_parent : in acknowledge_vector(0 to p - 1); receive_msg_from_parent : in connection_vector(0 to p - 1); send_ack_to_parent : out acknowledge_vector(0 to p - 1) ); end component; component aux_fat_tree generic ( h : natural; c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c**h - 1); send_ack_to_child : out acknowledge_vector(0 to c**h - 1); send_msg_to_child : out connection_vector(0 to c**h - 1); receive_ack_from_child : in acknowledge_vector(0 to c**h - 1); send_msg_to_parent : out connection_vector(0 to p**h - 1); receive_ack_from_parent : in acknowledge_vector(0 to p**h - 1); receive_msg_from_parent : in connection_vector(0 to p**h - 1); send_ack_to_parent : out acknowledge_vector(0 to p**h - 1) ); end component; constant outer_i : natural := i; begin simple_tree : if h = 1 generate the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => receive_msg_from_child, send_ack_to_child => send_ack_to_child, send_msg_to_child => send_msg_to_child, receive_ack_from_child => receive_ack_from_child, send_msg_to_parent => send_msg_to_parent, receive_ack_from_parent => receive_ack_from_parent, receive_msg_from_parent => receive_msg_from_parent, send_ack_to_parent => send_ack_to_parent ); end generate simple_tree; compound_tree : if h > 1 generate switch_array : for j in switch_range generate the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => receive_msg_from_child( j * c to (j + 1) * c - 1 ), send_ack_to_child => send_ack_to_child( j * c to (j + 1) * c - 1 ), send_msg_to_child => send_msg_to_child( j * c to (j + 1) * c - 1 ), receive_ack_from_child => receive_ack_from_child( j * c to (j + 1) * c - 1 ), send_msg_to_parent => switch_send_msg_to_subtree(j), receive_ack_from_parent => switch_receive_ack_from_subtree(j), receive_msg_from_parent => switch_receive_msg_from_subtree(j), send_ack_to_parent => switch_send_ack_to_subtree(j) ); end generate switch_array; subtree_array : for i in subtree_range generate the_subtree : aux_fat_tree generic map ( h - 1, c, p, k + 1, outer_i * p + i, j ) port map ( receive_msg_from_child => subtree_receive_msg_from_switch(i), send_ack_to_child => subtree_send_ack_to_switch(i), send_msg_to_child => subtree_send_msg_to_switch(i), receive_ack_from_child => subtree_receive_ack_from_switch(i), send_msg_to_parent => send_msg_to_parent( i * p**(h - 1) to (i + 1) * p**(h - 1) - 1 ), receive_ack_from_parent => receive_ack_from_parent( i * p**(h - 1) to (i + 1) * p**(h - 1) - 1 ), receive_msg_from_parent => receive_msg_from_parent( i * p**(h - 1) to (i + 1) * p**(h - 1) - 1 ), send_ack_to_parent => send_ack_to_parent( i * p**(h - 1) to (i + 1) * p**(h - 1) - 1 ) ); end generate subtree_array; connect_subtree : for i in subtree_range generate connect_switch : for j in switch_range generate switch_receive_msg_from_subtree(j)(i) <= subtree_send_msg_to_switch(i)(j); subtree_receive_ack_from_switch(i)(j) <= switch_send_ack_to_subtree(j)(i); subtree_receive_msg_from_switch(i)(j) <= switch_send_msg_to_subtree(j)(i); switch_receive_ack_from_subtree(j)(i) <= subtree_send_ack_to_switch(i)(j); end generate connect_switch; end generate connect_subtree; end generate compound_tree; end bottom_up_recursive; ---------------------------------------------------------------- configuration bottom_up_recursive_aux_fat_tree of aux_fat_tree is for bottom_up_recursive for simple_tree for the_switch : switch use entity work.switch(behavioural); end for; end for; for compound_tree for switch_array for the_switch : switch use entity work.switch(behavioural); end for; end for; for subtree_array for the_subtree : aux_fat_tree use configuration bottom_up_recursive_aux_fat_tree; end for; end for; end for; end for; end bottom_up_recursive_aux_fat_tree; ---------------------------------------------------------------- configuration bottom_up_recursive_fat_tree of fat_tree is for aux for the_tree : aux_fat_tree use configuration work.bottom_up_recursive_aux_fat_tree; end for; end for; end bottom_up_recursive_fat_tree; ---------------------------------------------------------------- architecture top_down_recursive of aux_fat_tree is subtype subtree_range is natural range 0 to c - 1; subtype switch_range is natural range 0 to p**(h - 1) - 1; subtype subtree_connection_vector is connection_vector(switch_range); subtype subtree_acknowledge_vector is acknowledge_vector(switch_range); type subtree_connection_vector_array is array (subtree_range) of subtree_connection_vector; type subtree_acknowledge_vector_array is array (subtree_range) of subtree_acknowledge_vector; signal subtree_receive_msg_from_switch, subtree_send_msg_to_switch : subtree_connection_vector_array; signal subtree_receive_ack_from_switch, subtree_send_ack_to_switch : subtree_acknowledge_vector_array; subtype switch_connection_vector is connection_vector(subtree_range); subtype switch_acknowledge_vector is acknowledge_vector(subtree_range); type switch_connection_vector_array is array (switch_range) of switch_connection_vector; type switch_acknowledge_vector_array is array (switch_range) of switch_acknowledge_vector; signal switch_receive_msg_from_subtree, switch_send_msg_to_subtree : switch_connection_vector_array; signal switch_receive_ack_from_subtree, switch_send_ack_to_subtree : switch_acknowledge_vector_array; component switch generic ( c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c - 1); send_ack_to_child : out acknowledge_vector(0 to c - 1); send_msg_to_child : out connection_vector(0 to c - 1); receive_ack_from_child : in acknowledge_vector(0 to c - 1); send_msg_to_parent : out connection_vector(0 to p - 1); receive_ack_from_parent : in acknowledge_vector(0 to p - 1); receive_msg_from_parent : in connection_vector(0 to p - 1); send_ack_to_parent : out acknowledge_vector(0 to p - 1) ); end component; component aux_fat_tree generic ( h : natural; c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c**h - 1); send_ack_to_child : out acknowledge_vector(0 to c**h - 1); send_msg_to_child : out connection_vector(0 to c**h - 1); receive_ack_from_child : in acknowledge_vector(0 to c**h - 1); send_msg_to_parent : out connection_vector(0 to p**h - 1); receive_ack_from_parent : in acknowledge_vector(0 to p**h - 1); receive_msg_from_parent : in connection_vector(0 to p**h - 1); send_ack_to_parent : out acknowledge_vector(0 to p**h - 1) ); end component; constant outer_j : natural := j; begin simple_tree : if h = 1 generate the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => receive_msg_from_child, send_ack_to_child => send_ack_to_child, send_msg_to_child => send_msg_to_child, receive_ack_from_child => receive_ack_from_child, send_msg_to_parent => send_msg_to_parent, receive_ack_from_parent => receive_ack_from_parent, receive_msg_from_parent => receive_msg_from_parent, send_ack_to_parent => send_ack_to_parent ); end generate simple_tree; compound_tree : if h > 1 generate switch_array : for i in switch_range generate the_switch : switch generic map ( c, p, k + h - 1, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_subtree(i), send_ack_to_child => switch_send_ack_to_subtree(i), send_msg_to_child => switch_send_msg_to_subtree(i), receive_ack_from_child => switch_receive_ack_from_subtree(i), send_msg_to_parent => send_msg_to_parent( i * p to (i + 1) * p - 1 ), receive_ack_from_parent => receive_ack_from_parent( i * p to (i + 1) * p - 1 ), receive_msg_from_parent => receive_msg_from_parent( i * p to (i + 1) * p - 1 ), send_ack_to_parent => send_ack_to_parent( i * p to (i + 1) * p - 1 )); end generate switch_array; subtree_array : for j in subtree_range generate the_subtree : aux_fat_tree generic map ( h - 1, c, p, k, i, outer_j * c + j ) port map ( receive_msg_from_child => receive_msg_from_child( j * c**(h - 1) to (j+ 1) * c**(h - 1) - 1 ), send_ack_to_child => send_ack_to_child( j * c**(h - 1) to (j + 1) * c**(h - 1) - 1 ), send_msg_to_child => send_msg_to_child( j * c**(h - 1) to (j + 1) * c**(h - 1) - 1 ), receive_ack_from_child => receive_ack_from_child( j * c**(h - 1) to (j+ 1) * c**(h - 1) - 1 ), send_msg_to_parent => subtree_send_msg_to_switch(j), receive_ack_from_parent => subtree_receive_ack_from_switch(j), receive_msg_from_parent => subtree_receive_msg_from_switch(j), send_ack_to_parent => subtree_send_ack_to_switch(j) ); end generate subtree_array; connect_switch : for i in switch_range generate connect_subtree : for j in subtree_range generate switch_receive_msg_from_subtree(i)(j) <= subtree_send_msg_to_switch(j)(i); subtree_receive_ack_from_switch(j)(i) <= switch_send_ack_to_subtree(i)(j); subtree_receive_msg_from_switch(j)(i) <= switch_send_msg_to_subtree(i)(j); switch_receive_ack_from_subtree(i)(j) <= subtree_send_ack_to_switch(j)(i); end generate connect_subtree; end generate connect_switch; end generate compound_tree; end top_down_recursive; ---------------------------------------------------------------- configuration top_down_recursive_aux_fat_tree of aux_fat_tree is for top_down_recursive for simple_tree for the_switch : switch use entity work.switch(behavioural); end for; end for; for compound_tree for switch_array for the_switch : switch use entity work.switch(behavioural); end for; end for; for subtree_array for the_subtree : aux_fat_tree use configuration top_down_recursive_aux_fat_tree; end for; end for; end for; end for; end top_down_recursive_aux_fat_tree; ---------------------------------------------------------------- configuration top_down_recursive_fat_tree of fat_tree is for aux for the_tree : aux_fat_tree use configuration work.top_down_recursive_aux_fat_tree; end for; end for; end top_down_recursive_fat_tree; ---------------------------------------------------------------- architecture repetitive_93 of fat_tree is function S ( h : integer ) return natural is begin if p /= c then return (p**(h + 1) - c**(h + 1)) / (p - c); elsif h >= 0 then return (h + 1) * p**h; else -- p = c and h = -1 return 0; end if; end S; function Op ( k : natural ) return natural is begin return p**(k + 1) * S(h - (k + 1)); end Op; function Mp ( k, i, j : natural ) return natural is begin return Op(k) + j * p**k + i * p; end Mp; function Oc ( k : natural ) return natural is begin return c**(h - (k - 2)) * S(k - 2); end Oc; function Mc ( k, i, j : natural ) return natural is begin return Oc(k) + i * c**(h - (k - 1)) + j * c; end Mc; subtype parent_connection_vector is connection_vector(0 to S(h) - c**h - 1); subtype parent_acknowledge_vector is acknowledge_vector(0 to S(h) - c**h - 1); signal switch_receive_msg_from_parent, switch_send_msg_to_parent : parent_connection_vector; signal switch_receive_ack_from_parent, switch_send_ack_to_parent : parent_acknowledge_vector; subtype child_connection_vector is connection_vector(0 to S(h) - p**h - 1); subtype child_acknowledge_vector is acknowledge_vector(0 to S(h) - p**h - 1); signal switch_receive_msg_from_child, switch_send_msg_to_child : child_connection_vector; signal switch_receive_ack_from_child, switch_send_ack_to_child : child_acknowledge_vector; component switch generic ( c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c - 1); send_ack_to_child : out acknowledge_vector(0 to c - 1); send_msg_to_child : out connection_vector(0 to c - 1); receive_ack_from_child : in acknowledge_vector(0 to c - 1); send_msg_to_parent : out connection_vector(0 to p - 1); receive_ack_from_parent : in acknowledge_vector(0 to p - 1); receive_msg_from_parent : in connection_vector(0 to p - 1); send_ack_to_parent : out acknowledge_vector(0 to p - 1) ); end component; begin switch_levels : for k in 1 to h generate -- bottom to top rows : for i in 0 to p**(k - 1) - 1 generate -- back to front cols : for j in 0 to c**(h - k) - 1 generate -- left to right the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_child( Mc(k, i, j) to Mc(k, i, j) + c - 1 ), send_ack_to_child => switch_send_ack_to_child( Mc(k, i, j) to Mc(k, i, j) + c - 1 ), send_msg_to_child => switch_send_msg_to_child( Mc(k, i, j) to Mc(k, i, j) + c - 1 ), receive_ack_from_child => switch_receive_ack_from_child( Mc(k, i, j) to Mc(k, i, j) + c - 1 ), send_msg_to_parent => switch_send_msg_to_parent( Mp(k, i, j) to Mp(k, i, j) + p - 1 ), receive_ack_from_parent => switch_receive_ack_from_parent( Mp(k, i, j) to Mp(k, i, j) + p - 1 ), receive_msg_from_parent => switch_receive_msg_from_parent( Mp(k, i, j) to Mp(k, i, j) + p - 1 ), send_ack_to_parent => switch_send_ack_to_parent( Mp(k, i, j) to Mp(k, i, j) + p - 1 ) ); end generate cols; end generate rows; end generate switch_levels; switch_receive_msg_from_child(0 to c**h - 1) <= receive_msg_from_child; send_ack_to_child <= switch_send_ack_to_child(0 to c**h - 1); send_msg_to_child <= switch_send_msg_to_child(0 to c**h - 1); switch_receive_ack_from_child(0 to c**h - 1) <= receive_ack_from_child; connection_levels : for k in 1 to h - 1 generate -- bottom to top rows : for i in 0 to p**k - 1 generate -- back to front cols : for j in 0 to c**(h - k) - 1 generate -- left to right switch_receive_msg_from_child ( Oc(k + 1) + i * c**(h - k) + j ) <= switch_send_msg_to_parent( Op(k) + j * p**k + i ); switch_receive_ack_from_parent( Op(k) + j * p**k + i ) <= switch_send_ack_to_child( Oc(k + 1) + i * c**(h - k) + j ); switch_receive_msg_from_parent( Op(k) + j * p**k + i ) <= switch_send_msg_to_child( Oc(k + 1) + i * c**(h - k) + j ); switch_receive_ack_from_child ( Oc(k + 1) + i * c**(h - k) + j ) <= switch_send_ack_to_parent( Op(k) + j * p**k + i ); end generate cols; end generate rows; end generate connection_levels; send_msg_to_parent <= switch_send_msg_to_parent(0 to p**h - 1); switch_receive_ack_from_parent(0 to p**h - 1) <= receive_ack_from_parent; switch_receive_msg_from_parent(0 to p**h - 1) <= receive_msg_from_parent; send_ack_to_parent <= switch_send_ack_to_parent(0 to p**h - 1); end repetitive_93; ---------------------------------------------------------------- configuration repetitive_93_fat_tree of fat_tree is for repetitive_93 for switch_levels for rows for cols for the_switch : switch use entity work.switch(behavioural); end for; end for; end for; end for; end for; end repetitive_93_fat_tree; ---------------------------------------------------------------- architecture repetitive_87 of fat_tree is function S ( h : integer ) return natural is begin if p /= c then return (p**(h + 1) - c**(h + 1)) / (p - c); elsif h >= 0 then return (h + 1) * p**h; else -- p = c and h = -1 return 0; end if; end S; subtype parent_connection_vector is connection_vector(0 to S(h) - c**h - 1); subtype parent_acknowledge_vector is acknowledge_vector(0 to S(h) - c**h - 1); signal switch_receive_msg_from_parent, switch_send_msg_to_parent : parent_connection_vector; signal switch_receive_ack_from_parent, switch_send_ack_to_parent : parent_acknowledge_vector; subtype child_connection_vector is connection_vector(0 to S(h) - p**h - 1); subtype child_acknowledge_vector is acknowledge_vector(0 to S(h) - p**h - 1); signal switch_receive_msg_from_child, switch_send_msg_to_child : child_connection_vector; signal switch_receive_ack_from_child, switch_send_ack_to_child : child_acknowledge_vector; component switch generic ( c, p : positive; k : positive; i, j : natural ); port ( receive_msg_from_child : in connection_vector(0 to c - 1); send_ack_to_child : out acknowledge_vector(0 to c - 1); send_msg_to_child : out connection_vector(0 to c - 1); receive_ack_from_child : in acknowledge_vector(0 to c - 1); send_msg_to_parent : out connection_vector(0 to p - 1); receive_ack_from_parent : in acknowledge_vector(0 to p - 1); receive_msg_from_parent : in connection_vector(0 to p - 1); send_ack_to_parent : out acknowledge_vector(0 to p - 1) ); end component; begin switch_levels : for k in 1 to h generate -- bottom to top rows : for i in 0 to p**(k - 1) - 1 generate -- back to front cols : for j in 0 to c**(h - k) - 1 generate -- left to right case_1 : if p /= c generate the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_child( c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c + c - 1 ), send_ack_to_child => switch_send_ack_to_child( c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c + c - 1 ), send_msg_to_child => switch_send_msg_to_child( c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c + c - 1 ), receive_ack_from_child => switch_receive_ack_from_child( c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((p**(k - 1) - c**(k - 1)) / (p - c)) + i * c**(h - (k - 1)) + j * c + c - 1 ), send_msg_to_parent => switch_send_msg_to_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p to p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p + p - 1 ), receive_ack_from_parent => switch_receive_ack_from_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p to p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c))+ j * p**k + i * p + p - 1 ), receive_msg_from_parent => switch_receive_msg_from_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p to p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p + p - 1 ), send_ack_to_parent => switch_send_ack_to_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p to p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i * p + p - 1 ) ); end generate case_1; case_2 : if p = c and k /= 1 and k /= h generate -- switch in an intermediate plane the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_child( c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c + c - 1 ), send_ack_to_child => switch_send_ack_to_child( c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c + c - 1 ), send_msg_to_child => switch_send_msg_to_child( c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c + c - 1 ), receive_ack_from_child => switch_receive_ack_from_child( c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c to c**(h - (k - 2)) * ((k - 1) * c**(k - 2)) + i * c**(h - (k - 1)) + j * c + c - 1 ), send_msg_to_parent => switch_send_msg_to_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p to p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p + p - 1 ), receive_ack_from_parent => switch_receive_ack_from_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p to p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p + p - 1 ), receive_msg_from_parent => switch_receive_msg_from_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p to p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p + p - 1 ), send_ack_to_parent => switch_send_ack_to_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p to p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i * p + p - 1 ) ); end generate case_2; case_3a : if p = c and k = 1 and h /= 1 generate -- switch in bottom row of tree h > 1 the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_child( j * c to j * c + c - 1 ), send_ack_to_child => switch_send_ack_to_child( j * c to j * c + c - 1 ), send_msg_to_child => switch_send_msg_to_child( j * c to j * c + c - 1 ), receive_ack_from_child => switch_receive_ack_from_child( j * c to j * c + c - 1 ), send_msg_to_parent => switch_send_msg_to_parent( p**2 * ((h - 1) * p**(h - 2)) + j * p to p**2 * ((h - 1) * p**(h - 2)) + j * p + p - 1 ), receive_ack_from_parent => switch_receive_ack_from_parent( p**2 * ((h - 1) * p**(h - 2)) + j * p to p**2 * ((h - 1) * p**(h - 2)) + j * p + p - 1 ), receive_msg_from_parent => switch_receive_msg_from_parent( p**2 * ((h - 1) * p**(h - 2)) + j * p to p**2 * ((h - 1) * p**(h - 2)) + j * p + p - 1 ), send_ack_to_parent => switch_send_ack_to_parent( p**2 * ((h - 1) * p**(h - 2)) + j * p to p**2 * ((h - 1) * p**(h - 2)) + j * p + p - 1 ) ); end generate case_3a; case_3b : if p = c and k = h and h /= 1 generate -- switch in top col of tree h > 1 the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_child( c**2 * ((h - 1) * c**(h - 2)) + i * c to c**2 * ((h - 1) * c**(h - 2)) + i * c + c - 1 ), send_ack_to_child => switch_send_ack_to_child( c**2 * ((h - 1) * c**(h - 2)) + i * c to c**2 * ((h - 1) * c**(h - 2)) + i * c + c - 1 ), send_msg_to_child => switch_send_msg_to_child( c**2 * ((h - 1) * c**(h - 2)) + i * c to c**2 * ((h - 1) * c**(h - 2)) + i * c + c - 1 ), receive_ack_from_child => switch_receive_ack_from_child( c**2 * ((h - 1) * c**(h - 2)) + i * c to c**2 * ((h - 1) * c**(h - 2)) + i * c + c - 1 ), send_msg_to_parent => switch_send_msg_to_parent( i * p to i * p+ p - 1 ), receive_ack_from_parent => switch_receive_ack_from_parent( i * p to i * p+ p - 1 ), receive_msg_from_parent => switch_receive_msg_from_parent( i * p to i * p+ p - 1 ), send_ack_to_parent => switch_send_ack_to_parent( i * p to i * p+ p - 1 ) ); end generate case_3b; case_3c : if p = c and h = 1 generate -- switch is the only one in the tree the_switch : switch generic map ( c, p, k, i, j ) port map ( receive_msg_from_child => switch_receive_msg_from_child( 0 to c - 1 ), send_ack_to_child => switch_send_ack_to_child( 0 to c - 1 ), send_msg_to_child => switch_send_msg_to_child( 0 to c - 1 ), receive_ack_from_child => switch_receive_ack_from_child( 0 to c - 1 ), send_msg_to_parent => switch_send_msg_to_parent( 0 to p - 1 ), receive_ack_from_parent => switch_receive_ack_from_parent( 0 to p - 1 ), receive_msg_from_parent => switch_receive_msg_from_parent( 0 to p - 1 ), send_ack_to_parent => switch_send_ack_to_parent( 0 to p - 1 ) ); end generate case_3c; end generate cols; end generate rows; end generate switch_levels; switch_receive_msg_from_child(0 to c**h - 1) <= receive_msg_from_child; send_ack_to_child <= switch_send_ack_to_child(0 to c**h - 1); send_msg_to_child <= switch_send_msg_to_child(0 to c**h - 1); switch_receive_ack_from_child(0 to c**h - 1) <= receive_ack_from_child; connection_levels : for k in 1 to h - 1 generate -- bottom to top rows : for i in 0 to p**k - 1 generate -- back to front cols : for j in 0 to c**(h - k) - 1 generate -- left to right case_1 : if p /= c generate switch_receive_msg_from_child ( c**(h - (k - 1)) * ((p**k - c**k) / (p - c)) + i * c**(h - k) + j ) <= switch_send_msg_to_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i ); switch_receive_ack_from_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i ) <= switch_send_ack_to_child( c**(h - (k - 1)) * ((p**k - c**k) / (p - c)) + i * c**(h - k) + j ); switch_receive_msg_from_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i ) <= switch_send_msg_to_child( c**(h - (k - 1)) * ((p**k - c**k) / (p - c)) + i * c**(h - k) + j ); switch_receive_ack_from_child ( c**(h - (k - 1)) * ((p**k - c**k) / (p - c)) + i * c**(h - k) + j ) <= switch_send_ack_to_parent( p**(k + 1) * ((p**(h - k) - c**(h - k)) / (p - c)) + j * p**k + i ); end generate case_1; case_2 : if p = c generate switch_receive_msg_from_child ( c**(h - (k - 1)) * (k * c**(k - 1)) + i * c**(h - k) + j ) <= switch_send_msg_to_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i ); switch_receive_ack_from_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i ) <= switch_send_ack_to_child( c**(h - (k - 1)) * (k * c**(k - 1)) + i * c**(h - k) + j ); switch_receive_msg_from_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i ) <= switch_send_msg_to_child( c**(h - (k - 1)) * (k * c**(k - 1)) + i * c**(h - k) + j ); switch_receive_ack_from_child ( c**(h - (k - 1)) * (k * c**(k - 1)) + i * c**(h - k) + j ) <= switch_send_ack_to_parent( p**(k + 1) * ((h - k) * p**(h - (k + 1))) + j * p**k + i ); end generate case_2; end generate cols; end generate rows; end generate connection_levels; send_msg_to_parent <= switch_send_msg_to_parent(0 to p**h - 1); switch_receive_ack_from_parent(0 to p**h - 1) <= receive_ack_from_parent; switch_receive_msg_from_parent(0 to p**h - 1) <= receive_msg_from_parent; send_ack_to_parent <= switch_send_ack_to_parent(0 to p**h - 1); end repetitive_87; ---------------------------------------------------------------- configuration repetitive_87_fat_tree of fat_tree is for repetitive_87 for switch_levels for rows for cols for case_1 for the_switch : switch use entity work.switch(behavioural); end for; end for; for case_2 for the_switch : switch use entity work.switch(behavioural); end for; end for; for case_3a for the_switch : switch use entity work.switch(behavioural); end for; end for; for case_3b for the_switch : switch use entity work.switch(behavioural); end for; end for; for case_3c for the_switch : switch use entity work.switch(behavioural); end for; end for; end for; end for; end for; end for; end repetitive_87_fat_tree; ---------------------------------------------------------------- entity fat_tree_test is end fat_tree_test; ---------------------------------------------------------------- use work.fat_tree_types.all; architecture bench of fat_tree_test is constant h : positive := 2; constant c : positive := 3; constant p : positive := 2; subtype node_range is natural range 0 to c**h - 1; subtype test_connection_vector is connection_vector(node_range); signal send_msg_to_bottom_up_tree, receive_msg_from_bottom_up_tree, send_msg_to_top_down_tree, receive_msg_from_top_down_tree, send_msg_to_repetitive_tree, receive_msg_from_repetitive_tree : test_connection_vector; subtype test_acknowledge_vector is acknowledge_vector(node_range); signal send_ack_to_bottom_up_tree, receive_ack_from_bottom_up_tree, send_ack_to_top_down_tree, receive_ack_from_top_down_tree, send_ack_to_repetitive_tree, receive_ack_from_repetitive_tree : test_acknowledge_vector; component fat_tree generic ( h : natural; c, p : positive ); port ( receive_msg_from_child : in connection_vector(0 to c**h - 1); send_ack_to_child : out acknowledge_vector(0 to c**h - 1); send_msg_to_child : out connection_vector(0 to c**h - 1); receive_ack_from_child : in acknowledge_vector(0 to c**h - 1); send_msg_to_parent : out connection_vector(0 to p**h - 1); receive_ack_from_parent : in acknowledge_vector(0 to p**h - 1) := (others => false); receive_msg_from_parent : in connection_vector(0 to p**h - 1) := (others => default_connection); send_ack_to_parent : out acknowledge_vector(0 to p**h - 1) ); end component; for bottom_up_dut : fat_tree use configuration work.bottom_up_recursive_fat_tree; for top_down_dut : fat_tree use configuration work.top_down_recursive_fat_tree; for repetitive_dut : fat_tree use configuration work.repetitive_87_fat_tree; use std.textio.all; file log_file : text is out "fat_tree_test.log"; begin bottom_up_dut : fat_tree generic map ( h, c, p ) port map ( receive_msg_from_child => send_msg_to_bottom_up_tree, send_ack_to_child => receive_ack_from_bottom_up_tree, send_msg_to_child => receive_msg_from_bottom_up_tree, receive_ack_from_child => send_ack_to_bottom_up_tree, send_msg_to_parent => open, receive_ack_from_parent => open, receive_msg_from_parent => open, send_ack_to_parent => open ); top_down_dut : fat_tree generic map ( h, c, p ) port map ( receive_msg_from_child => send_msg_to_top_down_tree, send_ack_to_child => receive_ack_from_top_down_tree, send_msg_to_child => receive_msg_from_top_down_tree, receive_ack_from_child => send_ack_to_top_down_tree, send_msg_to_parent => open, receive_ack_from_parent => open, receive_msg_from_parent => open, send_ack_to_parent => open ); repetitive_dut : fat_tree generic map ( h, c, p ) port map ( receive_msg_from_child => send_msg_to_repetitive_tree, send_ack_to_child => receive_ack_from_repetitive_tree, send_msg_to_child => receive_msg_from_repetitive_tree, receive_ack_from_child => send_ack_to_repetitive_tree, send_msg_to_parent => open, receive_ack_from_parent => open, receive_msg_from_parent => open, send_ack_to_parent => open ); message_generator : process variable msg : message_record; variable next_id : natural := 0; constant id_modulo : natural := 2**30; -- something large-ish variable L : line; begin write(L, string'("Parameters: h = ")); write(L, h); write(L, string'(", c = ")); write(L, c); write(L, string'(", p = ")); write(L, p); writeline(log_file, L); writeline(log_file, L); write(L, string'("----------------------------------------------------------------")); writeline(log_file, L); writeline(log_file, L); -- for source in node_range loop for destination in node_range loop msg := message_record'( source, destination, next_id, hops => 0, path => (others => (1,0,0)) ); next_id := (next_id + 1) mod id_modulo; send_msg_to_bottom_up_tree(source).message <= msg; send_msg_to_bottom_up_tree(source).message_waiting <= true; send_msg_to_top_down_tree(source).message <= msg; send_msg_to_top_down_tree(source).message_waiting <= true; send_msg_to_repetitive_tree(source).message <= msg; send_msg_to_repetitive_tree(source).message_waiting <= true; wait until receive_ack_from_bottom_up_tree(source) and receive_ack_from_top_down_tree(source) and receive_ack_from_repetitive_tree(source); send_msg_to_bottom_up_tree(source).message_waiting <= false; send_msg_to_top_down_tree(source).message_waiting <= false; send_msg_to_repetitive_tree(source).message_waiting <= false; wait until not receive_ack_from_bottom_up_tree(source) and not receive_ack_from_top_down_tree(source) and not receive_ack_from_repetitive_tree(source); writeline(log_file, L); end loop; write(L, string'("----------------------------------------------------------------")); writeline(log_file, L); writeline(log_file, L); end loop; wait; end process message_generator; receivers : for index in node_range generate bottom_up_receiver : process variable L : line; begin wait until receive_msg_from_bottom_up_tree(index).message_waiting; write(L, string'("Receiver ")); write(L, index); write(L, string'(" from bottom up tree: ")); write_message(L, receive_msg_from_bottom_up_tree(index).message); writeline(log_file, L); send_ack_to_bottom_up_tree(index) <= true; wait until not receive_msg_from_bottom_up_tree(index).message_waiting; send_ack_to_bottom_up_tree(index) <= false; end process bottom_up_receiver; top_down_receiver : process variable L : line; begin wait until receive_msg_from_top_down_tree(index).message_waiting; write(L, string'("Receiver ")); write(L, index); write(L, string'(" from top down tree: ")); write_message(L, receive_msg_from_top_down_tree(index).message); writeline(log_file, L); send_ack_to_top_down_tree(index) <= true; wait until not receive_msg_from_top_down_tree(index).message_waiting; send_ack_to_top_down_tree(index) <= false; end process top_down_receiver; repetitive_receiver : process variable L : line; begin wait until receive_msg_from_repetitive_tree(index).message_waiting; write(L, string'("Receiver ")); write(L, index); write(L, string'(" from repetitive tree: ")); write_message(L, receive_msg_from_repetitive_tree(index).message); writeline(log_file, L); send_ack_to_repetitive_tree(index) <= true; wait until not receive_msg_from_repetitive_tree(index).message_waiting; send_ack_to_repetitive_tree(index) <= false; end process repetitive_receiver; end generate receivers; end bench;