Implementing slot-based task-splitting multiprocessor scheduling

Consider the problem of scheduling a set of sporadic tasks on a multiprocessor system to meet deadlines using a task-splitting scheduling algorithm. Task-splitting (also called semi-partitioning) scheduling algorithms assign most tasks to just one processor but a few tasks are assigned to two or more processors, and they are dispatched in a way that ensures that a task never executes on two or more processors simultaneously. A particular type of task-splitting algorithms, called slot-based task-splitting dispatching, is of particular interest because of its ability to schedule tasks with high processor utilizations. Unfortunately, no slot-based task-splitting algorithm has been implemented in a real operating system so far. In this paper we discuss and propose some modifications to the slot-based task-splitting algorithm driven by implementation concerns, and we report the first implementation of this family of algorithms in a real operating system running Linux kernel version 2.6.34. We have also conducted an extensive range of experiments on a 4-core multicore desktop PC running task-sets with utilizations of up to 88%. The results show that the behavior of our implementation is in line with the theoretical framework behind it.

Unified overhead-aware schedulability analysis for slot-based task-splitting

Hard real- time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and global scheduling for the purposes of achieving efficient utilization of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilization bounds) and the number of preemptions/migrations involved. However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact that many unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of this new theory are evaluated by an extensive set of experiments.

CPMD-mindful task assignment for NPS-F

The multiprocessor scheduling scheme NPS-F for sporadic tasks has a high utilisation bound and an overall number of preemptions bounded at design time. NPS-F binpacks tasks offline to as many servers as needed. At runtime, the scheduler ensures that each server is mapped to at most one of the m processors, at any instant. When scheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overall number of preemptions, the migrations per se are not tightly bounded. Moreover, we cannot know a priori which task a server will be currently executing at the instant when it migrates. This uncertainty complicates the estimation of cache-related preemption and migration costs (CPMD), potentially resulting in their overestimation. Therefore, to simplify the CPMD estimation, we propose an amended bin-packing scheme for NPS-F allowing us (i) to identify at design time, which task migrates at which instant and (ii) bound a priori the number of migrating tasks, while preserving the utilisation bound of NPS-F.

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.

Landscape structure influences tree density patterns in fragmented woodlands in semi-arid eastern Australia.

Landscape and local-scale influences are important drivers of plant community structure. However, their relative contribution and the degree to which they interact remain unclear. We quantified the extent to which landscape structure, within-patch habitat and their confounding effects determine post-clearing tree densities and composition in agricultural landscapes in eastern subtropical Australia. Landscape structure (incorporating habitat fragmentation and loss) and within-patch (site) features were quantified for 60 remnant patches of Eucalyptus populnea (Myrtaceae) woodland. Tree density and species for three ecological maturity classes (regeneration, early maturity, late maturity) and local site features were assessed in one 100 × 10 m plot per patch. All but one landscape characteristic was determined within a 1.3-km radius of plots; Euclidean nearest neighbour distance was measured inside a 5-km radius. Variation in tree density and composition for each maturity class was partitioned into independent landscape, independent site and joint effects of landscape and site features using redundancy analysis. Independent site effects explained more variation in regeneration density and composition than pure landscape effects; significant predictors were the proportion of early and late maturity trees at a site, rainfall and the associated interaction. Conversely, landscape structure explained greater variation in early and late maturity tree density and composition than site predictors. Area of remnant native vegetation within a landscape and patch characteristics (area, shape, edge contrast) were significant predictors of early maturity tree density. However, 31% of the explained variation in early mature tree differences represented confounding influences of landscape and local variables. We suggest that within-patch characteristics are important in influencing semi-arid woodland tree regeneration. However, independent and confounding effects of landscape structure resulting from previous vegetation clearing may have exerted a greater historical influence on older cohorts and should be accounted for when examining woodland dynamics across a broader range of environments.

Determinants of root-associated fungal communities within Asteraceae in a semi-arid grassland

Summary

1.While plant–fungal interactions are important determinants of plant community assembly and ecosystem functioning, the processes underlying fungal community composition are poorly understood.
2.Here, we studied for the first time the root-associated eumycotan communities in a set of co-occurring plant species of varying relatedness in a species-rich, semi-arid grassland in Germany. The study system provides an opportunity to evaluate the importance of host plants and gradients in soil type and landscape structure as drivers of fungal community structure on a relevant spatial scale. We used 454 pyrosequencing of the fungal internal transcribed spacer region to analyse root-associated eumycotan communities of 25 species within the Asteraceae, which were sampled at different locations within a soil type gradient. We partitioned the variance accounted for by three predictors (host plant phylogeny, spatial distribution and soil type) to quantify their relative roles in determining fungal community composition and used null model analyses to determine whether community composition was influenced by biotic interactions among the fungi.
3.We found a high fungal diversity (156 816 sequences clustered in 1100 operational taxonomic units (OTUs)). Most OTUs belonged to the phylum Ascomycota (35.8%); the most abundant phylotype best-matched Phialophora mustea. Basidiomycota were represented by 18.3%, with Sebacina as most abundant genus. The three predictors explained 30% of variation in the community structure of root-associated fungi, with host plant phylogeny being the most important variance component. Null model analysis suggested that many fungal taxa co-occurred less often than expected by chance, which demonstrates spatial segregation and indicates that negative interactions may prevail in the assembly of fungal communities.
4.Synthesis. The results show that the phylogenetic relationship of host plants is the most important predictor of root-associated fungal community assembly, indicating that fungal colonization of host plants might be facilitated by certain plant traits that may be shared among closely related plant species.

