Title: Predicting program events for mobile programming
Abstract: Prediction has become fundamental to the performance of many computer applications and systems. Predictive techniques permeate all areas from low level hardware to complex user actions. In order to predict, a model of future behavior is created. Previous statistical and heuristic prediction techniques ignore an important source of information: the architecture of the system being modelled. Analysis of the internal architecture of a system can often provide a more specific model. In this work, program analysis is used to create a model of a program's future behavior.
Shape analysis has been previously used to determine static program properties including extraction of type information and reduction of synchronization primitives. We develop an access analysis based on shape analysis that can be used to predict the future actions of a program. The analysis purposely folds all data paths emanating from a program point in order to provide summaries of program actions that will occur after the program point has been executed. The summaries generated only include program data manipulations.
The shape graphs produced during access analysis model the actual program's data manipulations. A runtime predictor interprets the shape graph model over the program's runtime data producing a summary of the program's future data access operations. This work first demonstrates a predictor for prefetching based on an ordering of expected object acceses. The predictor has also been applied to the area of transaction scheduling. In this case, the total locks held and expected lock order is used to increase concurrency of transactions. Program execution time is also predictable using a similar technique. We show how such a predictor is used to estimate the length needed for leases, thus balancing message costs and recovery time.
These techniques have been implemented in Mokan, a system for mobile distributed programming and mobile applications. The system provides programmers with several simplifying language features including transactions and replication combined with a novel runtime architecture providing automatic prefetching and lease estimation.
Publication Year: 2004
Publication Date: 2004-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot