The hardware organization and software structure of a new database system are presented. This system, the relational replicated database system (RRDS), is based on a set of replicated processors operating on a partitioned database. Performance improvements and capacity growth can be obtained by adding more processors to the configuration. Based on designing goals a set of hardware and software design questions were developed. The system then evolved according to a five-phase process, based on simulation and analysis, which addressed and resolved the design questions. Strategies and algorithms were developed for data access, data placement, and directory management for the hardware organization. A predictive performance analysis was conducted to determine the extent to which original design goals were satisfied. The predictive performance results, along with an analytical comparison with three other relational multi-backend systems, provided information about the strengths and weaknesses of our design as well as a basis for future research.

A reconfiguration is developed for 2-dimensional mesh architectures and applied to a fault T tolerant cellular architecture. The reconfiguration is accomplished by adding communications paths to each cell which can be enabled by means of transistor switches controlled by decoding the contents of a register containing the relative position of faulty cells. This enables faulty cells to be bypassed and operations of cells in the same row east of the faulty cell to be shifted one cell to the east and a spare cell included in the active pattern. A modified s-value algorithm is also developed which enables a cell to determine the size of a square pattern that may be centered on that cell. / 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

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

International Telemetering Conference Proceedings / October 25-28, 1993 / Riviera Hotel and Convention Center, Las Vegas, Nevada / NASA's ground telemetry data systems developed by the Microelectronics Systems Branch at the Goddard Space Flight Center, use a generic but expandable architecture known as the "Functional Components Approach." This approach is based on the industry standard VMEbus and makes use of multiple commercial and custom VLSI hardware based cards to provide standard off-the-shelf telemetry processing functions (e.g., frame synchronization, packet processing, etc.) for many telemetry data handling applications. To maintain maximum flexibility and performance of these systems, a special real-time system environment has been developed, the Modular Environment for Data Systems (MEDS). Currently, MEDS comprises over 300,000 lines of tested and operational code based on a non-UNIX real-time commercial operating system. To provide for increased functionality and adherence to industry standards, this software is being transformed to run under a UNIX-compatible real-time environment. This effort must allow for existing systems and interfaces and provide exact duplicates of the system functions now used in the current real-time environment. Various techniques will be used to provide a relatively quick transition to this new real-time operating system environment. Additionally, all standard MEDS card to card and system to system interfaces will be preserved, providing for a smooth transition and allowing for telemetry processing cards that have not yet been converted to reside side-by-side with cards that have been converted. This paper describes this conversion effort.

In this thesis, a discrete Markov chain model for analyzing memory interference in multiprocessors, is presented.

by Wong Tin-Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 70-73). / Abstract --- p.ii / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Scheduling Problems --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Sized Multiprocessor Task Scheduling --- p.5 / Chapter 1.2.2 --- Fixed Multiprocessor Task Scheduling --- p.6 / Chapter 1.2.3 --- Set Multiprocessor Task Scheduling --- p.8 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Overview --- p.11 / Chapter 2.1 --- Machine Environment --- p.11 / Chapter 2.2 --- The Jobs and Their Requirements --- p.12 / Chapter 2.3 --- Assumptions --- p.13 / Chapter 2.4 --- Constraints --- p.14 / Chapter 2.5 --- Objective --- p.15 / Chapter 2.6 --- An Illustrative Example --- p.17 / Chapter 2.7 --- NP-Hardness --- p.20 / Chapter 3 --- Methodology --- p.22 / Chapter 3.1 --- Dynamic Programming --- p.22 / Chapter 3.1.1 --- Problem Analysis --- p.24 / Chapter 3.2 --- Key Idea to solve the problem --- p.27 / Chapter 3.3 --- Algorithm --- p.28 / Chapter 3.3.1 --- Phase 1 --- p.28 / Chapter 3.3.2 --- Phase 2 --- p.37 / Chapter 4 --- Extensions --- p.46 / Chapter 4.1 --- "Polynomially Solvable Cases P2 --- p.46 / Chapter 4.1.1 --- Dynamic Programming --- p.47 / Chapter 4.2 --- "Set Problem P2/setj,prmp/TmaX" --- p.55 / Chapter 4.2.1 --- Processing times for set jobs --- p.56 / Chapter 4.2.2 --- Algorithm --- p.58 / Chapter 4.3 --- k´ؤMachine Problem with only two types of jobs --- p.64 / Chapter 5 --- Conclusion and Future Work --- p.67 / Chapter 5.1 --- Conclusion --- p.67 / Chapter 5.2 --- Some Future Work --- p.68 / Bibliography --- p.70

Thesis. 1976. Sc.D.--Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics. / Microfiche copy available in Archives and Barker. / Vita. / Bibliography: p. 175-181. / by Jaynarayan H. Lala. / Sc.D.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Includes bibliographical references. / by Charles Zukowski. / M.S.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Vita. / Bibliography: p. 204-221. / by Evan Michael Tick. / M.S.