We present a case study of parallelizing serial legacy code using Invasive Interactive Parallelization (IIP) - a compositional approach to parallelizing code refactoring rooted in the Invasive Software Composition (ISC) and the Separation of Concerns (SoC). The study focuses on scientific code, in particular, Gaussian elimination where parallelization neither requires nor incurs serious changes in the algorithmic structure. As the major contribution we show how parallelization of Gaussian elimination can be automatized with reusable parallelization recipes implemented as composers in Reuseware. We consider parallelization for both shared-and distributed-memory systems with OpenMP and MPI respectively. We present the speed-ups achieved and discuss gains in code reusability.

We present a formal framework for a recently introduced approach to Automated Round-trip Software Engineering (ARE) in source-level aspect weaving systems. Along with the formalization we improve the original method and suggest a new concept of weaving transactions in Aspect-oriented Programming (AOP). As the major contribution we formally show how, given a tree-shaped intermediate representation of a program and an ancillary transposition tree, manual edits in statically woven code can consistently be mapped back to their proper source of origin, which is either in the application core or in an element in the aspect space. The presented formalism is constructive. It frames AOP by generalizing static aspect weaving to classical tree transformations.

We elaborate on reasoning in contemporary (semi) automatic parallelizing refactoring. As the main contribution we summarize contemporary approaches and show that all attempts to reason in parallelization thus far, have amounted to local code analysis given data and control dependencies. We conclude that, by retaining this perspective only, parallelization continues to exploit merely a subset of the reasoning methods available today and is likely to remain limited. To address this problem we suggest to expand the local analyses, such that, they take seriously relations between individual local parallelizing transformations. We argue that such a coupling allows to process sparser parallelizable constructs, such as, Producer-Consumer Coordination. We identify questions to be addressed to put this principle into action and report on-going work on (reasoning) mechanisms able to support this.

While looking at the strengths and weaknesses of contemporary approaches to parallelization this thesis s uggests a form of parallelizing refactoring - Invasive Interactive Parallelization - that aims at addressing a number of weaker sides of contemporary methods. Our ultimate goal is to make the parallelization more user and developer friendly. While admitting that the approach adds complexity at certain levels, in particular, it can be said to reduce code understandability, we conclude that it provides a remedy for a number of problems found in contemporary methods. As the main contribut ion the thesis discusses the benefits we see with the approach, introduces a set of parallelization categories a typical parallelization con sists of, and shows how the method can be realized with abstract syntax tree transformations. The thesis also presents a formal solution to the problem of automated round-trip software engineer ing in aspect-weaving systems.

We suggest an approach to Automated Round-trip Software Engineering in source-level aspect weaving systems that allows for transparent mapping of manual edits in the woven program back to the appropriate source of origin, which is either the application core or the aspect space.

In this thesis proposal we suggest an interactive method of parallelizing legacy software that is based on separation of concerns and aspect weaving. We statically inject parallelizing code into sequential cores by means of reusable rewrite rules. We view parallelization as a generic refactoring process with programmable control automated by inferences on structured parallelization categories.

We study strategies for local load balancing of irregular parallel divide-andconquer algorithms such as Quicksort and Quickhull in SPMD-parallel environments such as MPI and Fork that allow to exploit nested parallelism by dynamic group splitting. We propose two new local strategies, repivoting and serialisation, and develop a hybrid local load balancing strategy, which is calibrated by parameters that are derived off-line from a dynamic programming optimisation. While the approach is generic, we have implemented and evaluated our method for two very different parallel platforms. We found that our local strategy is superior to global dynamic load balancing on a Linux cluster, while the latter performs better on a tightly synchronised sharedmemory platform with nonblocking, cheap task queue access.

We propose a new method of interactively parallelising programs that is based on aspect weaving and invasive software composition. This can be seen as an alternative to skeleton programming. We give motivating examples for how our method could be applied.

This paper focuses on an efficient user-level handling of intensive interprocess communication in distributed parallel applications that are characterised by a high rate of data exchange. A common feature of such systems is that any parallelisation strategy focusing on the largest parallelisable fraction results in the highest possible rate of interprocess communication, compared to other parallelisation strategies. An example of such applications is the class of telecommunication traffic simulators, where the partition-communication phenomenon reveals itself due to the strong data interdependencies among the major parallelisable tasks, namely, encoding of messages, decoding of messages, and interpretation of messages.