Search

Suspension-based locks are widely used in real-time systems to coordinate simultaneous accesses to exclusive shared resources. Although suspension-based locks have been well studied for sequential real-time tasks, little work has been done on this topic for parallel real-time tasks. This article for the first time studies the problem of how to extend existing sequential-task locking protocols and their analysis techniques to the parallel task model. More specifically, we extend two locking protocols OMLP and OMIP, which were designed for clustered scheduling of sequential real-time tasks, to federated scheduling of parallel real-time tasks. We present corresponding blocking analysis techniques, and develop path-oriented techniques to analyze and count blocking time. Schedulability tests with different efficiency and accuracy are further developed. Experiments are conducted to evaluate the performance of our proposed approaches against the state-of-the-art. [ABSTRACT FROM AUTHOR]

As the power density of modern CPUs is gradually increasing, thermal management has become one of the primary concerns for multicore systems, where task scheduling and dynamic voltage/frequency scaling (DVFS) play a pivotal role in effectively managing the system temperature. In this article, we propose CARTAD, a new reinforcement learning (RL)-based task scheduling and DVFS method for temperature minimization and latency guarantee on multicore systems. The novelty of CARTAD framework is that we exploit the machine learning technique to analyze the applications’ intermediate representations (IRs) generated by a compiler and identify an important feature which is critical for predicting the application’s performance. With the newly explored feature, we construct an RL-based scheduler with the more effective state representation and reward function such that the system temperature can be minimized while guaranteeing applications’ latency. We implement and evaluate CARTAD on real platforms in comparison with the state-of-the-art approaches. Experimental results show CARTAD can reduce the maximum temperature by up to 16 °C and the average temperature by up to 10 °C. [ABSTRACT FROM AUTHOR]

The communication latency in traditional network-on-chip (NoC) with hop-by-hop traversal is inherently restricted by the distance between source-destination communicating pairs. SMART, as one of the dynamically reconfigurable NoC architectures, enables the new feature of single-cycle long-distance communication by building a direct bypass path between distant cores dynamically at runtime. With the increasing of the number of integrated cores in multi/many-core systems, SMART has been deemed a promising communication backbone in such systems. However, SMART is generally optimized for average-case performance for best-effort traffics, not offering real-time guaranteed services for real-time traffics, and thus SMART often shows extremely poor real-time performance (e.g., schedulability). To make SMART latency-predictable for real-time traffics, by combining with the single-cycle bypass forwarding technique, in this article, we first propose a priority-preemptive scheduling to allow contending packets to be arbitrated according to predefined priorities. Based on the priority-based scheduling, for the real-time packet flows with given flow mapping and predefined priorities, we then propose a real-time communication analysis model, by considering shared virtual channels (or priority levels) and arbitrary-deadline real-time packet flows, to predict the worst-case communication latency and validate the schedulability. Through theoretical and experimental comparison, the worst-case communication latency of the analyzed packet flows is reduced significantly compared with that of the traditional priority-preemptive NoCs with hop-by-hop traversal and the original distance-based SMART, thus improving the schedulability. [ABSTRACT FROM AUTHOR]

Spin-Torque Transfer Magnetic RAM (STT-RAM), one of the emerging nonvolatile memory (NVM) technologies explored as the replacement for SRAM memory architectures, is particularly promising due to the fast access speed, high integration density, and zero standby power consumption. Recently, hybrid deigns with SRAM and STT-RAM buffers for routers in Network-on-Chip (NoC) systems have been widely implemented to maximize the mutually complementary characteristics of different memory technologies, and leverage the efficiency of intra-router latency and system power consumption. With the realization of Processing-in-Memory enabled by STT-RAM, in this paper, we novelly offload the execution from processors to the STT-RAM based on-chip routers to improve the application performance. On top of the hybrid buffer design in routers, we further present system-level approaches, including an ILP model and polynomial-time heuristic algorithms, to fine-tune the application mapping and scheduling on NoCs, with the objectives of improving system performance-energy efficiency. Network overhead caused by flit conflict in conventional communication circumstances can be ideally avoided by computing the contended flits in intermediate routers; meanwhile, the pressure of heavy workload on processors can be relieved by transferring partial operations to routers, such that network latency and system power consumption can be significantly reduced. Experimental results demonstrate that application schedule length and system energy consumption can be reduced by 35.62, 32.87 percent on average, respectively, in extensive evaluation experiments on PARSEC benchmark applications. In particular, the achievements of application performance and energy efficiency, averagely 36.44 and 33.19 percent, for the CNN application AlexNet have verified the practicability and effectiveness of our presented approaches. [ABSTRACT FROM AUTHOR]

