💻 computer science

Dynamically Reprogrammable Runtime Monitors for Bounded-time MTL

This paper proposes a novel, dynamically reprogrammable runtime monitor implemented using standard cells on the same die as the system under verification, enabling high-speed, at-speed monitoring of bounded-time MTL properties with a compact footprint of 0.55 mm² and an operating frequency of 1.25 GHz.

Original authors: Chirantan Hebballi, Akash Poptani, Amrutha Benny, Rajshekar Kalayappan, Sandeep Chandran, Ramchandra Phawade

Published 2026-03-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chirantan Hebballi, Akash Poptani, Amrutha Benny, Rajshekar Kalayappan, Sandeep Chandran, Ramchandra Phawade

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very fast, high-performance race car (the System Under Verification). You want to install a "safety co-pilot" (the Monitor) that rides along with the car, watching every single move it makes in real-time. This co-pilot needs to check if the car is following the rules of the road, like "Don't speed up if the light is red" or "Always brake within 2 seconds of seeing a pedestrian."

The problem is that the rules of the road might change while you are driving. Maybe today you are driving in a city, and tomorrow you are on a highway. You need a co-pilot that can instantly change its rulebook without stopping the car or slowing it down.

The Old Way: The FPGA "Forklift"

Previously, engineers tried to build this co-pilot using a special chip called an FPGA. Think of an FPGA like a giant, programmable Lego board.

The Good: You can build any shape you want on it. If the rules change, you can tear down the Lego structure and rebuild a new one.
The Bad:
1. It's bulky and slow: A Lego structure is much bigger and slower than a custom-built machine part.
2. Rebuilding takes forever: To change the rules, you have to physically move thousands of Lego bricks. This takes time, and while you are rebuilding, the car is driving blind.
3. The connection is weak: The Lego board sits in a separate box next to the car engine. Sending data back and forth takes time, so the co-pilot can't keep up with the car's super-fast engine.

The New Way: The "Reprogrammable Micro-Factory"

The authors of this paper propose a brand new solution. Instead of a Lego board, they built a custom micro-factory directly inside the car's engine block (on the same silicon chip).

Here is how their invention works, using simple analogies:

1. The Workers (Processing Elements)

Imagine a factory floor with a team of identical workers. Each worker is a tiny, super-fast machine that can do exactly five things:

AND: "Is A true AND is B true?"
OR: "Is A true OR is B true?"
NOT: "Is A false?"
IMPLIES: "If A happens, does B happen?"
WIRE: "Just pass this message along."

These workers are standard cells. Think of them as pre-fabricated, high-speed bricks. They are tiny, fast, and built to run at the exact same speed as the car's engine (1.25 billion times a second!).

2. The Conveyor Belts (Queues)

The workers don't just shout answers; they write them down on a conveyor belt (called a Queue).

When a worker finishes a job, they push a result onto the belt.
The belt has a special feature: it can hold "Maybe" (M) for a moment, or change a "Maybe" to "True" or "False" later if new information arrives.
This allows the system to handle time-based rules, like "Wait 5 seconds and see if the light is still red."

3. The Traffic Controller (Programmable Interconnects)

This is the magic trick. The workers and conveyor belts are connected by a smart traffic controller.

Before: You had to physically rewire the factory to change the rules.
Now: You just send a digital "instruction manual" (a few bytes of data) to the traffic controller.
The controller instantly re-routes the wires. Worker A now talks to Worker B instead of Worker C. The conveyor belts shift direction.
The Result: The factory instantly transforms from checking "City Rules" to checking "Highway Rules" in a single heartbeat, without ever stopping the car.

Why This is a Big Deal

