Dual-port RAM design in Verilog - Time & Space Complexity

Time Complexity: Dual-port RAM design

O(1)

Understanding Time Complexity

We want to understand how the time it takes to read and write memory changes as the size of the memory grows.

How does the design of a dual-port RAM affect the speed when we increase its size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module dual_port_ram (
  input logic clk,
  input logic [7:0] addr_a, addr_b,
  input logic [7:0] data_in_a, data_in_b,
  input logic we_a, we_b,
  output logic [7:0] data_out_a, data_out_b
);
  logic [7:0] ram [0:255];

  always_ff @(posedge clk) begin
    if (we_a) ram[addr_a] <= data_in_a;
    data_out_a <= ram[addr_a];
    if (we_b) ram[addr_b] <= data_in_b;
    data_out_b <= ram[addr_b];
  end
endmodule

This code models a dual-port RAM with two independent read/write ports working on a 256-byte memory.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing memory array at given addresses for read and write.
• How many times: Each clock cycle, two memory accesses happen independently.

How Execution Grows With Input

As the memory size grows, each read or write still happens in one step because the address directly selects the memory location.

Input Size (memory size)	Approx. Operations per cycle
256	2 (one read/write per port)
1024	2 (still one read/write per port)
4096	2 (still one read/write per port)

Pattern observation: The number of operations per cycle stays the same regardless of memory size.

Final Time Complexity

Time Complexity: O(1)

This means each read or write happens in constant time, no matter how big the memory is.

Common Mistake

[X] Wrong: "Accessing larger memory always takes longer because it has more data to search through."

[OK] Correct: In hardware RAM, the address directly selects the memory cell, so access time stays constant regardless of size.

Interview Connect

Understanding how hardware memory access time stays constant helps you explain efficient designs and shows you know how hardware differs from software loops.

Self-Check

"What if the RAM was implemented as a large array accessed by a software loop instead of hardware memory? How would the time complexity change?"

Practice

1. What is the main advantage of using a dual-port RAM in hardware design?

easy

A. It allows two independent read/write operations simultaneously.

B. It reduces the size of the memory.

C. It makes the RAM slower but cheaper.

D. It only supports read operations.

Solution

1. Step 1: Understand dual-port RAM functionality

   Dual-port RAM has two ports that can access memory independently at the same time.

2. Step 2: Identify the main benefit

   This allows simultaneous read/write operations, improving performance.

3. Final Answer:

   It allows two independent read/write operations simultaneously. -> Option A

4. Quick Check:

   Dual-port RAM = two simultaneous accesses [OK]

Hint: Dual-port RAM means two ports can access memory at once [OK]

Common Mistakes:

• Thinking it reduces memory size
• Assuming it only supports reads
• Believing it slows down RAM

2. Which of the following is the correct Verilog port declaration for a dual-port RAM with separate read and write ports?

easy

A. input clk, input [7:0] addr_a, output [7:0] data_out_a, input [7:0] addr_b, output [7:0] data_out_b;

B. input clk, input [7:0] addr, input [7:0] data_in, output [7:0] data_out, input we;

C. input clk, input [7:0] addr, output [7:0] data_out, input we, input re;

D. input clk, input [7:0] addr_a, input [7:0] data_in_a, output [7:0] data_out_a, input we_a, input [7:0] addr_b, input [7:0] data_in_b, output [7:0] data_out_b, input we_b;

Solution

1. Step 1: Identify dual-port RAM ports

   Dual-port RAM needs separate address, data, and write enable signals for each port.

2. Step 2: Match correct declaration

   input clk, input [7:0] addr_a, input [7:0] data_in_a, output [7:0] data_out_a, input we_a, input [7:0] addr_b, input [7:0] data_in_b, output [7:0] data_out_b, input we_b; declares separate addr, data_in, data_out, and we signals for ports A and B, matching dual-port RAM design.

3. Final Answer:

   input clk, input [7:0] addr_a, input [7:0] data_in_a, output [7:0] data_out_a, input we_a, input [7:0] addr_b, input [7:0] data_in_b, output [7:0] data_out_b, input we_b; -> Option D

