Polar encoding is the first information coding method that has been proven to achieve channel capacity for binary-input discrete memoryless channels. Since its introduction, much research has been done on improving decoding performance, execution time and energy efficiency. Classic belief propagation uses radix-2 decoding, but a recent study proposed radix-4 decoding which reduces memory usage by 50%. However a drawback is its higher computational complexity, negatively impacting energy usage and throughput. In this paper we present an energy-efficient radix-4 belief propagation polar decoder architecture that uses a new sign-magnitude adder that does not require conversion to two's complement and back. On top of that we also propose using clock gating of input values by checking if all$R$inputs of the decoder are zero. These two key contributions lead to a more energy -efficient design that is smaller and has higher maximum clock speed and throughput. Post-layout simulation results show that compared to the previously proposed 1024-bit radix-4 belief propagation polar code decoder, our decoder uses between 30.22 % and 32.80 % less power and is 5.2 % smaller at the same clock speed. Also, our design can achieve a 15.7% higher clock speed at which it is still up to 10.76% more power efficient and 4.8% smaller.

In this paper, we propose a novel framework called DeepMLE, which gives a solution to the single-snapshot Direction Of Arrival (DOA) estimation problem, up to 4 distinct targets, using a radar equipped with a Minimum Redundancy antenna Array (MRA). This framework works by fusing a Deep Learning (DL) technique - 1D Residual Neural Network (1D ResNet) - with a classical DOA algorithm - Maximum Likelihood Estimation (MLE). By combining two very different approaches, we can address some of their limitations, such as the computational complexity of MLE. On the other hand, our proposed Deep-MLE uses MLE to correct, to some degree, the estimations made by the Neural Network (NN). The results from our framework are promising as it seems to be a viable solution to the DOA estimation problem, having a better performance than models using pure MLE or NN.

Hybrid automata are an emerging formalism used to model sampled-data control Cyber-Physical Systems (CPS), and analyze their behavior using reachability analysis. This is because hybrid automata provide a richer and more flexible modeling framework, compared to traditional approaches. However, modern state-of-the-art tools struggle to analyze such systems, due to the computational complexity of the reachability algorithm, and due to the introduced overapproximation error. These shortcomings are largely attributed (but not limited) to the aggregation of sets.

Disributed control systems often exhibit aperiodic sampling behavior due to varying communication delays and execution times. In such cases traditional analysis methods fall short because the functional and temporal behaviors need to be analyzed simultaneously. Therefore such systems are often modeled by Hybrid Automata (HA) with clock and non-clock variables, and verified using reachability analysis. However, modern reachability tools introduce a large overapproximation error because non-clock variables, as well as clock variables, are equally treated by the algorithm.

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.

There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow with auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected HSDFamodels into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models.

Bounding the latency of real-time multiprocessor applications is crucial for safety-critical systems. Several approximative analysis approaches exist that can efficiently analyze the latency. However, these approaches produce pessimistic latency results and do not exploit buffer sizing nor exploit additional sequence constraints to reduce the latency. More accurate latency analysis results can be obtained using model checking of timed-automata, however, at the cost of a typically excessive run-time.

Component-based and model-based reasonings are key concepts to address the increasing complexity of real-time systems. Bounding abstraction theories allow to create efficiently analyzable models that can be used to give temporal or functional guarantees on non-deterministic and non-monotone implementations. Likewise, bounding refinement theories allow to create implementations that adhere to temporal or functional properties of specification models. For systems in which jitter plays a major role, both best-case and worst-case bounding models are needed. In this paper we present a bounding abstraction-refinement theory for real-time systems. Compared to the state-of-the-art TETB refinement theory, our theory is less restrictive with respect to the automatic lifting of properties from component to graph level and does not only support temporal worst-case refinement, but evenhandedly temporal and functional, best-case and worst-case abstraction and refinement.

Real-time stream processing applications executed on embedded multiprocessor systems often have strict throughput and latency constraints. Violating these constraints is undesired and temporal analysis methods are therefore used to prevent such violations. These analysis methods use abstractions of the analyzed applications to simplify their temporal analysis.

