Recent desktop and mobile processors often integrate CPU and GPU onto the same die. The limited memory bandwidth of these integrated architectures can negatively affect the performance of data-parallel workloads when all computational resources are active. The combination of active CPU and GPU cores achieving the maximum performance depends on a workload's characteristics, making manual tuning a time-consuming task. Dopia is a fully automated framework that improves the performance of data-parallel workloads by adjusting the Degree Of Parallelism on Integrated Architectures. Dopia transparently analyzes and rewrites OpenCL kernels before executing them with the number of CPU and GPU cores expected to yield the best performance. Evaluated on AMD and Intel integrated processors, Dopia achieves 84% of the maximum performance attainable by an oracle.

When digital applications aim to blend virtual and real worlds, understanding the actual physical actions of users becomes an important task; the precise timing of these tangible interaction events is needed, along with the identity, and possibly location and history, of all involved actors/objects. With multiple actors or objects, it is difficult to identify who touches which object and when. Instrumenting objects for Body Channel Communication (BCC) allows message exchange around the human body between instrumented objects and the user themselves. In this paper we show how BCC can be utilized to perform under real-time conditions so that we can directly notice touch events (and the identity of actors). TangibleID is a framework that unifies tangible interaction capture for objects and users based on wearable BCC. TangibleID provides identification and communication with tagged objects/users in less than 120 ms and supports a variety of tangible interactions, without the need to restrict user (hand) movements or to maintain line-of-sight connection to cameras. When an AR application is combined with TangibleID, a new tangible mixed reality experience is achieved, as demonstrated in the “Haunted Castle” showcase. The paper presents an end-to-end technical evaluation including trade-offs regarding robustness and speed of touch recognition, outlines the breadth of interaction modalities, and reports on an initial user assessment.

Dynamic scheduling and dynamic creation of the pipeline structure are crucial for efficient execution of pipelined programs. Nevertheless, dynamic systems imply higher overhead than static systems. Therefore, chunking is the key to decrease the synchronization and scheduling overhead by grouping activities. We present a chunking algorithm for dynamic systems that handles dynamic linear pipelines, which allow the number and duration of stages to be determined at run-time. The evaluation on 44 cores shows that chunking brings the overhead of dynamic scheduling down to that of a static scheduler, and it enables efficient and scalable execution of fine-grained dynamic linear pipelines.

Today's hardware is increasingly parallel, and to increase performance, applications must be able to use this parallelism. Hence, programming languages must provide the means for parallel execution. The language Python offers a multithreading, shared-memory model for concurrency. However, simultaneous execution of threads, i.e., parallel execution, is not a standard feature of current virtual machines (VM) for Python. Instead, the predominant Python VMs depend on a global interpreter lock, which serializes the execution.

Open nesting allows replacing the automatic detection of conflicting memory accesses used in transactional memory (TM) with programmer-specified higher-level conflict detection. Higher-level conflict detection allows removing conflicts of commuting operations where the automatic conflict detection is too conservative. Different conflict detection schemes are incompatible with each other and thus must operate on separate memory locations to prevent inconsistencies. Using open nesting, a programmer implements this separation manually using source code modifications possibly assisted by static checks.

Software transactional memory (STM) stores information regarding ownership of memory locations in ownership records. We present a scheme to realize a one-to-one mapping of ownership records to memory locations that has moderate memory overhead and is suitable for STM implementations on top of managed runtimes.

Pipelining is a well-known technique to overlap loop iterations by partitioning the loop body into a sequence of stages. A large class of programs can be expressed as linear pipelines if data dependences only flow from earlier to later stages. Various pipelining techniques have been explored but reconciling load-balancing and efficient execution is still a challenge for two main reasons. First, partitioning of the loop body into stages that lead to load-balancing may depend on the data set as well as system properties, e.g., number of cores. Second, the configuration of the runtime system is far from obvious. In this article, we present Pipelight , a technique that achieves load-balancing for linear pipelines. Pipelight relies on a way of mapping stages onto threads that simplifies partitioning and enables the design of a lightweight algorithm for dynamic scheduling. Furthermore, Pipelight introduces a concurrent data structure that exploits the properties of data dependences presented in linear pipelines to provide efficient communication and synchronization. This data structure simplifies the configuration of the runtime system and makes Pipelight a practical solution. The evaluation on a 44-core system shows the efficiency of Pipelight for a set of programs selected from widely-used collections. Although Pipelight simplifies parallelization of linear pipelines, it performs similarly to the most efficient properly configured state-of-the-art technique. The price paid for the benefits of Pipelight is additional overhead for fine-grained loops. However, this overhead can be amortized successfully with chunking. To make Pipelight a promising solution, we propose a directive-based transformation for Pipelight , which is developed in a prototype source-to-source compiler. Consequently, Pipelight is an efficient and practical solution to achieve load-balancing for fine-grained linear pipelines.

We present Pipelite , a dynamic scheduler that exploits the properties of dynamic linear pipelines to achieve high performance for fine-grained workloads. The flexibility of Pipelite allows the stages and their data dependences to be determined at runtime. Pipelite unifies communication, scheduling, and synchronization algorithms with suitable data structures. This unified design introduces the local suspension mechanism and a wait-free enqueue operation, which allow efficient dynamic scheduling. The evaluation on a 44-core machine, using programs from three widely used benchmark suites, shows that Pipelite implies low overhead and significantly outperforms the state of the art in terms of speedup, scalability, and memory usage.

Integrating CPUs and GPUs on the same die provides new opportunities for optimization, especially for irregular data-parallel workloads that fail to fully exploit the computational power of the GPU. Such workloads benefit from a proper partitioning between the CPU and the GPU. This paper presents an on-the-fly workload partitioning technique for irregular workloads on integrated architectures. Unlike existing work, no prior analysis of the workload is required. GPU kernels and input data are analyzed and optimized at runtime. The technique executes work chunks of similar load on the GPU and assigns irregular chunks to the CPU. Evaluated with various irregular workloads, the method achieves a 1.4x--7.1x speedup over GPU execution on AMD and Intel processors.

Software often suffers from performance bottlenecks, e.g., because some code has a higher computational complexity than expected or because a code change introduces a performance regression. Finding such bottlenecks is challenging for developers and for profiling techniques because both rely on performance tests to execute the software, which are often not available in practice. This paper presents PerfSyn, an approach for synthesizing test programs that expose performance bottlenecks in a given method under test. The basic idea is to repeatedly mutate a program that uses the method to systematically increase the amount of work done by the method. We formulate the problem of synthesizing a bottleneck-exposing program as a combinatorial search and show that it can be effectively and efficiently addressed using well known graph search algorithms. We evaluate the approach with 147 methods from seven Java code bases. PerfSyn automatically synthesizes test programs that expose 22 bottlenecks. The bottlenecks are due to unexpectedly high computational complexity and due to performance differences between different versions of the same code.

Novel interactions that capacitively couple electromagnetic (EM) fields between devices and the human body are gaining more attention in the human-computer interaction community. One class of these techniques is Body Channel Communication (BCC), a method that overlays physical touch with digital information. Despite the number of published capacitive sensing and communication prototypes, there exists no guideline on how to design such hardware or what are the application limitations and possibilities. Specifically, wearable (groundless) BCC has been proven in the past to be extremely challenging to implement. Additionally, the exact behavior of the human body as an EM-field medium is still not fully understood today. Consequently, the application domain of BCC technology could not be fully explored. This paper addresses this problem. Based on a recently published general purpose wearable BCC system, we first present a thorough evaluation of the impact of various technical parameter choices and an exhaustive channel characterization of the human body as a host for BCC. Second, we discuss the implications of these results for the application design space and present guidelines for future wearable BCC systems and their applications. Third, we point out an important observation of the measurements, namely that BCC can employ the whole body as user interface (and not just hands or feet). We sketch several applications with these novel interaction modalities.

Object-oriented Programming has been effective in reducing code complexity in sequential programs, but in current practice, concurrent programs still present a number of challenges. We present here a model of object-oriented programming that identifies concurrent tasks and the relationship between objects and tasks , effectively making objects concurrency-aware . This awareness is formalized in a parallel programming model where every object plays a role in every task (e.g., the readonly role). When an object is shared with a new task, it adapts to the new sharing pattern by changing its roles, and therefore its behavior, i.e., the operations that can be performed with this object. This mechanism can be leveraged to prevent interfering accesses from concurrently executing tasks, and therefore makes parallel execution deterministic. To this end, we present a role-based programming language that includes several novel concepts (role transitions, guarding, slicing) to enable practical, object-oriented deterministic parallel programming. We show that this language can be used to safely implement programs with a range of different parallel patterns. The implementations to 8 widely used programming problems achieve substantial parallel speedups and demonstrate that this approach delivers performance roughly on par with manually synchronized implementations.

To leverage the benefits of modern hardware, dynamic languages must support parallelism, and parallelism requires a virtual machine (VM) capable of parallel execution — a parallel VM. However, unrestricted concurrency and the dynamism of dynamic languages pose great challenges to the implementation of parallel VMs. In a dynamic language, a program changing itself is part of the language model. To help the VM, languages often choose memory models (MM) that weaken consistency guarantees. With lesser guarantees, local program state cannot be affected by every concurrent state change. And less interference allows a VM to make local assumptions about the program state which are not immediately violated. These local assumptions are essential for a VM’s just-in-time compiler for delivering state-of-the-art VM performance. Unfortunately, some dynamic languages employ MMs that give exceedingly strong consistency guarantees and thereby hinder the development of parallel VMs. Such is the case in particular for languages that depend on a global interpreter lock, which mandates a MM with sequential consistency and instruction atomicity. In this paper, we reflect on a first implementation of the Parallel RPython execution model, which facilitates the development of parallel VMs by decoupling language semantics from the synchronization mechanism used within the VM. The implementation addresses the challenges imposed by strong MMs through strict isolation of concurrent computations. This isolation builds on transactional parallel worlds, which are implemented with a novel combination of software techniques and the capabilities of modern hardware. We evaluate a set of parallel Python programs on a parallel VM that relies on Parallel RPython’s implementation. Compared with a serial baseline VM that relies on a global interpreter lock, the parallel VM achieves speedups of up to 7.5× on 8 CPU cores. The evaluation shows that our realization of Parallel RPython meets the challenges of dynamic languages, and that it can serve as a solid foundation for the construction of parallel dynamic language VMs.

