Environmental stressors such as temperature, humidity, vibration, and radiation can severely impact the performance and reliability of SSDs, particularly in edge, automotive, aerospace, and datacenter deployments. Capturing sensor data in the field and conducting accelerated lab experiments are challenging, as they are time-consuming, resource-intensive, and often destructive to hardware. Specialized setups, such as thermal chambers or vibration rigs, are also required, which is why few studies explore this area, and current storage management techniques like RAID, tiering, and deduplication do not consider environmental factors. Models to capture these impacts would open new research opportunities across various fields. However, accurately modeling these effects remains challenging due to, (1) the limited availability of experimental data, (2) the complex, domino-like impact of historical exposure, (3) the interrelated nature of environmental factors, such as temperature and humidity, which exhibit correlation, (4) different response of each type of NAND flash memory TLC, MLC, and SLC to environmental factors, and (5) the difficulty that analytical and simple machine learning models face in generalizing across devices, environments, and unseen combinations of stressors. We believe that LLMs may offer a transformative alternative to this complex problem, with embedded domain knowledge and reasoning capabilities, to facilitate prompt-based natural language interaction. We propose a hybrid framework that combines Chain-of-Thought prompting and Retrieval-Augmented Generation to guide LLMs using physical principles and prior experiments. It enables interpretable "what-if" analysis of SSD behavior under environmental changes. Our results show that the LLM can effectively model the impact of temperature, humidity, and vibration on SSD performance, producing tail latency and bandwidth predictions with minimal error. The code and data are available on GitHub at https://github.com/Damrl-lab/SSD_LLM.

Homomorphic Encryption (HE) is a promising technology to protect clients’ data privacy for Machine Learning as a Service (MLaaS) on public clouds. However, HE operations can be orders of magnitude slower than their counterparts for plaintexts and thus result in prohibitively high inference latency, seriously hindering the practicality of HE. In this paper, we propose a HE-based fast neural network (NN) inference framework–SpENCNN built upon the co-design of HE operation-aware model sparsity and the single-instruction-multiple-data (SIMD)-friendly data packing, to improve NN inference latency. In particular, we first develop an encryption-aware HE-group convolution technique that can partition channels among different groups based on the data size and ciphertext size, and then encode them into the same ciphertext by novel group-interleaved encoding, so as to dramatically reduce the number of bottlenecked operations in HE convolution. We further tailor a HE-friendly sub-block weight pruning to reduce the costly HE-based convolution operation. Our experiments show that SpENCNN can achieve overall speedups of 8.37$\times$, 12.11$\times$, 19.26$\times$, and 1.87$\times$ for LeNet, VGG-5, HEFNet, and ResNet-20 respectively, with negligible accuracy loss. Our code is publicly available at https://github.com/ranran0523/SPECNN.

The marriage of Graph Convolutional Network (GCN) and Homomorphic Encryption (HE) enables the inference of graph data on the cloud with significantly enhanced client data privacy. However, the tremendous computation and memory overhead associated with HE operations challenges the practicality of HE-based GCN inference. GCN inference involves a sequence of expensive matrix-matrix multiplications, and we observe that directly applying the state-of-the-art HE-based secure matrix-matrix multiplication solutions to accelerate HE-GCN inference is far less efficient as it does not exploit the unique aggregation mechanism of two-dimension graph node-features in GCN layer computation. As a result, in this paper, we propose a novel HE-based ciphertext packing technique, i.e., Penguin, that can take advantage of the unique computation pattern during the HE-GCN inference to significantly reduce the computation and memory overhead associated with HE operations. Specifically, Penguin employs (i) an effective two-dimension parallel packing technique for feature ciphertext with optimal graph node partitioning and graph feature interleaving, and (ii) an interleaved assembly technique that can effectively make use of the blank slots to merge ciphertexts after feature reduction and significantly reduce the costly rotation operation. We provide theoretical analysis and experimental validation to demonstrate the speedup achieved by Penguin in accelerating GCN inference using popular GCN models and datasets. Our results show that Penguin can achieve up to $\sim10\times$ speedup and around $\sim79$% reduction in computational memory overhead, significantly outperforming state-of-the-art solutions. To the best of our knowledge, this is the first work that can ensure the protection of both graph structure and features when accelerating HE-GCN inference on encrypted data. Our code is publicly available at https://github.com/ranran0523/Penguin.

SSDs are becoming mainstream data storage de-vices, replacing HDDs in most data centers, consumer goods, and IoT gadgets. In this work, we ask an uncharted research question: What is the environmental conditions' impact on SSD performance? To answer it, we systematically measure, quantify, and characterize the impact of various commonly changing envi-ronmental conditions such as temperature and humidity on the performance of SSDs. Our experiments and analysis uncover that exposure to changes in temperature and humidity can significantly affect SSD performance.

Conventional learning-based speech enhancement methods usually utilize existing building blocks to design the deep neural networks (DNNs), while how to effectively integrate the statistical signal processing based schemes, which are expert-knowledge driven and could ameliorate the over-fitting problem, into the network design remains an open issue. In this paper, we extend the conventional Kalman filtering (KF) and propose a supervised-learning based neural Kalman filter (NKF) for speech enhancement. Similar to KF, the proposed method first obtains a prediction from the speech evolution model and then integrates the short-term instantaneous observation by linear weighting, and the weights are calculated by comparing between the speech prediction residual error and the environmental noise level. An end-to-end network is designed to convert the speech linear prediction model in KF to non-linear, and to compact all other conventional linear filtering operations. Different with other DNN based methods, the proposed method provides a specialized network design inspired from the conventional signal processing, the backpropagation can be directly applied on the linear filtering operations integrated from KF. We conduct experiments in different noisy conditions, and the results demonstrate that the proposed method outperforms the baseline methods which are based on either signal processing or DNNs.

As the automotive industry is moving towards electric and self-driving vehicles, how to ensure the high degree of reliability for electronic control systems (ECS) has emerged as a serious concern. Temperature plays a vital role in the reliability of ECS because vehicles are subjected to high chip temperature due to harsh operating conditions and high integrated circuit (IC) on-chip power density. In this paper, we study the problem on how to optimize the lifetime reliability and guarantee the chip's peak temperature of ECS by judiciously allocating the application to ECS. We first propose a simple mathematical programming based thermal aware approach, assuming temperature can reach a stable status immediately. We then present a genetic algorithm approach based on effective and computationally efficient methods for peak temperature identification and system-wide lifetime reliability calculation, by taking advantage of the periodicity of vehicle applications. Our experimental results, based on both synthetic test cases and practical benchmarks demonstrate the significant improvement in lifetime reliability and CPU time for automotive ECS achieved by our proposed algorithms compared to the state-of-the-art results.

Rapidly generated data and the amount magnitude of data analytical jobs pose great pressure to the underlying computing facilities. A distributed multi-cluster computing environment such as a hybrid cloud consequently raises its necessity due to its advantages in adapting geographically distributed and potentially cloud-based computing resources. Different clusters forming such an environment could be heterogeneous and may be resource-elastic as well. From analytical perspective, in accordance with increasing needs on streaming applications and timely analytical demands, many data analytical jobs nowadays are time-critical in terms of their temporal urgency. And the overall workload of the computing environment can be hybrid to contain both time-critical and general applications. These all call for an efficient resource management approach capable to apprehend both computing environment and application features.

With the exponential rise of the transistor count in one chip, the thermal problem has become a pressing issue in computing system design. While there have been extensive methods and techniques published for design optimization with thermal awareness, there is a need for more rigorous and formal thermal analysis in designing real-time systems and applications that demand a strong exception guarantee. In this article, we analytically prove a series of fundamental properties and principles concerning the RC thermal model, peak temperature identification, and peak temperature reduction for periodic real-time systems, which are general enough to be applied on 2D and 3D multi-core platforms. These findings enhance the worst-case temperature predictability in runtime scenarios, as well as help to develop more effective thermal management policy, which is key to thermal-constrained periodic real-time system design.

Allocating several Virtual Machines (VMs) onto a single server helps to increase cloud computing resource utilization and to reduce its operating expense. However, multiplexing VMs with different security levels on a single server gives rise to major VM-to-VM cybersecurity interdependency risks. In this paper, we address the problem of the static VM allocation with cybersecurity loss awareness by modeling it as a two-player zero-sum game between an attacker and a provider. We first obtain optimal solutions by employing the mathematical programming approach. We then seek to find the optimal solutions by quickly identifying the equilibrium allocation strategies in our formulated zero-sum game. We mean by "equilibrium" that none of the provider nor the attacker has any incentive to deviate from one's chosen strategy. Specifically, we study the characteristics of the game model, based on which, to develop effective and efficient allocation algorithms. Simulation results show that our proposed cybersecurity-aware consolidation algorithms can significantly outperform the commonly used multi-dimensional bin packing approaches for large-scale cloud data centers.

New DNN accelerators based on emerging technologies, such as resistive random access memory (ReRAM), are gaining increasing research attention given their potential of "in-situ" data processing. Unfortunately, device-level physical limitations that are unique to these technologies may cause weight disturbance in memory and thus compromising the performance and stability of DNN accelerators. In this work, we propose a novel fault-tolerant neural network architecture to mitigate the weight disturbance problem without involving expensive retraining. Specifically, we propose a novel collaborative logistic classifier to enhance the DNN stability by redesigning the binary classifiers augmented from both traditional error correction output code (ECOC) and modern DNN training algorithm. We also develop an optimized variable-length "decode-free" scheme to further boost the accuracy under fewer number of classifiers. Experimental results on cutting-edge DNN models and complex datasets show that the proposed fault-tolerant neural network architecture can effectively rectify the accuracy degradation against weight disturbance for DNN accelerators with low cost, thus allowing for its deployment in a variety of mainstream DNNs.

One of the most exciting advancements in Artificial Intelligence (AI) over the last decade is the wide adoption of Artificial Neural Networks (ANNs), such as Deep Neural Network (DNN) and Convolutional Neural Network (CNN), in real world applications. However, the underlying massive amounts of computation and storage requirement greatly challenge their applicability in resource-limited platforms like drone, mobile phone and IoT devices etc. The third generation of neural network model-Spiking Neural Network (SNN), inspired by the working mechanism and efficiency of human brain, has emerged as a promising solution for achieving more impressive computing and power efficiency within light-weighted devices (e.g. single chip). However, the relevant research activities have been narrowly carried out on conventional rate-based spiking system designs for fulfilling the practical cognitive tasks, underestimating SNN's energy efficiency, throughput and system flexibility. Although the time-based SNN can be more attractive conceptually, its potentials are not unleashed in realistic applications due to lack of efficient coding and practical learning schemes. In this work, a Precise-Zime-Dependent Single Spike Neuromorphic Architecture, namely “PT-Spike”, is developed to bridge this gap. Three constituent hardware-favorable techniques: precise single-spike temporal encoding, efficient supervised temporal learning and fast asymmetric decoding are proposed accordingly to boost the energy efficiency and data processing capability of the time-based SNN at a more compact neural network model size when executing real cognitive tasks. Simulation results show that “PT-Spike” demonstrates significant improvements in network size, processing efficiency and power consumption with marginal classification accuracy degradation, when compared with the rate-based SNN and ANN under the similar network configuration.

As one of most fascinating machine learning techniques, deep neural network (DNN) has demonstrated excellent performance in various intelligent tasks such as image classification. DNN achieves such performance, to a large extent, by performing expensive training over huge volumes of training data. To reduce the data storage and transfer overhead in smart resource-limited Internet-of-Thing (IoT) systems, effective data compression is a "must-have" feature before transferring real-time produced dataset for training or classification. While there have been many well-known image compression approaches (such as JPEG), we for the first time find that a human-visual based image compression approach such as JPEG compression is not an optimized solution for DNN systems, especially with high compression ratios. To this end, we develop an image compression framework tailored for DNN applications, named "DeepN-JPEG", to embrace the nature of deep cascaded information process mechanism of DNN architecture. Extensive experiments, based on "ImageNet" dataset with various state-of-the-art DNNs, show that "DeepN-JPEG" can achieve ∼ 3.5× higher compression rate over the popular JPEG solution while maintaining the same accuracy level for image recognition, demonstrating its great potential of storage and power efficiency in DNN-based smart IoT system design.

As the critical infrastructure for supporting Internet and cloud computing services, massive geo-distributed data centers are notorious for their huge electricity appetites and carbon footprints. Nonetheless, a lesser-known fact is that data centers are also “thirsty”: to operate data centers, millions of gallons of water are required for cooling and electricity production. The existing water-saving techniques primarily focus on improved “engineering” (e.g., upgrading to air economizer cooling, diverting recycled/sea water instead of potable water) and do not apply to all data centers due to high upfront capital costs and/or location restrictions. In this paper, we propose a software-based approach towards water conservation by exploiting the inherent spatio-temporal diversity of water efficiency across geo-distributed data centers. Specifically, we propose a batch job scheduling algorithm, called WACE (minimization of WAter, Carbon and Electricity cost), which dynamically adjusts geographic load balancing and resource provisioning to minimize the water consumption along with carbon emission and electricity cost while satisfying average delay performance requirement. WACE can be implemented online without foreseeing the far future information and yields a total cost (incorporating electricity cost, water consumption and carbon emission) that is provably close to the optimal algorithm with lookahead information. Finally, we validate WACE through a trace-based simulation study and show that WACE outperforms state-of-the-art benchmarks: 25 percent water saving while incurring an acceptable delay increase. We also extend WACE to joint scheduling of batch workloads and delay-sensitive interactive workloads for further water footprint reduction in geo-distributed data centers.

