Conformance testing of protocols specified as communicating finitestate machines-a guided random walk based approach

We present a new approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs). Our approach uses a guided random walk procedure. This procedure attempts to cover all transitions in the component FSMs. We also introduce the concept of observers that check some aspect of protocol behavior. We present the result of applying our method to two example protocols: full-duplex alternating bit protocol and the ATM-adaptation-layer-convergence protocol. Applying our procedure to the ATM adaptation layer, 99% of component FSMs edges can be covered in a test with 11692 input steps. Previous approaches cannot do conformance test generation for standard protocols (such as asynchronous transfer mode (ATM) adaptation layer) specified as a collection of communicating FSMs     

Reconfigurable finite-state machine based IP lookup engine for high-speed router

Internet protocol (IP) address lookup is one of the major performance bottlenecks in high-end routers. This paper presents an architecture for an IP address lookup engine based on programmable finite-state machines (FSMs). The IP address lookup problem can be translated into the implementation of a large FSM. Our hardware engine is then used to implement this FSM using a structured approach, in which the large FSM is broken down into a set of smaller FSMs which are then mapped into reconfigurable hardware blocks. The design of our hardware engine is based on a regular and well structured architecture, which is easy to scale. Our simulation results demonstrate that the FSM based architecture can easily scale to wire speed performance at OC-192 rates. Unlike previous approaches, the performance of our architecture is not constrained by memory bandwidth and is, therefore, in principle scalable with very large scale integration technology.     

Implementation of finite-state machines based on programmable logic ICs with the help of the merged model of Mealy and Moore machines

The problem concerning the synthesis of finite-state machines (FSMs) based on programmable logic ICs, in which FSM’s output variables serve as the code (or part of the code) of internal states, has been examined. A solution to the problem is obtained with the help of the merged model of Mealy and Moore machines. A principal distinction between the proposed and well-known techniques is that an initial FSM undergoes no conversions related to an increase in the number of internal states and transitions thereof. The necessary conditions under which output variables can be used as the code of FSM’s internal states are presented. The method for synthesizing the merged model AC of Mealy and Moore machines is described. Basic results of investigations, as well as promising directions of further studies concerned with the development of new structural models of FSMs, are discussed.     

Modeling robust asynchronous communication protocols withfinite-state machines

A.V. Aho et al. (Comput. Math. Applic., vol.8, p.205-14, 1982) used communicating finite-state machines to model synchronous protocols for reliable communication across unreliable channels. Their ideas are extended to modeling asynchronous protocols for communication across unreliable channels using finite-state machines communicating via an unreliable shared memory. Lower bounds on the size of machines and the number of symbols in the transmission alphabet required to achieve reliable communication are established. Two types of finite-state machines and two fault models for the shared memory are considered. In each case it is shown that there are robust protocols for deletion and insertion errors. It is also shown that there are no robust protocols for mutation errors. In contrast, in the synchronous case, robust protocols exist for all of these types of errors     

FunState-an internal design representation for codesign

In this paper, an internal design model called FunState (functions driven by state machines) is presented that enables the representation of different types of system components and scheduling mechanisms using a mixture of functional programming and state machines. It is shown how properties relevant for scheduling and verification of specification models such as Boolean dataflow, cyclostatic dataflow, synchronous dataflow, marked graphs, and communicating state machines as well as Petri nets can be represented in the FunState model of computation. Examples of methods suited for FunState are described, such as scheduling and verification. They are based on the representation of the model's state transitions in the form of a periodic graph. The feasibility of the novel approach is shown with an asynchronous transfer mode switch example     

Methods to explore design space for MPEG RMC codec specifications

The recent MPEG Reconfigurable Media Coding (RMC) standard aims at defining media processing specifications (e.g. video codecs) in a form that abstracts from the implementation platform, but at the same time is an appropriate starting point for implementation on specific targets. To this end, the RMC framework has standardized both an asynchronous dataflow model of computation and an associated specification language. Either are providing the formalism and the theoretical foundation for multimedia specifications. Even though these specifications are abstract and platform-independent the new approach of developing implementations from such initial specifications presents obvious advantages over the approaches based on classical sequential specifications. The advantages appear particularly appealing when targeting the current and emerging homogeneous and heterogeneous manycore or multicore processing platforms. These highly parallel computing machines are gradually replacing single-core processors, particularly when the system design aims at reducing power dissipation or at increasing throughput. However, a straightforward mapping of an abstract dataflow specification onto a concurrent and heterogeneous platform does often not produce an efficient result. Before an abstract specification can be translated into an efficient implementation in software and hardware, the dataflow networks need to be partitioned and then mapped to individual processing elements. Moreover, system performance requirements need to be accounted for in the design optimization process. This paper discusses the state of the art of the combinatorial problems that need to be faced at this design space exploration step. Some recent developments and experimental results for image and video coding applications are illustrated. Both well-known and novel heuristics for problems such as mapping, scheduling and buffer minimization are investigated in the specific context of exploring the design space of dataflow program implementations.     

