N131-061 TITLE: Improving Software Efficiency: Automated Program Transformation for Reclaiming Execution Efficiency (APTREE)

TECHNOLOGY AREAS: Information Systems

OBJECTIVE: Develop techniques, methods and tools for improving software execution efficiency and reducing software bloat while preserving the programming productivity gains offered by modern software engineering practices.

DESCRIPTION: The size and complexity of software in Navy systems has grown tremendously in recent years. The growth in software size and complexity partially comes from the rising percentage of software components in Navy and DoD systems. For example, the percentage of avionics specification requirements involving software control has risen from approximately 8 percent for the F-4 in 1960 to 45 percent for the F-16 in 1982, 80 percent for the F-22 in 2000, and 90 percent for the F-35 in 2006, and the code size has increased from about 3 million source lines of code (SLOC) in the F-22 to about 14 million SLOC in the F-35. It is expected that the percentage of software components in Navy systems will continue to grow. This growth factor is considered necessary as it provides enhanced capability and flexibility to Navy systems. The other growth factor in software size and complexity is an unfortunate artifact of modern software engineering practice which results in complexity and bloat. This growth factor is considered accidental and is a major contributor to unnecessary complexity, increase in computing requirements and vulnerability. This unfortunate side effect of modern software development practices affects most software products and is especially severe for the commercial off-the-shelf (COTS) software [1] [2]. It is also expected that a large percentage of Navy systems software components were adopted from COTS components and are not specifically built from scratch for the Navy.

Until recently software developers have relied on the increasing capacity of hardware to compensate for increased software inefficiency, but the benefits of the so-called Moore�s Dividend are running out [3]. While the number of transistors on a chip is still doubling every two years, the gain in number of transistors can no longer be used to increase individual processor performance due to insufficient instruction level parallelism in a program and a chips power dissipation limit. Instead, the gain is being used to increase the number of processors on a chip. Therefore, unless the application itself is highly parallel in nature the potential performance improvement from increased hardware capacity has reached its limit. To accommodate future computing requirements it is necessary that accidental growth be minimized. Hence, software efficiency is becoming more important.

Current software development practices (particularly reliance on shared libraries, elaborate class hierarchies, and layers of function calls), while increasing programmer productivity, also lead to software bloat and inefficient program execution. Existing compiler technology generally includes optimization options, but it neither removes unneeded or unreachable code from dynamically linked libraries nor simplifies class hierarchies. Because of this, existing technologies do not significantly reduce software bloat nor improve execution efficiency. Tools are needed to reduce software bloat and collapse software layers and thus improve software efficiency and robustness without impacting developer productivity.

The objective of this solicitation is to develop a tool which can substantially improve the efficiency and robustness of binary executables by performing whole-program optimization directly on compiled programs. A tool that successfully implements this goal will dramatically improve the way software is developed and deployed allowing program tailoring into the particular deployment environment. This can provide new optimizations available late in the development process, and even by the end user during the program installation time and beyond. This tool will provide headroom for future growth of software and the associated computing requirement and reduce vulnerability. It will also be immediately beneficial for computing environments where computing resources and power are at a premium, such as in a mobile and battery operated computing environment whose use by war-fighters is currently on the rise.

PHASE I: Architectural analysis and design of a tool for reclaiming program efficiency and reducing bloat from binary code. Develop a detailed and comprehensive plan for Phase II and minimal functionality, and minimal functionality proof of concept for Automated Program Transformation for Reclaiming Execution Efficiency tool. Identify the metrics that determine the efficacy of the proposed tool.

PHASE II: Develop a full functioning prototype of a tool which substantially improves the efficiency of binary execution. Demonstrate the efficacy of the tool.

PHASE III: The tool would be valuable for both the Navy as well as for civilian and commercial use. Besides providing room for future growth in Navy systems, it also provides reduction in power usage/requirement to current software executables. It will be very advantageous for mobile and battery powered devices where both power and computing resources are limited. It will be a stand-alone tool which can be used to improve program execution efficiency and security. Once matured, it can be integrated into software deployment process for Navy�s systems.

