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?"