Commercial-off-the-shelf (COTS) multicore systems on chip (SoC) represent a cheap and convenient solution for deploying sophisticated workloads in various application domains. The combination of several CPU cores and dedicated acceleration units tightly sharing memory and interconnect systems can provide tremendous peak performance, but also threatens timing predictability due to memory interference. Even when focusing on main CPU cores only, it has been reported that task slowdown due to memory interference can surpass 10 × . Such poorly predictable timing behaviors bar greater adoption of COTS multicore SoCs in the domain of timing-critical applications, and motivate the wide activity of the research community to study solutions aimed at mitigating the problem. Understanding worst-case interference patterns on such hardware platforms is fundamental for building any effective memory interference control mechanism. A common assumption in the literature is that worst-case interference is generated by (and therefore assessed through) read-intensive synthetic workloads with 100% cache miss rate. Yet certain real-life workloads exhibit worse slowdown than what is generated under said assumed worst-case, so we study the interference effects of both synthetic and real-life benchmarks on different multicore SoCs. Our experiments indicate that cache thrashing causes the worst interference experienced by real-life benchmarks – due to their different usage of caches – and that there is no universal worst-case workload for every platform.

Memory bandwidth contention may severely inflate the execution time of tasks co-running on modern Commercial Off-The-Shelf (COTS) multicores. An effective and widely deployed solution to mitigate the problem is bandwidth regulation , a technique to limit the available memory bandwidth for those cores that are not executing time-critical tasks . The granularity at which time-critical activities can be identified at the core level can be in fact even finer than a whole task, and just span smaller memory-critical section (MCS) therein. As the co-presence of MCS and non-critical task portions in the system dynamically changes over time, bandwidth regulators require more or less frequent reconfiguration of their parameters. Similar reconfiguration techniques thus represent a central component of dynamic Memory Bandwidth Management Schemes (MBMS). In particular, the overhead and latency of such a component determine the feasibility and control granularity of the overall bandwidth-regulation solution. The literature extensively covers low-level bandwidth regulation mechanisms and – to some extent – their integration in wider MBMSs, yet no in-depth analysis is currently available of the impact of reconfiguration techniques . This paper addresses this issue by proposing a comparative analysis of the two basic approaches to reconfiguring bandwidth regulators in a system: synchronous and asynchronous schemes. The analysis, performed on a real-world setup with both synthetic and real-world benchmarks, shows that the asynchronous technique improves the control granularity of a bandwidth regulator by a factor of up to 19x, moving from the ms to the μ s scale.

Commercial embedded systems increasingly rely on heterogeneous architectures that integrate general-purpose, multi-core processors, and various hardware accelerators on the same chip. This provides the high performance required by modern applications at a low cost and low power consumption, but at the same time poses new challenges. Hardware resource sharing at various levels, and in particular at the main memory controller level, results in slower execution time for the application tasks, ultimately making the system unpredictable from the point of view of timing. To enable the adoption of heterogeneous systems-on-chip (System on Chips (SoCs)) in the domain of timing-critical applications several hardware and software approaches have been proposed, bandwidth regulation based on monitoring and throttling being one of the most widely adopted. Existing solutions, however, are either too coarse-grained, limiting the control over computing engines activities, or strongly platform-dependent, addressing the problem only for specific SoCs. This article proposes an innovative approach that can accurately control main memory bandwidth usage in FPGA-based heterogeneous SoCs. In particular, it controls system bandwidth by connecting a runtime bandwidth regulation component to FPGA-based accelerators. Our solution offers dynamically configurable, fine-grained bandwidth regulation – to adapt to the varying requirements of the application over time – at a very low overhead. Furthermore, it is entirely platform-independent, capable of integration with any FPGA-based accelerator. Developed at the register-transfer level using a reference SoC platform, it is designed for easy compatibility with any FPGA-based SoC. Experimental results conducted on the Xilinx Zynq UltraScale+ platform demonstrate that our approach (i) is more than$100\times$faster than loosely-coupled, software controlled regulators; (ii) is capable of exploiting the system bandwidth 28.7% more efficiently than tightly-coupled hardware regulators (e.g., ARM CoreLink QoS-400, where available); (iii) enables task co-scheduling solutions not feasible with state-of-the-art bandwidth regulation methods.