PRIVATE SECTOR COMMERCIAL POTENTIAL/DUAL-USE APPLICATIONS: APTREE could be a valuable tool for both the Navy as well as for civilian and commercial use. It could provide improvements in program efficiency and reduction in hardware requirements, as well as reduction in power usage/requirements to current software executables. It will be very advantageous for mobile and battery powered devices where both power and computing resources are limited. It is applicable to both general computing as well as embedded computing applications. A properly marketed and successfully developed project has the potential in the private sector as a stand-alone tool (directly marketed to computer/mobile-computing users), as part of operating system's application support, or as part of a software development environment.

REFERENCES:
1. N. Mitchell, G. Sevitsky, H. Srinivasan, The Diary of a Datum: An Approach to Modeling Runtime Complexity in Framework-Based Applications, Workshop on Library-Centric Software Design (LCSD), at Object-Oriented Programming, Systems, Languages and Applications (OOPSLA) 2005.

2. G. Xu, N. Mitchell, M. Arnold, A. Rountev, and G. Sevitsky. Software Bloat Analysis: Finding, Removing, and Preventing Performance Problems in Modern Large-Scale Object-Oriented Applications. In 2010 ACM SIGSOFT FSE/SDP Working Conference on the Future of Software Engineering Research, Santa Fe, NM, Nov 2010.

3. J. Larus. Spending Moore�s Dividend. In Communications of the ACM, volume 52, no. 5, pages 62-69, May 2009.Matthew Arnold, Stephen Fink, Vivek Sarkar, and Peter F. Sweeney. A Comparative Study of Static and Profile-Based Heuristics for Inlining. Proceedings of the ACM Workshop on Dynamic and Adaptive Compilation and Optimization (DYNAMO �00), Jan 2000.

4. Susan Horwitz, Thomas W. Reps, David Binkley. Interprocedural Slicing Using Dependence Graphs. ACM Transactions on Programming Languages and Systems, volume 12(1), pp. 26-60, 1990.

5. David F. Bacon. Fast and Effective Optimization of Statically Typed Object-Oriented Languages. PhD thesis, Computer Science Division, U. of California, Berkeley, Dec 1997. Report No. UCB/CSD-98-1017.

6. David Grove, Greg DeFouw, Jeffrey Dean, Craig Chambers, Call Graph Construction in Object-Oriented Languages. Proceedings of the 12th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA �97), 1997.

7. George C. Necula. Translation Validation for an Optimizing Compiler. Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI00), Vancouver, British Columbia, Canada, Jun 18-21, 2000.

8. Amir Pnueli, Michael Siegel, and Eli Singerman. Translation Validation. In Proceedings of the Fourth International Conference of Tools and Algorithms for Construction and Analysis of Systems (TACAS �98), 1998.

9. Peter F. Sweeney and Frank Tip. Extracting Library-Based Object-Oriented Applications. Proceedings of the Eighth International Symposium on the Foundations of Software Engineering (FSE 2000), 2000.

10. Peter F. Sweeney and Frank Tip. A Study of Dead Data Members in C++ Applications. In Proceedings of the ACM SIGPLAN �98 ACM Conference on Programming Language Design and Implementation (PLDI 98), 1998.

11. Frank Tip, Jong-Deok Choi, John Field, and G. Ramalingam. Slicing Class Hierarchies in C++. Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA �96), 1996.

12. Frank Tip and Peter F. Sweeney. Class Hierarchy Specialization. In Acta Informatica 36: 927-982, 2000.

KEYWORDS: Robust software, software efficiency, efficiency reclamation, software de-bloating, binary program transformation, program specialization, program slicing.

** TOPIC AUTHOR (TPOC) **

DoD Notice:   Between 16 November, 2012 through 16 December 2012, you may talk directly with the Topic Authors (TPOC) to ask technical questions about the topics. Their contact information is listed above. For reasons of competitive fairness, direct communication between proposers and topic authors is not allowed starting 17 December, 2012, when DoD begins accepting proposals for this solicitation.

However, proposers may still submit written questions about solicitation topics through the DoD's SBIR/STTR Interactive Topic Information System (SITIS), in which the questioner and respondent remain anonymous and all questions and answers are posted electronically for general viewing until the solicitation closes. All proposers are advised to monitor SITIS (13.1 Q&A) during the solicitation period for questions and answers, and other significant information, relevant to the SBIR 13.1 topic under which they are proposing.

If you have general questions about DoD SBIR program, please contact the DoD SBIR Help Desk at (866) 724-7457 or email weblink.