Spanner is Google’s scalable, multiversion, globally distributed, and synchronously replicated database. It is the first system to distribute data at global scale and support externally-consistent distributed transactions. This article describes how Spanner is structured, its feature set, the rationale underlying various design decisions, and a novel time API that exposes clock uncertainty. This API and its implementation are critical to supporting external consistency and a variety of powerful features: nonblocking reads in the past, lock-free snapshot transactions, and atomic schema changes, across all of Spanner.

Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size: petabytes of data across thousands of commodity servers. Many projects at Google store data in Bigtable, including web indexing, Google Earth, and Google Finance. These applications place very different demands on Bigtable, both in terms of data size (from URLs to web pages to satellite imagery) and latency requirements (from backend bulk processing to real-time data serving). Despite these varied demands, Bigtable has successfully provided a flexible, high-performance solution for all of these Google products. In this article, we describe the simple data model provided by Bigtable, which gives clients dynamic control over data layout and format, and we describe the design and implementation of Bigtable.

This session describes three data management projects at Google. BigTable is a highly scalable system for distributed storage and querying of structured data. Sawzall is a system for large-scale analysis of data sets that have a flat but regular structure. Finally, GoogleBase is a system for storing and searching structured data contributed by external parties.

Single-language runtime systems, in the form of Java virtual machines, are widely deployed platforms for executing untrusted mobile code. These runtimes provide some of the features that operating systems provide: interapplication memory protection and basic system services. They do not, however, provide the ability to isolate applications from each other. Neither do they provide the ability to limit the resource consumption of applications. Consequently, the performance of current systems degrades severely in the presence of malicious or buggy code that exhibits ill-behaved resource usage. We show that Java runtime systems can be extended to support processes , and that processes can provide robust and efficient support for untrusted applications.We have designed and built KaffeOS, a Java runtime system that provides support for processes. KaffeOS isolates processes and manages the physical resources available to them: CPU and memory. Unlike existing Java virtual machines, KaffeOS can safely terminate processes without adversely affecting the integrity of the system, and it can fully reclaim a terminated process's resources. Finally, KaffeOS requires no changes to the Java language. The novel aspects of the KaffeOS architecture include the application of a user/kernel boundary as a structuring principle for runtime systems, the employment of garbage collection techniques for resource management and isolation, and a model for direct sharing of objects between untrusted applications. The difficulty in designing KaffeOS lay in balancing the goals of isolation and resource management against the goal of allowing direct sharing of objects.For the SpecJVM benchmarks, the overhead that our KaffeOS prototype incurs ranges from 0% to 25%, when compared to the open-source JVM on which it is based. We consider this overhead acceptable for the safety that KaffeOS provides. In addition, our KaffeOS prototype can scale to run more applications than running multiple JVMs. Finally, in the presence of malicious or buggy code that engages in a denial-of-service attack, KaffeOS can contain the attack, remove resources from the attacked applications, and continue to provide robust service to other clients.

Data access costs contribute significantly to the execution time of applications with complex data structures. As the latency of memory accesses becomes high relative to processor cycle times, application performance is increasingly limited by memory performance. In some situations it may be reasonable to trade increased computation costs for reduced memory costs. The contributions of this paper are three-fold: we provide a detailed analysis of the memory performance of a set of seven, memory-intensive benchmarks; we describe Computation Regrouping, a general, source-level approach to improving the overall performance of these applications by improving temporal locality to reduce cache and TLB miss ratios (and thus memory stall times); and we demonstrate significant performance improvements from applying Computation Regrouping to our suite of seven benchmarks. With Computation Regrouping, we observe an average speedup of 1.97, with individual speedups ranging from 1.26 to 3.03. Most of this improvement comes from eliminating memory stall time.

We have designed and implemented Maya, a version of Java that allows programmers to extend and reinterpret its syntax. Maya generalizes macro systems by treating grammar productions as generic functions, and semantic actions on productions as multimethods on the corresponding generic functions. Programmers can write new generic functions (i.e., grammar productions) and new multimethods (i.e., semantic actions), through which they can extend the grammar of the language and change the semantics of its syntactic constructs, respectively. Maya's multimethods are compile-time metaprograms that transform abstract syntax: they execute at program compile-time, because they are semantic actions executed by the parser. Maya's multimethods can be dispatched on the syntactic structure of the input, as well as the static, source-level types of expressions in the input. In this paper we describe what Maya can do and how it works. We describe how its novel parsing techniques work and how Maya can statically detect certain kinds of errors, such as code that generates references to free variables. Finally, to demonstrate Maya's expressiveness, we describe how Maya can be used to implement the MultiJava language, which was described by Clifton et al. at OOPSLA 2000.

