Explicit routing schemes for implementation of cellular automata on processor arrays

Massively parallel processor array (MPPA) architectures are becoming widely available computing platforms. Because of formal similarities, they are good candidates for implementing cellular automata (CA). An essential difference still remains regarding the freedom in communications. In MPPA there is a fixed on-chip network interconnection topology but every CA has its own definition of neighbourhood. While a cell in a CA can be considered as directly connected to its neighbours, these connections correspond to paths in the network of the MPPA. The communications need to be routed and scheduled to reach their proper destination. In previous work we introduced a formal data-flow process network model named KRG (for K-periodically Routed Graph). Its main feature is to allow regular switching directives. In the present paper we will use it to represent the proper local sequences of routing directives that will efficiently propagate values from cells to cells so as to implement the required CA neighbourhood. We present the neighbourhood broadcasting algorithm that computes these routing directives. One should note here that the problem is made more complex as data traffic between distinct source and target cells must be merged, while multicast may save a tremendous amount of communications when values are required in multiple locations. We demonstrate the expressive power of our formalism on the case of a 2D CA where the neighbourhood consists of all cells at Moore distance at most n. Further potential applications of our framework are hinted.     

Compositionality of Statically Scheduled IP

Timing Closure in presence of long global wire interconnects is one of the main current issues in System-on-Chip design. One proposed solution to the Timing Closure problem is Latency-Insensitive Design (LID) [Luca Carloni, Kenneth McMillan, and Alberto Sangiovanni-Vincentelli. Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20(no. 9):pp. 1059–1076, 2001; Mario R. Casu and Luca Macchiarulo. A new approach to latency insensitive design. In DAC'04: Proceedings of the 41st annual conference on Design automation, pages 576–581, New York, NY, USA, 2004. ACM Press].It was noticed in [Mario R. Casu and Luca Macchiarulo. A new approach to latency insensitive design. In DAC '04: Proceedings of the 41st annual conference on Design automation, pages 576–581, New York, NY, USA, 2004. ACM Press] that, in many cases, the dynamically scheduled synchronisations introduced by latency-insensitive protocols could be computed off-line as a static periodic schedule. We showed in [Julien Boucaron, Jean-Vivien Millo, and Robert De Simone. Latency-insensitive design and central repetitive scheduling. In Formal Methods and Models for Co-Design, 2006. MEMOCODE'06. Proceedings. Fourth ACM and IEEE International Conference on, pages 175–183, Piscataway, NJ, USA, 2006. IEEE Press; Julien Boucaron, Jean-Vivien Millo, and Robert De Simone. Formal methods of scheduling for latency-insensitive designs. EURASIP journal on embedded system, 2007 (not yet published)] how this schedule could then be used to further optimize the protocol resources when they are found redundant. The purpose of the present paper is to study how the larger blocks, obtained as synchronous components interconnected by LID protocols optimized by static schedule informations, can be again made to operate with an environment that provides also I/O connections at its own (synchronous or GALS) rate.We also consider the case of multirate SoC, using results from SDF (Synchronous DataFlow) theory [Edward A. Lee and David G. Messerschmitt. Synchronous data flow. Proceeding of the IEEE, vol. 75(no. 9):pp. 1235–1245, 1987].     

Scenario-based verification in presence of variability using a synchronous approach

This paper presents a new model of scenarios, dedicated to the specification and verification of system behaviours in the context of software product lines (SPL). We draw our inspiration from some techniques that are mostly used in the hardware community, and we show how they could be applied to the verification of software components. We point out the benefits of synchronous languages and models to bridge the gap between both worlds.     

Scenario-based verification in presence of variability using a synchronous approach

This paper presents a new model of scenarios, dedicated to the specification and verification of system be- haviours in the context of software product lines （SPL）. We draw our inspiration from some techniques that are mostly used in the hardware community, and we show how they could be applied to the verification of software components. We point out the benefits of synchronous languages and mod- els to bridge the gap between both worlds.     

Progressive and explicit refinement of scheduling for multidimensional data-flow applications using uml marte

Process networks and data-flow graphs are used to capture data-dependencies in computation-intensive embedded systems. Their simplicity allows the computation of static schedules that reduce the dynamic overhead and increase predictability. The resulting schedule is a total ordering of actor computations and communications. It can therefore become an over-specification of the initial system when several schedules are valid. This is particularly the case for multidimensional data-flow applications. We propose a methodology to avoid such an over-specification. We propose to use logical time to capture explicitly all the valid schedules for a given multi-dimensional data-flow model. Then, we show that the proposed approach allows for a progressive and explicit refinement of computation scheduling that also captures constraints imposed by the environment and the execution platform. All this is achieved by using uml marte concepts and the resulting models can be considered for simulation and analysis with existing tools for early design validation. The whole approach is validated on a typical application devoted to radar signal processing.