Object-distribution analysis for program decomposition and re-clustering

The next-generation of embedded systems confronts the designer with multi-processor systems both for performance and energy reasons. Exploiting task-level parallelism in combination with loop-level parallelism is becoming crucial. The challenge is to build compiler tools for the exploration of these types of parallelism. To achieve this goal, we have designed a transformation framework for analysis and extraction of the potential parallelism in sequential object-oriented programs. We present an inter-procedural, compositional, context and flow-sensitive algorithm for analysis of object distribution in sequential object-oriented programs. Our technique consists of three main phases: compositional inter-procedural object-distribution analysis, construction of minimal hierarchical object-distribution graph, and graph rendering using constrained force-directed layout. Integration of these algorithms allows us to reduce number of prospective program decompositions with respect to program flow and object-distribution properties. The visualisation environment further extends usability of our tools for employment of semi-automated as well as fully-automated heuristics with further constraints on definition of the final task boundaries. We demonstrate the usability of our approach on a number of realistic Java applications.