Dynamic hinting: Collaborative real-time resource management for reactive embedded systems

The increasing complexity of today’s reactive embedded applications can rapidly result in reduced real-time capabilities of the underlying hard and software. As an example for this paper we’ll refer to the specific and growing demands on the severely resource constrained sensor nodes in sensor/actuator networks (SANet). While preemptive operating systems are one way to retain acceptable reactivity within highly dynamic environments, their concurrency paradigm commonly leads to severe resource management problems, caused by the coexistence of tasks with interfering and even varying requirements. To counteract these problems, we present the novel Dynamic Hinting approach for maintaining good reactivity in typically resource constrained sensor/actuator systems by efficient combination of preemptive task scheduling and collaborative resource allocation. With respect to task priorities, our technique significantly improves classical methods for handling priority inversions (and deadlocks where required) under both short- and long-term resource allocations. Furthermore, we facilitate compositional software design by providing independently developed tasks with runtime information for yet collaborative and reflective resource sharing – e.g. by means of time-utility-functions. In many cases this even allows to reduce blocking delays as otherwise imposed by bounded priority inversion.     

Towards decentralized system-level security for MPSoC-based embedded applications

With the increasing connectivity and complexity of embedded systems, security issues have become a key consideration in design. In this paper, we propose a decentralized system-level approach for isolating application tasks without the need to rely on a centralized privileged authority at run-time. We discuss the need for isolation to reduce the potential impact of a task compromise or untrustworthy IP block, and present mechanisms to allow for safe sharing of memory regions and IP blocks between tasks in the system. After exploring the architectural requirements for enforcing our security model we present a hardware Isolation Unit, which can be customized for different types of dynamic permission changes depending on task-resource relationships and added to heterogeneous MPSoCs to enforce our security approach.     

Energy efficient task allocation for hybrid main memory architecture

Compared with the conventional dynamic random access memory (DRAM), emerging non-volatile memory technologies provide better density and energy efficiency. However, current NVM devices typically suffer from high write power, long write latency and low write endurance. In this paper, we study the task allocation problem for the hybrid main memory architecture with both DRAM and PRAM, in order to leverage system performance and the energy consumption of the memory subsystem via assigning different memory devices for each individual task. For an embedded system with a static set of periodical tasks, we design an integer linear programming (ILP) based offline adaptive space allocation (offline-ASA) algorithm to obtain the optimal task allocation. Furthermore, we propose an online adaptive space allocation (online-ASA) algorithm for dynamic task set where arrivals of tasks are not known in advance. Experimental results show that our proposed schemes achieve 27.01% energy saving on average, with additional performance cost of 13.6%.     

Analysis and implementation of the multiprocessor bandwidth inheritance protocol

The Multiprocessor Bandwidth Inheritance (M-BWI) protocol is an extension of the Bandwidth Inheritance (BWI) protocol for symmetric multiprocessor systems. Similar to Priority Inheritance, M-BWI lets a task that has locked a resource execute in the resource reservations of the blocked tasks, thus reducing their blocking time. The protocol is particularly suitable for open systems where different kinds of tasks dynamically arrive and leave, because it guarantees temporal isolation among independent subsets of tasks without requiring any information on their temporal parameters. Additionally, if the temporal parameters of the interacting tasks are known, it is possible to compute an upper bound to the interference suffered by a task due to other interacting tasks. Thus, it is possible to provide timing guarantees for a subset of interacting hard real-time tasks. Finally, the M-BWI protocol is neutral to the underlying scheduling policy: it can be implemented in global, clustered and semi-partitioned scheduling. After introducing the M-BWI protocol, in this paper we formally prove its isolation properties, and propose an algorithm to compute an upper bound to the interference suffered by a task. Then, we describe our implementation of the protocol for the?LITMUS ^RT real-time testbed, and measure its overhead. Finally, we compare M-BWI against FMLP and OMLP, two other protocols for resource sharing in multiprocessor systems.     

分时EDF算法及其在多媒体操作系统中的应用

提出了一种新的CPU调度算法－－分时EDF（Earliest Deadine First)算法,该算法能保证硬实时任务不丢失死线,并易于在分时系统中实现。以分时EDF算法为基础,提出一种新的CPU层次调度算法－－HRFSFQ,该算法用于多媒体操作系统时能保证各类任务的QoS。最后通过大量实验证明了上述算法的有效性和正确性。     

