Search

Exact combinatorial search is essential to a wide range of important applications, and there are many large problems that need to be solved quickly. Searches are extremely challenging to parallelise due to a combination of factors, e.g. searches are non-deterministic, dynamic pruning changes the workload, and search tasks have very different runtimes. YewPar is a C++/HPX framework that generalises parallel search by providing a range of sophisticated search skeletons.This paper demonstrates generic high performance combinatorial search, i.e. that a variety of exact combinatorial searches can be easily parallelised for HPC using YewPar. We present a new mechanism for profiling key aspects of YewPar parallel combinatorial search, and demonstrate its value. We exhibit, for the first time, generic exact combinatorial searches at HPC scale. We baseline YewPar against state-of-the-art sequential C++ and C++/OpenMP implementations. We demonstrate that deploying YewPar on an HPC system can dramatically reduce the runtime of large problems, e.g. from days to just 100s. The maximum relative speedups we achieve for an enumeration search are near-linear up to 195(6825) compute-nodes(workers), super-linear for an optimisation search on up to 128(4480) (pruning reduces the workload), and sub-linear for decision searches on up to 64(2240) compute-nodes(workers).

Internet of Things (IoT) software is notoriously complex, conventionally comprising multiple tiers. Traditionally an IoT developer must use multiple programming languages and ensure that the components interoperate correctly. A novel alternative is to use a single tierless language with a compiler that generates the code for each component and ensures their correct interoperation. We report a systematic comparative evaluation of two tierless language technologies for IoT stacks: one for resource-rich sensor nodes (Clean with iTask) and one for resource-constrained sensor nodes (Clean with iTask and mTask). The evaluation is based on four implementations of a typical smart campus application: two tierless and two Python-based tiered. (1) We show that tierless languages have the potential to significantly reduce the development effort for IoT systems, requiring 70% less code than the tiered implementations. Careful analysis attributes this code reduction to reduced interoperation (e.g., two embedded domain-specific languages and one paradigm versus seven languages and two paradigms), automatically generated distributed communication, and powerful IoT programming abstractions. (2) We show that tierless languages have the potential to significantly improve the reliability of IoT systems, describing how Clean iTask/mTask maintains type safety, provides higher-order failure management, and simplifies maintainability. (3) We report the first comparison of a tierless IoT codebase for resource-rich sensor nodes with one for resource-constrained sensor nodes. The comparison shows that they have similar code size (within 7%), and functional structure. (4) We present the first comparison of two tierless IoT languages, one for resource-rich sensor nodes and the other for resource-constrained sensor nodes.

Modern multi-robot systems often need to solve computationally intensive tasks but operate with limited compute resources and in the presence of failures. Cooperating to share computational tasks between robots at the edge reduces execution time. We introduce and evaluate a new computation load management technology for teams of robots: Reliable Autonomous Mobile Programs (RAMPs). RAMPs use information about the computational resources available in the team and a cost model to decide where to execute. RAMPs are implemented in ROS on a collection of Raspberry Pi-based robots. The performance of RAMPs is evaluated using route planning, a typical computationally-intensive robotics application. A systematic study of RAMPs demonstrates a high likelihood of optimal or near-optimal distribution and hence efficient resource utilisation. RAMPs successfully complete in the presence of simultaneous, or successive, robot failures and network failures, while preserving near-optimal distribution.

As the number of cores increases Non-Uniform Memory Access (NUMA) is becoming increasingly prevalent in general purpose machines. Effectively exploiting NUMA can significantly reduce memory access latency and thus runtime by 10-20%, and profiling provides information on how to optimise. Language-level NUMA profilers are rare, and mostly profile conventional languages executing on Virtual Machines. Here we profile, and develop new NUMA profilers for, a functional language executing on a runtime system.\ud \ud We start by using existing OS and language level tools to systematically profile 8 benchmarks from the GHC Haskell nofib suite on a typical NUMA server (8 regions, 64 cores). We propose a new metric: NUMA access rate that allows us to compare the load placed on the memory system by different programs, and use it to contrast the benchmarks. We demonstrate significant differences in NUMA usage between computational and data-intensive benchmarks, e.g. local memory access rates of 23% and 30% respectively. We show that small changes to coordination behaviour can significantly alter NUMA usage, and for the first time quantify the effectiveness of the GHC 8.2 NUMA adaption.\ud \ud We identify information not available from existing profilers and extend both the numaprof profiler, and the GHC runtime system to obtain three new NUMA profiles: OS thread allocation locality, GC count (per region and generation) and GC thread locality. The new profiles not only provide a deeper understanding of program memory usage, they also suggest ways that GHC can be adapted to better exploit NUMA architectures.