The ever-increasing computational demand drives modern electronic devices to integrate more processing elements for pursuing higher computing performance. However, the resulting soaring power density and potential thermal crisis constrain the system performance under a maximally allowed temperature. This paper analytically studies the throughput maximization problem of multi-core platforms under the peak temperature constraints. To take advantage of thermal heterogeneity of different cores for performance improvement, we propose to run each core with multiple speed levels and develop a schedule based on two novel concepts, i.e., the step-up schedule and the m-Oscillating schedule, for multi-core platforms. The proposed methodology can ensure the peak temperature guarantee with a significant improvement in computing throughput up to 89 percent, with an average improvement of 11 percent. Meanwhile, the computational time reduces orders of magnitude compared to the traditional exhaustive search-based approach.

Spin-transfer torque random access memory (STT-RAM) is a promising nonvolatile memory (NVM) solution to implement on-chip caches and off-chip main memories for its high integration density and short access time, but it suffers from considerable write latency and energy overhead. Aggressively relaxing its non-volatility for write fast and write energy efficient memory subsystems has been quite debatable, due to the unclear retention behavior on a timescale of microseconds-to-seconds. Moreover, recent studies project that retention failure will eventually dominate the cell reliability as STT-RAM scales. As a result, a comprehensive understanding of the thermal noise induced STT-RAM retention mechanism has become a must. In this work, we develop a compact semi-analytical model for fast retention failure analysis. We then systematically analyze critical factors (e.g., initial angle, device dimension etc.) and their impacts on the STT-RAM retention behavior through our model. Our experimental results show that STT-RAM suffers from a soft-error style retention failure, which may happen instantly just after the last write finishes and is totally different from that of DRAM and Flash, i.e., the gradual charge loss process. Our model offers an excellent agreement with the results from golden macro-magnetic simulations in the region of interest without conducting expensive Monte-Carlo runs. At last, we demonstrate our model can enable architectural designers to rethink STT-RAM based memory designs by emphasizing its probabilistic retention property.

In this paper, we study the problem of how to schedule real-time tasks on multi-core platforms to maximize the energy efficiency under a peak temperature constraint. Different from the traditional load-balancing approach, we propose energy saving solutions under the ``thermal balancing'' heuristic, which can effectively avoid hotspots and maximize the throughput. We first establish and formally prove a lower bound of energy when scheduling a periodic task set on a multi-core platform using the thermal-balancing approach. Considering the NP-nature of this problem, we formulate the problem as a variable-sized-bin-packing~(VSBP) problem and develop a partitioning heuristic.

Modern deep learning enabled artificial neural networks, such as Deep Neural Network (DNN) and Convolutional Neural Network (CNN), have achieved a series of breaking records on a broad spectrum of recognition applications. However, the enormous computation and storage requirements associated with such deep and complex neural network models greatly challenge their implementations on resource-limited platforms. Time-based spiking neural network has recently emerged as a promising solution in Neuromorphic Computing System designs for achieving remarkable computing and power efficiency within a single chip. However, the relevant research activities have been narrowly concentrated on the biological plausibility and theoretical learning approaches, causing inefficient neural processing and impracticable multilayer extension thus significantly limitations on speed and accuracy when handling the realistic cognitive tasks. In this work, a practical multilayer time-based spiking neuromorphic architecture, namely “MT-Spike”, is developed to fill this gap. With the proposed practical time-coding scheme, average delay response model, temporal error backpropagation algorithm and heuristic loss function, “MT-Spike” achieves more efficient neural processing through flexible neural model size reduction while offering very competitive classification accuracy for realistic recognition tasks. Simulation results well validate that the algorithmic power of deep multilayer learning can be seamlessly merged with the efficiency of time-based spiking neuromorphic architecture, demonstrating great potentials of “MT-Spike” in resource and power constrained embedded platforms.

Spreading across many parts of the world and presently hard striking California, extended droughts could even potentially threaten reliable electricity production and local water supplies, both of which are critical for data center operation. While numerous efforts have been dedicated to reducing data centers' energy consumption, the enormity of data centers' water footprints is largely neglected and, if still left unchecked, may handicap service availability during droughts. In this paper, we propose a water-aware workload management algorithm, called WATCH (WATer-constrained workload sCHeduling in data centers), which caps data centers' long-term water consumption by exploiting spatio-temporal diversities of water efficiency and dynamically dispatching workloads among distributed data centers. We demonstrate the effectiveness of WATCH both analytically and empirically using simulations: based on only online information, WATCH can result in a provably-low operational cost while successfully capping water consumption under a desired level. Our results also show that WATCH can cut water consumption by 20 percent while only incurring a negligible cost increase even compared to state-of-the-art cost-minimizing but water-oblivious solution. Sensitivity studies are conducted to validate WATCH under various settings.

The uncertainty due to performance variations of IC chips and resource sharing on multi-core platforms have significantly degraded the predictability of real-time systems. Traditional deterministic approaches based on the worst-case assumptions become extremely pessimistic and thus unpractical. In this article, we address the problem of scheduling a set of fixed-priority periodic real-time tasks on multi-core platforms in a probabilistic manner. Specifically, we consider task execution time as a probabilistic distribution and study how to schedule these tasks on multi-core platforms with guaranteed Quality of Service (QoS) requirements in terms of deadline-missing probabilities. Moreover, it is a well-known fact that the relationship among task periods, if exploited appropriately, can significantly improve the processor utilization. To this end, we present a novel approach to partition real-time tasks that can take both task execution time distributions and their period relationships into consideration. From our extensive experiment results, our proposed methods can greatly improve the schedulability of real-time tasks when compared with existing approaches.

Cloud data centers are widely employed to offer reliable cloud services. However, low resource utilization and high power consumption have been great challenges for cloud providers. Moreover, the rapid increase in demand for affordable cloud services magnifies the obstacles for proficient resource management policies. In this paper, we investigate how to improve resource utilization and power consumption in cloud data centers when delivering services with statistically guaranteed Quality of Service (QoS). We assume that the service provider hosts different types of services, each of which has request classes with different QoS requirements. Different from the traditional approaches that distribute workloads with different QoS levels on different Virtual Machines (VMs), we introduce an approach to pack requests of the same service type, even with different QoS requirements, into the same VM, and to remove potential failure requests in time to improve resource usage and energy cost. We formally prove that our algorithm can statistically guarantee QoS conditions in terms of deadline miss ratios. We develop a cloud prototype to empirically validate our proposed methods and algorithm. Our experimental results demonstrate that our approach can significantly outperform other traditional approaches in terms of QoS guarantees, power consumption, resource demand and electricity cost.

