Visual SLAM systems are concurrent, performance-critical systems that respond to real-time environmental conditions and are frequently deployed on resource-constrained hardware. Previous work has identified three interconnected systems challenges to building consistent, accurate, and robust SLAM systems— timeliness , concurrency , and context awareness . In this article, we analyze three popular, state-of-the-art frameworks with varying system designs and optimization techniques, and we quantify the extent to which they are affected by the aforementioned system challenges. We find that all SLAM systems must balance the interconnected nature of timeliness and accuracy, and different system designs and optimization techniques uniquely address this tension. Global-map-based SLAM systems typically achieve the best performance but suffer in resource-constrained scenarios with increased concurrency . Across all SLAM systems, incorporating context awareness into decision-making would mitigate the impact of timeliness and concurrency on accuracy in resource-constrained scenarios.

In the rapidly evolving landscape of Unmanned Aerial Vehicles (UAVs), regulation enforcement is critical. Unfortunately, existing practices are largely manual and reactive in nature. We present Themis1, a novel compiler-directed approach for automated and proactive regulation enforcement. By expressing regulations through a specification language and integrating their enforcement into the compilation process, Themis enables safe and regulation-compliant UAV flights by enforcing prohibited and restricted areas, avoiding flights over humans, and managing maximum limits of altitude and speed. Our framework features a bidirectional interface that allows the concrete algorithms used for enforcement to be customized. Our evaluation shows Themis-compiled autopilots can adhere to regulatory constraints amidst complex flight conditions, while significantly reducing the burden of UAV operators.

With the rapid growth of Artificial Intelligence (AI) applications supported by deep learning (DL), the energy efficiency of these applications has an increasingly large impact on sustainability. We introduce Smaragdine, a new energy accounting system for tensor-based DL programs implemented with TensorFlow. At the heart of Smaragdine is a novel white-box methodology of energy accounting: Smaragdine is aware of the internal structure of the DL program, which we call tensor-aware energy accounting. With Smaragdine, the energy consumption of a DL program can be broken down into units aligned with its logical hierarchical decomposition structure. We apply Smaragdine for understanding the energy behavior of BERT, one of the most widely used language models. Layer-by-layer and tensor-by-tensor, Smaragdine is capable of identifying the highest energy/power-consuming components of BERT. Furthermore, we conduct two case studies on how Smaragdine supports downstream toolchain building, one on the comparative energy impact of hyperparameter tuning of BERT, the other on the energy behavior evolution when BERT evolves to its next generation, ALBERT.

Online data services have stringent performance requirement and must tolerate workload fluctuation. This paper introduces P it S top , a new query language runtime design built on the idea of interruptible query processing : the time-consuming task of data inspection for processing each query or update may be interrupted and resumed later at the boundary of fine-grained data partitions. This counter-intuitive idea enables a novel form of fine-grained concurrency while preserving sequential consistency . We build P it S top through modifying the language runtime of Cypher, the query language of a state-of-the-art graph database, Neo4j. Our evaluation on the Google Cloud shows that P it S top can outperform unmodified Neo4j during workload fluctuation, with reduced latency and increased throughput.

Power modeling is an essential building block for computer systems in support of energy optimization, energy profiling, and energy-aware application development. We introduce Vesta , a novel approach to modeling the power consumption of applications with one key insight: language runtime events are often correlated with a sustained level of power consumption. When compared with the established approach of power modeling based on hardware performance counters (HPCs), Vesta has the benefit of solely requiring application-scoped information and enabling a higher level of explainability, while achieving comparable or even higher precision. Through experiments performed on 37 real-world applications on the Java Virtual Machine (JVM), we find the power model built by Vesta is capable of predicting energy consumption with a mean absolute percentage error of 1.56 % , while the monitoring of language runtime events incurs small performance and energy overhead.