Execution times may be reduced by offloading parallel loop nests to a GPU. Auto-parallelizing compilers are common for static languages, often using a cost model to determine when the GPU execution speed will outweigh the offload overheads. Nowadays scientific software is increasingly written in dynamic languages and would benefit from compute accelerators. The ALPyNA framework analyses moderately complex Python loop nests and automatically JIT compiles code for heterogeneous CPU and GPU architectures.\ud \ud We present the first analytical cost model for auto-parallelizing loop nests in a dynamic language on heterogeneous architectures. Predicting execution time in a language like Python is extremely challenging, since aspects like the element types, size of the iteration space, and amenability to parallelization can only be determined at runtime. Hence the cost model must be both staged, to combine compile and run-time information, and lightweight to minimize runtime overhead. GPU execution time prediction must account for factors like data transfer, block-structured execution, and starvation.\ud \ud We show that a comparatively simple, staged analytical model can accurately determine during execution when it is profitable to offload a loop nest. We evaluate our model on three heterogeneous platforms across 360 experiments with 12 loop-intensive Python benchmark programs. The results show small misprediction intervals and a mean slowdown of just 13.6%, relative to the optimal (oracular) offload strategy.

Combinatorial search is central to many applications, yet the huge irregular search trees and the need to respect search heuristics make it hard to parallelise. We aim to improve the reuse of intricate parallel search implementations by providing the first general purpose scalable parallel framework for exact combinatorial search, YewPar.\ud \ud We make the following contributions. (1) We present a novel formal model of parallel backtracking search, covering enumeration, decision, and optimisation search. (2) We introduce Lazy Node Generators as a uniform API for search tree generation. (3) We present the design and implementation of 12 widely applicable algorithmic skeletons for tree search on shared and distributed memory architectures. (4) Uniquely in the field we demonstrate how a wide range of parallel search applications can easily be constructed by composing Lazy Node Generators and the search skeletons. (5) We report a systematic performance analysis of all 12 YewPar skeletons on standard instances of 7 search applications, investigating skeleton overheads and scalability up to 255 workers on 17 distributed locations.

Combinatorial search is central to many applications yet\ud hard to parallelise. We argue for improving the reuse of parallel searches,\ud and present the design and implementation of a new parallel search\ud framework. YewPar generalises search by abstracting search tree generation, and by providing algorithmic skeletons that support three search\ud types, together with a set of search coordination strategies. The evaluation shows that the cost of YewPar generality is low (6.1%); global\ud knowledge is inexpensively shared between workers; irregular tasks are\ud effectively distributed; and YewPar delivers good runtimes, speedups and\ud efficiency with up to 255 workers on 17 localities

Servers are a key element of current IT infrastructures, and must often deal with large numbers of concurrent requests. The programming language used to construct the server has an important role in engineering efficient server software, and must support massive concurrency on multicore machines with low communication and synchronisation overheads.\ud \ud This paper investigates 12 highly concurrent programming languages suitable for engineering servers, and analyses three representative languages in detail: Erlang, Go, and Scala with Akka. We have designed three server benchmarks that analyse key performance characteristics of the languages. The benchmark results suggest that where minimising message latency is crucial, Go and Erlang are best; that Scala with Akka is capable of supporting the largest number of dormant processes; that for servers that frequently spawn processes Erlang and Go minimise creation time; and that for constantly communicating processes Go provides the best throughput.

Combinatorial search problems in mathematics, e.g. in finite geometry, are notoriously hard; a state-of-the-art backtracking search algorithm can easily take months to solve a single problem. There is clearly demand for parallel combinatorial search algorithms scaling to hundreds of cores and beyond. However, backtracking combinatorial searches are challenging to parallelise due to their sensitivity to search order and due to the their irregularly shaped search trees. Moreover, scaling parallel search to hundreds of cores generally requires highly specialist parallel programming expertise.\ud \ud This paper proposes a generic scalable framework for solving hard combinatorial problems. Key elements are distributed memory task parallelism (to achieve scale), work stealing (to cope with irregularity), and generic algorithmic skeletons for combinatorial search (to reduce the parallelism expertise required). We outline two implementations: a mature Haskell Tree Search Library (HTSL) based around algorithmic skeletons and a prototype C++ Tree Search Library (CTSL) that uses hand coded applications.\ud \ud Experiments on maximum clique problems and on a problem in finite geometry, the search for spreads in H(4,2^2), show that (1) CTSL consistently outperforms HTSL on sequential runs, and (2) both libraries scale to 200 cores, e.g. speeding up spreads search by a factor of 81 (HTSL) and 60 (CTSL), respectively. This demonstrates the potential of our generic framework for scaling parallel combinatorial search to large distributed memory platforms.

