Today computers have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I/O traffic to slower memories in the hierarchy. In this article, we study the computation of option pricing using the binomial and trinomial models on processors with a multilevel memory hierarchy. We derive lower bounds on memory traffic between different levels of the hierarchy for these two models. We also develop algorithms for the binomial and trinomial models that have near-optimal memory traffic between levels. We have implemented these algorithms on an UltraSparc IIIi processor with a 4-level of memory hierarchy and demonstrated that our algorithms outperform algorithms without cache blocking by a factor of up to 5 and operate at 70% of peak performance.

Error-correcting codes have been very successful in protecting against errors in data transmission. Computing on encoded data, however, has proved more difficult. In this paper we extend a framework introduced by Spielman [14] for computing on encoded data. This new formulation offers significantly more design flexibility, reduced overhead, and simplicity. It allows for a larger variety of codes to be used in computation and makes explicit conditions on codes that are compatible with computation. We also provide a lower bound on the overhead required for a single step of coded computation.

Stochastically assembled nanoscale architectures have the potential to achieve device densities 100 times greater than today's CMOS. A key challenge facing nanotechnologies is controlling parallel sets of nanowires (NWs), such as those in crossbars, using a moderate number of mesoscale wires. Three similar methods have been proposed to control NWs using a set of perpendicular mesoscale wires. The first is based on NW differentiation during manufacture, the second makes random connections between NWs and mesoscale wires, and the third, a mask-based approach, interposes high-K dielectric regions between NWs and mesoscale wires. Each of these addressing schemes involves a stochastic step in their implementation. In this paper, we analyze the mask-based approach and show that, when compared to the other two schemes, a large number of mesoscale control wires are necessary for its realization.

Methods for assembling crossbars from nanowires (NWs) have been designed and implemented. Methods for controlling individual NWs within a crossbar have also been proposed, but implementation remains a challenge. A NW decoder is a device that controls many NWs with a much smaller number of lithographically produced mesoscale wires (MWs). Unlike traditional demultiplexers, all proposed NW decoders are assembled stochastically. In a randomized-contact decoder (RCD) (Hogg et al., 2006), for example, field-effect transistors are randomly created at about half of the NW/MW junctions. In this paper, we tightly bound the number of MWs required to produce a correctly functioning RCD with high probability. We show that the number of MWs is logarithmic in the number of NWs, even when errors occur. We also analyze the overhead associated with controlling a stochastically assembled decoder. As we explain, lithographically-produced control circuitry must store information regarding which MWs control which NWs. This requires more area than the MWs themselves, but has received little attention elsewhere

We introduce radial encoding of nanowires (NWs), a new method of differentiating and controlling NWs by a small set of mesoscale wires for use in crossbar memories. We describe methods of controlling these NWs and give efficient manufacturing algorithms. These new encoding and decoding methods do not suffer from the misalignment characteristic of flow-aligned NWs. They achieve comparable effective pitch and resulting memory density with axially encoded NWs, while avoiding potential cases of address ambiguity and simplifying NW preparation. We also explore hybrid axial/radial encodings and show that they offer no net benefit over pure codes.

A key challenge facing nanotechnologies is learning to control uncertainty introduced by stochastic self-assembly. In this article, we explore architectural and manufacturing strategies to cope with this uncertainty when assembling nanoarrays, crossbars composed of two orthogonal sets of parallel nanowires (NWs) that are differentiated at their time of manufacture. NW deposition is a stochastic process and the NW encodings present in an array cannot be known in advance. We explore the reliable construction of memories from stochastically assembled arrays. This is accomplished by describing several families of NW encodings and developing strategies to map external binary addresses onto internal NW encodings using programmable circuitry. We explore a variety of different mapping strategies and develop probabilistic methods of analysis. This is the first article that makes clear the wide range of choices that are available.

We present a new parallel repartitioning algorithm for adaptive finite-element meshes that significantly reduces the amount of data that needs to move between processors in order to rebalance a workload after mesh adaptation (refinement or coarsening). These results derive their importance from the fact that the time to migrate data can be a large fraction of the total time far the parallel adaptive solution of partial differential equations.