A scalable approach to solving dense linear algebra problems on hybrid CPU‐GPU systems

Aiming to fully exploit the computing power of all CPUs and all graphics processing units (GPUs) on hybrid CPU‐GPU systems to solve dense linear algebra problems, we design a class of heterogeneous tile algorithms to maximize the degree of parallelism, to minimize the communication volume, and to accommodate the heterogeneity between CPUs and GPUs. The new heterogeneous tile algorithms are executed upon our decentralized dynamic scheduling runtime system, which schedules a task graph dynamically and transfers data between compute nodes automatically. The runtime system uses a new distributed task assignment protocol to solve data dependencies between tasks without any coordination between processing units. By overlapping computation and communication through dynamic scheduling, we are able to attain scalable performance for the double‐precision Cholesky factorization and QR factorization. Our approach demonstrates a performance comparable to Intel MKL on shared‐memory multicore systems and better performance than both vendor (e.g., Intel MKL) and open source libraries (e.g., StarPU) in the following three environments: heterogeneous clusters with GPUs, conventional clusters without GPUs, and shared‐memory systems with multiple GPUs. Copyright © 2014 John Wiley & Sons, Ltd.     

Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems

In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.     

A comparison of task pools for dynamic load balancing of irregular algorithms

Since a static work distribution does not allow for satisfactory speed‐ups of parallel irregular algorithms, there is a need for a dynamic distribution of work and data that can be adapted to the runtime behavior of the algorithm. Task pools are data structures which can distribute tasks dynamically to different processors where each task specifies computations to be performed and provides the data for these computations. This paper discusses the characteristics of task‐based algorithms and describes the implementation of selected types of task pools for shared‐memory multiprocessors. Several task pools have been implemented in C with POSIX threads and in Java. The task pools differ in the data structures to store the tasks, the mechanism to achieve load balance, and the memory manager used to store the tasks. Runtime experiments have been performed on three different shared‐memory systems using a synthetic algorithm, the hierarchical radiosity method, and a volume rendering algorithm. Copyright © 2004 John Wiley & Sons, Ltd.     

A computational intelligence perspective on process monitoring and optimization

In the design of autonomous computer-based systems, we often face the embarrassing situation of having to specify, to the system, how it should carry out certain tasks, which involve computations known to be intractable or are suspected of being so. To circumvent such impasses, we resort to complexity-reducing strategies and tactics which trade some loss of accuracy for significant reductions in complexity. The term computational intelligence refers to such complexity reduction methods and to the research aimed at identifying such methods. In this paper we describe briefly some of our own work in this area and then develop a computational intelligence view of the task of process monitoring and optimization, as performed by autonomous systems. Some important current fields of discovery in computational intelligence include neural-net computing, evolutionary programming, fuzzy sets, associative memory and so on.     

Dynamic threshold for imbalance assessment on load balancing for multicore systems

The introduction of multicore microprocessors has enabled smaller organizations to invest in high performance shared memory parallel systems. These systems ship with standard operating systems using preset thresholds for task imbalance assessment to activate load balancing. Unfortunately, this will unnecessarily trigger task migrations when the number of tasks is a few multiples of the number of processing cores. We illustrate this unnecessary task migration behavior through simulation and introduce a dynamic threshold for task imbalance assessment that is dependent on the number of tasks and the number of processing cores. This is as a replacement for the static threshold that is used by standard operating systems. With the dynamic threshold method, we are able to illustrate a performance gain of up to 17% on a synthetic benchmark and up to 25% gain using the Integer Sort Benchmark from the National Aeronautics and Space Administration (NASA) Advanced Supercomputing Parallel Benchmark Suite.     

Efficient data management for incoherent ray tracing

To obtain good performance on the GPU hardware, it is necessary to design algorithms to manage data, access memory under GPU memory hierarchy, and schedule more efficient threads. In this paper, we propose an efficient data management and task management designed for GPU based ray tracing. Due to the dynamic and uncertainty in ray tracing, we design data-management layer and task-management layer combined with fuzzy spatial analysis, use the two-level ray sorting and a ray bucket structure to reorganize ray data, then a warp's threads can be scheduled to access coherent geometry and nodes data, reduce memory bandwidth, and dispatch the data locally. We schedule tasks in data-driven execution according to coherent data, propose an adaptive ray compaction to eliminate inactive threads, maintain task efficiency of threads in a warp, and design two heuristics to decrease the compaction cost. On the basis of it, we also introduce a memory-optimized dynamic traversal management to reduce incoherent memory access, and avoid frequent sorting computation and compaction operations. Our experiments demonstrate all of these work combined can achieve good performance.     

