Search

Fully integrated CMOS frequency-modulated continuous-wave radar ICs are under development, in which computing FFTs cost a significant amount of energy. In this paper we introduce a power-efficient FFT solution which exploits that intermediate results of FFT computations typically have small amplitudes in FMCW radar systems. We propose using the sign-magnitude number representation combined with a custom, unsigned Booth multiplier that does not generate negative numbers internally, significantly decreasing switching activity. RTL power-simulation results show up to 46.45% less power usage with our sign-magnitude radix-2 FFT implementation compared to a two’s complement design, while only having a 6.67% lower maximum clock speed.

Cyber-physical control systems are typically time-triggered because the Analog to Digital (A/D) and Digital to Analog (D/A) converters are triggered by a periodic clock. This enables analytical stability analysis of closed-loop models in case the plant and controller are linear. However ensuring periodic sampling requires that a sampling period is selected larger than the Worst-Case Execution Times (WCETs) of the digital control tasks. Unfortunately, low sampling rates must be selected as a result of loose WCET bounds especially if multi-processor hardware is applied with shared data caches and SDRAM memory. In this paper we propose a model-checking based stability analysis approach for control systems that sample aperiodically. Our approach is targetting self-timed systems, where the A/D and D/A converters are driven by internal events, such as the completion of a task, which also trigger subsequent task executions. During self-timed execution the average sampling period tends to be significantly smaller than possible in time-triggered mode, and as a result the control performance is improved significantly. Self-timed systems also allow the use of a running average workload characterization of the tasks which is tighter than a WCET characterization, and which can greatly improve the accuracy of the stability analysis results. We show using two self-timed control systems that control performance in terms of stability and settling time improves for self-timed systems when the running average workload characterization is applied. Furthermore, we point at an essential feature that is needed for asymptotic stability analysis which is missing in well known model checkers such as SpaceEx.

State estimation algorithms, such as the Kalman filter, are applied for conditioning and sensor fusion in digital control loops. It is desirable that these algorithms can be executed on embedded multiprocessor systems. However this results in large worst-case execution times with a consequence that a large sampling period must selected, which degrades the estimation and control performance. In this paper, we propose a free-running state-estimation approach in which the next sample is taken as soon as the current iteration completes. The approach utilizes the particle filter algorithm to mitigate the effects of sampling jitter, introduced by the variation in the execution times of tasks. As a result of the reduced interval between subsequent sampling moments the estimation accuracy is improved. The delay introduced by the estimator in a control loop is reduced by enabling execution of the prediction step in parallel with other control tasks. We compare simulation results obtained for our approach with a Kalman filter based approach, by estimating the state of a DC motor. These results show that our approach minimizes the estimation error, as a result of sampling jitter, by up to a factor of 10. Additionally we show that the approach does not require precise knowledge of the distribution of the execution times of the tasks.

This is the appendix to the paper Temporal Analysis of Static Priority Preemptive Scheduled Cyclic Streaming Applications using CSDF Models [1]. The temporal analysis approach presented in [1] makes use of an iterative algorithm that computes so-called maximum busy periods over multiple task phases. The algorithm contains a stop criterion indicating after which iteration of the algorithm subsequent iterations do not need to be considered. The intuition behind that stop criterion is given in the paper and supplemented by a formal proof in this appendix.

Connection-oriented guaranteed-throughput mesh-based networks on chip have been proposed as a replacement for buses in real-time embedded multiprocessor systems such as software defined radios. Even with attractive features like throughput and latency guarantees they are not always used because their hardware cost tends to be higher than buses. In this paper we present a communication ring that provides throughput and latency guarantees. This ring is an attractive communication network as replacement for buses for small to medium scale embedded multiprocessor systems for real-time stream processing because of its relatively low hardware cost. We show that the data serialization of our ring makes it contention free and enables sharing of buffers which reduces the hardware cost. A further cost reduction is achieved by implementing end-to-end flow-control in software and by supporting only writes over the network. Data-flow analysis techniques are used to prove that throughput and latency guarantees can be given despite that the proposed communication ring is connectionless. We evaluated the performance and hardware cost of our communication ring using a 16 core multiprocessor system and a real-time PAL video decoder application. This design was implemented on a Virtex 6 FPGA and the ring was found to use roughly 2% of the logic cells used for the complete MPSoC design. Such a low hardware cost can justify the use of the ring in systems with low bandwidth utilization, as is the case for our PAL video decoder application which uses only 3% of the available bandwidth.

