Seminars at the Faculty of Informatics

High-level Caching in Optimization Aspects

The Faculty of Informatics is pleased to announce a seminar given by Karl Lieberherr

DATE: Monday, July 25th 2011
PLACE: USI Università della Svizzera italiana, room SI-008, Informatics building (Via G. Buffi 13)
TIME: 14.30

Caches can be used to avoid running the same intermediate computation more than once, to speed up subsequent computations, and to reorganize computations by precomputing and storing certain intermediate computations, etc. All these techniques can lead to improved asymptotic runtime complexity of programs or to reduced constant factors.

There are two main drawbacks to expressing cache-based optimization aspects in AspectJ-like general purpose aspect-oriented programming languages, reduced safety and low-level of abstraction. In this paper we propose an AspectJ extension for expressing cache-based optimization aspects more safely at a higher level of abstraction.

We illustrate the language with well-known examples: Dijkstra's shortest path algorithm, topological ordering and the closest pair algorithm. We noticed that in algorithm textbooks a clean but not so efficient algorithm description is followed by an implementation paragraph which refines the algorithm into an efficient implementation. Our cache-based optimization aspects formalize the "implementation paragraphs" by expressing them in a programming language. We hope that our new language will encourage software developers to think more systematically about how to speedup their software while keeping it easy to read and understand.

Joint work with Ahmed Abdelmeged.

Karl Lieberherr started his research career in computer science as a theoretical computer scientist, focusing on the theory of P-optimal algorithms for the generalized maximum satisfiability problem (MAX-CSP), still an active area of research. This work has motivated the development of a crowdsourcing platform for refutation-based, constructive scientific domains, called the Scientific Community Game. He also invented, independently and simultaneously on the other side of the Atlantic, an early form of non-chronological backtracking based on learned clauses (superresolution) which has become a key feature of most state-of-the-art SAT and CSP solvers. In the mid 1980s, he switched to his current research area: Object-Oriented and Aspect-Oriented Software Development and focused on issues of software design and modularity. He founded the Demeter research team, which studied the then-novel idea of Adaptive Programming, also known as structure-shy programming and produced the Law of Demeter ("talk only to your friends": an explicit form of coupling control) and several systems for separating concerns in an object-oriented programming context: Demeter/Flavors, Demeter/C++, DemeterJ, DJ, XAspects and DemeterF. Dr. Lieberherr is a Professor in the College of Computer and Information Science at Northeastern University.

HOST: Prof. Walter Binder

URL 1: