Program Efficiency

Program efficiency is vital in the context of real world applications. A program which performs DNA sequence analysis, for example, is of little use if it takes years to run. Similarly, locating data in a database is of limited use if each query takes hours to succeed.

Our study of program efficiency is motivated by the application of theoretical techniques (the study of computational complexity, algorithm analysis and program refinement) to the development of practical tools (for the performance monitoring of programs, prescriptive performance tuning and predictive cross-platform performance analysis) which can be used in the development of efficient program solutions.

Applications of the work include:

Genome analysis: Sequence analysis, genome signature analysis, methods for the identification of horizontally acquired DNA (work with the Institute of Molecular Medicine at Oxford University);

Data storage and retrieval of program performance data: using XML and XQL (work with Microsoft Research in Cambridge);

Performance monitoring and prediction of parallel and functional programs (work with the Oxford University Computing Laboratory and Sychron Ltd).

Staff involved: Stephen Jarvis