Stream processing applications executed on multiprocessor systems usually contain cyclic data dependencies due to the presence of bounded FIFO buffers and feedback loops, as well as cyclic resource dependencies due to the usage of shared processors. In recent works it has been shown that temporal analysis of such applications can be performed by iterative fixed-point algorithms that combine dataflow and response time analysis techniques. However, these algorithms consider resource dependencies based on the assumption that tasks on shared processors are enabled simultaneously, resulting in a significant overestimation of interference between such tasks. This paper extends these approaches by integrating an explicit consideration of precedence constraints with a notion of offsets between tasks on shared processors, leading to a significant improvement of temporal analysis results for cyclic stream processing applications. Moreover, the addition of an iterative buffer sizing enables an improvement of temporal analysis results for acyclic applications as well. The performance of the presented approach is evaluated in a case study using a WLAN transceiver application. It is shown that 56% higher throughput guarantees and 52% smaller end-to-end latencies can be determined compared to state-of-the-art.

Programming stream processing multiprocessor systems is a challenging task especially if there are real-time requirements. Therefore it is desirable to use formal models and real-time analysis techniques. However the classical periodic task-model does not match well with stream processing applications which results in suboptimal designs.

Real-time stream processing applications, such as Software Defined Radio applications, are often executed concurrently on multiprocessor systems. A unified data flow model and analysis method have been proposed that can be used to simultaneously determine the amount of pipeline and coarse-grained data parallelism required to meet the temporal constraints of such applications. However, this unified model is only defined for Synchronous Data Flow (SDF) graphs. Defining a unified model for a more expressive model such as Cyclo-Static Data Flow (CSDF) is not possible, because auto-concurrency can cause a time-dependent order of tokens and dependencies.

Modal real-time stream processing applications often contain cyclic dependencies and are typically executed on multiprocessor systems with processor sharing. Most real-time operating system kernels for these systems support Static Priority Pre-emptive (SPP) scheduling, however there is currently no suitable temporal analysis technique available for this type of systems.

Many embedded multiprocessor systems have hard real-time requirements which should be guaranteed at design time by means of analytical techniques that cover all cases. It is desirable to evaluate the correctness and tightness of the analysis results by means of simulation. However, verification of the analytically obtained results is hampered by the lack of a fast high level simulation approach that supports task scheduling and that does not produce pessimistic simulation traces.

Existing temporal analysis and buffer sizing techniques for real-time stream processing applications ignore that FIFO buffers bound interference between tasks on the same processor. By considering this effect it can be shown that a reduction of buffer capacities can result in a higher throughput. However, the relation between buffer capacities and throughput is non-monotone in general, which makes an exploitation of the effect challenging. In this paper a buffer sizing approach is presented which exploits that FIFO buffers bound interference between tasks on shared processors. The approach combines temporal analysis using a cyclic dataflow model with computation of buffer capacities in an iterative manner and thereby enables higher throughput guarantees at smaller buffer capacities. It is shown that convergence of the proposed analysis flow is guaranteed. The benefits of the presented approach are demonstrated using a WLAN 802.11p transceiver application executed on a multiprocessor system with shared processors. If buffers without blocking writes are used an up to 25% higher guaranteeable throughput and up to 23% smaller buffer capacities can be determined compared to existing approaches. For systems using buffers with blocking writes the guaranteeable throughput is even up to 43% higher and buffer capacities up to 11% smaller.

Real-time dataflow analysis techniques for multiprocessor systems ignore that the execution of tasks belonging to different operation modes are mutually exclusive. This results in more resources being reserved than strictly needed and a low resource utilization.

