In the world of real-time systems (RTS), security has often been overlooked in the design process. However, with the emergence of the Internet of Things and Cyber-Physical Systems, RTS are now frequently used in interconnected applications where data is shared regularly. Unfortunately, this increased connectivity has also led to a larger attack surface. As a result, it is crucial to redesign RTS to not only meet real-time requirements but also to be resilient to threats. To address this issue, we propose a new real-time security co-design task model, and an accompanying scheduling framework, where schedulability can be used to indicate whether both real-time and security requirements are met. Our algorithm is designed to be flexible, allowing different security mechanisms to be used along with real-time tasks. Specifically, we augment the frame-based task model by introducing an n-dimensional security matrix, which serves as a powerful tool to enable our approach. This matrix clearly indicates which defense mechanisms are available for each task in the system by storing the worst-case execution times of tasks. Then, we transform the problem of maximizing security, subject to schedulability, into a variant of the knapsack problem. To make this approach more practical, we implement a fully polynomial time approximation scheme (FPTAS) that reduces the time complexity of solving the knapsack problem from a pseudo-polynomial to a fully polynomial. We also experiment with a greedy-heuristic approach and compare the results of both algorithms. / Master of Science / Real-time systems are computer systems that need to respond to events in a timely manner. In the past, these systems were designed without much consideration for security. However, with the increasing use of interconnected devices and systems, it has become important to make sure that real-time systems are secure and protected against malicious attacks. To address this issue, we propose a new approach for designing real-time systems that prioritizes security from the very beginning. Our approach allows for different security tasks to be executed depending on the system's needs, and we use a two-dimensional security matrix to help with this. We also introduce a way to solve the security problem that is faster and more efficient than previous methods. Our experimental results show that our new approach significantly reduces the time and effort required to solve the security problem while still producing good results.

Heterogeneity is increasing across all levels of computing, with the rise of accelerators such as GPUs, FPGAs, and other coprocessors into everything from cell phones to supercomputers. More quietly it is increasing with the rise of NUMA systems, hierarchical caching, OS noise, and a myriad of other factors. As heterogeneity becomes a fact of life, efficiently managing heterogeneous compute resources is becoming a critical, and ever more complex, task. The focus of this dissertation is to lay the foundation for an autonomic system for heterogeneous computing, employing runtime adaptation to improve performance portability and performance consistency while maintaining or increasing programmability. We investigate heterogeneity arising from a myriad of factors, grouped into the dimensions of locality and capability. This work has resulted in runtime schedulers capable of automatically detecting and mitigating heterogeneity in physically homogeneous systems through MPI and adaptive coscheduling for physically heterogeneous accelerator based systems as well as a synthesis of the two to address multiple levels of heterogeneity as a coherent whole. We also discuss our current work towards the next generation of fine-grained scheduling and synchronization across heterogeneous platforms in the design of a highly-scalable and portable concurrent queue for many-core systems. Each component addresses aspects of the urgent need for automated management of the extreme and ever expanding complexity introduced by heterogeneity. / Ph. D.

The big data era has driven the needs for data analysis in every aspect of our daily lives. With the rapid growth of data size and complexity of data analysis models, modern big data analytic applications face the challenge to provide timely results often with limited resources. Such demand drives the growth of new hardware resources including GPUs and FPGAs, as well as storage devices such as SSDs and NVMs. It is challenging to manage the resources available in a cost restricted environment to best serve the applications with different characteristics. Extant approaches are agnostic to such heterogeneity in both underlying resources and workloads and require user knowledge and manual configuration for best performance. In this dissertation, we design, and implement a series of novel techniques, algorithms, and frameworks, to realize workload-aware resource management and scheduling. We demonstrate our techniques for efficient resource management across memory resource for in-memory data analytic platforms, processing resources for compute-intensive machine learning applications, and finally we design and develop a workload and heterogeneity-aware scheduler for general big data platforms. The dissertation demonstrates that designing an effective resource manager requires efforts from both application and system side. The presented approach makes and joins the efforts on both sides to provide a holistic heterogeneity-aware resource manage and scheduling system. We are able to avoid task failure due to resource unavailability by workload-aware resource management, and improve the performance of data processing frameworks by carefully scheduling tasks according to the task characteristics and utilization and availability of the resources. / Ph. D. / Clusters of multiple computers connected through internet are often deployed in industry for larger scale data processing or computation that cannot be handled by standalone computers. In such a cluster, resources such as CPU, memory, disks are integrated to work together. It is important to manage a pool of such resources in a cluster to efficiently work together to provide better performance for workloads running on top. This role is taken by a software component in the middle layer called resource manager. Resource manager coordinates the resources in the computers and schedule tasks to them for computation. This dissertation reveals that current resource managers often partition resources statically hence cannot capture the dynamic resource needs of workloads as well as the heterogeneous configurations of the underlying resources. For example, some computers in a clsuter might be older than the others with slower CPU, less memory, etc. Workloads can show different resource needs. Watching YouTube require a lot of network resource while playing games demands powerful GPUs. To this end, the disseration proposes novel approaches to manage resources that are able to capture the heterogeneity of resources and dynamic workload needs, based on which, it can achieve efficient resource management, and schedule the right task to the right resource.