Energy optimization is one of the most critical objectives for the synthesis of multiprocessor system-on-chip (MPSoC). Besides, to ensure a long processor lifetime and to maintain a safe chip temperature are also important for multiprocessor manufactures under deep submicrometer process technologies. This paper presents a mixed integer linear programming (MILP) model to determine the mapping and scheduling of real-time applications onto embedded MPSoC platforms, such that the total energy consumption is minimized with the lifetime reliability constraint and the temperature threshold constraint satisfied. We develop a lightweight temperature model that can be integrated in the MILP model to predict the chip temperature accurately and efficiently. By exploiting the dynamic voltage and frequency scaling capability of modern processors, processor voltage/frequency assignment is also considered in our MILP model. Extensive performance evaluations on synthetic and real-world applications demonstrate the effectiveness of the proposed approach. Our MILP model achieves an average reduction of 19.09% and 28.53% total energy in comparison with two state-of-the-art techniques on the basis of guaranteeing the safe chip temperature and system lifetime reliability. [ABSTRACT FROM AUTHOR]

Dark silicon refers to the phenomenon that a fraction of a many-core chip has to become “dark” or “dim” in order to guarantee the system to be kept in a safe temperature range and allowable power budget. Techniques have been developed to selectively activate non-adjacent cores on many-core chip to avoid temperature hotspot, while resulting unexpected increase of communication overhead due to the longer average distance between active cores, and in turn affecting application performance and energy efficiency, when Network-on-Chip (NoC) is used as a scalable communication subsystem. To address the brand-new challenges brought by dark silicon, in this paper, we present FoToNoC, a Folded Torus-like NoC, coupled with a hierarchical management strategy for heterogeneous many-core systems. On top of it, objectives of maximizing application performance, energy efficiency and chip reliability are isolated and well achieved by hardware-software co-design in several different phases, including application mapping and scheduling, cluster management and DVFS control. Evaluations on PARSEC benchmark applications demonstrate the significance of the entire strategy. Compared with state-of-the-art approaches, the proposed FoToNoC organization can achieve on average 35.4 and 35.2 percent on communication efficiency and application performance improvement, respectively, when maintaining the safe chip temperature. The hierarchical cluster-based management strategy can further reduce an average 34.6 percent of the total energy consumption with a notable reduction on the chip peak temperature. The significant achievements on system energy efficiency and the reduction on chip temperature of H.264 decoder and DSP-stone benchmarks additionally verify the effectiveness of the proposed methods. [ABSTRACT FROM PUBLISHER]

Network-on-chip (NoC) is promising for the communication paradigm of the next-generation multiprocessor system-on-chip (MPSoC). As communication has become an integral part of on-chip computing, and even the performance bottleneck, researchers are paying much attention to its implementation and optimization. Traditional techniques that model communication inaccurately will lead to unexpected runtime performance, which is on average 90.8% worse than the predicted results based on observation, and are not suitable for the deep optimization of communication-intensive scenarios. In this paper, techniques are presented for the NoC-based MPSoCs that integrate optimization on interprocessor communications with the objective of minimizing the schedule length. A fine-grained integer-linear programming (ILP) model is proposed to properly address the communication latency with a network contention, which generates runtime scheduling with trivial performance difference from the predictions. We further propose a heuristic algorithm, unified priority-based scheduling (UPS), to effectively solve the contention problem in polynomial time by assigning priorities to messages. Evaluation results show that the solutions obtained by the ILP model outperform the state-of-the-art techniques by 31.1%, and UPS improves application performance by 34.7% and 44.4% compared with acquainted first-in–first-out (FIFO)-based and random-based methods. In addition, UPS achieves averagely 8.3% approximated results with the optimal solutions generated by ILP. A case study on H.264 high-definition television (HDTV) decoder and the digital signal processor (DSP) filter benchmarks achieves significant improvement on the performance and the results prediction accuracy, as well as the prominent reduction in the number of network contention and energy consumption. [ABSTRACT FROM PUBLISHER]

As transistor density continues to increase with the advent of nanotechnology, reliability issues raised by more frequently appeared soft errors are becoming even more critical to the next-generation multiprocessor systems. In this paper, we present a systematic approach to address the soft-error problem in multiprocessor system-on-chip with the consideration of system performance optimization. To guarantee the system correctness, a hardware–software collaborated approach is proposed to protect the processors from soft errors. Tiny hardware sensors are embedded in the processor cores to detect the soft errors, and the software-based rollback scheduling mechanisms are applied for error recovery. The protection costs on hardware duplication and software redundancy are effectively reduced. To optimize the system performance, a distributed control system is built on top of the on-chip communication network and collaboratively manages the entire chip for application execution. With the cluster-based task migration techniques, an efficient runtime task remapping and rescheduling algorithm is proposed to further mitigate the overheads induced by soft-error protection and to minimize the total performance degradation. The distributed control strategy makes the system more adaptable and flexible to the development of the next-generation hardware and software with larger scales. Extensive performance evaluations using SystemC-based cycle-accurate simulations on a set of real-world applications show that our approach has on average 49% performance improvement and 79.6% energy consumption reduction compared with the related state-of-the-art techniques, and hardware synthesis results show that our approach only introduces 2.9% chip area overheads. [ABSTRACT FROM AUTHOR]

Shrinking the feature size allows more and better functions on a single chip. However, it makes multiprocessor system-on-chip (MPSoC) more susceptible to various reliability threats. Power supply noise is a major reliability problem faced by low power MPSoCs using power gating techniques. Powering on and off a processing unit in MPSoCs will induce large power/ground (P/G) noise and can cause timing divergence and even functional errors in surrounding processing units. Previous work on resilient architectures mainly focused on power/thermal management and neglected the important side-effect: P/G noise induced by power gating. In this paper, for the first time, we formulate a task scheduling problem with the consideration of P/G noise based on our detailed P/G noise analysis platform for MPSoC. Two efficient algorithms are proposed to reduce noise protection penalty and improve MPSoC performance. Our experiments show that both simulated annealing and heuristic algorithms can achieve on average 25% performance improvement together with up to 80% noise protection penalty saving compared with the conservative stop-go method for short tasks (shorter than 20 K clock cycles). For longer tasks up to 200 K clock cycles, the performance improvement of our methods will become relatively low. However, we can still achieve at least 35.2% noise protection penalty saving. Furthermore, a lightweight online adjustment strategy accompanying the offline scheduling method is proposed to adapt to runtime variations and improve reliability. [ABSTRACT FROM AUTHOR]

Abstract: Partial Runtime Reconfigurable (PRTR) FPGAs allow HW tasks to be placed and removed dynamically at runtime. We make two contributions in this paper. First, we present an efficient algorithm for finding the complete set of Maximal Empty Rectangles on a 2D PRTR FPGA. We also present a HW implementation of the algorithm with negligible runtime overhead. Second, we present an efficient online deadline-constrained task placement algorithm for minimizing area fragmentation on the FPGA by using an area fragmentation metric that takes into account probability distribution of sizes of future task arrivals as well as the time axis. The techniques presented in this paper are useful in an operating system for runtime reconfigurable FPGAs to manage the HW resources on the FPGA when HW tasks that arrive and finish dynamically at runtime. [Copyright &y& Elsevier]

Task graph scheduling on multiprocessor systems is a representative multiprocessor scheduling problem. A solution to this problem consists of the mapping of tasks to processors and the scheduling of tasks on each processor. Optimal solution can be obtained by exploring the entire design space of all possible mapping and scheduling choices. Since the problem is NP-hard, scalability becomes the main concern in solving the problem optimally. In this paper, a SAT-based optimization framework is proposed to address this problem, in which SAT solver is enhanced by integrating with a scheduling analysis tool in a branch and bound manner to prune the solution space efficiently. Performance evaluation results show that our technique has average performance improvement in more than an order of magnitude compared to state-of-the-art techniques. We further build a cycle-accurate network-on-chip simulator based on SystemC to verify the effectiveness of the proposed technique on realistic multiprocessor systems. [ABSTRACT FROM AUTHOR]