The term Internet of Things (IoT) has generated a lot of buzz in the information technology and consumer electronics industries. In the IoT setting, a large number of physically dispersed devices - such as sensors, actuators and processing units - coordinate to bring useful capabilities to the user. A significant portion of these devices may have rather small computation and storage footprints, but at the same time, they can leverage support from potential enormous computation and storage resources via the cloud. Also, a large set of small footprint devices can serve not just a single logical app or service, but also many independent logical apps or services. This requires a careful separation of computational activities and their associated data within a device, for privacy and security purposes. Application development for the Internet of Things gives a whole new meaning to the term "programming in the large", and some of this is likely to be new to the practitioner. This talk will discuss what the IoT environment means to the practical programmer, and what apps and app ecosystems for IoT might look like. The talk will also discuss the issues and open challenges in software engineering brought on by this new environment, pointing towards new opportunities for researchers in our community.

The World Wide Web (WWW) has become an indispensable part of the modern life, providing many benefits in diverse ways. For instance, the huge amount of information from the web offers people unprecedented levels of opportunities for education, entertainments, social activities, productivity improvements, and business. The web, however, has also become perilous with many dangers, such as privacy violation and security breaches, and therein exist many villains who would like to turn into victims scrupulous as well as casual users. In this regard, WWW has become almost like Wild Wild West, where wonderful opportunities and great perils co-existed. Tizen (www.tizen.org) is a web-centric open-source, standards-based software platform for smart devices, such as smartphones, smart TVs, IVI (In-Vehicle Infotainment) and other consumer devices like cameras, printers, and more. Tizen is web-centric in that it directly supports web apps - applications (apps) written in HTML5 and Javascript - even outside the web-browsers and provides seamless supports for the web. As such, Tizen not only shares the benefits and perils of the web with other platforms, but also has the additional burden to meet the performance of non-web platforms: platforms that directly support only conventional programming languages. In this talk, we present Tizen's approaches to taming the web to maximize its benefits while minimizing the risks of its perils. We also describe various optimizations of Tizen that enable delivering web-app performance on par with that of non-web platforms.

In this paper, we present the design and implementation of an Open Computing Language (OpenCL) framework that targets heterogeneous accelerator multicore architectures with local memory. The architecture consists of a general-purpose processor core and multiple accelerator cores that typically do not have any cache. Each accelerator core, instead, has a small internal local memory. Our OpenCL runtime is based on software-managed caches and coherence protocols that guarantee OpenCL memory consistency to overcome the limited size of the local memory. To boost performance, the runtime relies on three source-code transformation techniques, work-item coalescing, web-based variable expansion and preload-poststore buffering, performed by our OpenCL C source-to-source translator. Work-item coalescing is a procedure to serialize multiple SPMD-like tasks that execute concurrently in the presence of barriers and to sequentially run them on a single accelerator core. It requires the web-based variable expansion technique to allocate local memory for private variables. Preload-poststore buffering is a buffering technique that eliminates the overhead of software cache accesses. Together with work-item coalescing, it has a synergistic effect on boosting performance. We show the effectiveness of our OpenCL framework, evaluating its performance with a system that consists of two Cell BE processors. The experimental result shows that our approach is promising.

Although Xen's isolated driver domain (IDD) model enables strong system isolation by limiting the impact of driver faults to the driver domain itself, it results in severe security problems when malware in a guest domain tries to abuse mobile device's limited system resources by sending an extreme number of I/O requests to the IDD. In order to solve this problem, this paper presents a fine-grained I/O access control mechanism in an IDD. Requests from guest domains are managed by an accounting module in terms of CPU usage, with the calculation of estimated CPU consumption using regression equations. The requests are scheduled by an I/O access control enforcer according to security policies. As a result, our mechanism provides precise control on the CPU usage of a guest domain due to I/O device access, and prevents compromised guest domains from CPU overuse, performance degradation, and battery drain. We have implemented a prototype of our approach considering both network and storage devices with a real smart phone (SGH-i780) that runs two para-virtualized Linux kernels on top of Secure Xen on ARM. The evaluation shows our approach effectively protects a smart phone against excessive I/O attacks and guarantees availability.