An algorithm for cooperative task allocation in scalable,constrained multiple robot systems

The current trends in the robotics field have led to the development of large-scale multiple robot systems, and they are deployed for complex missions. The robots in the system can communicate and interact with each other for resource sharing and task processing. Many of such systems fail despite the availability of necessary resources. The major reason for this is their poor coordination mechanism. Task planning, which involves task decomposition and task allocation, is paramount in the design of coordination and cooperation strategies of multiple robot systems. Task allocation mechanism allocates the task in a mission to the robots by maximizing the overall expected performance, and thereby reducing the total allocation cost for the team. In this paper, we formulate a heuristic search-based task allocation algorithm for the task processing in heterogeneous multiple robot system, by maximizing the efficiency in terms of both communication and processing cost. We assume a set of decomposed tasks of a mission, which needs to be allocated to the robots. The near-optimal allocation schemes are found using the proposed peer structure algorithm for the given problem, where the number of the tasks is more than the robots present in the system. The cost function is the summation of static overhead cost of robots, assignment cost, and the communication cost between the dependent tasks, if they are assigned to different robots. Experiments are performed to verify the effectiveness of the algorithm by comparing it with the existing methods in terms of computational time and quality of solution. The experimental results show that the proposed algorithm performs the best under different problem scales. This proves that the algorithm can be scaled for larger system and it can work for dynamic multiple robot system.     

Adaptive maneuvering, with experiments, for a model ship in a marine control laboratory

The maneuvering problem involves two tasks. The first, called the geometric task, is to force the system output to converge to a desired path continuously parametrized by a scalar θ. The second task, called the dynamic task, is to satisfy a desired dynamic behavior along the path. In this paper, this dynamic behavior is further specified as a speed assignment for θ(t). While the main concern is to satisfy the geometric task, the dynamic task ensures that the system output follows the path with the desired speed. An adaptive recursive design technique is developed for a parametrically uncertain nonlinear plant describing the dynamics of a ship. First the geometric part of the problem is solved. Then an update law is constructed that bridges the geometric design with the dynamic task. The design procedure is performed and tested by several experiments for a model ship in a marine control laboratory.     

动态时间片缩放:一种优化Linux 任务公平性的方法

处理器动态电压频率调节技术,对Linux系统中并发任务的性能产生不同程度的变化,从而影响并发任务计算资源分配的公平性.提出了一种利用动态时间片缩放来优化任务公平性的方法,并基于Linux操作系统任务调度程序,加入动态时间片缩放模块,该模块通过读取CPU性能监控计数器,在线计算时间片缩放系数,并利用该系数对任务时间片长度进行动态缩放.实验表明,这种方法以较小的系统开销为价,极大地提高了Linux中并发任务计算资源分配的公平性.     

A systems approach to task allocation of human-robot interaction in manufacturing

Robots are sharing the manufacturing work environment with humans at an ever increasing rate. As such it has become imperative to analyze the manufacturing tasks and allocate them properly between humans and robots. A systems approach to task allocation has been taken in this paper that includes inventory of anticipated common tasks in manufacturing, design of products to be manufactured, allocation of tasks between humans and robots, and iterative improvement in product design.     

Dynamic scheduling of maintenance tasks in the petroleum industry: A reinforcement approach

Petroleum industry production systems are highly automatized. Maintenance of such systems is vital, not only to maintain production efficiency but also to insure minimal safety levels. Maintenance task scheduling is difficult since some tasks are already identified because they must be done repeatedly, and other tasks need to be identified dynamically. In this paper, we present a multi-agent approach for the dynamic maintenance task scheduling for a petroleum industry production system. Agents simultaneously insure effective maintenance scheduling and the continuous improvement of the solution quality by means of reinforcement learning, using the SARSA algorithm. Reinforcement learning allows the agents to adapt, learning the best behaviors for their various roles without reducing the performance or reactivity. To demonstrate the innovation of our approach, we include a computer simulation of our model and the results of experimentation applying our model to an Algerian petroleum refinery.     

Making DRAM refresh predictable