During the past decade, network and storage devices have undergone rapid performance improvements, delivering ultra-low latency and several Gbps of bandwidth. Nevertheless, current network and storage stacks fail to deliver this hardware performance to the applications, often due to the loss of I/O efficiency from stalled CPU performance. While many efforts attempt to address this issue solely on either the network or the storage stack, achieving high-performance for networked-storage applications requires a holistic approach that considers both. In this article, we present FlashNet, a software I/O stack that unifies high-performance network properties with flash storage access and management. FlashNet builds on RDMA principles and abstractions to provide a direct, asynchronous, end-to-end data path between a client and remote flash storage. The key insight behind FlashNet is to co-design the stack’s components (an RDMA controller, a flash controller, and a file system) to enable cross-stack optimizations and maximize I/O efficiency. In micro-benchmarks, FlashNet improves 4kB network I/O operations per second (IOPS by 38.6% to 1.22M, decreases access latency by 43.5% to 50.4μs, and prolongs the flash lifetime by 1.6-5.9× for writes. We illustrate the capabilities of FlashNet by building a Key-Value store and porting a distributed data store that uses RDMA on it. The use of FlashNet’s RDMA API improves the performance of KV store by 2× and requires minimum changes for the ported data store to access remote flash devices.

Pipelining allows the execution of loop iterations with cross-iteration dependences to overlap in time, provided that the loop body is partitioned into stages such that the data dependences are not violated. Then, the stages are mapped onto threads and communication and synchronization between stages is typically achieved using queues. Pipelining techniques that rely on static scheduling perform poorly for load-imbalanced loops. Moreover, previous research efforts that achieve load-balancing are restricted to work-stealing and imply high overhead for fine-grained loops. In this article, we present URTS, a unified runtime system with compiler support that provides a lightweight dynamic scheduler by combining mapping, communication and synchronization algorithms with a suitable data structure and an efficient ticket mechanism. Particularly, URTS shows that it is possible to combine the efficiency of static scheduling with the load-imbalance tolerance of work-stealing by using a unified design that exploits the properties of a novel data structure. The evaluation on 8- and 32-core machines shows that URTS implies low overhead, of the same order as a static scheduler, for a set of benchmarks chosen from widely-used collections. URTS is a scalable solution that performs efficient dynamic scheduling for fine-grained loops, i.e., a class of interesting loops that is poorly handled by the state-of-the-art due to high overhead.

We explore a programming approach for concurrency that synchronizes all accesses to shared memory by default. Synchronization takes place by ensuring that all program code runs inside atomic sections even if the program code has external side effects. Threads are mapped to atomic sections that a programmer must explicitly split to increase concurrency.

During the past decade, network and storage devices have undergone rapid performance improvements, delivering ultra-low latency and several Gbps of bandwidth. Nevertheless, current network and storage stacks fail to deliver this hardware performance to the applications, often due to the loss of IO efficiency from stalled CPU performance. While many efforts attempt to address this issue solely on either the network or the storage stack, achieving high-performance for networked-storage applications requires a holistic approach that considers both.

The RPython framework takes an interpreter for a dynamic language as its input and produces a Virtual Machine (VM) for that language. RPython is being used to develop PyPy, a high-performance Python interpreter. However, the produced VM does not support parallel execution since the framework relies on a Global Interpreter Lock (GIL): PyPy serialises the execution of multi-threaded Python programs.

Some loops with cross-iteration dependences can execute in parallel by pipelining. The loop body is partitioned into stages such that the data dependences are not violated and then the stages are mapped onto threads. Two well-known mapping techniques are fixed code and fixed data; they achieve high performance for load-balanced loops, but they fail to perform well for load-imbalanced loops. In this article, we present a novel hybrid mapping that eliminates drawbacks of both prior mapping techniques and enables dynamic scheduling of stages.

The Internet of Things (IoT) envisions that many devices can connect to a network. Visible Light Communication (VLC) based on Light Emitting Diodes (LEDs) is an attractive communication fabric for the IoT, as LEDs are readily available and can serve as transmitters as well as receivers. LED light bulbs, enhanced with photodiodes, provide an attractive path to extend device-to-device communication to room area networking. This paper describes a VLC system, called EnLighting, based on light bulbs that support an embedded Linux version (and its complete networking stack). These programmable light bulbs can both send and receive; they can communicate with objects in a room as well as with other light bulbs nearby. Bidirectional communication allows a light bulb to actively participate in networking and simplifies deployment, maintenance, configuration, and controllability of indoor lighting installations and services. EnLighting supports low-bandwidth communication services in a room (and via a gateway, beyond the room), which provide the base for other applications, e.g., a location service. This paper includes an initial evaluation of a room area communication and localization network based on prototype Linux-enabled light bulbs, reporting the performance for different network traffic types, and shows the benefits obtained from bidirectional communication. This proof-of- concept system illustrates that simple devices can provide an attractive solution to future communication challenges in the saturated radio spectrum.

Wireless communication remains to be the most efficient way of providing access to information to users in developing economies. We are interested in Delay-Tolerant Networks (DTNs) for distributing multimedia content to micro-entrepreneurs in under-served rural areas of South Africa. In our project, public commuter buses carrying WLAN-enabled devices (mobile infostations) that provide DTN connectivity are used to ferry data between urban and rural areas. Before the actual deployment in the field, rigorous lab experiments have been performed to study the performance of the proposed network design. Such an activity is time consuming and requires arduous preparation. Simulators, while convenient, do not provide the most realistic results. Given the complexity of DTN testing, we try to find a middle ground approach by building a mobility emulator testbed, which we use to emulate the network scenario. In this paper, we outline the design and implementation details of the network emulator. We then describe the experiments that were performed to study the impact of different network dynamics on content delivery, and their results. The results from the experiments are used to improve our current network design.

Distributed DRAM stores have become an attractive option for providing fast data accesses to analytics applications. To accelerate the performance of these stores, researchers have proposed using RDMA technology. RDMA offers high bandwidth and low latency data access by carefully separating resource setup from IO operations, and making IO operations fast by using rich network semantics and offloading. Despite recent interest, leveraging the full potential of RDMA in a distributed environment remains a challenging task. In this paper, we present RDMA Store or RStore, a DRAM-based data store that delivers high performance by extending RDMA's separation philosophy to a distributed setting. RStore achieves high aggregate bandwidth (705 Gb/s) and close-to-hardware latency on our 12-machine testbed. We developed a distributed graph processing framework and a Key-Value sorter using RStore's unique memory-like API. The graph processing framework, which relies on RStore for low-latency graph access, outperforms state-of-the-art systems by margins of 2.6 -- 4.2× when calculating Page Rank. The Key-Value sorter can sort 256 GB of data in 31.7 sec, which is 8× better than Hadoop TeraSort in a similar setting.

We investigate the applicability of IEEE 802.11ac for entertainment low-latency show control systems (to orchestrate free-riding vehicles in a theme-park environment) by experimentally characterizing the indoor throughput and jitter performance of 802.11ac using statistical analysis. 802.11ac is the successor of 802.11n that provides higher throughput by incorporating wider channels, more spatial streams and denser modulation. We show that multiple linear regression provides valuable insight in the influence of 802.11ac's independent features and their combinations on performance, for various links and interference scenarios. Finally, we show that 802.11ac could be used for not only delivering high throughput for multimedia streaming but also supports applications requiring minimal jitter variance in the setup investigated.

The TouchCom project aims to gain a thorough understanding of the transmission channel and to implement higher layer protocols to support Human-Computer Interaction applications and multi-hop body-to-body communication. Finally, we built a prototype of a transmitter and receiver device to demonstrate a real life application.

The Internet of Things (IoT) will connect not only Zigbee-enabled devices but also Wi-Fi-enabled consumer electronics, given the recent rise of IPv6. We developed a power saving communication protocol for low-complexity IPv6-connected devices that can support multiple applications. We demonstrate here in an entertainment-related application scenario how to use that protocol to bring what we refer to as the Internet of Toys to life (Fig. 1).

Performance bugs are a prevalent problem and recent research proposes various techniques to identify such bugs. This paper addresses a kind of performance problem that often is easy to address but difficult to identify: redundant computations that may be avoided by reusing already computed results for particular inputs, a technique called memoization. To help developers find and use memoization opportunities, we present MemoizeIt, a dynamic analysis that identifies methods that repeatedly perform the same computation. The key idea is to compare inputs and outputs of method calls in a scalable yet precise way. To avoid the overhead of comparing objects at all method invocations in detail, MemoizeIt first compares objects without following any references and iteratively increases the depth of exploration while shrinking the set of considered methods. After each iteration, the approach ignores methods that cannot benefit from memoization, allowing it to analyze calls to the remaining methods in more detail. For every memoization opportunity that MemoizeIt detects, it provides hints on how to implement memoization, making it easy for the developer to fix the performance issue. Applying MemoizeIt to eleven real-world Java programs reveals nine profitable memoization opportunities, most of which are missed by traditional CPU time profilers, conservative compiler optimizations, and other existing approaches for finding performance bugs. Adding memoization as proposed by MemoizeIt leads to statistically significant speedups by factors between 1.04x and 12.93x.

Many recent multiprocessor systems are realized with a non-uniform memory architecture (NUMA) and accesses to remote memory locations take more time than local memory accesses. Optimizing NUMA memory system performance is difficult and costly for three principal reasons: (1) today's programming languages/libraries have no explicit support for NUMA systems, (2) NUMA optimizations are not~portable, and (3) optimizations are not~composable (i.e., they can become ineffective or worsen performance in environments that support composable parallel software). This paper presents TBB-NUMA, a parallel programming library based on Intel Threading Building Blocks (TBB) that supports portable and composable NUMA-aware programming. TBB-NUMA provides a model of task affinity that captures a programmer's insights on mapping tasks to resources. NUMA-awareness affects all layers of the library (i.e., resource management, task scheduling, and high-level parallel algorithm templates) and requires close coupling between all these layers. Optimizations implemented with TBB-NUMA (for a set of standard benchmark programs) result in up to 44% performance improvement over standard TBB, but more important, optimized programs are portable across different NUMA architectures and preserve data locality also when composed with other parallel computations.

DMA-capable interconnects, providing ultra-low latency and high bandwidth, are increasingly being used in the context of distributed storage and data processing systems. However, the deployment of such systems in virtualized data centers is currently inhibited by the lack of a flexible and high-performance virtualization solution for RDMA network interfaces.

Raising the level of abstraction is a key concern of software engineering, and libraries (either used directly or as a target of a program generation system) are a successful technique to raise programmer productivity and to improve software quality. Unfortunately successful libraries may contain functions that may not be general enough. For example, many numeric performance libraries contain functions that work on one- or higher-dimensional arrays. A problem arises if a program wants to invoke such a function on a non-contiguous subarray (e.g., in C the column of a matrix or a subarray of an image). If the library developer did not foresee this scenario, the client program must include explicit copy steps before and after the library function call, incurring a possibly high performance penalty. A better solution would be an enhanced library function that allows for the desired access pattern. Exposing the access pattern allows the compiler to optimize for the intended usage scenario(s). As we do not want the library developer to generate all interesting versions manually, we present a tool that takes a library function written in C and generates such a customized function for typical accesses. We describe the approach, discuss limitations, and report on the performance. As example access patterns we consider those most common in numerical applications: striding and block striding, general permutations, as well as scaling. We evaluate the tool on various library functions including filters, scans, reductions, sorting, FFTs, and linear algebra operations. The automatically generated custom version is in most cases significantly faster than using individual steps, offering speed-ups that are typically in the range of 1.2-1.8x.

Developers of thread-safe classes struggle with two opposing goals. The class must be correct, which requires synchronizing concurrent accesses, and the class should provide reasonable performance, which is difficult to realize in the presence of unnecessary synchronization. Validating the performance of a thread-safe class is challenging because it requires diverse workloads that use the class, because existing performance analysis techniques focus on individual bottleneck methods, and because reliably measuring the performance of concurrent executions is difficult. This paper presents SpeedGun, an automatic performance regression testing technique for thread-safe classes. The key idea is to generate multi-threaded performance tests and to compare two versions of a class with each other. The analysis notifies developers when changing a thread-safe class significantly influences the performance of clients of this class. An evaluation with 113 pairs of classes from popular Java projects shows that the analysis effectively identifies 13 performance differences, including performance regressions that the respective developers were not aware of.

Wireless Local Area Networks (WLANs) based on the IEEE 802.11 standard apply a simple contention-based radio access protocol. Downlink communication from access points to mobile stations shares the radio channel with uplink communication from mobile stations to the access points. This protocol is due to the contention-based design that targets the operation in unlicensed spectrum. In the future, because of the growing demand for wireless communication services, WLANs might not only operate in unlicensed but also in licensed spectrum. However, licensed spectrum favors the use of separate (paired) radio channels for downlink and uplink communication - a setup that requires frequency-division-duplex communication. This paper describes and evaluates the feasibility of a WLAN system operating in paired spectrum with a proof of concept implementation. Our testbed employs off-the-shelf WLAN chips (two per device) and driver modifications that enable the system to operate with downlink-uplink separation while still maintaining the ability to function in unlicensed (single-channel) spectrum. We provide insights based on our testbed and evaluate the performance of our solution.

The performance of large-scale data-intensive applications running on thousands of machines depends considerably on the performance of the network. To deliver better application performance on rapidly evolving high-bandwidth, low-latency interconnects, researchers have proposed the use of network accelerator devices. However, despite the initial enthusiasm, translating network accelerator's capabilities into high application performance remains a challenging issue.

In this paper we propose a novel method to compress video content based on image retargeting. First, a saliency map is extracted from the video frames either automatically or according to user input. Next, nonlinear image scaling is performed which assigns a higher pixel count to salient image regions and fewer pixels to non-salient regions. The non-linearly downscaled images can then be compressed using existing compression techniques and decoded and upscaled at the receiver. To this end we introduce a non-uniform antialiasing technique that significantly improves the image resampling quality. The overall process is complementary to existing compression methods and can be seamlessly incorporated into existing pipelines. We compare our method to JPEG 2000 and H.264/AVC-10 and show that, at the cost of visual quality in non-salient image regions, our method achieves a significant improvement of the visual quality of salient image regions in terms of Structural Similarity (SSIM) and Peak Signal-to-Noise-Ratio (PSNR) quality measures, in particular for scenarios with high compression ratios.

Languages with inheritance and polymorphism assume that a subclass instance can substitute a superclass instance without causing behavioral differences for clients of the superclass. However, programmers may accidentally create subclasses that are semantically incompatible with their superclasses. Such subclasses lead to bugs, because a programmer may assign a subclass instance to a superclass reference. This paper presents an automatic testing technique to reveal subclasses that cannot safely substitute their superclasses. The key idea is to generate generic tests that analyze the behavior of both the subclass and its superclass. If using the subclass leads to behavior that cannot occur with the superclass, the analysis reports a warning. We find a high percentage of widely used Java classes, including classes from JBoss, Eclipse, and Apache Commons Collections, to be unsafe substitutes for their superclasses: 30% of these classes lead to crashes, and even more have other behavioral differences.

Visible Light Communication (VLC) with Light Emitting Diodes (LEDs) as transmitters and receivers enables low bitrate wireless adhoc networking. LED-to-LED VLC adhoc networks with VLC devices communicating with each other over free-space optical links typically achieve a throughput of less than a megabit per second at distances of no more than a few meters. LED-to-LED VLC adhoc networks are useful for combining a smart illumination with low-cost networking. We present and evaluate a software-based VLC physical layer and a VLC medium access control layer that retain the simplicity of the LED-to-LED approach. The design satisfies the requirement that LEDs should always be perceived as on with constant brightness. In each VLC device, in addition to an LED, only a low-cost microcontroller is required for handling the software-based communication protocol. The results of our performance measurements confirm recent claims about the potential of LED-to-LED VLC adhoc networks as a useful technology for sensor networks, smart and connected consumer devices, and the Internet-of-Things.

The performance of parallel code significantly depends on the parallel task granularity (PTG). If the PTG is too coarse, performance suffers due to load imbalance; if the PTG is too fine, performance suffers from the overhead that is induced by parallel task creation and scheduling.

Software updates are the current standard to respond to software bugs. The software developer provides an update fix that is then applied by the administrator: the binary is modified and the service is restarted. Restarting a service inevitably leads to downtime and service unavailability; in the case of a multithreaded installation of Apache, restart takes several seconds and depending on the load of the web server, several hundred or even thousand client requests will be rejected with an error. Given the cost of restarts, system administrators attempt to minimize the frequency of service restarts or postpone a restart until the next maintenance window. However, to ensure the integrity of the system, code repair must happen as soon as possible (ASAP). We describe here the effectiveness of an on-the-fly update system that provides ASAP repair by integrating dynamic patches with a sandbox based on dynamic binary translation. To investigate the feasibility of ASAP code repair, we analyze the software updates released for Apache 2.2 between Dec 1st, 2005 and Feb 18, 2013. The study shows that such a system allows patching 45 of 49 bugs at runtime. Of the 4 unpatchable bugs, 1 bug is not applicable to dynamic update mechanisms, and 3 bugs require a restart. Furthermore, a performance evaluation of the prototype implementation shows that our approach adds low execution overhead (below 7% for different configurations that request a 287kB file).

The steps of accessing, storing, and transmitting "Big Data" raise many interesting problems. But big data sets also amplify any system or software inefficiencies when large data sets require processing. So the efficiency of the generate code (and the runtime system) is crucial if we want to see widespread use of applications based on big data.

When calling a method that requires multiple arguments, programmers must pass the arguments in the expected order. For statically typed languages, the compiler helps programmers by checking that the type of each argument matches the type of the formal parameter. Unfortunately, types are futile for methods with multiple parameters of the same type. How can a programmer check that equally typed arguments are passed in the correct order? This paper presents two simple, yet effective, static program analyses that detect problems related to the order of equally typed arguments. The key idea is to leverage identifier names to infer the semantics of arguments and their intended positions. The analyses reveal problems that affect the correctness, understandability, and maintainability of a program, such as accidentally reversed arguments and misleading parameter names. Most parts of the analyses are language-agnostic. We evaluate the approach with 24 real-world programs written in Java and C. Our results show the analyses to be effective and efficient. One analysis reveals anomalies in the order of equally typed arguments; it finds 54 relevant problems with a precision of 82 percent. The other analysis warns about misleading parameter names and finds 31 naming bugs with a precision of 39 percent.

Many recent multicore multiprocessors are based on a nonuniform memory architecture (NUMA). A mismatch between the data access patterns of programs and the mapping of data to memory incurs a high overhead, as remote accesses have higher latency and lower throughput than local accesses. This paper reports on a limit study that shows that many scientific loop-parallel programs include multiple, mutually incompatible data access patterns, therefore these programs encounter a high fraction of costly remote memory accesses. Matching the data distribution of a program to the individual data access patterns is possible, however it is difficult to find a data distribution that matches all access patterns.

Testing multithreaded code is hard and expensive. A multithreaded unit test creates two or more threads, each executing one or more methods on shared objects of the class under test. Such unit tests can be generated at random, but basic random generation produces tests that are either slow or do not trigger concurrency bugs. Worse, such tests have many false alarms, which require human effort to filter out. We present Ballerina, a novel technique for automated random generation of efficient multithreaded tests that effectively trigger concurrency bugs. Ballerina makes tests efficient by having only two threads, each executing a single, randomly selected method. Ballerina increases chances that such simple parallel code finds bugs by appending it to more complex, randomly generated sequential code. We also propose a clustering technique to reduce the manual effort in inspecting failures of automatically generated multithreaded tests. We evaluate Ballerina on 14 real-world bugs from six popular codebases: Groovy, JDK, JFreeChart, Apache Log4j, Apache Lucene, and Apache Pool. The experiments show that tests generated by Ballerina find bugs on average 2×-10× faster than basic random generation, and our clustering technique reduces the number of inspected failures on average 4×-8×. Using Ballerina, we found three previously unknown bugs, two of which were already confirmed and fixed.

Mining specifications and using them for bug detection is a promising way to reveal bugs in programs. Existing approaches suffer from two problems. First, dynamic specification miners require input that drives a program to generate common usage patterns. Second, existing approaches report false positives, that is, spurious warnings that mislead developers and reduce the practicability of the approach. We present a novel technique for dynamically mining and checking specifications without relying on existing input to drive a program and without reporting false positives. Our technique leverages automatically generated tests in two ways: Passing tests drive the program during specification mining, and failing test executions are checked against the mined specifications. The output are warnings that show with concrete test cases how the program violates commonly accepted specifications. Our implementation reports no false positives and 54 true positives in ten well-tested Java programs.

Programmers using an API often must follow protocols that specify when it is legal to call particular methods. Several techniques have been proposed to find violations of such protocols based on mined specifications. However, existing techniques either focus on single-object protocols or on particular kinds of bugs, such as missing method calls. There is no practical technique to find multi-object protocol bugs without a priori known specifications. In this paper, we combine a dynamic analysis that infers multi-object protocols and a static checker of API usage constraints into a fully automatic protocol conformance checker. The combined system statically detects illegal uses of an API without human-written specifications. Our approach finds 41 bugs and code smells in mature, real-world Java programs with a true positive rate of 51%. Furthermore, we show that the analysis reveals bugs not found by state of the art approaches.

To avoid receiving incorrect arguments, a method specifies the expected type of each formal parameter. However, some parameter types are too general and have subtypes that the method does not expect as actual argument types. For example, this may happen if there is no common supertype that precisely describes all expected types. As a result of such brittle parameter typing, a caller may accidentally pass arguments unexpected by the callee without any warnings from the type system. This paper presents a fully automatic, static analysis to find brittle parameter typing and unexpected arguments given to brittle parameters. First, the analysis infers from callers of a method the types that arguments commonly have. Then, the analysis reports potentially unexpected arguments that stand out by having an unusual type. We apply the approach to 21 real-world Java programs that use the Swing API, an API providing various methods with brittle parameters. The analysis reveals 15 previously unknown bugs and code smells where programmers pass arguments that are compatible with the declared parameter type but nevertheless unexpected by the callee. The warnings reported by the analysis have 47% precision and 83% recall.

Concurrent, object-oriented programs often use thread-safe library classes. Existing techniques for testing a thread-safe class either rely on tests using the class, on formal specifications, or on both. Unfortunately, these techniques often are not fully automatic as they involve the user in analyzing the output. This paper presents an automatic testing technique that reveals concurrency bugs in supposedly thread-safe classes. The analysis requires as input only the class under test and reports only true positives. The key idea is to generate tests in which multiple threads call methods on a shared instance of the tested class. If a concurrent test exhibits an exception or a deadlock that cannot be triggered in any linearized execution of the test, the analysis reports a thread safety violation. The approach is easily applicable, because it is independent of hand-written tests and explicit specifications. The analysis finds 15 concurrency bugs in popular Java libraries, including two previously unknown bugs in the Java standard library.

Object-oriented programming languages like Java provide only low-level constructs (e.g., starting a thread) to describe concurrency. High-level abstractions (e.g., thread pools) are merely provided as a library. As a result, a compiler is not aware of the high-level semantics of a parallel library and therefore misses important optimization opportunities. This paper presents a simple source language extension based on which a compiler is provided with the opportunity to perform new optimizations that are particularly effective for parallel code.

The standard loader (ld.so) is a common target of attacks. The loader is a trusted component of the application, and faults in the loader are problematic, e.g., they may lead to local privilege escalation for SUID binaries. Software-based fault isolation (SFI) provides a framework to execute arbitrary code while protecting the host system. A problem of current approaches to SFI is that fault isolation is decoupled from the dynamic loader, which is treated as a black box. The sandbox has no information about the (expected) execution behavior of the application and the connections between different shared objects. As a consequence, SFI is limited in its ability to identify devious application behavior. This paper presents a new approach to run untrusted code in a user-space sandbox. The approach replaces the standard loader with a security-aware trusted loader. The secure loader and the sandbox together cooperate to allow controlled execution of untrusted programs. A secure loader makes security a first class concept and ensures that the SFI system does not allow any unchecked code to be executed. The user-space sandbox builds on the secure loader and subsequently dynamically checks for malicious code and ensures that all control flow instructions of the application adhere to an execution model. The combination of the secure loader and the user-space sandbox enables the safe execution of untrusted code in user-space. Code injection attacks are stopped before any unintended code is executed. Furthermore, additional information provided by the loader can be used to support additional security properties, e.g., in lining of Procedure Linkage Table calls reduces the number of indirect control flow transfers and therefore limits jump-oriented attacks. This approach implements a secure platform for privileged applications and applications reachable over the network that anticipates and confines security threats from the beginning.

Time Of Check To Time Of Use (TOCTTOU) race conditions for file accesses in user-space applications are a common problem in Unix-like systems. The mapping between filename and inode and device is volatile and can provide the necessary preconditions for an exploit. Applications use filenames as the primary attribute to identify files but the mapping between filenames and inode and device can be changed by an attacker.

Java was designed as a secure language that supports running untrusted code as part of trusted applications. For safety reasons, Java therefore defines a memory model that prevents undefined behavior in multi-threaded programs even if the programs are not correctly synchronized. Because of the potential negative performance impact the Java designers did not choose a simple and natural memory model, such as sequential consistency, but instead developed a relaxed memory model that gives the compiler more optimization opportunities. As it is today, however, the relaxed Java Memory Model is not only hard to understand but it unnecessarily complicates reasoning about parallel programs and it turned out to be difficult to implement correctly. This paper presents an optimizing compiler for a Java version that has sequential consistency as its memory model. Based on a programming model with explicit happens-before constraints between tasks, we describe a static schedule analysis that computes whether two tasks may be executed in parallel or if they are ordered. During optimization, the task-ordering information is exploited to reduce the number of volatile memory accesses the compiler must insert to guarantee sequential consistency. The evaluation shows that scheduling information significantly improves the effectiveness of the optimizations. For our set of multi-threaded benchmarks the fully optimizing compiler removes between 70% and 100% of the volatile memory accesses inserted by the non-optimizing compiler. As a result, the overhead of sequentially consistent Java compared to standard Java is reduced from 136% on average for the unoptimized version to 11% on average for the optimized version. The results indicate that with appropriate optimizations, sequential consistency can be a feasible alternative to the Java Memory Model.

Transactional memory (TM) is an attractive platform for parallel programs, and several software transactional memory (STM) designs have been presented. We explore and analyze several optimization opportunities to adapt STM parameters to a running program. This paper uses adaptSTM, a flexible STM library with a non-adaptive baseline common to current fast STM libraries to evaluate different performance options. The baseline is extended by an online evaluation system that enables the measurement of key runtime parameters like read- and write-locations, or commit- and abort-rate. The performance data is used by a thread-local adaptation system to tune the STM configuration. The system adapts different important parameters like write-set hash-size, hash-function, and write strategy based on runtime statistics on a per-thread basis. We discuss different self-adapting parameters, especially their performance implications and the resulting trade-offs. Measurements show that local per-thread adaptation outperforms global system-wide adaptation. We position local adaptivity as an extension to existing systems. Using the STAMP benchmarks, we compare adaptSTM to two other STM libraries, TL2 and tinySTM. Comparing adaptSTM and the adaptation system to TL2 results in an average speedup of 43% for 8 threads and 137% for 16 threads. adaptSTM offers performance that is competitive with tinySTM for low-contention benchmarks; for high-contention benchmarks adaptSTM outperforms tinySTM. Thread-local adaptation alone increases performance on average by 4.3% for 16 threads, and up to 10% for individual benchmarks, compared to adaptSTM without active adaptation.

In statically-typed programming languages, the compiler ensures that method arguments are passed in the expected order by checking the type of each argument. However, calls to methods with multiple equally-typed parameters slip through this check. The uncertainty about the correct argument order of equally-typed arguments can cause various problems, for example, if a programmer accidentally reverses two arguments. We present an automated, static program analysis that detects such problems without any input except for the source code of a program. The analysis leverages the observation that programmer-given identifier names convey information about the semantics of arguments, which can be used to assign equally-typed arguments to their expected position. We evaluate the approach with a large corpus of Java programs and show that our analysis finds relevant anomalies with a precision of 76%.

Multiprocessors based on processors with multiple cores usually include a non-uniform memory architecture (NUMA); even current 2-processor systems with 8 cores exhibit non-uniform memory access times. As the cores of a processor share a common cache, the issues of memory management and process mapping must be revisited. We find that optimizing only for data locality can counteract the benefits of cache contention avoidance and vice versa. Therefore, system software must take both data locality and cache contention into account to achieve good performance, and memory management cannot be decoupled from process scheduling. We present a detailed analysis of a commercially available NUMA-multicore architecture, the Intel Nehalem. We describe two scheduling algorithms: maximum-local, which optimizes for maximum data locality, and its extension, N-MASS, which reduces data locality to avoid the performance degradation caused by cache contention. N-MASS is fine-tuned to support memory management on NUMA-multicores and improves performance up to 32%, and 7% on average, over the default setup in current Linux implementations.

There is a debate on when and how to teach parallel programming in the undergraduate curriculum. We try to structure the debate along a number of dimensions and then present the solution that we adopted for an engineering-oriented curriculum. We added an introduction to parallel programming to the list of mandatory classes in the 2nd semester. The class exposes students to three styles of parallel programming: threads with shared memory, CSP-style message passing, and OpenMP-based parallel programming. Within these models, the class aims to focus the student's attention on communication as the key issue in parallel programs. Explicit communication (or their absence) causes correctness problems, implicit communication (e.g., when accessing shared data in different threads) forces the student to understand when updates are globally visible. An introductory class early in the undergraduate curriculum has a number of benefits and disadvantages, which are discussed in this paper. A preliminary evaluation after two editions of this course indicates that the design goals are met but also points to several issues that other institutions may want to consider.

Modern multicore processors with an on-chip memory controller form the base for NUMA (non-uniform memory architecture) multiprocessors. Each processor accesses part of the physical memory directly and has access to the other parts via the memory controller of other processors. These other processors are reached via the cross-processor interconnect. As a consequence a processor's memory controller must satisfy two kinds of requests: those that are generated by the local cores and those that arrive via the interconnect from other processors. On the other hand, a core (respectively the core's cache) can obtain data from multiple sources: data can be supplied by the local memory controller or by a remote memory controller on another processor. In this paper we experimentally analyze the behavior of the memory controllers of a commercial multicore processor, the Intel Xeon 5520 (Nehalem). We develop a simple model to characterize the sharing of local and remote memory bandwidth. The uneven treatment of local and remote accesses has implications for mapping applications onto such a NUMA multicore multiprocessor. Maximizing data locality does not always minimize execution time; it may be more advantageous to allocate data on a remote processor (and then to fetch these data via the cross-processor interconnect) than to store the data of all processes in local memory (and consequently over-loading the on-chip memory controller).

