Priority Queue - Latchup

1 / 1

View past submissions Leaderboard

Back to submissions

Submission #6

PASSED

RankingPercentile

Latency

4099.37 (728 cycles)ns

1st

top 1%

Throughput (ranked)

23.68 (13.3%)MHz

1st

top 1%

Throughput (visible)

48.43 (27.3%)MHz

—

top —%

Fmax

177.59MHz

—

top —%

Area

23404μm²

1st

top 1%

Score

100.00

1st

top 1%

Throughput is Fmax × the measured percentage. Rankings use hidden tests; visible tests are unranked feedback.

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_stream_fragment,
  input wire i_payload_stream_last,
  input wire [4-1:0] i_payload_k,
  output wire [16-1:0] o_payload_fragment_fragment,
  output wire o_payload_fragment_last,
  output wire o_payload_last,
  output wire o_valid
);

// this problem has k outputs per input.  this means sub-operations
// can be O(k) -- no need to sort the data in one cycle only to
// wait 14 cycles.
//
// originally, I didn't like this problem for this reason.  I
// started with a basic array structure and O(k) insertion while
// reading data.
//
// the shift register version didn't feel like it would be that
// interesting.  but then I thought about making a variable length
// cycle using two shift registers.
//
// I called this the "racetrack" and it looks like it's the
// intended solution.
//
// I fully embraced the racecar theme.  maybe too much.
//
//  
//     ---+->-+---     in
//    /  /     \  \    |
//  B0  /       \  F0  |
//   | /         \ |  /|
//   |/           \| / |
//   +             +/  |
//   |    wait     +   |
//   |      \      |  / 
//  B1       \-----F1/ 
//   |             |/ 
//   |             + 
//   +     1's ----+  VVV starting line
//   |\           /|\
//   | \         / | \
//  B2  \---<---/  F2 \
//   |             |   \
//   |             |    \
//   +             |     out
//   |\           /|
//   | \         / |
//  B3  \---<---/  F3
//   |             |
//   |             |
//   +             |
//   |\           /|
//   | \         / |
//  Bn  \---<---/  Fn
//    \           / 
//     \         /  
//      \---<---/    
//
//
// this design assumes k is constant for a sequence of i_valid.
// (if this is not the case, change the bypass logic)

// racetrack (data) declarations
// names are that of output values.  eg bypass[3] is the mux of
// b[3] or f[2].  vs naming based on inputs.
logic [15:0] f [0:7];
logic [15:0] b [7:0];
logic [15:0] b0_if_odd;
logic [15:0] f0_if_entered;
logic [15:0] f0_if_long;
logic [15:0] f1_if_cycling;
logic [15:0] f1_if_qualified;
logic [15:0] bypass [7:2];

// control declaratins
logic [4-1:0] k;
logic short_track;
logic [15:0] entering_car;
logic first_car;
logic last_car;
logic first_lap;
logic last_lap;
logic [3:0] next_cnt;
logic [3:0] cnt;
logic entering;
logic entered;

