Algebras based on combinators, i.e., variable-free, have been proposed as a better representation for query compilation and optimization. A key benefit of combinators is that they avoid the need to handle variable shadowing or accidental capture during rewrites. This simplifies both the optimizer specification and its correctness analysis, but the environment from the source language has to be reified as records, which can lead to more complex query plans.

We present Q*cert, a platform for the specification, verification, and implementation of query compilers written using the Coq proof assistant. The Q*cert platform is open source and includes some support for SQL and OQL, and for code generation to Spark and Cloudant. It internally relies on familiar database intermediate representations, notably the nested relational algebra and calculus and a novel extension of the nested relational algebra that eases the handling of environments. The platform also comes with simple but functional and extensible query optimizers.

Designing and prototyping new features is important in many industrial projects. Functional programming and formal verification tools can prove valuable for that purpose, but lead to challenges when integrating with existing product code or when planning technology transfer. This article reports on our experience using the Coq proof assistant as a prototyping environment for building a query compiler intended for use in IBM's ODM Insights product. We discuss the pros and cons of using Coq for this purpose and describe our methodology for porting the compiler to Java, as required for product integration.

This paper describes the Liquid Metal entry in the 2013 ICFPT Design Competition. The Liquid Metal system provides a high-level language called Lime and a toolchain targeting FPGAs. Lime allowed us to use standard software development processes for programming, debugging, and performance tuning our FPGA design. We believe such iteration and refinement are far more challenging with low-level languages and design tools commonly used for FPGA development.

Heterogeneous systems show a lot of promise for extracting high-performance by combining the benefits of conventional architectures with specialized accelerators in the form of graphics processors (GPUs) and reconfigurable hardware (FPGAs). Extracting this performance often entails programming in disparate languages and models, making it hard for a programmer to work equally well on all aspects of an application. Further, relatively little attention is paid to co-execution---the problem of orchestrating program execution using multiple distinct computational elements that work seamlessly together.

Lime is a new Java-compatible and object-oriented language designed to make programming of reconflgurable hardware significantly more accessible to skilled software developers. Lime programs may run either in software (via Java bytecodes) or in hardware (via behavioral and logic synthesis). This paper illustrates the salient synthesis-oriented features of the language using a photo-mosaic algorithm with inherent bit, pipeline, and data parallelism. The result is a virtual machine abstraction that extends across a heterogeneous architecture comprising a CPU, FPGA, and other computational structures.

The halt in clock frequency scaling has forced architects and language designers to look elsewhere for continued improvements in performance. We believe that extracting maximum performance will require compilation to highly heterogeneous architectures that include reconfigurable hardware.

The Flexotask system claims to enable implementation of both real-time applications and real-time schedulers in a Java Virtual Machine using an actors-like model. The PTIDES model is an actors-like model that claims to deliver precise control over end-to-end latencies in a complex real-time system. The present work jointly investigates both claims by (1) implementing several PTIDES-based schedulers as Flexotask scheduler plugins, and (2) using the resulting system to implement a new reactive control program for a simulation of the JAviator. We present results from the realistic JAviator control application and also from synthetic benchmarks designed to shed light on the differences between the several PTIDES schedulers we implemented.

Exotasks are a novel Java programming construct that achieve three important goals. They achieve low latency while allowing the fullest use of Java language features, compared to previous attempts to restrict the Java language for use in the submillisecond domain. They support pluggable schedulers, allowing easy implementation of new scheduling paradigms in a real-time Java system. They can achieve deterministic timing, even in the presence of other Java threads, and across changes of hardware and software platform. To achieve these goals, the program is divided into tasks with private heaps. Tasks may be strongly isolated, communicating only with each other and guaranteeing determinism, or weakly isolated, allowing some communication with the rest of the Java application. Scheduling of the tasks' execution, garbage collection, and value passing is accomplished by the pluggable scheduler. Schedulers that we have written employ logical execution time (LET) in association with strong isolation to achieve time portability. We have also built a quad-rotor model helicopter, the JAviator, which we use to evaluate our implementation of Exotasks in an experimental embedded version of IBM's J9 real-time virtual machine. Our experiments show that we are able to maintain very low scheduling jitter and deterministic behavior in the face of variations in both software load and hardware platform. We also show that Exotasks perform nearly as well as Eventrons on a benchmark audio application.

Real-time Garbage Collection (RTGC) has recently advanced to the point where it is being used in production for financial trading, military command-and-control, and telecommunications. However, among potential users of RTGC, there is enormous diversity in both application requirements and deployment environments.

The disadvantages of unconstrained shared-memory multi-threading in Java, especially with regard to latency and determinism in realtime systems, have given rise to a variety of language extensions that place restrictions on how threads allocate, share, and communicate memory, leading to order-of-magnitude reductions in latency and jitter. However, each model makes different trade-offs with respect to expressiveness, efficiency, enforcement, and latency, and no one model is best for all applications.