This paper presents an approach to the safe execution of applications based on software-based fault isolation and policy-based system call authorization. A running application is encapsulated in an additional layer of protection using dynamic binary translation in user-space. This virtualization layer dynamically recompiles the machine code and adds multiple dynamic security guards that verify the running code to protect and contain the application.

Software maintenance tasks, such as testing and program understanding, can benefit from formal specifications that describe how a program should use an API. Recently, there has been increasing interest in specification miners that automatically extract finite state specifications of method ordering constraints from existing software. However, comparing different mining approaches is difficult, because no common ground to evaluate the effectiveness of specification miners has been established yet. We present a framework for evaluating to which extent specification miners find valid finite state descriptions of API usage constraints. The framework helps in creating reference specifications and includes metrics to compare mined specifications to the reference specifications. The metrics are tailored for evaluating specification miners and account for imprecision and incompleteness in mined specifications. We use the framework to compare the effectiveness of three mining approaches and to show their respective benefits.

We introduce a type system based on intervals, objects representing the time in which a block of code will execute. The type system can verify time-based properties such as when a field will be accessed or a method will be invoked. One concrete application of our type system is data-race protection: For fields which are initialized during one phase of the program and constant thereafter, users can designate the interval during which the field is mutable. Code which happens after this initialization interval can safely read the field in parallel. We also support fields guarded by a lock and even the use of dynamic race detectors. Another use for intervals is to designate different phases in the object’s lifetime, such as a constructor phase. The type system then ensures that only appropriate methods are invoked in each phase.