Systems with chip multi-processors are currently used for several applications that have real-time requirements. In chip multi-processor architectures, many hardware resources such as parts of the cache hierarchy are shared between cores and by using such resources, applications can significantly interfere with each other. In previous work, we showed that a single X-ray imaging streaming applications can be executed with low jitter on such systems. However, it was assumed that only one application would be running on the system, which prevents system integration where multiple real-time and best- effort applications are executing on a single chip multi-processor. In this paper, we address the limited bandwidth in the cache hierarchy, which can cause threads to interfere with each other significantly. We propose a technique that implements cache bandwidth reservation in software, by dynamically duty-cycling best-effort applications, based on their cache bandwidth usages using processor performance counters in order to control the influence of best-effort applications on real-time applications. With this technique we can control the latency increase of real- time applications that is caused by best-effort application in order to satisfy real-time requirements with a minimal reduction in best-effort performance. The results of the experiments with real- life applications indicate that we can control the increase of the latency to such an extent that we can almost completely eliminate the influence of bandwidth sharing in the cache at the cost of best-effort performance.

Parallel stream processing applications are often executed on shared-memory multiprocessor systems. Synchronization between tasks is needed to guarantee correct functional behavior. An increase in the communication granularity of the tasks in the parallel application can decrease the synchronization overhead. However using coarser-grained synchronization can result in deadlock or violation of the throughput constraint for the application in case of cyclic data dependencies. Resynchronization tries to change the synchronization behavior in order to reduce the synchronization overhead. Determining the amount of resynchronization while preventing deadlock and satisfying the throughput constraint of the application, forms a global analysis problem. In this paper we present a Linear Programming (LP) algorithm for minimizing synchronization by means of resynchronization that is based on the properties of dataflow models. We demonstrate our approach with an extended Constant Modulus Algorithm (CMA) in a beam-forming application. For this application we reduce the number of synchronization statements with 30% while having a memory constraint of 200 tokens. The algorithm which calculates this reduction takes less than 20 milliseconds for this problem instance.

Many applications contain loops with an undetermined number of iterations. These loops have to be parallelized in order to increase the throughput when executed on an embedded multiprocessor platform. This paper presents a method to automatically extract a parallel task graph based on function level parallelism from a sequential nested loop program with while loops. In the parallelized task graph loop iterations can overlap during execution. We introduce the notion of a single assignment section such that we can exploit single assignment to overlap iterations of the while loop during the execution of the parallel task graph. Synchronization is inserted in the parallelized task graph to ensure the same functional behavior as the sequential nested loop program. It is shown that the generated parallel task graph does not introduce deadlock. A DVB-T radio receiver where the user can switch channels after an undetermined amount of time illustrates the approach.

Multimedia applications process streams of values and can often be represented as task graphs. For performance reasons, these task graphs are executed on multiprocessor systems. Inter-task communication is performed via buffers, where the order in which values are written into a buffer can differ from the order in which they are read. Some existing approaches perform inter-task communication via first-in-first-out buffers in combination with reordering tasks and require applications with affne index-expressions. In our previous work, we used circular buffers with a non-overlapping read and write window, such that a reordering task is not required. However, these windows can cause deadlock for cyclic task graphs. In this paper, we introduce circular buffers with multiple overlapping windows that do not delay the release of locations and therefore they do not introduce deadlock for cyclic task graphs. We show that buffers with multiple overlapping read and write windows are attractive, because they avoid that a buffer has to be selected from which a value has to be read or into which a value has to be written. This significantly simplifies the extraction of a task graph from a sequential application. These buffers are also attractive, because a buffer capacity equal to the array size is sufficient for deadlock-free execution, instead of performing global analysis to compute sufficient buffer capacities. Our case-study presents two applications that require these buffers.