Distributed actor languages are an effective means of constructing scalable reliable systems, and the Erlang programming language has a well-established and influential model. While the Erlang model conceptually provides reliable scalability, it has some inherent scalability limits and these force developers to depart from the model at scale. This article establishes the scalability limits of Erlang systems and reports the work of the EU RELEASE project to improve the scalability and understandability of the Erlang reliable distributed actor model. We systematically study the scalability limits of Erlang and then address the issues at the virtual machine, language, and tool levels. More specifically: (1) We have evolved the Erlang virtual machine so that it can work effectively in large-scale single-host multicore and NUMA architectures. We have made important changes and architectural improvements to the widely used Erlang/OTP release. (2) We have designed and implemented Scalable Distributed (SD) Erlang libraries to address language-level scalability issues and provided and validated a set of semantics for the new language constructs. (3) To make large Erlang systems easier to deploy, monitor, and debug, we have developed and made open source releases of five complementary tools, some specific to SD Erlang. Throughout the article we use two case studies to investigate the capabilities of our new technologies and tools: a distributed hash table based Orbit calculation and Ant Colony Optimisation (ACO). Chaos Monkey experiments show that two versions of ACO survive random process failure and hence that SD Erlang preserves the Erlang reliability model. While we report measurements on a range of NUMA and cluster architectures, the key scalability experiments are conducted on the Athos cluster with 256 hosts (6,144 cores). Even for programs with no global recovery data to maintain, SD Erlang partitions the network to reduce network traffic and hence improves performance of the Orbit and ACO benchmarks above 80 hosts. ACO measurements show that maintaining global recovery data dramatically limits scalability; however, scalability is recovered by partitioning the recovery data. We exceed the established scalability limits of distributed Erlang, and do not reach the limits of SD Erlang for these benchmarks at this scale (256 hosts, 6,144 cores).

Tracing JIT compilation generates units of compilation that are easy to analyse and are known to execute frequently. The AJITPar project investigates whether the information in JIT traces can be used to dynamically transform programs for a specific parallel architecture. Hence a lightweight cost model is required for JIT traces.\ud \ud This paper presents the design and implementation of a system for extracting JIT trace information from the Pycket JIT compiler. We define three increasingly parametric cost models for Pycket traces. We determine the best weights for the cost model parameters using linear regression. We evaluate the effectiveness of the cost models for predicting the relative costs of transformed programs.

The proliferation of widely available, but very different, parallel\ud architectures makes the ability to deliver good parallel performance\ud on a range of architectures, or performance portability, highly\ud desirable. Irregular parallel problems, where the number and size\ud of tasks is unpredictable, are particularly challenging and require\ud dynamic coordination.\ud The paper outlines a novel approach to delivering portable\ud parallel performance for irregular parallel programs. The approach\ud combines JIT compiler technology with dynamic scheduling and\ud dynamic transformation of declarative parallelism.\ud We specify families of algorithmic skeletons plus equations\ud for rewriting skeleton expressions. We present the design of a\ud framework that unfolds skeletons into task graphs, dynamically\ud schedules tasks, and dynamically rewrites skeletons, guided by a\ud lightweight JIT trace-based cost model, to adapt the number and\ud granularity of tasks for the architecture.\ud We outline the system architecture and prototype implementation\ud in Racket/Pycket. As the current prototype does not yet automatically\ud perform dynamic rewriting we present results based on manual\ud offline rewriting, demonstrating that (i) the system scales to hundreds\ud of cores given enough parallelism of suitable granularity, and\ud (ii) the JIT trace cost model predicts granularity accurately enough\ud to guide rewriting towards a good adaptive transformation.

Symbolic computation has underpinned a number of key advances in Mathematics and Computer Science. Applications are typically large and potentially highly parallel, making them good candidates for parallel execution at a variety of scales from multi-core to high-performance computing systems. However, much existing work on parallel computing is based around numeric rather than symbolic computations. In particular, symbolic computing presents particular problems in terms of varying granularity and irregular task sizes that do not match conventional approaches to parallelisation. It also presents problems in terms of the structure of the algorithms and data. This paper describes a new implementation of the free open-source GAP computational algebra system that places parallelism at the heart of the design, dealing with the key scalability and cross-platform portability problems. We provide three system layers that deal with the three most important classes of hardware: individual shared memory multi-core nodes, mid-scale distributed clusters of multi-core nodes and full-blown high-performance computing systems, comprising large-scale tightly connected networks of multi-core nodes. This requires us to develop new cross-layer programming abstractions in the form of new domain-specific skeletons that allow us to seamlessly target different hardware levels. Our results show that, using our approach, we can achieve good scalability and speedups for two realistic exemplars, on high-performance systems comprising up to 32000 cores, as well as on ubiquitous multi-core systems and distributed clusters. The work reported here paves the way towards full-scale exploitation of symbolic computation by high-performance computing systems, and we demonstrate the potential with two major case studies. © 2016 The Authors. Concurrency and Computation: Practice and Experience Published by John Wiley & Sons Ltd.