Parameterized dataflow modeling for DSP systems

Dataflow has proven to be an attractive computation model for programming digital signal processing (DSP) applications. A restricted version of dataflow, termed synchronous dataflow (SDF), that offers strong compile-time predictability properties, but has limited expressive power, has been studied extensively in the DSP context. Many extensions to synchronous dataflow have been proposed to increase its expressivity while maintaining its compile-time predictability properties as much as possible. We proposed a parameterized dataflow framework that can be applied as a meta-modeling technique to significantly improve the expressive power of any dataflow model that possesses a well-defined concept of a graph iteration, Indeed, the parameterized dataflow framework is compatible with many of the existing dataflow models for DSP including SDF, cyclo-static dataflow, scalable synchronous dataflow, and Boolean dataflow. In this paper, we develop precise, formal semantics for parameterized synchronous dataflow (PSDF)-the application of our parameterized modeling framework to SDF-that allows data-dependent, dynamic DSP systems to be modeled in a natural and intuitive fashion. Through our development of PSDF, we demonstrate that desirable properties of a DSP modeling environment such as dynamic reconfigurability and design reuse emerge as inherent characteristics of our parameterized framework. An example of a speech compression application is used to illustrate the efficacy of the PSDF approach and its amenability to efficient software synthesis techniques. In addition, we illustrate the generality of our parameterized framework by discussing its application to cyclo-static dataflow, which is a popular alternative to the SDF model     

Dataflow process networks

We review a model of computation used in industrial practice in signal processing software environments and experimentally and other contexts. We give this model the name “dataflow process networks,” and study its formal properties as well as its utility as a basis for programming language design. Variants of this model are used in commercial visual programming systems such as SPW from the Alta Group of Cadence (formerly Comdisco Systems), COSSAP from Synopsys (formerly Cadis), the DSP Station from Mentor Graphics, and Hypersignal from Hyperception. They are also used in research software such as Khoros from the University of New Mexico and Ptolemy from the University of California at Berkeley, among many others. Dataflow process networks are shown to be a special case of Kahn process networks, a model of computation where a number of concurrent processes communicate through unidirectional FIFO channels, where writes to the channel are nonblocking, and reads are blocking. In dataflow process networks, each process consists of repeated “firings” of a dataflow “actor.” An actor defines a (often functional) quantum of computation. By dividing processes into actor firings, the considerable overhead of context switching incurred in most implementations of Kahn process networks is avoided. We relate dataflow process networks to other dataflow models, including those used in dataflow machines, such as static dataflow and the tagged-token model. We also relate dataflow process networks to functional languages such as Haskell, and show that modern language concepts such as higher-order functions and polymorphism can be used effectively in dataflow process networks. A number of programming examples using a visual syntax are given     

An algorithmic procedure for checking safety properties ofprotocols

A procedure for checking safety properties of communication protocols is presented. A protocol is specified as a collection of communicating finite-state machines (FSMs). Two novel algorithms used in this procedure are described. The first algorithm does incremental composition and reduction of FSMs. It uses three heuristic rules which reduce the number of states in the global FSM by one to two orders of magnitude while maintaining its observational equivalence. The second algorithm checks whether the behavior of one FSM is a subset of another FSM's behavior. This procedure has been applied to the ISDN Q.931 and alternating bit protocols     

Mapping Parameterized Cyclo-static Dataflow Graphs onto Configurable Hardware

In recent years, parameterized dataflow has evolved as a useful framework for modeling synchronous and cyclo-static graphs in which arbitrary parameters can be changed dynamically. Parameterized dataflow has proven to have significant expressive power for managing dynamics of DSP applications in important ways. However, efficient hardware synthesis techniques for parameterized dataflow representations are lacking. This paper addresses this void; specifically, the paper investigates efficient field programmable gate array (FPGA)-based implementation of parameterized cyclo-static dataflow (PCSDF) graphs. We develop a scheduling technique for throughput-constrained minimization of dataflow buffering requirements when mapping PCSDF representations of DSP applications onto FPGAs. The proposed scheduling technique is integrated with an existing formal schedule model, called the generalized schedule tree, to reduce schedule cost. To demonstrate our new, hardware-oriented PCSDF scheduling technique, we have designed a real-time base station emulator prototype based on a subset of long-term evolution (LTE), which is a key cellular standard.     

