This paper presents a system design study for wearable sensor devices intended for healthcare and lifestyle applications based on ECG, EEG and activity monitoring. In order to meet the low-power requirement of these applications, a dual-core signal processing system is proposed which combines an ultra-low-power bio-medical Application Specific Instruction-set Processor (BioASIP) and a low-power general-purpose micro-controller (MSP430). To validate the merits of the proposed architecture, system-level power analysis and trade-offs are conducted using real hardware measurements of an ECG R-peak detection application. The results show that the proposed dual-core architecture consumes around 65.38µW, about 25.8x smaller than an MSP430-only approach. Out of 65.38µW, the BioASIP consumes only 11µW and the rest is used in the analog front-end, A/D conversion, and control tasks.

Efficient use of the memory hierarchy is critical for achieving high performance in a multiprocessor system- on-chip. An external memory that is shared between processors is a bottleneck in current and future systems. Cache misses and a large cache miss penalty contribute to a low processor utilisation. In this paper, we describe a novel cache optimisation technique to reduce instruction and data cache misses for streaming applications. The instruction and data locality are improved by executing a task multiple times before moving to the next task. Furthermore, we introduce a dataflow model that is used to trade-off the number of cache misses against end-to-end latency and memory usage. For our industrial application, which is a Digital Radio Mondiale receiver, the number of cache misses is reduced with a factor 4.2.

This work presents adomain-specificmemory subsystem based on a two-level memory hierarchy. It targets the application domain of video post-processing applications including video enhancement and format conversion. These applications are based on motion compensation and/or broad class of content adaptive filtering to provide the highest quality of pictures. Our approach meets the required performance and has sufficient flexibility for the application domain. It especially aims at the implementation-wise most challenging applications: compute-intensive and bandwidth-demanding applications that provide the highest quality at high picture resolutions. The lowest level of the memory hierarchy, closest to the processing element, the L0 scratchpad, is organized specifically to enable fast retrieval of an arbitrarily positioned 2-D block of pixels to the processing element. To guarantee the performance, most of its addressing logic is hardwired, leaving a user a set of API for initialization and storing/loading the data to/from the L0 scratchpad. The next level of the memory hierarchy, the L1 scratchpad, minimizes the off-chip memory bandwidth requirements. The L1 scratchpad is organized specifically to enable efficient aligned block-based accesses. With lower data rates compared to the L0 scratchpad and aligned block access, software-based addressing is used to enable full flexibility. The two-level memory hierarchy exploits prefetching to further improve the performance.

In an embedded multiprocessor system the minimum throughput and maximum latency of real-time applications are usually derived given the worst-case execution time of the software tasks. Derivation of the worst-case execution time becomes easier if it is independent of the available communication bandwidth. In this paper we show that the worst-case execution time of tasks does not depend on communication bandwidth if a Communication Assist (CA) is applied, despite that memory ports are shared. Furthermore we show that adding a CA increases the processor utilization and reduces the required communication bandwidth. Finally we show that the difference between the measured and computed worst-case processor utilization is less than 6%, for our MP3 playback application.

Programmable multiprocessor systems-on-chip are becoming the preferred implementation platform for embedded streaming applications. This enables using more software components, which leads to large and frequent dynamic variations of data-dependent execution times. In this context, accurate and conservative prediction of execution times helps in maintaining good audio/video quality and reducing energy consumption by dynamic evaluation of the amount of on-chip resources needed by applications. To be effective, multiprocessor systems have to employ the available parallelism. The combination of task-level parallelism and task delay variations makes predicting execution times a very hard problem. So far, under these conditions, no appropriate techniques exist for the conservative prediction of execution times with the required accuracy. In this paper, we present a novel technique for this problem, exploiting the concept of scenario-based prediction, and taking into account the transient and periodic behavior of scenarios and the effect of scenario transitions. In our MPEG-4 shape-decoder case study, we observe no more than 11% average overestimation.