It is well known that a harmonic task set, i.e., task periods are integer multiples of each other, can better utilize a processor to achieve high system utilization. However, the current definition of harmonic task set is limited only to tasks with deadlines equal to their periods. In this paper, we extend the concept of "harmonic task set" to tasks with constrained deadlines, i.e., deadlines less than or equal to their periods. We show that a harmonic task set with constrained deadlines has a better schedulability than the non-harmonic one with the same task utilization. We employ this characteristic for task partitioning on multi-core platform, and our extensive experimental results show that, by taking the task harmonic relationship into consideration, our partitioning approach can greatly improve the schedulability of real-time tasks on multi-core platforms.

While multi-core architectures, by exploring the thread/process level parallelism, help to lower down the power/thermal barrier for single core architectures, power/thermal issues are still the primary limiting factors to achieve high computing performance. In this paper, we study the problem of how to maximize the computing performance of multi-core platforms without violating their peak temperature constraint. As different cores may exhibit different thermal behaviors, we propose to run each core with different working frequencies and develop a schedule based on two novel concepts, i.e. the step-up schedule and the m-Oscillating schedule, for multi-core platforms. We formally prove that the proposed schedule can guarantee the peak temperature constraint for a given multi-core platform. Compared with the traditional exhaustive search-based approach, our approach can reduce the computation time by orders of magnitude and improve the throughput up to 89%, with an average improvement of 11%.

Multicore platforms are becoming the primary choice to achieve high performance in today's embedded system design. However, under the current IC technology, the dramatic increase in power density has made the thermal issue a critical concern in design of multicore systems. In this paper, we study the problem on how to determine if a periodic dynamic voltage and frequency scaling (DVFS) schedule for a multicore platform is thermally feasible in satisfying a given peak temperature constraint. To solve this problem, we first develop a novel analytic method to quickly calculate the temperature at an arbitrary time instant, which can achieve orders-of-magnitude speedups over the HotSpot simulator. We then present an approach to pinpoint the peak temperature of a given periodic multicore DVFS schedule. Finally, we develop three methods to check the thermal feasibility of an arbitrary schedule. We formally prove the fundamental principles and validity of our proposed methods and use simulation results to demonstrate their effectiveness.

The growing environmental and sustainability concerns have made energy efficiency a pressing issue for data center operation. Governments, as well as various organizations, are urging data centers to cap the increasing energy consumption. Naturally, achieving long term energy capping involves deciding energy usage over a long timescale (without accurately foreseeing the far future) and hence, we call this process “energy budgeting”. In this paper, we introduce an online resource management solution, called eBud (energy Budgeting), for a virtualized data center. eBud determines the number of servers, resource allocation to virtual machines and corresponding workload distribution to minimize data center operational cost while satisfying a long term energy cap. We prove that eBud achieves a close-to-minimum cost compared to the optimal offline algorithm with future information, while bounding the potential violation of energy budget constraint, in an almost arbitrarily random environment. We also perform a trace-based simulation study to complement the performance analysis. The simulation results show that eBud reduces the cost by more than$\mathrm{16}$percent (compared to state-of-the-art prediction-based algorithm) while resulting in a zero energy budget deficit. We also perform an experimental study based on RUBiS, demonstrating that in a real life scenario, eBud can achieve energy capping with a negligible increase in operational cost.

The increased resource sharing on multi-core platforms has posed significant challenges on the predictability of real-time systems. Cache memory partitioning has proven to be one of the most effective methods to improve the predictability and also the schedulability of real-time systems. In this paper, we study how to allocate cache memory of a multi-core platform when scheduling fixed-priority hard real-time tasks. As the bounded worst-case execution time (WCET) of a real-time task varies with its cache allocation, the challenges of this problem are twofold: how to judiciously allocate the cache memory among all real-time tasks and how to map real-time tasks to each core to improve the schedulability. To address these challenges, we develop an approach that takes into consideration not only the WCET variations with cache allocations but also the task period relationship and thus can significantly improve the schedulability of real-time tasks. Our simulation results, based on the SPEC CPU2000 benchmarks suite, show that our approach can increase the schedulability of real-time tasks up to four times when compared to other similar scheduling mechanisms.

In this paper, we study the problem of partitioned scheduling of periodic real-time tasks with the capability of tolerating transient faults on multi-core platforms under Rate Monotonic Scheduling (RMS) policy. In our approach, we exploit the implicit relations among periods and recovery costs among tasks and develop a novel metric, called "compatibility index", to quantify how "compatible" a task set is when they are allocated on the same core. We theoretically analyze its properties for improving the system schedulability. Based on this metric, we propose two task partitioning schemes to partition hard real-time tasks with fault-tolerance requirements on multi-core platforms. Simulation results demonstrate that our proposed approaches can significantly enhance the performance of existing techniques.

Web applications grow tremendously in both scale and scope, the application patterns turn to be more and more sophisticated. It is important but challenging for service providers to lower the operational costs without degrading user experiences, especially in the case where a service provider's profit is closely related to the user experience (e.g. response time.) In this paper, we study the problem of efficiently scheduling multi-tier time sensitive applications on distributed computing platforms with respect to the user's Quality of Service (QoS) requirements. The efficiency refers to the QoS satisfaction with low average response times. The service provider must ensures that service requests be served successfully before end-to-end deadlines with certain probabilities. To solve this problem, we propose an approach to judiciously assign a deadline for each service tier. An application request is dropped if any one of its services misses its deadline. Our simulation results demonstrate that our approach can statistically guarantee the required QoS more efficiently than the other widely applied methods (e.g. acceptance control, first-come-first-serve, deterministic sub deadline assignment, etc.) irrespective of whether the resources are shared or not by multiple different applications.

Distributed soft real-time applications often involve multiple jobs that are executed on different processing units. Hence, resource competitions among these applications can be on any processing unit in the system. However, due to distributed nature of these applications, each processing unit may not have the knowledge about the workload on other processing units. Therefore, scheduling decisions made by individual processing units about their local job execution orders may not be optimal for the applications to which the jobs belong with respect to meeting the applications' end-to-end deadlines. In this paper, we first introduce a metric to measure, at a local processing unit, the risk of a distributed soft real-time application missing its end-to-end deadline. Second, based on the metric, we develop a local deadline assignment algorithm, i.e., the delay-impact-based (DIB) local deadline assignment algorithm. With the DIB algorithm, distributed processing units can independently schedule their local job sets based on the assigned job deadlines with maximized successful ratio of meeting distributed real-time applications' end-to-end deadlines. We empirically compare the DIB algorithm with three commonly used local deadline assignment algorithms, i.e., the OLDA, Pure, and Norm algorithms. The experimental results show that the DIB algorithm has clear advantage over the OLDA, Pure, and Norm approaches — it results in up to 50%, 35%, and 35% higher successful ratio than the OLDA, Pure, and Norm approaches with respect to meeting application's end-to-end deadlines, respectively. Furthermore, for those applications that do miss their end-to-end deadlines, the application execution delay ratio resulted by the DIB algorithm is also up to 300%, 50%, and 150% smaller comparing to the other three approaches.

