Many properties of computer and software systems cannot be inferred from detailed analyses of their components: Chip performance is not easily predicted from the layout of transistors and wires; the rate of traffic flow on the Internet is not a simple function of the number of routers or hosts (relevant to the NSF-sponsored GENI project); it is not known how much power will be required to support the search engines of the future; and, there are few effective conceptual tools to comprehend the ever-increasing complexity of our software code base. Engineers often rely on rules of thumb to describe scaling behavior in computing, for example, Moore's Law for processors, Rent's Rule for wiring, and the well-known 80-20 rule for software execution. However, these are empirical observations, not theoretical derivations or proofs. The situation is similar to biology, where scaling behavior was documented for many years before a theoretical framework was discovered to explain the empirical observations. Perhaps the most famous example is that of metabolic rate, which varies as the 3/4 power of body mass across many orders of magnitude (e.g., from shrews to whales). A theoretical derivation from first principles was proposed in 1997, and since then scaling theories have been developed to explain a wide range of observations in living and social systems.
Computational complexity theory provides a principled method for predicting the scaling behavior of algorithms, but we have no similar theory for other parts of computer science. Simulation and empirical laws fill the gap, but a general predictive theory would be much more satisfying and believable, especially in areas where we project radical technological change. What is needed is a "scaling theory for the rest of computer science." The proposed research will develop such a theory, based on a method that has proven successful for biology---metabolic scaling theory.
Scaling describes how some property of a system varies systematically with some other property such as size. Metabolic scaling laws correspond to the class of polynomial time algorithms in computer science, where the running time of an algorithm scales as a fixed power of the size of the input. In biology, such relations arise because the distribution of resources (e.g., energy and nutrients) to individual components (e.g., cells) is a dominant design constraint, determining what sorts of organisms can evolve through natural selection. For example, vascular systems deliver oxygen to every cell in the body, and as body size increases, network constraints limit the metabolic rate of individual cells. This is similar to wire scaling issues that arise with increasing chip sizes. The mathematical derivations are complicated, but they rely on a few basic assumptions: (1) Resources are distributed through internal space-filling (fractal) networks; (2) Terminal units in the network (e.g., capillaries) are of invariant size; (3) The design is optimized to maximize metabolic rate and minimize transport times. By combining these assumptions with fundamental physical constraints (e.g., organisms are 3-dimensional) and conservation laws (e.g., conservation of matter and energy), the exact scaling metabolic relations have been derived in biology.
The project will apply concepts of metabolic scaling to three areas of information processing: i) the wiring of mammalian brains as reflected in the distribution of gray (neurons, the information processors) and white (axons, the information transmitting fibers) matter; ii) chip microarchitecture with regard to wire/transistor scaling and power efficiency; and iii) traffic on the Internet as a function of the quantity of information being processed and the terminal units (access points) in the network. The research has three phases: i) Collect and evaluate existing scaling laws and empirical rules of thumb; ii) Derive these scaling relations from first principles; and iii) Develop analytical and computer simulation models that make quantitative, testable predictions. The three topics represent a logical progression of information processing systems, starting with the brain (based in biology with its three dimensions and electro/physical transport systems), then moving to silicon-based chip design (still tied closely to physical processes, geometries, and conservation laws), and finally moving to the Internet (where geometry has a physical component but is less constrained and conservation laws are not well understood).
