By using self-assembling fabrication techniques at the cellular, molecular, or atomic scale, it is nowadays possible to create functional assemblies in a mainly bottom-up way that involve massive numbers of interconnected components. However, such assemblies are often highly irregular, unreliable, and heterogeneous. A grand challenge for future and emerging electronics is thus to reliably and efficiently compute and communicate in such systems. The goal of this paper is to illustrate why non-traditional network-on-chip paradigms are promising for massive scale systems and what the limits are. We have previously shown that certain irregular 3D assemblies and interconnects have major advantages over regular 2D and 3D mesh fabrics in terms of latency, throughput, scalability, and the robustness against simple link failures. We present these results from a complex network perspective and look into the scaling properties of different interconnect topologies and routing algorithms in an abstract framework. We argue that only small-world topologies will scale up to massive scale systems. The long term goal in using irregular, fabrication-friendly, and non-traditional interconnects is to eventually be able to cheaply and easily assemble massive scale computing devices that are able to solve specific large- scale problems competitively with traditional top-down fabricated silicon technology.

Scientific application kernels mapped to reconfigurable hardware have been reported to have 10times to 100times speedup over equivalent software. These promising results suggest that reconfigurable logic might offer significant speedup on applications in science and engineering. To accurately assess the benefit of hardware acceleration on scientific applications, however, it is necessary to consider the entire application including software components as well as the accelerated kernels. Aspects to be considered include alternative methods of hardware/software partitioning, communications costs, and opportunities for concurrent computation between software and hardware. Analysis of these factors is beyond the scope of current automatic parallelizing compilers. In this paper, a case study is presented in which a simulation of metropolitan road traffic networks is mapped onto a reconfigurable supercomputer, the Cray XD1. Five different methods are presented for mapping the application onto the combined hardware/software system. An approach for approximating the performance of each method is derived through analytic equations. Our results, both analytically and empirically, show that key predictors of performance (which are often not considered in reported speedup of kernel operations) are not necessarily maximum parallelism, but must account for the fraction of the problem that runs on the reconfigurable logic and the amount data flow between software and hardware.

Scalable and reliable routing is a critical issue in sensor network deployment. A number of approaches have been proposed for sensor network routing, but sensor field implementation tends to be lacking in the literature. In our study, the problems of scalability and reliability in sensor network routing are addressed through a simple but powerful scheme implemented on Mica2 motes running TinyOS along with other, more widely-used routing protocols. Motes are tested in an outdoor sensor field, and detailed experiments are carried out for performance analysis. This paper presents the implementation details and the results obtained from head-to-head comparison of routing protocols. The proposed protocol delivers 93% of packets injected at a rate of one packet per second in networks with end to end hop distances of over 10 hops-a result which significantly improves upon results from the standard TinyOS routing implementation of MINTRoute. The promising results can be explained by the key protocol properties of reliability (via multi-path redundancy), scalability (with efficiently contained flooding), and flexibility (source-tunable per-packet priority) which are achieved without adding protocol complexity or resource consumption. These strengths enable the protocol to outperform even sophisticated link estimation based protocols especially in adverse outdoor sensor field environments.

This work demonstrates that road traffic simulation of entire metropolitan areas is possible with reconfigurable supercomputing that combines 64-bit microprocessors and FPGAs in a high bandwidth, low latency interconnect. Previously, traffic simulation on FPGAs was limited to very-short road segments or required a very large number of FPGAs. Our data streaming approach overcomes scaling issues associated with direct implementations and still allows for high-level parallelism by dividing the data sets between hardware and software across the reconfigurable supercomputer. Using one FPGA on the Cray XD1 supercomputer, we are able to achieve a 34.4/spl times/ speed up over the AMD microprocessor. System integration issues must be optimized to exploit this speedup in the overall simulation.

Often reconfigurable systems are reported to have 10× to 100× speedup over that of a software system. However, the reconfigurable hardware must usually be combined with software to form an entire system. This system integration presents a hardware/software co-design problem with many system engineering issues. Here, we present traffic acceleration on the Cray XD1 supercomputer and describe the costs involved in different hardware/software trade-offs.

Techniques for computing soft information in the presence of unknown intersymbol interference are presented, with a particular focus on iterative detection of serially concatenated continuous phase modulation. The techniques are centered around the recursive least-squares algorithm, thus enabling unsupervised detection. In particular, we employ bidirectional estimation.

An antenna array is proposed as a means of achieving a space-diversity effect that partly overcomes the severity of continuous-time Rayleigh fading channels. The investigated channel is assumed to be frequency-nonselective with correlated diversity links, where the correlation is related to the array geometry and the spatial and Doppler dispersions. Further, the error performance is improved by bit interleaving and channel coding, where the encoders/channel is viewed as a serially concatenated system: a convolutional code constitutes the outer code, whereas a differential encoder and the fading channel (having truncated memory) form a joint inner code. In order to obtain a practical detector structure it is desirable to perform iterative decoding by applying some a posteriori probability (APP) algorithms. For this purpose, we propose a novel generalization of the well-known Bahl-Cocke-Jelinek-Raviv (1974) algorithm that calculates the APPs over channels having memory. Numerical results indicate that iterative decoding becomes more powerful when the exploited channel memory depth is extended. Also, the error performance is significantly improved by introducing multiple antennas. The interleaver gain is, however, seen to be quite moderate, in contrast to additive white Gaussian noise channels.

A multiple-antenna receiver is proposed for achieving a diversity effect that partly overcomes the severity of continuous-time frequency-flat Rayleigh fading channels, and fast fading channels in particular. The error performance is also improved by bit interleaving and channel coding, where the encoders/channel is viewed as a serially concatenated system: a convolutional code constitutes the outer code, whereas a differential encoder and the fading channel (having truncated memory) form a joint inner code. In order to obtain a feasible detector structure it is desirable to perform iterative decoding by applying some a posteriori probability (APP) algorithms. For this purpose, we derive a novel generalization of the well known BCJR (due to Bahl, Cocke, Jelinek, and Raviv 1974) algorithm that calculates the APPs for fading channels-or for channels having memory. Numerical results indicate that iterative decoding becomes more powerful when the exploited channel memory depth is extended, but the chief performance gain is achieved by introducing multiple antennas.

Optimum (in the sense of minimum-error probability) single-symbol diversity detection for fading, noisy channels is too complex for practical implementation. A simplified, near-optimum array receiver is proposed, which is based on the statistics (i.e., the covariance-function matrix) of the fading channel. This detector is then analyzed by calculating the exact error probability. When there is a spread of the direction of arrival of the incident radio waves, the proposed detector significantly gains over an adaptive antenna array (which forms a weighted sum of the received antenna signals). Also, for this adaptive array, a fundamental difference between maximum-likelihood weights and least-mean-square weights is observed.