As the number of cores grows in commodity architectures so does the likelihood of failures. A distributed actor model potentially facilitates the development of reliable and scalable software on these architectures. Key components include lightweight processes which 'share nothing' and hence can fail independently. Erlang is not only increasingly widely used, but the underlying actor model has been a beacon for programming language design, influencing for example Scala, Clojure and Cloud Haskell.While the Erlang distributed actor model is inherently scalable, we demonstrate that it is limited by some pragmatic factors. We address two network scalability issues here: globally registered process names must be updated on every node (virtual machine) in the system, and any Erlang nodes that communicate maintain an active connection. That is, there is a fully connected O ( n 2 ) network of n nodes.We present the design, implementation, and initial evaluation of a conservative extension of Erlang - Scalable Distributed (SD) Erlang. SD Erlang partitions the global namespace and connection network using s_groups. An s_group is a set of nodes with its own process namespace and with a fully connected network within the s_group, but only individual connections outside it. As a node may belong to more than one s_group it is possible to construct arbitrary connection topologies like trees or rings.We present an operational semantics for the s_group functions, and outline the validation of conformance between the implementation and the semantics using the QuickCheck automatic testing tool. Our preliminary evaluation in comparison with distributed Erlang shows that SD Erlang dramatically improves network scalability even if the number of global operations is tiny (0.01%). Moreover, even in the absence of global operations the reduced connection maintenance overheads mean that SD Erlang scales better beyond 80 nodes (1920 cores). We address the network scalability limitations of distributed Erlang.We present the design and implementation of Scalable Distributed Erlang.We give a semantics for scalable groups and validate the implementation against it.We provide a preliminary evaluation of distributed Erlang and SD Erlang performance.The performance evaluation shows that introducing s_groups improves the scalability.

Erlang has world leading reliability capabilities, but while it scales\ud extremely well within a single node, distributed Erlang has some\ud scalability issues. The Scalable Distributed (SD) Erlang libraries\ud have been designed to address the scalability limitations while\ud preserving the reliability model, and shown to deliver significant\ud performance benefits above 40 hosts using some relatively simple\ud benchmarks.\ud This paper compares the reliability and scalability of SD Erlang\ud and distributed Erlang using an Instant Messaging (IM) server\ud benchmark that is a far more typical Erlang application; a relatively\ud large and sophisticated benchmark; has throughput as the key\ud performance metric; and uses non-trivial reliability mechanisms.\ud We provide a careful reliability evaluation using chaos monkey.\ud The key performance results consider scenarios with and without\ud failures on up to 17 server hosts (272 cores). We show that SD\ud Erlang adds no performance overhead when all nodes are grouped in\ud a single s_group. However, either adding redundant router nodes in\ud distributed Erlang applications, or dividing a set of nodes into small\ud s_groups in SD Erlang applications, have small negative impact.\ud Both the distributed Erlang and SD Erlang IM tolerate failures and,\ud up to the failure rates measured, the failures have no impact on\ud throughput. The IM implementations show that SD Erlang preserves\ud the distributed Erlang reliability properties and mechanisms.

Reliability is set to become a major concern on emergent large-scale architectures. While there are many parallel languages, and indeed many parallel functional languages, very few address reliability. The notable exception is the widely emulated Erlang distributed actor model that provides explicit supervision and recovery of actors with isolated state. We investigate scalable transparent fault tolerant functional computation with automatic supervision and recovery of tasks. We do so by developing HdpH-RS, a variant of the Haskell distributed parallel Haskell (HdpH) DSL with Reliable Scheduling. Extending the distributed work stealing protocol of HdpH for task supervision and recovery is challenging. To eliminate elusive concurrency bugs, we validate the HdpH-RS work stealing protocol using the SPIN model checker. HdpH-RS differs from the actor model in that its principal entities are tasks, i.e. independent stateless computations, rather than isolated stateful actors. Thanks to statelessness, fault recovery can be performed automatically and entirely hidden in the HdpH-RS runtime system. Statelessness is also key for proving a crucial property of the semantics of HdpH-RS: fault recovery does not change the result of the program, akin to deterministic parallelism. HdpH-RS provides a simple distributed fork/join-style programming model, with minimal exposure of fault tolerance at the language level, and a library of higher level abstractions such as algorithmic skeletons. In fact, the HdpH-RS DSL is exactly the same as the HdpH DSL, hence users can opt in or out of fault tolerant execution without any refactoring. Computations in HdpH-RS are always as reliable as the root node, no matter how many nodes and cores are actually used. We benchmark HdpH-RS on conventional clusters and an High Performance Computing platform: all benchmarks survive Chaos Monkey random fault injection; the system scales well e.g. up to 1,400 cores on the High Performance Computing; reliability and recovery overheads are consistently low even at scale.

