Parallel Prefix Sum

1 / 1

View past submissions Leaderboard

Back to submissions

Submission #1

PASSED

RankingPercentile

Latency

—

top —%

Throughput

—

top —%

Area

—

top —%

Score

—

top —%

Submitted Solution

// Stream-based solution component
//
// Input stream interface:
//   i_ready (output): Assert when ready to accept input
//   i_valid (input): Asserted when input data is valid
//   i_payload_* (input): Input payload fields
//
// Output interface:
//   o_valid (output): Assert when output data is valid
//   o_payload* (output): Output payload fields
//
// Handshaking: Data transfers when both ready and valid are high

module Solution (
  input wire clk,
  input wire reset,
  output wire i_ready,
  input wire i_valid,
  input wire [16-1:0] i_payload_array_fragment,
  input wire i_payload_array_last,
  output wire [24-1:0] o_payload_fragment,
  output wire o_payload_last,
  output wire o_valid
);

// Define your design here

// submitting this to show that accumulators can be pipelined.

wire [16-1:0] din = i_payload_array_fragment;

reg  [7:0] high1;
wire [8:0] nx_low1 = {1'b0,acc1} + {1'b0,din[7:0]};
reg  [7:0] low1;
reg  [7:0] acc1;
reg        carry1;
reg        valid1;
reg        last1;

reg  [7:0] high2;
wire [8:0] nx_high2 = {1'b0,acc2} + {1'b0,high1} + carry1;
reg  [7:0] acc2;
reg        carry2;
reg  [7:0] low2;
reg        valid2;
reg        last2;

reg  [7:0] acc3;
wire [7:0] nx_acc3 = acc3 + carry2;

always@(posedge clk) begin
  // pipeline 1
  if (i_valid) begin
    {carry1, low1} <= nx_low1;
    if (!i_payload_array_last) begin
      acc1[7:0] <= nx_low1[7:0];
    end else begin
      acc1[7:0] <= 8'b0;
    end
  end
  high1 <= din[15:8];
  valid1 <= i_valid;
  last1 <= i_payload_array_last;

  // pipeline 2
  if (valid1) begin
    low2 <= low1;
    {carry2,high2} <= nx_high2;
    if (!last1) begin
      acc2 <= nx_high2;
    end else begin
      acc2 <= 8'b0;
    end
  end
  valid2 <= valid1;
  last2 <= last1;

  // pseudo 3
  if (valid2) begin
    if (!last2) begin
      acc3 <= nx_acc3;
    end else begin
      acc3 <= 8'b0;
    end
  end

  // resets
  if (reset) begin
    valid1 <= 0;
    valid2 <= 0;
    acc1 <= 8'b0;
    acc2 <= 8'b0;
    acc3 <= 8'b0;
  end

end

  assign i_ready = 1'b1;

  assign o_payload_fragment = {nx_acc3, high2, low2};
  assign o_valid = valid2;
  assign o_payload_last = last2;

endmodule

Generated Verilog

// Stream-based solution component
//
// Input stream interface:
//   i_ready (output): Assert when ready to accept input
//   i_valid (input): Asserted when input data is valid
//   i_payload_* (input): Input payload fields
//
// Output interface:
//   o_valid (output): Assert when output data is valid
//   o_payload* (output): Output payload fields
//
// Handshaking: Data transfers when both ready and valid are high

module Solution (
  input wire clk,
  input wire reset,
  output wire i_ready,
  input wire i_valid,
  input wire [16-1:0] i_payload_array_fragment,
  input wire i_payload_array_last,
  output wire [24-1:0] o_payload_fragment,
  output wire o_payload_last,
  output wire o_valid
);

// Define your design here

// submitting this to show that accumulators can be pipelined.

wire [16-1:0] din = i_payload_array_fragment;

reg  [7:0] high1;
wire [8:0] nx_low1 = {1'b0,acc1} + {1'b0,din[7:0]};
reg  [7:0] low1;
reg  [7:0] acc1;
reg        carry1;
reg        valid1;
reg        last1;

reg  [7:0] high2;
wire [8:0] nx_high2 = {1'b0,acc2} + {1'b0,high1} + carry1;
reg  [7:0] acc2;
reg        carry2;
reg  [7:0] low2;
reg        valid2;
reg        last2;

reg  [7:0] acc3;
wire [7:0] nx_acc3 = acc3 + carry2;

always@(posedge clk) begin
  // pipeline 1
  if (i_valid) begin
    {carry1, low1} <= nx_low1;
    if (!i_payload_array_last) begin
      acc1[7:0] <= nx_low1[7:0];
    end else begin
      acc1[7:0] <= 8'b0;
    end
  end
  high1 <= din[15:8];
  valid1 <= i_valid;
  last1 <= i_payload_array_last;

  // pipeline 2
  if (valid1) begin
    low2 <= low1;
    {carry2,high2} <= nx_high2;
    if (!last1) begin
      acc2 <= nx_high2;
    end else begin
      acc2 <= 8'b0;
    end
  end
  valid2 <= valid1;
  last2 <= last1;

  // pseudo 3
  if (valid2) begin
    if (!last2) begin
      acc3 <= nx_acc3;
    end else begin
      acc3 <= 8'b0;
    end
  end

  // resets
  if (reset) begin
    valid1 <= 0;
    valid2 <= 0;
    acc1 <= 8'b0;
    acc2 <= 8'b0;
    acc3 <= 8'b0;
  end

