Real-time scheduling of embedded applications on multi-core platforms

For the past several decades, we have experienced the tremendous growth, in both scale and scope, of real-time embedded systems, thanks largely to the advances in IC technology. However, the traditional approach to get performance boost by increasing CPU frequency has been a way of past. Researchers from both industry and academia are turning their focus to multi-core architectures for continuous improvement of computing performance. In our research, we seek to develop efficient scheduling algorithms and analysis methods in the design of real-time embedded systems on multi-core platforms. Real-time systems are the ones with the response time as critical as the logical correctness of computational results. In addition, a variety of stringent constraints such as power/energy consumption, peak temperature and reliability are also imposed to these systems. Therefore, real-time scheduling plays a critical role in design of such computing systems at the system level. We started our research by addressing timing constraints for real-time applications on multi-core platforms, and developed both partitioned and semi-partitioned scheduling algorithms to schedule fixed priority, periodic, and hard real-time tasks on multi-core platforms. Then we extended our research by taking temperature constraints into consideration. We developed a closed-form solution to capture temperature dynamics for a given periodic voltage schedule on multi-core platforms, and also developed three methods to check the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research by incorporating the power/energy constraint with thermal awareness into our research problem. We investigated the energy estimation problem on multi-core platforms, and developed a computation efficient method to calculate the energy consumption for a given voltage schedule on a multi-core platform. In this dissertation, we present our research in details and demonstrate the effectiveness and efficiency of our approaches with extensive experimental results.

Scheduling of track inspection and maintenance activities in railroad networks

The U.S. railroad companies spend billions of dollars every year on railroad track maintenance in order to ensure safety and operational efficiency of their railroad networks. Besides maintenance costs, other costs such as train accident costs, train and shipment delay costs and rolling stock maintenance costs are also closely related to track maintenance activities. Optimizing the track maintenance process on the extensive railroad networks is a very complex problem with major cost implications. Currently, the decision making process for track maintenance planning is largely manual and primarily relies on the knowledge and judgment of experts. There is considerable potential to improve the process by using operations research techniques to develop solutions to the optimization problems on track maintenance. In this dissertation study, we propose a range of mathematical models and solution algorithms for three network-level scheduling problems on track maintenance: track inspection scheduling problem (TISP), production team scheduling problem (PTSP) and job-to-project clustering problem (JTPCP). TISP involves a set of inspection teams which travel over the railroad network to identify track defects. It is a large-scale routing and scheduling problem where thousands of tasks are to be scheduled subject to many difficult side constraints such as periodicity constraints and discrete working time constraints. A vehicle routing problem formulation was proposed for TISP, and a customized heuristic algorithm was developed to solve the model. The algorithm iteratively applies a constructive heuristic and a local search algorithm in an incremental scheduling horizon framework. The proposed model and algorithm have been adopted by a Class I railroad in its decision making process. Real-world case studies show the proposed approach outperforms the manual approach in short-term scheduling and can be used to conduct long-term what-if analyses to yield managerial insights. PTSP schedules capital track maintenance projects, which are the largest track maintenance activities and account for the majority of railroad capital spending. A time-space network model was proposed to formulate PTSP. More than ten types of side constraints were considered in the model, including very complex constraints such as mutual exclusion constraints and consecution constraints. A multiple neighborhood search algorithm, including a decomposition and restriction search and a block-interchange search, was developed to solve the model. Various performance enhancement techniques, such as data reduction, augmented cost function and subproblem prioritization, were developed to improve the algorithm. The proposed approach has been adopted by a Class I railroad for two years. Our numerical results show the model solutions are able to satisfy all hard constraints and most soft constraints. Compared with the existing manual procedure, the proposed approach is able to bring significant cost savings and operational efficiency improvement. JTPCP is an intermediate problem between TISP and PTSP. It focuses on clustering thousands of capital track maintenance jobs (based on the defects identified in track inspection) into projects so that the projects can be scheduled in PTSP. A vehicle routing problem based model and a multiple-step heuristic algorithm were developed to solve this problem. Various side constraints such as mutual exclusion constraints and rounding constraints were considered. The proposed approach has been applied in practice and has shown good performance in both solution quality and efficiency.

Effects of visuospatial tasks on desensitization to emotive memories

