Algorithmic Profiling
Staff - Faculty of Informatics
Start date: 6 February 2013
End date: 7 February 2013
You are cordially invited to attend the PhD Dissertation Defense of Dmitrijs ZAPARANUKS on Wednesday, February 6th 2013 at 18h00 in room A11 (Red building)
Abstract:
Any software system has a primary, functional purpose, which could be formulated with an algorithm. The efficiency of an algorithm traditionally is characterized by complexity analysis. In this dissertation, we use the one aspect of algorithms that drives up their asymptotic complexity – repetition, in the form of loops and recursions – to assess the performance as well as the design of software systems.
First, we use repetitions to determine the algorithmically essential parts of a software system. Those parts of a system that are not algorithmically essential represent aspects of the design. A large portion of inessential parts is indicative of “over-design”, where a small portion indicates a lack of modularization.
Second, we use repetitions for performance analysis. Traditional profilers identify where a program spends most of its resources. They do not provide information about why the program spends those resources, or about how resource consumption would change for different program inputs. We introduce the idea of algorithmic profiling. While a traditional profiler determines a set of measured cost values, an algorithmic profiler determines a cost function. It does that by automatically determining the “inputs” of a program, by measuring the program’s “cost” for any given input, and by inferring an empirical cost function.
In our thesis we describe our algorithms and approaches for measuring essence and for algorithmic profiling, we describe our implementations of those approaches, and we show how they can be used in practice.
Dissertation Committee:
- Prof. Matthias Hauswirth, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Walter Binder, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Mehdi Jazayeri, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Paola Inverardi, University of L'Aquila, Italy (External Member)
- Prof. James Noble, Victoria University of Wellington, New Zealand (External Member)
- Prof. Jan Vitek, Purdue University, USA (External Member)
