Radix-based interconnection networks recursively partition the messages according to the most significant bits of their target addresses. The required split modules are usually implemented by binary sorting networks or by permutation networks. While sorting networks are self-routing, it can be proven that permutation networks cannot be self-routing so that they require additional configuration logic which is not required for sorting networks. In this paper, we point out that sorting networks are however not the best self-routing split modules. In particular, we first use our previous work to construct better self-routing split modules from sorting networks. Second, we show that even if the best sorting networks are used for the latter construction, we can still find better self-routing split modules. To determine optimal self-routing split modules, we reduce the problem to an equivalent model-checking problem. Using this, we derive provably optimal-depth and optimal-size self-routing split modules for small numbers of inputs.

A concentrator is a circuit with n inputs and m ≤ n outputs that can route any given subset of k ≤ m valid inputs to k of its m outputs. Concentrator circuits are important for many applications, in particular, for the design of interconnection networks. The design of concentrator circuits is however a challenging task that has already been considered in many research papers. All practical implementations aim at configuring the switches of a permutation network so that it behaves as a concentrator. In this paper, we present methods to analyze various properties of permutation networks by means of binary decision diagrams (BDDs). In particular, we can check whether it is possible to use a considered permutation network as a concentrator or even as a binary sorter. While our method can be applied to all permutation networks, we consider some particular permutation networks and verify that some of them can be used as concentrators and even as binary sorters provided that a specific permutation of the outputs is added.

Effectiveness of timing analysis of real-time applications depends on the timing predictability of the underlying execution platform. Modern hardware architectures improve average case performance using complex features. However, these features make Worst Case Execution Time (WCET) analysis complicated often leading to pessimistic derived worst case execution time. We present the preliminary design of Synchronous Control Asynchronous Dataflow (SCAD) - a new model of computation targeting time-predictability and competitive performance. Inorder execution of instructions and capability to bypass memory accesses imparts timing predictability to SCAD computational model. We also motivate a code generation technique to optimally utilize the memory bypassing capability of SCAD and that results in increased instruction level parallelism.