A3.1.2 Prove the Grant Comes

HardVerify35 minSymbiYosys · serverReview the topic

Problem

Description

State "every waiting request is granted" as a bound. A formal engine proves it on a fair arbiter and refutes it on three faulty ones.

A two-requester arbiter grants one requester per edge, with registered grants g0 and g1. A requester holds its request until it is granted. When both wait, the arbiter alternates, so no waiting request waits more than two edges.

Write the assertions. The engine must prove them on the correct arbiter and find a counterexample on each of three hidden faulty arbiters.

Pinned interface
PortDirectionBits
clkinput1
rstinput1
r0input1
r1input1
g0output1
g1output1
Full specification
PortDirectionMeaning
clkinputthe clock; every check is sampled at its rising edge
rstinputhigh in the first state only, then low (judge-owned)
r0, r1inputrequest levels; a waiting request (r && !g) is held until granted (judge-owned assumption)
g0, g1outputregistered grants, one per edge at most

A request is waiting at an edge where r0 is 1 and g0 is 0 (the same for r1 and g1). A request raised on its own grant edge is a new request, and the requester may drop it at once.

A formal engine reasons about every infinite run, and has no end of test. A weak wait such as ##[1:$] can never fail there. This judge proves safety properties only: unbounded ranges and s_eventually are outside its subset. State the guarantee as a bound.

Submit assert property lines on the pinned ports. The judge proves them on the correct arbiter and checks that they imply its own two obligations. Then it runs bounded model checking on the hidden arbiters. A resource limit or an unresolved proof is inconclusive, never a rated miss.

Measured Counterexample

FAIL · bmc · depth 12 · smtbmc yices · 513 ms

This measured failing run uses the published interface. Follow the sampled violation back to the preceding inputs and state. The worked solution below explains the required behaviour and the failure mechanisms.

Recorded solver trace
01234clkfreerstfreer0freer1g0g1sampled violation
Scroll horizontally ↔

Samples from the measured run. Free input lanes are shaded; the terminal VCD record is omitted.

The measured run is on a hidden faulty arbiter. A request is held, waiting, and its grant has not come two edges later: the bounded response fails at a finite step, so a bound turns "the grant comes" into a property with a finite counterexample.

Requirements

  • Use the published ports. Assumptions on the requests are judge-owned; do not add your own.
  • Submit assertions only: one or more assert property lines.

Hints

Hint 1

Which edges start an attempt: every edge with r0, or only an edge where a request is still waiting?

Hint 2

How long can a waiting request wait when both requesters keep asking?

Hint 3

A fair arbiter must be fair to both requesters.

Single clock, binary values, reset in the first state only. Your assertions are proved on the correct arbiter and must imply the judge-owned two-edge obligations. A looser bound, or a check on one requester, is refused at that step. The three hidden faulty arbiters then run as measured examples. Each breaks those obligations, so each fails any answer that passed the first step.

INCONCLUSIVE never counts as acceptance or a rated miss. Run previews the same checks that Submit uses.

More problems on this topic

Report a problem with this page

Worked solution

Opening the solution ends an unsolved rated attempt. Solving it first costs nothing.

Your Property File

SymbiYosys · server

Recent Submissions