A fundamental problem in multithreaded parallel programs is the partial serialization that is imposed due to the presence of mutual exclusion variables or critical sections. In this work we investigate a model that considers the threads consisting of an equal number L of functional blocks, where each functional block has the same duration and either accesses a critical section or executes non-critical code. We derived formulas to estimate the average time spent in a critical section in presence of synchronization barrier and in absence of it. We also develop and establish the optimality of a fast polynomial-time algorithm to find a schedule with the shortest makespan for any number of threads and for any number of critical sections for the case of L = 2. For the general case L > 2, which is NP-complete, we present a competitive heuristic and provide experimental comparisons with the ideal integer linear programming (ILP) formulation.

Catering to society’s demand for high performance computing, billions of transistors are now integrated on IC chips to deliver unprecedented performances. With increasing transistor density, the power consumption/density is growing exponentially. The increasing power consumption directly translates to the high chip temperature, which not only raises the packaging/cooling costs, but also degrades the performance/reliability and life span of the computing systems. Moreover, high chip temperature also greatly increases the leakage power consumption, which is becoming more and more significant with the continuous scaling of the transistor size. As the semiconductor industry continues to evolve, power and thermal challenges have become the most critical challenges in the design of new generations of computing systems. In this dissertation, we addressed the power/thermal issues from the system-level perspective. Specifically, we sought to employ real-time scheduling methods to optimize the power/thermal efficiency of the real-time computing systems, with leakage/ temperature dependency taken into consideration. In our research, we first explored the fundamental principles on how to employ dynamic voltage scaling (DVS) techniques to reduce the peak operating temperature when running a real-time application on a single core platform. We further proposed a novel real-time scheduling method, “M-Oscillations” to reduce the peak temperature when scheduling a hard real-time periodic task set. We also developed three checking methods to guarantee the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research from single core platform to multi-core platform. We investigated the energy estimation problem on the multi-core platforms and developed a light weight and accurate method to calculate the energy consumption for a given voltage schedule on a multi-core platform. Finally, we concluded the dissertation with elaborated discussions of future extensions of our research.

Time-sensitive applications that are also CPU intensive like video games, video playback, eye-candy desktops etc. are increasingly common. These applications run on commodity operating systems that are targeted at diverse hardware, and hence they cannot assume that sufficient CPU is always available. Increasingly, these applications are designed to be adaptive. When executing multiple such applications, the operating system must not only provide good timeliness but also (optionally) allow co-ordinating their adaptations so that applications can deliver uniform fidelity. In this work, we present a starvation-free, fair, process scheduling algorithm that provides predictable and low latency execution without the use of reservations and assists adaptive time sensitive tasks with achieving consistent quality through cooperation. We combine an event-driven application model called cooperative polling with a fair-share scheduler. Cooperative polling allows sharing of timing or priority information across applications via the kernel thus providing good timeliness, and the fair-share scheduler provides fairness and full utilization. Our experiments show that cooperative polling leverages the inherent efficiency advantages of voluntary context switching versus involuntary pre-emption. In CPU saturated conditions, we show that the scheduling responsiveness of cooperative polling is five times better than a well-tuned fair-share scheduler, and orders of magnitude better than the best-effort scheduler used in the mainstream Linux kernel. / Science, Faculty of / Computer Science, Department of / Graduate