Dynamic (on the fly) binary translation is an important part of many software systems. In this paper we discuss how to combine efficient translation with the generation of efficient code, while providing a high-level table-driven user interface that simplifies the generation of the binary translator (BT).

Formal specifications are used to identify programming errors, verify the correctness of programs, and as documentation. Unfortunately, producing them is error-prone and time-consuming, so they are rarely used in practice. Inferring specifications from a running application is a promising solution. However, to be practical, such an approach requires special techniques to treat large amounts of runtime data. We present a scalable dynamic analysis that infers specifications of correct method call sequences on multiple related objects. It preprocesses method traces to identify small sets of related objects and method calls which can be analyzed separately. We implemented our approach and applied the analysis to eleven real-world applications and more than 240 million runtime events. The experiments show the scalability of our approach. Moreover, the generated specifications describe correct and typical behavior, and match existing API usage documentation.

Wireless multi-hop access networks are an increasingly popular option to provide cost-efficient last-mile Internet access. However, despite extensive research, performance of even basic communication services, such as TCP, is still problematic. Measurements collected on a wireless testbed indicate that the poor performance of multi-hop access networks is caused by poor interactions between TCP congestion control and link- layer bit-rate adaptation resulting in severely reduced network efficiency even over short wireless paths (< 6 hops). However, bit-rate adaptation improves fairness across TCP flows. The same principal observations hold for hybrid wireless/wireline paths. To investigate approaches to improve TCP performance, we present a simple model that captures the cause for the inefficiency of TCP over autorate links. We then examine several techniques at both the TCP level and the link layer (TCP Vegas, clamping, limiting the buffer size at the wireless routers) to alleviate contention. None of these techniques works for all scenarios, but the simple approach to limit the buffer size is attractive in many settings that include four or more wireless hops.

Vehicular ad hoc networks using WLAN technology have recently received considerable attention. We present a position-based routing scheme called Connectivity-Aware Routing (CAR) designed specifically for inter-vehicle communication in a city and/or highway environment. A distinguishing property of CAR is the ability to not only locate positions of destinations but also to find connected paths between source and destination pairs. These paths are auto-adjusted on the fly, without a new discovery process. "Guards" help to track the current position of a destination, even if it traveled a substantial distance from its initially known location. For the evaluation of the CAR protocol we use realistic mobility traces obtained from a microscopic vehicular traffic simulator that is based on a model of driver behavior and the real road maps of Switzerland.

Hardware performance monitors provide detailed direct feedback about application behavior and are an additional source of infor-mation that a compiler may use for optimization. A JIT compiler is in a good position to make use of such information because it is running on the same platform as the user applications. As hardware platforms become more and more complex, it becomes more and more difficult to model their behavior. Profile information that captures general program properties (like execution frequency of methods or basic blocks) may be useful, but does not capture sufficient information about the execution platform. Machine-level performance data obtained from a hardware performance monitor can not only direct the compiler to those parts of the program that deserve its attention but also determine if an optimization step actually improved the performance of the application.

Long-running applications such as network services require continuous uptime but also frequent changes to the software. To avoid downtime for software maintenance, applications must be updated at run-time. We describe a system based on the ideas of aspect-oriented programming (AOP) to manage such updates. Join points as defined by AOP establish locations for code modification in a program. We use these join points to guide software updates. Updating a system is a two-step process: the original (old) and new (updated) versions of a software system are compared and a list of update actions and pointcuts is constructed. We present a case-study to evaluate the applicability of this approach

Policy-based management (PBM) is a promising approach to realize adaptivity in networks that would be hard - if not impossible - for administrators to configure manually. In PBM systems, the network configuration is not directly expressed in terms of low-level properties, such as IP or MAC addresses; rather, complex business entities, such as users or departments, can be defined and allow the administrators to specify high-level network policies. Even though PBM can reduce the effort for managing complex networks significantly, today's solutions lack a generic way for expressing adaptive policies. A PBM system can be called adaptive if the decision of when and in which order policies are activated is not only based on fixed predefined dates but the system also takes environmental and internal events into account. In this paper we describe a model of adaptive timing constraints and introduce an architecture for executing timing specifications (sets of constraints). Within a timing specification, the administrator usually creates single constraints only implicitly by defining the lifetime of managed resources, sequences of events, and high- level temporal relationships between them. Because each timing constraint defines a < relation between two single events, a timing specification can be described as a partial ordering of events over the event space. During execution, a timing service triggers PBM systems to activate, inactivate, or adapt management policies according to the timing specification.