Objectives. Intrusive memories of extreme trauma can disrupt a stepwise approach to imaginal exposure. Concurrent tasks that load the visuospatial sketchpad (VSSP) of working memory reduce the vividness of recalled images. This study tested whether relief of distress from competing VSSP tasks during imaginal exposure is at the cost of impaired desensitization . Design. This study examined repeated exposure to emotive memories using 18 unselected undergraduates and a within-subjects design with three exposure conditions (Eye Movement, Visual Noise, Exposure Alone) in random, counterbalanced order. Method. At baseline, participants recalled positive and negative experiences, and rated the vividness and emotiveness of each image. A different positive and negative recollection was then used for each condition. Vividness and emotiveness were rated after each of eight exposure trials. At a post-exposure session 1 week later, participants rated each image without any concurrent task. Results. Consistent with previous research, vividness and distress during imaging were lower during Eye Movements than in Exposure Alone, with passive visual interference giving intermediate results. A reduction in emotional responses from Baseline to Post was of similar size for the three conditions. Conclusion. Visuospatial tasks may offer a temporary response aid for imaginal exposure without affecting desensitization.

A framework for determining the authenticity of assessment tasks : applied to an example in law

Authentic assessment tasks enhance engagement, retention and the aspirations of students. This paper explores the discipline-generic features of authentic assessment, which reflect what students need to achieve in the real world. Some assessment tasks are more authentic than others and this paper designs a proposed framework supported by the literature that aids unit co-ordinators to determine the level of authenticity of an assessment task. The framework is applied to three summative assessment tasks, that is, tutorial participation, advocacy exercise and problem-based exam, in a law unit. The level of authenticity of the assessment tasks is compared and opportunities to improve authenticity are identified.

Coordinated control of grid connected photovoltaic reactive power and battery energy storage systems to improve the voltage profile of a residential distribution feeder

Increasing penetration of photovoltaic (PV) as well as increasing peak load demand has resulted in poor voltage profile for some residential distribution networks. This paper proposes coordinated use of PV and Battery Energy Storage (BES) to address voltage rise and/or dip problems. The reactive capability of PV inverter combined with droop based BES system is evaluated for rural and urban scenarios (having different R/X ratios). Results show that reactive compensation from PV inverters alone is sufficient to maintain acceptable voltage profile in an urban scenario (low resistance feeder), whereas, coordinated PV and BES support is required for the rural scenario (high resistance feeder). Constant as well as variable droop based BES schemes are analyzed. The required BES sizing and associated cost to maintain the acceptable voltage profile under both schemes is presented. Uncertainties in PV generation and load are considered, with probabilistic estimation of PV generation and randomness in load modeled to characterize the effective utilization of BES. Actual PV generation data and distribution system network data is used to verify the efficacy of the proposed method.

Measurement of energy expenditure of daily tasks among mothers of young children

There is currently some debate about whether the energy expenditure of domestic tasks is sufficient to confer health benefits. The aim of this study was therefore to measure the energy cost of five activities commonly undertaken by mothers of young children. Seven women with at least one child younger than five years of age spent 15 minutes in each of the following activities: sitting quietly, vacuum cleaning, washing windows, walking at moderate pace (approx 5km/hour), walking with a stroller and grocery shopping in a super-market. Each of the six 'trials' was completed on the same day, in random order. A carefully calibrated portable gas analyser was used to measure oxygen uptake during each activity, and data were converted to units of energy expenditure (METS). Vacuum cleaning, washing windows and walking with and without a stroller were found to be 'moderate intensity activities' (3 to 6 METs), but supermarket shopping did not reach this criterion. The MET values for these activities were similar to those reported in the Compendium of Physical Activities (Ainsworth et al., 2000). However, the energy expenditures of walking, both with and without a stroller, were higher than those reported in the Compendium. The findings suggest that some of the tasks associated with domestic caring duties are conducted at an intensity which is sufficient to confer some health benefit. Such benefits will only accrue however if the daily duration of these activities is sufficient to meet current guidelines.

A direct integration scheme for battery-supercapacitor hybrid energy storage systems with the use of grid side inverter