The Robot Operating System (ROS) is the de facto standard platform\ud for modern robots. However, communication between ROS nodes\ud has scalability and reliability issues in practice. In this paper, we\ud investigate whether Erlang’s lightweight concurrency and reliability\ud mechanisms have the potential to address these issues. The basis\ud of the investigation is a pair of simple but typical robotic control\ud applications, namely two face-trackers: one using ROS publish/subscribe\ud messaging, and the other a bespoke Erlang communication\ud framework.\ud We report experiments that compare five key aspects of the\ud ROS and Erlang face trackers. We find that Erlang communication\ud scales better, supporting at least 3.5 times more active processes\ud (700 processes) than its ROS-based counterpart (200 nodes) while\ud consuming half of the memory. However, while both face tracking\ud prototypes exhibit similar detection accuracy and transmission\ud latencies with 10 or fewer workers, Erlang exhibits a continuous\ud increase in the total time taken to process a frame as more agents\ud are added, and we identify the cause. A reliability study shows\ud that while both ROS and Erlang restart failed computations, the\ud Erlang processes restart 1000–1500 times faster than ROS nodes,\ud reducing robot component downtime and mitigating the impact of\ud the failures.

General purpose computing architectures are evolving quickly to become many-core and hierarchical: i.e. a core can communicate more quickly locally than globally. To be effective on such architectures programming models must be aware of the communication hierarchy, and yet preserve performance portability.We propose four new architecture-aware constructs for the parallel Haskell extension GpH that exploit information about task size and aim to reduce communication for small tasks, preserve data locality, or to distribute large units of work. We report a preliminary investigation of architecture-aware programming models that abstract over the new constructs. In particular we propose architecture-aware evaluation strategies and skeletons. We investigate three common parallel paradigms on hierarchical architectures with up to 224 cores. The results show that the architecture–aware constructs consistently deliver better speedup and scalability than existing constructs together with dramatically reduced variability. In some experiments speedup is improved by an order of magnitude.

Autonomous mobile programs (AMPs) offer a novel decentralised load management technology where periodic use is made of cost models to decide where to execute in a network. In this paper we demonstrate how sequential programs can be automatically converted into AMPs. The AMPs are generated by an automatic continuation cost analyser that replaces iterations with costed autonomous mobility skeletons (CAMS) that encapsulate autonomous mobility. The CAMS cost model uses an entirely novel continuation cost semantics to predict both the cost of the current iteration and the continuation cost of the remainder of the program. We show that CAMS convey significant performance advantages, e.g. reducing execution time by up to 53%; that the continuation cost models are consistent with the existing AMP cost models; and that the overheads of collecting and utilising the continuation costs are relatively small. We discuss example AMPs generated by the analyser and demonstrate that they have very similar performance to hand-costed CAMS programs.

Computational GRIDs potentially offer low-cost, readily available, and large-scale high-performance platforms. For the parallel execution of programs, however, computational GRIDs pose serious challenges: they are heterogeneous and have hierarchical and often shared interconnects, with high and variable latencies between clusters. This paper investigates whether a programming language with high-level parallel coordination and a distributed shared memory (DSM) model can deliver good and scalable performance on a range of computational GRID configurations. The high-level language Glasgow parallel Haskell (GpH) abstracts over the architectural complexities of the computational GRID, and we have developed GRID-GUM2, a sophisticated grid-specific implementation of GpH, to produce the first high-level DSM parallel language implementation for computational Grids. We report a systematic performance evaluation of GRID-GUM2 on combinations of high/low and homogeneous/heterogeneous computational GRIDS. We measure the performance of a small set of kernel parallel programs representing a variety of application areas, two parallel paradigms, and ranges of communication degree and parallel irregularity. We investigate GRID-GUM2's performance scalability on medium-scale heterogeneous and high-latency computational GRIDs and analyze the performance with respect to the program characteristics of communication frequency and degree of irregular parallelism.

Clustering is a descriptive data mining task aiming to group the data into homogeneous groups. This paper presents a novel evolutionary algorithm (NOCEA) that efficiently and effectively clusters massive numerical databases. NOCEA evolves individuals of variable-length consisting of disjoint and axis-aligned hyper-rectangular rules with homogeneous data distribution. The antecedent part of the rules includes an interval-like condition for each dimension. A novel quantisation algorithm imposes a regular multi-dimensional grid structure onto the data space to reduce the search combinations. Due to quantisation the boundaries of the intervals are encoded as integer values. The evolutionary search is guided by a simple data coverage maximisation function. The enormous data space is effectively explored by task-specific recombination and mutation operators producing candidate solutions with no overlapping rules. A parsimony generalisation operator shortens the discovered knowledge by replacing adjacent rules with more generic ones. NOCEA employs a special homogeneity operator that enforces quasi-uniform data distribution in the space enclosed by the candidate rules. After convergence the discovered knowledge undergoes simplification to perform subspace clustering, and to assemble the clusters. Results using real-world datasets are included to show that NOCEA has several attractive properties for clustering including: (a) comprehensible output in the form of disjoint and homogeneous rules, (b) the ability to discover clusters of arbitrary shape, density, size, and data coverage, (c) ability to perform effective subspace clustering, (d) near linear scalability with the database size, data and cluster dimensionality, and (e) substantial potential for task parallelism (speedup of 13.8 on 16 processors). A real-world example is a detailed study of the seismicity along the African-Eurasian-Arabian plate boundaries.