Memory fences inhibit the reordering of memory accesses in modern microprocessors; fences are useful to implement synchronization and strong shared memory semantics in multi-threaded programs. A naive implementation of memory fences can result in a significant performance penalty for processors with deep pipelines supporting multiple concurrent memory accesses. The paper compares three techniques to reduce the impact of memory fences: (1) Read-speculation allows reads that follow a fence to be issued while the fence is being processed; (2) Write-ahead additionally allows writes following a fence to proceed early; (3) Selective fences distinguish between memory accesses to thread-local and shared memory and enforce ordering only among accesses to shared memory. We evaluate and compare the effectiveness of these techniques with a simulator derived from the Pentium 4 architecture. We report data for a storage model that uses memory fences to enforce the memory semantics at monitor boundaries.

Vehicular ad hoc networks (VANETs) using WLAN tech-nology have recently received considerable attention. The evaluation of VANET routing protocols often involves simulators since management and operation of a large number of real vehicular nodes is expensive. We study the behavior of routing protocols in VANETs by using mobility information obtained from a microscopic vehicular traffic simulator that is based on the on the real road maps of Switzerland. The performance of AODV and GPSR is significantly in uenced by the choice of mobility model, and we observe a significantly reduced packet delivery ratio when employing the realistic traffic simulator to control mobility of nodes. To address the performance limitations of communication pro-tocols in VANETs, we investigate two improvements that increase the packet delivery ratio and reduce the delay until the first packet arrives. The traces used in this study are available for public download.

The simulation of mobile networks calls for a mobility model to generate the trajectories of the mobile users (or nodes). It has been shown that the mobility model has a major influence on the behavior of the system. Therefore, using a realistic mobility model is important if we want to increase the confidence that simulations of mobile systems are meaningful in realistic settings. In this paper we present an executable mobility model that uses real-life mobility characteristics to generate mobility scenarios that can be used for network simulations. We present a structured framework for extracting the mobility characteristics from a WLAN trace, for processing the mobility characteristics to determine a parameter set for the mobility model, and for using a parameter set to generate mobility scenarios for simulations. To derive the parameters of the mobility' model, we measure the mobility' characteristics of users of a campus wireless network. Therefore, we call this model the WLAN mobility model Mobility-analysis confirms properties observed by other research groups. The validation shows that the WLAN model maps the real-world mobility' characteristics to the abstract world of network simulators with a very small error. For users that do not have the possibility to capture a WLAN trace, we explore the value space of the WLAN model parameters and show how different parameters sets influence the mobility of the simulated nodes.

We present a technique to approximate the worst-case execution time that combines structural analysis with a loop-bounding algorithm based on local induction variable analysis. Structural analysis is an attractive foundation for several reasons: it delivers better bounds on the number of executions for each basic block than previous approaches, its complexity is well understood, and it allows the compiler to easily work on Java bytecode without requiring access to the original program source. There are two major steps. We first compute (min, max) bounds on the number of iterations for each loop. Then we use precise structural information to propagate these bounds to the whole control-flow graph and compute a bound for each basic block. Such a fine-grained result eases the identification of infeasible paths and improves the approximation of the worst-case execution time of a function or method. This analysis was successfully implemented in an ahead-of-time Java bytecode to native compiler and produces input for a worst-case execution time estimator. We describe the effectiveness in reducing the worst-case execution time for a number of programs from small kernels and soft-real-time applications.

Many situations call for an estimation of the execution time of applications, e.g., during design or evaluation of computer systems. In this paper we focus on large applications where the execution times heavily depend on the performance of the memory system. Since such applications are computationally expensive, direct simulation is not an option and an analytical model is called for. This paper addresses this problem by developing and evaluating two simple analytical models. These models focus on an application's interaction with the memory system. Applications are characterized by their memory access types. A regular application has continuous and stride memory accesses. An irregular application has three memory access types: continuous accesses, accesses within the same L1/L2 cache line, and random accesses. The analytical models are combined with results from micro-benchmarking or with appropriate performance estimates of memory accesses to predict application performance, either on real or future machines. We apply these models to executions of CHARMM (Chemistry at HARvard Molecular Mechanics) - a scientific application written in FORTRAN, SMV (Symbolic Model Verifier) - coded in C++. For all three applications, the approaches described here produce results with 5% accuracy on average (compared to the effective run-time measured on a real SPARC system).

Multipath streaming is used by resource intensive applications to stream their data over multiple, disjoint paths, thereby cumulating the resources of the different subpaths. The trend towards application-layer implementations of communication protocols allows the deployment of a multipath streaming protocol in the current Internet. However, because resource availability fluctuates in the Internet, a multipath streaming protocol must be combined with other mechanisms to address these fluctuations, e.g., adaptation. This paper describes two approaches to combine adaptation and multipath streaming. The first approach separates the two mechanisms and thereby allows a multipath streaming that is transparent to the application, whereas the other combines the two mechanisms in the application context. This paper compares the two approaches along various parameters. It shows that the first approach is easier to deploy from an engineering point of view, but the separation of multipath streaming and adaptation yields significant drawbacks. Especially, synchronization problems due to different latencies along the paths that form the multipath setup may lead to a significant drop in the quality of data.

This research was supported, in part, by the NCCR "Mobile Information and Communication Systems", a research program of the Swiss National Science Foundation, and by a gift from the Microprocessor Research Lab (MRL) of Intel Corp.An ad hoc network is formed by wireless mobile nodes (hosts) that operate as terminals as well as routers in the network, without any centralized administration. Research in ad hoc networks often involves simulators since management and operation of a large number of nodes is expensive. However, the widely used simulator NS-2 does not scale; it is very hard to simulate medium scale networks with 100+ nodes. We describe here improvements to NS-2 to meet the needs of large ad hoc network simulations. The modified NS-2 simulator is based on the idea of exploiting the limited interference of wireless communication. The modified simulator has simulated populations of up to 3000 nodes so far and works up to 30 times faster than the original version. We also discuss how the modified simulator is validated.

A distributed application that operates in an ad hoc network formed by mobile nodes must limit its use of all-to-all communication since the overall capacity of such a network is severely constrained. To address this problem, we describe an algorithm that allows an application to impose a hierarchical structure on the participating nodes. A simple tree is maintained as hosts join and leave the ad hoc network. We evaluate this algorithm in the context of a collaboration tool for a network of Linux laptops using IEEE 802.11b network cards. Preliminary performance results from our mobile test-bed indicate that the application responds well to connectivity changes and is sufficiently agile to run in a highly mobile environment.

A compiler for multi-threaded object-oriented programs needs information about the sharing of objects for a variety of reasons: to implement optimizations, to issue warnings, to add instrumentation to detect access violations that occur at runtime. An Object Use Graph (OUG) statically captures accesses from different threads to objects. An OUG extends the Heap Shape Graph (HSG), which is a compile-time abstraction for runtime objects (nodes) and their reference relations (edges). An OUG specifies for a specific node in the HSG a partial order of events relevant to the corresponding runtime object(s). Relevant events include read and write access, object escape, thread start and join.OUGs have been implemented in a Java compiler. Initial experience shows that OUGs are effective to identify object accesses that potentially conflict at runtime and isolate accesses that never cause a problem at runtime. The capabilities of OUGs are compared with an advanced program analysis that has been used for lock elimination. For the set of benchmarks investigated here, OUGs report only a fraction of shared objects as conflicting and reduce the number of compile-time reports in terms of allocation sites of conflicting objects by 28--92% (average 64%). For benchmarks of up to 30 KLOC, the time taken to construct OUGs is, with one exception, in the order of seconds.The information collected in the OUG has been used to instrument Java programs with checks for object races. OUGs provide precise information about object sharing and static protection, so runtime instrumentation that checks those cases that cannot be disambiguated at compile-time is sparse, and the total runtime overhead of checking for object races is only 3--86% (average 47%).

Managing scientific data warehouses requires constant adaptations to cope with changes in processing algorithms, computing environments, database schemas, and usage patterns. We have faced this challenge in the RHESSI Experimental Data Center (HEDC), a datacenter for the RHESSI NASA spacecraft. In this paper we describe our experience in developing HEDC and discuss in detail the design choices made. To successfully accommodate typical adaptations encountered in scientific data management systems, HEDC (i) clearly separates generic from domain specific code in all tiers, (ii) uses a file system for the actual data in combination with a DBMS to manage the corresponding meta data, and (iii) revolves around a middle tier designed to scale if more browsing or processing power is required. These design choices are valuable contributions as they address common concerns in a wide range of scientific data management systems.

Network-aware content delivery is an attractive approach to mitigate the problems produced by the significant fluctuations of the available bandwidth present in today's Internet. Such network-aware applications require information about the current condition of the network to adapt their resource demands. Such information can be obtained at the network level, the transport protocol level, or directly by the application. This paper compares two kinds of application-level monitoring (at the sender and receiver side) and transport-level monitoring with regard to their ability to provide useful information to network-aware applications. The results indicate that transport-level monitoring can effectively and efficiently satisfy the need for timely and accurate bandwidth information. This observation has direct implications for protocol/OS design. It is desirable to widen the transport layer API to allow the application efficient access to network status information required for adaptation.

Remos provides resource information to distributed applications. Its design goals of scalability, flexibility, and portability are achieved through an architecture that allows components to be positioned across the network, each collecting information about its local network. To collect information from different types of networks and from hosts on those networks, Remos provides several collectors that use different technologies, such as SNMP or benchmarking. By matching the appropriate collector to each particular network environment and by providing an architecture for distributing the output of these collectors across all querying environments, Remos collects appropriately detailed information at each site and distributes this information where needed in a scalable manner. Prediction services are integrated at the user-level, allowing history-based data collected across the network to be used to generate the predictions needed by a particular user. Remos has been implemented and tested in a variety of networks and is in use in a number of different environments.

Active services are application-specified programs that are executed inside the network. The location where the active service is executed plays an important role. The dynamic behavior of networks requires that the selection of the most suitable location to instantiate a service is done at run time. To dynamically place an active service, information about the network (topology, bandwidth) and application (type of the service) is necessary. This paper describes a method to dynamically search for available active service locations in the Internet. To be deployed in the current Internet, a solution is required to (i) scale well to large networks, (ii) to demand as little changes to the Internet as possible, especially not at lower network layers. Finally, the solution must be flexible and customizable to take application requirements into account. The proposed solution makes use of the routing path between two end systems. Active service locations that are located close to the routing path are then found via DNS queries. The evaluation shows that the application pays an overhead at startup time. For applications that can tolerate a startup delay, we show with two experiments using a video application that the quality of the application can be increased by dynamic placement of active services.

An important class of adaptive applications can trade off one kind of resources (e.g., network bandwidth) for requests of other resources (e.g., CPU cycles). They create new challenges for operating systems: their processor demands change rapidly based on external factors, and resource requests are recurring, though non-periodic. However these applications share some of the characteristics of "soft real-time" tasks and are often resilient with regard to un- or under-availability of resources. This paper presents a comprehensive approach to processor management for adaptive applications, the R-Scheduler. It co-exists with a best-effort scheduler and has been implemented for NetBSD and ported to Linux. The runtime costs of admission control and scheduling are modest (below 1%). For realistic usage scenarios, the R-Scheduler allows the application to meet its time limits, whereas the traditional (default) best-effort scheduling discipline fails to allocate the CPU resources effectively.

