Source level merging of independent programs

摘要

In here we describe a technique to merge at source level two (and hence more) independent C programs. Due to the independence of the programs, the merged program has more parallelism that can be extracted by the underlying compiler and CPU. Thus it is expected that the execution time of the merged program will be better than the time obtained by executing the two programs separately. The usefulness of such merging for embedded systems has been studied and demonstrated by the works of Dean and others with the Thrint compiler for merging threads at Assembly level. The main contribution of this work is an efficient algorithm for matching sub-components considering the inside structure of the sub-components and not only their execution frequency. Two novel techniques for balancing the merge of sub-components are presented:rn1. Residual loop merging (RLM) as a way to merge loops with different nesting and execution frequency levels.rn2. Using the remaining iterations formed after merging two non-equal loops (loops with different number of iterations) in future mergings of other loops.rnThese two abilities allow the proposed algorithm to simplify the matching process and overcome merging problems related to deep nested structure. We also consider the problem of merging function calls and make extensive use of cloning (and not only inlining as is the case with previous works). The final tool is the first complete system for merging C-programs at source level supporting profile and structure based matching.rnThe main use of merging is to speed up embedded systems that usually execute independent threads or processes that can potentially be merged. Our experimental results suggest that the proposed merging technique can speedup the execution of two independent programs by 10%-20% for about half of mergings that have been tested.