Developing energy-aware applications is a well known approach to software-based energy optimization. This promising approach is however faced with a significant hurdle when deployed to the environments shared among multiple applications, where the energy consumption effected by one application may erroneously be observed by another application. We introduce Eflect, a novel software framework for disentangling the energy consumption of co-running applications. Our key idea, called energy virtualization, enables each energy-aware application to be only aware of the energy consumption effected by its execution. Eflect is unique in its lightweight design: it is a purely application-level solution that requires no modification to the underlying hardware or system software. Experiments show Eflect incurs low overhead with high precision. Furthermore, it can seamlessly port existing application-level energy frameworks --- one for energy-adaptive approximation and the other for energy profiling --- to shared environments while retaining their intended effectiveness.

Visual SLAM is a long-standing research area with many significant advances over the years. New systems typically build on previous contributions, but this requires significant development overhead, a highly detailed understanding of previous system implementations, and is rife with programming pitfalls. To enable fast experimentation and reduce the need for researchers to re-invent the wheel, we propose an extensible Visual SLAM framework with three features: modularity, seamless edge offloading, and safe concurrency.

Data processing systems are a fundamental component of the modern computing stack. These systems are routinely deployed online: they continuously receive the requests of data processing operations, and continuously return the results to end users or client applications. Online data processing systems have unique features beyond conventional data processing, and the optimizations designed for them are complex, especially when data themselves are structured and dynamic. This paper describes DON Calculus, the first rigorous foundation for online data processing. It captures the essential behavior of both the backend data processing engine and the frontend application, with the focus on two design dimensions essential yet unique to online data processing systems: incremental operation processing (IOP) and temporal locality optimization (TLO). A novel design insight is that the operations continuously applied to the data can be defined as an operation stream flowing through the data structure, and this abstraction unifies diverse designs of IOP and TLO in one calculus. DON Calculus is endowed with a mechanized metatheory centering around a key observable equivalence property: despite the significant non-deterministic executions introduced by IOP and TLO, the observable result of DON Calculus data processing is identical to that of conventional data processing without IOP and TLO. Broadly, DON Calculus is a novel instance in the active pursuit of providing rigorous guarantees to the software system stack. The specification and mechanization of DON Calculus provide a sound base for the designers of future data processing systems to build upon, helping them embrace rigorous semantic engineering without the need of developing from scratch.

Unmanned Aerial Vehicles (UAVs) are an emerging computation platform known for their safety-critical need. In this paper, we conduct an empirical study on a widely used open-source UAV software framework, Paparazzi, with the goal of understanding the safety-critical concerns of UAV software from a bottom-updeveloper-in-the-fieldperspective. We set our focus on the use of Bounding Functions (BFs), the runtime checks injected by Paparazzi developers on the range of variables. Through an in-depth analysis on BFs in the Paparazzi autopilot software, we found a large number of them (109 instances) are used to bound safety-critical variables essential to the cyber-physical nature of the UAV, such as its thrust, its speed, and its sensor values. The novel contributions of this study are two fold. First, we take a static approach to classify all BF instances, presenting a noveldatatype-based5-category taxonomy with fine-grained insight on the role of BFs in ensuring the safety of UAV systems. Second, we dynamically evaluate the impact of the BF uses through adifferentialapproach, establishing the UAV behavioral difference with and without BFs. The two-pronged static and dynamic approach together illuminates a rarely studied design space of safety-critical UAV software systems.

UAVs are deployed in various applications including disaster search-and-rescue, precision agriculture, law enforcement and first response. As UAV software systems grow more complex, the drawbacks of developing them in low-level languages become more pronounced. For example, the lack of memory safety in C implies poor isolation between the UAV autopilot and other concurrent tasks. As a result, the most crucial aspect of UAV reliability-timely control of the flight-could be adversely impacted by other tasks such as perception or planning. We introduce JCopter, an autopilot framework for UAVs developed in a managed language, i.e., a high-level language with built-in safe memory and timing management. Through detailed simulation as well as flight testing, we demonstrate how JCopter retains the timeliness of C-based autopilots while also providing the reliability of managed languages.

