Michael D. Vose, Alden H. Wright, Jonathan E. Rowe · 2003
Abstract. This paper assumes a search space of fixed-length strings, where the size of the alphabet can vary from position to position. Structural crossover is mask-based crossover, and thus includes ¦-point and uniform crossover. Structural mutation is mutation that commutes with a group operation on the search space. This paper shows that structural crossover and mutation project naturally onto competing families of schemata. In other words, the effect of crossover and mutation on a set of string positions can be specified by considering only what happens at those positions and ignoring other positions. However, it is not possible to do this for proportional selection except when fitness is constant on each schema of the family. One can write down an equation which includes selection which generalizes the Holland Schema theorem. However, like the Schema theorem, this equation cannot be applied over multiple time steps without keeping track of the frequency of every string in the search space. 1
Cited by 0
Alden H. Wright, Michael D. Vose, Jonathan E. Rowe · 2003
Cited by 0
José Manuel Calderón Trilla, Colin Runciman · ACM SIGPLAN Notices · 2015
Using static analysis techniques compilers for lazy functional languages can be used to identify parts of a program that can be legitimately evaluated in parallel and ensure that those expressions are executed concurrently with the main thread of execution. These techniques can produce improvements in the runtime performance of a program, but are limited by the static analyses’ poor prediction of runtime performance. This paper outlines the development of a system that uses iterative profile-directed improvement in addition to well-studied static analysis techniques. This allows us to achieve higher performance gains than through static analysis alone.
Cited by 0
José Manuel Calderón Trilla, Colin Runciman · 2015
Using static analysis techniques compilers for lazy functional languages can be used to identify parts of a program that can be legitimately evaluated in parallel and ensure that those expressions are executed concurrently with the main thread of execution. These techniques can produce improvements in the runtime performance of a program, but are limited by the static analyses’ poor prediction of runtime performance. This paper outlines the development of a system that uses iterative profile-directed improvement in addition to well-studied static analysis techniques. This allows us to achieve higher performance gains than through static analysis alone.
Cited by 5
Calderon, Jose Manuel · White Rose eTheses Online (University of Leeds, The University of Sheffield, University of York) · 2015
We propose a new technique for exploiting the inherent parallelism in lazy functional programs. Known as implicit parallelism, the goal of writing a sequential program and having the compiler improve its performance by determining what can be executed in parallel has been studied for many years. Our technique abandons the idea that a compiler should accomplish this feat in ‘one shot’ with static analysis and instead allow the compiler to improve upon the static analysis using iterative feedback. \n \nWe demonstrate that iterative feedback can be relatively simple when the source language is a lazy purely functional programming language. We present three main contributions to the field: the auto- matic derivation of parallel strategies from a demand on a structure, and two new methods of feedback-directed auto-parallelisation. The first method treats the runtime of the program as a black box and uses the ‘wall-clock’ time as a fitness function to guide a heuristic search on bitstrings representing the parallel setting of the program. The second feedback approach is profile directed. This allows the compiler to use profile data that is gathered by the runtime system as the pro- gram executes. This allows the compiler to determine which threads are not worth the overhead of creating them. \n \nOur results show that the use of feedback-directed compilation can be a good source of refinement for the static analysis techniques that struggle to account for the cost of a computation. This lifts the burden of ‘is this parallelism worthwhile?’ away from the static phase of compilation and to the runtime, which is better equipped to answer the question.
Cited by 0
Tim Harris, Satnam Singh · ACM SIGPLAN Notices · 2007
In this paper we present an automated way of using spare CPU resources within a shared memory multi-processor or multi-core machine. Our approach is ( i ) to profile the execution of a program, ( ii ) from this to identify pieces of work which are promising sources of parallelism, ( iii ) recompile the program with this work being performed speculatively via a work-stealing system and then ( iv ) to detect at run-time any attempt to perform operations that would reveal the presence of speculation. We assess the practicality of the approach through an implementation based on GHC 6.6 along with a limit study based on the execution profiles we gathered. We support the full Concurrent Haskell language compiled with traditional optimizations and including I/O operations and synchronization as well as pure computation. We use 20 of the larger programs from the 'nofib' benchmark suite. The limit study shows that programs vary a lot in the parallelism we can identify: some have none, 16 have a potential 2x speed-up, 4 have 32x. In practice, on a 4-core processor, we get 10-80% speed-ups on 7 programs. This is mainly achieved at the addition of a second core rather than beyond this. This approach is therefore not a replacement for manual parallelization, but rather a way of squeezing extra performance out of the threads of an already-parallel program or out of a program that has not yet been parallelized.
Cited by 3
Tuukka Haapasalo, Glasgow Parallel Haskell · 2009
Programmer doesn’t define how computation is parallelized Compiler parallelizes the execution automatically Language’s constructs are inherently parallel Often purely functional languages (single-assignment) Parallelization not programmed ⇒ no parallelization bugs in code, easier to program Explicit Parallelism [8] Is explicitly defined by the programmer Can be difficult to program, debugging is hard
Cited by 0
Gerald Ostheimer, Antony J. T. Davie · 2007
It is well known that exploiting parallelism beyond the available machine parallelism can lead to vastly increased resource requirements. Programs which can run in linear space under a sequential execution regime may require exponential space in the context of unrestricted parallelism. In this paper we present an efficient adaptive software solution for the problem of avoiding excessive parallelism when evaluating implicitly parallel functional programs. We give an informal proof for the effectiveness of our method and discuss its limitations. The solution and the proof are based on a compilation scheme mapping lazy functional programs onto message-passing parallel architectures. Our strategy is completely distributed and can be expected to scale well to large machine configurations. 1 1 Introduction and Background Fifteen years after John Backus' clarion call to break the von Neumann bottleneck by adopting a functional programming style [Ba78], commercial multiprocessors are now ava...
Cited by 0
The MIT Press eBooks · 1995
December 4-7, 1995, Portland, Oregon The International Logic Programming Symposium is one of two major international conferences sponsored by the Association of Logic Programming. It is held annually in North America. The theme for the 1995 conference is Declarative Systems, particularly the integration of the logic programming, functional programming, and object-oriented programming paradigms.Logic Programming series, Research Reports and Notes
Cited by 0
Michael D. Vose, Alden H. Wright · Evolutionary Computation · 2001
Holland's schema theorem (an inequality) may be viewed as an attempt to understand genetic search in terms of a coarse graining of the state space. Stephens and Waelbroeck developed that perspective, sharpening the schema theorem to an equality. Of particular interest is a "form invariance" of their equations; the form is unchanged by the degree of coarse graining. This paper establishes a similar form invariance for the more general model of Vose et al. and uses the attendant machinery as a springboard for an interpretation and discussion of implicit parallelism.
Cited by 21
Tim Harris · 2008
In this paper we present an automated way of using spare CPU resources within a shared memory multi-processor or multi-core machine. Our approach is (i) to profile the execution of a program, (ii) from this to identify pieces of work which are promising sources of parallelism, (iii) recompile the program with this work being performed speculatively via a work-stealing system and then (iv) to detect at run time any attempt to perform operations that would reveal the presence of speculation. We assess the practicality of the approach through an implementation based on GHC 6.6 along with a limit study based on the execution profiles we gathered. We use 20 of the larger programs from the ‘nofib ’ benchmark suite as tests. The limit study shows that programs vary a lot in the parallelism we can identify: some have none, several have a potential 2x speedup, one has 32x. In practice, our implementation running on quad-core processor, shows 10-80 % speedups on several programs. We support the full Concurrent STM Haskell language compiled with traditional optimizations and including IO operations and synchronization as well as pure computation. This approach is not a replacement for manual parallelization, but rather a way of squeezing extra performance out of the threads of an already-parallel program or out of a program that has not yet been parallelized. 1.
Cited by 0
Nikolas Ioannou, Marcelo Cintra · 2011
Multi-core and many-core systems are the norm in contemporary processor technology and are expected to remain so for the foreseeable future. Programs using parallel programming primitives like PThreads or OpenMP often exploit coarse-grain parallelism, because it offers a good trade-off between programming effort versus performance gain. Some parallel applications show limited or no scaling beyond a number of cores. Given the abundant number of cores expected in future many-cores, several cores would remain idle in such cases while execution performance stagnates. This paper proposes using cores that do not contribute to performance improvement for running implicit fine-grain speculative threads. In particular, we present a many-core architecture and protocol that allow applications with coarse-grain explicit parallelism to further exploit implicit speculative parallelism within each thread. Implicit speculative parallelism frees the programmer from the additional effort to explicitly partition the work into finer and properly synchronized tasks. Our results show that, for a many-core comprising of 128 cores supporting implicit speculative parallelism in clusters of 2 or 4 cores, performance improves on top of the highest scalability point by 41% on average for the 4-core cluster and by 27% on average for the 2-core cluster. These performance improvements come with an energy consumption that is close to -- and sometimes better than -- the baseline. This approach often leads to better performance and energy efficiency compared to existing alternatives such as Core Fusion and Frequency Boosting. We also investigate the tradeoffs between explicit and implicit threads as input dataset sizes vary. Finally, we present a dynamic mechanism to choose the number of explicit and implicit threads, which performs within 6% of the static oracle selection of threads.
Cited by 10
Baohai Ni, Peng Wang, Lu Liu · 2025
Cited by 0
Aart J.C. Bik, et al. · 2009
Cited by 0
Haoran Wang · theses.fr (ABES) · 2022
Cited by 0Open access
Tolga Ovatman, Thomas Weigert, Feza Buzluca · Journal of Systems and Software · 2011
Cited by 6
Lubomir Bic, Mayez Al-Mouhamed · Journal of Parallel and Distributed Computing · 1993
Cited by 0
Christoph Von Praun, Luis Ceze · 2008
Implicit Parallelism with Ordered Transactions (IPOT) is an extension of sequential or explicitly parallel programming models to support speculative parallelization. The key idea is to specify opportunities for parallelization in a sequential program using annotations similar to transactions. Unlike explicit parallelism, IPOT annotations do not require the absence of data dependence, since the parallelization relies on runtime support for speculative execution. IPOT as a parallel programming model is determinate, i.e., program semantics are independent of the thread scheduling. For optimization, non-determinism can be introduced selectively. We describe the programming model of IPOT and an online tool that recommends boundaries of ordered transactions by observing a sequential execution. On three example HPC workloads we demonstrate that our method is effective in identifying opportunities for fine-grain parallelization. Using the automated task recommendation tool, we were able to perform the parallelization of each program within a few hours.
Cited by 0
Cody Permann, David Andrš, John W. Peterson et al. · University of North Texas Digital Library (University of North Texas) · 2013
As hardware advances continue to modify the supercomputing landscape, traditional scientific software development practices will become more outdated, ineffective, and inefficient. The process of rewriting/retooling existing software for new architectures is a Sisyphean task, and results in substantial hours of development time, effort, and money. Software libraries which provide an abstraction of the resources provided by such architectures are therefore essential if the computational engineering and science communities are to continue to flourish in this modern computing environment. The Multiphysics Object Oriented Simulation Environment (MOOSE) framework enables complex multiphysics analysis tools to be built rapidly by scientists, engineers, and domain specialists, while also allowing them to both take advantage of current HPC architectures, and efficiently prepare for future supercomputer designs. MOOSE employs a hybrid shared-memory and distributed-memory parallel model and provides a complete and consistent interface for creating multiphysics analysis tools. In this paper, a brief discussion of the mathematical algorithms underlying the framework and the internal object-oriented hybrid parallel design are given. Representative massively parallel results from several applications areas are presented, and a brief discussion of future areas of research for the framework are provided.
Cited by 6Open access
Cody J. Permann; David Andrs; John W. Peterson; Derek R. Gaston · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2016
As hardware advances continue to modify the supercomputing landscape, traditional scientific software development practices will become more outdated, ineffective, and inefficient. The process of rewriting/retooling existing software for new architectures is a Sisyphean task, and results in substantial hours of development time, effort, and money. Software libraries which provide an abstraction of the resources provided by such architectures are therefore essential if the computational engineering and science communities are to continue to flourish in this modern computing environment. The Multiphysics Object Oriented Simulation Environment (MOOSE) framework enables complex multiphysics analysis tools to be built rapidly by scientists, engineers, and domain specialists, while also allowing them to both take advantage of current HPC architectures, and efficiently prepare for future supercomputer designs. MOOSE employs a hybrid shared-memory and distributed-memory parallel model and provides a complete and consistent interface for creating multiphysics analysis tools. In this paper, a brief discussion of the mathematical algorithms underlying the framework and the internal object-oriented hybrid parallel design are given. Representative massively parallel results from several applications areas are presented, and a brief discussion of future areas of research for the framework are provided.
Cited by 0Open access