end

  assign i_ready = 1'b1;

  assign o_payload_fragment = {nx_acc3, high2, low2};
  assign o_valid = valid2;
  assign o_payload_last = last2;

endmodule

Timing Analysis

Path 1-4.341 ns

From: acc2[0]$_SDFFE_PP0P_/Q

To: high2[7]$_DFFE_PP_/D

Data Arrival: 4.153 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`acc2[0]$_SDFFE_PP0P_/CLK`
0.696	sky130_fd_sc_hvl__dfxtp_1	`acc2[0]$_SDFFE_PP0P_/Q`
0.696	sky130_fd_sc_hvl__xor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$984/A`
1.052	sky130_fd_sc_hvl__xor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$984/X`
1.052	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$989/A2`
1.405	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$989/Y`
1.405	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$997/A1`
1.703	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$997/Y`
1.703	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1007/A1`
2.048	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1007/Y`
2.048	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1015/A1`
2.345	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1015/Y`
2.345	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1024/A1`
2.691	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1024/Y`
2.691	sky130_fd_sc_hvl__a21o_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1036/A1`
3.056	sky130_fd_sc_hvl__a21o_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1036/X`
3.056	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1042/A2`
3.296	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1042/Y`
3.296	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1044/A`
3.630	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1044/Y`
3.630	sky130_fd_sc_hvl__mux2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1060/A1`
4.153	sky130_fd_sc_hvl__mux2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1060/X`
4.153	sky130_fd_sc_hvl__dfxtp_1	`high2[7]$_DFFE_PP_/D`

Path 2-4.159 ns

From: acc2[0]$_SDFFE_PP0P_/Q

To: acc2[7]$_SDFFE_PP0P_/D

Data Arrival: 4.014 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`acc2[0]$_SDFFE_PP0P_/CLK`
0.696	sky130_fd_sc_hvl__dfxtp_1	`acc2[0]$_SDFFE_PP0P_/Q`
0.696	sky130_fd_sc_hvl__xor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$984/A`
1.030	sky130_fd_sc_hvl__xor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$984/X`
1.030	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$989/A2`
1.326	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$989/Y`
1.326	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$997/A1`
1.673	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$997/Y`
1.673	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1007/A1`
1.990	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1007/Y`
1.990	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1015/A1`
2.338	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1015/Y`
2.338	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1024/A1`
2.656	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1024/Y`
2.656	sky130_fd_sc_hvl__a21o_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1036/A1`
3.039	sky130_fd_sc_hvl__a21o_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1036/X`
3.039	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1042/A2`
3.358	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1042/Y`
3.358	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1044/A`
3.636	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1044/Y`
3.636	sky130_fd_sc_hvl__nand3_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1045/C`
3.822	sky130_fd_sc_hvl__nand3_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1045/Y`
3.822	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1046/A2`
4.014	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$1046/Y`
4.014	sky130_fd_sc_hvl__dfxtp_1	`acc2[7]$_SDFFE_PP0P_/D`

Path 3-4.093 ns

From: acc1[1]$_SDFFE_PP0P_/Q

To: acc1[7]$_SDFFE_PP0P_/D

Data Arrival: 3.960 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`acc1[1]$_SDFFE_PP0P_/CLK`
0.710	sky130_fd_sc_hvl__dfxtp_1	`acc1[1]$_SDFFE_PP0P_/Q`
0.710	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$905/A`
1.097	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$905/Y`
1.097	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$911/A2`
1.456	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$911/Y`
1.456	sky130_fd_sc_hvl__a21o_1	`$abc$874$auto$blifparse.cc:396:parse_blif$920/A1`
1.818	sky130_fd_sc_hvl__a21o_1	`$abc$874$auto$blifparse.cc:396:parse_blif$920/X`
1.818	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$930/A1`
2.085	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$930/Y`
2.085	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$938/A1`
2.431	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$938/Y`
2.431	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$948/A1`
2.748	sky130_fd_sc_hvl__a21oi_1	`$abc$874$auto$blifparse.cc:396:parse_blif$948/Y`
2.748	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$957/A1`
3.098	sky130_fd_sc_hvl__o21ai_1	`$abc$874$auto$blifparse.cc:396:parse_blif$957/Y`
3.098	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$959/A`
3.354	sky130_fd_sc_hvl__xnor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$959/Y`
3.354	sky130_fd_sc_hvl__nand2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$960/B`
3.550	sky130_fd_sc_hvl__nand2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$960/Y`
3.550	sky130_fd_sc_hvl__o21a_1	`$abc$874$auto$blifparse.cc:396:parse_blif$961/A2`
3.856	sky130_fd_sc_hvl__o21a_1	`$abc$874$auto$blifparse.cc:396:parse_blif$961/X`
3.856	sky130_fd_sc_hvl__nor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$962/B`
3.960	sky130_fd_sc_hvl__nor2_1	`$abc$874$auto$blifparse.cc:396:parse_blif$962/Y`
3.960	sky130_fd_sc_hvl__dfxtp_1	`acc1[7]$_SDFFE_PP0P_/D`

Post-Synthesis Verilog

Download synth.v