// combinatorials
always_comb begin
  // convenience
  k = i_payload_k;
  entering_car = i_payload_stream_fragment;
  last_lap = i_payload_stream_last;

  // next state
  first_car = (cnt & 4'b1110) == 4'b0; // cnt starts <= 1
  next_cnt = (first_car) ? k : (cnt - 1);
  // first_lap doesn't need first_car due to !entered forcing it to
  // apply only to first car.
  entering = ((entering_car < f[1]) || first_lap) && !entered;

  // comb outputs
  short_track = (k & 4'b1110) == 4'b0;
  last_car = (next_cnt & 4'b1110) == 4'b0;
end

// state registers
always@(posedge clk) begin
  if (i_valid) begin
    cnt <= next_cnt;
    // set to 1 after last car of last lap.  
    // only changes at lap boundaries.
    if (last_car) begin
      first_lap <= last_lap;
    end
    // set to 0 after end of lap.  set to 1 after car enters.
    if (last_car) begin
      entered <= 1'b0;
    end else if (entering) begin
      entered <= 1'b1;
    end
  end
  // these controls actually do need resets
  if (reset) begin
    cnt <= 4'b0;
    first_lap <= 1'b1;
    entered <= 1'b0;
  end
end

// racetrack muxes!
always_comb begin
  // if cycle is odd length, include b[0], else bypass
  b0_if_odd = k[0] ? b[0] : b[1];

  // if a car entered this lap, the others get backed up by one place.
  // then last car is cut off at end of lap.
  f0_if_entered = (entered && !last_car) ? f[0] : b0_if_odd;

  // if track is too short, must change entry point.
  f0_if_long = (!short_track) ? f0_if_entered : entering_car;

  // either let new car enter here or take the f1 place.
  f1_if_cycling = (!entering) ? f[1] : entering_car;

  // during the first lap, disqualify everything except first car
  // which will be selected previously by f1_if_cycling.
  f1_if_qualified = (!first_lap || first_car) ? f1_if_cycling : 16'hFFFF;

  // forward path doesn't have any additional muxes.
  // round the corner!
  //
  // (b[7]'s input always comes from f[7], for k = 14,15)
  //
  // logic map for mux selects.
  // some muxes can be selected if previous mux handles the cycle.
  //
  //      bl2 bl3 bl4 bl5 bl6 bl7 bl8
  // 0000   1   X   X   X   X   X   X
  // 0001   1   X   X   X   X   X   X
  // 0010   1       X       X       X
  // 0011   1       X       X       X
  // 0100       1   X           X   X
  // 0101       1   X           X   X
  // 0110           1               X
  // 0111           1               X
  // 1000               1   X   X   X
  // 1001               1   X   X   X
  // 1010                   1       X
  // 1011                   1       X
  // 1100                       1   X
  // 1101                       1   X
  // 1110                           1
  // 1111                           1
  bypass[7] = ((k & 4'b0010) == 4'b0) ? f[6]            : b[7];
  bypass[6] = ((k & 4'b0100) == 4'b0) ? f[5]            : b[6];
  bypass[5] = ((k & 4'b0110) == 4'b0) ? f[4]            : b[5];
  bypass[4] = ((k & 4'b1000) == 4'b0) ? f[3]            : b[4];
  bypass[3] = ((k & 4'b1010) == 4'b0) ? f[2]            : b[3];
  bypass[2] = ((k & 4'b1100) == 4'b0) ? f1_if_qualified : b[2];
end

// racetrack registers!
always@(posedge clk) begin
  if (i_valid) begin
    f[0] <= b0_if_odd;
    if (short_track ? entering : (last_car || !entering)) begin
      f[1] <= f0_if_long;
    end
    f[2] <= f1_if_qualified; // START!!!
    f[3] <= f[2];
    f[4] <= f[3];
    f[5] <= f[4];
    f[6] <= f[5];
    f[7] <= f[6];
    b[7] <= f[7]; // round the corner!
    b[6] <= bypass[7];
    b[5] <= bypass[6];
    b[4] <= bypass[5];
    b[3] <= bypass[4];
    b[2] <= bypass[3];
    b[1] <= bypass[2];
    b[0] <= b[1];
  end
  // needed for "entering"
  if (reset) begin
    f[1] <= 16'hFFFF;
  end
end

// outputs
assign i_ready = last_car;
assign o_payload_fragment_fragment = f1_if_qualified;
assign o_payload_fragment_last = last_car;
assign o_payload_last = last_lap && last_car;
assign o_valid = i_valid;

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_stream_fragment,
  input wire i_payload_stream_last,
  input wire [4-1:0] i_payload_k,
  output wire [16-1:0] o_payload_fragment_fragment,
  output wire o_payload_fragment_last,
  output wire o_payload_last,
  output wire o_valid
);

// this problem has k outputs per input.  this means sub-operations
// can be O(k) -- no need to sort the data in one cycle only to
// wait 14 cycles.
//
// originally, I didn't like this problem for this reason.  I
// started with a basic array structure and O(k) insertion while
// reading data.
//
// the shift register version didn't feel like it would be that
// interesting.  but then I thought about making a variable length
// cycle using two shift registers.
//
// I called this the "racetrack" and it looks like it's the
// intended solution.
//
// I fully embraced the racecar theme.  maybe too much.
//
//  
//     ---+->-+---     in
//    /  /     \  \    |
//  B0  /       \  F0  |
//   | /         \ |  /|
//   |/           \| / |
//   +             +/  |
//   |    wait     +   |
//   |      \      |  / 
//  B1       \-----F1/ 
//   |             |/ 
//   |             + 
//   +     1's ----+  VVV starting line
//   |\           /|\
//   | \         / | \
//  B2  \---<---/  F2 \
//   |             |   \
//   |             |    \
//   +             |     out
//   |\           /|
//   | \         / |
//  B3  \---<---/  F3
//   |             |
//   |             |
//   +             |
//   |\           /|
//   | \         / |
//  Bn  \---<---/  Fn
//    \           / 
//     \         /  
//      \---<---/    
//
//
// this design assumes k is constant for a sequence of i_valid.
// (if this is not the case, change the bypass logic)

// racetrack (data) declarations
// names are that of output values.  eg bypass[3] is the mux of
// b[3] or f[2].  vs naming based on inputs.
logic [15:0] f [0:7];
logic [15:0] b [7:0];
logic [15:0] b0_if_odd;
logic [15:0] f0_if_entered;
logic [15:0] f0_if_long;
logic [15:0] f1_if_cycling;
logic [15:0] f1_if_qualified;
logic [15:0] bypass [7:2];

// control declaratins
logic [4-1:0] k;
logic short_track;
logic [15:0] entering_car;
logic first_car;
logic last_car;
logic first_lap;
logic last_lap;
logic [3:0] next_cnt;
logic [3:0] cnt;
logic entering;
logic entered;

// combinatorials
always_comb begin
  // convenience
  k = i_payload_k;
  entering_car = i_payload_stream_fragment;
  last_lap = i_payload_stream_last;

  // next state
  first_car = (cnt & 4'b1110) == 4'b0; // cnt starts <= 1
  next_cnt = (first_car) ? k : (cnt - 1);
  // first_lap doesn't need first_car due to !entered forcing it to
  // apply only to first car.
  entering = ((entering_car < f[1]) || first_lap) && !entered;

  // comb outputs
  short_track = (k & 4'b1110) == 4'b0;
  last_car = (next_cnt & 4'b1110) == 4'b0;
end

// state registers
always@(posedge clk) begin
  if (i_valid) begin
    cnt <= next_cnt;
    // set to 1 after last car of last lap.  
    // only changes at lap boundaries.
    if (last_car) begin
      first_lap <= last_lap;
    end
    // set to 0 after end of lap.  set to 1 after car enters.
    if (last_car) begin
      entered <= 1'b0;
    end else if (entering) begin
      entered <= 1'b1;
    end
  end
  // these controls actually do need resets
  if (reset) begin
    cnt <= 4'b0;
    first_lap <= 1'b1;
    entered <= 1'b0;
  end
end

// racetrack muxes!
always_comb begin
  // if cycle is odd length, include b[0], else bypass
  b0_if_odd = k[0] ? b[0] : b[1];

  // if a car entered this lap, the others get backed up by one place.
  // then last car is cut off at end of lap.
  f0_if_entered = (entered && !last_car) ? f[0] : b0_if_odd;

  // if track is too short, must change entry point.
  f0_if_long = (!short_track) ? f0_if_entered : entering_car;

  // either let new car enter here or take the f1 place.
  f1_if_cycling = (!entering) ? f[1] : entering_car;

  // during the first lap, disqualify everything except first car
  // which will be selected previously by f1_if_cycling.
  f1_if_qualified = (!first_lap || first_car) ? f1_if_cycling : 16'hFFFF;

  // forward path doesn't have any additional muxes.
  // round the corner!
  //
  // (b[7]'s input always comes from f[7], for k = 14,15)
  //
  // logic map for mux selects.
  // some muxes can be selected if previous mux handles the cycle.
  //
  //      bl2 bl3 bl4 bl5 bl6 bl7 bl8
  // 0000   1   X   X   X   X   X   X
  // 0001   1   X   X   X   X   X   X
  // 0010   1       X       X       X
  // 0011   1       X       X       X
  // 0100       1   X           X   X
  // 0101       1   X           X   X
  // 0110           1               X
  // 0111           1               X
  // 1000               1   X   X   X
  // 1001               1   X   X   X
  // 1010                   1       X
  // 1011                   1       X
  // 1100                       1   X
  // 1101                       1   X
  // 1110                           1
  // 1111                           1
  bypass[7] = ((k & 4'b0010) == 4'b0) ? f[6]            : b[7];
  bypass[6] = ((k & 4'b0100) == 4'b0) ? f[5]            : b[6];
  bypass[5] = ((k & 4'b0110) == 4'b0) ? f[4]            : b[5];
  bypass[4] = ((k & 4'b1000) == 4'b0) ? f[3]            : b[4];
  bypass[3] = ((k & 4'b1010) == 4'b0) ? f[2]            : b[3];
  bypass[2] = ((k & 4'b1100) == 4'b0) ? f1_if_qualified : b[2];
end

// racetrack registers!
always@(posedge clk) begin
  if (i_valid) begin
    f[0] <= b0_if_odd;
    if (short_track ? entering : (last_car || !entering)) begin
      f[1] <= f0_if_long;
    end
    f[2] <= f1_if_qualified; // START!!!
    f[3] <= f[2];
    f[4] <= f[3];
    f[5] <= f[4];
    f[6] <= f[5];
    f[7] <= f[6];
    b[7] <= f[7]; // round the corner!
    b[6] <= bypass[7];
    b[5] <= bypass[6];
    b[4] <= bypass[5];
    b[3] <= bypass[4];
    b[2] <= bypass[3];
    b[1] <= bypass[2];
    b[0] <= b[1];
  end
  // needed for "entering"
  if (reset) begin
    f[1] <= 16'hFFFF;
  end
end

// outputs
assign i_ready = last_car;
assign o_payload_fragment_fragment = f1_if_qualified;
assign o_payload_fragment_last = last_car;
assign o_payload_last = last_lap && last_car;
assign o_valid = i_valid;

endmodule

Timing Analysis

Path 1-5.634 ns

From: cnt[1]$_SDFFE_PP0P_/Q

To: f[1][0]$_SDFFE_PP1P_/D

Data Arrival: 5.453 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`cnt[1]$_SDFFE_PP0P_/CLK`
0.779	sky130_fd_sc_hvl__dfxtp_1	`cnt[1]$_SDFFE_PP0P_/Q`
0.779	sky130_fd_sc_hvl__nor3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1915/C`
1.480	sky130_fd_sc_hvl__nor3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1915/Y`
1.480	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1922/S`
1.768	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1922/X`
1.768	sky130_fd_sc_hvl__inv_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1923/A`
1.868	sky130_fd_sc_hvl__inv_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1923/Y`
1.868	sky130_fd_sc_hvl__and3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1924/C`
2.286	sky130_fd_sc_hvl__and3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1924/X`
2.286	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2017/B`
3.349	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2017/X`
3.349	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2019/S`
4.030	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2019/X`
4.030	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2020/A0`
4.539	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2020/X`
4.539	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2021/A0`
5.043	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2021/X`
5.043	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2022/B`
5.453	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2022/X`
5.453	sky130_fd_sc_hvl__dfxtp_1	`f[1][0]$_SDFFE_PP1P_/D`

Path 2-5.634 ns

From: cnt[1]$_SDFFE_PP0P_/Q

To: f[1][10]$_SDFFE_PP1P_/D

Data Arrival: 5.453 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`cnt[1]$_SDFFE_PP0P_/CLK`
0.779	sky130_fd_sc_hvl__dfxtp_1	`cnt[1]$_SDFFE_PP0P_/Q`
0.779	sky130_fd_sc_hvl__nor3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1915/C`
1.480	sky130_fd_sc_hvl__nor3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1915/Y`
1.480	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1922/S`
1.768	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1922/X`
1.768	sky130_fd_sc_hvl__inv_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1923/A`
1.868	sky130_fd_sc_hvl__inv_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1923/Y`
1.868	sky130_fd_sc_hvl__and3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1924/C`
2.286	sky130_fd_sc_hvl__and3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1924/X`
2.286	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2017/B`
3.349	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2017/X`
3.349	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2069/S`
4.030	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2069/X`
4.030	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2070/A0`
4.539	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2070/X`
4.539	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2071/A0`
5.043	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2071/X`
5.043	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2072/B`
5.453	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2072/X`
5.453	sky130_fd_sc_hvl__dfxtp_1	`f[1][10]$_SDFFE_PP1P_/D`

Path 3-5.634 ns

From: cnt[1]$_SDFFE_PP0P_/Q

To: f[1][11]$_SDFFE_PP1P_/D

Data Arrival: 5.453 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`clk`
0.000	sky130_fd_sc_hvl__dfxtp_1	`cnt[1]$_SDFFE_PP0P_/CLK`
0.779	sky130_fd_sc_hvl__dfxtp_1	`cnt[1]$_SDFFE_PP0P_/Q`
0.779	sky130_fd_sc_hvl__nor3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1915/C`
1.480	sky130_fd_sc_hvl__nor3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1915/Y`
1.480	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1922/S`
1.768	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1922/X`
1.768	sky130_fd_sc_hvl__inv_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1923/A`
1.868	sky130_fd_sc_hvl__inv_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1923/Y`
1.868	sky130_fd_sc_hvl__and3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1924/C`
2.286	sky130_fd_sc_hvl__and3_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$1924/X`
2.286	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2017/B`
3.349	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2017/X`
3.349	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2074/S`
4.030	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2074/X`
4.030	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2075/A0`
4.539	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2075/X`
4.539	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2076/A0`
5.043	sky130_fd_sc_hvl__mux2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2076/X`
5.043	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2077/B`
5.453	sky130_fd_sc_hvl__or2_1	`$abc$1874$auto$blifparse.cc:396:parse_blif$2077/X`
5.453	sky130_fd_sc_hvl__dfxtp_1	`f[1][11]$_SDFFE_PP1P_/D`

Post-Synthesis Verilog

Download synth.v