The coverage and energy issues are the fundamental problems which prevent the development of wireless sensor networks. In order to accurately evaluate the monitoring quality (coverage), one needs to model the interactive of sensors, phenomenons and the environment. Furthermore, in collaborative with scheduling algorithm and computer optimization, protocols can improve the overall monitoring quality and prolong the lifetime of network. This thesis is an investigation of coverage problem and its relative applications in the wireless sensor networks. We first discuss the realistic of current boolean sensing model and propose an irregular sensing model used to determine the coverage in the area with obstacles. We then investigate a joint problem of maintaining the monitoring quality and extending the lifetime of network by using scheduling schemes. Since the scheduling problem is NP hard, genetic algorithm and Markov decision process are used to determine an achievable optimal result for the joint problem of coverage-preserving and lifetime-prolong. In order to avoid the cost of centralized or distributed scheduling algorithms, a localized coverage-preserving scheduling algorithm is proposed by exploring the construction process of Voronoi diagram. Besides exploring the coverage characteristic in a static wireless sensor network, we investigate the coverage problem when the mobile elements are introduced into network. We consider the single-hop mobile data gathering problem with the energy efficiency and data freshness concerns in a wireless sensor network where the connectivity cannot be maintained. We first investigate the upper/lower bound of the covering time for a single collector to cover the monitoring area. Through our investigation we show that for a bounded rectangle area a hexagon walk could explore the area more efficiently than a random walk when the edges of area are known. We then propose a virtual force mobile model (VFM) in which the energy consumption for data transmission is modeled as a virtual elastic force and used to guide of mobile collectors to move to optimal positions for energy saving.

The purpose of this study is to examine the three scheduling systems available today as a management tool. The first two systems--Milestone Reporting and Line-of-Balance--are essentially Gantt charts which do not appear to meet the requirements for management control of scheduling. An investigation of PERT is made to see if it will provide additional controls necessary for proper scheduling.

The number of wireless systems, services, and users are constantly increasing and therefore the bandwidth requirements have become higher. One of the most robust modulations is Orthogonal Frequency-Division Multiplexing (OFDM). It has been considered as an attractive solution for future broadband wireless communications. This dissertation investigates bit and power allocation, joint resource allocation, user scheduling, and limited feedback problem in multi-user OFDM systems. The following dissertation contributes to improved OFDM systems in the following manner. (1) A low complexity sub-carrier, power, and bit allocation algorithm is proposed. This algorithm has lower computational complexity and results in performance that is comparable to that of the existing algorithms. (2) Variations of the proportional fair scheduling scheme are proposed and analyzed. The proposed scheme improves system throughput and delay time, and achieves higher throughput without sacrificing fairness which makes it a better scheme in terms of efficiency and fairness. (3) A DCT feedback compression algorithm based on sorting is proposed. This algorithm uses sorting to increase the correlation between feedback channel quality information of frequency selective channels. The feedback overhead of system is successfully reduced.

Broadcasts and timelines are the primary mechanism of information exchange in online social platforms today. Services like Facebook, Twitter and Instagram have enabled ordinary people to reach large audiences spanning cultures and countries, while their massive popularity has created increasingly competitive marketplaces of attention. Timing broadcasts to capture the attention of such geographically diverse audiences has sparked interest from many startups and social marketing gurus. However, formal study is lacking on both the timing and frequency problems. In this thesis, we introduce, motivate and solve the broadcast scheduling problem of specifying the timing and frequency of publishing content to maximise the attention received. We validate and quantify three interacting behavioural phenomena to parametrise social platform users: information overload, bursty circadian rhythms and monotony aversion, which is defined here for the first time. Our analysis of the influence of monotony refutes the common assumption that posts on social network timelines are consumed piecemeal independently. Instead, we reveal that posts are consumed in chunks, which has important consequences for any future work considering human behaviour over social network timelines. Our quantification of monotony aversion is also novel, and has applications to problems in various domains such as recommender list diversification, user satiation and variety-seeking consumer behaviour. Having studied the underlying behavioural phenomena, we link schedules, timelines, attention and behaviour by formalising a timeline information exchange process. Our formulation gives rise to a natural objective function that quantifies the expected collective attention an arrangement of posts on a timeline will receive. We apply this formulation as a case-study on real-data from Twitter, where we estimate behavioural parameters, calculate the attention potential for different scheduling strategies and, using the method of marginal allocation, discover a new scheduling strategy that outperforms popular scheduling heuristics while producing fewer posts.

