Modern applications generate massive amounts of data that is challenging to process or analyse. Graph algorithms have emerged as a solution for the analysis of such data because they can represent the entities participating in the generation of large-scale datasets in terms of vertices and their relationships in terms of edges. Graph analysis algorithms are used for finding patterns within these relationships, aiming to extract information to be further analysed. The breadth-first search (BFS) is one of the main graph search algorithms used for graph analysis and its optimisation has been widely researched using different parallel computers. However, the parallelisation of BFS has been shown to be challenging because of its inherent characteristics, including irregular memory access patterns, data dependencies and workload imbalance, that limit its scalability. This paper investigates the optimisation of the BFS on the Xeon Phi (Knights Corner), a modern parallel architecture provided with an advanced vector processor supporting the AVX-512 instruction set, using a bespoke development framework integrated with the Graph 500 benchmark. In addition, to demonstrate portability, we show results for a direct port of the algorithms to a more recent version of the Xeon Phi (Knights Landing) and to a Skylake CPU which supports most of the AVX-512 instruction set. Optimised parallel versions of two high-level algorithms for BFS were created using vectorisation, starting with the conventional top-down BFS algorithm and, building on this, a hybrid BFS algorithm. On the KNC our best implementations result in speedups of 1.37x (top-down) and 1.37x (hybrid), for a one million vertices graph, compared to the state-of-the-art. On the KNL and Skylake, the performance is higher than on KNC. In addition, we show results of our best hybrid algorithm on real-world graphs from the SNAP datasets with speedups up to 1.3x on KNC. Performance on KNL and Skylake is again higher, demonstrating the robustness and portability of our algorithm. The hybrid BFS algorithm can be further used to speed up other graph analysis algorithms and the lessons learned from vectorisation can be applied to other algorithms targeting existing and future models of the Xeon Phi and other advanced vector architectures.

As Visual Simultaneous Localisation and Mapping (VSLAM) formulations are increasingly deployed on low-power mobile platforms, it is essential to manage their power consumption in the context of minimal impact on their accuracy or robustness. This is particularly challenging when the runtime changes in motion or scene complexity are unknown in advanced. Further, different VSLAM formulations have different interpretations of the scene, posing a portability challenge for any management techniques. To this effect, we propose a new light-weight runtime adaptation model that relies purely on the change in sensor motion to characterise the tracking difficulty. The model is then used to adapt two general and portable parameters, namely Dynamic Voltage and Frequency Scaling (DVFS) and redundant frame-skipping. The model is evaluated in the context of both direct and indirect keyframe-based VSLAMs (DSO and ORB-SLAM) using scenes from the ICL-NUIM and EuRoC MAV datasets. Our results show a best-case power reduction of 75% with a marginal impact on the accuracy and robustness of the VSLAM formulations over multiple runs, compared to original base real-time versions of the algorithms. Analysis of the scenes showing an impact on robustness indicates that this is caused by critical points in the trajectory, motivating the search an improved characterisation metrics.

Development of application specific accelerators for deep convolutional neural networks (ConvNets) have mainly focussed on accelerating the computationally intensive layers, that is the convolutional layers, to improve performance and energy efficiency. Traditional approaches in this space have relied on handcrafted dataflow implementations to leverage the fine-grained parallelism and data-locality properties within these layers. However, ConvNets layers also have an untapped potential from cross-layer data locality.

As the SLAM research area matures and the number of SLAM systems available increases, the need for frameworks that can objectively evaluate them against prior work grows. This new version of SLAMBench moves beyond traditional visual SLAM, and provides new support for scene understanding and non-rigid environments (dynamic SLAM). More concretely for dynamic SLAM, SLAMBench 3.0 includes the first publicly available implementation of DynamicFusion, along with an evaluation infrastructure. In addition, we include two SLAM systems (one dense, one sparse) augmented with convolutional neural networks for scene understanding, together with datasets and appropriate metrics. Through a series of use-cases, we demonstrate the newly incorporated algorithms, visulation aids and metrics (6 new metrics, 4 new datasets and 5 new algorithms).

We demonstrate the feasibility of undertaking performance evaluations for JVMs using: (1) a hybrid JVM/OS tool, such as async-profiler, (2) OS centric profiling and tracing tools based on Linux perf, and (3) the Extended Berkeley Packet Filter Tracing (eBPF) framework where we demonstrate the rationale behind the standard offwaketime tool, for analysing the causes of blocking latencies, and our own eBPF-based tool bcc-java, that relates changes in microarchitecture performance counter values to the execution of individual JVM and application threads at low overhead.