Typical translation lookaside buffers (TLBs) can map a far smaller region of memory than application footprints demand, and the cost of handling TLB misses therefore limits the performance of an increasing number of applications. This bottleneck can be mitigated by the use of superpages, multiple adjacent virtual memory pages that can be mapped with a single TLB entry that extend TLB reach without significantly increasing size or cost. We analyze hardware/software tradeoff for dynamically creating superpages. This study extends previous work by using execution-driven simulation to compare creating superpages via copying with remapping pages within the memory controller and by examining how the tradeoffs change when moving front a single-issue to a superscalar processor model. We find that remapping-based promotion outperforms copying-based promotion, often significantly. Copying-based promotion is slightly more effective on superscalar processors than on single-issue processors, and the relative performance of remapping-based promotion on the two platform is application-dependent.

We present Jiazzi, a system that enables the construction of large-scale binary components in Java. Jiazzi components can be thought of as generalizations of Java packages with added support for external linking and separate compilation. Jiazzi components are practical becuase they are constructed out of standard Java source code. Jiazzi requires neither extensions to the Java language nor special conventions for writing Java source code that will go inside a component. Our components are expressive becuase Jiazzi supports cyclic component linking and mixins, which are used together in an open class pattern that enables the modular addition of new features to existing classes. This paper describes Jiazzi, how it enhances Java with components, its implementation, and how type checking works. An implementation of Jiazzi is available for download.

Impulse is a memory system architecture that adds an optional level of address indirection at the memory controller. Applications can use this level of indirection to remap their data structures in memory. As a result, they can control how their data is accessed and cached, which can improve cache and bus utilization. The Impulse design does not require any modification to processor, cache, or bus designs since all the functionality resides at the memory controller. As a result, Impulse can be adopted in conventional systems without major system changes. We describe the design of the Impulse architecture and how an Impulse memory system can be used in a variety of ways to improve the performance of memory-bound applications. Impulse can be used to dynamically create superpages cheaply, to dynamically recolor physical pages, to perform strided fetches, and to perform gathers and scatters through indirection vectors. Our performance results demonstrate the effectiveness of these optimizations in a variety of scenarios. Using Impulse can speed up a range of applications from 20 percent to over a factor of 5. Alternatively, Impulse can be used by the OS for dynamic superpage creation; the best policy for creating superpages using Impulse outperforms previously known superpage creation policies.

No abstract available.

Impulse is a new memory system architecture that adds two important features to a traditional memory controller. First, Impulse supports application-specific optimizations through configurable physical address remapping. By remapping physical addresses, applications control how their data is accessed and cached, improving their cache and bus utilization. Second, Impulse supports prefetching at the memory controller, which can hide much of the latency of DRAM accesses. In this paper we describe the design of the Impulse architecture, and show how an Impulse memory system can be used to improve the performance of memory-bound programs. For the NAS conjugate gradient benchmark, Impulse improves performance by 67%. Because it requires no modification to processor, cache, or bus designs, Impulse can be adopted in conventional systems. In addition to scientific applications, we expect that Impulse will benefit regularly strided memory-bound applications of commercial importance, such as database and multimedia programs.

Dynamic code generation allows programmers to use run-time information in order to achieve performance and expressiveness superior to those of static code. The 'C(Tick C) language is a superset of ANSI C that supports efficient and high-level use of dynamic code generation. 'C provides dynamic code generation at the level of C expressions and statements and supports the composition of dynamic code at run time. These features enable programmers to add dynamic code generation to existing C code incrementally and to write important applications (such as “just-in-time” compilers) easily. The article presents many examples of how 'C can be used to solve practical problems. The tcc compiler is an efficient, portable, and freely available implementation of 'C. tcc allows programmers to trade dynamic compilation speed for dynamic code quality: in some aplications, it is most important to generate code quickly, while in others code quality matters more than compilation speed. The overhead of dynamic compilation is on the order of 100 to 600 cycles per generated instruction, depending on the level of dynamic optimizaton. Measurements show that the use of dynamic code generation can improve performance by almost an order of magnitude; two- to four-fold speedups are common. In most cases, the overhead of dynamic compilation is recovered in under 100 uses of the dynamic code; sometimes it can be recovered within one use.

Many modern extensible systems, such as Java and the SPIN operating system, depend on type safety for memory protection. Unfortunately, current type-safe languages do not support systems programming well, because they do not give programmers the ability to deal with untyped data easily. In particular, they do not support the ability to cast between untyped data and language-level types. We describe a powerful, type-safe cast operator that helps programmers write low-level systems codes in type-safe languages. We have implemented this operator in Modula-3 for the SPIN operating system, and we give specific examples of how we use it in SPIN. © 1998 John Wiley & Sons, Ltd.

