A Compiler Analysis of Interprocedural Data Communication

ABSTRACT

This paper presents a compiler analysis for data communication for the purpose of transforming ordinary programs into ones that run on distributed systems. Such transformations have been used for process migration and computation offloading to improve the performance of mobile computing devices. In a client-server distributed environment, the efficiency of an application can be improved by careful partitioning of tasks between the server and the client. Optimal task partitioning depends on the tradeoff between the computation workload and the communication cost. Our compiler analysis, assisted by a minimum set of user assertions, estimates the amount of data communication between procedures. The paper also presents experimental results based on an implementation in the GCC compiler. The static estimates for several multimedia programs are compared against dynamic measurement performed using Shade, a SUN Microsystem's instruction-level simulator. The results show a high precision of the static analysis for most pairs of the procedures.

REFERENCES

• 1: Kasidit Chanchio , Xian-He Sun, Data collection and restoration for heterogenenous process migration, Software—Practice & Experience, v.32 n.9, p.845-871, July 2002 [doi>10.1002/spe.464]
• 2: Robert F. Cmelik , David Keppel, Shade: A Fast Instruction Set Simulator for Execution Profiling, Sun Microsystems, Inc., Mountain View, CA, 1993
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 5: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 6: David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996 [doi>10.1145/234533.234534]
• 7: [7] U. Kremer, J. Hicks, and J. Rehg. A compilation framework for power and energy management on mobile computers. Proc. of the 14th International Workshop on Parallel Computing (LCPC'01), August 2001.
• 8: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: Zhiyuan Li , Cheng Wang , Rong Xu, Computation offloading to save energy on handheld devices: a partition scheme, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502257]
• 10: Zhiyuan Li , Cheng Wang , Rong Xu, Task Allocation for Distributed Multimedia Processing on Wirelessly Networked Handheld Devices, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.312, April 15-19, 2002
• 11: Amy W. Lim , Gerald I. Cheong , Monica S. Lam, An affine partitioning algorithm to maximize parallelism and minimize communication, Proceedings of the 13th international conference on Supercomputing, p.228-237, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305197]
• 12: H. D. Pande , W. A. Landi , B. G. Ryder, Interprocedural Def-Use Associations for C Systems with Single Level Pointers, IEEE Transactions on Software Engineering, v.20 n.5, p.385-403, May 1994 [doi>10.1109/32.286418]
• 13: Alexey Rudenko , Peter Reiher , Gerald J. Popek , Geoffrey H. Kuenning, Saving portable computer battery power through remote process execution, ACM SIGMOBILE Mobile Computing and Communications Review, v.2 n.1, p.19-26, January 1998 [doi>10.1145/584007.584008]
• 14: [14] M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352-357, July 1984.
• 15: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995