Energy accounting is a fundamental problem in energy management, defined as attributing global energy consumption to individual components of interest. In this paper, we take on this problem at the application level, where the components for accounting are application logical units, such as methods, classes, and packages. Given a Java application, our novel runtime system Chappie produces an energy footprint, i.e., the relative energy consumption of all programming abstraction units within the application.

Mobile applications regularly interact with their noisy and ever-changing physical environment. The fundamentally uncertain nature of such interactions leads to significant challenges in energy optimization, a crucial goal of software engineering on mobile devices. This paper presents Aeneas, a novel energy optimization framework for Android in the presence of uncertainty. Aeneas provides a minimalistic programming model where acceptable program behavioral settings are abstracted as knobs and application-specific optimization goals — such as meeting an energy budget — are crystallized as rewards, both of which are directly programmable. At its heart, Aeneas is endowed with a stochastic optimizer to adaptively and intelligently select the reward-optimal knob setting through a form of reinforcement learning. We evaluate Aeneas on mobile GPS applications built over Google LocationService API. Through an in-field case study that covers approximately 6500 miles and 150 hours of driving as well as 20 hours of biking and hiking, we find that Aeneas can effectively and resiliently meet programmer-specified energy budgets in uncertain physical environments where individual GPS readings undergo significant fluctuation. Compared with non-stochastic approaches such as profile-guided optimization, Aeneas produces significantly more stable results across runs.

ForkJoin framework is a widely used parallel programming framework upon which both core concurrency libraries and real-world applications are built. Beneath its simple and user-friendly APIs, ForkJoin is a sophisticated managed parallel runtime unfamiliar to many application programmers: the framework core is a work-stealing scheduler, handles fine-grained tasks, and sustains the pressure from automatic memory management. ForkJoin poses a unique gap in the compute stack between high-level software engineering and low-level system optimization. Understanding and bridging this gap is crucial for the future of parallelism support in JVM-supported applications. This paper describes a comprehensive study on parallelism bottlenecks in ForkJoin applications, with a unique focus on how they interact with underlying system-level features, such as work stealing and memory management. We identify 6 bottlenecks, and found that refactoring them can significantly improve performance and energy efficiency. Our field study includes an in-depth analysis of Akka — a real-world actor framework — and 30 additional open-source ForkJoin projects. We sent our patches to the developers of 15 projects, and 7 out of the 9 projects that replied to our patches have accepted them.

Application-level energy management is an important dimension of energy optimization. In this paper, we introduce ENT, a novel programming language for enabling *proactive* and *adaptive* mode-based energy management at the application level. The proactive design allows programmers to apply their application knowledge to energy management, by characterizing the energy behavior of different program fragments with modes. The adaptive design allows such characterization to be delayed until run time, useful for capturing dynamic program behavior dependent on program states, configuration settings, external battery levels, or CPU temperatures. The key insight is both proactiveness and adaptiveness can be unified under a type system combined with static typing and dynamic typing. ENT has been implemented as an extension to Java, and successfully ported to three energy-conscious platforms: an Intel-based laptop, a Raspberry Pi, and an Android phone. Evaluation shows ENT improves the programmability, debuggability, and energy efficiency of battery-aware and temperature-aware programs.

This paper presents a Haskell library for graph processing: DeltaGraph. One unique feature of this system is that intentions to perform graph updates can be memoized in-graph in a decentralized fashion, and the propagation of these intentions within the graph can be decoupled from the realization of the updates. As a result, DeltaGraph can respond to updates in constant time and work elegantly with parallelism support. We build a Twitter-like application on top of DeltaGraph to demonstrate its effectiveness and explore parallelism and opportunistic computing optimizations.