Stream processing applications executed on embedded multiprocessor systems regularly contain cyclic data dependencies due to the presence of feedback loops and bounded FIFO buffers. Dataflow modeling is suitable for the temporal analysis of such applications. However, the accuracy can be unsatisfactory as existing temporal analysis techniques ignore that cyclic data dependencies limit interference between tasks executed on shared processors. This paper presents a dataflow analysis approach that increases the analysis accuracy by taking into account that cyclic data dependencies limit interference between tasks. It is shown that the approach is applicable for single-rate stream processing applications that are executed on multiprocessor systems using static priority preemptive schedulers. The improvement of accuracy is demonstrated in a case study employing a WLAN 802.11p transceiver application that is executed on a multiprocessor system with shared processors.

Real-time stream processing applications such as software defined radios are usually executed concurrently on multiprocessor systems. Exploiting coarse-grained data parallelism by duplicating tasks is often required, besides pipeline parallelism, to meet the temporal constraints of the applications. However, no unified model and analysis method exists that can be used to determine the required amount of data and pipeline parallelism, and buffer sizes simultaneously. This paper presents an analysis method which can determine the required amount of data parallelism by describing data parallelism in a dataflow model without replicating dataflow actors. This allows to make a trade-off between the amount of data and pipeline parallelism that is required to meet the temporal constraints of the application. It is also shown how large the buffers need to be such that the determined amount of data and pipeline parallelism required for the satisfaction of the throughput constraint, can be realized. Furthermore, it is shown that the use of the applied circular buffers enables the proposed dataflow modeling. The presented analysis method is demonstrated using a WLAN 802.11p transceiver application. This application contains multi-rate behavior and has a cyclic data dependency because of a re-encoding loop. Given the real-time constraints of the application, sufficient buffer sizes and sufficient data parallelism are derived.

Modern real-time stream processing applications, such as Software Defined Radio (SDR) applications, typically have multiple modes and multi-rate behavior. Modes are often described using while-loops whereas multi-rate behavior is frequently described using arrays with pseudo-random indexing patterns. The temporal properties of these applications have to be analyzed in order to determine whether optimizations improve throughput. However, no method exists in which a temporal analysis model is derived from these applications that is suitable for temporal analysis and optimization.

Real-time stream processing applications often contain multi-rate behavior. This multi-rate behavior can be accurately modeled using Synchronous Dataflow (SDF) graphs. However, no temporal analysis technique exists which is applicable for arbitrary cyclic SDF graphs and can handle cyclic resource dependencies.

Many real-time stream processing applications are initially described as a sequential application containing while-loops, which execute for an unknown number of iterations. These modal applications have to be executed in parallel on an MPSoC system in order to meet their real-time throughput constraints. However, no suitable approach exists that can automatically derive a temporal analysis model from a sequential specification containing while- loops with an unknown number of iterations.

Real-time stream processing applications, such as radios, can often be modeled intuitively with dataflow models. Given the Worst-Case Execution Times (WCETs) of the tasks, which characterizes workload with one parameter, dataflow analysis techniques have been used to compute the minimum throughput and maximum latency of these applications. However, a large difference between the WCETs of the tasks and their average execution times can result in a large difference between the computed worst-case throughput and the actual obtained throughput. To reduce the difference between the worst-case throughput, determined by analysis, and the actual obtained throughput, we introduce in this paper a two parameter (σ,ρ) workload characterization of the tasks to improve the accuracy of dataflow analysis. The (σ, ρ) workload characterization captures information on the maximum cumulative execution time of consecutive executions of a task and can therefore be seen as a generalization of the WCET characterization. We show how the (σ,ρ) workload characterization can be used in combination with several types of dataflow graphs and how it can be used to improve the temporal analysis results of real-time stream processing applications. We illustrate this for a DVB-T radio application, a car-radio application and a data-dependent MP3 playback application.

Automatic parallelization of Nested Loop Programs (NLPs) is an attractive method to create embedded real-time stream processing applications for multi-core systems. However, the description and parallelization of applications with a time dependent functional behavior has not been considered in NLPs. In such a description, semantic information about time dependent behavior must be made available for the compiler, such that an optimized time independent implementation can be generated automatically. This article introduces language constructs with temporal semantics to NLPs. Using these language constructs, time dependent applications can be specified and a corresponding data-driven implementation can be generated for use on a multi-core system. Despite that these time-aware language constructs can be data-dependent, the application remains functionally deterministic. Pipelining is exploited to increase the throughput of an application. The media access control (MAC) protocol of an IEEE 802.11p WLAN transceiver is used to illustrate the relevance and applicability of the introduced concepts.

