Lo, Kwun Kit. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 153-161). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Existing Approaches in Program Understanding --- p.2 / Chapter 1.1.1 --- Localized Program Understanding --- p.2 / Chapter 1.1.2 --- Whole System Analysis --- p.3 / Chapter 1.2 --- Example of Function Execution Probability Reduction of the Call Graph --- p.5 / Chapter 1.3 --- Organization of the Dissertation --- p.7 / Chapter 2 --- Preliminary Study --- p.8 / Chapter 2.1 --- Participants --- p.8 / Chapter 2.2 --- Study Design --- p.8 / Chapter 2.3 --- ispell --- p.10 / Chapter 2.3.1 --- Subject I1 (ispell) --- p.10 / Chapter 2.3.2 --- Subject PG1 (ispell) --- p.12 / Chapter 2.3.3 --- Subject PG2 (ispell) --- p.13 / Chapter 2.3.4 --- Subject I2 (ispell) --- p.14 / Chapter 2.3.5 --- ispell Analysis --- p.15 / Chapter 2.4 --- FreeBSD Kernel Malloc --- p.15 / Chapter 2.4.1 --- Subject I1 (FreeBSD) --- p.16 / Chapter 2.4.2 --- Subject PG1 (FreeBSD) --- p.17 / Chapter 2.4.3 --- Subject PG2 (FreeBSD) --- p.18 / Chapter 2.4.4 --- Subject I2 (FreeBSD) --- p.20 / Chapter 2.4.5 --- FreeBSD Analysis --- p.20 / Chapter 2.5 --- Threats to Validity --- p.21 / Chapter 2.6 --- Summary --- p.22 / Chapter 3 --- Approach --- p.24 / Chapter 3.1 --- Building Branch-Preserving Call Graphs --- p.26 / Chapter 3.1.1 --- Branch Reserving Call Graphs --- p.26 / Chapter 3.1.2 --- Branch-Preserving Call Graphs --- p.28 / Chapter 3.1.3 --- Example of BPCG Building Process --- p.31 / Chapter 3.2 --- System Function Removal --- p.34 / Chapter 3.3 --- Function Rating Calculation --- p.35 / Chapter 3.3.1 --- Rating Algorithm Complexity --- p.38 / Chapter 3.4 --- Building the Colored Call Graph --- p.39 / Chapter 3.5 --- Call Graph Reduction --- p.39 / Chapter 3.5.1 --- Remove-high-fan-in-functions Approach (FEPR-fanin) --- p.39 / Chapter 3.5.2 --- Remove-leaf-nodes Approach (FEPR-leaf) --- p.41 / Chapter 4 --- Validation --- p.42 / Chapter 4.1 --- Measures --- p.43 / Chapter 4.1.1 --- Inclusion Accuracy (IA) --- p.43 / Chapter 4.1.2 --- Reduction Efficiency (RE) --- p.44 / Chapter 4.1.3 --- Stability (S) --- p.45 / Chapter 4.2 --- Analysis of FEPR Techniques --- p.45 / Chapter 4.2.1 --- Settings --- p.45 / Chapter 4.2.2 --- Inclusion Accuracy (IA): --- p.47 / Chapter 4.2.3 --- Reduction Efficiency (RE): --- p.47 / Chapter 4.2.4 --- Stability (S) --- p.48 / Chapter 4.3 --- Ying and Tarr´ةs Approach --- p.48 / Chapter 4.3.1 --- Settings --- p.50 / Chapter 4.3.2 --- Inclusion Accuracy (IA) --- p.50 / Chapter 4.3.3 --- Reduction Efficiency (RE) --- p.51 / Chapter 4.3.4 --- Stability (S) --- p.51 / Chapter 4.4 --- Centrality Measure Approach --- p.52 / Chapter 4.4.1 --- Inclusion Accuracy (IA) --- p.53 / Chapter 4.5 --- Top-down Search Approach --- p.56 / Chapter 4.5.1 --- Reduction Efficiency (RE) --- p.57 / Chapter 4.6 --- Synthesized Analysis --- p.58 / Chapter 4.6.1 --- Inclusion Accuracy (IA) --- p.58 / Chapter 4.6.2 --- Reduction Efficiency (RE) --- p.59 / Chapter 4.6.3 --- Stability (S) --- p.59 / Chapter 4.6.4 --- Threats to Validity --- p.59 / Chapter 4.7 --- Summary --- p.60 / Chapter 5 --- Discussion --- p.62 / Chapter 5.1 --- Flexibility of Analysis --- p.62 / Chapter 5.2 --- "Existence of Function Pointers, GOTOs and Early Exits" --- p.62 / Chapter 5.3 --- Precision of Branch-Preserving Call Graphs --- p.63 / Chapter 5.4 --- Function Ranking and Recommender System --- p.64 / Chapter 5.5 --- Extending the Approach Beyond C --- p.66 / Chapter 6 --- Related Work --- p.67 / Chapter 6.1 --- Existing Approaches in Program Understanding --- p.67 / Chapter 6.1.1 --- Localized Program Understanding --- p.67 / Chapter 6.1.2 --- Whole Program Analysis --- p.69 / Chapter 6.2 --- Branch Prediction and Static Profiling --- p.73 / Chapter 7 --- Conclusions --- p.76 / Chapter A --- Call Graphs in Case Studies --- p.78 / Chapter B --- Source Files for BPCG Builder --- p.85 / Bibliography --- p.153