A growing number of energy optimization solutions operate at the application runtime level. Despite delivering promising results, these application-scoped optimizations are fundamentally greedy: They assume to have an exclusive access to power management and often perform poorly when multiple power-managing applications co-exist, or different threads of the same application share power management hardware. In this paper, we introduce AEQUITAS, a first step to address this critical yet largely overlooked problem. The insight behind AEQUITAS is that co-existing applications may view power-managing hardware as a shared resource and coordinate power management decisions. As a concrete instance of this philosophy, we evaluated our ideas on top of a state-of-the-art energy-efficient work-stealing runtime. Experiments show that without AEQUITAS, multiple co-existing power-managing application runtimes suffer up to 32% performance loss and negate all power savings. With AEQUITAS, the beneficial energy-performance tradeoff reported in the single-application setting (12.9% energy savings and 2.5% performance loss) can be retained, but in a much more challenging setting where multiple power-managing runtimes co-exist on parallel architectures and multiple CPU cores share the same power domain.

Java programmers are served with numerous choices of collections, varying from simple sequential ordered lists to sophisticated hashtable implementations. These choices are well-known to have different characteristics in terms of performance, scalability, and thread-safety, and most of them are well studied. This paper analyzes an additional dimension, energy efficiency. We conducted an empirical investigation of 16 collection implementations (13 thread-safe, 3 non-thread-safe) grouped under 3 commonly used forms of collections (lists, sets, and mappings). Using micro-and real world-benchmarks (Tomcat and Xalan), we show that our results are meaningful and impactful. In general, we observed that simple design decisions can greatly impact energy consumption. In particular, we found that using a newer hashtable version can yield a 2.19x energy savings in the micro-benchmarks and up to 17% in the real world-benchmarks, when compared to the old associative implementation. Also, we observed that different implementations of the same thread-safe collection can have widely different energy consumption behaviors. This variation also applies to the different operations that each collection implements, e.g, a collection implementation that performs traversals very efficiently can be more than an order of magnitude less efficient than another implementation of the same collection when it comes to insertions.

Analyzing the energy consumption of application level software is an emerging direction. This artifact makes available all the toolset and raw data needed to reproduce the main findings of our research paper. The artifact consists of: ● The source code of the micro-benchmarks analyzed, ● The source code of the case study used, ● The jRAPL tool, ● The raw energy data generated by the jRAPL tool with the source code of the experiments, ● The plotting scripts used to create the figures of the paper, based on the raw energy data.

This paper introduces a novel type-and-effect calculus, first-class effects, where the computational effect of an expression can be programmatically reflected, passed around as values, and analyzed at run time. A broad range of designs "hard-coded" in existing effect-guided analyses — from thread scheduling, version-consistent software updating, to data zeroing — can be naturally supported through the programming abstractions. The core technical development is a type system with a number of features, including a hybrid type system that integrates static and dynamic effect analyses, a refinement type system to verify application-specific effect management properties, a double-bounded type system that computes both over-approximation of effects and their under-approximation. We introduce and establish a notion of soundness called trace consistency, defined in terms of how the effect and trace correspond. The property sheds foundational insight on "good" first-class effect programming.

Type-and-effect systems are a powerful tool for program construction and verification. We describe intensional effect polymorphism, a new foundation for effect systems that integrates static and dynamic effect checking. Our system allows the effect of polymorphic code to be intensionally inspected through a lightweight notion of dynamic typing. When coupled with parametric polymorphism, the powerful system utilizes runtime information to enable precise effect reasoning, while at the same time retains strong type safety guarantees. We build our ideas on top of an imperative core calculus with regions. The technical innovations of our design include a relational notion of effect checking, the use of bounded existential types to capture the subtle interactions between static typing and dynamic typing, and a differential alignment strategy to achieve efficiency in dynamic typing. We demonstrate the applications of intensional effect polymorphism in concurrent programming, security, graphical user interface access, and memoization.