Although applications running on virtual machines, such as Java, can achieve platform independence, performance evaluation and analysis becomes difficult due to extra intermediate layers and the dynamic nature of virtual execution environment.

In this paper, we present a novel deployment-time binding selection framework for Web services to improve the performance. Using the information about target environments, we determine the best binding based on the availability and the accessibility of a service, and the performance characteristics of the bindings in a target environment. We have implemented the proposed mechanism as part of Eclipse-based development tools. We present an extensive performance evaluation of our methodology using benchmarks that we have created following public Web service interfaces, and emulating several e-business applications including a large scale legacy transaction processing system that runs on a mainframe.

This paper introduces a novel deployment time optimization (DTO) technology for Internet services. Using the configuration information collected from the target operation environment, the proposed optimization technology attempts to deploy only necessary and most performant components for a service in the target environment. To facilitate DTO, we have developed a framework called blue pencil, which consists of the following modules: configuration discovery module, optimization rule repository, deployment optimization module, proxy generation module, and code transformation module. We present how these modules enable DTO and show the performance benefit of DTP in a client-server binding selection scenario.

Conventional relaxed memory ordering techniques follow a proactive model: at a synchronization point, a processor makes its own updates to memory available to other processors by executing a memory barrier instruction, ensuring that recent writes have been ordered with respect to other processors in the system. We show that this model leads to superfluous memory barriers in programs with acquire-release style synchronization, and present a combined hardware/software synchronization mechanism called conditional memory ordering (CMO) that reduces memory ordering overhead. CMO is demonstrated on a lock algorithm that identifies those dynamic lock/unlock operations for which memory ordering is unnecessary, and speculatively omits the associated memory ordering instructions. When ordering is required, this algorithm relies on a hardware mechanism for initiating a memory ordering operation on another processor. Based on evaluation using a software-only CMO prototype, we show that CMO avoids memory ordering operations for the vast majority of dynamic acquire and release operations across a set of multithreaded Java workloads, leading to significant speedups for many. However, performance improvements in the software prototype are hindered by the high cost of remote memory ordering. Using empirical data, we construct an analytical model demonstrating the benefits of a combined hardware-software implementation

Calling context profiles are used in many inter-procedural code optimizations and in overall program understanding. Unfortunately, the collection of profile information is highly intrusive due to the high frequency of method calls in most applications. Previously proposed calling-context profiling mechanisms consequently suffer from either low accuracy, high overhead, or both. We have developed a new approach for building the calling context tree at runtime, called adaptive bursting. By selectively inhibiting redundant profiling, this approach dramatically reduces overhead while preserving profile accuracy. We first demonstrate the drawbacks of previously proposed calling context profiling mechanisms. We show that a low-overhead solution using sampled stack-walking alone is less than 50% accurate, based on degree of overlap with a complete calling-context tree. We also show that a static bursting approach collects a highly accurate profile, but causes an unacceptable application slowdown. Our adaptive solution achieves 85% degree of overlap and provides an 88% hot-edge coverage when using a 0.1 hot-edge threshold, while dramatically reducing overhead compared to the static bursting approach.

We present a new method for dynamically detecting potential data races in multithreaded programs. Our method improves on the state of the art in accuracy, in usability, and in overhead. We improve accuracy by combining previously known race detection techniques -- lockset-based detection and happens-before-based detection -- to obtain fewer false positives than lockset-based detection alone. We enhance usability by reporting more information about detected races than any previous dynamic detector. We reduce overhead compared to previous detectors -- particularly for large applications such as Web application servers -- by not relying on happens-before detection alone, by introducing a new optimization to discard redundant information, and by using a two phase approach to identify error-prone program points and then focus instrumentation on those points. We justify our claims by presenting the results of applying our tool to a range of Java programs, including the widely-used Web application servers Resin and Apache Tomcat. Our paper also presents a formalization of locksetbased and happens-before-based approaches in a common framework, allowing us to prove a folk theorem that happens-before detection reports fewer false positives than lockset-based detection (but can report more false negatives), and to prove that key optimizations are correct.