Model-based design based on the Simulink modeling formalism and the associated toolchain has gained its popularity in the development of complex embedded control systems. However,the current research on software synthesis for Simulink models has a critical gap for providing a deterministic, semantics-preserving implementation on multicore architectures with partitioned fixed-priority scheduling. In this thesis, we propose to judiciously assign task offset, task priority, and task communication mechanism, to avoid simultaneous access to shared memory by tasks on different cores, to preserve the model semantics, and to optimize the control performance. We develop two approaches to solve the problem: (a) a mixed integer linear programming (MILP) formulation; and (b) a problem specific exact algorithm that may run several magnitudes faster than MILP. / Master of Science / To save development time and money, automotive industries have been developing models using software, before implementing them directly on hardware. For reliability, the model generated from the software tool should behave in a well defined manner, coherent to the ideal design of the model. While the current tools are able to generate this reliable model for a single processor system, they are not able to do so for a system with multiple processors. When two or more processors contend to access the same resource at the same time, the existing tools are unable to provide a well defined execution order in their model. Since modern embedded systems need multiple processors to meet their increasing performance demands, it is imperative that the software tools scale up to multiple processors as well. In this work, we seek to bridge this gap by presenting two solutions that generate a deterministic software implementation of a system with multiple processors. In our solutions, we generate a model with well defined execution order by ensuring that at any given time, only one processor accesses a given resource. Furthermore, apart from ensuring determinism, we also improve upon the performance of the generated model by ensuring that there is minimal end-to-end latency in the system.