This paper presents a novel energy-aware and temperature-aware programming model with first-class support for sustainability. A program written in the new language, named Eco, may adaptively adjusts its own behaviors to stay on a given (energy or temperature) budget, avoiding both deficit that would lead to battery drain or CPU overheating, and surplus that could have been used to improve the quality of results. Sustainability management in Eco is captured as a form of supply and demand matching, and the language runtime consistently maintains the equilibrium between supply and demand. Among the efforts of energy-adaptive and temperature-adaptive systems, Eco is distinctive in its role in bridging the programmer and the underlying system, and in particular, bringing both programmer knowledge and application-specific traits into energy optimization. Through a number of intuitive programming abstractions, Eco reduces challenging issues in this domain --- such as workload characterization and decision making in adaptation --- to simple programming tasks, ultimately offering fine-grained, programmable, and declarative sustainability to energy-efficient computing. Eco is an minimal extension to Java, and has been implemented as an open-source compiler. We validate the usefulness of Eco by upgrading real-world Java applications with energy awareness and temperature awareness.

Work stealing is a promising approach to constructing multithreaded program runtimes of parallel programming languages. This paper presents HERMES, an energy-efficient work-stealing language runtime. The key insight is that threads in a work-stealing environment -- thieves and victims - have varying impacts on the overall program running time, and a coordination of their execution "tempo" can lead to energy efficiency with minimal performance loss. The centerpiece of HERMES is two complementary algorithms to coordinate thread tempo: the workpath-sensitive algorithm determines tempo for each thread based on thief-victim relationships on the execution path, whereas the workload-sensitive algorithm selects appropriate tempo based on the size of work-stealing deques. We construct HERMES on top of Intel Cilk Plus's runtime, and implement tempo adjustment through standard Dynamic Voltage and Frequency Scaling (DVFS). Benchmarks running on HERMES demonstrate an average of 11-12% energy savings with an average of 3-4% performance loss through meter-based measurements over commercial CPUs.

A growing number of software solutions have been proposed to address application-level energy consumption problems in the last few years. However, little is known about how much software developers are concerned about energy consumption, what aspects of energy consumption they consider important, and what solutions they have in mind for improving energy efficiency. In this paper we present the first empirical study on understanding the views of application programmers on software energy consumption problems. Using StackOverflow as our primary data source, we analyze a carefully curated sample of more than 300 questions and 550 answers from more than 800 users. With this data, we observed a number of interesting findings. Our study shows that practitioners are aware of the energy consumption problems: the questions they ask are not only diverse -- we found 5 main themes of questions -- but also often more interesting and challenging when compared to the control question set. Even though energy consumption-related questions are popular when considering a number of different popularity measures, the same cannot be said about the quality of their answers. In addition, we observed that some of these answers are often flawed or vague. We contrast the advice provided by these answers with the state-of-the-art research on energy consumption. Our summary of software energy consumption problems may help researchers focus on what matters the most to software developers and end users.

We introduce RATE TYPES, a novel type system to reason about and optimize data-intensive programs. Built around stream languages, RATE TYPES performs static quantitative reasoning about stream rates -- the frequency of data items in a stream being consumed, processed, and produced. Despite the fact that streams are fundamentally dynamic, we find two essential concepts of stream rate control -- throughput ratio and natural rate -- are intimately related to the program structure itself and can be effectively reasoned about by a type system. RATE TYPES is proven to correspond with a time-aware and parallelism-aware operational semantics. The strong correspondence result tolerates arbitrary schedules, and does not require any synchronization between stream filters.We further implement RATE TYPES, demonstrating its effectiveness in predicting stream data rates in real-world stream programs.

Java programmers are faced with numerous choices in managing concurrent execution on multicore platforms. These choices often have different trade-offs (e.g., performance, scalability, and correctness guarantees). This paper analyzes an additional dimension, energy consumption. It presents an empirical study aiming to illuminate the relationship between the choices and settings of thread management constructs and energy consumption. We consider three important thread management constructs in concurrent programming: explicit thread creation, fixed-size thread pooling, and work stealing. We further shed light on the energy/performance trade-off of three ``tuning knobs'' of these constructs: the number of threads, the task division strategy, and the characteristics of processed data. Through an extensive experimental space exploration over real-world Java programs, we produce a list of findings about the energy behaviors of concurrent programs, which are not always obvious. The study serves as a first step toward improving energy efficiency of concurrent programs on parallel architectures.