Energy consumption has been widely studied in the computer architecture field for decades. While the adoption of energy as a metric in machine learning is emerging, the majority of research is still primarily focused on obtaining high levels of accuracy without any computational constraint. We believe that one of the reasons for this lack of interest is due to their lack of familiarity with approaches to evaluate energy consumption. To address this challenge, we present a review of the different approaches to estimate energy consumption in general and machine learning applications in particular. Our goal is to provide useful guidelines to the machine learning community giving them the fundamental knowledge to use and build specific energy estimation methods for machine learning algorithms. We also present the latest software tools that give energy estimation values, together with two use cases that enhance the study of energy consumption in machine learning.

Visual understanding of 3-D environments in real time, at low power, is a huge computational challenge. Often referred to as simultaneous localization and mapping (SLAM), it is central to applications spanning domestic and industrial robotics, autonomous vehicles, and virtual and augmented reality. This paper describes the results of a major research effort to assemble the algorithms, architectures, tools, and systems software needed to enable delivery of SLAM, by supporting applications specialists in selecting and configuring the appropriate algorithm and the appropriate hardware, and compilation pathway, to meet their performance, accuracy, and energy consumption goals. The major contributions we present are: 1) tools and methodology for systematic quantitative evaluation of SLAM algorithms; 2) automated, machine-learning-guided exploration of the algorithmic and implementation design space with respect to multiple objectives; 3) end-to-end simulation tools to enable optimization of heterogeneous, accelerated architectures for the specific algorithmic requirements of the various SLAM algorithmic approaches; and 4) tools for delivering, where appropriate, accelerated, adaptive SLAM solutions in a managed, JIT-compiled, adaptive runtime context.

Real-time dense computer vision and SLAM offer great potential for a new level of scene modelling, tracking and real environmental interaction for many types of robot, but their high computational requirements mean that use on mass market embedded platforms is challenging. Meanwhile, trends in low-cost, low-power processing are towards massive parallelism and heterogeneity, making it difficult for robotics and vision researchers to implement their algorithms in a performance-portable way. In this paper we introduce SLAMBench, a publicly-available software framework which represents a starting point for quantitative, comparable and validatable experimental research to investigate trade-offs in performance, accuracy and energy consumption of a dense RGB-D SLAM system. SLAMBench provides a KinectFusion implementation in C++, OpenMP, OpenCL and CUDA, and harnesses the ICL-NUIM dataset of synthetic RGB-D sequences with trajectory and scene ground truth for reliable accuracy comparison of different implementation and algorithms. We present an analysis and breakdown of the constituent algorithmic elements of KinectFusion, and experimentally investigate their execution time on a variety of multicore and GPU-accelerated platforms. For a popular embedded platform, we also present an analysis of energy efficiency for different configuration alternatives.

Abstract GENIE is a suite of modular Earth System Model components coupled in a variety of configurations used to investigate climate phenomena. As part of the GENIEfyproject, there is a desire to make the activity of coupling GENIE configurations more flexible in order to ease the integration of new components, permit experimentation with alternative model orderings and connectivity, and execute GENIE components in distributed environments. The current coupling framework is inflexible because models are run in a fixed order by a prescriptive main code. This paper shows how the BFG2 (Bespoke Framework Generator—version 2) coupling tool offers significantly more flexibility. Using BFG2, scientists describe GENIE configurations as metadata that can then be transformed automatically into the desired framework. It is demonstrated that BFG2 provides flexibility in composition and deployment, improvements that are brought without modification to the GENIE components, without loss of performance and in a such a manner that it is possible to produce exactly the same results as under the original framework. We also demonstrate how BFG2 may be used to improve the performance of future GENIE coupled models. Copyright © 2008 John Wiley & Sons, Ltd.

