There has been significant interest in hardware-assisted deterministic Record and Replay (RnR) systems for multithreaded programs on multiprocessors. However, no proposal has implemented this technique in a hardware prototype with full operating system support. Such an implementation is needed to assess RnR practicality.

Prior work on HW support for memory race recording piggybacks time stamps on coherence messages and logs the outcome of memory races using point-to-point or chunk-based approaches. These memory race recorder (MRR) techniques are effective, but they require modifications to the cache coherence protocol that can hurt performance. In addition, prior work has mostly focused on directory coherence and considered only CMP systems with single-level cache hierarchies. Most modern CMP systems shipped today, however, implement snoop coherence and feature multilevel cache hierarchies. To be practical, a MRR must target CMPs with multilevel caches, mitigate the coherence overhead due to piggybacking, and emphasize on replay speed to broaden applicability of deterministic replay. This paper contributes three new solutions for making chunk-based MRR practical for modern CMPs. We show that MRR interactions with a cache hierarchy can degrade performance and present a novel mechanism that mitigates this degradation. We propose new mechanisms for snoop-based caches that eliminate coherence traffic overhead due to piggybacking. We finally propose new techniques for improving replay speed and introduce a novel framework for evaluating the replay speed potential of MRR designs.

This paper presents a prototype system that executes a set of periodic real-time tasks utilizing dynamic hardware reconfiguration. The proposed scheduling technique, MSDL, is not only able to give an offline guarantee for the feasibility of the task set but also minimizes the number of device configurations. After describing this technique, we extend the schedulability analysis to include different runtime system overheads, including the device reconfiguration time. Then we detail a light-weight runtime system that performs the online part of the MSDL scheduling technique. The runtime system is entirely implemented in hardware. Finally, we outline the corresponding synthesis tool flow and report on the overhead posed by the runtime system

Reconfigurable hardware devices, such as FPGAs, are increasingly used in embedded systems. To utilize these devices for real-time work loads, scheduling techniques are required that generate predictable task timings. In this paper, we present a partitioning-EDF (earliest deadline first) approach to find such schedules. The FPGA area is partitioned along one dimension into slots. The tasks are partitioned into groups. Then, each group is scheduled to exactly one slot using the EDF rule. We show that the problem of finding an optimal partitioning is related to the well-known 2D level bin-packing problem. We extend a previously reported ILP model to solve our partitioning problem to optimality. By a simulation study we demonstrate that the partitioning-EDF approach is able to find feasible schedules for most task sets with a system utilization of up to 70%. Additionally, we allow a task to be realized in alternative implementations. A simulation study reveals that the scheduling performance increases considerably if three instead of one task variants are considered. Finally, we model and study the impact of the device reconfiguration time on the scheduling performance

In this paper, we consider the scheduling of periodic real-time tasks on reconfigurable hardware devices. Such devices can execute several tasks in parallel. All executing tasks share the hardware resource, which makes the scheduling problem differ from single- and multiprocessor scheduling. We adapt the global EDF multiprocessor scheduling approach to the reconfigurable hardware execution model and define two preemptive scheduling algorithms, EDF-First-k-Fit and EDF-Next-Fit. For these algorithms, we present a novel linear-time schedulability test and give a proof based on a resource augmentation technique. Then, we propose a task placement and relocation scheme utilizing partial device reconfiguration. This scheme allows us to extend the schedulability test to include reconfiguration time overheads. Experiments with synthetic workloads compare the scheduling test with the actual scheduling performance of EDF-First-k-Fit and EDF-Next-Fit. The main evaluation result is that the reconfiguration overhead is acceptable if the task computation times are one order of magnitude higher than the device reconfiguration time.

This paper deals with scheduling periodic real-time tasks on reconfigurable hardware devices, such as FPGAs. Reconfigurable hardware devices are increasingly used in embedded systems. To utilize these devices also for systems with real-time constraints, predictable task scheduling is required. We formalize the periodic task scheduling problem and propose two preemptive scheduling algorithms. The first is an adaption of the well-known earliest deadline first (EDF) technique to the FPGA execution model. Although the algorithm reveals good scheduling performance, it lacks an efficient schedulability test and requires a high number of FPGA configurations. The second algorithm uses the concept of servers that reserve area and execution time for other tasks. Tasks are successively merged into servers, which are then scheduled sequentially. While this method is inferior to the EDF-based technique regarding schedulability, it comes with a fast schedulability test and greatly reduces the number of required FPGA configurations.

Summary form only given. This work explores various solutions to implement an application using runtime reconfigurable field programmable gate arrays (FPGA). The example is a mechatronic control system which has to adapt its behavior from time to time. Our model is a task-graph where every task is associated with an hardware module characterized by its required FPGA resource and its execution time. We propose various mappings of the tasks onto the FPGA. For the implementation of the tasks themselves the computation technique known as distributed arithmetic is used. We achieve numerous alternatives with different resource consumptions and execution times for every task. We estimate these characteristics and compare them to synthesis results. The received values are used to get the characteristics of the over-all system. The results show that the optimal mapping depends on the application timing constrains, on the complexity of the tasks as well as on the reconfiguration speed of the used FPGA.

We present a new approach for reconfigurable massively parallel computers. The approach uses FPGA as reconfigurable device to build parallel computers which can adapt their physical topology to match the virtual topology used to model the parallel computation paradigm of a given application. We use a case study in which a virtual ring topology is first simulated on a tree topology and then directly implemented in an FPGA configuration. Preliminary results show that we can increase the performance of the parallel computers which make use of message passing interface by a factor of up to 20% if a reconfigurable topology approach is used.