STG Decomposition

STG Decomposition

Asynchronous circuits are a promising type of digital circuits. They perform better, use less energy and emit less radiation than conventional synchronous circuits. A widely used formalism for their modelling are signal transition graphs (STGs), which are interpreted Petri nets.

While STGs are relatively simple and well-studied, synthesising a control circuit from an STG is often very expensive due to the state space explosion problem. The resulting size bounds on the synthesisable circuits are restrictive, especially if the STG models are not constructed manually by a designer but rather generated automatically from high-level hardware descriptions.

One way to alleviate state space explosion is to decompose an STG into several smaller ones which behave together in the same way as the original one. The advantages are a faster synthesis and a reduced peak memory usage.

This project deals with the theoretical background and algorithmic techniques of such STG decompositions.