Automatic program partitioning to alleviate resource constraints of object-oriented applications.

摘要

Automatic application partitioning has been the interests in parallel and distributed computing for a number of purposes. In recent years, it has been applied to a newly emerging field---partitioning the application to alleviate resource constraints on mobile devices. Traditionally, automatic application partitioning has been studied mainly in the domain of scientific regular applications. The fact that mobile devices are rapidly embracing object-oriented mobile code such as Java brings new challenges to this already difficult topic. This thesis aims to tackle these challenges and presents a unified graph partitioning approach to automatically partition object-oriented programs for a mobile device to conserve resource usage.;The first step of the partitioning is to build an object graph model to estimate the runtime object dependence relations. Learning from the limitations of existing analysis approaches, we see the necessity of a combined analysis that uses both static and dynamic factors. We first build an initial Object Relation Graph (ORG) that is based on points-to analysis, and then enhance this static information with offline profiling results. The resulting ORG gives a relatively accurate estimate of runtime objects and their interactions.;When an application is distributed, the target computing infrastructures and the distribution objectives can be different. It is therefore often inappropriate to apply partitioning directly onto the ORG. In our approach, we solve this problem by a two-layer graph structure, in which we use a second layer of graphs, the Target Graphs (TGs), to account for the various target infrastructures and distribution objectives. After mapping the ORG onto a TG, we then apply appropriate partitioning strategies to the TG. Thus, by this two-layer graph modeling, we achieve a unified application partitioning for different goals.;The thesis presents an automatic application distribution framework to realize these proposed approaches. The framework transforms monolithic Java programs automatically into distributed programs for a mobile device and a tethered server, and provides remote execution support for the resulting distributed programs. Preliminary benchmark results are highly promising, with an average speedup factor of almost 1.5 and an average energy savings of 83.5% for the beneficial benchmarks.