Speed: Because this factory is built with the same tiny, fast bricks as the car's engine (Standard Cells), it runs at 1.25 GHz. That's roughly 1,000 times faster than the typical FPGA solutions. It can watch 1.25 billion events every second.
Size: Even a factory capable of handling complex rules (up to 16 different conditions) is tiny. It takes up only 0.55 square millimeters. To put that in perspective, if a standard computer chip were the size of a football field, this monitor would be smaller than a postage stamp.
Flexibility: You can change the rules while the car is driving. The paper shows a simulation where the monitor switches from one rule to another in the middle of operation, just like a general-purpose processor (like your phone's CPU) does.

The Bottom Line

The authors built a universal, high-speed rule-checker that fits inside the device it is monitoring. Instead of using a slow, bulky, re-wirable Lego board (FPGA), they built a tiny, super-fast assembly line that can be instantly reconfigured by sending it a new set of instructions.

This means safety-critical systems (like self-driving cars or medical devices) can have a co-pilot that is fast enough to catch errors instantly, small enough to fit on the chip, and flexible enough to adapt to new rules on the fly.

1. Problem Statement

Runtime Verification (RV) is critical for safety-critical systems, requiring monitors to observe system behavior in real-time ("at-speed") without affecting performance. While Field-Programmable Gate Arrays (FPGAs) have been used to implement flexible RV monitors that can be reconfigured in the field, they suffer from three significant drawbacks when compared to standard Integrated Circuit (IC) implementations:

Inefficiency: FPGA implementations using Look-Up Tables (LUTs) are less area-efficient, consume more power, and have higher latency compared to designs built with standard cells (optimized logic gates like NAND).
Reconfiguration Overhead: Reconfiguring an FPGA to change the monitored property is time-consuming, as it requires rewriting thousands to hundreds of thousands of LUTs.
Communication Bottlenecks: The bandwidth between a processor core and an FPGA (even on Systems-on-Chip like Zynq) is limited. This often forces verification to coarse-grained data (e.g., bus transactions) rather than fine-grained data (every instruction), limiting the ability to monitor complex, high-speed software.

The authors aim to create a Dynamically Reprogrammable Hardware Monitor implemented using standard cells that can be co-located with the System Under Verification (SUV) on the same die. This design must support Metric Temporal Logic (MTL) properties, allow for dynamic reprogramming of the monitored property after deployment (without re-synthesis), and operate at the same high clock frequency as the SUV.

2. Methodology

The proposed solution replaces the concept of "reconfiguration" (changing the circuit structure) with "dynamic reprogrammability" (changing the circuit's behavior via input instructions while the circuit structure remains fixed).

A. Core Abstraction: Abstract Machines (AMs)

The fundamental building block is an Abstract Machine (AM), a single-state machine capable of performing five basic operations:

not, and, or, implies, wire (identity).
Queue Interaction: The AM interacts with a custom Queue (Que) data structure. The queue holds partial results and verdicts over time. It supports:
- add: Pushes a value (initially Maybe/M) to the head.
- del: Removes a value from a specific index (Head).
- modify: Conditionally updates values in a specific time interval within the queue based on the operation result.

B. Evaluator Machines (EMs)

An Evaluator Machine is a composition of one or more AMs and a Queue that evaluates a specific MTL operator (e.g., $\neg$ , $\lor$ , $\land$ , $\to$ , $X$ , $\square$ , $\diamond$ , $U$ ).

Streaming Nature: The design processes input events exactly once.
Correctness: The authors prove that by setting the Head index of the queue correctly (based on the operator's time horizon $l(\odot)$ ), the EM produces stable, correct verdicts for the corresponding time step.
Handling Time Bounds: For bounded operators (like $U_{[t1, t2]}$ ), multiple AMs may operate on the same queue to handle different temporal constraints simultaneously without conflict.

C. Composition via Abstract Syntax Tree (AST)

To monitor a complex MTL formula:

The formula is parsed into an Abstract Syntax Tree (AST).
Each node in the AST is assigned an EM.
Interconnects: Programmable interconnects link the output queues of child EMs to the input operands of parent EMs.
Queue Balancing: A critical algorithm (Algorithm 1) computes the correct Head values for each EM to ensure that operands arriving at a parent node correspond to the same logical time step, preventing functional errors caused by latency mismatches in the tree.

D. Hardware Architecture

The hardware consists of three main components:

Processing Elements (PEs): Hardware implementations of the AMs. They receive operands from Atomic Propositions (APs) or other Queues and write results to a target Queue.
Queues (Qs): Buffers that store temporal results. They support deletion (producing verdicts) and modification.
Programmable Interconnects: Crossbar switches connecting APs $\to$ PEs, PEs $\to$ Queues, and Queues $\to$ PEs/Outputs.

Programming: The system is programmed via a bitstream sent through I/O pins. This bitstream configures:

The operation (opcode) of each PE.
The source of operands (AP or Queue).
The target Queue ID.
The Head and modification intervals for Queues.
The interconnect routing.

3. Key Contributions

Standard Cell Implementation of RV: The first proposal of a reprogrammable MTL monitor implemented using standard cells rather than FPGAs, enabling co-location with high-performance processors.
Dynamic Reprogrammability: The ability to change the monitored property post-deployment by simply updating input instructions (bitstream), eliminating the need for time-consuming FPGA reconfiguration or circuit re-synthesis.
Theoretical Framework: A formal proof that a composition of programmable AMs can faithfully implement discrete-time, bounded MTL semantics, including a novel algorithm for balancing queue latencies in AST-based monitors.
Compiler Toolchain: Development of a tool (in Python/Clash) that takes an MTL formula, generates the hardware design (Verilog), and produces the specific programming bits required to configure the monitor for that formula.

4. Results

The authors synthesized and simulated their design using a 32nm standard cell library (SAED32nm_EDK) and Synopsys Design Compiler.

Area Efficiency:
- A large monitor supporting up to 16 Atomic Propositions, 16 MTL operators, and a maximum time bound of 256 steps occupies only 0.55 mm².
- This is approximately 0.13% of a typical 400 mm² general-purpose processor die.
Performance:
- Frequency: The monitor operates at 1.25 GHz.
- Throughput: It can observe 1.25 billion events per second (1 verdict per cycle), significantly outperforming typical FPGA-based monitors which operate in the MHz range.
- Latency: The latency is determined by the horizon of the specific MTL formula being monitored (e.g., 8–11 cycles in simulations), but the throughput remains constant at 1 verdict/cycle.
Reprogramming: Simulations demonstrated that the monitor can be dynamically reprogrammed at runtime (e.g., switching from property $A \to X B$ to $A \lor \diamond_{[1,3]} B$ ) by sending new configuration bits via I/O pins, with the new property becoming active within a few dozen clock cycles.

5. Significance

This work bridges the gap between the flexibility of software/FPGA-based verification and the performance of hardware. By moving the monitor onto the same die as the processor using standard cells, it enables fine-grained, at-speed verification of complex safety-critical systems (like autonomous vehicles or avionics) without the bandwidth or latency penalties associated with off-chip FPGA communication.

The ability to reprogram the monitor dynamically means that a single hardware block can adapt to new safety requirements or bug fixes in the field without hardware replacement or long reconfiguration downtimes. This makes it a viable solution for next-generation safety-critical systems where properties may evolve during operation.