Sometimes a client that receives a multimedia stream from a server can change the connection used to transfer the data. There may be multiple paths or multiple servers, but a switch from one connection to another requires a handoff. During such a handoff, the player (of the video and/or audio stream) should be fed with a constant data stream so that they player does not have to stop. Handoffs can be used in addition to adaptive (frame-dropping) filters to improve the quality of multimedia streams as received by the client.This paper investigates the influence of several factors on the quality of the multimedia stream during the handoff: the time needed to establish the connection to the new server, the size and the fill degree of the client buffer, the length of the synchronization phase (where both the old and the new connection are sending) and the most appropriate start packet for the new connection. The evaluation showsm that a handoff can be a viable solution if an appropriate strategy is chosen to phase over from the old connection to the new one.

We present an on-the-fly mechanism that detects access conflicts in executions of multi-threaded Java programs. Access conflicts are a conservative approximation of data races. The checker tracks access information at the level of objects (object races) rather than at the level of individual variables. This viewpoint allows the checker to exploit specific properties of object-oriented programs for optimization by restricting dynamic checks to those objects that are identified by escape analysis as potentially shared. The checker has been implemented in collaboration with an "ahead-of-time"Java compiler. The combination fo static program analysis (escape-analysis) and inline instrumentation during code generation allows us to reduce the runtime overhead of detecting access conflicts. This overhead amounts to about 16-129% in time and less than 25% in space for typical benchmark applications and compares favorably to previously published on-the-fly mechanism that incurred an overhead of about a factor of 2-80 in time and up to a factor of 2 in space.

Accurate network topology information is important for both network management and application performance prediction. Most topology discovery research has focused on wide-area networks and examined topology only at the IP router level, ignoring the need for LAN topology information. Recent work has demonstrated that bridged Ethernet topology can be determined using standard SNMP MIBs; however, these algorithms require each bridge to learn about all other bridges in the network. Our approach to Ethernet topology discovery can determine the connection between a pair of the bridges that share forwarding entries for only three hosts. This minimal knowledge requirement significantly expands the size of the network that can be discovered. We have implemented the new algorithm, and it has accurately determined the topology of several different networks using a variety of hardware and network configurations. Our implementation requires access to only one endpoint to perform the queries needed for topology discovery.

The innovative techniques of TCP Vegas have been the subject of much debate in recent years. Several studies have reported that TCP Vegas provides better performance than TCP Reno. However, the question of which of the new techniques are responsible for the impressive performance gains remains unanswered so far. This paper presents a detailed performance evaluation of TCP Vegas. By decomposing TCP Vegas into the various novel mechanisms proposed and assessing the effect of each of these mechanisms on performance, we show that the reported performance gains are achieved primarily by TCP Vegas's new techniques for slow start and congestion recovery. TCP Vegas's innovative congestion avoidance mechanism is shown to have only a minor influence on throughput. Furthermore, we find that the congestion avoidance mechanism exhibits fairness problems even if all competing connections operate with the same round trip time.

The register allocation phase of a compiler maps live ranges of a program to registers. If there are more candidates than there are physical registers, the register allocator must spill a live range (the home location is in memory) or split a live range (the live range occupies multiple locations). One of the challenges for a register allocator is to deal with spilling and splitting together. Fusion-based register allocation uses the structure of the program to make splitting and spilling decisions, with the goal to move overhead operations to infrequently executed parts of a program. The basic idea of fusion-based register allocation is to build up the interference graph. Starting with some base region (e.g., a basic block, a loop), the register allocator adds basic blocks to the region and incrementallly builds the interference graph. When there are more live ranges than registers, the register allocator selects live ranges to split; these live ranges are split along the edge that was most recently added to the region. This article describes fusion-based register allocation in detail and compares it with other approaches to register allocation. For programs from the SPEC92 suite, fusion-based register allocation can improve the execution time (of optimized programs, for the MIPS architecture) by up to 8.4% over Chaitin-style register allocation.

Large scale networked image retrieval systems face a number of problems that are not fully satisfied by current systems. On one hand, integrated solutions that store all image data centrally are often limited in terms of scalability and autonomy of data providers. On the other hand, WWW-based search engines proved to be fairly scalable, and data providers retain their autonomy. However, such engines often confront users with links to servers that are not available or to images that no longer exist, i.e., they are unable to keep their meta-database consistent with the repositories' contents. Furthermore, existing solutions often neglect the cost of image delivery. The considerable variations in the effective bandwidth in today's Internet lead to highly unpredictable response times, which are often intolerable from the user's point of view.

The development and performance of network-aware applications depends on the availability of accurate predictions of network resource properties. Obtaining this information directly from the network is a scalable solution that provides the accurate performance predictions and topology information needed for planning and adapting application behavior across a variety of networks. The performance predictions obtained directly from the network are as accurate as application-level benchmarks, but the network-based technique provides the added advantages of scalability and topology discovery. We describe how to determine network properties directly from the network using SNMP. We provide an overview of SNMP and describe the features it provides that make it possible to extract both available bandwidth and network topology information from network devices. The available bandwidth predictions based on network queries using SNMP are compared with traditional predictions based on application history to demonstrate that they are equally useful. To demonstrate the feasibility of topology discovery, we present results for a large Ethernet at CMU.

Network-aware applications attempt to adjust their resource demands in response to changes in resource availability. E.g., if a server maintains a connection to a client, the server may want to adjust the amount of data sent to the client based on the effective bandwidth realized for the connection. Information about current and future network performance is therefore crucial for an adaptive application. This paper discusses three aspects of the coupling of applications and networks: (1) a network-aware application needs timely information about the status of the network; (2) a simple bandwidth estimation technique performs reasonably well for TCP-Reno connections without timeouts; (3) enhancements proposed to TCP-Reno to reduce the number of timeouts (i.e., SACKs and its variants) increase the bandwidth but also improve the accuracy of bandwidth estimators developed by other researchers. The empirical observations reported in this paper are based on an in-vivo experiment in the Internet. Over a 6-month period, we logged the micro dynamics of random connections between a set of selected hosts. These results are encouraging for the developer of a network-aware application since they provide evidence that a simple widening of the interface between applications and network (protocol) may provide the information that allows an application to successfully adapt to changes in resource availability.

We present a system that allows OpenMP programs to execute on a network of workstations with a variable number of nodes. The ability to adapt to a variable number of nodes allows a program to take advantage of additional nodes that become available after it starts execution, or to gracefully scale down when the number of available nodes is reduced. We demonstrate that the cost of adaptation is modest; the system allows a program to adapt at a moderate rate without much performance loss.Two ideas underlie the efficiency of our design. First, we recognize that OpenMP programs exhibit convenient adaptation points during their execution, points at which the cost of adaptation can be much reduced. Second, by allowing a process a certain grace period before it must leave a node, we insure that most adaptations can occur at these adaptation points, and thus at low cost. Migration of a process, a much more expensive method for providing adaptivity, is used only as a back-up solution, when the process cannot reach an adaptation point within the grace period.Our implementation consists of an OpenMP pre-processor that generates TreadMarks distributed shared memory (DSM) programs, and a version of TreadMarks modified to adapt to a variable number of nodes. Using a DSM as the underlying substrate facilitates the data (re-)distribution necessary after an adaptation.

Irregular applications based on sparse matrices are at the core of many important scientific computations. Since the importance of such applications is likely to increase in the future, high-performance parallel and distributed systems must provide adequate support for such applications. We characterize a family of irregular scientific applications and derive the demands they will place on the communication systems of future parallel systems. Running time of these applications is dominated by repeated sparse matrix vector product (SMVP) operations. Using simple performance models of the SMVP, we investigate requirements for bisection bandwidth, sustained bandwidth on each processing element (PE), burst bandwidth during block transfers, and block latencies for PEs under different assumptions about sustained computational throughput. Our model indicates that block latencies are likely to be the most problematic engineering challenge for future communication networks.

Development of portable network-aware applications demands an interface to the network that allows an application to obtain information about its execution environment. The paper motivates and describes the design of Remos, an API that allows network-aware applications to obtain relevant information. The major challenges in defining a uniform interface are network heterogeneity, diversity in traffic requirements, variability of the information, and resource sharing in the network. Remos addresses these issues with two abstraction levels, explicit management of resource sharing, and statistical measurements. The flows abstraction captures the communication between nodes, and the topologies abstraction provides a logical view of network connectivity. Remos measurements are made at network level, and therefore information to manage sharing of resources is available. Remos is designed to deliver best effort information to applications, and it explicitly adds statistical reliability and variability measures to the core information. The paper also presents preliminary results and experience with a prototype Remos implementation for a high speed IP based network testbed.

Today, any large object-oriented software system is built using frameworks. Yet, designing frameworks and defining their interaction with clients remains a difficult task. A primary reason is that today's dominant modeling concept, the class, is not well suited to describe the complexity of object collaborations as it emerges in framework design and integration. We use role modeling to overcome the problems and limitations of class-based modeling. Using role models, the design of a framework and its use by clients can be described succinctly and with much better separation of concerns than with classes. Using role objects, frameworks can be integrated into use-contexts that have not been foreseen by their original designers.

Modern networks provide a QoS (quality of service) model to go beyond best-effort services, but current QoS models are oriented towards low-level network parameters (e.g., bandwidth, latency, jitter). Application developers, on the other hand, are interested in quality models that are meaningful to the end-user and, therefore, struggle to bridge the gap between network and application QoS models. Examples of application quality models are response time, predictability or a budget (for transmission costs). Applications that can deal with changes in the network environment are called network-aware. A network-aware application attempts to adjust its resource demands in response to network performance variations. This paper presents a framework-based approach to the construction of network-aware programs. At the core of the framework is a feedback loop that controls the adjustment of the application to network properties. The framework provides the skeleton to address two fundamental challenges for the construction of network-aware applications: how to find out about dynamic changes in network service quality; and how to map application-centric quality measures (e.g., predictability) to network-centric quality measures (e.g., QoS models that focus on bandwidth or latency). Our preliminary experience with a prototype network-aware image retrieval system demonstrates the feasibility of our approach. The prototype illustrates that there is more to network-awareness than just taking network resources and protocols into account and raises questions that need to be addressed (from a software engineering point of view) to make a general approach to network-aware applications useful.

Many parallel systems offer a simple view of memory: all storage cells are addressed uniformly. Despite a uniform view of the memory, the machines differ significantly in their memory system performance (and may offer slightly different consistency models). Cached and local memory accesses are much faster than remote read accesses to data generated by another processor or remote write to data intentionally pushed to memories close to another processor. The bandwidth from/to cache and local memory can be an order of magnitude (or more) higher than the bandwidth to/from remote memory. The situation is further complicated by the heavy influence of the access pattern (i.e. the spatial locality of reference) on both the local and the remote memory system bandwidth. In these modern machines, a compiler for a parallel system is faced with a number of options to accomplish a data transfer most efficiently. The decision for the best option requires a cost benefit model, obtained in an empirical evaluation of the memory system performance. We evaluate three DEC Alpha based parallel systems, to demonstrate the practicality of this approach. The common DEC-Alpha processor architecture facilitates a direct comparison of memory system performance. These systems are the DEC 8400, the Cray T3D, and the Cray T3E. The three systems differ in their clock speed, their scalability and in the amount of coherency they provide.

Choosing the right kind of register for a live range plays a major role in eliminating the register-allocation overhead when the compiled function is frequently executed or function tails are on the most frequently executed paths. Picking the wrong kind of register for a live range incurs a high penalty that may dominate the total overhead of register allocation. In this paper, we present three improvements, storage-class analysis, benefit-driven simplification, and preference decision that are effective in selecting the right kind of register for a live range. Then we compare an enhanced Chaitin-style register allocator (with these three improvements) with priority-based and optimistic coloring.