This article presents an escape analysis framework for Java to determine (1) if an object is not reachable after its method of creation returns, allowing the object to be allocated on the stack, and (2) if an object is reachable only from a single thread during its lifetime, allowing unnecessary synchronization operations on that object to be removed. We introduce a new program abstraction for escape analysis, the connection graph , that is used to establish reachability relationships between objects and object references. We show that the connection graph can be succinctly summarized for each method such that the same summary information may be used in different calling contexts without introducing imprecision into the analysis. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the nonescaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in the user code in three out of the ten benchmarks (with a median of 19%); 11% to 92% of all mutex lock operations are eliminated in those 10 programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333-MHz PowerPC workstation with 512 MB memory.

Consider a multi-threaded application that occasionally fails due to non-determinism. Using the DEJAVU capture/replay tool, it is possible to record the thread schedule and replay the application in a deterministic way. By systematically narrowing down the difference between a thread schedule that makes the program pass and another schedule that makes the program fail, the Delta Debugging approach can pinpoint the error location automatically---namely, the location(s) where a thread switch causes the program to fail. In a case study, Delta Debugging isolated the failure-inducing schedule difference from 3.8 billion differences in only 50 tests.

We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3x to 30x. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.

Development of multithreaded applications is particularly tricky because of their non-deterministic execution behaviors. Tools that support the debugging and performance timing of such applications are needed. Key to the construction of such tools is the ability to repeat the nondeterministic execution behavior of a multithreaded application. A clean separation between the application and the system that runs it facilitates supporting that ability. This paper presents a platform for constructing such tools in a context in which any separation between the application and the underlying system (and between both and the platform's own instrumentation code) has been obscured. DejaVu supports deterministic replay of nondeterministic executions of multithreaded Java programs on the Jalapeno virtual machine (running on a uniprocessor). Jalapeno is written in Java and its optimizing compiler regularly integrates application, virtual machine, and DejaVu instrumentation code into unified machine-code sequences. DejaVu ensures deterministic replay through symmetric instrumentation-side-effect identical instrumentation in both record and replay modes-and remote reflection which exposes the state of an application without perturbing it.

Execution behavior of a Java application can be nondeterministic due to concurrent threads of execution, thread scheduling, and variable network delays. This nondeterminism in Java makes the understanding and debugging of multi-threaded distributed Java applications a difficult and a laborious process. It is well accepted that providing deterministic replay of application execution is a key step towards programmer productivity and program under-standing. Towards this goal, we developed a replay framework based on logical thread schedules and logical intervals. An application of this framework was previously published in the context of a system called Deja Vu that provides deterministic replay of multi-threaded Java programs on a single Java Virtual Machine (JVM). In contrast, this paper focuses on distributed Deja Vu that provides deterministic replay of distributed Java applications running on multiple JVMs. We describe the issues and present the design, implementation and preliminary performance results of distributed Deja Vu that supports both multi-threaded and distributed Java applications.

Dynamic class loading during program execution in the Java Programming Language is an impediment for generating code that is as efficient as code generated using static whole-program analysis and optimization. Whole-program analysis and optimization is possible for languages, such as C++, that do not allow new classes and/or methods to be loaded during program execution. One solution for performing whole-program analysis and avoiding incorrect execution after a new class is loaded is to invalidate and recompile affected methods. Runtime invalidation and recompilation mechanisms can be expensive in both space and time, and, therefore, generally restrict optimization.

This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can be removed. We introduce a new program abstraction for escape analysis, the connection graph, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory.

The Factored Control Flow Graph, FCFG, is a novel representation of a program's intraprocedural control flow, which is designed to efficiently support the analysis of programs written in languages, such as Java, that have frequently occurring operations whose execution may result in exceptional control flow. The FCFG is more compact than traditional CFG representations for exceptional control flow, yet there is no loss of precision in using the FCFG. In this paper, we introduce the FCFG representation and outline how standard forward and backward data flow analysis algorithms can be adapted to work on this representation. We also present empirical measurements of FCFG sizes for a large number of methods obtained from a variety of Java programs, and compare these sizes with those of a traditional CFG representation.

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework for interprocedural pointer alias analysis that handles function pointers by constructing the program call graph while alias analysis is being performed; (2) a flow-sensitive interprocedural pointer alias analysis algorithm; (3) a flow-insensitive interprocedural pointer alias analysis algorithm; (4) a flow-insensitive interprocedural pointer alias analysis algorithm that incorporates kill information to improve precision; (5) empirical measurements of the efficiency and precision of the three interprocedural alias analysis algorithms.

This paper describes an algorithm for slicing class hierarchies in C++ programs. Given a C++ class hierarchy (a collection of C++ classes and inheritance relations among them) and a program P that uses the hierarchy, the algorithm eliminates from the hierarchy those data members, member functions, classes, and inheritance relations that are unnecessary for ensuring that the semantics of P is maintained.Class slicing is especially useful when the program P is generated from a larger program P' by a statement slicing algorithm. Such an algorithm eliminates statements that are irrelevant to a set of slicing criteria---program points of particular interest. There has been considerable previous work on statement slicing, and it will not be the concern of this paper. However, the combination of statement slicing and class slicing for C++ has two principal applications: First, class slicing can enhance statement slicing's utility in program debugging and understanding applications, by eliminating both executable and declarative program components irrelevant to the slicing criteria. Second, the combination of the two slicing algorithms can be used to decrease the space requirements of programs that do not use all the components of a class hierarchy. Such a situation is particularly common in programs that use class libraries.

Reducing communication cost is crucial to achieving good performance on scalable parallel machines. This paper presents a new compiler algorithm for global analysis and optimization of communication in data-parallel programs. Our algorithm is distinct from existing approaches in that rather than handling loop-nests and array references one by one, it considers all communication in a procedure and their interactions under different placements before making a final decision on the placement of any communication. It exploits the flexibility resulting from this advanced analysis to eliminate redundancy, reduce the number of messages, and reduce contention for cache and communication buffers, all in a unified framework. In contrast, single loop-nest analysis often retains redundant communication, and more aggressive dataflow analysis on array sections can generate too many messages or cache and buffer contention. The algorithm has been implemented in the IBM pHPF compiler for High Performance Fortran. During compilation, the number of messages per processor goes down by as much as a factor of nine for some HPF programs. We present performance results for the IBM SP2 and a network of Sparc workstations (NOW) connected by a Myrinet switch. In many cases, the communication cost is reduced by a factor of two.

A static program slice is an extract of a program which can help our understanding of the behavior of the program; it has been proposed for use in debugging, optimization, parallelization, and integration of programs. This article considers two types of static slices: executable and nonexecutable. Efficient and well-founded methods have been developed to construct executable slices for programs without goto statements; it would be tempting to assume these methods would apply as well in programs with arbitrary goto statements. We show why previous methods do not work in this more general setting, and describe our solutions that correctly and efficiently compute executable slices for programs even with arbitrary goto statements. Our conclusion is that goto statements can be accommodated in generating executable static slices.

Recent advances in languages, software design methodologies, and architecture have prompted the development of improved compile-time methods for analyzing the effects of procedure calls, pointer references, and array accesses. Such sophistication, however, generally implies that compilers and programming environments will experience a corresponding increase in the volume of analysis information, which may be difficult to use efficiently. In this paper, we consider the practical accommodation of such information. Our results show how to engineer a compiler such that its optimization phase takes time proportional to the benefit, rather than the size, of such information.>

We present practical approximation methods for computing interprocedural aliases and side effects for a program written in a language that includes pointers, reference parameters and recursion. We present the following results: 1) An algorithm for flow-sensitive interprocedural alias analysis which is more precise and efficient than the best interprocedural method known. 2) An extension of traditional flow-insensitive alias analysis which accommodates pointers and provides a framework for a family of algorithms which trade off precision for efficiency. 3) An algorithm which correctly computes side effects in the presence of pointers. Pointers cannot be correctly handled by conventional methods for side effect analysis. 4) An alias naming technique which handles dynamically allocated objects and guarantees the correctness of data-flow analysis. 5) A compact representation based on transitive reduction which does not result in a loss of precision and improves precision in some case. 6) A method for intraprocedural alias analysis which is based on a sparse representation.