Combined use of finite-state machines and petri nets for modelling communicating processes

In order to model and verify systems of concurrent processes (such as those involved in communication protocols), finite-state machines and Petri nets can be used as local and global models, respectively. The problem of composing a set of communicating finite-state machines into a single global Petri net is considered in the letter with special attention to the case of more than two processes.     

Monitoring machine based synthesis technique for concurrent error detection in finite state machines

This paper discusses a new design methodology for concurrent error detection in synchronous sequential circuits based on the use of monitoring machines. In this approach, an auxiliary sequential circuit, called the monitoring machine, operates in lock-step with the main machine, such that any fault in either of the two machines is immediately detected. This methodology is independent of the fault model. It can be applied to FSMs with pre-encoded states and can also be used for ones being synthesised. It also provides a systematic framework for the combined optimisation of the main and monitoring machines, and for exploring tradeoffs in their implementation. The design of monitored sequential circuits is a two-fold problem; namely one of designing an optimal monitoring machine given the main machine, and the other of encoding the main machine states so that the resulting monitoring machine is minimal. This paper formally discusses the design of both the main and monitoring machines and techniques for their combined optimisation. Tradeoffs in their implementation based on selective fault detection are also examined. Through experimental results, it is shown that the proposed synthesis technique is eminently suitable for the design of low-cost sequential circuits with concurrent error detection. The monitoring machine is less costly than the main machine. It is also not identical to it. As a result, a monitored sequential circuit has significantly lower hardware cost and improved fault coverage than previous implementations. Presently at Texas Instruments (India) Ltd., Bangalore, India.     

SoC Memory Hierarchy Derivation from Dataflow Graphs

Hardware synthesis from dataflow graphs of signal processing systems is a growing research area as focus shifts to high level design methodologies. For data intensive systems, dataflow based synthesis can lead to an inefficient usage of memory due to the restrictive nature of synchronous dataflow and its inability to easily model data reuse. This paper explores how dataflow graph changes can be used to drive both the on-chip and off-chip memory organisation and how these memory architectures can be mapped to a hardware implementation. By exploiting the data reuse inherent to many image processing algorithms and by creating memory hierarchies, off-chip memory bandwidth can be reduced by a factor of a thousand from the original dataflow graph level specification of a motion estimation algorithm, with a minimal increase in memory size. This analysis is verified using results gathered from implementation of the motion estimation algorithm on a Xilinx Virtex-4 FPGA, where the delay between the memories and processing elements drops from 14.2 ns down to 1.878 ns through the refinement of the memory architecture. Care must be taken when modeling these algorithms however, as inefficiencies in these models can be easily translated into overuse of hardware resources.     

On the hard-real-time scheduling of embedded streaming applications

In this paper, we consider the problem of hard-real-time (HRT) multiprocessor scheduling of embedded streaming applications modeled as acyclic dataflow graphs. Most of the hard-real-time scheduling theory for multiprocessor systems assumes independent periodic or sporadic tasks. Such a simple task model is not directly applicable to dataflow graphs, where nodes represent actors (i.e., tasks) and edges represent data-dependencies. The actors in such graphs have data-dependency constraints and do not necessarily conform to the periodic or sporadic task models. In this work, we prove that the actors in acyclic Cyclo-Static Dataflow (CSDF) graphs can be scheduled as periodic tasks. Moreover, we provide a framework for computing the periodic task parameters (i.e., period and start time) of each actor, and handling sporadic input streams. Furthermore, we define formally a class of CSDF graphs called matched input/output (I/O) rates graphs which represents more than 80 % of streaming applications. We prove that strictly periodic scheduling is capable of achieving the maximum achievable throughput of an application for matched I/O rates graphs. Therefore, hard-real-time schedulability analysis can be used to determine the minimum number of processors needed to schedule matched I/O rates applications while delivering the maximum achievable throughput. This can be of great use for system designers during the Design Space Exploration (DSE) phase.     

How a large ATM MTU causes deadlocks in TCP data transfers