Embedded systems are increasingly adopting heterogeneous templates integrating hardware accelerators and application-specific processors, which poses novel challenges. In particular, it is difficult to have accurate control of task activities in Commercial Off-the-shelf (COTS) System on Chips (SoCs), due to complex main memory sharing mechanisms among different computing engines. To address this problem, bandwidth regulation approaches based on monitoring and throttling are widely adopted. Existing solutions, however, are either too coarse-grained, limiting the control over computing engines activities, or platform-dependent, addressing the problem only for specific SoCs. In this paper we propose an innovative, fine-grained and platform-independent approach that can accurately control main memory bandwidth usage in an FPGA-based Heterogeneous System on Chip (HeSoC). Experimental results conducted on the Xilinx Zynq UltraScale+ platform demonstrate that our approach enables solutions not feasible with state-of-the-art bandwidth regulation methods.

High-performance embedded platforms are increasingly adopting heterogeneous systems-on-chip (HeSoC) that couple multi-core CPUs with accelerators such as GPU, FPGA, or AI engines. Adopting HeSoCs in the context of real-time workloads is not immediately possible, though, as contention on shared resources like the memory hierarchy—and in particular the main memory (DRAM)—causes unpredictable latency increase. To tackle this problem, both the research community and certification authorities mandate (i) that accesses from parallel threads to the shared system resources (typically, main memory) happen in a mutually exclusive manner by design, or (ii) that per-thread bandwidth regulation is enforced. Such arbitration schemes provide timing guarantees, but make poor use of the memory bandwidth available in a modern HeSoC. Controlled Memory Request Injection (CMRI) is a recently-proposed bandwidth limitation concept that builds on top of a mutually-exclusive schedule but still allows the threads currently not entitled to access memory to use as much of the unused bandwidth as possible without losing the timing guarantee. CMRI has been discussed in the context of a multi-core CPU, but the same principle applies also to a more complex system such as an HeSoC. In this article, we introduce two CMRI schemes suitable for HeSoCs: Voluntary Throttling via code refactoring and Bandwidth Regulation via dynamic throttling. We extensively characterize a proof-of-concept incarnation of both schemes on two HeSoCs: an NVIDIA Tegra TX2 and a Xilinx UltraScale+, highlighting the benefits and the costs of CMRI for synthetic workloads that model worst-case DRAM access. We also test the effectiveness of CMRI with real benchmarks, studying the effect of interference among the host CPU and the accelerators.

The paper presents a multiscale simulation methodology and EDA tool that assesses the effect of thermal mechanical stresses arising after die assembly on chip performance. Existing non uniformities of feature geometries and composite nature of on-chip interconnect layers are addressed by developed methodology of the anisotropic effective thermomechanical material properties (EMP) that reduces complexity of FEA simulations and enhances the accuracy and performance. Physical nature of the calculated EMP makes it scalable with the simulation grid size, which enables resolution of stress/strain at different scales from package to device channel. With feature-scale resolution, the tool enables accurate calculation of stress components in the active region of each device, where the carrier mobility variation results in deviations of circuits performance. The tool's capability of back-annotation of the hierarchic Spice netlist with the stress values allows a user to perform circuit simulation in different stress environments, by placing the circuit block in different locations in the layout characterized by different distances from the stress sources, such as die edges and C4 bumps. Both schematic and post-layout netlists can be employed for finding optimal floorplan minimizing the stress impact at early design stages, as well as for the final design sign-off. Electrical measurements on a specially designed test-package were used for validation of the methodology. Good agreement between measured and simulated variations of device characteristics has been demonstrated.

One of the main predictability bottlenecks of modern multi-core embedded systems is contention for access to shared memory resources. Partitioning and software-driven allocation of memory resources is an effective strategy to mitigate contention in the memory hierarchy. Unfortunately, however, many of the strategies adopted so far can have unforeseen side-effects when practically implemented latest-generation, high-performance embedded platforms. Predictability is further jeopardized by cache eviction policies based on random replacement, targeting average performance instead of timing determinism. In this paper, we present a framework of software-based techniques to restore memory access determinism in high-performance embedded systems. Our approach leverages OS-transparent and DMA-friendly cache coloring, in combination with an invalidation-driven allocation (IDA) technique. The proposed method allows protecting important cache blocks from (i) external eviction by tasks concurrently executing on different cores, and (ii) internal eviction by tasks running on the same core. A working implementation obtained by extending the Jailhouse partitioning hypervisor is presented and evaluated with a combination of synthetic and real benchmarks.