The emergence of standards for programming real-time systems in Java has encouraged many developers to consider its use for systems previously only built using C, Ada, or assembly language. However, the RTSJ standard in isolation leaves many important problems unaddressed, and suffers from some serious problems in usability and safety.

Existing programming methodologies for real-time systems suffer from a low level of abstraction and non-determinism in both the timing and the functional domains. As a result, real-time systems are difficult to test and must be re-certified every time changes are made to either the software or hardware environment. Exotasks are a novel Java programming construct that achievedeterministic timing, even in the presence of other Java threads, and across changes of hardware and software platform. They are deterministic functional data-flow tasks written in Java, combined with an orthogonal scheduling policy based on the logical execution time (LET) model. We have built a quad-rotor model helicopter, the JAviator, which we use as a testbed for this work. We evaluate our implementation of exotasks in IBM's J9 real-time virtual machine using actual flights of the helicopter. Our experiments show that we are able to maintain deterministic behavior in the face of variations in both software load and hardware platform.

Embedded systems pose unique challenges to Java application developers and virtual machine designers. Chief among these challenges is the memory footprint of both the virtual machine and the applications that run within it. With the rapidly increasing set of features provided by the Java language, virtual machine designers are often forced to build custom implementations that make various tradeoffs between the footprint of the virtual machine and the subset of the Java language and class libraries that are supported. In this paper, we present the ExoVM, a system in which an application is initialized in a fully featured virtual machine, and then the code, data, and virtual machine features necessary to execute it are packaged into a binary image. Key to this process is feature analysis, a technique for computing the reachable code and data of a Java program and its implementation inside the VM simultaneously. The ExoVM reduces the need to develop customized embedded virtual machines by reusing a single VM infrastructure and automatically eliding the implementation of unused Java features on a per-program basis. We present a constraint-based instantiation of the analysis technique, an implementation in IBM's J9 Java VM, experiments evaluating our technique for the EEMBC benchmark suite, and some discussion of the individual costs of some of Java's features. Our evaluation shows that our system can reduce the non-heap memory allocation of the virtual machine by as much as 75%. We discuss VM and language design decisions that our work shows are important in targeting embedded systems, supporting the long-term goal of a common VM infrastructure spanning from motes to large servers.

While real-time garbage collection has achieved worst-case latencies on the order of a millisecond, this technology is approaching its practical limits. For tasks requiring extremely low latency, and especially periodic tasks with frequencies above 1 KHz, Java programmers must currently resort to the NoHeapRealtimeThread construct of the Real-Time Specification for Java. This technique requires expensive run-time checks, can result in unpredictable low-level exceptions, and inhibits communication with the rest of the garbage-collected application. We present Eventrons, a programming construct that can arbitrarily preempt the garbage collector, yet guarantees safety and allows its data to be visible to the garbage-collected heap. Eventrons are a strict subset of Java, and require no run-time memory access checks. Safety is enforced using a data-sensitive analysis and simple run-time support with extremely low overhead. We have implemented Eventrons in IBM's J9 Java virtual machine, and present experimental results in which we ran Eventrons at frequencies up to 22 KHz (a 45 μs period). Across 10 million periods, 99.997% of the executions ran within 10 μss of their deadline, compared to 99.999% of the executions of the equivalent program written in C.

The Progressive Deployment System (PDS) is a virtual execution environment and infrastructure designed specifically for deploying software, or on demand while enabling management from a central location. PDS intercepts a select subset of system calls on the target machine to provide a partial virtualization at the operating system level. This enables an asset's install-time environment to be reproduced virtually while otherwise not isolating the asset from peer applications on the target machine. Asset components, or shards, are fetched as they are needed (or they may be pre-fetched), enabling the asset to be progressively deployed by overlapping deployment with execution. Cryptographic digests are used to eliminate redundant shards within and among assets, which enables more efficient deployment. A framework is provided for intercepting interfaces above the operating system (e.g., Java class loading), enabling optimizations requiring semantic awareness not present at the OS level. The paper presents the design of PDS, motivates its porous isolation model with respect to the challenges of software deployment, and presents measurements of PDS's execution characteristics.

We describe algorithms to scalably support durable subscriptions in a publish-subscribe system. Durable subscriptions are guaranteed exactly-once message delivery, despite periods of disconnection from the system. Our algorithms persistently log each message only once in the system, and can support administratively specified 'early-release' policies that reclaim persistent storage in the presence of misbehaving durable subscribers. To efficiently recover messages missed by a disconnected durable subscriber, without refiltering messages published while the subscriber was disconnected, we persistently log filtering information in a manner optimized for the read/write pattern of durable subscriptions. Consolidation of data-structures across all subscribers that are done with catching up (after a disconnection) , helps the system support a larger number of subscribers. We experimentally demonstrate the low-latency and scalability properties of our implementation, both in the presence and absence of failures.

