Granular computing is a new style of computing where applications are composed of large numbers (thousands to millions) of very short-lived (10-100μs) tasks. Today's systems and infrastructure were designed to support millisecond-scale operations and are inadequate to meet the demands of granular computing. In this position paper we discuss the challenges of supporting granular applications, such as handling extreme bursts of activity, and we present a few initial ideas about the infrastructure required to enable granular computing, such as new mechanisms for communication and persistence.

Homa is a new transport protocol for datacenter networks. It provides exceptionally low latency, especially for workloads with a high volume of very short messages, and it also supports large messages and high network utilization. Homa uses in-network priority queues to ensure low latency for short messages; priority allocation is managed dynamically by each receiver and integrated with a receiver-driven flow control mechanism. Homa also uses controlled overcommitment of receiver downlinks to ensure efficient bandwidth utilization at high load. Our implementation of Homa delivers 99th percentile round-trip times less than 15 μs for short messages on a 10 Gbps network running at 80% load. These latencies are almost 100x lower than the best published measurements of an implementation. In simulations, Homa's latency is roughly equal to pFabric and significantly better than pHost, PIAS, and NDP for almost all message sizes and workloads. Homa can also sustain higher network loads than pFabric, pHost, or PIAS.

Linearizability is the strongest form of consistency for concurrent systems, but most large-scale storage systems settle for weaker forms of consistency. RIFL provides a general-purpose mechanism for converting at-least-once RPC semantics to exactly-once semantics, thereby making it easy to turn non-linearizable operations into linearizable ones. RIFL is designed for large-scale systems and is lightweight enough to be used in low-latency environments. RIFL handles data migration by associating linearizability metadata with objects in the underlying store and migrating metadata with the corresponding objects. It uses a lease mechanism to implement garbage collection for metadata. We have implemented RIFL in the RAMCloud storage system and used it to make basic operations such as writes and atomic increments linearizable; RIFL adds only 530 ns to the 13.5 μs base latency for durable writes. We also used RIFL to construct a new multi-object transaction mechanism in RAMCloud; RIFL's facilities significantly simplified the transaction implementation. The transaction mechanism can commit simple distributed transactions in about 20 μs and it outperforms the H-Store main-memory database system for the TPC-C benchmark.

RAMCloud is a storage system that provides low-latency access to large-scale datasets. To achieve low latency, RAMCloud stores all data in DRAM at all times. To support large capacities (1PB or more), it aggregates the memories of thousands of servers into a single coherent key-value store. RAMCloud ensures the durability of DRAM-based data by keeping backup copies on secondary storage. It uses a uniform log-structured mechanism to manage both DRAM and secondary storage, which results in high performance and efficient memory usage. RAMCloud uses a polling-based approach to communication, bypassing the kernel to communicate directly with NICs; with this approach, client applications can read small objects from any RAMCloud storage server in less than 5μs, durable writes of small objects take about 13.5μs. RAMCloud does not keep multiple copies of data online; instead, it provides high availability by recovering from crashes very quickly (1 to 2 seconds). RAMCloud’s crash recovery mechanism harnesses the resources of the entire cluster working concurrently so that recovery performance scales with cluster size.

RAMCloud is a DRAM-based storage system that provides inexpensive durability and availability by recovering quickly after crashes, rather than storing replicas in DRAM. RAMCloud scatters backup data across hundreds or thousands of disks, and it harnesses hundreds of servers in parallel to reconstruct lost data. The system uses a log-structured approach for all its data, in DRAM as well as on disk: this provides high performance both during normal operation and during recovery. RAMCloud employs randomized techniques to manage the system in a scalable and decentralized fashion. In a 60-node cluster, RAMCloud recovers 35 GB of data from a failed server in 1.6 seconds. Our measurements suggest that the approach will scale to recover larger memory sizes (64 GB or more) in less time with larger clusters.

Zebra is a network file system that increases throughput by striping the file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an approach similar to a log-structured file system. This provides high performance for writes of small files as well as for reads and writes of large files. Zebra also writes parity information in each stripe in the style of RAID disk arrays; this increases storage costs slightly, but allows the system to continue operation while a single storage server is unavailable. A prototype implementation of Zebra, built in the Sprite operating system, provides 4–5 times the throughput of the standard Sprite file system or NFS for large files and a 15–300% improvement for writing small files.

Zebra is a network file system that increases throughput by striping file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an approach similar to a log-structured file system. This provides high performance for writes of small files as well as for reads and writes of large files. Zebra also writes parity information in each stripe in the style of RAID disk arrays; this increases storage costs slightly but allows the system to continue operation even while a single storage server is unavailable. A prototype implementation of Zebra, built in the Sprite operating system, provides 4--5 times the throughput of the standard Sprite file system or NFS for large files and a 20%-3x improvement for writing small files.

