Search

Ensuring timing guarantees for every individual tasks is critical in real-time systems. Even for periodic tasks, providing timing guarantees for tasks with segmented self-suspending behavior is challenging due to timing anomalies, i.e., the reduction of execution or suspension time of some jobs increases the response time of another job. The release jitter of tasks can add further complexity to the situation, affecting the predictability and timing guarantees of real-time systems. The existing worst-case response time analyses for sporadic self-suspending tasks are only over-approximations and lead to overly pessimistic results. In this work, we address timing anomalies without compromising the worst-case response time (WCRT) analysis when scheduling periodic segmented self-suspending tasks with release jitter. We propose two treatments: segment release time enforcement and segment priority modification, and prove their effectiveness in eliminating timing anomalies. Our evaluation demonstrates that the proposed treatments achieve higher acceptance ratios in terms of schedulability compared to state-of-the-art scheduling algorithms. Additionally, we implement the segment-level fixed-priority scheduling mechanism on RTEMS and verify the validity of our segment priority modification treatment. This work expands our previous conference publication at the 29th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2023), which considers only periodic segmented self-suspending tasks without release jitter., Comment: This is an extension from a previous conference publication at the 29th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2023)

Owing to the characteristics of high density and unlimited write cycles, skyrmion racetrack memory (SK-RM) has demonstrated great potential as either the next-generation main memory or the last-level cache of processors with non-volatility. Nevertheless, the distinct skyrmion manipulations, such as injecting and shifting, demand a fundamental change in widely-used memory structures to avoid excessive energy and performance overhead. For instance, while B{\epsilon}-trees yield an excellent query and insert performance trade-off between B-trees and Log-Structured Merge (LSM)-trees, the applicability of deploying B{\epsilon}-trees onto SK-RM receives much less attention. In addition, even though optimizing designs have been proposed for B+-trees on SK-RM, those designs are not directly applicable to B{\epsilon}-trees owing to the batch update behaviors between tree nodes of B{\epsilon}-trees. Such an observation motivates us to propose the concept of Sky{\epsilon}-tree to effectively utilize the access port parallelism of SK-RM to embrace the excellent query and insert performance of B{\epsilon}-trees. Experimental results have shown promising improvements in access performance and energy conservation.

The rise of machine learning methods on heavily resource constrained devices requires not only the choice of a suitable model architecture for the target platform, but also the optimization of the chosen model with regard to execution time consumption for inference in order to optimally utilize the available resources. Random forests and decision trees are shown to be a suitable model for such a scenario, since they are not only heavily tunable towards the total model size, but also offer a high potential for optimizing their executions according to the underlying memory architecture. In addition to the straightforward strategy of enforcing shorter paths through decision trees and hence reducing the execution time for inference, hardware-aware implementations can optimize the execution time in an orthogonal manner. One particular hardware-aware optimization is to layout the memory of decision trees in such a way, that higher probably paths are less likely to be evicted from system caches. This works particularly well when splits within tree nodes are uneven and have a high probability to visit one of the child nodes. In this paper, we present a method to reduce path lengths by rewarding uneven probability distributions during the training of decision trees at the cost of a minimal accuracy degradation. Specifically, we regularize the impurity computation of the CART algorithm in order to favor not only low impurity, but also highly asymmetric distributions for the evaluation of split criteria and hence offer a high optimization potential for a memory architecture-aware implementation. We show that especially for binary classification data sets and data sets with many samples, this form of regularization can lead to an reduction of up to approximately four times in the execution time with a minimal accuracy degradation.