The implementation of protocols, such as TCP/IP, and their integration into the operating system environment is crucial for protocol performance. Putting TCP on high-speed networks, e.g., ATM, with large maximum transmission units causes the TCP maximum segment size to be relatively large. What Nagle's algorithm considers a “small” segment is no longer small, which affects the TCP performance. The authors report on TCP/IP throughput and RPC response time performance measurements for various sizes of send and receive socket buffers, using the Sparc10 architecture machines Axil 311/5.1 running SunOS 4.1.3 connected to a FORE System's ATM network. For some common combinations of socket buffer sizes the authors observe a dramatic performance degradation to less than 1% of expected throughput and to one order-of-magnitude longer response time than expected. The performance degradation is caused by a deadlock situation in the TCP connection which is resolved by the 200 ms spaced timer generated TCP delayed acknowledgment. The authors explain the causes of the deadlock situations, and discuss means to avoid or prevent them     

An interface between continuous and discrete-event controllers forvehicle automation

The work presented is part of a bigger effort to design an automated highway system (AHS) to improve the capacity and safety of current highways. Automation of highways and, in particular, platooning of vehicles raise a number of control issues. In the design proposed by Varaiya,(see IEEE Trans. Automat., Contr., vol.38, no.2, p.195-207, 1993), these issues are addressed by a hierarchical structure consisting of both discrete-event and continuous controllers. Our work is an attempt to construct a consistent interface between these two types of controllers. The proposed design is in the form of a set of finite-state machines (FSMs) that interact with the discrete controllers through discrete commands and with the continuous controllers by issuing commands that get translated to inputs for the vehicle actuators. The operation of the proposed design is verified using COSPAN and tested in simulation. The interface design provides insight into interesting problems related to the hybrid nature of the AHS as it touches on both the discrete and continuous worlds     

Circuit Level Concurrent Error Detection in FSMs

Finite state machines (FSMs) are contained in many building blocks of digital electronic circuits. Such electronic circuits are prone to transient errors, caused e.g. by cosmic radiation, and to permanent errors. In this article, the authors give an overview of known error detection methods for FSMs. One method (dependent state encoding for dynamic error detection) is described in detail, as well as the problems arising when the method is applied to a practical example. Additionally, the authors propose a modification of the method above. For several benchmark circuits, this modification shows better results, compared to the state-of-the-art implementation.     

一种HDMI-CEC控制器的设计与实现

在充分理解HDMI-CEC协议1.4版本的基础上,提出一种消费电子控制器的ASIC电路设计方案。通过对串行接口上波形进行分析,设计了两个分工不同的有限状态机来处理协议的两个重要部分:比特位时序和信息构成。利用可综合Verilog语言完成了消费电子控制器IP核的设计,并且通过NC-Verilog的仿真工具和FPGA开发板验证其功能。仿真结果表明,该设计完全符合HDMICEC通讯接口模块的要求,并且可以作为IP广泛应用于支持HDMI接口的SoC开发中去。     

Hardware/software codesign: a systematic approach targeting data-intensive applications

This article presents a systematic approach to hardware/software codesign targeting data-intensive applications. It focuses on the application processes that can be represented in directed acrylic graphs (DAGs) and use a synchronous dataflow (SDF) model, the popular form of dataflow employed in DSP systems when running the process. The codesign system is based on the ultrasonic reconfigurable platform, a system designed jointly at Imperial College and the SONY Broadcast Laboratory. This system is modeled as a loosely coupled structure consisting of a single instruction processor and multiple reconfigurable hardware elements. The paper also introduces and demonstrates a task-based hardware/software codesign environment specialized for real-time video applications. Both the automated partitioning and scheduling environment and the task manager program help to provide a fast robust for supporting demanding applications in the codesign system.     

Properties of Self-Timed Ring Architectures for Deadlock-Free and Consistent Configuration Reaching Maximum Throughput

Multiprocessor System-on-Chip with self-ti-med design becomes increasingly attractive due to its ability to exploit high parallelism of applications. Previous research efforts on self-timed techniques mostly focused on hardware layer. However, the problem of correctly synthesizing self-timed systems remains to be difficult. In particular, the problem of how to configure a self-timed ring structure to achieve the maximal throughput with no deadlock is still unsolved. Self-timed ring (STR) is composed of a ring of connected “stages”, each consisting of a processing element, communication units and its current state. The correct configuration of STR is determined by the initial state of each stage and a number of inserted buffers into the ring to maintain correct behavior of applications on an STR. This paper establishes a series of theorems based on the understanding of properties of self-timed structures. Based on the theorems, the setting of initial states and buffers can be decided to guarantee correct configuration. Our theorem also establishes mathematical formulas to calculate throughput of an STR. The algorithms presented in the paper find the optimal initial configuration of an STR that achieves the maximum throughput with the minimum number of inserted buffers. The experimental results show that the throughput of applications mapped on STR with the optimal configuration is improved by 64.99 % on average compared with synchronous system.