BIC: Collaborative Research: A Biologically Motivated Scaling Theory for

计算机和软件系统的许多特性不能从对其组件的详细分析中推断出来：芯片的性能不容易从晶体管和电线的布局中预测出来；互联网上的流量速率不是路由器或主机数量的简单函数（与nsf赞助的GENI项目有关）；目前还不知道需要多少电力来支持未来的搜索引擎；而且，很少有有效的概念性工具来理解我们的软件代码库日益增加的复杂性。工程师经常依靠经验法则来描述计算中的伸缩行为，例如，处理器的摩尔定律，布线的雷特法则，以及众所周知的软件执行的80-20法则。然而，这些都是经验观察，而不是理论推导或证明。这种情况类似于生物学，在发现一个理论框架来解释经验观察之前，缩放行为已经被记录了很多年。也许最著名的例子是代谢率，它随着体重的3/4次方而变化，跨越了许多数量级（例如，从鼩鼱到鲸鱼）。1997年提出了第一原理的理论推导，从那时起，尺度理论已经发展到解释生活和社会系统中的广泛观察。计算复杂性理论为预测算法的缩放行为提供了一种原则性的方法，但我们在计算机科学的其他部分没有类似的理论。模拟和经验法则填补了空白，但一般的预测理论将更令人满意和可信，特别是在我们预测激进技术变革的领域。我们需要的是一种“适用于计算机科学其他领域的尺度理论”。拟议的研究将发展这样一个理论，基于一种已被证明在生物学上成功的方法——代谢缩放理论。缩放描述了系统的某些属性如何随其他属性（如大小）而系统地变化。代谢缩放定律对应于计算机科学中的多项式时间算法，其中算法的运行时间按输入大小的固定幂进行缩放。在生物学中，这种关系的出现是因为资源（例如，能量和营养）分配给个体组成部分（例如，细胞）是一个主要的设计约束，决定了哪种生物可以通过自然选择进化。例如，血管系统将氧气输送到身体的每个细胞，随着身体尺寸的增加，网络限制了单个细胞的代谢率。这类似于随着芯片尺寸的增加而出现的线缩放问题。数学推导是复杂的，但它们依赖于几个基本假设：(1)资源通过内部空间填充（分形）网络分布；(2)网络中的终端单元（如毛细血管）大小不变；(3)优化设计，使代谢率最大化，运输时间最小化。通过将这些假设与基本的物理约束（例如，生物体是三维的）和守恒定律（例如，物质和能量守恒）相结合，在生物学中推导出了精确的缩放代谢关系。该项目将把代谢缩放的概念应用于信息处理的三个领域：1)哺乳动物大脑的布线，反映在灰质（神经元，信息处理器）和白质（轴突，信息传输纤维）的分布上；Ii)关于导线/晶体管缩放和功率效率的芯片微架构；以及iii)互联网上的流量作为正在处理的信息量和网络中的终端单元（接入点）的函数。研究分为三个阶段：1)收集和评价现有的标度定律和经验法则；ii)从第一性原理推导出这些比例关系；（三）发展分析和计算机模拟模型，作出定量的、可检验的预测。这三个主题代表了信息处理系统的逻辑进展，从大脑开始（基于具有三维和电/物理传输系统的生物学），然后转移到基于硅的芯片设计（仍然与物理过程，几何和守恒定律密切相关），最后转移到互联网（几何具有物理组成部分，但约束较少，守恒定律不被很好地理解）。

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).