Application of landsat images for quantifying the energy balance under conditions of land use changes in the semi-arid region of Brazil

In the Nilo Coelho irrigation scheme, Brazil, the natural vegetation has been replaced by irrigated agriculture, bringing importance for the quantification of the effects on the energy exchanges between the mixed vegetated surfaces and the lower atmosphere. Landsat satellite images and agro-meteorological stations from 1992 to 2011 were used together, for modelling these exchanges. Surface albedo (α0), NDVI and surface temperature (T0) were the basic remote sensing retrieving parameters necessary to calculate the latent heat flux (λE) and the surface resistance to evapotranspiration (rs) on a large scale. The daily net radiation (Rn) was obtained from α0, air temperature (Ta) and short-wave transmissivity (τsw) throughout the slob equation, allowing the quantification of the daily sensible heat flux (H) by residual in the energy balance equation. With a threshold value for rs, it was possible to separate the energy fluxes from crops and natural vegetation. The averaged fractions of Rn partitioned as H and λE, were in average 39 and 67%, respectively. It was observed an increase of the energy used for the evapotranspiration process inside irrigated areas from 51% in 1992 to 80% in 2011, with the ratio λE/Rn presenting an increase of 3 % per year. The tools and models applied in the current research, can subsidize the monitoring of the coupled climate and land use changes effects in irrigation perimeters, being valuable when aiming the sustainability of the irrigated agriculture in the future, avoiding conflicts among different water users. © 2012 SPIE.

EEG amplitude modulation analysis for semi-automated diagnosis of Alzheimer's disease

Recent experimental evidence has suggested a neuromodulatory deficit in Alzheimer's disease (AD). In this paper, we present a new electroencephalogram (EEG) based metric to quantitatively characterize neuromodulatory activity. More specifically, the short-term EEG amplitude modulation rate-of-change (i.e., modulation frequency) is computed for five EEG subband signals. To test the performance of the proposed metric, a classification task was performed on a database of 32 participants partitioned into three groups of approximately equal size: healthy controls, patients diagnosed with mild AD, and those with moderate-to-severe AD. To gauge the benefits of the proposed metric, performance results were compared with those obtained using EEG spectral peak parameters which were recently shown to outperform other conventional EEG measures. Using a simple feature selection algorithm based on area-under-the-curve maximization and a support vector machine classifier, the proposed parameters resulted in accuracy gains, relative to spectral peak parameters, of 21.3% when discriminating between the three groups and by 50% when mild and moderate-to-severe groups were merged into one. The preliminary findings reported herein provide promising insights that automated tools may be developed to assist physicians in very early diagnosis of AD as well as provide researchers with a tool to automatically characterize cross-frequency interactions and their changes with disease.

Semi-active control for structural vibration based on predictive algorithm [Chinese title = 基于预测算法的结构振动半主动控制]

Based on Newmark-β method, a structural vibration response is predicted. Through finding the appropriate control force parameters within certain ranges to optimize the objective function, the predictive control of the structural vibration is achieved. At the same time, the numerical simulation analysis of a two-storey frame structure with magneto-rheological (MR) dampers under earthquake records is carried out, and the parameter influence on structural vibration reduction is discussed. The results demonstrate that the semi-active control based on Newmark-β predictive algorithm is better than the classical control strategy based on full-state feedback control and has remarkable advantages of structural vibration reduction and control robustness.

Semi-analytic method of contact modelling

An algorithm to improve the accuracy and stability of rigid-body contact force calculation is presented. The algorithm uses a combination of analytic solutions and numerical methods to solve a spring-damper differential equation typical of a contact model. The solution method employs the recently proposed patch method, which especially suits the spring-damper differential equations. The resulting semi-analytic solution reduces the stiffness of the differential equations, while performing faster than conventional alternatives.

Performance tests for visual servo control systems, with application to partitioned approaches to visual servo control

Visual servoing has been a viable method of robot manipulator control for more than a decade. Initial developments involved positionbased visual servoing (PBVS), in which the control signal exists in Cartesian space. The younger method, image-based visual servoing (IBVS), has seen considerable development in recent years. PBVS and IBVS offer tradeoffs in performance, and neither can solve all tasks that may confront a robot. In response to these issues, several methods have been devised that partition the control scheme, allowing some motions to be performed in the manner of a PBVS system, while the remaining motions are performed using an IBVS approach. To date, there has been little research that explores the relative strengths and weaknesses of these methods. In this paper we present such an evaluation. We have chosen three recent visual servo approaches for evaluation in addition to the traditional PBVS and IBVS approaches. We posit a set of performance metrics that measure quantitatively the performance of a visual servo controller for a specific task. We then evaluate each of the candidate visual servo methods for four canonical tasks with simulations and with experiments in a robotic work cell.