Parallel languages allow the programmer to express parallelism at a high level. The management of parallelism and the generation of interprocessor communication is left to the compiler and the runtime system. This approach to parallel programming is particularly attractive if a suitable widely accepted parallel language is available. High Performance Fortran (HPF) has emerged as the first popular machine independent parallel language, and remarkable progress has been made towards compiling HPF efficiently. However, the performance of HPF programs is often poor and unpredictable, and obtaining adequate performance is a major stumbling block that must be overcome if HPF is to gain widespread acceptance. The programmer is often in the dark about how to improve the performance of an HPF program since poor performance can be attributed to a variety of reasons, including poor choice of algorithm, limited use of parallelism, or an inefficient data mapping. This paper presents a profiling tool that allows the programmer to identify the regions of the program that execute inefficiently, and to focus on the potential causes of poor performance. The central idea is to distinguish the code that is executing efficiently from the code that is executing poorly. Efficient code uses all processors of a parallel system to make progress, while inefficient code causes processors to wait, execute replicated code, idle, communicate, or perform compiler bookkeeping. We designate the latter code as non-scalable, since adding more processors generally does not lead to improved performance for such code. By analogy, the former code is called scalable. The tool presented here separates a program into scalable and non-scalable components and identifies the causes of non-scalability of different components. We show that compiler information is the key to dividing the execution times into logical categories that are meaningful to the programmer. We present the design and implementation of a profiler that is integrated with Fx, a compiler for a variant of HPF. The paper includes two examples that demonstrate how the data reported by the profiler are used to identify and resolve performance bugs in parallel programs. © 1997 John Wiley & Sons, Ltd.

This paper describes how the cmcc compiler reuses code---both internally (reuse between different modules) and externally (reuse between versions for different target machines). The key to reuse are the application frameworks developed for global data-flow analysis, code generation, instruction scheduling, and register allocation.The code produced by cmcc is as good as the code produced by the native compilers for the MIPS and SPARC, although significantly less resources have been spent on cmcc (overall, about 6 man years by 2.5 persons). cmcc is implemented in C++, which allowed for a compact expression of the frameworks as class hierarchies. The results support the claim that suitable frameworks facilitate reuse and thereby significantly improve developer effectiveness.

Although compiler optimizations play a crucial role in the performance of modern computer systems, debugger technology has lagged behind in its support of optimization. Yet debugging the unoptimized translation is often impossible or futile, so handling of code optimizations in the debugger is necessary. But compiler optimizations make it difficult to provide source-level debugger functionality: Global optimizations can cause the runtime value of a variable to be inconsistent with the source-level value expected at a breakpoint; such variables are called endangered variables. A debugger must detect and warn the user of endangered variables otherwise the user may draw incorrect conclusions about the program. This paper presents a new algorithm for detecting variables that are endangered due to global scalar optimization. Our approach provides more precise classifications of variables and is still simpler than past approaches. We have implemented and evaluated our techniques in the context of the cmcc optimizing C compiler. We describe the compiler extensions necessary to perform the required bookkeeping of compiler optimization. We present measurements of the effect of optimizations on a debugger's ability to present the expected values of variables to the user.

This paper addresses job scheduling for parallel supercomputers. Modern parallel systems with n nodes can be used by jobs requesting up to n nodes. If less than n nodes are requested, multiple jobs can be run at the same time, allowing several users to use the system. One of the challenges for the operating system is to give reasonable service to a diverse group of requests. A single 1-node job that is running for a long time may effectively block the whole machine if the next job requests all n nodes. To date various policies have been proposed for the scheduling highly parallel computers. But as the users of current supercomputers know, these policies work far from perfect. This paper reports on the measurement of the usage of a 96-node Intel Paragon at ETH Zurich, a 512 node IBM SP2 at Cornell Theory Center, and a 512 node Cray T3D at Pittsburgh Supercomputing Center. We discuss the common characteristics of the different workloads and identify their impact on job scheduling techniques for such parallel systems. The metrics used for evaluating scheduling are based on turnaround time and fairness among jobs. We specifically show how two simple scheduling optimizations based on reordering the waiting queue can be used to effectively improve scheduling performance on real workloads. An important contribution of this paper is to establish that supercomputer workloads do exhibit some common characteristics but they also differ in important ways, and the knowledge of workloads is important for design of effective scheduling algorithms. Given the current ad-hoc approach applied to tuning the scheduler systems, these results are of interest to scheduling researchers, supercomputer installations, and developers of scheduling software.

Article Decoupling synchronization and data transfer in message passing systems of parallel computers Share on Authors: T. Stricker School of Computer Science, Carnegie Mellon University, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, Pittsburgh, PAView Profile , J. Stichnoth School of Computer Science, Carnegie Mellon University, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, Pittsburgh, PAView Profile , D. O'Hallaron School of Computer Science, Carnegie Mellon University, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, Pittsburgh, PAView Profile , S. Hinrichs School of Computer Science, Carnegie Mellon University, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, Pittsburgh, PAView Profile , T. Gross School of Computer Science, Carnegie Mellon University, Pittsburgh, PA and Institut für Computer Systeme, ETH Zürich, CH 8092 Zürich School of Computer Science, Carnegie Mellon University, Pittsburgh, PA and Institut für Computer Systeme, ETH Zürich, CH 8092 ZürichView Profile Authors Info & Claims ICS '95: Proceedings of the 9th international conference on SupercomputingJuly 1995 Pages 1–10https://doi.org/10.1145/224538.224539Online:03 July 1995Publication History 25citation370DownloadsMetricsTotal Citations25Total Downloads370Last 12 Months2Last 6 weeks1 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 SiteGet Access

Communication in a parallel system frequently involves moving data from the memory of one node to the memory of another; this is the standard communication model employed in message passing systems. Depending on the application, we observe a variety of patterns as part of communication steps, e.g., regular (i.e. blocks of data), strided, or irregular (indexed) memory accesses. The effective speed of these communication steps is determined by the network bandwidth and the memory bandwidth, and measurements on current parallel supercomputers indicate that the performance is limited by the memory bandwidth rather than the network bandwidth.Current systems provide a wealth of options to perform communication, and a compiler or user is faced with the difficulty of finding the communication operations that best use the available memory and network bandwidth. This paper provides a framework to evaluate different solutions for inter-node communication and presents the copy-transfer model; this model captures the contributions of the memory system to inter-node communication. We demonstrate the usefulness of this simple model by applying it to two commercial parallel systems, the Cray T3D and the Intel Paragon.In particular we identify two methods to transfer data between nodes in these two machines. In buffer-packing transfers, a contiguous block of data is transferred across the network. If the data are not stored contiguously, they are copied to (gathering) or from (scattering) buffers in local memory before and after the transfer. Chained transfers perform gathering, transfer and scattering in one step, reading the data elements with some non-sequential pattern and immediately transferring them on to the destination.Our model and measurements indicate that chaining of the gather, transfer, and scatter operations results in better performance than buffer packing for many important access patterns. Most standard message passing libraries (like MPI, PVM or NX) force the parallelizing compiler (or the programmer) to employ the buffer-packing communication operations. However, the addition of hardware support dedicated to communication (e.g., DMAs, line-transfer units) now gives the compiler a wider range of options.

We consider the problem of high-speed I/O for a single application running on multiple nodes of a distributed-memory parallel computer. Our model is that the parallel system is connected to an I/O system that provides the interface between the internal connections of the parallel system and one or more external connections, such as HIPPI links. We identify two primary operations for this I/O system: scattering data from a high speed link across several lower speed links and gathering data from multiple links onto a single high speed link. We show that these core operations are the basis of the I/O system, independent of the relative speeds of the internal and external connections.

For a wide variety of applications, both task and data parallelism must be exploited to achieve the best possible performance on a multicomputer. Recent research has underlined the importance of exploiting task and data parallelism in a single compiler framework, and such a compiler can map a single source program in many different ways onto a parallel machine. The tradeoffs between task and data parallelism are complex and depend on the characteristics of the program to be executed, most significantly the memory and communication requirements, and the performance parameters of the target parallel machine. We present a framework to isolate and examine the specific characteristics of programs that determine the performance for different mappings. Our focus is on applications that process a stream of input, and whose computation structure is fairly static and predictable. We describe three such applications that were developed with our compiler: fast Fourier transforms, narrowband tracking radar; and multibaseline stereo. We examine the tradeoffs between various mappings for them and show how the framework is used to obtain efficient mappings.>

Trace scheduling is an optimization technique that selects a sequence of basic blocks as a trace and schedules the operations from the trace together. If an operation is moved across basic block boundaries, one or more compensation copies may be required in the off-trace code. This article discusses the generation of compensation code in a trace scheduling compiler and presents techniques for limiting the amount of compensation code: avoidance (restricting code motion so that no compensation code is required) and suppression (analyzing the global flow of the program to detect when a copy is redundant). We evaluate the effectiveness of these techniques based on measurements for the SPEC89 suite and the Livermore Fortran Kernels, using our implementation of trace scheduling for a Multiflow Trace 7/300. The article compares different compiler models contrasting the performance of trace scheduling with the performance obtained from typical RISC compilation techniques. There are two key results of this study. First, the amount of compensation code generated is not large. For the SPEC89 suite, the average code size increase due to trace scheduling is 6%. Avoidance is more important than suppression, although there are some kernels that benefit significantly from compensation code suppression. Since compensation code is not a major issue, a compiler can be more aggressive in code motion and loop unrolling. Second, compensation code is not critical to obtain the benefits of trace scheduling. Our implementation of trace scheduling improves the SPEC mark rating by 30% over basic block scheduling, but restricting trace scheduling so that no compensation code is required improves the rating by 25%. This indicates that most basic block scheduling techniques can be extended to trace scheduling without requiring any complicated compensation code bookkeeping.

Instruction scheduling re-orders and interleaves instruction sequences from different source statements. This impacts the task of a symbolic debugger, which attempts to present the user a picture of program execution that matches the source program. At a breakpoint B, if the value in the run-time location of a variable V may not correspond to the value the user expects V to have, then this variable is endangered at B. This paper describes an approach to detecting and recovering endangered variables caused by instruction scheduling. We measure the effects of instruction scheduling on a symbolic debugger's ability to recover source values at a breakpoint. This paper reports measurements for three C programs from the SPEC suite and a collection of programs from the Numerical Recipes, which have been compiled with a variant of a commercial C compiler.

A symbolic debugger allows a user to display the values of program variables at a breakpoint. However, problems arise if the program is translated by an optimizing compiler. This paper addresses the effects of global register allocation and assignment: a register assigned to a variable V may not be holding V's value at a breakpoint since the register can also be assigned to other variables. We define the problem of determining whether a variable is in its assigned register as the residence problem. Prior work on debugging of optimized code has focused on the currency problem; detecting whether a variable's run-time value is the expected value. Determining residence is a more serious problem than currency detection. We present a data flow algorithm that accurately computes a variable's residency, by determining when a variable becomes evicted from its register. We measure the effectiveness of different approaches to determine variable residence for three C programs from the SPEC suite.

For many applications, achieving good performance on a private memory parallel computer requires exploiting data parallelism as well as task parallelism. Depending on the size of the input data set and the number of nodes (i.e., processors), different tradeoffs between task and data parallelism are appropriate for a parallel system. Most existing compilers focus on only one of data parallelism and task parallelism. Therefore, to achieve the desired results, the programmer must separately program the data and task parallelism. We have taken a unified approach to exploiting both kinds of parallelism in a single framework with an existing language. This approach eases the task of programming and exposes the tradeoffs between data and task parallelism to the compiler. We have implemented a parallelizing Fortran compiler for the iWarp system based on this approach. We discuss the design of our compiler, and present performance results to validate our approach. 1 Introduction Many applicati...