Embedded media applications have real-time constraints such as throughput and latency. In this paper we show that a tight bound on the minimum throughput can be computed with a cyclo static dataflow model that represents the application executed on the multiprocessor system-on-chip. We identify the sources that affect the tightness of the computed bound. One source of inaccuracy is that we do not implement, for efficiency reasons, the firing rule of an actor. We will show that this is allowed for a static order task schedule and that the computed bound is a conservative estimate of the actual minimum throughput. For our case study the computed throughput bound is 10.1% lower than the throughput measured with cycle accurate simulation.

Soft real-time applications that process data streams can often be intuitively described as dataflow process networks. In this paper we present a novel analysis technique to compute conservative estimates of the required buffer capacities in such process networks. With the same analysis technique scheduler settings can be verified. Unlike many other soft real-time analysis techniques, it is guaranteed that the desired throughput is obtained for the input stream that is used to characterize the application.

Modern day applications require use of multi-processor systems for reasons of scalability and power efficiency. As more and more applications are integrated on a single device, mapping and analyzing them on a multi-processor system becomes a multi-dimensional problem. Each possible set of applications that can be active simultaneously leads to a different use-case (also referred to as scenario) that the system has to be verified and tested for. Analyzing the feasibility and resource utilization of all possible use-cases is very demanding and often infeasible. In this paper, we highlight the issue of composability, i.e. being able to analyze applications in isolation while still reason about their overall behavior. We observe that arbitration plays an important role in this analysis. We compare two simple, yet commonly used arbitration mechanisms, and highlight the properties that are important for such analysis. We conclude that none of this arbitration mechanism is ideal for such an analysis and propose some variations to make them more suited for the analysis

With the growing complexity of new multimedia applications and the parallel execution enabled by multiprocessor architectures, quality-of-service (QoS) management for modern network-on-chip (NoC) systems becomes relevant. This paper presents an approach for efficient usage of platform resources and simultaneously controlling overall system performance, when multiple applications are active. Therefore, on top of the conventional QoS, we introduce an algorithm for setting quality levels of parallel executed applications on a multiprocessor network-on-chip. The new concept is a hierarchical system, where an application manager negotiates with the resource management to jointly optimize the quality of individual and overall application settings. The proposed QoS manager concept was successfully evaluated by an experimental set-up, employing two independent video-object decoders, a background sprite decoder from the MPEG-4 standard and an abstract audio object. This simultaneous execution of four independent applications was mapped on a simulator based on AEthereal network and eight ARM7 processors executed with a clock-cycle true simulator. The proposed distributed QoS management decreases the complexity of the overall management and improves the transparency and responsibilities in the decision taking.

Growing complexity of multiprocessor systems on chip (MP-SoC) requires future communication resources that can only be met by highly scalable architectures. Networks-on-Chip (NoCs) offer this scalability and other advantages like modularity, quality-of-service (QoS), possibly smaller area footprint and lower power dissipation. Although many papers describe the advantages of NoCs and describe techniques to apply NoCs on certain application domains, few have actually employed the complete design chain to make a netlist level implementation and area comparison (Steenhof et al., 2006) and (Angiolini et al., 2006). This paper describes the application of the AEligthereal NoC to an existing bus-based MP-SoC design and an area comparison with the original interconnects structure down to netlist level

This paper focuses on stream-oriented applications with real-time constraints for on-chip multiprocessors, e.g. video/audio coding. In such an application the same function, e.g. frame decoding, is executed over and over again. In general, the execution time is data-dependent. Thus, at run-time a situation may arise when the execution time exceeds the deadline specified in the real-time constraints and a preventive action should be taken. For stream-oriented applications pipelined execution of the function is very important for achieving the required throughput. An accurate execution time estimation method supporting pipelined execution on a multiprocessor architecture is proposed in this paper

An embedded multiprocessor that can run multiple hard-real-time (HRT) jobs simultaneously has to guarantee that enough resources are available to meet the timing constraints. It is essential that both application model and hardware be tailored to this goal. Moreover, suitable resource allocation and scheduling are needed. This paper proposes a resource allocator that gives guarantees for HRT streaming applications. Because new jobs arrive during operation, resource allocation is performed at run-time. This provides admission control. Resource budget enforcement is handled by local schedulers. We formalize our resource allocation problem and show that it is NP-complete. We developed heuristics to tackle the problem during runtime and evaluated them. A modified First-fit Vector Bin-Packing algorithm provides a good solution; it can allocate 95% of the resources, while handling a large number of job arrivals and departures on a heavily loaded system.

In this paper we derive the end-to-end temporal behavior of real-time applications that are described as process networks. We demonstrate that a tight upper bound on the arrival time of data can be derived by simulation of this process network. We also show that the effects of arbitration can be taken into account if resources are reserved. For an H263 video decoder example we derive by means of simulation the settings of the schedulers and the buffer capacities. We arrive at the conclusion that for this application a close to maximum throughput is obtained with small buffers if only one process is executed on each processor. Larger buffers are needed if processors are shared and processes are executed during long time-slices.

The gap between application specific integrated circuits (ASICs) and general-purpose programmable processors in terms of performance, power, cost and flexibility is well known. Application specific instruction-set processors (ASIPs) bridge this gap. In this work, we demonstrate the key benefits of ASIPs for several video applications. One of the most compute- and memory-intensive functions in video processing is motion estimation (ME). The focus of this work is on the design of a ME template, which is useful for several video applications like video encoding, obstacle detection, picturerate up-conversion, 2-D-to-3-D video conversion, etc. An instruction-set suitable for performing a variety of ME functions is developed. The ASIP is based on a very long instruction word (VLIW) processor template and meets low-power and low-cost requirements still providing the flexibility needed for the application domain. The ME ASIP design consumes 27 mW and takes an area of 1.1 mm/sup 2/ in 0.13 /spl mu/m technology performing picturerate up-conversion, for standard definition (CCIR601) resolution at 50 frames per second.

Networks on chip (NoCs) are a scalable interconnect solution for multiprocessor systems on chip. We propose a generic reconfigurable online event-based NoC monitoring service, based on hardware probes attached to NoC components, offering run-time observability of NoC behavior and supporting system-level debugging. We present a probe architecture, its programming model, traffic management strategies, and a cost analysis. We prove feasibility via a prototype implementation for the Æthereal NoC. Two MPEG NoC examples show that the monitoring service area, without advanced optimizations, is 17--24% of the NoC area. Two realistic monitoring examples show that monitoring traffic is several orders of magnitude lower than the 2GB/s/link raw bandwidth.

The demands in terms of processing performance, communication bandwidth and real-time throughput of new generation mobile communication applications (mobile and base-stations) are much higher than today's programmable processing architectures can deliver. On the other hand standards and market uncertainties, nonrecurring engineering costs, and lack of access to (or knowledge of) application IP will require the next generation of embedded computing platforms to be fully programmable. In terms of silicon cost and power, practical yet fully programmable embedded computing platforms are enabled by reconfigurable processors that replace fixed ASICs in current standard platforms. This paper explains the concepts behind a novel reconfigurable WCDMA rake receiver and gives benchmark results. The proposed RAKE receiver enables a high performance, yet flexible computing platform for WCDMA.

We consider a dynamic application running on a multiprocessor network-on-chip as a set of independent jobs, each job possibly running on multiple processors. To provide guaranteed quality and performance, the scheduling of jobs, jobs themselves and the hardware must be amenable to timing analysis. For a certain class of applications and multiprocessor architectures, we propose exact timing models that effectively co-model both the computation and communication of a job. The models are based on interprocessor communication (IPC) graphs [4]. Our main contribution is a precise model of network-on-chip communication, including buffer models. We use a JPEG-decoder job as an example to demonstrate that our models can be used in practice to derive upper bounds on the job execution time and to reason about optimal buffer sizes.

Although FPGAs are a cost-efficient alternative for both ASICs and general purpose processors, they still result in designs which are more than an order of magnitude more costly and slower than their equivalents implemented in dedicated logic. This efficiency gap makes FPGAs less suitable for high-volume cost-sensitive applications (e.g. embedded systems).We show that the intrinsic cost of traditional general-purpose FPGAs can be reduced if they are designed to target an application domain or a class of applications only. We propose a method of the application-domain characterization and apply it to characterize DSP. A novel FPGA logic block architecture derived based on such an analysis, and which exploits properties of target applications, is presented. Its key feature is the 'mixed-level granularity' being a trade-off between fine and coarse granularity required for the implementation of datapath and random logic functions, respectively. This leads to a factor of four improvement in the LUT memory size compared to commercial FPGAs, and, assuming a standard-cell implementation, a 1.6-2.8 lower datapath mapping cost. A modified mixed-grain architecture with the ALU-like functionality reduces the LUT memory size by a factor of 16 compared to commercial FPGAs, and mapped onto standard cells has a 1.9-3.3 times higher datapath mapping efficiency. For these reasons, the proposed FPGA architectures may be an interesting alternative to the traditional general-purpose FPGA devices, especially if characteristics of a target application domain are known a priority.

Motion estimation algorithms play a key role in picture-rate up-conversion. To realise high quality interpolated images, while keeping the processing requirements low, we analyse the following parameters of the motion estimation algorithm: the number of motion estimation iterations per input image pair and the image scanning order of individual iterations. Furthermore, we tackle the issue of the optimal selection of the motion vector candidates. The selected motion estimation algorithm is the three-dimensional recursive search (3DRS) block matcher that offers a smooth and accurate motion vector field at relatively low computational cost.

We advocate a network on silicon (NOS) as a hardware architecture to implement communication between IP cores in future technologies, and as a software model in the form of a protocol stack to structure the programming of NOSs. We claim guaranteed services are essential. In the ETHEREAL NOS they pervade the NOS as a requirement for hardware design, and as foundation for software programming.

Turbo decoding offers outstanding error correcting capabilities, that will be used in wireless applications like the Universal Mobile Telecom Standard (UMTS). However the algorithm is very computational intensive, and therefore an implementation on a general purpose programmable DSP results in a power consumption which reduces the applicability of turbo decoding in hand-held applications. In this paper we present a solution based on a layered processing architecture. This architecture includes an application specific Very Long Instruction Word (VLIW) processor, a data flow processor, and hard-wired execution units in a hierarchical way. The power consumption of this solution is an order of magnitude better than the implementation on a current state of the art, power efficient general purpose DSP.

With the ongoing advancements in VLSI technology the performance of an embedded system is determined to a large extent by the communication of data and instructions. This results in new methods for on- and off-chip communication and caching schemes. In this paper we use an arbitration scheme that exploits the characteristics of continuous 'media' streams while minimizing the latency for random (e.g. CPU) memory accesses to background memory. We also introduce a novel caching scheme for a stream-based multiprocessor architecture, to limit as much as possible the amount of on-chip buffering required to guarantee the throughput of the continuous streams. With these two schemes we can build an architecture for media processing with optimal flexibility at run-time while performance guarantees can be determined at compile-time.

Code generation methods for digital signal processors are increasingly hampered by the combination of tight timing constraints imposed by signal p processing applications and resource constraints implied by the processor architecture. In particular, limited resource availability (e.g.registers) poses a problem for traditional methods that perform code generation in separate stages (e.g., scheduling followed by register binding). This separation often results in suboptimality (or even infeasibility) of the generated solutions because it ignores the problem of phase coupling (e.g., since value lifetimes are a result of scheduling, scheduling affects the solution space for register binding). As a result, traditional methods need an increasing amount of help from the programmer (or designer) to arrive at a feasible solution. Because this requires an excessive amount of design time and extensive knowledge of the processor architecture, there is a need for automated techniques that can cope with the different kinds of contraints during scheduling. By exploiting these constraints to prune the schedule search space, the scheduler is often prevented from making a decision that inevitably violates one or more constraints. FACTS is a research tool developed for this purpose. In this paper we will elucidate the philosophy and concepts of FACTS and demonstrate them on a number of examples.

Code generation methods for digital signal processing (DSP) applications are hampered by the combination of tight timing constraints imposed by the performance requirements of DSP algorithms and resource constraints imposed by a hardware architecture. In this paper, we present a method for register binding and instruction scheduling based on the exploitation and analysis of the combination of resource and timing constraints. The analysis identifies implicit sequencing relations between operations in addition to the preceding constraints. Without the explicit modeling of these sequencing constraints, a scheduler is often not capable of finding a solution that satisfies the timing and resource constraints. The presented approach results in an efficient method to obtain high-quality instruction schedules with low register requirements.

The demands in terms of processing performance, communication bandwidth and real-time throughput of many multimedia applications are much higher than today's processing architectures can deliver. The PROPHID heterogeneous multiprocessor architecture template aims to bridge this gap. The template contains a general purpose processor connected to a central bus, as well as several high-performance application domain specific processors. A high-throughput communication network is used to meet the high bandwidth requirements between these processors. In this network multiple time-division-multiplexed data streams are transferred over several parallel physical channels. This paper presents a method for guaranteeing the throughput for hard-real-time streams in such a network. At compile time sufficient bandwidth is assigned to these streams. The assignment can be determined in polynomial time. Remaining bandwidth is assigned to soft-real-time streams at run time. We thus achieve efficient stream communication with guaranteed performance.

Code generation methods for DSP applications are hampered by the combination of tight timing constraints imposed by the performance requirements of DSP algorithms, and resource constraints imposed by a hardware architecture. In this paper we present a method for register binding and instruction scheduling based on the exploitation and analysis of resource and timing constraints. The analysis identifies sequencing constraints between operations additional to the precedence constraints. Without the explicit modeling of these sequencing constraints, a scheduler is often not capable of finding a solution that satisfies the timing, resource and register constraints. The presented approach results in an efficient method of obtaining high quality instruction schedules with low register requirements.

PROPHID is a design method aiming at high-performance systems with a focus on high-throughput signal processing for multimedia applications. The processing and communication bandwidth requirements of such systems are very high. To obtain a good balance between performance, programmability and efficiency in terms of speed, area and power PROPHID uses a novel heterogeneous multi-processor architecture template which exploits task-level concurrency. A general purpose processor aimed at control-oriented tasks and low to medium-performance signal processing tasks, as well as application domain specific processors aimed at high-performance signal processing tasks are available in this template. Next to a central control-oriented bus a special high-throughput communication network is used to meet the high bandwidth requirements of the application domain specific processors. This paper discusses the characteristics and advantages of the PROPHID architecture showing that high performance is obtained by embedding multiple autonomous data-driven processors in a stream-based communication environment.

Application domain specific DSP cores are becoming increasingly popular due to their advantageous trade--off between flexibility and cost. However, existing code generation methods are hampered by the combination of tight timing and resource constraints, imposed by the throughput requirements of DSP algorithms together with a fixed core architecture. In this paper, we present a method to model resource and instruction set conflicts uniformly and statically before scheduling. With the model we exploit the combination of all possible constraints, instead of being hampered by them. The approach results in an exact and run time efficient method to solve the instruction scheduling problem, which is illustrated by real life examples. 1. Introduction Predefined DSP cores which are tuned towards specific application domains are becoming increasingly popular, due to their advantageous trade--off between flexibility and cost. Such a core is relatively flexible in comparison to an ASIC: differen...

This paper discusses improved force-directed scheduling and its application in the design of high-throughput DSP systems, such as real-time video VLSL circuits. We present a mathematical justification of the technique of force-directed scheduling, introduced by Paulin and Knight (1989), and we show how the algorithm can be used to find cost-effective time assignments and resource allocations, allowing trade-offs between processing units and memories. Furthermore, we present modifications that improve the effectiveness and the efficiency of the algorithm. The significance of the improvements is illustrated by an empirical performance analysis based on a number of problem instances.>

