We present a parallel profiling tool, GAPP, that identifies serialization bottlenecks in parallel Linux applications arising from load imbalance or contention for shared resources . It works by tracing kernel context switch events using kernel probes managed by the extended Berkeley Packet Filter (eBPF) framework. The overhead is thus extremely low (an average 4% runtime overhead for the applications explored), the tool requires no program instrumentation and works for a variety of serialization bottlenecks. We evaluate GAPP using the Parsec3.0 benchmark suite and two large open-source projects: MySQL and Nektar++ (a spectral/hp element framework). We show that GAPP is able to reveal a wide range of bottleneck-related performance issues, for example arising from synchronization primitives, busy-wait loops, memory operations, thread imbalance and resource contention.

Type family applications in Haskell must be fully saturated. This means that all type-level functions have to be first-order, leading to code that is both messy and longwinded. In this paper we detail an extension to GHC that removes this restriction. We augment Haskell’s existing type arrow, |->|, with an unmatchable arrow, | >|, that supports partial application of type families without compromising soundness. A soundness proof is provided. We show how the techniques described can lead to substantial code-size reduction (circa 80%) in the type-level logic of commonly-used type-level libraries whilst simultaneously improving code quality and readability.

Thread coarsening on GPUs combines the work of several threads into one. We show how thread coarsening can be implemented as a fully automated compile-time optimisation that estimates the optimal coarsening factor based on a low-cost, approximate static analysis of cache line re-use and an occupancy prediction model. We evaluate two coarsening strategies on three different NVidia GPU architectures. For NVidia reduction kernels we achieve a maximum speedup of 5.08x, and for the Rodinia benchmarks we achieve a mean speedup of 1.30x over 8 of 19 kernels that were determined safe to coarsen.

The International Conference on Performance Engineering (ICPE) took place in Prague in the Czech Republic on April 21–24, 2013. The conference was attended by over 160 delegates. The main research track for ICPE attracted 42 submissions from which 20 full papers and two short papers were accepted for presentation. The Program Committee comprised over 50 leading academics and industrialists from 12 countries. There was also an Industry and Experience track that focused on the application of research results and performance-related technologies to industrial performance-engineering problems and the reporting of insightful performance results based on industry experience. This track received 22 submissions of which eight were selected for presentation. The papers accepted to these two main tracks covered a range of topics addressing performance-driven software development and various flavors of modeling, including performance, survivability, and scalability modeling. The development of representative workloads and benchmarks was also well represented. There were then a number of papers that focused on performance aspects of cloud-related systems and more general aspects of scheduling and load balancing. ICPE also had a Vision/Work-in-Progress track that provided a forum for researchers to present and discuss newly-emerging ideas and showcase ongoing work that shows promise. This track received 18 submissions of which 10 were accepted for short presentations at the conference. At the end of the conference, the authors of 11 papers from the Research Track and the Industry and Experience Track were invited to submit extended versions of their papers for consideration in this special issue. The extended papers submitted went through a new round of reviews, and this led to the selection of the six contributions that appear here. We would like to thank the authors of all the extended papers for their diligence in preparing their manuscripts for consideration and the members of the special issue Program Committee for their many insightful and helpful suggestions. The contributions include a new analytical model for estimating the survivability of a smart power grid 1; a method for identifying (‘blaming’) software components and/or component compositions that result in performance errors in a component-based application 2; a new performance model for Hadoop's MapReduce framework that is based on modeling separately the generic and application-specific phases of the framework 3; a measurement-based study of the performance of web servers running on multi-core systems that can be used to understand the scaling behavior of a web server and to help find server configurations that optimize performance for a given workload 4; a method for dynamically switching between different time-series-based forecasting methods for an evolving workload trace whose behavior is controlled solely by user-defined forecasting objectives 5; a resampling technique that constructs a workload model from a supercomputer job trace that can then be used to conduct a simulation-based analysis of the performance of a parallel job scheduler 6. This rich diversity of research contributions to performance engineering reflects the evolution of the field and the roots of ICPE, which evolved from a performance evaluation workshop sponsored by the Standard Performance Evaluation Corporation (SPEC) and from the Workshop on Software and Performance (WOSP). While the SPEC workshop focused on benchmarking and encompassed many areas of software and hardware evaluation, the main focus of WOSP was the development of methodologies for software performance modeling, prediction, and engineering. Besides reflecting this diversity, the contributions in this special issue also point to the potential for fruitful collaborations and mutual learning between these two segments of the performance evaluation community. We are excited by the potential future opportunities that this union affords and hope that this special issue provides a useful insight into some of the current key topics.