4. Quick Check:

   Separate signals per port = input clk, input [7:0] addr_a, input [7:0] data_in_a, output [7:0] data_out_a, input we_a, input [7:0] addr_b, input [7:0] data_in_b, output [7:0] data_out_b, input we_b; [OK]

Hint: Dual-port RAM needs separate signals for each port [OK]

Common Mistakes:

• Using single address and data signals for both ports
• Missing write enable signals
• Confusing read and write signals

3. Given the following Verilog snippet for a dual-port RAM, what will be the value of data_out_b after the clock edge if we_b is 0 and addr_b is 3?

reg [7:0] ram [0:7];
always @(posedge clk) begin
  if (we_a) ram[addr_a] <= data_in_a;
  if (we_b) ram[addr_b] <= data_in_b;
  data_out_a <= ram[addr_a];
  data_out_b <= ram[addr_b];
end

medium

A. The value of data_in_b.

B. The value stored at address 3 before the clock edge.

C. Zero, because we_b is 0.

D. Undefined, because data_out_b is not assigned.

Solution

1. Step 1: Understand write enable effect

   Since we_b is 0, no write occurs at addr_b on this clock edge.

2. Step 2: Determine data_out_b value

   data_out_b reads the RAM at addr_b, so it outputs the stored value at address 3 before the clock edge.

3. Final Answer:

   The value stored at address 3 before the clock edge. -> Option B

4. Quick Check:

   we_b=0 means no write; output = stored value [OK]

Hint: If write enable is 0, output shows stored memory value [OK]

Common Mistakes:

• Assuming data_out_b equals data_in_b always
• Thinking output is zero when no write
• Ignoring read operation on clock edge

4. Identify the error in this dual-port RAM Verilog code snippet:

reg [7:0] ram [0:15];
always @(posedge clk) begin
  if (we_a) ram[addr_a] <= data_in_a;
  if (we_b) ram[addr_b] <= data_in_b;
  data_out_a <= ram[addr_a];
  data_out_b <= ram[addr_b];
end

assign data_out_a = ram[addr_a];

medium

A. Conflicting assignments to data_out_a: both procedural and continuous.

B. Missing clock signal in sensitivity list.

C. Incorrect RAM size declaration.

D. No write enable signals declared.

Solution

1. Step 1: Check assignments to data_out_a

   Data_out_a is assigned inside the always block and also by continuous assign statement, causing conflict.

2. Step 2: Understand Verilog rules

   A signal cannot be driven by both procedural and continuous assignments simultaneously.

3. Final Answer:

   Conflicting assignments to data_out_a: both procedural and continuous. -> Option A

4. Quick Check:

   Signal driven twice = conflict error [OK]

Hint: Avoid assigning same signal in always block and assign statement [OK]

Common Mistakes:

• Ignoring multiple drivers on one signal
• Thinking sensitivity list needs clock and addr
• Misunderstanding RAM size syntax

5. You want to design a dual-port RAM where Port A is write-only and Port B is read-only. Which modification correctly implements this behavior in Verilog?

hard

A. Disable clock on Port B to make it read-only.

B. Use write enable on both ports and read data from both ports.

C. Use write enable only on Port A and never write on Port B; read data only from Port B.

D. Use a single write enable for both ports.

Solution

1. Step 1: Define port roles

   Port A should only write data, so it needs a write enable and no read output.

2. Step 2: Configure Port B as read-only

   Port B should not write, so write enable is never asserted; it only reads data from RAM.

3. Final Answer:

   Use write enable only on Port A and never write on Port B; read data only from Port B. -> Option C

4. Quick Check:

   Write-only Port A + Read-only Port B = Use write enable only on Port A and never write on Port B; read data only from Port B. [OK]

Hint: Assign write enable only to write port, read from the other [OK]

Common Mistakes:

• Trying to write on both ports
• Disabling clock to control read/write
• Using single write enable for both ports