The Rent Is Due in Kilowatts

1 / 1

View past submissions Leaderboard

Back to submissions

Submission #1

PASSED

RankingPercentile

Latency

0.50 (1 cycles)ns

1st

top 1%

Throughput (ranked)

1996.01 (100.0%)MHz

1st

top 1%

Throughput (visible)

1996.01 (100.0%)MHz

—

top —%

Fmax

1996.01MHz

—

top —%

Area

123μ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 [4-1:0] i_payload_requests,
  input wire [4-1:0] i_payload_limit,
  output wire [4-1:0] o_payload,
  output wire o_valid
);


////////////////////////////////////////////////////////////////////////////////
// naming:
// r = i_payload_request
// l = i_payload_limit
// g = o_payload (grant)
//
////////////////////////////////////////////////////////////////////////////////
//
// key insights:
// k >= 8 when k is between 8 and 15.
// 8 > k when k is between 0 and 7.
//
// these look silly, but they're actually important due to the binary
// encodings.
//
// the first line looks at v[3] = 1.  this happens for v in the set:
// {1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111} which is the set
// of values from 8 to 15.  thus it is possible to determine that v >= 8
// by only looking at the first bit. this is relevant when deciding if
// g[3] should be set based only on r[3] && l[3].  no lower bits matter.
// it's possible the limit is even higher, but that doesn't change anything.
//
// the second line also looks at v[3] = 1.  in this case, image l[3] = 1
// and r[3] = 0.  in that case, there is at least a limit of 8 left over
// after looking at r[3].  with 8 limit (or more), we can just grant any
// request with lower index.  eg, if r = 0111 and l = 1000, we grant g = 0111.
//
// and this logic also works when l[2] = 1 and r[2] = 0 -- r[1] and r[2]
// can be granted without even considering l[1] or l[0].
//
// it's clear that there's extra limit:
//   x = {1'b0, (l[3:1] & ~r[3:1])
//
// where I've shifted the "extra" down one bit.  this ends up making the
// code easier later.  basically, l[0] & !r[0] isn't ever going to be used.
// it's the rightmost bit and if that credit of 1 is extra due to r[0]
// being false, there's just nothing else that can make use of it.
//
// the logic for granting bit location i is then true when:
//   g[i] = r[i] && (l[i] || |x[3:i])
//
// that sequence of |x[3:i] is a "prefix" structure and has multiple
// implementations.  we can define one version as:
//   p = {|x[3:3], |x[3:2], |x[3:1], |x[3:0]}
// (where x[3] has a value of 0 and isn't based on r[3]/l[3])
//
// with this prefix structure we have:
//   g = r & (l | p)
//
////////////////////////////////////////////////////////////////////////////////
//
// there are a wide range of prefix structures.  not so much at size=4 though.
// but you have the simple and confusingly but concise:
//   p = {x[3], x[2:0] | p[3:1]}
//
// which is a chain implementation.  since:
//   p[3] = x[3]
//   p[2] = x[2] | p[3]
//   p[1] = x[1] | p[2]
//   p[0] = x[0] | p[1]
// 
// IMO, it's not that readable in the vector version, but is interesting.
//
// at size=4, the tree-based versions don't have much difference. but I'll
// show some anyways:
//
//   l1 = {x[3], |x[3:2], |x[2:1], |x[1:0]}
//   p = {l1[3], l1[2], l1[3] || l1[1], l1[2] || l1[0]}
//
// this implies l1 has 3 or gates, p has 2, and the max or-depth is 2.  the
// fanout on l1 is {2,2,1,1}
//
//   l1 = {x[3], |x[3:2], x[1], |x[1:0]}
//   p = {l1[3], l1[2], l1[2] || l1[1], l1[2] || l1[0]}
//
// which has a depth of 2, 4 gates, and fanouts on l1 of {1,3,1,1}.
//
// and it's possible to have p use other bits of p in the definition as in the
// chain version.  this makes more sense with size >= 8.
//
////////////////////////////////////////////////////////////////////////////////

wire [3:0] extra = {1'b0, i_payload_limit[3:1] & ~i_payload_requests[3:1]};
wire [3:0] layer1 = {extra[3], |extra[3:2], extra[1], |extra[1:0]};
wire [3:0] prefix = {layer1[3], layer1[2], |layer1[2:1], layer1[2] || layer1[0]};
assign i_ready = 1'b1;
assign o_payload = i_payload_requests & (i_payload_limit | prefix);
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 [4-1:0] i_payload_requests,
  input wire [4-1:0] i_payload_limit,
  output wire [4-1:0] o_payload,
  output wire o_valid
);


