Multi-fidelity algorithms for interactive mobile applications
Mahadev Satyanarayanan, Dushyanth Narayanan · 1999
The concept of an algorithm has proved robust over half a century of advances in the speed and versatility of computing hardware and software.In this paper, we show why interactive mobile applicationsrequire us to rethink this concept from first principles.Such applications are difficult to support because they place heavy resource demands on hardware that is typically optimized for weight, size and battery life rather than compute power.We show how the notion of an algorithm can be extended to help alleviate this problem, and examine the implications of this shift in viewpoint.The paper is organized in three parts: rationale, research agenda, and related work.1 Rationale 1.1 Classical view of an algorithm Informally, an algorithm is a sequence of steps to accomplish some computing task.This task has a precisely-defined output specification.A sequence whose execution does not always meet this specification is not considered to be an algorithm for that task.For example, a sorting algorithm must preserve all its input elements but reorder them according to some precisely-defined sort criterion.No deviation from this specification is allowed in a candidate that claims to be a sorting algorithm.Resources such as time, space or energy needed to accomplish a task are dependent variables.As much of each resource is consumed as necessary to meet the output specification.The figure of merit of an algorithm is how sparingly it uses one or more of these resources while meeting the output specification.This research was supported by the Air Force