To devise novel parallelism control mechanisms further insights into dynamic behaviour of parallel functional programs and run-time systems (RTS) are needed. We use pro ling to characterise eight applications on a multi-core and on a multi-core cluster. We focus on thread granularity, memory management and communication. Our results con rm that parallel Haskell implementations cope well with large numbers of potential threads, identify memory management overhead as a key limiting factor in a shared-memory RTS, whilst in the distributed RTS, the amount of sharing determines the dominant communication overhead.
This work is partly supported by the Scottish Informatics and Computer Science Alliance (SICSA).
Most applications1 were adopted from [
Five applications use the Divide-an-Conquer (D&C) pattern, where a problem is recursively split into subproblems that are solved and the results combined to form the nal result. A threshold value can be used to restrict the depth of a tree to a certain level from which on the problem is solved sequentially.
The regular and at (i.e. not nested) parfib computes the number of function calls for computation of the N th Fibonacci number using arbitrary-length integers (input: N = 50, threshold of 23); the naive exponential implementation is primarily aimed at assessing thread subsumption capabilities of the RTS. The worpitzky program, from the domain of symbolic computation, checks the Worpitzky identity for two given arbitrary-length integers (19 to the exponent of 27, threshold 10).
The queens program determines the number of solutions for placement of N queens on an N N board without attacking each other (N = 16); a solution is a list of integers generated by discarding unsafe positions, which results in sharing of data structures at RTS level.
The coins program computes ways to pay out a speci ed amount (5777) from a given set of coins. The minimax application calculates winning positions for a Noughts-vs-Crosses game on a N N board up to a speci ed depth using alpha-beta search and lazyness to prune unpromising sub-trees (N = 4, depth 8).
Three applications are data parallel, i.e. the parallelism is exploited by simultaneously applying a function to the elements of a data structure. Explicit chunking can be used for explicit granularity tuning.
The sumeuler program computes the sum over Euler Totient numbers in a given integer interval and is fairly irregular ([0..100000], chunk 500); all the parallelism is generated in the beginning of the execution. The mandelbrot application computes the fairly irregular Mandelbrot fractal set for a given range and image size as well as number of iterations (range [-2:0..2:0], 4096x4096 image size, 3046 iterations).
The maze program is a nested data-parallel AI application which searches for a path in a maze (of size 29).
The benchmarks are implemented in Glasgow parallel Haskell [
Additionally, we use larger input sizes and obtain more detailed pro les. We have extended the pro ling
infrastructure to record per-lightweight-thread granularity information as well as to collect more detailed summary
statistics on protocol messages and sizes (speci c to the distributed RTS). Relevant background information on
high-level programming models and RTS-level policies can be found in [
We report relative speedups and pro les from a median run out of three on a dedicated multi-core and on a lightly loaded cluster of multi-cores as as we are primarily interested in the parallelism behaviour of the applications.
The 48-core machine (cantor) consists of four AMD Opteron processors with two NUMA nodes with six 2.8GHz cores each. Every two cores share 2MB L2 cache and all six cores on a NUMA-node share 6MB L3 cache and 64GB RAM (512GB in sum). Average memory latency is 16ns with up to 3x di erence depending on the NUMA regions. The beowulf cluster comprises of 8-core Xeon 5504 nodes with two sockets with four 2GHz cores each, using 256 KB L2 cache, and 4MB shared L3 cache and 12GB RAM, and 8-core Xeon 5450 nodes with two sockets with four 3GHz cores each, using 6MB shared L2 cache and 16GB RAM, connected via Gigabit Ethernet with average latency of 150ns. We use CentOS 6.5, GHC 6.12.32, gcc 4.4.7, and PVM 3.4.6. 1Application source code can be obtained from http://www.macs.hw.ac.uk/~eb96/atps15benchmarks.tar.gz or via email. 2Some experiments using GHC 7.6.3 show similar trends for SMP; GUM has not yet been ported to more recent GHC versions. 3.1
We x the input size and increase the number of PEs to assess scalability. Run time decreases as the applications are able to pro tably exploit parallelism resulting in an order of magnitude reduction in execution time for 5 programs. The exceptions are queens due to excessive memory use, maze which generates more work with increasing PE numbers, and GHC-SMP3 runs on higher numbers of PEs which indicates a scalability issue.
In Figure 1 we observe strong scaling for parfib and coins for GUM and good scaling for sumeuler with load balancing issues on high numbers of PEs. GUM scales up to 64 PEs in most cases, although often the bene t of adding PEs decreases with PE number due to increasing overhead and reduced work per PE. SMP shows best performance for relatively low number of PEs, whilst on 48 cores a memory management issue discussed in Section 3.3 leads to a slowdown for 5 out of 8 programs. Moreover, queens, mandelbrot, and minimax exhibit limited scalability due to excessive communication and heap residency, which hints at improvement potential at application level. Increasing granularity for worpitzky is deemed likely to improve performance as currently median thread size is very small and the number of threads very high compared to programs that scale better. 3.2
We have extended run-time pro ling capabilities of GUM and SMP to record thread granularity information4. Unlike SMP, GUM RTS instances maintain private heaps and thus avoid GC-related synchronisation overhead. In Figure 2 we present application granularity pro les5, grouped by the RTS and architecture. A log-log scale is used for comparability due to orders of magnitude di erences in thread sizes (x-axis) and numbers (y-axis).
For parfib, coins, and worpitzky, we observe an order of magnitude less and larger threads for GUM than
for SMP, which demonstrates e ectiveness of GUM's thread subsumption mechanism and the aggressiveness of
SMP's thread creation for D&C applications. Subsumption allows to implement advisory parallelism where the
RTS decides whether to inline child threads into the parent or execute them in parallel, similar to lazy futures [
Parallelism is often over-abundant and ne-grained in functional programs, leaving considerable parallel slackness and requiring an e ective thread subsumption mechanism. We observe a wide range of actual and potential parallelism degrees across applications. For instance, sumeuler only has 200 potential threads which is insu cient to keep all PEs busy, whereas for coins and worpitzky there are four orders of magnitude more potential threads, most of which are pruned at run time. GUM appears well-suited for D&C applications and is able to subsume threads to a larger extent than SMP which creates threads more aggressively. The systems automatically adapt the degree of actual parallelism to the number of the available PEs.
By contrast, thread subsumption is ine ective in at data-parallel applications, where parallelism is created at the start of the computation. Hence, to exploit the subsumption mechanism, data-parallel applications appear to require nested parallelism. We observe optimisation potential for D&C applications: recognising and inlining smaller threads as well as reducing the spread of the granularity distribution and the number of threads whilst preserving larger threads. 3.3
Many parallel functional programs are memory-bound as they perform graph reduction. Figure 3 depicts GC overhead { a reason for scalability issues for SMP. The GC% increases consistently across all applications for SMP and results in severe contention on the rst generation heap. By contrast, GUM starts o with higher GC% which then drops or remains constant in most cases. This highlights the bene t of a distributed-memory design on shared-memory architectures by avoiding some of the synchronisation, which pays o particularly for applications with low communication rate. In addition to GC%, allocation rate signi es computational intensity of each application and can be used to compare aggressiveness of work allocation across run-time systems. In Figure 4 we observe initially higher allocation rates for SMP that are then dropping faster than for GUM.
Application working sets are represented by heap residency. We observe roughly constant or decreasing residency for GUM on both distributed- and shared-memory architectures (except for minimax), whilst for SMP the residency is growing in most cases, as due to contention some heap-allocated objects are retained for longer. 3.4
GUM uses virtual shared memory, so each RTS instance maintains a Global Address (GA) table of stable inter-processor pointers which are used as roots for GC. Fragmentation of the shared heap can lead to decreased performance since excessive sharing results in higher GA residency and reduced locality, which leads to additional communication overhead. Thus GA residency can be used as an indicator of the degree of virtual shared heap fragmentation. Based on this metric, our application set can be partitioned into two classes: most of the applications shown in Figure 5, exhibit a moderate GA residency of at most 600 per PE; in contrast to this behaviour, worpitzky reaches a value of 2500 for a large number of PEs, and even worse mandelbrot (not shown) reaches a GA residency of 8000, and queens (not shown) of over 250000. This points to a high degree of sharing in the program due to poor data distribution and locality, which incurs a lot of communication and becomes a bottleneck for parallel performance, hinting at potential for application-level optimisation.
As shown in Figure 6, for parfib, coins, maze, and to lesser extent minimax and sumeuler we observe modest linear increase in communication rate with less than 40% of work request messages. The median of the graph sent usually increases slightly, but only for queens it is excessive with over 14MB median graph sent per mutation second on 48 cores, as communication rate skyrockets (840k messages on 48 cores with frequent very long fetches (when a light-weight thread blocks waiting for another), with only 15% of the messages being work requests).
We are currently investigating ways to eliminate these overheads. Next highest communication rate is for worpitzky with over 100k messages sent on 48 cores, almost 50% of which are work requests, due to very ne thread granularity. Then sumeuler follows, illustrating another issue | lack of inherent parallelism for the given chunk size leads to load imbalance on higher number of PEs demonstrated by over 95% of sent messages being requests for work, which also coincides with decreasing memory residency and low allocation rate.
For most applications the number of packets sent increases linearly and re ects the size of shared graph, whilst packet size is mostly very small and constant (in the range between 5 and 50 bytes), except for queens (4k) and mandelbrot (ca. 9k). Due to space limitation we present no graphs on these metrics. We nd that in general packets are smallest for integer-based programs and data-parallel programs often have larger packets than D&C programs. Communication rate appears to correlate with heap fragmentation (GA residency) and the percentage of work requests of the total number of messages seems to indicate the degree of load imbalance.
Careful parallelisation is required to avoid pitfalls that result in excessive overhead and limit scalability. We have found that semi-explicit parallel functional programs have the potential to scale, provided there is enough work on the one hand, but that the granularity and sharing are adequately controlled, on the other. 4
We have characterised a set of small and medium-sized parallel functional applications run on a multi-core and on a cluster of multi-cores in terms of scalability, granularity, GC overhead, global address table residency, allocation rate and communication rate, among other metrics. We have found that pro ling reveals diverse bottlenecks and helps gain insight into dynamic application behaviour. In particular, the results indicate that: Subsumption works well across architectures and D&C applications, as the RTS is able to handle a large number of potential light-weight threads and prune super uous parallelism by subsuming computations into the parent thread. For data-parallel programs nesting appears to be necessary to bene t from subsumption. Compared to SMP, GUM is less aggressive in instantiating parallelism, i.e. generates fewer threads of larger granularity, adapting to the number of PEs and to system latency (the higher the latency, the lazier the instantiation). Additionally, granularity varies across run-time systems but seems relatively similar for the same RTS across di erent architectures.
High GA residency is a good indicator of heap fragmentation due to sharing, which in turn causes a high degree of communication, limiting the scalability of the application.
Communication rate and GA residency vary considerably across applications and have a high, direct impact on parallel performance.
System-level information (e.g. granularity pro les, GA residency representing heap fragmentation and the fraction of work requests in relation to the total number of messages) appears promising for improving dynamic policy control decisions at RTS level.
Increased memory residency and GC-percentage in a shared-memory design point to a scalability issue due
to contention on the rst generation heap, in contrast to a distributed-memory design, con rming the results
from [
The insights from this characterisation inform the design of a dynamic adaptation mechanism, based on
monitoring a set of relevant parameters and dynamically tuning related policies. For instance, we are currently
implementing a co-location mechanism for potential threads that leverages ancestry information to encourage
stealing work from the nearby sources to improve locality and reduce fragmentation of the shared heap for
applications with multiple sources of parallelism. Additionally, architectural information on communication
latency and computational power of di erent PEs could be used to further improve co-location decisions [
Ultimately, we envision a growing set of representative parallel functional benchmark applications that could be used (similar to mainstream languages) to compare di erent novel parallelism management policies and mechanisms, aiming at high performance portability across heterogeneous architectures whilst retaining productivity.
We are grateful to Natalia Chechina, Julian Godesa, Rob Stewart, and Prabhat Totoo for inspiring discussions and to the anonymous reviewers who helped improve the presentation and the discussion of the results.