A significant number of mobile applications employ HTTP as their primary network protocol, as the underlying remote services oftentimes are based on World Wide Web (WWW) technology stacks. Similarly, in recent years, mobile devices have emerged as the primary means to access the WWW. We present cacheConnect, a portable mobile proxy implementation that enables aggregation and content optimization on mobile devices, rather than the commonplace proxy operations performed in the cloud. Based on this additional local caching tier that negotiates between remote data servers (for browsing or otherwise) and local applications, we enable new means of content provisioning and application-level transparent optimizations. Our demonstration highlights the operations of our solution on Android mobile devices.

As the main web page access modality shifts to mobile devices, evaluations of the impact on underlying networks is required to perform long-term strategic optimizations. In this paper, we characterize individual mobile web page objects by size, cache expiration, and their composition into pages. Employing popular mobile web landing pages, we evaluate their characteristics on an individual and composed page level to derive a model that captures their main facets with respect to object size and caching distributions on a lumped and contextually aggregated page level. We observe that similar distributions can be employed for overall object sizes as well as their composition to web pages, while the cache expiration ages need to be taken into account for different contextual types of web pages. Employing our model, we successfully approximate cache lifetime for the mobile web, demonstrating its use for mobile web performance evaluations. The employed model thus allows network operators to perform broad planning on different time scales.

In this work, we present a scheme based on Bluetooth friendly device names to enable power-optimized ad-hoc localization of mobile devices. Eliminating the service discovery and connection (including potential pairing) phases in Bluetooth allows for speedier and more power-efficient conveying of location information using friendly device names. Furthermore, we observe that using the signal strength commonly provided in reference APIs of mobile OSs, client distances can be calculated with high accuracy and without additional power penalties.

Chip multiprocessors (CMPs), or multi-core processors, have become a common way of reducing chip complexity and power consumption while maintaining high performance. Speculative CMPs use hardware to enforce dependence, allowing a parallelizing compiler to generate multithreaded code without needing to prove independence. In these systems, a sequential program is decomposed into threads to be executed in parallel; dependent threads cause performance degradation, but do not affect correctness. Thread decomposition attempts to reduce the run-time overheads of data dependence, thread misprediction, and load imbalance. Because these overheads depend on the runtimes of the threads that are being created by the decomposition, reducing the overheads while creating the threads is a circular problem. Static compile-time decomposition handles this problem by estimating the run times of the candidate threads, but is limited by the estimates' inaccuracy. Dynamic execution-time decomposition in hardware has better run-time information, but is limited by the decomposition hardware's complexity and run-time overhead. We propose a third approach where a compiler instruments a profile run of the application to search through candidate threads and pick the best threads as the profile run executes. The resultant decomposition is compiled into the application so that a production run of the application has no instrumentation and does not incurany decomposition overhead. We avoid static decomposition's estimation accuracy problem by using actual profile-run execution times to pick threads, and we avoid dynamic decomposition's overhead by performing the decomposition at profile time. Because we allow candidate threads to span arbitrary sections of the application's call graph and loop nests, an exhaustive search of the decomposition space is prohibitive, even in profile runs. To address this issue, we make the key observation that the run-time overhead of a thread depends, to the first order, only on threads that overlap with the thread inexecution (e.g., in a four-core CMP, a given thread can overlap with at most three preceding and three following threads). This observation implies that a given thread affects only a few other threads, allowing pruning of the space. Using a CMP simulator, we achieve an average speedup of 3.51 on four cores for five of the SPEC CFP2000 benchmarks, which compares favorably to recent static techniques. We also discuss experiments with CINT2000.

Progressing beyond the productivity of present-day languages appears to require using domain-specific knowledge. Domain-specific languages and libraries (DSLs) proliferate, but most optimizations and language features have limited portability because each language's semantics are related closely to its domain. We explain how any DSL compiler can use a domain-independent AI planner to implement algorithm composition as a language feature. Our notion of composition addresses a common DSL problem: good library designers tend to minimize redundancy by including only fundamental procedures that users must chain together into call sequences. Novice users are confounded by not knowing an appropriate sequence to achieve their goal. Composition allows the programmer to define and call an abstract algorithm (AA) like a procedure. The compiler replaces an AA call with a sequence of library calls, while considering the calling context. Because AI planners compute a sequence of operations to reach a goal state, the compiler can implement composition by analyzing the calling context to provide the planner's initial state. Nevertheless, mapping composition onto planning is not straightforward because applying planning to software requires extensions to classical planning, and procedure specifications may be incomplete when expressed in a planning language. Compositions may not be provably correct, so our approach mitigates semantic incompleteness with unobtrusive programmer-compiler interaction. This tradeoff is key to making composition a practical and natural feature of otherwise imperative languages, whose users eschew complex logical specifications. Compositions satisfying an AA may not be equal in performance, memory usage, or precision and require selection of a preferred solution. We examine language design and implementation issues, and we perform a case study on the BioPerl bioinformatics library.

With billion-transistor chips on the horizon, single-chip multiprocessors (CMPs) are likely to become commodity components. Speculative CMPs use hardware to enforce dependence, allowing the compiler to improve performance by speculating on ambiguous dependences without absolute guarantees of independence. The compiler is responsible for decomposing a sequential program into speculatively parallel threads, while considering multiple performance overheads related to data dependence, load imbalance, and thread prediction. Although the decomposition problem lends itself to a min-cut-based approach, the overheads depend on the thread size, requiring the edge weights to be changed as the algorithm progresses. The changing weights make our approach di#erent from graph-theoretic solutions to the general problem of task scheduling. One recent work uses a set of heuristics, each targeting a specific overhead in isolation, and gives precedence to thread prediction, without comparing the performance of the threads resulting from each heuristic. By contrast, our method uses a sequence of balanced min-cuts that give equal consideration to all the overheads, and adjusts the edge weights after every cut. This method achieves an (geometric) average speedup of 74% for floating-point programs and 23% for integer programs on a four-processor chip, improving on the 52% and 13% achieved by the previous heuristics.

This paper presents Kosha, a peer-to-peer (p2p) enhancement for the widely-used Network File System (NFS). Kosha harvests redundant storage space on cluster nodes and user desktops to provide a reliable, shared file system that acts as a large storage with normal NFS semantics. P2p storage systems provide location transparency, mobility transparency, load balancing, and file replication - features that are not available in NFS. On the other hand, NFS provides hierarchical file organization, directory listings, and file permissions, which are missing from p2p storage systems. By blending the strengths of NFS and p2p storage systems, Kosha provides a low overhead storage solution. Our experiments show that compared to unmodified NFS, Kosha introduces a 4.1% fixed overhead and 1.5% additional overhead as nodes are increased from one to eight. For larger number of nodes, the additional overhead increases slowly. Kosha achieves load balancing in distributed directories, and guarantees 99.99% or better file availability.

To achieve peak performance in a multiprocessor system, processor synchronization must be accomplished with minimal overhead. Static hardware barrier synchronization has become a popular mechanism for coordinating parallel processors [1]. Dynamic hardware barrier synchronization has typically been considered to require an extensive amount of overhead as compared to static barrier hardware, and so the potential performance increase it gives has been largely ignored [2, 3]. This paper describes a hardware implementation of a dynamic barrier synchronization mechanism with minimal overhead using “cyclical cascade chains.” It is shown that this design can be synthesized into a single FPGA for an inexpensive and efficient synchronization solution for clusters and multiprocessor computers. The design is proven to be deadlock-free and can synchronize 32 processors in an average of 196 nanoseconds. Scalability is addressed for all aspects of the design relevant to its synthesis.