Keep every route of a source-routed 4 x 4 crossbar and bring it from 295 cells under a budget of 215.
Hardware context: A source-routed 4 x 4 crossbar of 8-bit words in which the lowest-numbered input wins a contested output. Bring the correct 295-cell crossbar under its 215-cell budget without changing a route.
A small switch carries 8-bit words from four inputs to four outputs. Each input names the output it wants. When two inputs want the same output, the lower-numbered input wins. The other sees its grant stay 0 and tries again later.
The design below is correct. It measures 295 cells on this flow, and the block has room for 215. This is an Optimize problem: make it fit without changing a single route or grant. The tests apply every pattern of valid bits and destinations.
Brief: combinational. Output j shows the word of the lowest-numbered valid input whose dest is j. out_valid[j] is 1 if there is one. grant[i] is 1 when input i is valid and its word is the one on its output. The word on an output whose out_valid is 0 is not checked. Synthesis check: the design must build on the site's synthesis flow with no latch. The cell and level counts come from an open-source flow and are a proxy for area and depth, not a foundry result.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
script | 88 | input of each check |
Full specification
module xbar4 (
input logic [3:0] in_valid, // input i has a word
input logic [3:0][1:0] dest, // the output input i asks for
input logic [3:0][7:0] in,
output logic [3:0] grant, // input i reached its output
output logic [3:0] out_valid, // output j shows a word
output logic [3:0][7:0] out
);
// your design
endmodule
| Item | This design |
|---|---|
| route | out[j] = in[i] for the lowest i with in_valid[i] = 1 and dest[i] = j |
| out_valid[j] | 1 when at least one valid input asks for output j |
| grant[i] | 1 when input i is valid and no lower-numbered valid input asks for the same output |
| idle output | out[j] may be anything while out_valid[j] is 0 |
| budget | cells on the pinned synthesis flow at or under 215 (the reference measures 200, the shipped design 295) |
Most tests apply two patterns and show grant, out_valid and the four output words for each. Three tests apply all 4096 patterns of in_valid and dest and report a checksum of everything the outputs showed.
Examples
Example 1
Straight Through, Then Reversed- Input
in0=11->out0, in1=22->out1, in2=33->out2, in3=44->out3; then in0=11->out3, in1=22->out2, in2=33->out1, in3=44->out0
- Output
grant_pattern0 = 'b1111, out_valid_pattern0 = 'b1111, out_pattern0 = 0x44332211, grant_pattern1 = 'b1111, out_valid_pattern1 = 'b1111, out_pattern1 = 0x11223344
No two inputs share an output, so all four are granted. Reversed, output 0 shows the word of input 3.
Example 2
Two Inputs Ask for One Output- Input
in0=11->out2, in1=22->out2, in2 idle, in3 idle; then in0 idle, in1=22->out1, in2 idle, in3=44->out1
- Output
grant_pattern0 = 'b0001, out_valid_pattern0 = 'b0100, out_pattern0 = 0x110000, grant_pattern1 = 'b0010, out_valid_pattern1 = 'b0010, out_pattern1 = 0x2200
Inputs 0 and 1 both name output 2. Input 0 wins: grant is 0001 and output 2 shows 11. In the second pattern inputs 1 and 3 both name output 1, and input 1 wins.
Example 3
All Four Ask for Output 3- Input
in0=11->out3, in1=22->out3, in2=33->out3, in3=44->out3; then in0 idle, in1 idle, in2=33->out1, in3 idle
- Output
grant_pattern0 = 'b0001, out_valid_pattern0 = 'b1000, out_pattern0 = 0x11000000, grant_pattern1 = 'b0100, out_valid_pattern1 = 'b0010, out_pattern1 = 0x3300
Only input 0 is granted. In the second pattern the idle inputs name output 3 as well, and they do not count: input 2 reaches output 1.
Constraints and Contract
- Inputs are known 0/1 values. dest[i] may hold any value while in_valid[i] is 0.
- Keep the module name and the ports. The design stays combinational.
Hints
Hint 1
Synthesize the shipped design and read the cell types. Then price the part you cannot avoid: four 4:1 muxes of 8 bits. Lesson R5.5 measured what that costs.
Hint 2
The shipped design builds each output word with ANDs and ORs, and it settles the conflicts input by input. Ask what each output needs to know to drive a plain mux.
Hint 3
Per output, find the number of the winning input once. Use it as the select of the mux, and use it again to answer each input's grant. Read the brief on idle outputs before you clear them.
What the grader checks: Six directed and twelve seeded pairs of patterns are compared field by field with an independent model. Three sweeps apply all 4096 patterns of in_valid and dest with fixed words. Each compares a checksum of grant, out_valid and the valid output words, so every routing pattern is checked. The synthesis check then counts cells.
The submitted design must synthesize with 0 latches and no combinational loop. It must use at most 215 cells; a result equal to the limit passes. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.
21 checks on Icarus Verilog + Yosys · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 1 steps and the final capstone