Describes our experience using PARED, an object-oriented system for the adaptive solution of partial differential equations (PDEs) in a distributed computing environment. PARED handles selective mesh refinement and coarsening, mesh repartitioning for load balancing and interprocessor mesh migration. PARED is an object-oriented system that runs on distributed memory parallel computers such as the IBM SP and networks of workstations. In this paper, we report on the use of PARED to solve 2D and 3D PDEs. We show that our object-oriented technology provides great flexibility with a small overhead to support the highly desirable adaptive features of PARED.

Multi-grained parallel computers can be very effective on computationally intensive problems that have important serial and parallel components. We introduce the Mesh SuperHet, a model of this type consisting of the close coupling of a d-dimensional toroidal mesh of coarse-grained processors to a serial machine consisting of memory modules connected via a low-diameter network to a serial processor. We exhibit problems for which the Mesh SuperHet is superior to its serial or parallel components alone and develop tight performance bounds for sorting, the fast Fourier transform, and matrix multiplication. As multi-grained machines become more common, studies such as this will both reveal the fundamental limitations on such architectures and set the context for algorithm development.

Two-layer channel routers typically require a post-processing phase to reduce or eliminate column conflicts. Attempts have been made to parallelize this problem using local search heuristics that swap horizontal channel wire segments. The authors show that all such heuristics for this problem are P-hard and unlikely to be efficiently parallelizable.>

Trade-offs between space and time provide ~mportant information on the simultaneous use of these resources.They have been studied most successfully using the Grigoryev method, which leads to lower bounds on the space-time product for certain models of computation.In this paper, we generalize the model to which the Gngoryev method applies and derive space-time lower bounds for banded matnx multiphcatlon and inversion, and for the solution of a set of banded equations.We also investigate full matrix inversion and several other problems.The new computational model consists of algorithms on fimte-state machine with the proviso that input and output are done at times that are data independent.Space is measured by the logarithm of the number of states in the machine, and tame is measured by the number of cycles in which input and/or output is done.We show that standard algorithms for the multiplication ofp x p matrices of bandwith b, and for the inversion of such matrices when b = f~(p) are optimal to within multlphcative factors.Good algorithms are also presented for the soluUon of a set of banded equations and for banded matrix inversion.

The pebble game on directed acyclic graphs can be used to model the space-time tradeoff behavior of a straight-line algorithm (SLA). In this game, the maximum number of pebbles used at any one time corresponds to the number of temporary registers available and is called space. The number of moves made to reach the outputs of the graph, or the time, corresponds to the number of operations required by the SLA. In this paper, it is shown that there exist infinite families of constructible graphs on N nodes which possess an extreme time-space tradeoff. For a particular set of graphs, if space is restricted to fall in the range of Θ(log N) to Θ((@@@@N/log N)), then the pebbling time necessary is superpolynomial in N. This result is obtained by deriving a lower bound on time when extra space is restricted, and then diagonalizing over the amount of this space. An extension of this argument shows that the minimum space requirement for such constructible graph families can grow as any slowly increasing function of N.

A linear recursive procedure is one in which a procedural call can activate at most one other procedural call. When linear recursion cannot be replaced by iteration, it is usually implemented with a stack of size proportional to the depth of recursion. In this paper we analyze implementations of linear recursion which permit large reductions in storage space at the expense of a small increase in computation time. For example, if the depth of recursion is n, storage space can be reduced to √n at the cost of a constant factor increase in running time. The problem is treated by abstracting linear recursion into the pebbling of a simple graph and for this abstraction we exhibit the optimal space-time tradeoffs.

Synchronous combinational complexity, a measure of the size of logic circuits without races, is investigated in this paper. The first author has presented a method for obtaining an $O(n\log n)$ lower bound to synchronous combinational complexity and has shown that this bound applies to “almost all” Boolean functions in n variables. However, he could not constructively exhibit functions to which the lower bound applied (although Wolfgang Paul did produce an example). In this paper we weaken and extend the hypothesis of the lower bound so that a larger class of functions satisfies it and apply it to the determinant and marriage functions of $GF(2)$.