We consider the problem of adapting distributed Erlang applications to large or heterogeneous architectures to achieve good performance in a portable way. In many architectures, and especially large architectures, the communication latency between pairs of virtual machines (nodes) is no longer uniform.\ud \ud We propose two language-level methods that enable programs to automatically adapt to heterogeneity and non-uniform communication latencies, and both provide information enabling a program to identify an appropriate node when spawning a process. We provide a means of recording node attributes describing the hardware and software capabilities of nodes, and mechanisms that allow an application to examine the attributes of remote nodes. We provide an abstraction of communication distances that enables an application to select nodes to facilitate efficient communication.\ud \ud We have developed open source libraries that implement these ideas. We show that the use of attributes for node selection can lead to significant performance improvements if different components of the application have different processing requirements. We report a detailed empirical investigation of non-uniform communication times in several representative architectures, and show that our abstract model provides a good description of the hierarchy of communication times.

Naira is a compiler for Haskell, written in Glasgow parallel Haskell. It exhibits modest, but irregular, parallelism that is determined by properties of the program being compiled, e.g. the complexity of the types and of the pattern matching. We report four experiments into Naira's parallel behaviour using a set of realistic inputs: namely the 18 Haskell modules of Naira itself. The issues investigated are: • Does increasing input size improve sequential efficiency and speedup? • To what extent do high communications latencies reduce average parallelism and speedup? • Does migrating running threads between processors improve average parallelism and speedup at all latencies?

The statelessness of functional computations facilitates both parallelism and fault recovery. Faults and non-uniform communication topologies are key challenges for emergent large scale parallel architectures. We report on HdpH and HdpH-RS , a pair of Haskell DSLs designed to address these challenges for irregular task-parallel computations on large distributed-memory architectures. Both DSLs share an API combining explicit task placement with sophisticated work stealing. HdpH focuses on scalability by making placement and stealing topology aware whereas HdpH-RS delivers reliability by means of fault tolerant work stealing. We present operational semantics for both DSLs and investigate conditions for semantic equivalence of HdpH and HdpH-RS programs, that is, conditions under which topology awareness can be transparently traded for fault tolerance. We detail how the DSL implementations realise topology awareness and fault tolerance. We report an initial evaluation of scalability and fault tolerance on a 256-core cluster and on up to 32K cores of an HPC platform.

We describe the first ever parallelisation of an algebraic computation at modern HPC scale. Our case study poses challenges typical of the domain: it is a multi-phase application with dynamic task creation and irregular parallelism over complex control and data structures.\ud \ud Our starting point is a sequential algorithm for finding invariant bilinear forms in the representation theory of Hecke algebras, implemented in the GAP computational group theory system. After optimising the sequential code we develop a parallel algorithm that exploits the new skeleton-based SGP2 framework to parallelise the three most computationally-intensive phases. To this end we develop a new domain-specific skeleton, parBufferTryReduce. We report good parallel performance both on a commodity cluster and on a national HPC, delivering speedups up to 548 over the optimised sequential implementation on 1024 cores.

Erlang is a functional language with a much-emulated model for building reliable distributed systems. This paper outlines the RELEASE project, and describes the progress in the first six months. The project aim is to scale the Erlang's radical concurrency-oriented programming paradigm to build reliable general-purpose software, such as server-based systems, on massively parallel machines. Currently Erlang has inherently scalable computation and reliability models, but in practice scalability is constrained by aspects of the language and virtual machine. We are working at three levels to address these challenges: evolving the Erlang virtual machine so that it can work effectively on large scale multicore systems; evolving the language to Scalable Distributed SD Erlang; developing a scalable Erlang infrastructure to integrate multiple, heterogeneous clusters. We are also developing state of the art tools that allow programmers to understand the behaviour of massively parallel SD Erlang programs. We will demonstrate the effectiveness of the RELEASE approach using demonstrators and two large case studies on a Blue Gene.

