No description available.

This thesis introduces FlowGSP, a general-purpose sequence mining algorithm for flow graphs. FlowGSP ranks sequences according to the frequency with which they occur and according to their relative cost. This thesis also presents two parallel implementations of FlowGSP. The first implementation uses JavaTM threads and is designed for use on workstations equipped with multi-core CPUs. The second implementation is distributed in nature and intended for use on clusters. The thesis also presents results from an application of FlowGSP to mine program profiles in the context of the development of a dynamic optimizing compiler. Interpreting patterns within raw profiling data is extremely difficult and heavily reliant on human intuition. FlowGSP has been tested on performance-counter profiles collected from the IBM WebSphere Application Server. This investigation identifies a number of sequences which are known to be typical of WebSphere Application Server behavior, as well as some sequences which were previously unknown.

No description available.

abstract: Software Managed Manycore (SMM) architectures - in which each core has only a scratch pad memory (instead of caches), - are a promising solution for scaling memory hierarchy to hundreds of cores. However, in these architectures, the code and data of the tasks mapped to the cores must be explicitly managed in the software by the compiler. State-of-the-art compiler techniques for SMM architectures require inter-procedural information and analysis. A call graph of the program does not have enough information, and Global CFG, i.e., combining all the control flow graphs of the program has too much information, and becomes too big. As a result, most new techniques have informally defined and used GCCFG (Global Call Control Flow Graph) - a whole program representation which captures the control-flow as well as function call information in a succinct way - to perform inter-procedural analysis. However, how to construct it has not been shown yet. We find that for several simple call and control flow graphs, constructing GCCFG is relatively straightforward, but there are several cases in common applications where unique graph transformation is needed in order to formally and correctly construct the GCCFG. This paper fills this gap, and develops graph transformations to allow the construction of GCCFG in (almost) all cases. Our experiments show that by using succinct representation (GCCFG) rather than elaborate representation (GlobalCFG), the compilation time of state-of-the-art code management technique [4] can be improved by an average of 5X, and that of stack management [20] can be improved by an average of 4X. / Dissertation/Thesis / Masters Thesis Computer Science 2014

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第25425号 / 情博第863号 / 新制||情||144(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 森 信介, 教授 中村 裕一, 教授 鹿島 久嗣 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Profiling techniques to detect performance bugs in applications are usually customized to detect a specific bug pattern and involve significant engineering effort. In spite of this effort, many techniques either suffer from high runtime overheads or are imprecise. This necessitates the design of a common and efficient instrumentation substrate that profiles the flow of objects during an execution. Designing such a substrate which enables profile generation precisely with low overhead is non-trivial due to the number of objects created, accessed and paths traversed by them in an execution. In this thesis, we design and implement an efficient instrumentation substrate that efficiently generates object flow profiles for Java programs, without requiring any modifications to the underlying virtual machine. We achieve this by applying Ball-Larus numbering on a specialized hy-brid ow graph (hfg). The hfg path profiles that are collected during runtime are post-processed o ine to derive the object flow profiles. We extend the design to handle inter-procedural objec flows by constructing flow summaries for each method and incorporating them appropriately. We have implemented the substrate and validated its efficacy by applying it on programs from popular benchmark suites including dacapo and java-grande. The results demonstrate the scalability of our approach, which handles 0.2M to 0.55B object accesses with an average runtime overhead of 8x. We also demonstrate the effectiveness of the generated profiles by implementing three client analyses that consume the profiles to detect performance bugs. The analyses are able to detect 38 performance bugs which when refactored result in signi cant performance gains (up to 30%) in running times.

Depending on the role of software in everyday life, the cost of a software failure can sometimes be unaffordable. During system execution, errors may occur in system components and failures may be manifested due to these errors. These errors differ with respect to their effects on system behavior and consequent failure manifestation manners. Predicting failures before their manifestation is important to assure system resilience. It helps avoid the cost of failures and enables systems to perform corrective actions prior to failure occurrences. However, effective runtime error detection and failure prediction techniques encounter a prohibitive challenge with respect to the control flow representation of large software systems with intricate control flow structures. In this thesis, we provide a technique for failure prediction from runtime errors of large software systems. Aiming to avoid the possible difficulties and inaccuracies of the existing Control Flow Graph (CFG) structures, we first propose a Connection Dependence Graph (CDG) for control flow representation of large software systems. We describe the CDG structure and explain how to derive it from program source code. Second, we utilize the proposed CDG to provide a connection-based signature approach for control flow error detection. We describe the monitor structure and present the error checking algorithm. Finally, we utilize the detected errors and erroneous state parameters to predict failure occurrences and modes during system runtime. We craft runtime signatures based on these errors and state parameters. Using system error and failure history, we determine a predictive function (an estimator) for each failure mode based on these signatures. Our experimental evaluation for these techniques uses a large open-source software (PostgreSQL 8.4.4 database system). The results show highly efficient control flow representation, error detection, and failure prediction techniques. This work contributes to software reliability by providing a simple and accurate control flow representation and utilizing it to detect runtime errors and predict failure occurrences and modes with high accuracy. / Thesis (Ph.D, Computing) -- Queen's University, 2012-09-25 23:44:12.356

No description available.

No description available.

No description available.