Automatic Synthesis of Optimal-Size Concentrators by Answer Set Programming

A concentrator is a circuit with N inputs and \(M\le N\) outputs that can route any given subset of \(K\le M\) valid inputs to K of its M outputs. Concentrator circuits are important building blocks of many parallel algorithms. The design of optimal concentrator circuits is however a challenging task that has already been considered in many research papers. In this paper, we show how answer set programming can be used to automatically generate concentrator circuits of provably optimal size.