Abstract Scientists in many fields rely on computational simulations that are built from a collection of separate, inter‐communicating single models (e.g. Earth System Models often consist of single models of the ocean, atmosphere and land processes); these simulations are called coupled models. Coupled models allow scientists to simulate richer scientific phenomena than is possible by running single models alone. Scientific interest is typically focused on the investigation served by a coupled model, rather than the complex and inadequately supported software engineering activity of constructing it. In response to this lack of support, a coupling methodology called the Flexible Coupling Approach (FCA) has been developed at the University of Manchester together with a tool that implements this approach, the Bespoke Framework Generator (BFG). Whilst being adequate for a large class of coupled models (e.g., many Earth System Models), the BFG is unable to handle coupled models with complex behavioural requirements (in terms of the scheduling and inter‐communication of single models). To capture these more complex expressions of behaviour, this paper introduces NOAH, a domain‐specific language that is implemented in the formalism Communicating Sequential Processes (CSP), and which is used by a new implementation of the FCA, called the CSP‐based Framework Generator (CFG). NOAH is introduced through two example coupled models which have complex behavioural requirements. NOAH represents the first attempt to bring the advantages of using formal descriptions of coupled models to application scientists, providing a language in which to specify coupled model behaviour precisely and the ability to check that a coupled model is deadlock free using tools such as the Failures‐Divergence Refinement (FDR) model checker. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract Coupled modelling is increasingly necessary to make progress in understanding the science of complex physical phenomena and a number of bespoke (‘custom’) coupled solutions to specific scientific challenges have emerged in recent years. These coupled models generally consist of some framework code in which individual models are embedded. The framework code promotes the required interoperation of the models to solve the larger problem being addressed. Bespoke solutions limit the ability of scientists to share models and to couple them together flexibly to produce (efficient) implementations to address new problems. This paper presents an approach, GCF, which addresses several of these limitations. Individual model sharing and flexibility in composition and deployment is achieved by imposing some lightweight development rules for single models and capturing information relating to the models themselves, to their composition into coupled models and to their deployment onto computational resources as machine‐readable metadata. These metadata can be processed to support the generation of an implementation of the coupled model required by the developer. For example, lean and efficient framework code for the specific coupled model and deployment described by the developer can be generated. Alternatively, GCF‐compliant models can be automatically adapted for use within other, existing frameworks. This paper presents the design and implementation of a bespoke framework generator to achieve the former, and the flexibility in the composition of GCF‐compliant models is demonstrated. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract In recent years, there has been increasing interest in the development of computer simulations of complex biological systems, and of multi‐physics and multi‐scale physical phenomena. Applications have been developed that involve the coupling together of separate executable models of individual systems, where these models may have been developed in isolation. A lightweight yet general solution is required to problems of linking coupled models, and of handling the incompatibilities between interacting models that arise from their diverse origins and natures. Many such models require high‐performance computers to provide acceptable execution times, and there is increasing interest in utilizing Grid technologies. However, Grid applications need the ability to cope with heterogeneous and dynamically changing execution environments, particularly where run‐time changes can affect application performance. A general coupling framework (GCF) is described that allows the construction of flexible coupled models. This approach results in a component‐based implementation of a coupled model application. A semi‐formal presentation of GCF is given. Components under GCF are separately deployable and coupled by simple data flows, making them appropriate structures for dynamic execution platforms such as the Grid. The design and initial implementation of a performance control system (PERCO) is reviewed. PERCO acts by redeploying components, and is thus appropriate for controlling GCF coupled model applications. Redeployment decisions in PERCO require performance prediction capabilities. A proof‐of‐concept performance prediction algorithm is presented, based on the descriptions of GCF and PERCO. Copyright © 2005 John Wiley & Sons, Ltd.

Performance analysis is an important step in tuning performance critical applications. It is a cyclic process of measuring and analyzing performance data which is driven by the programmers hypotheses on potential performance problems. Currently this process is controlled manually by the programmer. The implicit knowledge applied in this cyclic process must be formalized in order to be reused in the automation of performance analysis tools. This article describes the performance property specification language ASL developed in the APART Esprit IV working group. ASL allows the specification of performance data via an object model and of performance properties via a specially designed notation. Performance bottlenecks can then be identified based on the specification since bottlenecks are viewed as performance properties with a huge negative impact. We present the ASL language in the context of MPI applications.

Article Free Access Share on Performance improvement through overhead analysis: a case study in molecular dynamics Authors: Graham D. Riley Centre for Novel Computing, University of Manchester, Oxford Road, Manchester M13 9PL, United Kingdom Centre for Novel Computing, University of Manchester, Oxford Road, Manchester M13 9PL, United KingdomView Profile , J. Mark Bull Centre for Novel Computing, University of Manchester, Oxford Road, Manchester M13 9PL, United Kingdom Centre for Novel Computing, University of Manchester, Oxford Road, Manchester M13 9PL, United KingdomView Profile , John R. Gurd Centre for Novel Computing, University of Manchester, Oxford Road, Manchester M13 9PL, United Kingdom Centre for Novel Computing, University of Manchester, Oxford Road, Manchester M13 9PL, United KingdomView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 36–43https://doi.org/10.1145/263580.263589Published:11 July 1997Publication History 12citation261DownloadsMetricsTotal Citations12Total Downloads261Last 12 Months6Last 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 SiteeReaderPDF

The SDEM code models systems of interacting blocks of rock using the distinct element (DE) method, which represents these systems as discontinuums with each block acting under Newton's laws of motion. The data structures associated with the DE method make the task of obtaining performance gains through vectorisation difficult. Typical systems, however, contain thousands of blocks and there is the potential to perform calculations associated with groups of blocks in parallel.