Nanocomputers-Theoretical Models
Traditional Models of Computation
Download 0.53 Mb.
|
- Navigate this page:
- Fundamental Limits Violated Opportunities Leveraged
- Turing machines.
- RAM machine.
- Cellular automata.
Traditional Models of ComputationIn this section, we systematically survey a wide variety of early models of computing, and identify exactly which of the limits or opportunities listed in the previous section each one fails to account for, which result in the model’s lacking one or the other of the properties of physical realism (PR) or universal maximal scalability (UMS). Furthermore, we consider what types of costs are respected in the model. In the next section, we will present the newer models which may actually come close to being both PR and UMS for all practical purposes in the foreseeable future. Here are some contributions to real-world costs that an economically-thorough cost model ought to take into account:
Traditional computational complexity theory (cf. [29]) considers purely time-proportional costs like item 2, simplified to just the total number of discrete time-steps (clock ticks) performed (i.e., assuming a fixed rate of steps per unit time), and dubbed time complexity. It also considers a rough measure of manufacturing cost, in the form of the total number of bits of storage required to perform the computation, and calls this space complexity. However, most work in complexity theory doesn’t combine the two in the natural way suggested by items 2b-2e, which is that real costs are usually proportional to both space and time, or in other words to the spacetime utilized, that is to say, the cost to rent the required amount of hardware for the amount of time needed to perform the computation, and to other costs that can be assumed to scale proportionally to this quantity, such as maintenance cost, opportunity cost, and energy used (typically). Some cost models in complexity theory count the number of fixed-size computational operations that are performed, rather than the number of parallel steps. This comes closer to spacetime cost, but still does not quite hit the mark, since there are real costs even associated with those bits that are just sitting statically and not being operated on at all. (Hardware rental cost, maintenance cost, opportunity cost.) Newer models such as VSLI theory (cf. [30]) address these problems somewhat by considering the hardware efficiency of algorithms, which is essentially the reciprocal of their spacetime usage. However, these models still do not usually integrate the cost of energy into the analysis in a way that treats it as somewhat independent from spacetime cost, which it is, as we will see. Table 3 below summarizes how a variety of existing theoretical models of computation fare with respect to the fundamental limits and opportunities discussed in sec. 2, and the costs discussed above. Discussion follows.
Table 3. We can compare various models of computation as to which fundamental physical limits they violate (see table 1), which opportunities for more efficient computing they leverage (table 2), and which aspects of cost (see list above) they take into account. Opportunity #2 gives the number of dimensions explicitly or implicitly assumed by the model; 3 or more is unrealistic, 2 or less is under-ambitious. Cost measure #3 (spacetime) is denoted “½-way considered” if spacetime cost could be easily measured in the model, but is typically ignored instead. Note that the quantum reversible 3-D mesh model described in sec. 6 below (first introduced in [Error: Reference source not found]) strictly dominates all earlier models in realism and comprehensiveness, so long as gravity (limit #10) is not a concern, which we can expect to remain true for very long time. (This limit would only become relevant if/when we come to build computer systems of near black-hole density, e.g., by building them out of several suns’ worth of matter, or alternatively by somehow achieving an average device-pitch scale nearly as small as the Planck length scale of fundamental particles. Both of these possibilities seem extremely distant at present, to say the least.) Turing machines. The Turing machine [33] was the first universal, physically-evocative (as opposed to totally abstract and formal) model of computation. It has a single fixed-size processor (the head), and a memory laid out in one dimension that is accessed in serial fashion (the tape). The Turing machine model does not violate any of the fundamental physical limits on information processing, and therefore it is physically realistic. However, since a Turing machine has only a single, fixed-size “processor” (the tape head), it does not leverage the possibility of parallelism. Multi-tape and multi-head Turing machines provide limited parallelism, but true parallelism in the model requires that the number of processors must be scaled up in proportion to the information capacity of the machine. Turing machine models usually do not try to do this, but later we will see other models that do. It is possible to analyze space and time costs in a Turing machine model, but the joint spacetime cost is not usually a concern, since the model has such understated efficiency in any case. Due to its drastic sub-optimality, the Turing machine and related models are primarily only suitable for the following purposes:
These concerns are generic ones in computing, and are not tied to nanocomputing specifically, but can be used in that context as well. However, if one wishes a more precise model of costs to perform a desired computation than can be provided by Turing machines, one must turn to other models. RAM machine. One limitation of the Turing machine was that since the memory tape was laid out serially in only one dimension, merely traversing it to arrive at a desired item consumed a large portion of the machine’s time. For early electronic memories, in contrast, the time required for a signal to traverse the distance through the machine was negligible in comparison to the time taken to perform logic operations. Therefore, it was useful to model memory access as requiring only a single step, regardless of the physical distance to the desired memory location. This fast memory access model is the defining characteristic of the RAM or Random-Access Machine model of computation [Error: Reference source not found]. The RAM model is occasionally called the von Neumann machine model, after the inventor of architectures having a CPU with a separate random-access memory for storing programs and data. The RAM model is also sometimes extended to a parallel model called the PRAM. Today, however, individual transistors have become so fast that the speed-of-light travel time across an ordinary-sized machine is becoming a significant limiting factor on the time required to access memory, especially for computations requiring large-scale supercomputers having large numbers of processors. For example, at the 3 GHz processor clock speeds that are now routinely available in COTS (commercial off-the-shelf) microprocessors, light can only travel 10 cm in 1 clock cycle, so the memory accessible within a round-trip latency of 1 cycle is limited to, at most, the amount that will fit within a 5-cm radius sphere centered on the processor. (In practice, at present, the situation is even worse than this, because the time to access today’s commercial memory technologies is much greater than the speed-of-light travel time.) And, when considering a wide-area distributed computation, communication halfway around the Earth (i.e., ~20,000 km) requires at least 200 million clock cycles! Delays like these can be worked around somewhat by using architectural latency hiding techniques in processor architectures and parallel algorithms, but only to a very limited extent [Error: Reference source not found,35]. Furthermore, these problems are only going to get worse as clock speeds continue to increase. Communication time is no longer insignificant, except for the restricted class of parallel computations that require only very infrequent communication between processors, or for serial computations that require only small amounts of memory. For more general purposes, the RAM-type model is no longer tenable. Slightly more realistic than the RAM are models that explicitly take communication time into account, to some extent, by describing a network of processing nodes or logic gates that pass information to each other along explicit communication links. However, depending on the topology of the interconnection network, these models may not be physically realistic either. Binary trees, fat trees, hypercubes, and butterfly or omega networks are all examples of interconnection patterns in which the number of locations accessible within n hops grows much faster than n3, and therefore, these networks are impossible to implement with unit-time hops above a certain scale within ordinary 3-dimensional space. The only scalable networks in 3-d space are the locally-connected or mesh type networks, and subgraphs of these [Error: Reference source not found,Error: Reference source not found]. Cellular automata. Cellular automaton (CA) models, also originally due to von Neumann [36], improve upon the RAM-type or abstract-network model in that they explicitly recognize the constraints imposed by communication delays through ordinary Euclidean space. CAs are essentially equivalent to mesh-interconnected networks of fixed-capacity processors. The 1-dimensional and 2-dimensional CA variations are entirely physically realistic, and the 2-d CA can be used as a starting point for developing a more detailed theoretical or engineering model of today’s planar circuits, such as, for example, the VLSI (Very Large-Scale Integrated circuit) theory of Leiserson [Error: Reference source not found]. However, ordinary CAs break down physically when one tries to extend them to 3 dimensions, because the entropy that is inevitably produced by irreversible operations within a 3-d volume cannot escape quickly enough through the 2-d surface. To circumvent this constraint while still making some use of the 3rd dimension requires avoiding entropy production using reversible models, such as we will discuss in section . These models can be shown to have better cost-efficiency scaling than any physically possible non-reversible models, even when taking the overheads associated with reversibility into account [Error: Reference source not found]. Finally, all of the above models, in their traditional form, miss the opportunity afforded by quantum mechanics of allowing machine states that are superpositions (weighted combinations) of many possible states, within a single piece of hardware, which apparently opens up drastic shortcuts to the solution of at least certain specialized types of problems. We will discuss quantum models further in section .
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||