Atomic recovery units (ARUs) are a mechanism that allows several logical disk operations to be executed as a single atomic unit with respect to failures. For example, ARUs can be used during file creation to update several pieces of file meta-data atomically. ARUs simplify systems, as they isolate issues of atomicity within the logical disk system, ARUs are designed as part of the Logical Disk (LD), which provides an interface to disk storage that separates file and disk management by using logical block numbers and block lists. This paper discusses the semantics of concurrent ARUs, as well as the concurrency control they require. A prototype implementation in a log-structured logical disk system is presented and evaluated. The performance evaluation shows that the run-time overhead to support concurrent ARUs is negligible for Read and Write operations, and small but pronounced for file creation (4.0%-7.2%) and deletion (17.9%-20.5%) which mainly manipulate meta-data. The low overhead (when averaged over file creation, writing, reading, and deletion) for concurrent ARUs shows that issues of atomicity can be successfully isolated within the disk system.

Dynamic code generation allows specialized code sequences to be created using runtime information. Since this information is by definition not available statically, the use of dynamic code generation can achieve performance inherently beyond that of static code generation. Previous attempts to support dynamic code generation have been low-level, expensive, or machine-dependent. Despite the growing use of dynamic code generation, no mainstream language provides flexible, portable, and efficient support for it.We describe 'C (Tick C), a superset of ANSI C that allows flexible, high-level. efficient, and machine-independent specification of dynamically generated code. 'C provides many of the performance benefits of pure partial evaluation, but in the context of a complex, statically typed, but widely used language. 'C examples illustrate the ease of specifying dynamically generated code and how it can be put to use. Experiments with a prototype compiler show that 'C enables excellent performance improvement (in some cases, more than an order of magnitude).

We describe dynamic computation migration, the runtime choice between computation and data migration. Dynamic computation migration is useful for concurrent data structures with unpredictable read/write patterns. We implemented it in MCRL, a multithreaded DSM system that runs on the MIT Alewife machine and Thinking Machines' CM-5. We evaluate two dynamic migration heuristics relative to data migration. On a concurrent, distributed B-tree with 50% lookups and 50% inserts, the STATIC heuristic improves performance by about 17%, on both Alewife and the CM-5. The REPEAT heuristic generally performs better than the STATIC heuristic. On Alewife, with 80% lookups and 20% inserts, the REPEAT heuristic improves performance by 23%; on the CM-5, it improves performance by 46%. Our results apply to concurrent, dynamic data structures whose access patterns are only known at runtime. For regularly accessed data structures, static methods will always be applicable, but we expect future applications to be more dynamic.

Low-overhead message passing is critical to the performance of many applications. Active Messages reduce the software overhead for message handling: messages are run as handlers instead of as threads, which avoids the overhead of thread management and the unnecessary data copying of other communication models. Scheduling the execution of Active Messages is typically done by disabling and enabling interrupts, or by polling the network. This primitive scheduling control, combined with the fact that handlers are not schedulable entities, puts severe restrictions on the code that can be run in a message handler. This paper describes a new software mechanism, Optimistic Active Messages (OAM), that eliminates these restrictions; OAMs allow arbitrary user code to execute in handlers, and also allow handlers to block. Despite this gain in expressiveness, OAMs perform as well as Active Messages.

We describe computation migration, a new technique that is based on compile-time program transformations, for accesing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the access is performed remotely, and with data migration, where the data is moved so that it is local, computation migration moves part of the current thread to the processor where the data resides. The access is performed at the remote processor, and the migrated thread portion continues to run on that same processor; this makes subsequent accesses in the thread portion local.

The Logical Disk (LD) defines a new interface to disk storage that separates file management and disk management by using logical block numbers and block lists. The LD interface is designed to support multiple file systems and to allow multiple implementations, both of which are important given the increasing use of kernels that support multiple operating system personalities.A log-structured implementation of LD (LLD) demonstrates that LD can be implemented efficiently. LLD adds about 5% to 10% to the purchase cost of a disk for the main memory it requires. Combining LLD with an existing file system results in a log-structured file system that exhibits the same performance characteristics as the Sprite log-structured file system.

Article Free Access Share on Automatic generation of DAG parallelism Authors: R. Cytron IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , M. Hind Courant Institute, New York University, 251 Mercer St., New York, NY Courant Institute, New York University, 251 Mercer St., New York, NYView Profile , W. Hsieh Laboratory for Computer Science, Massachusetts Institute, Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute, Technology, Cambridge, MAView Profile Authors Info & Claims PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementationJune 1989 Pages 54–68https://doi.org/10.1145/73141.74823Published:21 June 1989Publication History 37citation653DownloadsMetricsTotal Citations37Total Downloads653Last 12 Months44Last 6 weeks4 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

An approach to finding and forming parallel processes for both sequential and parallel programs is presented. The approach is presented in a framework that can create useful parallelism for a variety of parallel architectures. The framework makes use of a control dependence graph to capture maximal parallelism, a process tree to expose useful parallelism, renaming and storage segregation to reduce data dependencies, and an architecture-specific cost analyzer to evaluate the effectiveness of the potential processes. The framework is currently being implemented.