The purpose of this thesis is to investigate the effectiveness of executing High Performance Computing (HPC) workloads on multiprocessors with heterogeneous Instruction Set Architecture (ISA) cores. ISA-heterogeneity in processor designs provides a unique dimension for researchers to explore performance benefits through diversity in design choices. Additionally, each application has a natural preference to one processor in a selected group of processors (we defined this term as processor-preference), and processor-preference is highly affected by processor design choices. Thus, a system with heterogeneous-ISA cores offers an intriguing design perspective, packing heterogeneous-ISA cores in the same processor or system that compensate each other in dynamic workload scenarios. This thesis considers dynamic migrating applications with different processor-preferences across ISA-different cores to exploit the potential of this idea. With SIMD instructions getting more attention from chip designers, this thesis also presents the necessary modifications for a general compiler/run-time infrastructure to transform the dynamic program state of SIMD regions at run-time from one ISA format to another for cross-ISA migration and execution. Lastly, this thesis presents a processor-preference-aware scheduling policy that makes dynamic cross-ISA migration decisions that improve overall system throughput compared to homogeneous-ISA systems. This thesis prototypes a heterogeneous-ISA system using an Intel Xeon Gold 5118 x86-64 server and a Cavium ThunderX ARMv8 server and evaluates the effectiveness of our infrastructure and scheduling policy. Our results reveal that heterogeneous-ISA systems that are processor-preference-aware and with cross-ISA execution migration capability can yield throughput gains up to 36\% compared to traditional homogeneous ISA systems. / Master of Science / The author of this thesis has a family full of non-engineers. To persuade family members that the work of this thesis is meaningful, aka the author is not procrastinating in school, the author decided to draw an analogy between processors and cars. Suppose in an alternative universe, cars (systems) can be powered by engines (processors) that uses two different fuel-sources (ISAs): gasoline or electric (single-ISA) processors but not both (heterogeneous-ISA). Car manufacturers (chip designers) can build engines with different design choices (processors with varying design options): engines combined with turbochargers for gasoline-powered cars, high-performance batteries combined with energy-efficient batteries for electric-powered cars (added extended instruction sets, CPU designs that target vastly different use cases, etc.). However, each design choice is limited to improving performance for a specific type of fuel-source based engine. For example, having battery alternatives has no performance impact on gasoline-powered engines. As time passes by, car manufacturers have exhausted options to make a drastic improvement to their existing engine designs (limited performance gains in recent chips). To tackle this problem, in this thesis, the author first examined the usage of cars: driving on the road (running applications). The author's study found that no single engine is suitable for all routes (no single processor is good for all workloads), and cars powered by different fuel-source based engines showed a significant diversity in performance (application performance varies drastically between systems with processors built on different ISAs). Gasoline-powered cars perform well on high-speed roads, whereas electric-powered cars perform well on low-speed roads. Unfortunately, in real life, a person's commute (a workload of applications) consists of a mixture of high-speed roads and low-speed roads, and one cannot know the exact percentage of each kind of path they travel (exact application composition in a workload) beforehand. Therefore it is challenging for a person to make the correct car selection for the incoming commute (choose the right system for a workload). This thesis tries to solve this commuting problem by building a car that has multiple engines fitted to suit different road needs (systems with processors that have vastly different use cases). This thesis looks at a particular dimension of combining various fuel-powered engines in the same car (a system with heterogeneous-ISA processors). The author believes that adding diversity in fuel-powered engine selections provide an exciting dimension in car design choices (adding ISA-heterogeneity in processors provide a unique dimension in system design). Thus, this thesis focuses on estimating a theoretical multi fuel-powered car's performance by combining two different fuel-powered cars into a single mega-car using some framework (Popcorn Linux). This framework allows this mega-car to be driven by a combined fuel source with fuel intake freely transfer between fuel-sources (cross-ISA migration and execution) based on road conditions (application encountered). Based on the evaluation of this new prototype, the author finds that in a real-life scenario (workload with mixed application combination), cars with multiple fuel-source based engines have better performance than two single fuel-source based cars (systems with heterogeneous-ISAs processors perform better than systems with homogeneous-ISAs processors). The author hopes that this study can help build the foundation for the development of hybrid cars (system with heterogeneous-ISAs in the same processor) in the future as well as the consideration of modifying existing car into a mega-car with multiple engines suited for different road needs for improved commute performance for now. Ultimately, this thesis is not about cars. The author hopes that by explaining the research done in this paper through cars, general audiences can understand what this work is trying to investigate and what solution they have provided. In this work, we investigate the potential of a system with heterogeneous-ISA processors. This thesis prototypes one such system and finds that heterogeneous-ISA systems have performance benefits than traditional homogeneous-ISA systems over a series of experiment evaluations.

In this thesis we present new results for the makespan and the flowtime in a flow shop without intermediate storage between machines. We consider m machines and n jobs with random processing times. Since there is no intermediate storage between machines, a job which has finished processing at one machine may have to stay at that machine until the next machine is free. This phenomenon is known as blocking. Our goal is to select the optimal schedule; in our case, the schedule which in some sense minimizes the makespan or the flowtime. Makespan is the total time required to process a set of jobs and flowtime is sum of all the times at which jobs are completed. Our results require various stochastic orderings on the processing time distributions. Some of these orderings minimize the expected flowtime or expected makespan, and some stochastically minimize the makespan. The stochastic minimization results are much stronger. The optimum sequence in these cases not only minimize the expected makespan, but also maximize the probability of completing a set of jobs by time t for any t. Our last result resolves the conjecture of Pinedo (1982a) that in a stochastic flow shop with m machines, n-2 deterministic jobs with unit processing time, and two stochastic jobs each with mean one, the sequence which minimizes the expected makespan has one of the stochastic jobs first and the other last. We prove that Pinedo's conjecture is almost true. We prove that either the sequence suggested by Pinedo or a sequence in which the stochastic jobs are adjacent at one end of the sequence minimizes the expected makespan. Our result does not require the stochastic jobs to have an expected value of one. Furthermore, we show that our result cannot be improved in the sense that in some cases one sequence is strictly optimal and in other cases the other is strictly optimal. / Master of Science

All passengers travel at the hour most convenient to them. But it is not always possible to find a flight at the right time to fly them to their destination. In the case where service in any one time period is insufficient to meet air travel demanded, it may be expected that some unfilled demand passengers will either delay their flight or will advance it, thus adding to the effective demand of the adjoining time periods.The obvious alternate means of travel is a rental car. It takes a lot more time than flight, but it is readily available at any given time. This brings us to think of an airline system that will work in a similar fashion; A system that can be named an "Air Taxi System." This would mean a virtual highway in air space leading to a vast network. The network would be served by small aircraft flying from one city to another loading and unloading passengers. Such a large network having dynamic demand will have many issues to resolve before successfully launching a Small Aircraft Transportation System. One of the most important problems to solve is scheduling of aircraft for such a stochastic demand flow. The objective of the research is to study a given set of airports with dynamic demand and known aircraft type. The major task will be to analyze the flow of passengers between each origin-destination pair and then schedule flights. The research will be to develop a schedule for a fixed set of airports with dynamic demand and known type of aircraft. The main objective is to maximize demand satisfaction. The study will also analyze the number of aircraft required for a given set of airports and find a method to schedule them. / Master of Science

