Thomas M. Conte, Wen‐mei Hwu · NASA Technical Reports Server (NASA) · 1990
Modern memory systems are composed of levels of cache memories, a virtual memory system, and a backing store. Varying more than a few design parameters and measuring the performance of such systems has traditionally be constrained by the high cost of simulation. Models of cache performance recently introduced reduce the cost simulation but at the expense of accuracy of performance prediction. Stack-based methods predict performance accurately using one pass over the trace for all cache sizes, but these techniques have been limited to fully-associative organizations. This paper presents a stack-based method of evaluating the performance of cache memories using a recurrence/conflict model for the miss ratio. Unlike previous work, the performance of realistic cache designs, such as direct-mapped caches, are predicted by the method. The method also includes a new approach to the problem of the effects of multiprogramming. This new technique separates the characteristics of the individual program from that of the workload. The recurrence/conflict method is shown to be practical, general, and powerful by comparing its performance to that of a popular traditional cache simulator. The authors expect that the availability of such a tool will have a large impact on future architectural studies of memory systems.
Cited by 4Open access
Verna Elizabeth Knapp · 1985
Virtually addressed caches offer advantages of improved performance and simplicity of design over real addressed caches. They have not been generally used because their implementation presents some difficulties.
A technique was devised to allow the use of virtually addressed cache by multiple processes sharing global memory without cache coherency problems. When the question of how to best combine I/O subsystems with virtually addressed cache using that technique was raised, several more problems were discovered. These included the MMU coherency problem and the question of whether the MMU should be associated with the processor or with main memory. The advantages and disadvantages of a large number of locations of processors, caches, buses, MMUs, and main memories were discussed. Associating the MMU(s) with main memory rather than with the cache or the processor has a number of advantages. These advantages include a solution to the MMU coherency problem, better performance, virtual addresses for I/O which yields uniform addresses for all references, and simplicity of design.
An implementation of the ideas developed in this dissertation is proposed. The system to be implemented is a multiprocessor workstation using shared global memory for multiprocessing and multiprogramming tasks. Operating system and system software issues are discussed.
In the uniprocessor case, the expected performance gain due to using virtually addressed cache is significant, primarily because it allows non-paged address translation units to be used. Comparisons were made between real address cache architectures and virtual address cache architectures.
In the multiprocessor case, there is also a gain in performance for all of the reasons which apply with uniprocessors, plus a reduction in bus contention. There is also a considerable reduction in the complexity of the system. All of the processors, including I/O processors, can be treated in a uniform fashion with respect to the protocol for memory access. Each processor deals with virtual addresses only. Translation of virtual addresses is defered until a main memory reference occurs. The main memory translates the virual address to a real address, maintains cache coherency between the various processors, detects page faults, and transfers data.
Cited by 14
Tokumi Yokohira, Hideo Miyahara · Systems and Computers in Japan · 1989
Abstract This paper presents a state analysis of multiprogramming, using the concept of cusp catastrophe in the theory of catastrophe. Based on the result, the catastrophic phenomena in the multiprogramming system are analyzed. It is shown first that the multiprogramming system exhibits two stable states, i.e., monostable and bistable states, for the change of job generation rate and the change of the maximum multiprogramming level. Then it is shown that a rapid change (catastrophe) of the performance of the multiprogramming system, such as the mean number of jobs in the system, throughput and response time, may occur with the change of the stable state of the system. Furthermore, it is shown that for any given job generation rate, there exists a maximum multiprogramming level which maximizes the throughput and minimizes the response time.
Cited by 0
Daniel A. Menasc&eacute, Virgilio A. F. Almeida, Departamento De et al. · 2016
Supercomputers run multiprogrammed time-sharing operating systems, so their facilities can be shared by many local and remote users. Therefore, it is important to be able to assess the performance of supercomputers in multiprogrammed environments. Analytic models based on Queueing Networks (QNs) and Stochastic Petri Nets (SPNs) are used in this paper with two purposes: to evaluate the performance of supercomputers in multi-programmed environments, and to compare, perfor-mance-wise, conventional supercomputer architectures with a novel architecture proposed here. It is shown, with the aid of the analytic models, that the proposed architecture is preferable performance-wise over the existing conventional supercomputer architectures. A three-level workload characterization model for super-computers is presented. Input data for the numerical ex-amples discussed here are extracted from the well-known Los Alamos benchmark, and the results are vali-dated by simulation.
Cited by 0
Jayadev Misra · Unisa Institutional Repository (University of South Africa) · 1998
This paper presents a short introduction to the UNITY logic, a fragment of linear temporal logic. The logic was designed to specify safety and progress properties of reactive systems. A version of the UNITY logic appears in {1}. There have been several changes in this logic since then; a full account is available at \nhttp:// www.cs.utexas.edu/users/psp/newunity.html, and the essential ideas have appeared in {5, 4}.
Cited by 0Open access
Mohammad Malkawi, J.H. Patel · ACM SIGARCH Computer Architecture News · 1986
This paper presents empirical results on the performance of CD, a compiler directed memory management policy, and the Working Set policy in a multiprogramming system. A description of the multiprogramming model used in the experiments is also presented. The results show that CD outperforms WS in terms of fault rate, space time cost, and throughput characteristics. Moreover, WS is shown to lack controllability. Two anomaly types are reported in this paper, both of which are exhibited by WS but not by CD.
Cited by 8Open access
Dijkstra, EW · TU/e Research Portal (Eindhoven University of Technology) · 1983
A multiprogramming system is described in which all activities are divided over a number of sequential processes. These sequential processes are placed at various hierarchical levels, in each of which one or more independent abstractions have been implemented. The hierarchical structure proved to be vital for the verification of the logical soundness of the design and the correctness of its implementation.
Cited by 0
K. J. Burkhardt · Behavior Research Methods & Instrumentation · 1976
Cited by 8Open access
Alexandre Brandwajn, William M. McCormack · ACM SIGMETRICS Performance Evaluation Review · 1984
Queueing network models of multiprogramming systems with memory constraints and multiple classes of jobs are important in representing large commercial computer systems. Typically, an exact analytical solution of such models is unavailable, and, given the size of their state space, the solution of models of this type is approached through simulation and/or approximation techniques. Recently, a computationally efficient iterative technique has been proposed by Brandwajn, Lazowska and Zahorjan for models of systems in which each job is subject to a separate memory constraint, i.e., has its own memory domain. In some important applications, it is not unusual, however, to have several jobs of different classes share a single memory “domain” (e.g., IBM's Information Management System). We present a simple approximate solution to the shared domain problem. The approach is inspired by the recently proposed technique which is complemented by a few approximations to preserve the conceptual simplicity and computational efficiency of this technique. The accuracy of the results is generally in fair agreement with simulation.
Cited by 7Open access
T. S. Heines Professor · The Journal of Data Education · 1977
Cited by 0
Guy Latouche · Journal of the ACM · 1981
A computer system consisting of several identical CPUs and several identical I/O units Is described The system works under light load conditions in a multlprogrammmg mode Programs belong either to an incoming queue, which may be empty, or to an inner loop if they are allowed access to the resources of the system The maximum number of programs in the inner loop is finite Under Markovlan assumptions it is shown that the steady-state probablhty distribution is of matrixgeometric form. The stablhty condition is exphcltly given For stable systems It Is shown how the stationary probability distribution, the virtual waiting time in the incoming queue, and other features of interest may be computed
Cited by 17Open access
S. Abramsky, R. Sykes · Oxford University Research Archive (ORA) (University of Oxford) · 1985
Cited by 1
Ryo Wakizaka, S. Nishio, Daisuke Sakuma et al. · arXiv (Cornell University) · 2025
Fault-tolerant quantum computers are expected to be offered as cloud services due to their significant resource and infrastructure requirements. Quantum multiprogramming, which runs multiple quantum jobs in parallel, is a promising approach to maximize the utilization of such systems. A key challenge in this setting is the need for an online scheduler capable of handling jobs submitted dynamically while other programs are already running. In this study, we formulate the online job scheduling problem for fault-tolerant quantum computing systems based on lattice surgery and propose an efficient scheduler to address it. To meet the responsiveness required in an online environment, our scheduler approximates lattice surgery programs, originally represented as polycubes, by using simpler cuboid representations. This approximation enables efficient scheduling while improving overall throughput. In addition, we incorporate a defragmentation mechanism into the scheduling process, demonstrating that it can further enhance the utilization of quantum processing unit.
Cited by 0Open access
Lawrence W. Dowdy, Manvinder S. Chopra · 1985
A computer system's workload is represented by its multiprogramming level, which is defined as the number of tasks (jobs, customers) which actively compete for resources within the system. In a product-form queuing network model of the system, the workload is modeled by assuming that the multiprogramming level is either fixed (i.e., closed model) or that the multiprogramming level depends upon an outside arrival process (i.e., open model). However, in many actual systems, closed and open models are both inappropriate since the multiprogramming level is neither fixed nor governed by an outside arrival process.
Cited by 1Open access
N. S. Losapio, William G. Bulgren · 1972
CPU scheduling or dispatching in computer systems is surveyed. In order to study and evaluate a dispatching algorithm, a simulation model of a dispatching algorithm for multiprogramming operating system has been devised and programmed. Essential elements which have been included are the job environment, the computer system environment, and the user environment. The model is patterned basically after GECOS III, on the H-600 line computer. Some results of the investigation are presented, such as lengths of various queues, I/O time, processor utilization, expected time in various queues, throughput and flexibility.
Cited by 0Open access
Mauricio Hanzich, Francesc Giné, Porfídio Hernández et al. · Lecture notes in computer science · 2004
Cited by 12
DeGroot, Doug, Agarwal, Anant · CERN Bulletin · 1989
Cited by 0
Henry R. Bauer · 1976
A multiprogramming operating system for the TI980A permits replacement of system primitives by a programmer familiar with the system's design and data structures. This paper describes the hardware features available; the method of use of the replaceable parts facility; typical student assignments for an operating systems course (e.g. ACM Curriculum '68 I4); and student reaction to the projects.
Cited by 1
Qing Xian Xu, Pen-Chung Yew · 1984
Cited by 3
Hoon-Liong Ong · MacSphere (McMaster University) · 1978
Title: The Design and Implementation of a Multiprogramming Operating System, Author: Hoon-Liong Ong, Location: Thode
Cited by 0Open access