Market-based Proportional Resource Sharing for Clusters
Published 7 February 2000
Brent Chun, David Culler
Citations159
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An abstract architecture for market-based cluster resource management based on the idea of proportional resource sharing of basic computing resources is described and a 32-node (64 processors) prototype system that provides a market for time-shared CPU usage for sequential and parallel programs is implemented.
Abstract
Enabling technologies in high speed communication and global process scheduling have pushed clusters of computers into the mainstream as general-purpose high-performance computing systems. More generality, however, implies more sharing and this raises new questions in the area of cluster resource management. In particular, in systems where the aggregate demand for computing resources can exceed the aggregate supply, how to allocate resources amongst competing applications is an important problem. Traditional solutions to this problem have focused mainly on global optimization with respect to system-centric performance metrics, metrics which ignore higher level user intent. In this paper, we propose an alternative market-based approach based on the notion of a computational economy which optimizes for user value. Starting with fundamental requirements, we describe an abstract architecture for market-based cluster resource management based on the idea of proportional resource s...
Keywords
Computer Science
Elsevier eBooksScheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
3,241 Citations2002C. L. Liu, J. W. Layland
Modern Operating Systems
1,923 Citations1992Andrew S. Tanenbaum
Modern Operating Systems gives a solid conceptual overview of operating system design, including detailed case studies of Unix/Linux and Windows 2000, and makes frequent references to the Frederick Brooks classic The Mythical Man month for wisdom on managing large, complex software development projects.
IEEE MicroMyrinet: a gigabit-per-second local area network
1,702 Citations1995N.J. Boden, D. Cohen +5 more
The Myrinet local area network employs the same technology used for packet communication and switching within massively parallel processors, but with the highest performance per unit cost of any current LAN.
Operating System Concepts
1,596 Citations1983Abraham Silberschatz, Peter Galvin +1 more
Princeton University Press eBooksGame Theory for Applied Economists
1,475 Citations1992Robert Gibbons
IEEE MicroA case for NOW (Networks of Workstations)
797 Citations1995Thomas E. Anderson, David Culler +1 more
This paper identifies three opportunities for NOWs that will benefit end- users: dramatically improving virtual memory and file system performance by using the aggregate DRAM of a NOW as a giant cache for disk, achieving cheap, highly available, and scalable file storage by using redundant arrays of workstation disks, and multiple CPUs for parallel computing.
IEEE Transactions on Software EngineeringSpawn: a distributed computational economy
649 Citations1992Carl A. Waldspurger, Tad Hogg +3 more
Using concurrent Monte Carlo simulations as prototypical applications, the authors explore issues of fairness in resource distribution, currency as a form of priority, price equilibria, the dynamics of transients, and scaling to large systems.
Operating Systems Design and ImplementationLottery scheduling: flexible proportional-share resource management
645 Citations1994Carl A. Waldspurger, William E. Weihl
A prototype lottery scheduler for the Mach 3.0 microkernel is implemented, and it is found that it provides flexible and responsive control over the relative execution rates of a wide range of applications.
The Design and implementation of the 4.3BSD UNIX operating system
616 Citations1991Marshall Kirk McKusick, Keith Bostic +2 more
Virtual clock: a new traffic control algorithm for packet switching networks
616 Citations1990Li Zhang
A new algorithm is described, VirtualClock, for data traffic control in high-speed networks that maintains the statistical multiplexing flexibility of pocket switching while ensuring each data flow its reserved average throughput rate at the same time.
ACM Transactions on Computer SystemsVirtualClock
510 Citations1991Lixia Zhang
A new algorithm is described, VirtualClock, for data traffic control in high-speed networks that maintains the statistical multiplexing flexibility of pocket switching while ensuring each data flow its reserved average throughput rate at the same time.
Software Practice and ExperienceUtopia: A load sharing facility for large, heterogeneous distributed computer systems
318 Citations1993Songnian Zhou, Xiaohu Zheng +2 more
The design and implementation issues in Utopia, a load sharing facility specifically built for large and heterogeneous systems, are discussed, which has no restriction on the types of tasks that can be remotely executed, involves few application changes and no operating system change, and incurs low overhead.
Communications of the ACMA fair share scheduler
254 Citations1988Judy Kay, P. Lauder
A fair Share scheduler allocates resources so that users get their fair machine share over a long period because central-processing-units have traditionally allocated resources fairly among processes.
DSpace@MIT (Massachusetts Institute of Technology)Lottery and stride scheduling: flexible proportional-share resource management
241 Citations1995Carl A. Waldspurger, William E. Weihl
This thesis presents flexible abstractions for specifying resource management policies, together with efficient mechanisms for implementing those abstractions, including both randomized and deterministic algorithms that provide proportional-share control over resource consumption rates.
DSpace@MIT (Massachusetts Institute of Technology)Stride Scheduling: Deterministic Proportional- Share Resource Management
210 Citations1995Carl A. Waldspurger
This paper introduces new techniques to support dynamic changes and higher-level resource management abstractions, and introduces a novel hierarchical stride scheduling al-gorithm that achieves better throughput accuracy and lower response time variability than prior schemes.
Microeconomic algorithms for load balancing in distributed computer systems
182 Citations2003Donald Ferguson, Y. Yemini +1 more
A novel approach to allocating and sharing communication and computational resources in a distributed system is described, which uses algorithms that are competitive rather than cooperative and which achieves substantial performance benefits.
An economic paradigm for query processing and data migration in Mariposa
179 Citations2002Michael Stonebraker, Robert Devine +5 more
This work presents the protocols which underlie the Mariposa economy, a database system under construction at Berkeley which combines the best features of traditional distributed database systems, object-oriented DBMSs, tertiary memory file systems and distributed file systems.
Beowulf: harnessing the power of parallelism in a pile-of-PCs
158 Citations1997D. Ridge, Daniel Becker +2 more
The technologies and methodologies employed to achieve the increased performance of PCs are described in the framework of hardware and software systems as well as the results from benchmarking experiments.
The POPCORN market—an online market for computational resources
154 Citations1998Ori Regev, Noam Nisan
The design emphasizes minimal communication requirements and minimal strategic considerations on the part of both buyers and sellers, and implemented several market mechanisms of the single-sided and double-sided auction types to support the use of these mechanisms in the Internet environment.
An Implementation and Analysis of the Virtual Interface Architecture
117 Citations1998Philip Buonadonna, Andrew Geweke +1 more
Scheduling with implicit information in distributed systems
108 Citations1998Andrea C. Arpaci-Dusseau, David Culler +1 more
This paper more rigorously analyze the two-phase spin-block algorithm and shows that spin time should be increased when a process is receiving messages, and shows how implicit coscheduling behaves under different job layouts and scaling.
eCommons (Cornell University)Incorporating Memory Management into User-Level Network Interfaces
107 Citations1997Matt Welsh, Anindya Basu +1 more
This paper presents an extension to the U-Net user-level network architecture (U-Net/MM) allowing messages to be transferred directly to and from any part of an application''s address space by integrating a translation look-aside buffer into the network interface and coordinating its operation with the operating system''s virtual memory subsystem.
Software Practice and ExperienceGLUix: a global layer unix for a network of workstations
94 Citations1998Douglas P. Ghormley, David Petrou +3 more
Performance and scalability measurements of the GLUnix system indicate that a centralized, user‐level design can scale gracefully to significant cluster sizes, incurring only an additional 220 μs of overhead per node for remote execution.
Rate Monotonic Analysis for Real-Time Systems
93 Citations1991Lui Sha, Mark Klein +1 more
As a mathematical discipline travels far from its empirical source, or still more, if it is a second and third generation only indirectly inspired by the ideas coming from ‘reality,’ it is beset with very grave dangers.
IEEE MicroVirtual network transport protocols for Myrinet
83 Citations1998Brent Chun, Alan Mainwaring +1 more
The AM-II API extends traditional active messages with support for client-server computing and facilitates the construction of parallel clients and distributed servers, and a virtual network segment driver enables a large number of arbitrary sequential and parallel applications to access network interface resources directly in a concurrent but fully protected manner.
Design challenges of virtual networks
22 Citations1999Alan Mainwaring, David Culler
The design of a large-scale virtual network system is presented and the integration of communication programming interface, system resource management, and network interface operation is examined, showing full hardware performance is delivered to dedicated applications and time-shared workloads.
Charge-Based Proportional Scheduling
15 Citations1996U. Maheshwari
A new scheme that controls execution rates over much smaller intervals and provides better service guarantees is presented, which is based on charging threads for CPU usage and occasionally skipping some threads to keep the usage close to the intended proportion.
Software Practice and ExperienceScheduling for a share of the machine
14 Citations1975John Larmouth
The mechanism used to schedule jobs and control machine use on the IBM 370/165 at Cambridge University, England is described, believed to be an original one, having a number of advantages over more conventional scheduling and control algorithms.