Buffer allocation for real-time streaming applications, modeled as dataflow graphs, minimizes the total memory consumption while reserving sufficient space for each data production without overwriting any live data and guaranteeing the satisfaction of real-time constraints. We focus on the problem of buffer allocation for systems without back-pressure. Since systems without back-pressure lack blocking behavior at the side of the producer, buffer allocation requires both best- and worst-case timing analysis. Moreover, the dynamic (data-dependent) behavior in these applications makes buffer allocation challenging from the best- and worst-case- timing analysis perspective. We argue that static dataflow cannot conveniently express the dynamic behavior of these applications, leading to overallocation of memory resources. Mode-controlled Dataflow (MCDF) is a restricted form of dynamic dataflow that allows mode switching at runtime and static analysis of real-time constraints. In this paper, we address the problem of buffer allocation for MCDF graphs scheduled on systems without back-pressure. We consider practically relevant applications that can be modeled in MCDF using recurrent-choice mode sequence that consists of the mode sequences of equal length; it provides tractable analysis. Our contribution is a buffer allocation algorithm that achieves up to 36% reduction in total memory consumption compared to the current state-of-the-art for an LTE and an LTE Advanced receiver use cases.

Today's smartphones and tablets contain multiple cellular modems to support 2G/3G/4G standards, including Long Term Evolution (LTE). They run on complex multi-processor hardware platforms and have to meet hard real-time constraints. Dataflow modeling can be used to design an LTE receiver. Static dataflow allows a rich set of analysis techniques, but is too restrictive to model the dynamic behavior in many realistic applications, including LTE receivers. Dynamic dataflow allows modeling of many realistic applications, but does not support rigorous temporal analysis. Mode-Controlled Dataflow (MCDF) is a restricted form of dynamic dataflow, and allows the same analysis techniques as static dataflow, in principle. We prove that MCDF is sufficiently expressive to handle the dynamic behavior of a realistic LTE receiver, by systematically and stepwise developing a complete MCDF model for an LTE receiver.

This paper presents a complexity adaptive channel estimator for low power. Channel estimation (CE) is one of the most computation intensive tasks in a software-defined radio (SDR) based OFDM demodulator. Complementary to the conventional low-power design methodology on processor architectures or circuits, we propose to reduce power also at the algorithm level. The idea is to dynamically scale the processing load of the channel estimator according to the run-time estimated channel quality. In this work, with a case study on China Mobile Multimedia Broadcasting (CMMB) standard, three practical CE algorithms are adopted to form a complexity scalable algorithm set, and signal noise ratio (SNR) is chosen to be the channel quality parameter for CE algorithm switching. In order to accurately estimate the SNR in the run-time, we also propose a noise variance estimation algorithm which is robust against fast-fading channels and introduces small computation overheads. Simulation shows that, under a pre-defined scenario for our targeting SDR demodulator, more than 50% run-time load reduction can be achieved compared with a fixed worst case channel estimator, while still fulfilling the mean square error requirement, resulting in about 25% of power reduction for the total demodulator. In addition, complexity adaption enables dynamical voltage and frequency scaling (DVFS) in a SDR demodulator which can lead to furthermore power reduction.

In Software Defined Radio (SDR), some or all of the physical layer functions are implemented by software. In this paper, we focus on the channel decoding part of SDR. We use Synchronous Data Flow (SDF) and Cyclo-Static Data Flow (CSDF) graphs to model channel decoding functions. We want to tackle the problem of scheduling a dynamic mix of multiple radios with throughput constraints on a multi-standard multi-channel channel decoder. The decoder consists of a Micro-Controller Unit (MCU) and several weakly programmable Hardware Units (HU) with internal states and very limited buffer sizes. Each HU has a Round Robin (RR) scheduler hosted on the MCU. To reduce scheduling overhead, RR schedules applications at coarse granularity. Due to limited buffer sizes, some tasks of an application are tightly coupled. We propose a so-called coupled scheduling policy, which is a relaxation of strict gang scheduling, to concurrently schedule these tasks. We propose a technique to model coupled scheduling in (C)SDF graphs. Under our scheduling policies, we also design an admission controller to guarantee the throughput requirements of running applications. To verify the approach, we have implemented a simulation system to run DVB-SH and DVB-T concurrently and independently.