In this article, we study the problem of how to maximize the throughput of a periodic real-time system under a given peak temperature constraint. We assume that different tasks in our system may have different power and thermal characteristics. Two scheduling approaches are presented. The first is built upon processors that can be in either active or sleep mode. By judiciously selecting tasks with different thermal characteristics as well as alternating the processor's active / sleep mode, the sleep period required to cool down the processor is kept at a minimum level, and, as the result, the throughput is maximized. We further extend this approach for processors with dynamic voltage/frequency scaling (DVFS) capability. Our experiments on a large number of synthetic test cases as well as real benchmark programs show that the proposed methods not only consistently outperform the existing approaches in terms of throughput maximization, but also significantly improve the feasibility of tasks when a more stringent temperature constraint is imposed.

This paper presents a new semipartitioned approach to schedule sporadic tasks on multicore platforms based on the Rate Monotonic Scheduling policy. To improve the schedulability, our approach exploits the fact that the utilization bound of a task set increases as task periods become closer to harmonic on single processor platforms. The challenge for our approach, however, is how to take advantage of this fact to assign and split appropriate tasks on different processors in the semipartitioned approach, and how to guarantee the schedulability of real-time tasks. We formally prove that our scheduling approach can successfully schedule any task set with a system utilization bounded by Liu&Layland's bound for N tasks, that is, N(21/N- 1). Our extensive experimental results demonstrate that the proposed algorithm can significantly improve the scheduling performance compared with the previous work.

Mobile embedded system is an excellent candidate to provides depth, breadth, and rigorousness for meeting the emerging workforce and education needs in science, technology, and engineering. However, the high requirements of investment in resources and instructors make the mobile embedded system education impractical for universities and colleges that lack the resources and build-ups. This work-in-progress paper presents a novel low-cost and portable labware for hands-on labs and projects using Android smartphones and scalable sensory platform. It is easy-to-adopt, promotes students with authentic and creative learning, and supports wide dissemination.

The advent of cloud systems has spurred the emergence of an impressive assortment of Internet services. Recent pressures on enhancing the profitability by curtailing surging dollar costs on energy have posed challenges to, as well as placed a new emphasis on, designing energy-efficient request dispatching and resource management algorithms. What further adds to the design challenge is the highly diverse nature of Internet service requests in terms of Quality-of-Service (QoS) constraints and business values. Nonetheless, most of the existing job scheduling and resource management solutions are for a single type of request and are profit oblivious. They are unable to reap the benefit of multi-service profit-aware algorithm designs. In this paper, we consider a cloud service provider operating geographically distributed data centers in a multi-electricity-market environment, and propose an energy-efficient, profit-and cost-aware request dispatching and resource allocation algorithm to maximize a service provider's net profit. We formulate the net profit maximization issue as a constrained optimization problem, using a unified task model capturing multiple cloud layers (e.g., SaaS, PaaS, IaaS.) The proposed approach maximizes a service provider's net profit by judiciously distributing service requests to data centers, powering on/off an appropriate number of servers, and allocating server resources to dispatched requests. We conduct extensive experiments to validate our proposed algorithm. Results show that our proposed approach can improve a service provider's net profit significantly.

Energy minimization is a critical issue and challenge when considering the cyclic dependency of leakage power and temperature as IC technology reaches deep sub-micron level. In this paper, we present an analytical method to calculate the energy consumption efficiently and effectively for a given voltage schedule on a multi-core platform, with the leakage/temperature dependency taken into consideration. Our experiments show that the proposed method can achieve a speedup of 15 times compared with the numerical method, with a relative error of no more than 1.5%.

Relentless technology scaling not only dramatically increased the energy consumption of modern processors, it also makes processors less reliable. In this paper, we study the energy minimization problem for real-time applications on multi-processor platforms while tolerating K transient faults using checkpointing. We first introduce an efficient method to determine the checkpointing scheme that minimizes the worst-case response time for a task set that shares the reserved recoveries on a single processor. We then present a fault-tolerant task assignment algorithm to minimize the overall energy. Experimental results show that the proposed algorithm significantly outperforms other related approaches in energy savings.

In this paper, we study the energy minimization problem for a frame-based real time system with guaranteed reliability using the checkpointing technique. We formally prove that executing a real time task set with a uniform frequency, or neighboring frequencies if the desired frequency is not available, not only optimizes its energy consumption but also achieves maximal reliability. Based on the theoretic conclusion, we further develop a Dynamic Voltage Frequency Scaling (DVFS) and checkpoint allocation strategy for a task set to guarantee both reliability and deadline constraints but with minimal energy consumption. The proposed strategy has very small frequency switching overhead as no more than one frequency change is needed for the entire task set execution and thus is particularly effective for processors with large frequency switching overhead. We further empirically compare our approach with recent work published in the literature. The experimental results show that the proposed approach can reduce as much as 15% energy consumption.

Increasingly serious concerns about the IT carbon footprints have been pushing data center operators to cap their (brown) consumption. Naturally, achieving capping involves deciding the usage over a long timescale (without foreseeing the far future) and hence, we call this process energy budgeting. The specific goal of this paper is to study budgeting for virtualized data centers from an algorithmic perspective: we develop a provably-efficient online algorithm, called eBud (energy Budgeting), which determines server CPU speed and resource allocation to virtual machines for minimizing the data center operational cost while satisfying the long-term capping constraint in an online fashion. We rigorously prove that eBud achieves a close-to-minimum cost compared to the optimal offline algorithm with future information, while bounding the potential violation of budget constraint, in an almost arbitrarily random environment. We also perform a trace-based simulation study to complement the analysis. The simulation results are consistent with our theoretical analysis and show that eBud reduces the cost by more than 60% (compared to state-of-the-art prediction-based algorithm) while resulting in a zero budget deficit.

As computers and Internet technology advance, many time-dependent applications, such as mobile navigation and online gaming, are emerging. Time-dependent applications are associated with a pair of time-dependent functions representing accrued gain at the time when tasks complete or accrued cost when tasks fail to complete, respectively. For systems that provide time-dependent services, the optimization goal is to maximize the system profit when both potential gain and potential cost exist for each request the system accepts. This paper presents two scheduling algorithms, prediction-based highest gain density first (PHGDF) and iterative PHGDF (iPHGDF) scheduling algorithms with the objective to maximize the system's total accrued profit. Simulation results provide clear evidence that, with respect to the system total accrued profit, the proposed PHGDF and iPHGDF algorithms have advantages over other commonly used scheduling algorithm, such as the Earliest Deadline First (EDF), the Generic Utility Scheduling (GUS) and the Profit and Penalty aware scheduling (PP-aware) algorithms.