A multiport memory allocation problem for hierarchical, i.e. multi-dimensional, data streams is described. Memory allocation techniques are used in high level synthesis for foreground and background memory allocation, the design of data format converters, and the design of synchronous inter-processor communication hardware. The techniques presented in this paper differ from other approaches in the sense that data streams are considered to be design entities and are not expanded to individual samples. A formal model for hierarchical data streams is given and a memory allocation algorithm is presented. The algorithm comprises two steps: data routing and assignment of signal delays to memories. A number of sub-problems are formulated as ILP programs. In the presented form, the allocation algorithm only considers interconnect costs, but memory size and other cost factors can be taken into account. The presented work is implemented in the memory allocation tool MEDEA which is part of the PHIDEO synthesis system.

Force-directed scheduling is a technique which schedules operations under time constraints in order to achieve schedules with a minimum number of resources. The worst case time complexity of the algorithm is cubic in the number of operations. This is due to the computation of the changes in the distribution functions needed for the force calculations. An incremental way to compute the changes in the distribution functions, based on gradual time-frame reduction, is presented. This reduces the time complexity of the algorithm to quadratic in the number of operations, without any loss in effectiveness or generality of the algorithm. Implementations show a substantial CPU-time reduction of force-directed scheduling, which is illustrated by means of some industrially relevant examples.>

Functions executed by a multifunctional processing unit (PU) correspond to clusters of operations in the specification, which are represented as signal flow graphs (SFGs). Because of high-throughput demands, the operations of each SFG are executed in parallel. Since operations for only one of the SFGs are executed at a given time, operations belonging to different SFGs can be executed on the same operator. Here, the most important part of the mapping of several SFGs onto one PU, which is the assignment of the SFGs operations to the PU's operators, given a number of allocated operators, is considered. The problem is to find an operator assignment that minimizes the silicon area that is occupied by the PU's interconnection consisting of multiplexers and wires. An approach based on local search algorithms such as iterative improvement and simulated annealing is presented. Although these algorithms are known to be generally applicable, it is shown that detailed knowledge of the operator assignment problem is required to obtain good results within acceptable CPU time limits for large problem instances.>

The state of the art of compiling digital signal processing (DSP) algorithms into silicon is discussed. It is indicated how digital signal processing differs from numerical data processing, including the consequences for the synthesis tools. On the basis of a broad range of DSP applications, four classes of architectures are then distinguished to serve as templates for four different synthesis systems. Although each of these four silicon compilers is tuned to a specific class of applications in order to generate area-efficient chips, they all accept as input the same behavioral DSP specification. The four selected architectural styles are best characterized by hard-wired bit-serial data-paths, microcoded multiprocessors, cooperating bit-parallel data-paths, and regular arrays. The characteristics of the first three architectures are treated in more detail in a discussion of three different Cathedral synthesis environments for their respective design. A fourth Cathedral environment, aiming at the synthesis of regular arrays, is still in an early stage of development and is not discussed. The claims for the compilers are substantiated by typical designs.>

A novel methodology is proposed for the data-path definition and assignment for high-throughput front-end audio, image, and video applications. The technique is based on the concept of the identification of application-specific units that can solve the computational bottlenecks of an algorithm in an efficient way. An algorithm for the automatic assignment of operations on these specific units is presented. A test vehicle taken from the video field demonstrates the proposed method.>

A 2µm CMOS Digital Signal Processor (PCB5010 / PCB5011), capable of eight million instructions per second (8MIPS), and up to 6 concurrent operations in each instruction will be described [1]. This high throughput results from a highly parallel architecture (see Fig. 1) with high-speed data handling capability. It contains two 16b data buses, two primary execution units, five I/O interfaces, a data ROM, two data RAMs, and flexible addressing of on and off-chip memory using three address computation units. Benchmarks show a two to six times improvement in overall performance over its predecessors.

A set of three custom-designed LSI circuits implements harmonic-sieve pitch extraction as can be used in vocoders. The set consists of a segmentation buffer for 256 speech samples, a discrete Fourier transform processor and a 16-bit micro-computer. In the application of a DFT vocoder, a pitch value can be extracted every 10 ms.