Semi-supervised intelligent surveillance system for secure environments

This paper proposes a semi-supervised intelligent visual surveillance system to exploit the information from multi-camera networks for the monitoring of people and vehicles. Modules are proposed to perform critical surveillance tasks including: the management and calibration of cameras within a multi-camera network; tracking of objects across multiple views; recognition of people utilising biometrics and in particular soft-biometrics; the monitoring of crowds; and activity recognition. Recent advances in these computer vision modules and capability gaps in surveillance technology are also highlighted.

Analysis of the build-up of semi and non volatile organic compounds on urban roads

Vehicular traffic in urban areas may adversely affect urban water quality through the build-up of traffic generated semi and non volatile organic compounds (SVOCs and NVOCs) on road surfaces. The characterisation of the build-up processes is the key to developing mitigation measures for the removal of such pollutants from urban stormwater. An in-depth analysis of the build-up of SVOCs and NVOCs was undertaken in the Gold Coast region in Australia. Principal Component Analysis (PCA) and Multicriteria Decision tools such as PROMETHEE and GAIA were employed to understand the SVOC and NVOC build-up under combined traffic scenarios of low, moderate, and high traffic in different land uses. It was found that congestion in the commercial areas and use of lubricants and motor oils in the industrial areas were the main sources of SVOCs and NVOCs on urban roads, respectively. The contribution from residential areas to the build-up of such pollutants was hardly noticeable. It was also revealed through this investigation that the target SVOCs and NVOCs were mainly attached to particulate fractions of 75 to 300 µm whilst the redistribution of coarse fractions due to vehicle activity mainly occurred in the >300 µm size range. Lastly, under combined traffic scenario, moderate traffic with average daily traffic ranging from 2300 to 5900 and average congestion of 0.47 was found to dominate SVOC and NVOC build-up on roads.

Modulation of depth-dependent properties in tissue-engineered cartilage with a semi-permeable membrane and perfusion : a continuum model of matrix metabolism and transport

The functional properties of cartilaginous tissues are determined predominantly by the content, distribution, and organization of proteoglycan and collagen in the extracellular matrix. Extracellular matrix accumulates in tissue-engineered cartilage constructs by metabolism and transport of matrix molecules, processes that are modulated by physical and chemical factors. Constructs incubated under free-swelling conditions with freely permeable or highly permeable membranes exhibit symmetric surface regions of soft tissue. The variation in tissue properties with depth from the surfaces suggests the hypothesis that the transport processes mediated by the boundary conditions govern the distribution of proteoglycan in such constructs. A continuum model (DiMicco and Sah in Transport Porus Med 50:57-73, 2003) was extended to test the effects of membrane permeability and perfusion on proteoglycan accumulation in tissue-engineered cartilage. The concentrations of soluble, bound, and degraded proteoglycan were analyzed as functions of time, space, and non-dimensional parameters for several experimental configurations. The results of the model suggest that the boundary condition at the membrane surface and the rate of perfusion, described by non-dimensional parameters, are important determinants of the pattern of proteoglycan accumulation. With perfusion, the proteoglycan profile is skewed, and decreases or increases in magnitude depending on the level of flow-based stimulation. Utilization of a semi-permeable membrane with or without unidirectional flow may lead to tissues with depth-increasing proteoglycan content, resembling native articular cartilage.

Maintenance strategy optimization using a continuous-state partially observable semi-Markov decision process

Due to the limitation of current condition monitoring technologies, the estimates of asset health states may contain some uncertainties. A maintenance strategy ignoring this uncertainty of asset health state can cause additional costs or downtime. The partially observable Markov decision process (POMDP) is a commonly used approach to derive optimal maintenance strategies when asset health inspections are imperfect. However, existing applications of the POMDP to maintenance decision-making largely adopt the discrete time and state assumptions. The discrete-time assumption requires the health state transitions and maintenance activities only happen at discrete epochs, which cannot model the failure time accurately and is not cost-effective. The discrete health state assumption, on the other hand, may not be elaborate enough to improve the effectiveness of maintenance. To address these limitations, this paper proposes a continuous state partially observable semi-Markov decision process (POSMDP). An algorithm that combines the Monte Carlo-based density projection method and the policy iteration is developed to solve the POSMDP. Different types of maintenance activities (i.e., inspections, replacement, and imperfect maintenance) are considered in this paper. The next maintenance action and the corresponding waiting durations are optimized jointly to minimize the long-run expected cost per unit time and availability. The result of simulation studies shows that the proposed maintenance optimization approach is more cost-effective than maintenance strategies derived by another two approximate methods, when regular inspection intervals are adopted. The simulation study also shows that the maintenance cost can be further reduced by developing maintenance strategies with state-dependent maintenance intervals using the POSMDP. In addition, during the simulation studies the proposed POSMDP shows the ability to adopt a cost-effective strategy structure when multiple types of maintenance activities are involved.