07-11-2009, 04:08 PM
Interest in adaptive computing systems has increased dramatically in the past few years, and a variety of techniques now allow software to adapt dynamically to its environment. Two revolutions in the computing field are driving this development. First is the emergence of ubiquitous computing, which focuses on dissolving traditional boundaries for how, when, and where humans and computers interact. For example, mobile computing devices must adapt to variable conditions on wireless networks and conserve limited battery life. Second is the growing demand for autonomic computing, which focuses on developing systems that can manage and protect themselves with only high-level human guidance. This capability is especially important to systems such as financial networks and power grids that must survive hardware component failures and security attacks.
There are two general approaches to implementing Software adaptation. Parameter adaptation modifies program variables that determine behavior. The Internet's Transmission Control Protocol is an often-cited example: TCP adjusts its behavior by changing values that control window management and retransmissions in response to apparent network congestion. But parameter adaptation has an inherent weakness. It does not allow new algorithms and components to be added to an application after the original design and construction. It can tune parameters or direct an application to use a different existing strategy, but it cannot adopt new strategies. By contrast, compositional adaptation exchanges algorithmic or structural system components with others that improve a program's fit to its current environment. With compositional adaptation, an application can adopt new algorithms for addressing concerns that were unforeseen during development. This flexibility supports more than simple tuning of program variables or strategy selection. It enables dynamic recomposition of the software during execution-for example, to switch program components in and out of a memory-limited device or to add new behavior to deployed systems.
What is compositional adaptation?
Compositional adaptation enables software to modify its structure and behavior dynamically in response to changes in its execution environment. The complexity comes from three dimensions. First, there are more users. Now everyone, not just trained professionals, uses software. Second, there are more systems and more interactions among them. Third, there are more resources and goals.
Compositional adaptation exchanges algorithmic or structural system components with others that improve a program are fit to its current environment. It enables dynamic recomposition of the software during execution, which means it provides switching of program components in and out of a memory-limited device or to add new behavior to deployed systems.
We can classify opportunities for adaptivity into three categories:
Application-level adaptivity: A variety of mathematical models may be available to describe the science of a given problem. Some of these models may be more accurate than others but they may also have higher computational and storage requirements. A simulation code may find it advantageous to switch adaptively between such models to trade off accuracy for computational time and resources. For example, consider a chemically-reacting-flow simulation of an internal-combustion engine. Chemical reaction between the fuel and air occurs in both the intake stroke and the power stroke, but the rate of reaction during the intake stroke is so slow that the simulation can ignore the reaction during this stroke, modeling it only in the power stroke. This reduces computational requirements without affecting the accuracy of results.
Algorithm-level adaptivity: There may be many algorithms for implementing a desired functionality, and it may be advantageous to switch between algorithms to adapt to resource availability or to properties of the desired output. For example, an out-of-core sorting algorithm may use a divide-and-conquer style algorithm like merge-sort when the array size is large, and switch to an iterative, in-place sorting algorithm like insertion-sort once the size of the sub-array to be sorted becomes small enough to fit into cache. The divide-and-conquer algorithm performs better on a memory hierarchy but once the sub-array is small enough, the simple iterative algorithm is more efficient because it has lower recursive overhead.
System-level adaptivity: Fault-tolerant computers adapt to hardware failure to ensure system survival. Portable devices can change quality of service (QoS) to adapt to available resources; for example, an Internet device can display color and images when a high bandwidth connection is available, but switch to black-and-white and suppress images when bandwidth is insufficient.