Multicast services, assisted by special hardware, are being considered as a part of high-speed wide-area networks (WANs) in order to support new generations of multiuser applications. The paper describes a multicast service application for high-speed WANs which is capable of exploiting multicast hardware. Indeed, this research was conducted in the context of the spanning tree hardware structure of PARIS and of plaNET, the pioneering broadband experimental networks that predated ATM. The results of this research were also included in IBM's ATM, called networking broadband services (NBBS). We achieve modularity and low cost by assigning to distinct components the separate problems of: 1) naming groups; 2) finding group members in a network; 3) configuring multicast hardware; 4) delivering multicast messages in sequence. This modularity enables, for example, the multicast, on one hand, to a group to which the user initiates the joining (formed by using 1 and 2 above) and, on the other hand, to groups computed by the source. We give the overall organization of our service and then describe in detail the methods used to solve the first two of the subproblems.

This paper presents a general knowledge model for propagating information in a content-based publish-subscribe system. The model is used to derive an efficient and scalable Protocol for exactly-once delivery to large numbers (tens of thousands per broker) of content-based subscribers in either publisher order or uniform total order Our protocol allows intermediate content filtering at each hop, but requires persistent storage only at the publishing site. It is tolerant of message drops, message reorderings, node failures, and link failures, and maintains only "soft" state at intermediate nodes. We evaluate the performance of our implementation both under failure-free conditions and with fault injection.

Mockingbird is a prototype tool for developing interlanguage and distributed applications. It compiles stubs from pairs of interface declarations, allowing existing data types to be reused on both sides of every interface. Other multilanguage stub compilers impose data types on the application, complicating development. Mockingbird supports C/C++, Java, and CORBA IDL, and can be extended to other languages. Mockingbird can generate stubs that convert between types whose structural equivalence would be missed by other tools. We show that this kind of tool improves programming productivity, and describe, in detail, Mockingbird's design and implementation.

We describe the design and implementation of the Concert/C compiler and runtime. We describe solutions to the problems of (1) how to extend a language without compromising the use of legacy source and object code and tools, (2) how to extract language-neutral interface information from native language type declarations, (3) how to make function pointers into first-class values transmissable over a network while retaining runtime compatibility with plain C, and (4) how to interoperate with multiple RPC and messaging protocols, selecting protocols at runtime, with little sacrifice of efficiency.>

An application for multicast service for high-speed WANs (wide area networks) which is capable of exploiting multicast hardware is described. Modularity and low cost area achieved by assigning to distinct components the separate problems of (1) naming groups, (2) finding group members in a network, (3) configuring multicast hardware, and (4) delivering multicast messages in sequence. The overall organization of the service is given, along with the methods used to solve the first two subproblems.>

A description is given of TACT (Transport Abstraction Conversion Toolkit), a toolkit (or software function library) for synthesizing conversions between different transport interfaces. TACT classifies transport interfaces according to their abstraction type or basic model of communication. Each actual transport interface is converted to or from a canonical form for its abstraction type, and TACT provides sufficient abstraction converters to convert between all of the canonical forms. A TACT conversion is accomplished by combining some number of elementary conversions that execute in series. Also provided are remedies for other sources of heterogeneity, such as differences in endpoint naming or buffer management. A program that has been augmented with TACT functions can adapt to different available transports at run time.>

This paper describes a “toolkit” (a software function library) for synthesizing conversions between different transport interfaces. The method employed involves classifying these interfaces according to their “transport abstraction type.” Each actual interface is converted to or from a canonical form depending on its type, and the library also contains sufficient “abstraction converters” to convert between all of the canonical forms. The overall conversion is accomplished by combining some number of elementary conversions which execute in series. The paper describes the toolkit, contrasts it with other approaches, and shows how it can be used to solve various problems in protocol conversion and the “migration” of distributed services to new network contexts.

This paper surveys some of the issues involved in building useful distributed systems involving PC's and hosts. Alternative communications techniques for micro-mainframe communication are compared. The point of view is presented that the PC user should be provided with a unified view of the heterogeneous distributed system to which he is connected. The proposed method is to formalize the notion of a service request and provide distributed services by function shipping service requests to remote nodes able to provide the service, e.g., personal computers will ship requests which they cannot satisfy locally to hosts on the network. Providing a unified view of data which allows PC application programs to access files on mainframes is an example of a service which can be built by intercepting and shipping service requests. Examples from current IBM products are used to illustrate approaches. The views presented are the authors' own, based on systems research in progress at the IBM Thomas J. Watson Research Center.