The real-time system research community has paid a lot of attention to the design of safety critical hard real-time systems for which the use of non-standard hardware and operating systems can be justified. However, stream processing applications like medical imaging systems are often not considered safety critical enough to justify the use of hard real-time techniques that would increase the cost of these systems significantly. Instead commercial off the shelf (COTS) hardware and OS are used, and techniques at the application level are employed to reduce the variation in the end-to-end latency of these imaging processing systems. In this paper, we study the effectiveness of a number of scheduling heuristics that are intended to reduce the latency and the jitter of stream processing applications that are executed on COTS multiprocessor systems. The proposed scheduling heuristics take the execution times of tasks into account as well as dependencies between the tasks, the data structures accessed by the tasks, and the memory hierarchy. Experiments were carried out on a quad core symmetric multiprocessing (SMP) Intel processor. These experiments show that the proposed heuristics can reduce the end-to-end latency with almost 60%, and reduce the variation in the latency with more than 90% when compared with a naive scheduling heuristic that does not consider execution times, dependencies and the memory hierarchy.

Modern embedded multimedia systems process multiple concurrent streams of data processing jobs. Streams often have throughput requirements. These jobs are implemented on a multiprocessor system as a task graph. Tasks communicate data over buffers, where tasks wait on sufficient space in output buffers before producing their data. For cost reasons, jobs share resources. Because jobs can share resources with other jobs that include tasks with data-dependent execution rates, we assume run-time scheduling on shared resources. Budget schedulers are applied, because they guarantee a minimum budget in a maximum replenishment interval. Both the buffer sizes as well as the budgets influence the temporal behaviour of a job. Interestingly, a trade-off exists: a larger buffer size can allow for a smaller budget while still meeting the throughput requirement. This work is the first to address the simultaneous computation of budget and buffer sizes. We solve this non-linear problem by formulating it as a second-order cone program. We present tight approximations to obtain a non-integral second-order cone program that has polynomial complexity. Our experiments confirm the non-linear trade-off between budget and buffer sizes.

This paper summarizes a special session on multicore/ multi-processor system-on-chip (MPSoC) programming challenges. The current trend towards MPSoC platforms in most computing domains does not only mean a radical change in computer architecture. Even more important from a SW developer´s viewpoint, at the same time the classical sequential von Neumann programming model needs to be overcome. Efficient utilization of the MPSoC HW resources demands for radically new models and corresponding SW development tools, capable of exploiting the available parallelism and guaranteeing bug-free parallel SW. While several standards are established in the high-performance computing domain (e.g. OpenMP), it is clear that more innovations are required for successful deployment of heterogeneous embedded MPSoC. On the other hand, at least for coming years, the freedom for disruptive programming technologies is limited by the huge amount of certified sequential code that demands for

A growing number of applications, often with real-time requirements, are integrated on the same system on chip (SoC), in the form of hardware and software intellectual property (IP). To facilitate real-time applications, networks on chip (NoC) guarantee bounds on latency and throughput. These bounds, however, only extend to the network interfaces (NI), between the IP and the NoC. To give performance guarantees on the application level, the buffers in the NIs must be sufficiently large for the particular application. At the same time, it is imperative to minimise the size of the NI buffers, as they are major contributors to the area and power consumption of the NoC. Existing buffer-sizing methods use coarse-grained application models, based on linear traffic bounds or periodic producers and consumers, thus severely limiting their applicability. In this work, the authors propose to capture the behaviour of the NoC and the applications using a dataflow model. This enables one to verify the temporal behaviour and to compute buffer sizes using existing dataflow analysis techniques. The authors show what is required from the NoC architecture and demonstrate how to construct an NoC model, with multiple levels of detail. Using the proposed model, buffer sizes are determined for a range of SoC designs with a run time comparable to existing analytical methods, and results comparable to exhaustive simulation. For an application case study, where existing buffer-sizing methods are not applicable, the proposed model enables the verification of end-to-end temporal behaviour. © 2009 The Institution of Engineering and Technology. U7 - Cited By (since 1996): 2 U7 - Export Date: 5 February 2010 U7 - Source: Scopus

A network on chip (NoC) with end-to-end flow control is modelled by a cyclo-static dataflow graph. Using the proposed model together with state-of-the-art dataflow analysis algorithms, we size the buffers in the network interfaces. We show, for a range of NoC designs, that buffer sizes are determined with a run time comparable to existing analytical methods, and results comparable to exhaustive simulation.

Streaming applications are often implemented as task graphs, in which data is communicated from task to task over buffers. Currently, techniques exist to compute buffer capacities that guarantee satisfaction of the throughput constraint if the amount of data produced and consumed by the tasks is known at design-time. However, applications such as audio and video decoders have tasks that produce and consume an amount of data that depends on the decoded stream. This paper introduces a dataflow model that allows for data-dependent communication, together with an algorithm that computes buffer capacities that guarantee satisfaction of a throughput constraint. The applicability of this algorithm is demonstrated by computing buffer capacities for an H.263 video decoder.

Multimedia applications, executed by embedded multiprocessor systems, can in some cases be represented as task graphs, with the tasks containing nested loop programs. The nested loop programs communicate via arrays and can be executed on different processors. Typically an array can be communicated via a circular buffer with a capacity smaller than the array. For such buffers, the communicating nested loop programs have to synchronize and a sufficient buffer capacity needs to be computed. In a circular buffer we use a write and a read window to support rereading, out-of-order reading or writing, and skipping of locations. A cyclo static dataflow model is derived from the application and used to compute buffer capacities that guarantee deadlock free execution. Our case-study applies circular buffers in a Digital Audio Broadcasting channel decoder application, where the frequency deinterleaver reads according to a non-affine pseudo-random function. For this application, buffer capacities are calculated that guarantee deadlock free execution.

Streaming applications are often implemented as task graphs. Currently, techniques exist to derive buffer capacities that guarantee satisfaction of a throughput constraint for task graphs in which the inter-task communication is data-independent, i.e. the amount of data produced and consumed is independent of the data values in the processed stream. This paper presents a technique to compute buffer capacities that satisfy a throughput constraint for task graphs with data dependent inter-task communication, given that the task graph is a chain. We demonstrate the applicability of the approach by computing buffer capacities for an MP 3 playback application, of which the MP 3 decoder has a variable consumption rate. We are not aware of alternative approaches to compute buffer capacities that guarantee satisfaction of the throughput constraint for this application.

In modern multiprocessor systems, processors can be stalled by inter-task communication when reading from a remote buffer. This paper presents a solution for the inter-task communication, that has a minimal impact on the performance of the system, hides the inter-task communication latency without requiring additional hardware. The solution applies to jobs, represented as task graphs, where the tasks are nested loop programs. Buffers are allocated in scratch-pad memories of the consuming tasks to provide low latency read access. For the nested loop programs, minimal buffer sizes can be determined to cover all possible communication patterns. The added computational complexity is low, as the solution adds only a few operations to the nested loop programs.

Our Multi Processor System on Chip (MPSoC) template provides processing tiles that are connected via a network on chip. A processing tile contains a processing unit and a Scratch Pad Memory (SPM). This paper presents the Omphale tool that performs the first step in mapping a job, represented by a task graph, to such an MPSoC, given the SPM sizes as constraints. Furthermore a memory tile is introduced. The result of Omphale is a Cyclo Static DataFlow (CSDF) model and a task graph where tasks communicate via sliding windows that are located in circular buffers. The CSDF model is used to determine the size of the buffers and the communication pattern of the data. A buffer must fit in the SPM of the processing unit that is reading from it, such that low latency access is realized with a minimized number of stall cycles. If a task and its buffer exceed the size of the SPM, the task is examined for additional parallelism or the circular buffer is partly located in a memory tile. This results in an extended task graph that satisfies the SPM size constraints.