Bringing high-level machine learning models to efficient and well-suited machine implementations often invokes a bunch of tools, e.g.~code generators, compilers, and optimizers. Along such tool chains, abstractions have to be applied. This leads to not optimally used CPU registers. This is a shortcoming, especially in resource constrained embedded setups. In this work, we present a code generation approach for decision tree ensembles, which produces machine assembly code within a single conversion step directly from the high-level model representation. Specifically, we develop various approaches to effectively allocate registers for the inference of decision tree ensembles. Extensive evaluations of the proposed method are conducted in comparison to the basic realization of C code from the high-level machine learning model and succeeding compilation. The results show that the performance of decision tree ensemble inference can be significantly improved (by up to $\approx1.6\times$), if the methods are applied carefully to the appropriate scenario.

Occasional deadline misses are acceptable for soft real-time systems. Quantifying probabilistic and deterministic characteristics of deadline misses is therefore essential to ensure that deadline misses indeed happen only occasionally. This is supported by recent research activities on probabilistic worst-case execution time, worst-case deadline failure probability, the maximum number of deadline misses, upper bounds on the deadline miss probability, and the deadline miss rate. This paper focuses on the deadline miss rate of a periodic soft real-time task in the long run. Our model assumes that this soft real-time task has an arbitrary relative deadline and that a job can still be executed after a deadline-miss until a dismiss point. This model generalizes the existing models that either dismiss a job immediately after its deadline miss or never dismiss a job. We provide mathematical notation on the convergence of the deadline miss rate in the long run and essential properties to calculate the deadline miss rate. Specifically, we use a Markov chain to model the execution behavior of a periodic soft real-time task. We present the required ergodicity property to ensure that the deadline miss rate in the long run is described by a stationary distribution.

Nowadays, various memory-hungry applications like machine learning algorithms are knocking "the memory wall". Toward this, emerging memories featuring computational capacity are foreseen as a promising solution that performs data process inside the memory itself, so-called computation-in-memory, while eliminating the need for costly data movement. Recent research shows that utilizing the custom extension of RISC-V instruction set architecture to support computation-in-memory operations is effective. To evaluate the applicability of such methods further, this work enhances the standard GNU binary utilities to generate RISC-V executables with Logic-in-Memory (LiM) operations and develop a new gem5 simulation environment, which simulates the entire system (CPU, peripherals, etc.) in a cycle-accurate manner together with a user-defined LiM module integrated into the system. This work provides a modular testbed for the research community to evaluate potential LiM solutions and co-designs between hardware and software.

In many machine learning applications, e.g., tree-based ensembles, floating point numbers are extensively utilized due to their expressiveness. Nowadays performing data analysis on embedded devices from dynamic data masses becomes available, but such systems often lack hardware capabilities to process floating point numbers, introducing large overheads for their processing. Even if such hardware is present in general computing systems, using integer operations instead of floating point operations promises to reduce operation overheads and improve the performance. In this paper, we provide \mdname, a full precision floating point comparison for random forests, by only using integer and logic operations. To ensure the same functionality preserves, we formally prove the correctness of this comparison. Since random forests only require comparison of floating point numbers during inference, we implement \mdname~in low level realizations and therefore eliminate the need for floating point hardware entirely, by keeping the model accuracy unchanged. The usage of \mdname~basically boils down to a one-by-one replacement of conditions: For instance, a comparison statement in C: if(pX[3]<=(float)10.074347) becomes if((*(((int*)(pX))+3))<=((int)(0x41213087))). Experimental evaluation on X86 and ARMv8 desktop and server class systems shows that the execution time can be reduced by up to $\approx 30\%$ with our novel approach.

In the near future, the development of autonomous driving will get more complex as the vehicles will not only rely on their own sensors but also communicate with other vehicles and the infrastructure to cooperate and improve the driving experience. Towards this, several research areas, such as robotics, communication, and control, are required to collaborate in order to implement future-ready methods. However, each area focuses on the development of its own components first, while the effects the components may have on the whole system are only considered at a later stage. In this work, we integrate the simulation tools of robotics, communication and control namely ROS2, OMNeT++, and MATLAB to evaluate cooperative driving scenarios. The framework can be utilized to develop the individual components using the designated tools, while the final evaluation can be conducted in a complete scenario, enabling the simulation of advanced multi-robot applications for cooperative driving. Furthermore, it can be used to integrate additional tools, as the integration is done in a modular way. We showcase the framework by demonstrating a platooning scenario under cooperative adaptive cruise control (CACC) and the ETSI ITS-G5 communication architecture. Additionally, we compare the differences of the controller performance between the theoretical analysis and practical case study., Comment: 8 pages, preprint, https://github.com/tu-dortmund-ls12-rt/AuNa

