The high-level goal of this research is to identify a method to accelerate general purpose software using heterogeneous systems. Heterogeneous systems offer the potential of improving performance through the use of hardware components specialised for a particular task. The issue considered in this research is how best to map parts of an existing piece of software to components in a heterogeneous architecture to deliver the optimal program execution time. The heterogeneous partitioning problem is an NP-hard quadratic optimisation problem. However, before the problem could be addressed using optimisation techniques, the problem had to be quantified and formalised using software characterisation and computational abstraction models. The main contributions delivered by this research are: • 3S: a novel software characterisation framework that combines static instrumentation with dynamic characterisation enabling simple tools to measure real fine-grained execution timing, control and data flow information for any compilable program. • MAP: a new execution model and multi-level parallel assignment approach that delivers up to 64 times the heterogeneous acceleration potential of previous work for the benchmarks considered. • MIP: the first formal work on multiple instantiation under activation sequence uncertainty, providing more than twice the acceleration potential of previous optimal assignment methods for the software considered and capable of being integrated with MAP to deliver significant gains for heterogeneous partitioning. These contributions have been published in a collection of research papers and are the focus of Chapters 3, 4 and 5 of this thesis.