This tutorial reviews four popular mathematical formalisms -- dataflow analysis, schedulability analysis, network calculus, and queueing theory -- and how they have been applied to the analysis of Network-on-Chip (NoC) performance. We review the basic concepts and results of each formalism and provide examples of how they have been used in on-chip communication performance analysis. The tutorial also discusses the respective strengths and weaknesses of each formalism, their suitability for a specific purpose, and the attempts that have been made to bridge these analytical approaches. Finally, we conclude the tutorial by discussing open research issues.

Real-time embedded systems like smartphones tend to comprise an ever increasing number of processing cores. For scalability and the need for guaranteed performance, the use of a connection-oriented network-on-chip (NoC) is advocated. Furthermore, a distributed shared memory architecture is preferred as it simplifies software development for a multicore system. In this paper, experimental evidence is provided, showing that replacing a connection-oriented NoC by a connectionless one in a distributed shared memory system reduces the hardware costs and improves the performance. We observed that our FPGA could only support an 8-core system with a connection-oriented NoC. We exchanged the NoC with our tree-shaped, connectionless network and a ring, allowing a 32-core system in the same FPGA, mainly because of a reduced number of physical connections. Although the analytical worst-case performance slightly decreased, measurements show that the latency of latency-critical memory reads was reduced by 52% on average.

The incremental design and analysis of parallel hard real-time stream processing applications is hampered by the lack of an intuitive compositional temporal analysis model that supports arbitrary cyclic dependencies between tasks.

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.

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.

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 date-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.

Increasingly, stream-processing applications include complex control structures to better adapt to changing conditions in their environment. This adaptivity often results in task execution rates that are dependent on the processed stream. Current approaches to compute buffer capacities that are sufficient to satisfy a throughput constraint have limited applicability in case of data-dependent task execution rates. In this article, we present a dataflow model that allows tasks to have loops with an unbounded number of iterations. For instances of this dataflow model, we present efficient checks on their validity. Furthermore, we present an efficient algorithm to compute buffer capacities that are sufficient to satisfy a throughput constraint. This allows to guarantee satisfaction of a throughput constraint over different modes of a stream processing application, such as the synchronization and synchronized modes of a digital radio receiver.

Currently, the guaranteed throughput of a stream processing application, mapped on a multi-processor system, can be computed with a conservative dataflow model, if only time division multiplex (TDM) schedulers are applied. A TDM scheduler is a budget scheduler. Budget schedulers can be characterized by two parameters: budget and replenishment interval. This paper introduces a priority-based budget scheduler (PBS), which is a budget scheduler that additionally associates a priority with every task. PBS improves the guaranteed minimum throughput of a stream processing application compared to TDM, given the same amount of resources. We construct a conservative dataflow model for a task scheduled by PBS. This dataflow model generalizes previous work, because it is valid for a sequence of execution times instead of one execution time per task which results in an improved accuracy of the model. Given this dataflow model, we can compute the guaranteed minimum throughput of the task graph that implements the stream processing application. Experiments confirm that a significantly higher guaranteed minimum throughput of the task graph can be obtained with PBS instead of TDM schedulers and that a conservative bound on the guaranteed throughput of the task graph can be computed with a dataflow model. Furthermore, our bound on the guaranteed throughput of the task graph is accurate, if the buffer capacities in the task graph do not affect the guaranteed throughput.

Performance analysis of applications in multi-core platforms is challenging because of temporal interference while accessing shared resources. Especially, memory arbiters introduce a non-constant delay which significantly influences the execution time of a task. In this paper, we selected a priority-based budget scheduler as memory arbiter which bounds temporal interference by construction and is well suited for bursty service provision. While existing performance analysis approaches assume a constant memory access latency leading to high overestimation, we propose in this paper a conservative data flow model for this scheduler, in which the history of memory accesses is considered.