This paper presents a hardware design for a scalable, high throughput, configurable LFSR. High throughput is achieved by producing L consecutive outputs per clock cycle with a clock cycle period that, for practical cases, increases only logarithmically with the block size L and the length of the register N. Flexibility is ensured by offering full reconfigurability of the generator polynomial within 1 clock cycle. At the heart of the design is a decomposition of the block-based state-update transition-matrix into two matrices, which enables an efficient implementation in terms of both latency and area. Potential target applications for this design include PN sequence generation in CDMA systems, BIST for VLSI circuits, CRC, encryption and error correction.

High-end mobile phones support multiple radio standards and a rich suite of applications, which involves advanced radio, audio, video, and graphics processing. The overall digital workload amounts to nearly 100GOPS, from 4b integer to 24b floating-point operations. With a power budget of only 1W this inevitably leads to heterogeneous multi-core architectures with aggressive power management. We review the state-of-theart as well as trends.

A queue typically connects a producer and a consumer and improves the overall performance by smoothening irregular production and consumption over time. In this paper, we introduce so-called multiple-input-multiple-output (MIMO) queues, connectingNPproducers withNCconsumers, that are symmetric, scalable, and have a high throughput. MIMO queues can be used to perform fine-grained load balancing and are proposed as key building blocks for variation-tolerant architectures. We present and analyze a family of asynchronous MIMO queues.

Reed Solomon (RS) codes are used in a variety of (wireless) communication systems. Although commonly implemented in dedicated hardware, this paper explores the mapping of high-throughput RS decoding on vector DSPs. The four modules of such a decoder, viz. syndrome computation, key equation solver, Chien search, and Forney pose different vectorization challenges. Their vectorizations are explained in detail, including optimizations specific for embedded vector processor (EVP). For RS (255,239), this solution is benchmarked vs published implementations, and scalability up to vector size 64 is explored. The best and the worst case throughput of our implementation is 8 times and 2 times higher respectively than other architectures.

This paper presents a method for static performance analysis of SoC architectures. The method is based on a network calculus theory known as LR servers. This network calculus is extended and applied to make it support SoC performance analysis. Performance requirements of subsystems are elegantly captured as traffic flows and associated latency constraints. The SoC infrastructure is modeled as a set of LR servers to validate that the worst-case delays in handling the traffic flows meet the latency constraints. A multi-channel DVB-T set-top box case study demonstrates the power of the method. Key architecture choices, such as schedule or interconnect variant, can be varied easily to support exploration of architecture options.

This paper describes VPF, a VLIW SIMD processor architecture developed to demonstrate the possibilities and limitations of the modern FPGA devices with respect to vector processing. VPF is developed in a bottom-up manner, using some specific Xilinx Virtex-4 device features to achieve 200 MHz performance for vector widths up to 16 issuing one VLIW instruction per clock cycle. The theoretical peak performance of VPF is 1.2·109vector operations per second. For classical real-world DSP benchmarks around 1...3·108vector operations per second can be achieved.

Vector DSPs, or SIMD DSPs, have received considerable attention recently, since they are considered to be a viable alternative for dedicated hardware in signal processing for multimedia and wireless communication. It is possible to construct dedicated hardware for IIR filters with a linear speedup, but because of their recursive nature these filters are considered difficult to map efficiently on a vector DSP. The IIR programs for vector DSPs presented so far have their speedup bounded by the order of the filter. In this paper we present a program that has a linear speed up, in the sense that doubling the vector size doubles the throughput. The program is a vectorization of the incremental block-state architecture. The speedup of this program is not bounded by the order of the filter, and even works for low order filters. Besides strided memory access, no special processor features are required by our program. As a proof of concept we implemented it on the Philips EVP processor.

Context awareness will become increasingly important in future domestic consumer electronics. In many domestic context aware applications, there is a need for location and orientation information about persons, devices or objects in the home. This information can be provided by a dedicated indoor location system. A consumer location system should be robust, safe, easy to set up, low cost, and should have a minimal infrastructure. In this paper, a step towards consumer location systems is taken by proposing an ultrasonic positioning method that needs just a single compact base station to measure 3D positions of mobile devices in a room. The method employs ultrasound time-of-flight tri-lateration to estimate device positions, using a base station containing an array of three ultrasound transducers. Five potential problems of the proposed method are identified; the main problem being line-of-sight path occlusion. The method has been prototyped, and initial results show an accuracy of 1.41 m or better for 95% of the position estimates, in case of a good line-of-sight path. It is concluded that the method is promising for providing 3D position information at around 1 m accuracy for context aware applications, but that the problem of line-of-sight occlusion requires further investigation.