Given the decreasing cost of non-volatile RAM (NVRAM), by the late 1990’s it will be feasible for most workstations to include a megabyte or more of NVRAM, enabling the design of higher-performance, more reliable systems. We present the trace-driven simulation and analysis of two uses of NVRAM to improve I/O performance in distributed file systems: non-volatile file caches on client workstations to reduce write traffic to file servers, and write buffers for write-optimized file systems to reduce server disk accesses. Our results show that a megabyte of NVRAM on diskless clients reduces the amount of file data written to the server by 40 to 50%. Increasing the amount of NVRAM shows rapidly diminishing returns, and the particular NVRAM block replacement policy makes little difference to write traffic. Closely integrating the NVRAM with the volatile cache provides the best total traffic reduction. At today’s prices, volatile memory provides a better performance improvement per dollar than NVRAM for client caching, but as volatile cache sizes increase and NVRAM becomes cheaper, NVRAM will become cost effective. On the server side, providing a one-half megabyte write-buffer per file system reduces disk accesses by about 20 % on most of the measured logstructured file systems (LFS), and by 90 % on one heavilyused file system that includes transaction-processing workloads. 1.

This paper presents a new technique for disk storage management called a log-structured file system . A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, we divide the log into segments and use a segment cleaner to compress the live information from heavily fragmented segments. We present a series of simulations that demonstrate the efficiency of a simple cleaning policy based on cost and benefit. We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes. Even when the overhead for cleaning is included, Sprite LFS can use 70% of the disk bandwidth for writing, whereas Unix file systems typically can use only 5–10%.

We analyzed the user-level file access patterns and caching behavior of the Sprite distributed file system. The first part of our analysis repeated a study done in 1985 of the: BSD UNIX file system. We found that file throughput has increased by a factor of 20 to an average of 8 Kbytes per second per active user over 10-minute intervals, and that the use of process migration for load sharing increased burst rates by another factor of six. Also, many more very large (multi-megabyte) files are in use today than in 1985. The second part of our analysis measured the behavior of Sprite's main-memory file caches. Client-level caches average about 7 Mbytes in size (about one-quarter to one-third of main memory) and filter out about 50% of the traffic between clients and servers. 35% of the remaining server traffic is caused by paging, even on workstations with large memories. We found that client cache consistency is needed to prevent stale data errors, but that it is not invoked often enough to degrade overall system performance.

This paper presents a new technique for disk storage management called a log-structured file system. A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, we divide the log into segments and use a segment cleaner to compress the live information from heavily fragmented segments. We present a series of simulations that demonstrate the efficiency of a simple cleaning policy based on cost and benefit. We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes. Even when the overhead for cleaning is included, Sprite LFS can use 70% of the disk bandwidth for writing, whereas Unix file systems typically can use only 5--10%.

Abstract The Sprite operating system allows executing processes to be moved between hosts at any time. We use this process migration mechanism to offload work onto idle machines, and also to evict migrated processes when idle workstations are reclaimed by their owners. Sprite's migration mechanism provides a high degree of transparency both for migrated processes and for users. Idle machines are identified, and eviction is invoked, automatically by daemon processes. On Sprite it takes up to a few hundred milliseconds on SPARCstation 1 workstations to perform a remote exec, whereas evictions typically occur in a few seconds. The pmake program uses remote invocation to invoke tasks concurrently. Compilations commonly obtain speed‐up factors in the range of three to six; they are limited primarily by contention for centralized resources such as file servers. CPU‐bound tasks such as simulations can make more effective use of idle hosts, obtaining as much as eight‐fold speed‐up over a period of hours. Process migration has been in regular service for over two years.

The Sprite network operating system uses large main-memory disk block caches to achieve high performance in its file system. It provides non-write-through file caching on both client and server machines. A simple cache consistency mechanism permits files to be shared by multiple clients without danger of stale data. In order to allow the file cache to occupy as much memory as possible, the file system of each machine negotiates with the virtual memory system over physical memory usage and changes the size of the file cache dynamically. Benchmark programs indicate that client caches allow diskless Sprite workstations to perform within O-12 percent of workstations with disks. In addition, client caching reduces server loading by 50 percent and network traffic by 90 percent.