Battery-supercapacitor hybrid energy storage systems are becoming popular in the renewable energy sector due to their improved power and energy performances. These hybrid systems require separate dc-dc converters, or at least one dc-dc converter for the supercapacitor bank, to connect them to the dc-link of the grid interfacing inverter. These additional dc-dc converters increase power losses, complexity and cost. Therefore, possibility of their direct connection is investigated in this paper. The inverter system used in this study is formed by cascading two 3-level inverters, named as the “main inverter” and the “auxiliary inverter”, through a coupling transformer. In the test system the main inverter is connected with the rectified output of a wind generator while the auxiliary inverter is directly attached to a battery and a supercapacitor bank. The major issues with this approach are the dynamic changes in dc-link voltages and inevitable imbalances in the auxiliary inverter voltages, which results in unevenly distributed space vectors. A modified SVM technique is proposed to solve this issue. A PWM based time sharing method is proposed for power sharing between the battery and the supercapacitor. Simulation results are presented to verify the efficacy of the proposed modulation and control techniques.

A Battery Energy Storage interface for wind power systems with the use of grid side inverter

This paper presents a novel concept of Energy Storage System (ESS) interfacing with the grid side inverter in wind energy conversion systems. The inverter system used here is formed by cascading a 2-level inverter and a three level inverter through a coupling transformer. The constituent inverters are named as the “main inverter” and the “auxiliary inverter” respectively. The main inverter is connected with the rectified output of the wind generator while the auxiliary inverter is attached to a Battery Energy Storage System (BESS). The BESS ensures constant power dispatch to the grid irrespective of change in wind condition. Furthermore, this unique combination of BESS and inverter eliminates the need of additional dc-dc converters. Novel modulation and control techniques are proposed to address the problem of non-integer, dynamically-changing dc-link voltage ratio, which is due to random wind changes. Strategies used to handle auxiliary inverter dc-link voltage imbalances and controllers used to charge batteries at different rates are explained in detail. Simulation results are presented to verify the efficacy of the proposed modulation and control techniques in suppressing random wind power fluctuations.

Optimal scheduling of hydro-thermal power systems under shortage

The problem of optimal scheduling of the generation of a hydro-thermal power system that is faced with a shortage of energy is studied. The deterministic version of the problem is first analyzed, and the results are then extended to cases where the loads and the hydro inflows are random variables.

Efficient scheduling of sensor activity for information coverage in wireless sensor networks

In this paper, we are concerned with algorithms for scheduling the sensing activity of sensor nodes that are deployed to sense/measure point-targets in wireless sensor networks using information coverage. Defining a set of sensors which collectively can sense a target accurately as an information cover, we propose an algorithm to obtain Disjoint Set of Information Covers (DSIC), which achieves longer network life compared to the set of covers obtained using an Exhaustive-Greedy-Equalized Heuristic (EGEH) algorithm proposed recently in the literature. We also present a detailed complexity comparison between the DSIC and EGEH algorithms.

Analysis of grid connected induction generators driven by hydro/wind turbines under realistic system constraints

Results of an investigation dealing with the behaviour of grid-connected induction generators (GCIGs) driven by typical prime movers such as mini-hydro/wind turbines are presented. Certain practical operational problems of such systems are identified. Analytical techniques are developed to study the behavior of such systems. The system consists of the induction generator (IG) feeding a 11 kV grid through a step-up transformer and a transmission line. Terminal capacitors to compensate for the lagging VAr are included in the study. Computer simulation was carried out to predict the system performance at the given input power from the turbine. Effects of variations in grid voltage, frequency, input power, and terminal capacitance on the machine and system performance are studied. An analysis of self-excitation conditions on disconnection of supply was carried out. The behavior of a 220 kW hydel system and 55/11 kW and 22 kW wind driven system corresponding to actual field conditions is discussed

Optimal scheduling of a processor executing a communication protocol stack

We consider the problem of optimally scheduling a processor executing a multilayer protocol in an intelligent Network Interface Controller (NIC). In particular, we assume a typical LAN environment with class 4 transport service, a connectionless network service, and a class 1 link level protocol. We develop a queuing model for the problem. In the most general case this becomes a cyclic queuing network in which some queues have dedicated servers, and the others have a common schedulable server. We use sample path arguments and Markov decision theory to determine optimal service schedules. The optimal throughputs are compared with those obtained with simple policies. The optimal policy yields upto 25% improvement in some cases. In some other cases, the optimal policy does only slightly better than much simpler policies.