Interference in ad hoc wireless networks causes the performance of traditional networking protocols to suffer. However, some user applications in ad hoc networks demand high throughput and low end-user delay. In the literature, the backpressure policy, i.e. queue backlog differential-based joint routing and scheduling, is known to be throughput-optimal with robust support for traffic load fluctuations \cite{Tssailus92}. Unfortunately, many backpressure-based algorithms cannot be implemented due to high end-user delay, inaccurate assumptions for interference, and high control overhead in distributed scenarios. We develop new backpressure based approaches to address these issues. We first propose a heuristic packet forwarding scheme that solves the issue of high end-user delay and still provides near-optimal throughput. Next we develop a novel interference model that provides simple yet accurate interference relationships among users. Such a model is helpful in designing a simple backpressure scheduling algorithm that does not violate realistic interference constraints. Finally we develop distributed backpressure algorithms based on our proposed ideas. Our distributed algorithms provide throughput performance close to the optimal and have low control overhead and simple implementation. / Master of Science

This thesis studies the problem of experimentally evaluating the scaling behaviors of existing multicore real-time task scheduling algorithms on large-scale multicore platforms. As chip manufacturers rapidly increase the core count of processors, it becomes imperative that multicore real-time scheduling algorithms keep pace. Thus, it must be determined if existing algorithms can scale to these new high core-count platforms. Significant research exists on the theoretical performance of multicore real-time scheduling algorithms, but the vast majority of this research ignores the effects of scalability. It has been demonstrated that multicore real-time scheduling algorithms are feasible for small core-count systems (e.g. 8-core or less), but thus far the majority of the algorithmic research has never been tested on high core-count systems (e.g. 48-core or more). We present an experimental analysis of the scalability of 16 multicore real-time scheduling algorithms. These algorithms include global, clustered, and partitioned algorithms. We cover a broad range of algorithms, including deadline-based and utility accrual scheduling algorithms. These algorithms are compared under metrics including schedulability, tardiness, deadline satisfaction ratio, and utility accrual ratio. We consider multicore platforms ranging from 8 to 48 cores. The algorithms are implemented in a real-time Linux kernel we create called ChronOS. ChronOS is based on the Linux kernel's PREEMPT RT patch, which provides the underlying operating system kernel with real-time capabilities such as full kernel preemptibility and priority inheritance for kernel locking primitives. ChronOS extends these capabilities with a flexible, scalable real-time scheduling framework. Our study shows that it is possible to implement global fixed and dynamic priority and simple global utility accrual real-time scheduling algorithms which will scale to large-scale multicore platforms. Interestingly, and in contrast to the conclusion of prior research, our results reveal that some global scheduling algorithms (e.g. G-NP-EDF) is actually scalable on large core counts (e.g. 48). In our implementation, scalability is restricted by lock contention over the global schedule and the cost of inter-processor communication, rather than the global task queue implementation. We also demonstrate that certain classes of utility accrual algorithms such as the GUA class are inherently not scalable. We show that algorithms implemented with scalability as a first-order implementation goal are able to provide real-time guarantees on our 48-core platform. / Master of Science

Yes / Maintenance planning for busy railway systems is challenging because there is growing pressure on increasing operation time, which reduces the infrastructure-accessible time for maintenance. This paper proposes an optimization model that is aimed at finding the best maintenance schedule for multiple components in a railway track to minimize the total cost in the planning horizon. One distinct and practical feature of the model is that the track accessible time for maintenance is limited. We formulate all relevant costs in the component's life cycle, including maintenance cost, fixed track-closure (possession) cost, social-economic cost related to the effects of maintenance time on the train operation, and service-life shortening cost due to the shifting of activities. Generally, it is beneficial to cluster and maintain several components in a single possession because this helps reduce the cost by occupying the track only once. However, the decision must depend on the available possession time. A sensitivity analysis is performed to highlight the effects of available possession time on the number of required possessions as well as the total cost incurred.