BIC: Collaborative Research: A Biologically Motivated Scaling Theory for

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

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