This paper describes a simple distributed mechanism for caching files among a networked collection of workstations. We have implemented it as part of Sprite, a new operating system being implemented at the University of California at Berkeley. A preliminary version of Sprite is currently running on Sun-2 and Sun-3 workstations, which have about 1-2 MIPS processing power and 4-16 Mbytes of main memory. The system is targeted for workstations like these and newer models likely to become available in the near future; we expect the future machines to have at least five to ten times the processing power and main memory of our current machines, as well as small degrees of multiprocessing. We hope that Sprite will be suitable for networks of up to a few hundred of these workstations. Because of economic and environmental factors, most workstations will not have local disks; instead, large fast disks will be concentrated on a few server machines.

We have implemented a fast hierarchical circuit extractor for the Magic VLSI layout system. The keys to its speed are a new algorithm based on corner-stitching, and its ability to extract cells incrementally. Because the extractor is incremental, typically only a few cells must be re-extracted when the layout changes. The extractor computes circuit connectivity and transistor dimensions, both internodal and substrate parasitic capacitance, and parasitic resistances. It is parameterized to work across a wide range of MOS technologies.

Article Free Access Share on A trace-driven analysis of the UNIX 4.2 BSD file system Authors: John K. Ousterhout Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , Hervé Da Costa Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , David Harrison Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , John A. Kunze Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , Mike Kupfer Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , James G. Thompson Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile Authors Info & Claims SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principlesDecember 1985 Pages 15–24https://doi.org/10.1145/323647.323631Published:01 December 1985Publication History 390citation1,640DownloadsMetricsTotal Citations390Total Downloads1,640Last 12 Months127Last 6 weeks18 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Crystal is a timing verification program for digital nMOS and CMOS circuits. Using the circuit extracted from a mask set, the program determines the length of each clock phase and pinpoints the longest paths. Crystal can process circuits with about 40 000 transistors in about 20-30 min of VAX-11/780 CPU time. The program uses a switch-level approach in which the circuit is decomposed into chains of switches called stages. A depth-first search, with pruning, is used to trace out stages and locate the critical paths. Bidirectional pass transistor arrays are handled by having the designer tag such structures with flow control information, which is used by Crystal to avoid endless searches. Delays are computed on a stage-by-stage basis, using a simple resistor-switch model based on rise-time ratios (a measure of how fully turned-on the transistors in the stage are). The delay modeler executes 10 000 times as fast as SPICE, yet produces delay estimates that are typically within 10 percent of SPICE for digital circuits.

Corner stitching is a technique for representing rectangular two-dimensional objects. It is especially well suited for interactive VLSI layout editing systems. The data structure has two important features: first, empty space is represented explicitly; and second, rectangular areas are stitched together at their corners like a patchwork quilt. This organization results in fast algorithms (linear or constant expected time) for searching, creation, deletion, stretching, and compaction. The algorithms are presented under a simplified model of VLSI circuits, and the storage requirements of the structure are discussed. Corner stitching has been implemented in a working layout editor. Initial measurements indicate that it requires about three times as much memory space as the simplest possible representation.

This paper describes several novel aspects of Caesar, a layout editor for Manhattan-style integrated circuits. The program's user interface is similar to painting. By hiding many irrelevant details, the painting mechanism provides a powerful yet simple user interface. Its implementation using horizontal strips is efficient in both time and space. To handle large circuits efficiently, Caesar represents them hierarchically and capitalizes on their hierarchical structure to avoid excess computation and I/O. Mask information is rendered on color displays with a novel combination of transparent and opaque layers that clarifies layer interactions even in the presence of a large number of mask layers.

Lyra is a layout rule checking program for Manhattan VLSI circuits. In Lyra, rules are specified in terms of constraints that must hold at certain corners in the design. The corner-based mechanism permits a wide variety of rules to be specified easily, including rules involving asymmetric constructs such as transistor overhangs. Lyra's mechanism also has locality, which can be exploited to construct incremental and/or hierarchical checkers. A rule compiler translates symbolic rules into efficient code for checking those rules, and permits the system to be retargeted for different processes.

This paper presents data about three facets of a recently-completed VLSI design containing 45000 transistors. The first set of data describes the mask-level features of the circuit, from which it is seen that almost all features have at least one small dimension. The second set of data analyzes the hierarchical cell structure used by the designers to specify the circuit. The measurements show that composite cells have a different structure from primitive cells, and that, outside of arrays, cells are rarely re-used. The third set of data concerns the usage of an interactive layout program during the circuit's design. In spite of the circuit's size, the most frequently invoked commands were all simple.

The paper is a discussion of the issues that arose in the design of an operating system for a distributed multiprocessor, Cm*. Medusa is an attempt to understand the effect on operating system structure of distributed hardware, and to produce a system that capitalizes on and reflects the underlying architecture. The resulting system combines several structural features that make it unique among existing operating systems.