In real-time systems, schedulability tests are utilized to provide timing guarantees. However, for self-suspending task sets, current suspension-aware schedulability tests are limited to Task-Level Fixed-Priority~(TFP) scheduling or Earliest-Deadline-First~(EDF) with constrained-deadline task systems. In this work we provide a unifying schedulability test for the uniprocessor version of Global EDF-Like (GEL) schedulers and arbitrary-deadline task sets. A large body of existing scheduling algorithms can be considered as EDF-Like, such as EDF, First-In-First-Out~(FIFO), Earliest-Quasi-Deadline-First~(EQDF) and Suspension-Aware EDF~(SAEDF). Therefore, the unifying schedulability test is applicable to those algorithms. Moreover, the schedulability test can be applied to TFP scheduling as well. Our analysis is the first suspension-aware schedulability test applicable to arbitrary-deadline sporadic real-time task systems under Job-Level Fixed-Priority (JFP) scheduling, such as EDF. Moreover, it is the first unifying suspension-aware schedulability test framework that covers a wide range of scheduling algorithms. Through numerical simulations, we show that the schedulability test outperforms the state of the art for EDF under constrained-deadline scenarios. Moreover, we demonstrate the performance of different configurations under EQDF and SAEDF.

Due to the growing popularity of the Internet of Things, edge computing concept has been widely studied to relieve the load on the original cloud and networks while improving the service quality for end-users. To simulate such a complex environment involving edge and cloud computing, EdgeCloudSim has been widely adopted. However, it suffers from certain efficiency and scalability issues due to the ignorance of the deficiency in the originally adopted data structures and maintenance strategies. Specifically, it generates all events at beginning of the simulation and stores unnecessary historical information, both result in unnecessarily high complexity for search operations. In this work, by fixing the mismatches on the concept of discrete-event simulation, we propose enhancement of EdgeCloudSim which improves not only the runtime efficiency of simulation, but also the flexibility and scalability. Through extensive experiments with statistical methods, we show that the enhancement does not affect the expressiveness of simulations while obtaining 2 orders of magnitude speedup, especially when the device count is large., Comment: 8 pages

