Diversely Enumerating System-Level Architectures

Embedded systems are highly constrained. System-level constraints, such as task partitioning problems and communication scheduling problems, are common, combinatorial, and fundamentally intractable. Though modern constraint solvers can help to synthesize constrained architectures, the architect’s troubles do not end here: There may be (infinitely) many architectures satisfying system-level constraints. Multiple candidates must be examined and this is often infeasible for large solution spaces.

In this paper we describe an improved enumeration scheme, which still reaps the benefits of modern constraint solvers. The idea is to build a diverse enumerator around an unmodified constraint solver. A diverse enumerator uniformly draws equivalence classes of solutions. Such an enumerator is powerful because it allows unbiased enumeration of the space and can be used to make inferences about the space as a whole. This paper presents the theory, practice, and algorithms for diverse enumeration of architectures with system-level constraints.