One important issue in parallel program debugging is the efficient detection of access anomalies caused by uncoordinated accesses to shared variables.On-the-fly detection of access anomalies has two advantages over static analysis or post-mortem trace analysis.First, it reports only actual anomalies during execution.Second, it produces shorter traces for post-mortem analysis purposes if an anomaly is detected, since generating further trace information after the detection of an anomaly is of dubious value.Existing methods for on-the-fly access anomaly detection suffer from performance penalties since the execution of the program being debugged has to be interrupted on every access to shared variables.In this paper, we propose an efficient cachebased access anomaly detection scheme that piggybacks on the overhead already paid by the underlying cache coherence protocol.

In this paper, we present an algorithm that con-structs sparse evaluation graphs for forward or backward monotone data flow problems. The sparse graph combines information as early as possible, yet directly connects nodes that generate and use information. This allows problems from the large, general class of monotone data flow problems to err joy the advantages of solutions based on Static Single Assignment (SSA) form. 1

Races in describes a mechanism to debug unintended data races

Flowback analysis is a powerful technique for debugging programs.It allows the programmer to examine dynamic dependence in a program's execution history without having to reexecute the program.The goal is to present to the programmer a graphical view of the dynamic program dependence.We are building a system, called PPD, that performs flowback analysis while keeping the execution time overhead low.We also extend the semantics of flowback analysis to parallel programs.This paper describes details of the graphs and algorithms needed to implement efficient flowback analysis for parallel programs.Execution-time overhead is kept low by recording only a small amount of trace during a program's execution.We use semantic analysis and a technique called incremental tracing to keep the time and space overhead low.As part of the semantic analysis, PPD uses a static program dependence graph structure that reduces the amount of work done at compile time and takes advantage of the dynamic information produced during execution time.Parallel programs have been accommodated in two ways.First, the flowback dependence can span process boundaries; that is, the most recent modification to a variable might be traced to a different process than that one that contains the current reference.The static dynamic program dependence graphs of the individual processes are tied together with synchronization and data dependence information to form complete graphs that represent the entire program.Second, our algorithms will detect potential data-race conditions in the access to shared variables.The programmer can be directed to the cause of the race condition.PPD is currently being implemented for the C programming language on a Sequent Symmetry shared-memory .

Interactive debugging requires that the programmer be able to half a program at interesting points in its execution. The authors define distributed breakpoints and present an algorithm for implementing the detection points and an algorithm for halting a distributed program in a consistent state. Events that can be partially ordered are defined as detectable and form the basis for the breakpoint predicates. From the breakpoint definition, an algorithm is obtained that can be used in a distributed debugger to detect these breakpoints. The halting algorithm extends K.M. Chandy and L. Lamport's (1985) algorithm for recording global state and solves the problem of processes that are not fully connected or frequently communicating.>

This paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (SMMP). We describe the use of flowback analysis to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. We introduce a mechanism called incremental tracing that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. We extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.