Embedded control systems with hard real-time constraints require that deadlines are met at all times or the system may malfunction with potentially catastrophic consequences. Schedulability theory can assure deadlines for a given task set when periods and worst-case execution times (WCETs) of tasks are known. While periods are generally derived from the problem specification, a task??s code needs to be statically analyzed to derive safe and tight bounds on its WCET. Such static timing analysis abstracts from program input and considers loop bounds and architectural features, such as pipelining and caching. However, unpredictability due to dynamic memory (DRAM) refresh cannot be accounted for by such analysis, which limits its applicability to systems with static memory (SRAM). In this paper, we assess the impact of DRAM refresh on task execution times and demonstrate how predictability is adversely affected leading to unsafe hard real-time system design. We subsequently contribute a novel and effective approach to overcome this problem through software-initiated DRAM refresh. We develop (1)?a?pure software and (2)?a?hybrid hardware/software refresh scheme. Both schemes provide predictable timings and fully replace the classical hardware auto-refresh. We discuss implementation details based on this design for multiple concrete embedded platforms and experimentally assess the benefits of different schemes on these platforms. We further formalize the integration of variable latency memory references into a data-flow framework suitable for static timing analysis to bound a task??s memory latencies with regard to their WCET. The resulting predictable execution behavior in the presence of DRAM refresh combined with the additional benefit of reduced access delays is unprecedented, to the best of our knowledge.     

KM4: Visual reasoning via Knowledge Embedding Memory Model with Mutual Modulation

Visual reasoning is a special kind of visual question answering, which is essentially multi-step and compositional, and also requires intensive text-visual interaction. The most important and challenging problem of visual reasoning is to design an effective and robust visual reasoning model. To this end, there are two challenges to overcome. The first is that textual and visual information must be jointly considered to make accurate inferences about reasoning. The second is that existing deep learning-based works are often too specific to a particular task. To address these issues, we propose a knowledge memory embedding model with mutual modulation for visual reasoning. This approach learns not only knowledge-based embeddings derived from key–value memory network to make the full and joint of textual and visual information, but also exploits the prior knowledge to improve the performance with knowledge-based representation learning for applying other general reasoning tasks. Experimental results on four benchmarks show that the proposed approach significantly improves performance compared with other state-of-the-art methods, guarantees the robustness with our model. Most importantly, we apply our model to four reasoning tasks, and experimentally show that our model effectively supports relational reasoning and improves performance in several tasks and datasets.     

Robust output maneuvering for a class of nonlinear systems

The output maneuvering problem involves two tasks. The first, called the geometric task, is to force the system output to converge to a desired path parametrized by a continuous scalar variable θ. The second task, called the dynamic task, is to satisfy a desired dynamic behavior along the path. This dynamic behavior is further specified via a time, speed, or acceleration assignment. While the main concern is to satisfy the geometric task, the dynamic task ensures that the system output follows the path with the desired speed. A robust recursive design technique is developed for uncertain nonlinear plants in vectorial strict feedback form. First the geometric part of the problem is solved. Then an update law is constructed that bridges the geometric design with the speed assignment. The design procedure is illustrated through several examples.     

A Compiler-Directed Approach to Network Latency Reduction for Distributed Shared Memory Multiprocessors

In distributed shared memory multiprocessor systems, parallel tasks communicate through sharing memory data. As the system size increases, such communication cost becomes the main factor that limits the overall parallelism and performance. In this paper, we propose a new solution to the problem through judiciously managing the relevant resource, namely, the shared data and the interconnection network (IN) through which the sharing is carried out. In this approach, communication cost is minimized by means of data migration/allocation which is based on analyzing general layered task graphs, sharing behavior of parallel tasks, and network topology. Our method is not applicable for read only variables. Further, for the time being, the usefulness of the method is limited to multiprocessors where no cache coherence mechanism is implemented. Four typical interconnection topologies for multiprocessors are considered, namely, shared-bus, hierarchical-bus, 2-D mesh, and fat-tree structures. Efficient data allocation algorithms for each of the four network topologies are developed that make decision on data allocation/migration at the compile time. The complexity of one algorithm isO(np) for shared-bus andO(n²p) for the remaining three in a system withnprocessors executing ap-layer task graph for one shared variable. We have also given an algorithm to determine optimal allocation/migration scheme for multiple shared variables. However, the cost of the algorithm become prohibitive when the number of shared variables is high. Therefore, a heuristic of low complexity is suggested. The heuristic is optimal for some topologies.