Strongly-typed functional languages provide a powerful framework for embedding Domain-Specific Languages (DSLs). However, building type-safe functions defined over an embedded DSL can introduce application-specific type constraints that end up being imposed on the DSL data types themselves. At best, these constraints are unwieldy and at worst they can limit the range of DSL expressions that can be built. We present a simple solution to this problem that allows application-specific constraints to be specified at the point of use of a DSL expression rather than when the DSL's embedding types are defined. Our solution applies equally to both tagged and tagless representations and, importantly, also works in the presence of higher-rank types.

We present a new approach to software performance analysis that aims to extend conventional profiling with some of the predictive capabilities of a performance model. The idea is to execute programs in virtual time, which allows hypothetical time scaling of the constituent parts of an application to be explored in advance of any speculative redevelopment aimed at improving performance. Virtual time execution works via a virtual time scheduler that controls execution by wrapping the underlying (real time) system scheduler and enforcing a thread schedule that takes account of time scaling. The necessary instruments to achieve this are added automatically to the profiled program at load time. We present VEX, a generic low-level kernel for supporting such a `scheduling profiler' in this sense and JINE, a specific instrumentation framework for the Java programming language, that builds on VEX. An evaluation of the VEX/JINE framework with a wide range of standard benchmarks shows that the prediction error is less 10% on average and the execution time overheads less than a factor of two on average, for the benchmarks tested. We also illustrate various time scaling experiments, which yield results that are quite different to those predicted from conventional profiling measurements.

We investigate how a power-save mode affects the battery life of a device subject to stochastically determined charging and discharging periods. We use a multi-regime fluid queue, imposing a threshold at some value. When the power level falls below the threshold, (for example, 20% of charge remaining) a power-save mode is entered and the rate of discharge decreased. An expression for the Laplace transform of the battery life's probability density function is found and inverted numerically in particular instances. We show the life of battery can be significantly improved by the introduction of the power-saving threshold.

This paper describes the acceleration of virtual ecology models using field-programmable gate arrays (FPGAs). Our approach targets models generated by the Virtual Ecology Workbench (VEW); an existing tool used by biological oceanographers to build and analyze models of the plankton ecosystem in the upper ocean. Depending on the plankton study and required level of detail, the logic, memory, and data transfer requirements of the generated models can vary significantly. Using FPGAs, hardware implementations can be customized to the specific requirements of the ecological system under study and provide significant speed-ups compared to software implementations. This paper describes a framework for maximizing the speedup of VEW generated models implemented on FPGA-based acceleration platforms and then describes the implementation of a typical VEW generated model to validate the framework and demonstrate that significant speedups are possible. Based on timing and area estimates from a commercial synthesis tool, the example model implemented on a Celoxica RCHTX acceleration board featuring a Xilinx Virtex-4 FPGA performs 39 times faster at 150 MHz than the software implementation on an AMD Opteron 2200 series CPU at 1.0 GHz.

We present a virtualisation and method specialisation framework for Java that facilitates efficient, dynamic modification of the behaviour of object accesses at run time. The technique works by virtualising all method calls and field accesses associated with selected classes so that all corresponding object accesses are via the invocation of a virtual method. Different access behaviours are then supported by allowing arbitrary specialisations of those methods to be defined. The virtualisation overheads are partially recovered by allowing the JVM's optimisation subsystem to perform guarded inlining of specialised methods. We describe an implementation based on the Jikes RVM and show how the framework can be used to implement an 'implicit' readbarrier that supports incremental garbage collection. The performance overhead of full virtualisation, and the performance of the implicit read barrier compared with an existing conventional, explicit barrier, are evaluated using SPEC JVM98 and DaCapo benchmarks. The net virtualisation costs are shown to be remarkably low and the implicit barrier is shown to outperform the explicit barrier substantially in most cases. Other potential applications, including object proxying, caching, and relocation, and instrumentation are also discussed.

We present generic extensions to the GCspy visualisation frame-work that make it suitable for tracking the way continuous dynamic memory allocators such as dlmalloc or incremental and concurrent garbage collectors make use of heap memory. These extensions include sample-driven client-server communication, in-cremental stream updates and client-controlled stream update frequency. Additional extensions to the current GCspy client are also described. These include hierarchical driver grouping and hierarchical visualisation, zooming, and the ability to define and view relationships between tiles in different spaces. We also introduce a heuristics engine that is responsible for flipping GCspy from its decoupled 'observation' mode to a synchronous 'single-step' mode, and describe a backtrace facility that can trace the server-side call sequence that led to the triggering of a specified event, such as the allocation or freeing of a block of memory. This enables aspects of the allocator (fragmentation, block ordering, splitting and coalescing policies, etc.) to be understood in the context of a particular application and potential optimisations to be identified. The effectiveness of the enhanced framework is demonstrated with a complete integration with dlmalloc. The framework is evaluated in terms of both performance and its ability to explore contrived modifications to dlmalloc's coalescing policy.

We document the desi n and implementation of a "production" incremental garbage collector for GHC 6.2.It builds on our earlier work (Non-stop Haskell)that exploited GHC's dynamic dispatch mechanism to hijack object code pointers so that objects in to-space automatically scavenge themselves when the mutator attempts to "enter" them. This paper details various optimisations based on code specialisation that remove the dynamic space,and associated time, overheads that accompanied our earlier scheme.We detail important implementation issues and provide a detailed evaluation of a range of design alternatives in comparison with Non-stop Haskell and GHC's current generational collector.We also show how the same code specialisation techniques can be used to eliminate the write barrier in a enerational collector.

Effective exploitation of computational grids can only be achieved when applications are fully integrated with the grid middleware and the underlying computational resources. Fundamental to this exploitation is information. Information about the structure and behaviour of the application, the capability of the computational and networking resources, and the availability and access to these resources by an individual, a group or an organisation. This paper describes an integrated grid environment that is open, extensible and platform independent. We match a high-level application specification, defined as a network of components, to an optimal combination of the currently available component implementations within our grid environment. We demonstrate the effectiveness of this architecture through high-level specification and solution of a set of linear equations by automatic and optimal resource and implementation selection.

We describe an efficient technique for incorporating Baker's incremental garbage collection algorithm into the Spineless Tagless G-machine on stock hardware. This algorithm eliminates the stop/go execution associated with bulk copying collection algorithms, allowing the system to place an upper bound on the pauses due to garbage collection. The technique exploits the fact that objects are always accessed by jumping to code rather than being explicitly dereferenced. It works by modifying the entry code-pointer when an object is in the transient state of being evacuated but not scavenged. An attempt to enter it from the mutator causes the object to "self-scavenge" transparently before resetting its entry code pointer. We describe an implementation of the scheme in v4.01 of the Glasgow Haskell Compiler and report performance results obtained by executing a range of applications. These experiments show that the read barrier can be implemented in dynamic dispatching systems such as the STG-machine with very short mutator pause times and with negligible overhead on execution time.

In this paper we consider the distribution of message transmission times in buffered full cross bar interconnection networks with cyclic arbitration in which the input buffers are serviced in a 'round robin' fashion. The system is modelled as an open queue ing network in which the queues appear at the net work outputs and with the cyclic arbiter being mod elled by queue jumping. We obtain the Laplace Trans form of the transmission time by deriving a condi tional Laplace Transform and solving by the use of a generating function. The density function is then enumerated by numerical inversion and compared with similar results from a simulation model. The analysis is then extended to general service times by modelling each output as a LCFS queue with a suitably modified arrival rate. In the special case of exponential service times, this model is less versatile than the previous one since it only works in the case where the jump probability is fixed. In this case, however, it is shown to produce the same result as the original.

In this paper we describe two types of complex server aggregations which can be used to model collections of components in certain types of parallel computer systems and give a case study showing how the aggregations may be applied in practice. Analytical models of such systems are becoming increasingly important as a means of guiding the often complex design processes, particularly since recent developments in VLSI technology now make it possible to fabricate many paper-designs hitherto impractical for reasons of cost. We argue that aggregations of the type described are essential in the modelling of parallel systems; using the proposed techniques, large numbers of components can be modelled as queue-length-dependent servers within a queueing network in which the number of servers is the same as the number of distinct types of processing element in the system being modelled. Because the number of severs in the model is fixed i.e. is independent of the number of processors, very large multiprocessor systems can be modelled efficiently with no explosion in the size of the state space.