Performance is a central issue in parallel computing. In this paper, we describe our approach to teaching advanced undergraduates and graduate students about the fundamentals of measuring and analyzing the performance of programs running on a variety of parallel machines. This approach can be applied to virtually any type of parallel machine, as well as to parallel program simulators. Although performance analysis can serve many purposes, we focus on the needs of the parallel programmer: understanding the behavior of algorithms and programs, and making informed choices among them.

A global barrier synchronizes all processors in a parallel system.This paper investigates algorithms that allow disjoint subsets of processors to synchronize independently and in parallel.The user model of a subset barrier is straight forward; a processor that participates in a subset barrier needs to know only the name of the barrier and the number of participating processors.This paper identifies two general communication models for private-memory parallel systems: the bounded buffer broadcast model and the anonymous destination messagepassing model and presents algorithms fior barrier synchronization in the terms of these models.The models are detailed enough to allow meaningful cost estimates for their primitives, yet independent of a specific architecture and ~canbe supported efficiently by a modem private-memory parallel system.The anonymous destination message passing model is the most attractive.The time complexity to synchronize over a uni-directional ring of N processors is O(log N) for common cases, and 0( m) in the worst case.The algorithms have been implemented on iWarp, a private-memory parallel system and are now in daily use.The paper concludes with timing measurements obtained on a 64-node system. 1 Introduction Barrier synchronization is a useful technique for organizing 'the execution of a parallel program into a sequence of loosely coordinated phases.For example, a phase of a data-parallel program running on a private memory system might consist of a communication step,

CachingStorage systems have always attempted to use properties of the files that are stored in the system to optimize access time, capacity, and/or cost.Compression exploits patterns within files, and file migration and file caching exploit file access patterns, but the combination of these concepts has not been reported on before.We discuss here the effectiveness of a filesystem that integrates caching and compression to provide two levels of file storage on disks.This investigation is based on measurements that were collected on nine computers at three different sites.Tfie data indicate that automatic compression of least recently used files doubles the amount of data that can be stored on a given disk system, while incurring only a slight performance cost.

Parallel computers are becoming increasingly important for scientists and engineers in a wide range of disciplines.However, most undergraduate students rarely have the opportunity to program a parallel computer.Furthermore, the field of parallel computers is rapidly

The iWarp processor, which integrates both communication and computation functions on a single VLSI component, is described. The iWarp component and subsystems including it are powerful building blocks for constructing a new generation of application-specific computing systems. These special-purpose systems can achieve very high performance, while maintaining a high degree of flexibility to address different needs of an application. In particular, iWarp systems deliver high computation bandwidth (up to 20 GFLOPS for a 1024 cell system), as well as high communication bandwidth (320 Mbytes/s per cell). Programming these systems is assisted by modern tools such as optimizing compilers and parallel program generators.>

iWarp is a parallel architecture developed jointly by Carnegie Mellon University and Intel Corporation. The iWarp communication system supports two widely used interprocessor communication styles: memory communication and systolic communication. This paper describes the rationale, architecture, and implementation for the iWarp communication system.

Abstract We extend the well‐known interval analysis method so that it can be used to gather global flow information for individual array elements. Data dependences between all array accesses in different basic blocks, different iterations of the same loop, and across different loops are computed and represented as labelled arcs in a program flow graph. This approach results in a uniform treatment of scalars and arrays in the compiler and builds a systematic basis from which the compiler can perform numerous global optimizations. This global dataflow analysis is performed as a separate phase in the compiler. This phase only gathers the global relationships between different accesses to a variable, yet the use of this information is left to the code generator. This organization substantially simplifies the engineering of an optimizing compiler and separates the back end of the compiler (e.g. code generator and register allocator) from the flow analysis part. The global dataflow analysis algorithm described in this paper has been implemented and used in an optimizing compiler for a processor with deep pipelines. This paper describes the algorithm and its compact implementation and evaluates it, both with respect to the accuracy of the information and to the compile‐time cost of obtaining and using it.

A very long instruction word (VLIW) processor exploits parallelism by controlling multiple operations in a single instruction word. This paper describes the architecture and compiler tradeoffs in the design of iWarp, a VLIW single-chip microprocessor developed in a joint project with Intel Corp. The iWarp processor is capable of specifying up to nine operations in an instruction word and has a peak performance of 20 million floating-point operations and 20 million integer operations per second. An optimizing compiler has been constructed and used as a tool to evaluate the different architectural proposals in the development of iWarp. We present here the analysis and compiler optimizations for those architectural features that address two key issues in the design of a VLIW microprocessor: code density and a streamlined execution cycle. We support the results of our analysis with performance data for the Livermore Loops and a selection of programs from the LINPACK library.

An application for a parallel computer with multiple, independent processors often includes different programs (functions) for the individual processors; compilation of such functions can proceed independently. We implemented a compiler that exploits this parallelism by partitioning the input program for parallel translation. The host system for the parallel compiler is an Ethernet-based network of workstations, and different functions of the application program are compiled in parallel on different workstations. For typical programs in our environment, we observe a speedup ranging from 3 to 6 using not more than 9 processors. The paper includes detailed measurements for this parallel compiler; we report the system overhead, implementation overhead, as well as the speedup obtained when compared with sequential compilation.

The iWarp processor is a building block for parallel systems and is developed in a joint project by Carnegie Mellon University and Intel Corporation. The iWarp processor integrates computation and communication: the iWarp component architecture consists of a computation agent, capable of delivering 20 MFLOPS and 20 MIPS, and a communication agent that provides a bandwidth of 320 MBytes/sec. We expect the first iWarp-based system to be available early 1990, organized as a 8X8 two-dimensional torus.

The goal of the Warp Programming Environment (WPE) is to provide easy access to the Warp machine, a parallel supercomputer with a peak performance of 100 MFLOPS that is based on the systolic array architecture. The Warp Programming Environment offers a uniform environment for editing, compiling, debugging and executing Warp programs. It is based on an extensible shell written in Common Lisp and a runtime system written in C. It runs on a network of SUN-3 workstations under UNIX 4.2. This paper describes how the program development environment interacts with the Warp machine to support the development and execution of real-time programs on Warp.

A description is given of the iWarp architecture and how it supports various communication models and system configurations. The heart of an iWarp system is the iWarp component: a single-chip processor that requires only the addition of memory chips to form a complete system building block, called the iWarp cell. Each iWarp component contains both a powerful computation engine that runs at 20 MFLOPS (million floating-point operations per second) and a high-throughput (320 Mb/s), low-latency (100-150-ns) communication engine for interfacing with other iWarp cells. Because of their strong computation and communication capabilities, the iWarp components provide a versatile building block for high-performance parallel systems ranging from special-purpose systolic arrays to general-purpose distributed memory computers. They can support both fine-grain parallel and coarse-grain distributed computation models simultaneously in the same system. The initial iWarp demonstration system consists of an 8*8 torus of iWarp cells, delivering more than 1.2 GFLOP (billions of FLOPS). It can be expanded to include up to 1024 cells.>

MIPS is a 32-bit processor architecture that has been implemented as an nMOS VLSI chip. The instruction set architecture is RISC-based. Close coupling with compilers and efficient use of the instruction set by compiled programs were goals of the architecture. The MIPS architecture requires that the software implement some constraints in the design that are normally considered part of the hardware implementation. This paper presents experimental results on the effectiveness of this processor as a program host. Using sets of large and small benchmarks, the instruction and operand usage patterns are examined both for optimized and unoptimized code. Several of the architectural and organizational innovations in MIPS, including software pipeline scheduling, multiple-operation instructions, and word-based addressing, are examined in light of this data.

The Warp machine is a systolic array computer of linearly connected cells, each of which is a programmable processor capable of performing 10 million floating-point operations per second (10 MFLOPS). A typical Warp array includes ten cells, thus having a peak computation rate of 100 MFLOPS. The Warp array can be extended to include more cells to accommodate applications capable of using the increased computational bandwidth. Warp is integrated as an attached processor into a Unix host system. Programs for Warp are written in a high-level language supported by an optimizing compiler. The first ten-cell prototype was completed in February 1986; delivery of production machines started in April 1987. Extensive experimentation with both the prototype and production machines has demonstrated that the Warp architecture is effective in the application domain of robot navigation as well as in other fields such as signal processing, scientific computation, and computer vision research. For these applications, Warp is typically several hundred times faster than a VAX 11/780 class computer. This paper describes the architecture, implementation, and performance of the Warp machine. Each major architectural decision is discussed and evaluated with system, software, and application considerations. The programming model and tools developed for the machine are also described. The paper concludes with performance data for a large number of applications.

This paper describes the scan line array processor (SLAP), a new architecture designed for high-performance yet low-cost image computation. A SLAP is a SIMD linear array of processors, and hence is easy to build and scales well with VLSI technology; yet appropriate special features and programming techniques make it efficient for a surprisingly wide variety of low and medium level computer vision tasks. We describe the basic SLAP concept and some of its variants, discuss a particular planned implementation, and indicate its performance on computer vision and other applications.

Current single chip implementations of reduced-instruction-set processors do not support hardware floating-point operations. Instead, floating point operations have to be provided cither by a co-processor or by software. This paper discusses issues arising from a software implementation of floating point arithmetic for the MIPS processor, an experimental VLSI architecture. Measurements indicate that an acceptable level of performance is achieved, but this approach is no substitute for a hardware accelerator if higher precision results are required. This paper includes instruction profiles for the basic floating point operations and evaluates the usefulness of some aspects of the instruction set.

Warp is a programmable systolic array processor. One of its objectives is to support computer vision research. This paper shows how the Warp architecture can be used to fulfill the computational needs of low-level vision. We study the characteristics of low-level vision algorithms and show how they lead to requirements for computer architecture. These requirements are met by Warp. We then describe how the Warp system can be used. Warp programs can be classified in two ways: chained versus severed, and heterogeneous versus homogeneous. Chained and severed characterize the degree of interprocessor dependency, while heterogeneous and homogeneous characterize the degree of similarity between programs on individual processors. Taken in combination, these classes give four user models. Sophisticated programming tools are needed to support these user models.

Pipeline interlocks are used in a pipelined architecture to prevent the execution of a machine instruction before its operands are available.An alternative to this complex piece of hardware is to rearrange the instructions at compile time to avoid pipeline interlocks.This problem is called code reorganization and is studied here.The basic problem of reorganization of machine-level instructions at compile time is shown to be NP-complete.A heuristic algorithm is proposed, and its properties and effectiveness are explored.Empirical data from MIPS, a VLSI processor design, are given.The impact of code reorganization techniques on the rest of a compiler system is discussed.

Most new computer architectures are concerned with maximizing performance by providing suitable instruction sets for compiled code and providing support for systems functions. We argue that the most effective design methodology must make simultaneous tradeoffs across all three areas: hardware, software support, and systems support. Recent trends lean towards extensive hardware support for both the compiler and operating systems software. However, consideration of all possible design tradeoffs may often lead to less hardware support. Several examples of this approach are presented, including: omission of condition codes, word-addressed machines, and imposing pipeline interlocks in software. The specifics and performance of these approaches are examined with respect to the MIPS processor.

Pipeline interlocks are used in a pipelined architecture to prevent the execution of a machine instruction before its operands are available. An alternative to this complex piece of hardware is to rearrange the instructions at compile-time to avoid pipeline interlocks. This problem, called code reorganization, is studied. The basic problem of reorganization of machine level instructions at compile-time is shown to be NP-complete. A heuristic algorithm is proposed and its properties and effectiveness are explored. The impact of code reorganization techniques on the rest of a compiler system are discussed.