A test method for asynchronous handshake circuits is presented that is based on synchronous full-scan techniques. The method adds a synchronous test mode to the circuit, in which the entire circuit is controlled by external clocks. This enables the use of conventional test generation tools. The method resulted in an operational flow, capable of automatically testing any handshake circuit with test-quality equal to synchronous circuits. Several circuits have been evaluated, demonstrating over 99% stuck-at fault coverage.

A comparison with synchronous circuits suggests four opportunities for the application of asynchronous circuits: high performance, low power; improved noise and electromagnetic compatibility (EMC) properties, and a natural match with heterogeneous system timing. In this overview paper each opportunity is reviewed in some detail, illustrated by examples, compared with synchronous alternatives, and accompanied by numerous pointers to the literature. Conditions for applying asynchronous circuit technology, such as the existence and availability of computer-aided design (CAD) tools, circuit libraries, and effective test approaches, are discussed briefly. Asynchronous circuits do offer advantages for many applications, and their design methods and tools are now starting to become mature.

This technology review explores the behavioral and structural design domains for asynchronous circuits and systems. It proceeds bottom up, introducing relevant concepts, terminology and techniques through a succession of simple examples. There are seven main points: 1) Signal transitions provide a key to understanding the switching behavior of asynchronous logic. 2) Burst-mode circuits and speed-independent control circuits offer reliable operation that is free from glitches. 3) Various notations are available for specification of control circuitry and as a starting point for logic synthesis. 4) Bundled data and delay-insensitive coding schemes are suitable for representing data because they address the issues of data validity and completion detection. 5) Asynchronous networks, constructed from modules and channels, provide a systems architecture for asynchronous design. 6) Handshaking on channels, which controls data communication and synchronization between modules, is implemented using signal transitions. 7) The translation of algorithmic descriptions into asynchronous networks facilitates an automated approach to large-scale system design.

No abstract.

Recent research has demonstrated that for certain types of applications like sampled audio systems, self-timed circuits can achieve very low power consumption, because unused circuit parts automatically turn into a stand-by mode. Additional savings may be obtained by combining the self-timed circuits with a mechanism that adaptively adjusts the supply voltage to the smallest possible, while maintaining the performance requirements. This paper describes such a mechanism, analyzes the possible power savings, and presents a demonstrator chip that has been fabricated and tested. The idea of voltage scaling has been used previously in synchronous circuits, and the contributions of the present paper are: 1) the combination of supply scaling and self-timed circuitry which has some unique advantages, and 2) the thorough analysis of the power savings that are possible using this technique.>

VLSI design is viewed as a programming activity. VLSI programs are described in CP-0 (Communicating Process-level 0), essentially a subset of CSP. By means of a few simple examples the authors introduce the CP-0 program notation and discuss its compatibility with VLSI. With larger examples (block sorters and FIR filters) they demonstrate how CP-0 programs can be derived from formal specifications and how to comply with performance-related requirements.>

The authors address the compilation of VLSI programs described in CP-0 into VLSI circuits. So-called abstract circuits play a central role in the compilation method. Abstract circuits are obtained by a syntax-directed decomposition of CP-0 programs and may subsequently be implemented as delay-insensitive ('purely self-timed') circuits. The compilation method is presented together with an assessment of the performance of compiled delay-insensitive circuits based on first-time-right silicon. It is concluded that, with the compilation method presented, CP-0 programs of any complexity can be implemented as efficient VLSI circuits.>

To make silicon as an implementation medium accessible to system designers, the Philips approach requires an interface between the system-level and algorithmic concerns on the one hand and the more physical concerns on the other hand. The CP-0 programming language is proposed as such an interface. The actual design amounts to the translation of system requirements into a CP-0 program, for which the term VLSI programming is proposed. A silicon compiler subsequently transforms the CP-0 program into a VLSI layout and a test trace. Other issues considered include the implementation of delay-insensitive circuits, testing, and the use of 'zoom and pan' (ZaP) as a vehicle.>

The authors present the design of 'zoom and pan' (ZaP), a complex 160K-transistor delay-insensitive VLSI circuit. ZaP generates images from structured geometric data with a performance of a million boxes per second. A VLSI program is derived from a formal specification of ZaP though stepwise refinement and decomposition. The subsequent silicon compilation is described briefly. It is concluded that ZaP demonstrates that the design of 'systems on silicon' can be seen as a VLSI-programming activity, to be carried out by system designers.>