When considering recurrent tasks in real-time systems, concurrent accesses to shared resources, can cause race conditions or data corruptions. Such a problem has been extensively studied since the 1990s, and numerous resource synchronization protocols have been developed for both uni-processor and multiprocessor real-time systems, with the assumption that the implementation overheads are negligible. However, in practice, the implementation overheads may impact the performance of different protocols depending upon the practiced scenarios, e.g., resources are accessed locally or remotely, and tasks spin or suspend themselves when the requested resources are not available. In this paper, to show the applicability of different protocols in real-world systems, we detail the implementation of several state-of-the-art multiprocessor resource synchronization protocols in RTEMS. To study the impact of the implementation overheads, we deploy these implemented protocols on a real platform with synthetic task set. The measured results illustrate that the developed resource synchronization protocols in RTEMS are comparable to the existed protocol, i.e., MrsP., Comment: 6 pages, 5 figures, presented in 16th annual workshop on Operating Systems Platforms for Embedded Real-Time applications (OSPERT'22)

To reduce the resource demand of neural network (NN) inference systems, it has been proposed to use approximate memory, in which the supply voltage and the timing parameters are tuned trading accuracy with energy consumption and performance. Tuning these parameters aggressively leads to bit errors, which can be tolerated by NNs when bit flips are injected during training. However, bit flip training, which is the state of the art for achieving bit error tolerance, does not scale well; it leads to massive overheads and cannot be applied for high bit error rates (BERs). Alternative methods to achieve bit error tolerance in NNs are needed, but the underlying principles behind the bit error tolerance of NNs have not been reported yet. With this lack of understanding, further progress in the research on NN bit error tolerance will be restrained. In this study, our objective is to investigate the internal changes in the NNs that bit flip training causes, with a focus on binarized NNs (BNNs). To this end, we quantify the properties of bit error tolerant BNNs with two metrics. First, we propose a neuron-level bit error tolerance metric, which calculates the margin between the pre-activation values and batch normalization thresholds. Secondly, to capture the effects of bit error tolerance on the interplay of neurons, we propose an inter-neuron bit error tolerance metric, which measures the importance of each neuron and computes the variance over all importance values. Our experimental results support that these two metrics are strongly related to bit error tolerance., Comment: Presented at DATE Friday Workshop on System-level Design Methods for Deep Learning on Heterogeneous Architectures (SLOHA 2021) (arXiv:2102.00818)

Several emerging technologies for byte-addressable non-volatile memory (NVM) have been considered to replace DRAM as the main memory in computer systems during the last years. The disadvantage of a lower write endurance, compared to DRAM, of NVM technologies like Phase-Change Memory (PCM) or Ferroelectric RAM (FeRAM) has been addressed in the literature. As a solution, in-memory wear-leveling techniques have been proposed, which aim to balance the wear-level over all memory cells to achieve an increased memory lifetime. Generally, to apply such advanced aging-aware wear-leveling techniques proposed in the literature, additional special hardware is introduced into the memory system to provide the necessary information about the cell age and thus enable aging-aware wear-leveling decisions. This paper proposes software-only aging-aware wear-leveling based on common CPU features and does not rely on any additional hardware support from the memory subsystem. Specifically, we exploit the memory management unit (MMU), performance counters, and interrupts to approximate the memory write counts as an aging indicator. Although the software-only approach may lead to slightly worse wear-leveling, it is applicable on commonly available hardware. We achieve page-level coarse-grained wear-leveling by approximating the current cell age through statistical sampling and performing physical memory remapping through the MMU. This method results in non-uniform memory usage patterns within a memory page. Hence, we further propose a fine-grained wear-leveling in the stack region of C / C++ compiled software. By applying both wear-leveling techniques, we achieve up to $78.43\%$ of the ideal memory lifetime, which is a lifetime improvement of more than a factor of $900$ compared to the lifetime without any wear-leveling.

Non-volatile memory, such as resistive RAM (RRAM), is an emerging energy-efficient storage, especially for low-power machine learning models on the edge. It is reported, however, that the bit error rate of RRAMs can be up to 3.3% in the ultra low-power setting, which might be crucial for many use cases. Binary neural networks (BNNs), a resource efficient variant of neural networks (NNs), can tolerate a certain percentage of errors without a loss in accuracy and demand lower resources in computation and storage. The bit error tolerance (BET) in BNNs can be achieved by flipping the weight signs during training, as proposed by Hirtzlin et al., but their method has a significant drawback, especially for fully connected neural networks (FCNN): The FCNNs overfit to the error rate used in training, which leads to low accuracy under lower error rates. In addition, the underlying principles of BET are not investigated. In this work, we improve the training for BET of BNNs and aim to explain this property. We propose straight-through gradient approximation to improve the weight-sign-flip training, by which BNNs adapt less to the bit error rates. To explain the achieved robustness, we define a metric that aims to measure BET without fault injection. We evaluate the metric and find that it correlates with accuracy over error rate for all FCNNs tested. Finally, we explore the influence of a novel regularizer that optimizes with respect to this metric, with the aim of providing a configurable trade-off in accuracy and BET., Comment: 6 pages, 2 figures