Representation of multiple-output logic functions by Multi-Terminal Binary Decision Diagrams (MTBDDs) is studied for the useful class of sparse logic functions specified by the number of true min-terms. This paper derives upper bounds on the MTBDD width, which determine the size of look-up tables (LUTs) needed for hardware realization of these functions in FPGA logic synthesis. The obtained bounds are generalization of similar known bounds for single-output logic functions. Finally a procedure how to find the optimum mapping of MTBDD to a LUT cascade is presented and illustrated on a set of benchmarks.

The Spidergon interconnection network has become popular recently in multiprocessor systems on chips. To the best of our knowledge, algorithms for collective communications (CC) have not been discussed in the literature as yet, contrary to pair-wise routing algorithms. The paper investigates complexity of CCs in terms of lower bounds on the number of communication steps at conflict-free scheduling. The considered networks on chip make use of wormhole switching, full duplex links and all-port non-combining nodes. A search for conflict-free scheduling of CCs has been done by means of evolutionary algorithms and the resulting numbers of communication steps have been summarized and compared to lower bounds. Time performance of CCs can be evaluated from the obtained number of steps, the given start-up time and link bandwidth. Performance prediction of applications with CCs among computing nodes of the Spidergon network is thus possible.

Multi-terminal binary decision diagrams (MTBDDs) are useful representation of multiple output Boolean functions. However, construction of such a diagram is a difficult task, especially when in some sense optimum diagram is sought. The paper presents an improved algorithm of MTBDD synthesis aiming at minimum MTBDD width or cost. The presented algorithm is a core of the upgraded version of a synthesis tool that accepts incompletely specified integer-valued functions of Boolean variables specified by possibly compatible cubes. The suggested technique is suitable for hardware (LUT cascades) or firmware implementation (branching microprograms).

This paper presents a new algorithm of iterative decomposition for multiple-output Boolean functions with an embedded heuristics to order variables. The algorithm produces a cascade of look-up tables (LUTs) that implements the given function and simultaneously a sub-optimal Multi-Terminal Binary Decision Diagram (MTBDD). The LUT cascade can be used for pipelined processing on FPGAs with BRAMs or at a non-traditional synthesis of large combinational and sequential circuits. On the other hand, suboptimal MTBBDs can serve as prototypes for efficient firmware implementation, especially when a micro-programmed controller that firmware runs on supports multi-way branching. A novel technique is illustrated on practical examples of three types of arbiters. It may be quite useful as a more flexible alternative implementation of digital systems with increased testability and improved manufacturability.

Scheduling collective communications (CC) in networks based on optimal graphs and digraphs has been done with the use of the evolutionary techniques. Inter-node communication patterns scheduled in the minimum number of time slots have been obtained. Numerical values of communication times derived for illustration can be used to estimate speedup of typical applications that use CC frequently. The results show that evolutionary techniques often lead to ultimate scheduling of CC that reaches theoretical bounds on the number of steps. Analysis of fault tolerance by the same techniques revealed graceful CC performance degradation for a single link fault. Once the faulty link is located, CC can be re-scheduled during a recovery period.

In this paper, we describe two evolutionary algorithms aimed at scheduling collective communications on interconnection networks of parallel computers. To avoid contention for links and associated delays, collective communications proceed in synchronized steps. Minimum number of steps is sought for the given network topology, wormhole (pipelined) switching, minimum routing and given sets of sender and/or receiver nodes. Used algorithms are able not only re-invent optimum schedules for known symmetric topologies like hyper-cubes, but they can find schedules even for any asymmetric or irregular topologies in case of general many-to-many collective communications. In most cases does the number of steps reach the theoretical lower bound for the given type of collective communication; if it does not, non-minimum routing can provide further improvement. Optimum schedules may serve for writing high-performance communication routines for application-specific networks on chip or for development of communication libraries in case of general-purpose interconnection networ.

A recent renewed interest in hypercube interconnection network has been concentrated to the more scalable and mostly cheaper version known as a fat cube. This paper generalizes the known results on time complexity of collective communications on a hypercube for the wormhole fat cube. Examples of particular communication algorithms on the 2D-fat cube topology with 8 processors are summarized and given in detail. The performed study shows that a large variety of fat cubes can provide lower cost, better scalability and manufacturability without compromising communication performance.

Multiprocessor SoCs (MSoCs) for network and stream processing have to cope with growing speed and flexibility requirements of new complex packet processing tasks. Performance optimization of a homogenous network of CPUs in a certain application leads basically to optimization of CPUs interconnect and communication algorithms. Several on-chip communication architectures are compared with respect to their cost, simplicity of routing algorithms, and performance in collective communications. It is shown, that if group communication patterns are considered in certain proportions, the fat cube architecture rather than Octagonal architecture may have the best performance/cost figure. A methodology for designing efficient on-chip interconnects on regular group communication patterns is suggested. It may be useful if the system is targeted for specific class of applications.

Abstract—A simple synthesis procedure has been derived for the simultaneous realization of two arbitrary binary functions of the same 4 variables in a single two-rail cascade. The synthesis method is based on successive transformations of the given table of functions into the table realizable by a 2-cell cascade. Usable transformations relate to 13 classes of 2-input, 2-output networks, a list of which is presented. Every transformation of the table of functions requires the use of one cell in the cascade. The canonical two-rail cellular cascades for functions of 4 and more input variables are also presented and the use of a common decoder for great cellular arrays is suggested.