Digitized by Kansas Correctional Industries

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Typescript (photocopy). / Digitized by Kansas Correctional Industries

No description available.

No description available.

Abstract not available

Abstract not available

Program optimizations analyze and transform the programs such that better performance results can be achieved. Classical optimizations mainly use the static properties of the programs to analyze program code and make sure that the optimizations work for every possible combination of the program and the input data. This approach is conservative in those cases when the programs show the same runtime behaviors for most of their execution time. On the other hand, profile-guided optimizations use runtime profiling information to discover the aforementioned common behaviors of the programs and explore more optimization opportunities, which are missed in the classical, non-profile-guided optimizations. Redundancy elimination is one of the most powerful optimizations in compilers. In this thesis, a new partial redundancy elimination (PRE) algorithm and a partial dead code elimination algorithm (PDE) are proposed for a profile-guided redundancy elimination framework. During the design and implementation of the algorithms, we address three critical issues: optimality, feasibility and profitability. First, we prove that both our speculative PRE algorithm and our region-based PDE algorithm are optimal for given edge profiling information. The total number of dynamic occurrences of redundant expressions or dead codes cannot be further eliminated by any other code motion. Moreover, our speculative PRE algorithm is lifetime optimal, which means that the lifetimes of new introduced temporary variables are minimized. Second, we show that both algorithms are practical and can be efficiently implemented in production compilers. For SPEC CPU2000 benchmarks, the average compilation overhead for our PRE algorithm is 3%, and the average overhead for our PDE algorithm is less than 2%. Moreover, edge profiling rather than expensive path profiling is sufficient to guarantee the optimality of the algorithms. Finally, we demonstrate that the proposed profile-guided redundancy elimination techniques can provide speedups on real machines by conducting a thorough performance evaluation. To the best of our knowledge, this is the first performance evaluation of the profile-guided redundancy elimination techniques on real machines.

This thesis describes the development of a decision support tool for unplanned maintenance of aircraft at ramp time during airport operations. Ramp time is the time between an aircraft arrival and its next departure. Clearance of an aircraft for flight is controlled by aviation regulations. Therefore decisions regarding maintenance are taken by engineers who have to comply with the regulations that are governed outside the organizational structure of the airline. Unplanned maintenance also often disrupts the normal operational scheduling and leads to significant costs. Therefore, the decision support tool must include the relevant aviation regulations, be capable of rescheduling to minimise disruption and be able to optimise solutions based on cost. In this project an aircraft schedule is used to demonstrate the procedures. An assumed fleet of six airplanes fly between three cities. Consultation with aviation experts ensured the size of the fleet and operations are realistic. A regulation database was developed based on the Master Minimum Equipment List (MMEL) for the aircraft, and a computer programme was developed to provide different options that comply with the regulations and take into account scheduling disruption and costs. In certain cases the regulations allow an aircraft to fly with some components inoperable so long as backup systems can perform the tasks. It is possible then to postpone the maintenance until the aircraft arrives at a properly equipped airport, or until a longer scheduled stopover reduces the disruption to operations. To address the engineering aspects of the project, maintenance of a single component that appears in the MMEL for the chosen aircraft is considered. To plan maintenance following a failure, the cause of the failure needs to be identified. Only then can the resources and time required to repair the defect be defined. The programme validation has confirmed it is able to balance different aspects of decisions related to unplanned aircraft ramp maintenance. Although the programme is based on an assumed fleet operation, the structure of the programme will allow it to be applied to other fleet and route configurations.