Tenants in a cloud environment run services, such as Virtual Network Function instantiations, that may legitimately generate millions of packets per second. The hosting platform, hence, needs robust packet scheduling mechanisms that support these rates and, at the same time, provide isolation and dependable service guarantees under all load conditions. Current hardware or software packet scheduling solutions fail to meet all these requirements, most commonly lacking on either performance or guarantees. In this paper we propose an architecture, called PSPAT to build efficient and robust software packet schedulers suitable to high speed, highly concurrent environments. PSPAT decouples clients, scheduler and device driver through lock-free mailboxes, thus removing lock contention, providing opportunities to parallelize operation, and achieving high and dependable performance even under overload. We describe the operation of our system, discuss implementation and system issues, provide analytical bounds on the service guarantees of PSPAT, and validate the behavior of its Linux implementation even at high link utilization, comparing it with current hardware and software solutions. Our prototype can make over 28 million scheduling decisions per second, and keep latency low, even with tens of concurrent clients running on a multi-core, multi-socket system.

The packet scheduling problem has been deeply studied for lot of years by researchers in the computer science and telecommunications fields as an important solution that decides the order in which packets are sent over a link in order to provide QoS on a network. Recently, the packet scheduling has become again a challenging topic due to the massive use of wireless technologies (e.g. WiFi, LTE, 4G/5G), both for public and PPDR networks, with which to provide high QoS guarantees is still an open problem. Unfortunately, it is difficult to compare different solutions and actually test them in order to select the most proper packet scheduler for each particular environment.

Round-robin schedulers are the most efficient solution for providing strong QoS guarantees on high-speed links. Yet these schedulers suffer from a high worst-case delay with respect to an ideal, perfectly fair service. More costly schedulers are needed to provide better service guarantees. In this paper we tackle this problem by proposing a simple modification scheme for reducing the amortized execution time of fair-queueing schedulers. We prove that, applying this scheme to existing accurate schedulers, we can define new schedulers providing near-optimal service guarantees at an amortized computational cost close to that of just Deficit Round Robin (DRR). Finally, we show Quick Fair Queueing Plus (QFQ+), a new scheduler obtained by applying our scheme to QFQ. QFQ+ replaced QFQ in the Linux kernel. According to our experimental results, and exactly in the scenarios where QFQ+ provides better service guarantees than a round-robin scheduler, the time and the energy needed to process packets with QFQ+ is lower than with DRR.

Packet scheduling, together with classification, is one of the most expensive processing steps in systems providing tight bandwidth and delay guarantees at high packet rates. Schedulers with near-optimal service guarantees andO(1) time complexity have been proposed in the past, using techniques such as timestamp rounding and flow grouping to keep their execution time small. However, even the two best proposals in this family have a per-packet cost component that is linear either in the number of groups or in the length of the packet being transmitted. Furthermore, no studies are available on the actual execution time of these algorithms. In this paper we make two contributions. First, we present Quick Fair Queueing (QFQ), a newO( 1) scheduler that provides near-optimal guarantees and is the first to achieve that goal with a truly constant cost also with respect to the number of groups and the packet length. The QFQ algorithm has no loops and uses very simple instructions and data structures that contribute to its speed of operation. Second, we have developed production-quality implementations of QFQ and of its closest competitors, which we use to present a detailed comparative performance analysis of the various algorithms. Experiments show that QFQ fulfills our expectations, outperforming the other algorithms in the same class. In absolute terms, even on a low-end workstation, QFQ takes about 110 ns for an enqueue()/dequeue() pair (only twice the time of DRR, but with much better service guarantees).

BFQ (Budget Fair Queueing) is a production-quality, proportional-share disk scheduler with a relatively large user base. Part of its success is due to a set of simple heuristics that we added to the original algorithm about one year ago. These heuristics are the main focus of this paper.