Staff scheduling is one of the most important challenges that every healthcare organization faces. Long wait times due to the lack of care providers, high salary costs, rigorous work regulations, decreasing workforce availability, and other similar difficulties make it necessary for healthcare decision-makers to pay special attention to this crucial part of their management activities. Staff scheduling decisions can be very difficult. At inpatient clinics, there is not always a good estimate of the demand for services and patients can be discharged at any given time, consequently affecting staff requirements. Moreover, there are many other unpredictable factors affecting the decision process. For example, various seasonal patterns or possible staff leaves due to sickness, vacations, etc. This research describes a solution approach for staff scheduling problems at inpatient clinics where demand for services and patient discharges are considered to be stochastic. The approach is comprehensive enough to be generalizable to a wide range of different inpatient settings with different staff requirements, patient types, and workplace regulations. We first classify patients into a number of patient groups with known care-provider requirements and then develop a predictive model that captures patients’ flow and arrivals for each patient category in the inpatient clinic. This model provides a prediction of the number of patients of each type on each specific day of the planning horizon. Our predictive modelling methodology is based on a Discrete Time Markov model with the number of patients of different types as the state of the system. The predictive model generates a potentially large set of possible scenarios for the system utilization over the planning horizon. We use Monte Carlo Simulation to generate samples of these scenarios and a well known Stochastic Optimization algorithm, called the Sample Average Approximation (SAA) to find a robust solution for the problem across all possible scenarios. The algorithm is linked with a Mixed-Integer Programming (MIP) model which seeks to find the optimal staff schedule over the planning horizon while ensuring maximum demand coverage and cost efficiency are achieved. To check the validity of the proposed approach, we simulated a number of scenarios for different inpatient clinics and evaluated the model’s performance for each of them.

The desire to have enhanced and increased feature sets in embedded applications has contributed to a significant increase in the computational demands of such systems over the years. To support such demand and yet maintain reasonable power/energy budgets, the industry has begun a shift to multi-core architectures even in the embedded systems domain. Embedded real-time applications such as Avionics and Automotive systems are no exception to this trend. Such systems have strict certification requirements of subsets of their functionality, which result in strict temporal constraints on those subsets, while other subsets may have less strict requirements. Migrating such {\em mixed criticality} systems from single-core to multi-core platforms is challenging because application/component isolation and freedom from interference among them must be guaranteed. Safe and efficient, architecture-aware mapping and scheduling of system components (e.g., partitions, tasks, etc. as relevant to a particular domain) on the multiple cores is at the center of any scheme to migrate such systems from single-core to multi-core platforms. In this dissertation, we propose, develop and evaluate a unified framework to automate the mapping and scheduling process with the consideration of several architectural and application level requirements/constraints (e.g., communication and cache conflicts among system components, constraints prohibiting the allocation of certain system components on the same core, etc.)

This paper deals with the comparison of how restrictions on resources affect the performance of task scheduling in light of a multi-criterion minimization of summarized flowtime and makespan. In order to investigate the performance of three different resource restriction strategies a simulation of the task scheduling problem was created and analyzed. The results were compared by examining the mean and variance of summarized flowtime and makespan. This paper shows that restrictions on resources affects the performance of summarized flowtime and makespan. One conclusion that can be drawn from these results is that to increase performance in task scheduling with restricted resources it is vital to assign time consuming tasks to efficient resources. / Denna studie jämför hur restriktioner på resurser påverar effektiviteten av schemaläggning med hänsyn till flera mål i form av summerad responstid och total processtid. För att undersöka effektiviten av tre olika resursrestriktionsstrategier utfördes simulationer. De resulterande distributionerna jämfördes med avseende på medelvärde och standardavvikelse. Resultaten visar att effektiviteten påverkas av vilken resursrestriktionsstrategi som används. En slutstats som kan dras från detta resultat är att en ökad effektivitet vid schemaläggning med restriktioner på resurser fås då tidskrävande arbeten schemaläggs på effektiva resurser.