The performance of the fast Fourier transfmm algorithm is examined under limitations on computational space and time. It is shown that if the algorithm withninputs,nas a power of two, is implemented withStemporary locations whereS=o(n/ \log n), then the computation timeTgrows faster thann \log n. Furthermore,Tcan grow as fast asn^{2}ifS=S_{min} + O(1)whereS_{min}=l+\log_{2}n, the minimum necessary. These results are obtained by deriving tight bounds onTversusSandn.

Many problems, including matrix-vector multiplication and polynomial evaluation, involve the computation of linear forms. An algorithm is presented here which offers a substantial improvement on the conventional algorithm for this problem when the coefficient set is small. In particular, this implies that every polynomial of degree n with at most s distinct coefficients can be realized with $O(n/\log _s n)$ operations. It is demonstrated that the algorithm is sharp for some problems.

In this paper we address the mutual interference problems that arise as a result of many independent terminals simultaneously accessing a common channel. "Random code" bounds are used to show the existence of large signal sets for which any one signal can be reliably detected by matched filters despite the mutual interference. Two types of signal sets are considered: sets with a unique signature for every terminal and sets drawn from a small collection of distinct waveforms. The latter sets permit reductions in receiver complexity.

Measures of the computational work and computational delay required by ms chines to compute functions are given.Exchange inequalities are developed for random acces~ tape, and drum machines to show that product inequalities between storage and time, numbe of drum tracks and time, number of bits in an address and time, etc., must be satisfied to corn pute finite functions on bounded machines.

The computational work and the time required to decode with reliabilityEat code rateRon noisy channels are defined, and bounds on the size of these measures are developed. A number of ad hoc decoding procedures are ranked on the basis of the computational work they require.

In the past, criteria for predicting the performance of individual codes with sequential decoding have been intuitive. In this paper, simple tests are derived that allow easy determination of the performance on the BSC (binary symmetric channel) of a given binary convolutional code decoded with a modified version of the Fano algorithm. A "distance-guaranteed computational cutoff rate,"R_{dgcomp}, is defined in terms of the BSC crossover probability and the "uniform minimum distance" of the code. The latter is a measure of the minimum distance between codewords of all lengths up to and including the constraint length of the code. A bound is derived on the average number of decoding computations and is shown to be small and insensitive to constraint length if the code rate,R, satisfies the testR < R_{dgcomp}. Also, the probability of a decoding error is overbounded and the bound decreases exponentially with constraint length with exponent(R_{dgcomp} - R). Consequently, the probability of error is small if(R_{dgcom} - R)is large. The existence of binary convolutional codes with a uniform minimum distance which meets the Gilbert bound is demonstrated. This result is combined with the conditionR < R_{dgcomp}to show the existence of codes of rate less than a rateR_{D}for which the average number of decoding computations is small. The rateR_{D}is approximately one half of the true computational cutoff rateR_{comp}on the BSC with crossover probability of10^{-4}.

Several classes of decoding rules are considered here including block decoding rules, tree decoding rules, and bounded-distance and minimum-distance decoding rules for binary parity-check codes. Under the assumption that these rules are implemented with combinational circuits and sequential machines constructed with AND gates, OR gates, INVERTERS, and binary memory cells, bounds are derived on their complexity. Complexity is measured by the number of logic elements and memory cells, and it is shown that minimum-distance and other decoders for parity-check codes can be realized with complexity proportional to the square of block length, although at the possible expense of a large decoding time. We examine tradeoffs between probability of error and complexity for the several classes of rules.

Previous studies of sequential decoding algorithms have shown that the computation time required per decoded digit is small, on the average, when the source rate is less than a rateR_{comp}. In this paper, we consider the probability distribution of the computation time per decoded digit for the Fano algorithm on the binary symmetric channel. We show by underbounding this distribution that it behaves asL^{-\alpha}, \alpha > 0, in the distribution parameterL, that is, it is of the Pareto type. We deduce from this fact that the probability of overflowing the buffer required to store data during periods of high computation is relatively insensitive to the buffer storage capacity and to the maximum speed of the accompanying logic unit. It is shown that this lack of sensitivity exists because the computation per decoded digit is large during intervals of high channel noise and grows exponentially with the length of such an interval. The overflow probability, however, is a strong function of the source rate and is more than squared by a halving of this rate.