This paper introduces Green Streams, a novel solution to address a critical but often overlooked property of data-intensive software: energy efficiency. Green Streams is built around two key insights into data-intensive software. First, energy consumption of data-intensive software is strongly correlated to data volume and data processing, both of which are naturally abstracted in the stream programming paradigm; Second, energy efficiency can be improved if the data processing components of a stream program coordinate in a “balanced” way, much like an assembly line that runs most efficiently when participating workers coordinate their pace. Green Streams adopts a standard stream programming model, and applies Dynamic Voltage and Frequency Scaling (DVFS) to coordinate the pace of data processing among components, ultimately achieving energy efficiency without degrading performance in a parallel processing environment. At the core of Green Streams is a novel constraint-based inference to abstract the intrinsic relationships of data flow rates inside a stream program, that uses linear programming to minimize the frequencies — hence the energy consumption — for processing components while still maintaining the maximum output data flow rate. The core algorithm of Green Streams is formalized, and its optimality is established. The effectiveness of Green Streams is evaluated on top of the StreamIt framework, and preliminary results show the approach can save CPU energy by an average of 28% with a 7% performance improvement.

This paper presents a novel type system to promote and facilitate energy-aware programming. Energy Types is built upon a key insight into today's energy-efficient systems and applications: despite the popular perception that energy and power can only be described in joules and watts, real-world energy management is often based on discrete phases and modes, which in turn can be reasoned about by type systems very effectively. A phase characterizes a distinct pattern of program workload, and a mode represents an energy state the program is expected to execute in. This paper describes a programming model where phases and modes can be intuitively specified by programmers or inferred by the compiler as type information. It demonstrates how a type-based approach to reasoning about phases and modes can help promote energy efficiency. The soundness of our type system and the invariants related to inter-phase and inter-mode interactions are rigorously proved. Energy Types is implemented as the core of a prototyped object-oriented language ET for smartphone programming. Preliminary studies show ET can lead to significant energy savings for Android Apps.

Atomic regions are an important concept in correct concurrent programming: since atomic regions can be viewed as having executed in a single step, atomicity greatly reduces the number of possible interleavings the programmer needs to consider. This paper describes a method for building atomicity into a programming language in an organic fashion. We take the view that atomicity holds for whole threads by default, and a division into smaller atomic regions occurs only at points where an explicit need for sharing is needed and declared. A corollary of this view is every line of code is part of some atomic region. We define a polymorphic type system, Task Types, to enforce most of the desired atomicity properties statically. We show the reasonableness of our type system by proving that type soundness, isolation invariance, and atomicity enforcement properties hold at run time. We also present initial results of a Task Types implementation built on Java

Software deployment is a complex process, and industrial-strength frameworks such as .NET, Java, and CORBA all provide explicit support for component deployment. However, these frameworks are not built around fundamental principles as much as they are engineering efforts closely tied to particulars of the respective systems. Here we aim to elucidate the fundamental principles of software deployment, in a platform-independent manner. Issues that need to be addressed include deployment unit design, when, where and how to wire components together, versioning, version dependencies, and hot-deployment of components. We define the application buildbox as the place where software is developed and deployed, and define a formal Labeled Transition System (LTS) on the buildbox with transitions for deployment operations that include build, install, ship, and update. We establish formal properties of the LTS, including the fact that if a component is shipped with a certain version dependency, then at run time that dependency must be satisfied with a compatible version. Our treatment of deployment is both platform- and vendor-independent, and we show how it models the core mechanisms of the industrial-strength deployment frameworks.

This paper presents Classages, a novel interaction-centric object-oriented language. Classes and objects in Classages are fully encapsulated, with explicit interfaces for all interactions they might be involved in. The design of Classages touches upon a wide range of language design topics, including encapsulation, object relationship representation, and object confinement. An encoding of Java's OO model in Classages is provided, showing how standard paradigms are supported. A prototype Classages compiler is described.