Modern embedded multi-processors can execute several stream-processing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.

A growing number of applications, often with firm or soft real-time requirements, are integrated on the same System on Chip, in the form of either hardware or software intellectual property. The applications are started and stopped at run time, creating different use-cases. Resources, such as interconnects and memories, are shared between different applications, both within and between use-cases, to reduce silicon cost and power consumption. The functional and temporal behaviour of the applications is verified by simulation and formal methods. Traditionally, designers resort to monolithic verification of the system as whole, since the applications interfere in shared resources, and thus affect each other's behaviour. Due to interference between applications, the integration and verification complexity grows exponentially in the number of applications, and the task to verify correct behaviour of concurrent applications is on the system designer rather than the application designers. In this work, we propose a Composable and Predictable Multi-Processor System on Chip (CoMPSoC) platform template. This scalable hardware and software template removes all interference between applications through resource reservations. We demonstrate how this enables a divide-and-conquer design strategy, where all applications, potentially using different programming models and communication paradigms, are developed and verified independently of one another. Performance is analyzed per application, using state-of-the-art dataflow techniques or simulation, depending on the requirements of the application. These results still apply when the applications are integrated onto the platform, thus separating system-level design and application design.

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.

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.

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.

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.

Multiprocessor systems-on-chip (MPSoC) with distributed shared memory and caches are flexible when it comes to inter-processor communication but require an efficient memory consistency and cache coherency solution. In this paper we present a novel consistency model, streaming consistency, for the streaming domain in which tasks communicate through circular buffers. The model allows more reordering than release consistency and, among other optimizations, enables an efficient software cache coherency solution and posted writes. We also present a software cache coherency implementation and discuss a software circular buffer administration that does not need an atomic read-modify-write instruction. A small experiment demonstrates the potential performance increase of posted writes in MPSoCs with high communication latencies.

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.

This paper proposes a scheduling strategy and an automatic scheduling flow that enable the simultaneous execution of multiple hard-real-time dataflow jobs. Each job has its own execution rate and starts and stops independently from other jobs, at instants unknown at compile-time, on a multiprocessor system-on-chip. We show how a combination of Time-Division Multiplex (TDM) and static-order scheduling can be modeled as additional nodes and edges on top of the dataflow representation of the job using Single-Rate Dataflow semantics to enable tight worst-case temporal analysis. We also propose algorithms to find combined TDM/static order schedules for jobs that guarantee a requested minimum throughput and maximum latency, while minimizing the usage of processing resources. We illustrate the usage of these techniques for a combination of Wireless LAN and TD-SCDMA radio jobs running on a prototype Software-Defined Radio platform.

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.

This paper describes a conservative approximation algorithm that derives close to minimal buffer capacities for an application described as a cyclo-static dataflow graph. The resulting buffer capacities satisfy constraints on the maximum buffer capacities and end-to-end throughput and latency constraints. Furthermore we show that the effects of run-time arbitration can be included in the response times of dataflow actors. We show that modelling an MP3 playback application as a cyclo-static dataflow graph instead of a multi-rate dataflow graph results in buffer capacities that are reduced up to 39%. Furthermore, the algorithm is applied to a real-life car-radio application, in which two independent streams are processed

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.

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.

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.

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.

Summary form only given. In this paper we extend the method to deal with coarse-grain operations in static scheduled VLIW processors as is introduced by Busa (2000). We allow functional units with a controller that does not traverse its states in a predefined way. This makes it possible to execute a function that contains a conditional construct like an if-statement as a single operation on a functional unit. In this way the performance penalty otherwise caused by branch instructions is reduced. By adding valid input and output signals, the problem is circumvented that during compilation it is, for this type of functional unit, not known when and how many samples will be consumed or produced. We refer to these units as Conditional Input/output Units (CIUs). The operations that are executed on CIUs are called Conditional Input/output Operations (CIOs). The difference with guarded operations is that the production of a result of a CIO depends on the state of the CIU.

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.

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.