As the semiconductor technology proceeds into the deep sub-micron era, leakage and its dependency with the temperature become critical in dealing with the power/energy minimization problem. In this paper, we develop an analytical method to estimate energy consumption on-line with the leakage/temperature dependency taken into consideration. Based on this method, we develop an on-line scheduling algorithm to reduce the overall energy consumption for a hard real-time system scheduled according to the Earliest Deadline First (EDF) policy. Our experimental results show that the proposed energy estimation method can achieve up to 210X speedup compared with an existing approach while still maintaining high accuracy. In addition, with a large number of different test cases, the proposed energy saving scheduling method consistently outperforms two closely related researches in average by 10% and 14% respectively.

This paper presents a new semi-partitioned approach to schedule sporadic tasks on multi-core platform based on the Rate Monotonic Scheduling (RMS) policy. Our approach exploits the well known fact that harmonic tasks have better schedulablility than non-harmonic ones on a single processor. The challenge for our approach, however, is how to take advantage of this fact to assign and split appropriate tasks on different processors in the semi-partitioned approach. We formally prove that our scheduling approach can successfully schedule any task sets with system utilizations bounded by the Liu&Layland's bound. Our extensive experiment results demonstrate that the proposed algorithm can significantly improve the scheduling performance compared with the previous work.

With the high integration density and complexity of the modern multi-core platform, thermal problems become more and more significant for both the manufacture and system designer. Dynamic thermal management technique is one effective and efficient way to mitigate and avoid thermal emergences. In this paper, we propose a novel predictive dynamic thermal management algorithm to maximize the multi-core system throughput while satisfying the peak temperature constraints. Different from the conventional approaches, we found that it is not necessarily always a good choice to migrate a hot task to the core with the lowest temperature. Instead, in our algorithm, we develop a new temperature prediction technique and migration scheme that take the local temperature of a core as well as the impacts from neighboring cores into considerations. According to our experiment results on a practical Intel desktop platform, the proposed algorithm can significantly improve the throughput compared with the conventional approach.

The paper presents our preliminary work on developing a remote hardware development lab using mixed reality technology (mRLab). The mRLab allows a group of students to remotely and simultaneously work on a VHDL project with an FPGA development board. All lab objects are created in 3D and an interactive layer on the 3D objects is added to host learning information along with caveats to assist learning.

Phase Change Memory (PCM) is emerging as one of the most promising alternative technology to the Dynamic RAM (DRAM) when building large-scale main memory systems. Even though the PCM is easy to scale, it encounters serious endurance problems. Writes are the primary wear mechanism in the PCM. The PCM can perform 108to 109times of writes before it cannot be programmed reliably. In addition, the PCM has high write latency. To prolong the lifetime of the PCM as the main memory and enhance the performance, we propose a Scratch Pad Memory (SPM) based memory mechanism and an Integer Linear Programming (ILP) memory activities scheduling algorithm to reduce the redundant write operations in the PCM. The idea of our approach is to share the data copies among the SPMs, instead of writing back to the PCM main memory each time a modify occurs. Our experimental results show that the ILP scheduling can generate the optimal schedule of memory activities with minimum write operations, reducing the number of write by up to 61%.

As transistor's feature size continues to scale down into the deep sub-micron domain, IC chip performance variation caused by manufacturing process becomes un-negligible and can cause significant discrepancies between an application's nominal design and its actual realization on individual manycore platforms. In this paper, we study the problem on how to reduce the total schedule length of a task graph when realizing its nominal design on individual Network-on-Chip(NoC) based many-core platform with faulty cores. Different from traditional approaches to re-define the mapping/scheduling decisions in the nominal design, our methods judiciously mirror the physical architecture of each individual platform to the logical platform, based on which the nominal design is conducted. To facilitate the phyical/logic architecture virtualization, we develop a performance metric based on the opportunity cost, a concept borrowed from the economics field. Three virtualization heuristics are presented in this paper. Our experimental results show that the proposed approach can achieve up to 30% with an average 15% performance improvement by taking advantage of the heterogeneity of each individual platform.

As computer and Internet technology continue to advance, real-time online services are emerging. Different from traditional real-time applications for which the scheduling objective is to meet task deadlines, the optimization goal for online service systems is to maximize profit obtained through providing timely services. For this class of applications, there are two distinctive characteristics. First, tasks are associated with a pair of time dependent functions representing accrued profit when completed before their deadlines and accrued penalty otherwise, respectively. Second, the service requests or tasks arrive aperiodically with execution time varying in a wide range. This paper presents a novel scheduling method and related analysis for such applications. Two scheduling algorithms, i.e., the nonpreemptive and preemptive Profit and Penalty aware (PP-aware) scheduling algorithms, are proposed with an objective to maximize system's total accrued profit. Our simulation results clearly demonstrate the advantages of the proposed algorithms, with respect to the system total accrued profit, over other commonly used scheduling algorithms, such as Earliest Deadline First (EDF) and Utility Accrual (UA) algorithms.

In this paper, we incorporate the dependencies among the leakage, the temperature and the supply voltage into the theoretical analysis and explore the fundamental characteristics on how to employ dynamic voltage scaling (DVS) to reduce the peak operating temperature. We find that, for a specific interval, a real-time schedule using the lowest constant speed is not necessarily the optimal choice any more in minimizing the peak temperature. We identify the scenarios when a schedule using two different speeds can outperform the one using the constant speed. In addition, we find that the constant speed schedule is still the optimal one to minimize the peak temperature at the temperature stable status when scheduling a periodic task set. We formulate our conclusions into several theorems with formal proofs.

We study the problem on how to maximize the throughput for a periodic real-time system under the given peak temperature constraint. We assume that different tasks in our system may have different power and thermal characteristics. Two algorithms are presented in this paper. The first one is built upon processors that can be either in active or sleep mode. By judiciously selecting tasks with different thermal characteristics as well as alternating the processor active/sleep mode, our approach can improve the throughput upon the existing techniques by 21% in average. We further extend this approach for processors with dynamic voltage/frequency scaling (DVFS) capability. Our experiments show that an improvement of 24% can be achieved when compared with the existing methods.

In this paper, we study the problem on how to reduce the overall energy consumption while at the same time ensuring the timing and maximum temperature constraints for a real-time system. We incorporate the interdependence of leakage, temperature and supply voltage into analysis and develop a novel method to quickly estimate the overall energy consumption. Based on this method, we then propose a scheduling technique to minimize the overall energy consumption under the maximum temperature constraint. Our experimental results show that the proposed energy estimation method can achieve up to four-order-of-magnitude speedup compared with existing approaches while keeping the maximum estimation error within 4.8%. In addition, simulation results also demonstrate that our proposed energy minimization method consistently outperforms previous related approaches significantly.