A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure, which means that tasks wait for space in output buffers. Consequently buffer capacities affect the throughput. This requires the derivation of buffer capacities that both result in a satisfaction of the throughput constraint, and also satisfy the constraints on the maximum buffer capacities. Existing exact solutions suffer from the computational complexity that is associated with the required conversion from a cyclo-static dataflow graph to a single-rate dataflow graph. In this paper we present an algorithm, with polynomial computational complexity, that does not require this conversion and that obtains close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our multi-processor system. For this application, we see that a cyclo-static dataflow model can reduce the buffer capacities by 50% compared to a multi-rate dataflow model.

In order to obtain a cost-efficient solution, tasks share resources in a Multi-Processor System-on-Chip. In our architecture, shared resources are run-time scheduled. We show how the effects of Latency-Rate servers, which is a class of run-time schedulers, can be included in a dataflow model. The resulting dataflow model, which can have an arbitrary topology, enables us to provide guarantees on the temporal behaviour of the implementation. Traditionally, the end-to-end behaviour of multiple Latency-Rate servers has been analysed with Latency-Rate analysis, which is a Network Calculus. This paper bridges a gap between Network Calculi and dataflow analysis techniques, since we show that a class of run-time schedulers can now be included in dataflow models, or, from a Network Calculus perspective, that restrictions on the topology of graphs that include run-time scheduling can be removed.

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. Experiments with artificial test-cases indicate that the computed FIFO capacities become more conservative if the desired throughput gets closer to the maximum throughput. The run-time of our algorithm for an H263 video decoder test-case was 14 seconds.

A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure, which means that tasks wait for space in output buffers. Consequently buffer capacities affect the throughput. This requires the derivation of buffer capacities that both result in a satisfaction of the throughput constraint, and also satisfy the constraints on the maximum buffer capacities. Existing exact solutions suffer from the computational complexity that is associated with the required conversion from a cyclo-static dataflow graph to a single-rate dataflow graph. In this paper we present an algorithm, with polynomial computational complexity, that does not require this conversion and that obtains close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our multi-processor system. For this application, we see that a cyclo-static dataflow model can reduce the buffer capacities by 50% compared to a multi-rate dataflow model.

The throughput analysis technique described in this paper is intended for applications that are executed on heterogeneous embedded multiprocessor systems. A mix of runtime arbitration policies is often applied in these systems. Backpressure prevents buffer overflow because tasks do not start before sufficient buffer space is available. We show that the effects of run-time arbitration can be included in the response time of the actors of a multi-rate dataflow model. Given this model we compute conservative estimates of the arrival times of data in the system. Furthermore, we show that latency constraints can be included in a multi-rate dataflow model. The analysis technique is demonstrated on a real-life car-radio application. In this application two independent streams are processed. One of these streams has a latency constraint.

A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multiprocessor system, we apply back-pressure, which means that tasks wait for space in output buffers. Consequently buffer capacities affect the throughput. This requires the derivation of buffer capacities that both result in a satisfaction of the throughput constraint, and also satisfy the constraints on the maximum buffer capacities. Existing exact solutions suffer from the computational complexity that is associated with the required conversion from a cyclo-static dataflow graph to a single-rate dataflow graph. In this paper we present an algorithm, with linear computational complexity, that does not require this conversion and that strives to obtain close to minimal buffer capacities. The algorithm is applied to an MP3 playback application that is mapped on our multi-processor system.

In the signal processing domain, dataflow graphs [2] [10] and their associated analysis techniques are a well-accepted modeling paradigm. The vertices of a dataflow graph represent functionality and are called actors, while the edges model which actors communicate with each other. Traditionally, these actors have been scheduled in a static order or in a fully static fashion [9] [16]. However, for firm real-time applications, run-time scheduling is required if there are tasks, that operate on different streams and share the same resource, for which either the execution time or the execution rate is unknown or impractical to bound.

A key step in the design of multi-rate real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure as caused by bounded buffers in order to control jitter. This requires the derivation of buffer capacities that both satisfy the temporal constraints as well as constraints on the buffer capacity. Existing exact solutions suffer from the computational complexity associated with the required conversion from a multi-rate dataflow graph to a single-rate dataflow graph. In this paper we present an algorithm, with linear computational complexity, that does not require this conversion and that determines close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our network based multi-processor system.