We present the results of the first four years of the European research project SCIEnce-Symbolic Computation Infrastructure in Europe (http://www.symbolic-computing.org), which aims to provide key infrastructure for symbolic computation research. A primary outcome of the project is that we have developed a new way of combining computer algebra systems using the Symbolic Computation Software Composability Protocol (SCSCP), in which both protocol messages and data are encoded in the OpenMath format. We describe the SCSCP middleware and APIs, outline implementations for various Computer Algebra Systems (CAS), and show how SCSCP-compliant components may be combined to solve scientific problems that cannot be solved within a single CAS, or may be organised into a system for distributed parallel computations. Additionally, we present several domain-specific parallel skeletons that capture commonly used symbolic computations. To ease use and to maximise inter-operability, these skeletons themselves are provided as SCSCP services and take SCSCP services as arguments.

The many core revolution makes scalability a key property. The RELEASE project aims to improve the scalability of Erlang on emergent commodity architectures with 100,000 cores. Such architectures require scalable and available persistent storage on up to 100 hosts. We enumerate the requirements for scalable and available persistent storage, and evaluate four popular Erlang DBMSs against these requirements. This analysis shows that Mnesia and CouchDB are not suitable persistent storage at our target scale, but Dynamo-like NoSQL DataBase Management Systems (DBMSs) such as Cassandra and Riak potentially are. We investigate the current scalability limits of the Riak 1.1.1 NoSQL DBMS in practice on a 100-node cluster. We establish for the first time scientifically the scalability limit of Riak as 60 nodes on the Kalkyl cluster, thereby confirming developer folklore. We show that resources like memory, disk, and network do not limit the scalability of Riak. By instrumenting Erlang/OTP and Riak libraries we identify a specific Riak functionality that limits scalability. We outline how later releases of Riak are refactored to eliminate the scalability bottlenecks. We conclude that Dynamo-style NoSQL DBMSs provide scalable and available persistent storage for Erlang in general, and for our RELEASE target architecture in particular.

Symbolic computation is an important area of both Mathematics and Computer Science, with many large computations that would benefit from parallel execution. Symbolic computations are, however, challenging to parallelise as they have complex data and control structures, and both dynamic and highly irregular parallelism. The SymGridPar framework (SGP) has been developed to address these challenges on small-scale parallel architectures. However the multicore revolution means that the number of cores and the number of failures are growing exponentially, and that the communication topology is becoming increasingly complex. Hence an improved parallel symbolic computation framework is required. This paper presents the design and initial evaluation of SymGridPar2 (SGP2), a successor to SymGridPar that is designed to provide scalability onto 10 5 cores, and hence also provide fault tolerance. We present the SGP2 design goals, principles and architecture. We describe how scalability is achieved using layering and by allowing the programmer to control task placement. We outline how fault tolerance is provided by supervising remote computations, and outline higher-level fault tolerance abstractions. We describe the SGP2 implementation status and development plans. We report the scalability and efficiency, including weak scaling to about 32,000 cores, and investigate the overheads of tolerating faults for simple symbolic computations.

The manycore revolution is steadily increasing the performance and size of massively parallel systems, to the point where system reliability becomes a pressing concern. Therefore, massively parallel compute jobs must be able to tolerate failures. For example, in the HPC-GAP project we aim to coordinate symbolic computations in architectures with 106 cores. At that scale, failures are a real issue. Functional languages are well known for advantages both for parallelism and for reliability, e.g. stateless computations can be scheduled and replicated freely. This paper presents a software level reliability mechanism, namely supervised fault tolerant workpools implemented in a Haskell DSL for parallel programming on distributed memory architectures. The workpool hides task scheduling, failure detection and task replication from the programmer. To the best of our knowledge, this is a novel construct. We demonstrate how to abstract over supervised workpools by providing fault tolerant instances of existing algorithmic skeletons. We evaluate the runtime performance of these skeletons both in the presence and absence of faults, and report low supervision overheads.

Distributed load balancers exhibit thrashing where tasks are repeatedly moved between locations due to incomplete global load information. This paper shows that systems of autonomous mobile programs (AMPs) exhibit the same behaviour, and identifies two types of redundant movement (greedy effect). AMPs are unusual in that, in place of some external load management system, each AMP periodically recalculates network and program parameters and may independently move to a better execution environment. Load management emerges from the behaviour of collections of AMPs.\ud \ud The paper explores the extent of greedy effects by simulating collections of AMPs and proposes negotiating AMPs (NAMPs) to ameliorate the problem. We present the design of AMPs with a competitive negotiation scheme (cNAMPs), and compare their performance with AMPs by simulation. We establish new properties of balanced networks of AMPs, and use these to provide a theoretical analysis of greedy effects.

Distributed load managers exhibit thrashing where tasks are repeatedly moved between locations due to incomplete global load information. This paper shows that systems of Autonomous Mobile Programs (AMPs) exhibit the same behaviour, identifying two types of redundant movement and terming them greedy effects. AMPs are unusual in that, in place of some external load management system, each AMP periodically recalculates network and program parameters and may independently move to a better execution environment. Load management emerges from the behaviour of collections of AMPs. The paper explores the extent of greedy effects by simulation, and then proposes negotiating AMPs (NAMPs) to ameliorate the problem. We present the design of AMPs with a competitive negotiation scheme (cNAMPs), and compare their performance with AMPs by simulation.

An important application of resource analysis is to improve the performance of parallel and distributed programs. In this context key resources are time, space and communication. Given the spectrum of cost models and associated analysis techniques available, what combination should be selected for a specific parallel or distributed context? We address the question as follows. We outline a continuum of coordination cost models and a range of analysis techniques. We consider six representative parallel/distributed applications of resource analysis techniques, and aim to extract general principles governing why the combination of techniques is effective in its context.

This paper describes a very high-level approach that aims to orchestrate sequential components written using high-level domain-specific programming into high-performance parallel applications. By achieving this goal, we hope to make parallel programming more accessible to experts in mathematics, engineering and other domains. A key feature of our approach is that parallelism is achieved without any modification to the underlying sequential computational algebra systems, or to the user-level components: rather, all orchestration is performed at an outer level, with sequential components linked through a standard communication protocol, the Symbolic Computing Software Composability Protocol, SCSCP. Despite the generality of our approach, our results show that we are able to achieve very good, and even, in some cases, super-linear, speedups on clusters of commodity workstations: up to a factor of 33.4 on a 28-processor cluster. We are, moreover, able to parallelise a wider variety of problem, and achieve higher performance than typical specialist parallel computational algebra implementations.

In a mobile language, computations can move between locations in a network to better utilise resources, e.g., as in a computational GRID. Mobile Haskell, or mHaskell, is a small extension of Concurrent Haskell that enables the construction of distributed mobile software by introducing higher order communication channels called Moble Channels (MChannels). mHaskell only provides weak mobility, i.e. the ability to start new computations on remote locations. This paper shows how strong mobility, i.e. the ability to migrate running threads between locations, can be implemented in a language like mHaskell with weak mobility, higher-order channels and first-class continuations. Using Haskell's high level features, such as higher-order functions, type classes and support for monadic programming, strong mobility is achieved without any changes to the runtime system, or built-in support for continuations. Strong mobility is illustrated with examples and a mobile agent case study.

To manage load on large and dynamic networks we propose Autonomous Mobile Programs (AMPs) that periodically use a cost model to decide where to execute in the network. Unusually this form of autonomous mobility affects only where the program executes and not what it does. We present a generic AMP cost model, together with a validated instantiation and comparative performance results for two AMPs. Experiments on a homogeneous network show that collections of AMPs quickly obtain and maintain optimal or near-optimal balance. The advantages of our decentralised approach are scalability to very large and dynamic networks, improved balance, and guaranteed maximum overhead. The disadvantages are higher overheads and the necessity of both a cost model and explicit mobility control.

We provide a complete description of mHaskell, a new mobile programming language that extends the Haskell functional language. We describe new stateful mobility primitives that use higher-order channels, giving their operational semantics and an implementation outline. We show how medium-level coordination abstractions can be constructed using monadic composition of the mobility primitives. We briefly outline how high-level mobile coordination abstractions, or mobility skeletons, can be defined using the lower-level abstractions. The use of all three abstractions is demonstrated with examples and a new case study: a distributed stateless web server where a thread farm skeleton is used to distribute work to remote locations.

This paper investigates using a functional language with a sophisticated type system to implement data-intensive programs. We focus on how bulk data types can be represented rather than on the efficient implementation of those types. The paper is intended more as a discussion document, recording some thoughts on how to represent bulk data in a functional language, than as a conclusive statement on functional databases. It also serves as a reasonably complex and hopefully realistic example of how some of the new features of Haskell 1.3, including constructor classes, can be exploited to good effect. The limitations of these features are also assessed.

We present the design, implementation and evaluation of Deadline-Driven Auctions (DDAs), a novel task-mapping infrastructure for heterogeneous distributed environments. DDA is primarily designed for hosting Non-Player Characters (NPCs) in P2P Massively Multiplayer Online Games (MMOGs). Experimental and analytical results demonstrate that DDA provides four significant advantages. It is self-organising: the infrastructure is automatically managed. It efficiently allocates computing resources for large numbers (1000s) of real-time NPC tasks. It supports gaming interactivity by minimising communication latency between NPC hosts. Finally, it supports flexible matchmaking policies, and a friendly incentive policy establishes a cooperative economic model to motivate participants to contribute resources.

Massively Multiplayer Online Games (MMOGs) are increasing in both popularity and scale, and while classical Client/Server (C/S) architectures convey some benefits, they suffer from significant technical and commercial drawbacks. This realisation has sparked intensive research interest in adapting MMOGs to Peer-to-Peer (P2P) architectures. This paper articulates a comprehensive set of six design issues to be addressed by P2P MMOGs, namely Interest Management (IM), game event dissemination, Non-Player Character (NPC) host allocation, game state persistency, cheating mitigation and incentive mechanisms. Design alternatives for each issue are systematically compared, and their interrelationships discussed. We further evaluate how well representative P2P MMOG architectures fulfil the design criteria.