Skip to content

Instantly share code, notes, and snippets.

@ProgrammableGatorade

ProgrammableGatorade/GraphRadius.v

Created December 28, 2013 22:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ProgrammableGatorade/8165003 to your computer and use it in GitHub Desktop.
Save ProgrammableGatorade/8165003 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
GraphRadius.v
module GraphRadius #(
parameter NumNodes = 10,
parameter L2NumNodes = Log2(NumNodes),
parameter DistVecWidth = NumNodes * L2NumNodes,
parameter DistMatrixPkdWidth = NumNodes * DistVecWidth,
parameter CHARS_PER_LINE = 16,
parameter CYCLES_PER_IDLE = 375000,
parameter CYCLES_PER_CMD = 25000,
parameter CYCLE_ENA_ASSERT = 25,
parameter CYCLE_ENA_DEASSERT = 50
)(
input wire rst_n_i,
input wire clk50_i,
output wire lcd_rs_o,
output wire lcd_rw_o,
output wire [7:0] lcd_data_o,
output wire lcd_e_o
);
//--------------------------------------------------------------------------------------------
function integer Log2;
input [31:0] value;
for (Log2=0; value>=1; Log2=Log2+1)
value = value>>1;
endfunction
localparam STATE_IDLE = 0;
localparam STATE_INIT_ADJ_MATRIX = 1;
localparam STATE_WAIT_FOR_ANSWER = 2;
localparam STATE_DISPLAY_ANSWER = 3;
localparam STATE_DONE = 4;
localparam NumStates = 5;
localparam StateWidth = Log2(NumStates);
reg rst_i;
wire clk_i;
reg [StateWidth-1:0] state;
reg adj_vec_enb;
reg [NumNodes-1:0] adj_vec_dat;
reg [L2NumNodes-1:0] adj_vec_adr;
wire [DistMatrixPkdWidth-1:0] dist_matrix_pkd;
wire [DistVecWidth-1:0] dist_vec [NumNodes-1:0];
wire [L2NumNodes-1:0] max_dist [NumNodes-1:0];
reg [L2NumNodes-1:0] total_max_dist;
reg [L2NumNodes-1:0] total_max_dist_r;
reg [L2NumNodes-1:0] node_cntr;
reg lcd_ena;
wire lcd_rdy;
//--------------------------------------------------------------------------------------------
// invert active-low reset
//--------------------------------------------------------------------------------------------
always@(posedge clk50_i) begin
rst_i <= ~rst_n_i;
end
//--------------------------------------------------------------------------------------------
// divide 50MHz clock down to 25Mhz
//--------------------------------------------------------------------------------------------
ClkDiv
ClkDiv (
.areset ( rst_i ),
.inclk0 ( clk50_i ),
.c0 ( clk_i ),
.locked ( )
);
//--------------------------------------------------------------------------------------------
// this process programs the adjacency matrix
always@(posedge rst_i, posedge clk_i) begin
if (rst_i) begin
adj_vec_enb <= 'd0;
adj_vec_adr <= 'd0;
adj_vec_dat <= 'd0;
node_cntr <= 'd0;
lcd_ena <= 'd0;
state <= STATE_IDLE;
end else begin
adj_vec_enb <= 'd0;
adj_vec_adr <= 'd0;
adj_vec_dat <= 'd0;
node_cntr <= 'd0;
lcd_ena <= 'd0;
case (state)
STATE_IDLE: begin
state <= STATE_INIT_ADJ_MATRIX;
end
STATE_INIT_ADJ_MATRIX: begin
node_cntr <= node_cntr + 1;
adj_vec_enb <= 1'b1;
adj_vec_adr <= node_cntr;
case (node_cntr)
0: adj_vec_dat <= 'b0000110010; // 4 5 8
1: adj_vec_dat <= 'b0001000101; // 3 7 9
2: adj_vec_dat <= 'b0010001010; // 2 6 8
3: adj_vec_dat <= 'b0100010100; // 1 5 7
4: adj_vec_dat <= 'b1000001001; // 0 6 9
5: adj_vec_dat <= 'b0110000001; // 1 2 9
6: adj_vec_dat <= 'b1100000010; // 0 1 8
7: adj_vec_dat <= 'b1000100100; // 0 4 7
8: adj_vec_dat <= 'b0001101000; // 3 4 6
9: adj_vec_dat <= 'b0011010000; // 2 3 5
endcase
if (node_cntr >= NumNodes) begin
node_cntr <= 0;
state <= STATE_WAIT_FOR_ANSWER;
end
end
STATE_WAIT_FOR_ANSWER: begin
node_cntr <= node_cntr + 1;
if (node_cntr >= NumNodes) begin
node_cntr <= 0;
state <= STATE_DISPLAY_ANSWER;
end
end
STATE_DISPLAY_ANSWER: begin
if (lcd_rdy) begin
lcd_ena <= 'd1;
state <= STATE_DONE;
end
end
STATE_DONE: begin
end
default: begin
state <= STATE_IDLE;
end
endcase
end
end
//--------------------------------------------------------------------------------------------
genvar n;
generate
for (n=0; n<NumNodes; n=n+1) begin : GEN_NODES
Node #(
.NodeID ( n ),
.NumNodes ( NumNodes ),
.L2NumNodes ( L2NumNodes ),
.DistVecWidth ( DistVecWidth ),
.DistMatrixPkdWidth ( DistMatrixPkdWidth )
)
Node (
.rst_i ( rst_i ),
.clk_i ( clk_i ),
.adj_vec_enb_i ( adj_vec_enb ),
.adj_vec_adr_i ( adj_vec_adr ),
.adj_vec_dat_i ( adj_vec_dat ),
.dist_matrix_pkd_i ( dist_matrix_pkd ),
.dist_vec_o ( dist_vec[n] ),
.max_dist_o ( max_dist[n] )
);
assign dist_matrix_pkd[n*DistVecWidth +: DistVecWidth] = dist_vec[n];
end
endgenerate
//--------------------------------------------------------------------------------------------
always@(*)
begin : FIND_TOTAL_MAX_DIST
integer n;
total_max_dist = 0;
for (n=0; n<NumNodes; n=n+1) begin
if (max_dist[n] > total_max_dist) begin
total_max_dist = max_dist[n];
end
end
end
//--------------------------------------------------------------------------------------------
always@(posedge clk_i) begin
total_max_dist_r <= total_max_dist;
end
//--------------------------------------------------------------------------------------------
// convert our digits to 16-bytes of ascii (to be displayed on the lcd)
//--------------------------------------------------------------------------------------------
wire [CHARS_PER_LINE*8-1:0] lcd_data;
assign lcd_data[CHARS_PER_LINE*8-1:8] = "Graph radius = ";
assign lcd_data[7:0] = total_max_dist_r | "0";
//--------------------------------------------------------------------------------------------
// once we've finally found our answer we display it on the lcd
//--------------------------------------------------------------------------------------------
LcdController #(
.CHARS_PER_LINE ( CHARS_PER_LINE ),
.CYCLES_PER_CMD ( CYCLES_PER_CMD ),
.CYCLES_PER_IDLE ( CYCLES_PER_IDLE ),
.CYCLE_ENA_ASSERT ( CYCLE_ENA_ASSERT ),
.CYCLE_ENA_DEASSERT ( CYCLE_ENA_DEASSERT )
)
LcdController (
.rst_i ( rst_i ),
.clk_i ( clk_i ),
.init_i ( 1'b0 ),
.line_ena_i ( lcd_ena ),
.line_data_i ( lcd_data ),
.line_rdy_o ( lcd_rdy ),
.lcd_rs_o ( lcd_rs_o ),
.lcd_rw_o ( lcd_rw_o ),
.lcd_data_o ( lcd_data_o ),
.lcd_e_o ( lcd_e_o )
);
//--------------------------------------------------------------------------------------------
// synthesis translate_off
string state_str;
always@(state) begin
case (state)
STATE_IDLE : state_str = "STATE_IDLE";
STATE_INIT_ADJ_MATRIX : state_str = "STATE_INIT_ADJ_MATRIX";
STATE_WAIT_FOR_ANSWER : state_str = "STATE_WAIT_FOR_ANSWER";
STATE_DISPLAY_ANSWER : state_str = "STATE_DISPLAY_ANSWER";
STATE_DONE : state_str = "STATE_DONE";
endcase
end
// synthesis translate_on
endmodule
`default_nettype none
Raw
Node.v
// macro to select a node's distance in a packed distance vector
`define NODE_SEL(node_num) (node_num)*L2NumNodes +: L2NumNodes
module Node #(
parameter NodeID = 0,
parameter NumNodes = 10,
parameter L2NumNodes = Log2(NumNodes),
parameter DistVecWidth = NumNodes * L2NumNodes,
parameter DistMatrixPkdWidth = NumNodes * NumNodes * L2NumNodes
)(
input wire rst_i,
input wire clk_i,
input wire adj_vec_enb_i,
input wire [L2NumNodes-1:0] adj_vec_adr_i,
input wire [NumNodes-1:0] adj_vec_dat_i,
input wire [DistMatrixPkdWidth-1:0] dist_matrix_pkd_i,
output reg [DistVecWidth-1:0] dist_vec_o,
output reg [L2NumNodes-1:0] max_dist_o
);
reg [NumNodes-1:0] adj_vec;
reg [L2NumNodes-1:0] max_dist;
reg [DistVecWidth-1:0] dist_matrix_rmt [NumNodes-1:0];
reg [DistVecWidth-1:0] dist_matrix_lcl [NumNodes-1:0];
//------------------------------------------------------------------------
function integer Log2;
input [31:0] value;
for (Log2=0; value>=1; Log2=Log2+1)
value = value>>1;
endfunction
//------------------------------------------------------------------------
always@(*)
begin : UNPACK_DIST_MATRIX
integer r;
for (r=0; r<NumNodes; r=r+1) begin
dist_matrix_rmt[r] <= dist_matrix_pkd_i[r*DistVecWidth +: DistVecWidth];
end
end
//------------------------------------------------------------------------
always@(posedge rst_i, posedge clk_i)
begin : LOAD_ADJACENCY_VECTOR
if (rst_i) begin
adj_vec <= 0;
end else if (adj_vec_enb_i && adj_vec_adr_i == NodeID) begin
adj_vec <= adj_vec_dat_i;
end
end
//------------------------------------------------------------------------
always@(posedge clk_i)
begin : UPDATE_DIST_MATRIX
integer r, c;
for (r=0; r<NumNodes; r=r+1) begin
for (c=0; c<NumNodes; c=c+1) begin
if (r == NodeID) begin
if (c == NodeID) begin
dist_matrix_lcl[r][`NODE_SEL(c)] <= 0;
end else if (adj_vec[c]) begin
dist_matrix_lcl[r][`NODE_SEL(c)] <= 1;
end else begin
dist_matrix_lcl[r][`NODE_SEL(c)] <= -1; // all ones
end
end else if (adj_vec[r]) begin
if (dist_matrix_rmt[r][`NODE_SEL(c)] == 4'hf) begin // all ones
dist_matrix_lcl[r][`NODE_SEL(c)] <= 4'hf;
end else begin
dist_matrix_lcl[r][`NODE_SEL(c)] <= dist_matrix_rmt[r][`NODE_SEL(c)] + 1;
end
end else begin
dist_matrix_lcl[r] <= {DistVecWidth{1'b1}};
end
end
end
end
//------------------------------------------------------------------------
always@(*)
begin : REPORT_DIST_VECTOR
integer r,c;
dist_vec_o = {DistVecWidth{1'b1}};
for (c=0; c<NumNodes; c=c+1) begin
for (r=0; r<NumNodes; r=r+1) begin
if (dist_matrix_lcl[r][`NODE_SEL(c)] < dist_vec_o[`NODE_SEL(c)]) begin
dist_vec_o[`NODE_SEL(c)] = dist_matrix_lcl[r][`NODE_SEL(c)];
end
end
end
end
//------------------------------------------------------------------------
always@(*)
begin : FIND_MAX_DIST
integer c;
max_dist = 4'h0;
for (c=0; c<NumNodes; c=c+1) begin
if (dist_vec_o[`NODE_SEL(c)] > max_dist) begin
max_dist = dist_vec_o[`NODE_SEL(c)];
end
end
end
//------------------------------------------------------------------------
always@(posedge clk_i) begin
max_dist_o <= max_dist;
end
endmodule
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment