DIC_final_project/maze_solver_design_report.md

Maze Solver Chip Design Report

An explanation of the design of our 16x16 expandable maze solver chip, including a detailed dive into the SystemVerilog.

Table of Contents

1. High-Level Chip Purpose & Design

2. FSM Design & General Flow

3. Datapath Design

4. Code Implementation

1. High-Level Chip Purpose & Design

The chip is able to solve a maze, outputting the correct sequence of moves (up, down, left, right) needed to traverse the maze without any dead ends. It accomplishes this by requesting cell locations from off-chip memory and accepting their wall configurations as a 4-bit input.

• As the chip moves around the maze, it requests new memory locations until it reaches the end of the maze.
  • The chip may take dead-end paths, but its solution does not include any dead ends due to the implementation of a hardware stack.
• Once it reaches the end, the chip outputs the solution as a series of 2-bit numbers corresponding to the series of moves (up, right, down, left) needed to successfully traverse the maze.

Inputs & Outputs

We have a total of 21 I/O pins.

• Inputs
  • 1 start pin
  • 1 rst pin
  • 1 clk pin
  • 1 input_enable pin
  • 4 bits for the cur_wall input
• Outputs
  • 1 done output pin
  • 1 req_next_addr output pin
  • 1 out_val pin
  • 4 bits for the next_x output
  • 4 bits for the next_y output
  • 2 bits for the solution output

2. FSM Design & General Flow

FSM Implementation

The chip's controller is a 14-state FSM. The FSM state diagram is shown below. Note: only inputs and outputs to the FSM are shown, not the datapath.

General Flow

This is the general flow of the chip:

Setup

1. IDLE (S0): Wait for the external start input pin to go high before proceeding. Then go to INPUT (S1).

Intake Walls

1. INPUT (S1): Wait for the external input_enable input pin to go high, indicating that input cur_wall [3:0] is valid for the requested address req_addr [7:0] output. Then go to LOAD (S2).
2. LOAD (S2): Save cur_wall input at the start of the datapath. If the input is 0000, we've reached the end so jump to LAST (S11); otherwise, continue to RIGHT (S3).

Move Decision

1. RIGHT (S3): Check to see if a right turn is possible. If so, go to CHECK (S7); otherwise, continue to UP (S4).
2. UP (S4): Check to see if going straight is possible. If so, go to CHECK (S7); otherwise, continue to LEFT (S5).
3. LEFT (S5): Check to see if a left turn is possible. If so, go to CHECK (S7); otherwise, continue to DOWN (S6).
4. DOWN (S6): This move will always be possible (for details, see datapath section). Go to CHECK (S7).

Backtrack Detection

1. CHECK (S7): Check to see if current move is is backtracking on a previous move. If so, go to POP (S9); otherwise, go to PUSH (S8).
2. PUSH (S8): Push the current move to the stack. Go to UPDATE (S10).
3. POP (S9): Pop from the stack. Go to UPDATE (S10).
4. UPDATE (S10): Update internal registers in preparation for next cycle. Go to INPUT (S2).

Output Solution

1. LAST (S11): Check to see if the last move has been read. If so, go to DONE (S13); otherwise, go to OUTPUT (S12).
2. OUTPUT (S12): Read value from stack, starting from the bottom, to the solution [1:0] output. Go to LAST (S11).
3. DONE (S13): Wait for external rst signal to go back to IDLE (S0).

3. Datapath Design

This is our circuit diagram:

Absolute vs. Relative Directions/Moves

In a maze, there are two ways of thinking about movement.

1. The absolute view, from the perspective of someone looking at the maze from the outside.
2. The relative view, from the perspective of someone who is walking around the maze themselves.

The chip uses both of these perspectives. In the datapath, we start with an absolute wall configuration, which is the walls surrounding a cell when viewing it from the perspective of the whole maze. This data is then translated into the relative wall configuration, which is the walls from the perspective of the current direction. For example, if the walls above and to the right a cell looking at it from the outside (absolute configuration), then if the chip is currently moving right through the maze, from its perspective there are walls above and to the left (relative configuration).

The relative move can then be decided based on this relative configuration, and the relative move can finally be translated back into an absolute move Using the pervious example, if we were moving right, and had walls above and to the left, we would turn right (relative move). But because we were already going right, turning right again would actually mean we're now going down, so the absolute move would be down.

Loading an Input

The cur_wall input is saved at the beginning of the datapath. This input represents the absolute wall configuration of a cell. Walls in the datapath are 4 bits, each representing a wall surrounding the cell - up, right, down, left.

Example: A cell with walls above and to the left of it would have the encoding 1001.

If the wall input = 0000, a NOR gate called wall_check sets the no_walls flag to 1. This flag tells the FSM that the chip has reached the end of the maze.

The current absolute direction is saved in the abs_dir_reg register in the datapath. Direction, both absolute and relative, is represented as follows:

1. 00 - Up
2. 01 - Right
3. 10 - Down
4. 11 - Left

The absolute direction value is used to perform a barrel shift left on the current wall input, transforming it from an absolute configuration to a relative configuration. This is accomplished by the rotate_wall module in the datapath.

Example: We are moving left, which is direction 11. Shifting 1001 by 11 results in 1100, which is the relative configuration. We now know we have walls above and to our right from our perspective of moving left

Deciding a Move

Since we transformed the absolute wall configuration to a relative one, there is no need to account for every combination of walls for every direction. The move decision is now easy. We follow this pattern:

1. Try to move right
2. Try to move up (go stright)
3. Try to move left
4. Go down (backwards)

In the datapath, this is as easy as selecting the right bit, then the up bit, then the left bit, etc. of the relative wall config to see if there's a wall there (this happens in the wall_check module of the datapath). We invert the wall input so if there is no wall and the move is valid, the val_move flag goes high. This flag is an input to the FSM.

Example: Our relative wall config is 1100, which means we can't go right or up. We can go left (11), so we'll choose that move.

The relative move is saved to the rel_move_reg register. Now we can tranform our relative move to an absolute move. This is done simply by adding our relative move to our absolute direction, and happens in the rel_to_abs_alu module.

Example: The selected move is left (11), and our current direction is left (11). 11 + 11 = (1)10, so our absolute move is 10 (down).

Detecting a Backtrack

We now have our absolute move, which is saved to the abs_move_buf register and is an input to the back_test module. The second input to the back_test module is the value at the top of the stack, representing the last valid move pushed to the stack. The back_test module checks to see if these moves are opposite; in other words, if the current move and the top move of the stack are inverse (up & down, or left & right), we know we are backtracking. If so, the back_test module sets the back_flag to 1.

Example: If the last absolute valid move was left (11), and our current absolute move is down (10), then we are not backtracking because these are not inverses. The back_flag is not set to 1.

Storing the Correct paths

If we aren't backtracking, we can store the current move to the stack as a valid move. (This move could later become invalid if we backtrack over it, but for now it's valid.) To do this, the FSM sets stack_en to 1 and stack_op to 0, which corresponds to a push operation. The current move is pushed to the stack.

If we are backtracking, the FSM sets stack_en to 1 and stack_op to 1, corresponding to a pop operation. The previous move is popped from the stack and the current move is not pushed since they "cancel out".

Example: We push our down (10) move to the stack since we aren't backtracking.

Updating the Next Address & Internal Registers

Regardless of a push or pop, we still need to decide which address to request next from external memory. For a 16x16 maze, the address is stored as a single 8-bit number, with bits 7-4 for the x coordinate and bits 3-0 for the y coordinate. The cur_addr_reg register stores the current address. When the chip resets, this address is set to 0.

The current move is translated into an ALU operation and input like this:

1. 00 (Up) - Add 1 to the y coordinate (add_sub = 0, x_y = 00000001)
2. 01 (Right) - Add 1 to the x coordinate (add_sub = 0, x_y = 00010000)
3. 10 (Down) - Subtract 1 from the y coordinate (add_sub = 1, x_y = 00000001)
4. 11 (Left) - Subtract 1 from the x coordinate (add_sub = 1, x_y = 00010000)

The x_y bus is added to or subtracted from the current address to form the next address, stored in the next_addr_reg register and split into its x and y chip outputs with the addr_split module. This address is requested from memory.

Example: Let's say our previous address was [x,y] = [13,5] (11010101), and our current move is down (10). We subtract 1 from the y coordinate: 11010101 - 00000001 = 11010100, which is [13, 4]. The outputs x = 13 and y = 4 are requested from external memory.

The final part of the main FSM loop involves updating the internal registers. The current move is written to the abs_dir_reg, since it is not the absolute direction we are travelling through the maze. The current address is updated to the next address. The FSM then returns to S1 where it waits for the next input.

Example: The current move, down (10), is written to the abs_dir_reg register. The address stored in the next_addr_reg register, 11010100, is stored in the cur_addr_reg register.

Outputting the Solution

When the chip has reached the end of the maze, it's time to send the solution. This is all implemented in the FSM and stack. Details on the stack implementation can be found here.

The stack has an internal pointer, separate from the stack pointer, which starts at stack address 0 and can be incremented by the FSM with the stack_sol_inc signal. The FSM increments this pointer and checks to see if it has reached the end of the path with the stack_ptrs_eq flag, set by the stack when the output pointer has reached the top of the stack, marked by the stack pointer.

On each increment of the solution pointer, the FSM...

1. enables the sol_reg register, writing to the solution [1:0] output pins, and
2. sets out_val to 1, marking the output valid.

This marks the end of the datapath.

4. Code Implementation

Our maze solver code is organized hierarchically as follows:

    // FSM declaration
    module fsm_design;
    
    // Datapath component declarations
    module reg_nbit;
    module add_sub_wrap_nbit;
    module not_left_nbit;
    module bit_sel_4bit;
    module not_4bit;
    module nor_4bit;
    module move_conv_logic;
    module back_test_logic;
    module split_1_to_2_nbit;
    module stack_ncell;
    
    // Datapath declaration
    module datapath_design (
       	reg_nbit cur_wall_reg,
       	rot_left_4bit rotate_wall,
       	reg_nbit abs_dir_reg,
       	not_4bit wall_invert,
       	bit_sel_4bit test_move,
       	nor_4bit wall_check,
        reg_nbit rel_move_reg,
        reg_nbit abs_move_buf,
        reg_nbit rel_to_abs_alu,
        move_conv_logic move_conv,
        add_sub_wrap_nbit cur_to_next_alu,
        reg_nbit cur_addr_reg,
        reg_nbit next_addr_reg,
        split_1_to_2_nbit addr_split,
        back_test_logic back_test,
        stack_ncell stack,
        reg_nbit sol_reg
    );
    
    module chip_design (
        fsm_design controller,
        datapath_design datapath
    );

Our highest-level module, chip_design, is at the bottom of the .sv file to preserve Verilog hierarchical organization rules, where the components of a module are declared above the module. Most of this breakdown will concern the datapath components, since this is where the actual processing is happening.

Registers

Our variable-size register file is defined as follows:

    module reg_nbit #(
        parameter N = 8 // default to 8 bits
    ) (
        input wire reg_clk,
        input wire reg_en,
        input wire reg_rst,
        input wire [N-1:0] reg_in,
    
        output logic [N-1:0] reg_out
    );
    
        always_comb begin
            if (reg_rst) begin
                reg_out <= {N{1'b0}}; // zero register on rst signal
            end
            else if (reg_en) begin
                reg_out <= reg_in; // update reg on en signal
            end
        end
    
    endmodule

We made this register of variable size so it can be used for all internal registers, and so chip can be expanded to accommodate larger mazes according to the MAX_SIZE parameter. These registers are:

• 2-bit: abs_dir_reg, rel_mov_reg, abs_move_buf, sol_reg
• 4-bit: cur_wall_reg
• *8-bit: cur_addr_reg, next_addr_reg *for 16x16 mazes only

We used a always_comb block instead of an always_ff block to avoid the 1-cycle delay that is inherent to a flip-flop. Our register implementation is only a problem if we have a register feeding directly back into itself, but we have everything buffered so this isn't an issue.

The register is zeroed when it receives a rst signal, and when it receives a reg_en it saves the input.

Rotate_Wall Module

The rotate_wall module takes a 4-bit wall input (rot_in) and rotates it by the 2-bit input rot_val. This is accomplished by rotating the input left and appending the bits that rotated out of bounds to the right side with an assign statement:

    assign rot_out = (rot_in << rot_val) | (rot_in >> (4 - rot_val));

Adder/Subtractor

We made one ALU (really just an adder & subtractor) module to use for the two ALUs in the datapath:

1. The rel_to_abs_alu, which takes the relative move and converts it to an absolute move by adding the current absolute direction [1:0]
2. The cur_to_next_alu, which increments or decrements the x/y coordinates stored in the cur_addr_reg register to calculate the next address [7:0]

We needed our implementation to be able to overflow, since the rel_to_abs_alu relies on this behavior to function. We also needed to make the module expandable to account for the two different sizes needed.

Here is the SystemVerilog code:

    module add_sub_wrap_nbit #(
        parameter N = 2
    ) (
        input wire [N-1:0] a_in,
        input wire [N-1:0] b_in,
        input wire         add_sub_sel, // 0 = add, 1 = sub
    
        output logic [N-1:0] result
    );
        assign result = add_sub_sel ? (a_in - b_in) : (a_in + b_in);
    endmodule

The add_sub_sel input is used to select the operation. The rel_to_abs_alu does not use the subtract, so for its module instantiation, this signal is hardcoded as 0:

    add_sub_wrap_nbit #(.N(2)) rel_to_abs_alu (
            .a_in   (relative_move_wire),
            .b_in   (absolute_dir_wire),
            .add_sub_sel (1'b0),
            .result (absolute_move_wire)
    );

Stack

Our expandable stack has 6 inputs and 3 outputs.

• Inputs
  • clk: connected to external clk input pin
  • rst_stack: resets stack's internal pointers and memory
  • stack_en: when 1, stack operation will be performed on clk signal
  • stack_op: 0 = push, 1 = pop
  • stack_in [1:0]: data input to the stack
  • stack_sol_inc: increments stack_sol_ptr for output
• Outputs
  • stack_out [1:0]: memory location pointed to by stack_ptr, inc/dec internally
  • stack_sol [1:0]: memory location pointed to by stack_sol_ptr + 1, incremented by stack_sol_inc input
  • stack_ptrs_eq: set to 1 when stack_ptr = stack_sol_ptr

Here is the SystemVerilog code:

    module stack_ncell #(
        parameter CELLS = 256
    ) (
        input  wire         clk,
        input  wire         rst_stack,
        input  wire         stack_en,    // High to enable push/pop operations
        input  wire         stack_op,    // 0 for push, 1 for pop
        input  wire  [1:0]  stack_in,
        input  wire         stack_sol_inc,
        output logic [1:0]  stack_out,
        output logic [1:0]  stack_sol,
        output logic        stack_ptrs_eq
    );
    
        localparam PTR_WIDTH = $clog2(CELLS);
    
        logic [1:0] mem [0:CELLS-1];
        logic [PTR_WIDTH-1:0] stack_ptr;
        logic [PTR_WIDTH-1:0] stack_sol_ptr;
    
        always_ff @(posedge clk or posedge rst_stack) begin
            if (rst_stack) begin
                stack_ptr <= 0;
                stack_sol_ptr <= 0;
                mem <= '{default:2'b00};
            end else if (stack_sol_inc) begin
                stack_sol_ptr <= stack_sol_ptr + 1;
            end else if (stack_en) begin
                if (!stack_op) begin // Push Operation (stack_op is 0)
                    // 1. Increment the stack pointer
                    stack_ptr <= stack_ptr + 1;
                    // 2. Write the input data to the new top location
                    mem[stack_ptr + 1] <= stack_in;
                end else begin // Pop Operation (stack_op is 1)
                    stack_ptr <= stack_ptr - 1;
                end
            end
        end
    
        assign stack_out = mem[stack_ptr];
        assign stack_sol = mem[stack_sol_ptr + 1];
        assign stack_ptrs_eq = (stack_ptr == stack_sol_ptr);
    
    endmodule

If stack_en = 1 and stack_op = 0, this indicates a push operation. We increment the stack pointer and write the stack input to the new memory location. If stack_op = 1, this is a pop operation and we decrement the stack pointer. We don't actually pop data out of the stack to use; we're essentially deleting the top value of the stack by making it out of bounds.

The stack_sol output is the stack_sol_ptr + 1 because the stack_sol_ptr starts at address 0, but the first valid move will be at address 1, not 0. The FSM checks stack_ptrs_eq and then increments the pointer, so when stack_sol_ptr = stack_ptr - 1, the FSM will...

1. Read the value at stack_sol_ptr + 1, which is the top of the stack (mem[stack_ptr])
2. Increment the stack_sol_ptr
3. Check stack_ptrs_eq, which is now 1
4. Exit

This does mean that we only have 255 usable locations for a 16x16 solver instead of 256, but this doesn't matter since 255 is the maximum number of moves within a 16x16 grid. The stack is expandable to accommodate the MAX_SIZE parameter.

Test_Move Module

The test_move module is a simple 4-bit bit selector, which sets the 1-bit output equal to the selected bit of the 4-bit input.

    module bit_sel_4bit (
        input wire [3:0] sel_in,
        input wire [1:0] sel_val, // bit to select
    
        output logic sel_out
    );
    
        always_comb begin
            case (sel_val)
                2'b00: sel_out = sel_in[3]; // "up" direction
                2'b01: sel_out = sel_in[2]; // "right" direction
                2'b10: sel_out = sel_in[1]; // "left" direction
                2'b11: sel_out = sel_in[0]; // "down" direction
    
                default: sel_out = 1'b0; // default case
            endcase
        end
    
    endmodule

Back_Test Module

The back_test module implements clever logic to simplify the detection of backtracking. Instead of checking the four possible cases for current and previous values:

1. Up (00), Down (10)
2. Down (10), Up (00)
3. Right (01), Left (11)
4. Left (11), Right (01)

it instead checks two conditions with an assign statement:

1. The inputs are different
2. The inputs have the same least significant bit

module back_test_logic (
    input wire [1:0] cur_in,
    input wire [1:0] prev_in,

    output logic backtrack
);
    // If cur_in and prev_in are different but have the same LSB, chip is backtracking
    assign backtrack = (cur_in != prev_in) && (cur_in[0] == prev_in[0]);

endmodule

Move_Conv Module

The move_conv logic block takes in a 2-bit move and outputs a 1-bit ALU operation (add_sub) and the data output x_y.

    module move_conv_logic #(
        parameter COOR_WIDTH = 4
    ) (
        input wire [1:0] move_in,
    
        output logic [(COOR_WIDTH*2)-1:0] x_y,
        output logic add_sub // 0 for add, 1 for sub
    );
    
        logic [COOR_WIDTH-1:0] add_x;
        logic [COOR_WIDTH-1:0] add_y;
    
        always_comb begin
            case (move_in)
                2'b00: begin // up
                    add_sub = 0;
                    add_x   = 0;
                    add_y   = 1;
                end
    
                2'b01: begin // right
                    add_sub = 0;
                    add_x   = 1;
                    add_y   = 0;
                end
    
                2'b10: begin // down
                    add_sub = 1;
                    add_x   = 0;
                    add_y   = 1;
                end
    
                2'b11: begin // left
                    add_sub = 1;
                    add_x   = 1;
                    add_y   = 0;
                end
    
                default: begin // default case
                    add_sub = 0;
                    add_x   = 0;
                    add_y   = 0;
                end
            endcase
        end
    
        assign x_y = {add_x, add_y}; // recombine x and y into one output

endmodule

The module has two separate internal wires for x and y called add_x and add_y, which it combines into the single x_y output with an assign statement. We chose this design so the module can be expanded according to the MAX_SIZE parameter.

See the previous section for details on the move conversion logic.

Splitter

The addr_split module takes the 8-bit next address output (for a 16x16 maze) and splits it into its x and y components with two assign statements:

    assign split_high_out = split_in[N-1:N/2];
    assign split_low_out = split_in[(N/2)-1:0];

Wall_Invert & Wall_Check

The wall_invert and wall_check modules are simple NOT and NOR gates, respectively.

The wall_invert module takes the 4-bit absolute wall configuration and inverts each bit with an assign statement:

    assign not_out = ~not_in;

Similarly, the wall_check module uses an assign statement to produce the NOR output of the 4-bit relative wall configuration:

    assign nor_out = ~(|nor_in);