Mainstream applications-such as file copy/transfer, Web, DBMS, or video streaming-typically issue synchronous disk requests. As shown in this paper, this fact may cause work-conserving schedulers to fail both to enforce guarantees and provide a high disk throughput. A high throughput can be, however, recovered by just idling the disk for a short time interval after the completion of each request. In contrast, guarantees may still be violated by existing time-stamp-based schedulers because of the rules they use to tag requests. Budget Fair Queuing (BFQ), the new disk scheduler presented in this paper, is an example of how disk idling, combined with proper back-shifting of request time stamps, may allow a time-stamp-based disk scheduler to preserve both guarantees and a high throughput. Under BFQ, each application is always guaranteed-over any time interval and independently of whether it issues synchronous requests-a bounded lag with respect to its reserved fraction of the total number of bytes transferred by the disk device. We show the single-disk performance of our implementation of BFQ in the Linux kernel through experiments with real and emulated mainstream applications.

Providing strong QoS guarantees for wireless multi-hop networks is very challenging, due to many factors such as use of a shared communication medium, variability in wireless link quality, and so on. However, wireless mesh technology gives the opportunity to alleviate some of these problems, due to lack of mobility in the wireless infrastructure, and presence of natural centralization points in the network. The main contribution of this paper is the definition of a simple framework that exploits these features to provide provable, strong QoS guarantees to network clients. In particular, admitted clients are guaranteed a certain minimum bandwidth and maximum delay on their connections. The framework is based on STDMA scheduling at the MAC layer, which is periodically executed at the network manager to adapt to changes in traffic demand. While scheduling computation is centralized, admission control is performed locally at the wireless backbone nodes, thus reducing signaling. We propose two bandwidth distribution and related admission control policies, which are at opposite ends of the network utilization/spatial fairness trade-off. Through extensive simulations, we show that the proposed framework achieves its design goals of providing strong QoS guarantees to VoIP clients while not sacrificing throughput in a realistic mesh network scenario, also in presence of highly unbalanced load at the backbone nodes. To the best of our knowledge, this is the first proposal with similar features for wireless mesh networks.

Multiprocessors are now commonplace for efficiently achieving high computational power, even in embedded systems. A considerable research effort is being addressed to schedulability analysis of global scheduling in symmetric multiprocessor platforms (SMP), where there is a global queue of ready tasks, and preemption and migration are allowed. In many soft real-time applications (as e.g. multimedia and telecommunication) a bounded lateness is often tolerated. Unfortunately, when considering priority-driven scheduling of periodic/sporadic tasks, previous results only focused on guaranteeing all deadlines, and provided worst-case utilization bounds that are lower than the maximum available computational power. In particular, until now, the existence of an upper bound on the lateness of soft real-time tasks for a fully utilized SMP was still an open problem. In this paper we do solve this problem by providing an upper bound to the lateness of periodic/sporadic tasks - with relative deadlines equal to periods/minimum inter-arrival times - scheduled by EDF on a SMP, under the only assumption that the total utilization is no higher than the total system capacity

Generalized Processor Sharing (GPS) is a fluid scheduling policy providing perfect fairness. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one packet size. To the best of our knowledge, the only packet scheduler guaranteeing such minimum deviation is Worst-case Fair Weighted Fair Queueing (WF2Q), that requires on-line GPS simulation. Existing algorithms to perform GPS simulation have O(N) complexity per packet transmission (N being the number of competing flows). Hence WF2Q has been charged for O(N) complexity too. Schedulers with lower complexity have been devised, but at the price of at least O(N) deviation from the GPS service, which has been shown to be detrimental for real-time adaptive applications and feedback based applications. Furthermore, it has been proven that the lower bound complexity to guarantee O(1) deviation is Ω(log N), yet a scheduler achieving such result has remained elusive so far.In this paper we present an algorithm that performs exact GPS simulation with O(log N) worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. In particular, using our algorithm within WF2Q, we achieve the minimum deviation from the GPS service with O(log N) complexity, thus matching the aforementioned lower bound. Furthermore, we assess the effectiveness of the proposed solution by simulating real-world scenarios.