////////////////////////////////////////////////////////////////////////////////
// naming:
// r = i_payload_request
// l = i_payload_limit
// g = o_payload (grant)
//
////////////////////////////////////////////////////////////////////////////////
//
// key insights:
// k >= 8 when k is between 8 and 15.
// 8 > k when k is between 0 and 7.
//
// these look silly, but they're actually important due to the binary
// encodings.
//
// the first line looks at v[3] = 1.  this happens for v in the set:
// {1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111} which is the set
// of values from 8 to 15.  thus it is possible to determine that v >= 8
// by only looking at the first bit. this is relevant when deciding if
// g[3] should be set based only on r[3] && l[3].  no lower bits matter.
// it's possible the limit is even higher, but that doesn't change anything.
//
// the second line also looks at v[3] = 1.  in this case, image l[3] = 1
// and r[3] = 0.  in that case, there is at least a limit of 8 left over
// after looking at r[3].  with 8 limit (or more), we can just grant any
// request with lower index.  eg, if r = 0111 and l = 1000, we grant g = 0111.
//
// and this logic also works when l[2] = 1 and r[2] = 0 -- r[1] and r[2]
// can be granted without even considering l[1] or l[0].
//
// it's clear that there's extra limit:
//   x = {1'b0, (l[3:1] & ~r[3:1])
//
// where I've shifted the "extra" down one bit.  this ends up making the
// code easier later.  basically, l[0] & !r[0] isn't ever going to be used.
// it's the rightmost bit and if that credit of 1 is extra due to r[0]
// being false, there's just nothing else that can make use of it.
//
// the logic for granting bit location i is then true when:
//   g[i] = r[i] && (l[i] || |x[3:i])
//
// that sequence of |x[3:i] is a "prefix" structure and has multiple
// implementations.  we can define one version as:
//   p = {|x[3:3], |x[3:2], |x[3:1], |x[3:0]}
// (where x[3] has a value of 0 and isn't based on r[3]/l[3])
//
// with this prefix structure we have:
//   g = r & (l | p)
//
////////////////////////////////////////////////////////////////////////////////
//
// there are a wide range of prefix structures.  not so much at size=4 though.
// but you have the simple and confusingly but concise:
//   p = {x[3], x[2:0] | p[3:1]}
//
// which is a chain implementation.  since:
//   p[3] = x[3]
//   p[2] = x[2] | p[3]
//   p[1] = x[1] | p[2]
//   p[0] = x[0] | p[1]
// 
// IMO, it's not that readable in the vector version, but is interesting.
//
// at size=4, the tree-based versions don't have much difference. but I'll
// show some anyways:
//
//   l1 = {x[3], |x[3:2], |x[2:1], |x[1:0]}
//   p = {l1[3], l1[2], l1[3] || l1[1], l1[2] || l1[0]}
//
// this implies l1 has 3 or gates, p has 2, and the max or-depth is 2.  the
// fanout on l1 is {2,2,1,1}
//
//   l1 = {x[3], |x[3:2], x[1], |x[1:0]}
//   p = {l1[3], l1[2], l1[2] || l1[1], l1[2] || l1[0]}
//
// which has a depth of 2, 4 gates, and fanouts on l1 of {1,3,1,1}.
//
// and it's possible to have p use other bits of p in the definition as in the
// chain version.  this makes more sense with size >= 8.
//
////////////////////////////////////////////////////////////////////////////////

wire [3:0] extra = {1'b0, i_payload_limit[3:1] & ~i_payload_requests[3:1]};
wire [3:0] layer1 = {extra[3], |extra[3:2], extra[1], |extra[1:0]};
wire [3:0] prefix = {layer1[3], layer1[2], |layer1[2:1], layer1[2] || layer1[0]};
assign i_ready = 1'b1;
assign o_payload = i_payload_requests & (i_payload_limit | prefix);
assign o_valid = i_valid;

endmodule

Timing Analysis

Path 1-0.504 ns

From: i_payload_requests[3]

To: o_payload[0]

Data Arrival: 0.505 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`i_payload_requests[3]`
0.000	sky130_fd_sc_hvl__inv_1	`$abc$122$auto$blifparse.cc:396:parse_blif$123/A`
0.093	sky130_fd_sc_hvl__inv_1	`$abc$122$auto$blifparse.cc:396:parse_blif$123/Y`
0.093	sky130_fd_sc_hvl__a22oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$128/A1`
0.368	sky130_fd_sc_hvl__a22oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$128/Y`
0.368	sky130_fd_sc_hvl__a21oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$130/A1`
0.505	sky130_fd_sc_hvl__a21oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$130/Y`
0.505	Solution	`o_payload[0]`

Path 2-0.495 ns

From: i_payload_requests[3]

To: o_payload[1]

Data Arrival: 0.496 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`i_payload_requests[3]`
0.000	sky130_fd_sc_hvl__inv_1	`$abc$122$auto$blifparse.cc:396:parse_blif$123/A`
0.093	sky130_fd_sc_hvl__inv_1	`$abc$122$auto$blifparse.cc:396:parse_blif$123/Y`
0.093	sky130_fd_sc_hvl__a22oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$128/A1`
0.368	sky130_fd_sc_hvl__a22oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$128/Y`
0.368	sky130_fd_sc_hvl__a21oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$131/A2`
0.496	sky130_fd_sc_hvl__a21oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$131/Y`
0.496	Solution	`o_payload[1]`

Path 3-0.327 ns

From: i_payload_requests[3]

To: o_payload[2]

Data Arrival: 0.328 ns

Arrival (ns)	Cell	Pin
0.000	Solution	`i_payload_requests[3]`
0.000	sky130_fd_sc_hvl__inv_1	`$abc$122$auto$blifparse.cc:396:parse_blif$123/A`
0.093	sky130_fd_sc_hvl__inv_1	`$abc$122$auto$blifparse.cc:396:parse_blif$123/Y`
0.093	sky130_fd_sc_hvl__a21oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$132/A1`
0.274	sky130_fd_sc_hvl__a21oi_1	`$abc$122$auto$blifparse.cc:396:parse_blif$132/Y`
0.274	sky130_fd_sc_hvl__nor2_1	`$abc$122$auto$blifparse.cc:396:parse_blif$133/B`
0.328	sky130_fd_sc_hvl__nor2_1	`$abc$122$auto$blifparse.cc:396:parse_blif$133/Y`
0.328	Solution	`o_payload[2]`

Post-Synthesis Verilog

Download synth.v