One common approach for partitioned multiprocessor scheduling problem is to transform this problem into a traditional bin-packing problem, with the utilization of a task being the "size" of the object and the utilization bound of a processor being the "capacity" of the bin. However, this approach ignores the fact that some implicit relations among tasks may significantly affect the feasibility of the tasks allocated to a processor. In this paper, we present a novel multiprocessor partitioned scheduling algorithm for fixed-priority sporadic real-time tasks based on the Rate Monotonic Scheduling (RMS) policy. Our approach takes advantage of the fact that harmonic tasks can achieve a much higher processor utilization than that defined by a utilization bound. As demonstrated in our experiment results, when taking the task period relationship into consideration, our algorithm can achieve a significant improvement over previous work.

In this paper, we introduce a novel utility accrual scheduling algorithm for real-time cloud computing services. The real-time tasks are scheduled non-preemptively with the objective to maximize the total utility. The most unique characteristic of our approach is that, different from the traditional utility accrual approach that works under one single time utility function (TUF), we have two different TUFs-a profit TUF and a penalty TUF-associated with each task at the same time, to model the real-time applications for cloud computing that need not only to reward the early completions but also to penalize the abortions or deadline misses of real-time tasks. Our experimental results show that our proposed algorithm can significantly outperform the traditional scheduling algorithms such as the Earliest Deadline First (EDF), the traditional utility accrual scheduling algorithm and an early scheduling approach based on the similar model.

While the dynamic thermal management problem is closely related to the dynamic power management problem, it has its own distinct features. In this paper, we study the feasibility checking problem for real-time periodic task sets under the peak temperature constraint. We show that the traditional scheduling approach, i.e. to repeat the schedule that is feasible through the range of one hyperperiod, does not apply any more. We then present new necessary and sufficient conditions to check the feasibility of real-time schedules. We further incorporate the close relationship of leakage, temperature, and supply voltage into our feasibility analysis, and develop more elaborated feasibility conditions. Our experiments, based on technical parameters derived from a processor using the 65 nm IC technology, demonstrate the effectiveness of our feasibility conditions and, at the same time, highlight the fact that a power/thermal-aware computing technique becomes ineffective at the submicron scale if the inter dependency of leakage, temperature, and supply voltage is not properly addressed.

As semiconductor technology continues to evolve, the chip temperature increases rapidly due to the exponentially growing power consumption. In the meantime, the high chip temperature increases the leakage power, which is becoming the dominate part in the overall power consumption for sub-micron IC circuits. A power/thermal-aware computing technique becomes ineffective if this temperature/leakage relation is not properly addressed in the sub-micron domain. In this paper, we study the feasibility problem for scheduling a hard real-time periodic task set under the peak temperature constraint, with the interaction between temperature and leakage being taken into consideration. Three analysis techniques are developed to guarantee the schedulability of periodic real-time task sets under the maximal temperature constraint. Our experiments, based on technical parameters from a processor using the 65 nm technology, show that the feasibility analysis without considering the interactions between temperature and leakage can be significantly overoptimistic.

In this paper, we present a dynamic scheduling algorithm to minimize the energy consumption by both the DVS processor and peripheral devices in a weakly hard real-time system. In our approach, we first use a new static approach to partition real-time jobs into mandatory and optional part to meet the weakly hard real-time constraints. We then adopt an on-line approach that can effectively exploit the run-time variations and reduce the preemption impacts to leverage the energy saving performance. Extensive simulation studies demonstrate that our approach can effectively reduce the system-wide energy consumption while guaranteeing the weakly hard constraints

Energy consumption has become an increasingly important consideration in designing many real-time embedded systems. Variable voltage processors, if used properly, can dramatically reduce such system energy consumption. In this paper, we present a technique to determine voltage settings for a variable voltage processor that utilizes a fixed-priority assignment to schedule jobs. By exploiting more efficiently the processor slack time, our approach can be more effective in reducing the execution speed for real-time tasks when necessary. Our approach also produces the minimum constant voltage needed to feasibly schedule the entire job set. With both randomly generated and practical examples, our heuristic approach can achieve the dynamic energy reduction very close to the theoretically optimal one (within 2%) with much less computation cost.

Time transition overhead is a critical problem for hard real-time systems that employ dynamic voltage scaling (DVS) for power and energy management. While it is a common practice of much previous work to ignore transition overhead, these algorithms cannot guarantee deadlines and/or are less effective in saving energy when transition overhead is significant and not appropriately dealt with. In this article we introduce two techniques, one offline and one online, to correctly account for transition overhead in preemptive fixed-priority real-time systems. We present several DVS scheduling algorithms that implement these methods that can guarantee task deadlines under arbitrarily large transition time overheads and reduce energy consumption by as much as 40% when compared to previous methods.

Energy reduction is critical to increase the mobility and battery life for today's pervasive portable computing systems. At the same time, energy reduction must be subject to the real-time constraints and quality of service (QoS) requirements for multimedia applications running on many of these systems. This paper presents a novel run-time scheduling approach to reduce the system-wide energy consumption for such systems. In this paper, the multimedia applications are modeled using a popular weakly hard realtime model, i.e., the (m,k)-model. Our experimental results show that, by judiciously scheduling the real-time tasks and shutting down the processor and/or peripheral devices, our approach can lead to significant energy savings while guaranteeing the (m,k) firm deadlines at the same time

Energy consumption and quality of service (QoS) are two primary concerns in the development of today's pervasive computing systems. While most of the current research in energy-aware real-time scheduling has been focused on hard real-time systems, a large number of practical applications and systems exhibit more soft real-time nature. In this paper, we study the problem of minimizing energy for soft real-time systems while providing a QoS guarantee. The QoS requirements are deterministically quantified with the (m,k)-constraints, which require that at least m out of any k consecutive jobs of a task meet their deadlines. In this paper, we propose a hybrid approach to achieve the dual goals of QoS guarantee and energy minimization. We first present the necessary and sufficient schedulability conditions for the static mandatory/optional workload partitioning. Then, we propose to dynamically vary the statically defined mandatory/optional partitions to accommodate dynamic run-time variations while minimizing the energy consumption. The experimental results demonstrate that our proposed techniques outperform previous work significantly in terms of both the energy savings and achieved QoS.

We present an online dynamic voltage scaling (DVS) algorithm for preemptive fixed-priority real-time systems called low power limited demand analysis with transition overhead (lpLDAT). It is the first algorithm in its class to explicitly account for transition overhead, and can reduce the energy consumption by as much as 40% when compared to previous methods.

Energy reduction is critical to increase the mobility and to extend the mission period in the development of today's pervasive computing systems. On the other hand, however, energy reduction must be subject to the requirements not to compromise the quality of service (QoS) that these systems need to provide. While most of the current research in energy-aware real-time scheduling has been focused on hard real-time systems, a large number of practical applications and systems exhibit more soft real-time nature. In this paper, we study the problem of minimizing energy for soft real-time systems with the requirements of QoS-guarantee. The QoS requirements are deterministically quantified with the (m, k)-constraints, which require that at least m out of any k consecutive jobs of a task meet their deadlines. To deal with the dynamic characteristics of such applications and systems, we propose a hybrid static/dynamic scheduling approach that can efficiently reduce the energy consumption while guaranteeing the (m, k)-constraints. The experimental results demonstrate that our proposed techniques outperform previous research significantly in terms of both the energy savings and QoS that can be achieved.

While the dynamic voltage scaling (DVS) techniques are efficient in reducing the dynamic energy consumption for the processor, varying voltage alone becomes less effective for the overall power reduction as the leakage power is growing rapidly, i.e., five times per technical generation as predicted. In this paper, we study the problem of reducing both the static and dynamic power consumption at the same time for the hard real-time system scheduled by the earliest deadline first (EDF) strategy. To balance the dynamic and leakage energy consumption, higher-than-necessary processor speeds may be required when executing real-time tasks, which can result in a large number of idle intervals. To effectively reduce the energy consumption during these idle intervals, we propose a technique that can effectively merge these scattered intervals into larger ones without causing any deadline miss. Simulation studies demonstrate the effectiveness of our approach. Specifically, our experiments show that the proposed technique can lead up to more than 80% idle energy savings than that by the previous ones.

While dynamic voltage scaling (DVS) is an efficient technique in reducing the dynamic energy consumption of a CMOS processor, methods that employ DVS without considering leakage current are quickly becoming less efficient when considering the processor's overall energy consumption. A leakage conscious DVS voltage schedule may require the processor to run at a higher-than-necessary speed to execute a given set of real-time tasks, which can result in a large number of idle intervals. To effectively reduce the energy consumption during these idle intervals, and therefore the overall energy consumption, the DVS schedule must judiciously allow the processor to enter and leave the power down state during these idle intervals, while considering the time and energy cost of doing so. In this paper, we present a scheduling technique that can effectively reduce the overall energy consumption for hard real-time systems scheduled according to a fixed priority (FP) scheme. Experimental results demonstrate that a processor using our strategy consumes as less as 15% of the idle energy of a processor employing the conventional strategy.

Voltage scheduling is an essential technique used to exploit the benefit of dynamic voltage-scaling processors. Though extensive research exists in this area, current processor limitations such as time and energy transition overhead and voltage-level discretization are often dismissed as insignificant. We show that for hard real-time applications, disregarding these details can lead to suboptimal or even invalid results. We propose two algorithms to account for these limitations. The first is a greedy approach, while the second is more complex, but can significantly reduce the system's energy consumption. Through experimental results on both real and randomly generated systems, we show the effectiveness of both algorithms and explore what conditions make it beneficial to use the complex algorithm over the basic one.

To fully exploit the benefit of variable voltage processors, voltage schedules must be designed in the context of work load requirement. In this paper, we present an approach to finding the least-energy voltage schedule for executing real-time jobs on such a processor according to a fixed priority, preemptive policy. The significance of our approach is that the theoretical limit in terms of energy saving for such systems is established, which can, thus, serve as the standard to evaluate the performance of various heuristic approaches. Two algorithms for deriving the optimal voltage schedule are provided. The first one explores fundamental properties of voltage schedules while the second one builds on the first one to further reduce the computational cost. Experimental results are shown to compare the results of this paper with previous ones.

To fully exploit the benefit of variable voltage processors, voltage schedules must be designed in the context of work load requirement. In this paper, we present an approach to finding the least-energy voltage schedule for executing real-time jobs on such a processor according to a fixed priority, preemptive policy. The significance of our approach is that the theoretical limit in terms of energy saving for such systems is established, which can thus serve as the standard to evaluate the performance of various heuristic approaches. Two algorithms for deriving the optimal voltage schedule are provided. The first one explores fundamental properties of voltage schedules while the second one builds on the first one to further reduce the computational cost. Experimental results are shown to compare the results of this paper with previous ones.

Voltage scheduling is indispensable for exploiting the benefit of variable voltage processors. Though extensive research has been done in this area, current processor limitations such as transition overhead and voltage level discretization are often considered insignificant and are typically ignored. We show that for hard, real-time applications, disregarding such details can lead to sub-optimal or even invalid results. We propose two algorithms that guarantee valid solutions. The first is a greedy yet simple approach, while the second is more complex but significantly reduces energy consumption under certain conditions. Through experimental results on both real and randomly generated systems, we show the effectiveness of both algorithms, and explore what conditions make it beneficial to use the complex algorithm over the basic one.

Energy consumption has become an increasingly important consideration in designing many real-time embedded systems. Variable voltage processors, if used properly, can dramatically reduce such system energy consumption. In this paper, we present a technique to determine voltage settings for a variable voltage processor that utilizes a fixed priority assignment to schedule jobs. Our approach also produces the minimum constant voltage needed to feasibly schedule the entire job set. Our algorithms lead to significant energy saving compared with previously presented approaches.

Studies the problem of scheduling task sets with (m,k) constraints. In our approach, jobs of each task are partitioned into two sets: mandatory and optional. Mandatory jobs are scheduled according to their pre-defined priorities, while optional jobs are assigned to the lowest priority. We show that finding the optimal partition as well as determining the schedulability of the resultant task set are both NP-hard problems. A new technique, based on the general Chinese remainder theorem, is proposed to quantify the interference among tasks, which is then used to derive two partitioning approaches. Furthermore, a sufficient condition is presented to predict, in polynomial time, the schedulability of mandatory jobs. We prove that our partitions are never worse than those obtained in previous work. Experimental results also show significant improvement achieved by our approaches.

Much effort in hardware/software co-design has been devoted to developing "push-button" types of tools for automatic hardware/software partitioning. However, given the highly complex nature of embedded system design, user guided design exploration can be more effective. In this paper, we propose a fi'amework for designer assisted partitioning that can be used in conjunction with any given search strategy. A key component of this fi'amework is the visualization of the design space, without enumerating all possible design configurations. Furthermore, this design space representation provides a straightforward way for a designer to identify promising partitions and hence guide the subsequent exploration process. Experiments have shown the effectiveness of this approach.

We present a hierarchical evolutionary approach to hardware/software partitioning for real-time embedded systems. In contrast to most previous approaches, we apply a hierarchical structure and dynamically determine the granularity of tasks and hardware modules to adaptively optimize the solution while keeping the search space as small as possible. Two new search operators are described, which exploit the proposed hierarchical structure. Efficient ranking is another problem addressed. Imprecisely specified multiple attribute utility theory has the advantage of constraining the solution space computation overhead. We propose a new technique to reduce the overhead. Experiment results show that our algorithm is both effective and efficient.