Pre-trained gaze models learn to identify useful patterns commonly found across users, but subtle user-specific variations (i.e., eyelid shape or facial structure) can degrade model performance. Test-time personalization (TTP) adapts pre-trained models to these user-specific domain shifts using only a few unlabeled samples. Efficient fine-tuning is critical in performing this domain adaptation: data and computation resources can be limited-especially for on-device customization. While popular parameter-efficient fine-tuning (PEFT) methods address adaptation costs by updating only a small set of weights, they may not be taking full advantage of structures encoded in pre-trained filters. To more effectively leverage existing structures learned during pre-training, we reframe personalization as a process to reweight existing features rather than learning entirely new ones. We present Attentive Low-Rank Filter Adaptation (Alfa) to adapt gaze models by reweighting semantic patterns in pre-trained filters. With Alfa, singular value decomposition (SVD) extracts dominant spatial components that capture eye and facial characteristics across users. Via an attention mechanism, we need only a few unlabeled samples to adjust and reweight pre-trained structures, selectively amplifying those relevant to a target user. Alfa achieves the lowest average gaze errors across four cross-dataset gaze benchmarks, outperforming existing TTP methods and low-rank adaptation (LoRA)-based variants. We also show that Alfa's attentive low-rank methods can be applied to applications beyond vision, such as diffusion-based language models.

Large language models (LLMs) have recently emerged as a promising approach for automating Verilog code generation; however, existing methods primarily emphasize syntactic correctness and often rely on commercial models or external verification tools, which introduces concerns regarding cost, data privacy, and limited guarantees of functional correctness. This work proposes a unified multi-agent framework for reasoning-oriented training data generation with integrated testbench-driven verification, enabling locally fine-tuned LLMs, SiliconMind-V1, to iteratively generate, test, and debug Register-Transfer Level (RTL) designs through test-time scaling. Experimental results on representative benchmarks (VerilogEval-v2, RTLLM-v2, and CVDP) demonstrate that the proposed approach outperforms the state-of-the-art QiMeng-CodeV-R1 in functional correctness while using fewer training resources.

Real-time personalized gaze estimation on AR/VR devices requires both accuracy and efficiency, especially when adapting to individual users with limited personal data. This task is challenging due to low-latency requirements, the presence of dataset biases from dominant gaze directions, and risk of catastrophic forgetting during adaptation. We present Distilled and Fine-Tuned (DFT) Gaze, a lightweight model for personalized gaze estimation. Distilled from a larger teacher model, DFT Gaze reduces model size while retaining essential visual features through knowledge distillation, without relying on gaze-specific supervision. During fine-tuning, it integrates gaze-specific supervision with Adapters, reaching 281K parameters for efficient adaptation and online updates on edge devices. To mitigate dataset biases and reduce catastrophic forgetting, we introduce a clustering-based sampling that balances gaze distribution for better generalization and improves adaptation to individual gaze patterns, even with only 5 personal images. DFT Gaze outperforms state-of-the-art methods on the MPIIFaceGaze dataset for personalized gaze estimation. Despite having the smallest model size at 281K parameters, it maintains low gaze errors across other datasets, including MPIIGaze, OpenEDS2020, and AEA. At 10× smaller than its teacher model, DFT Gaze achieves fast inference, a low parameter count, and effective adaptation, making it well-suited for real-time applications in resource-constrained environments.

We present a novel rank-sliced GAther-Scatter Activation (GASA) algorithm to minimize I/O costs in computing neural network layer activations (XW) between a data matrix X, and a singular value decomposition (SVD) of a weight matrix W = UΣVT. We maintain high accuracy with ResNet-18 [1] on the CIFAR-10 [2] dataset and Deberta-V3-base [3] on the IMDB dataset [4] at high sparsities (i.e., up to 85% sparsity for U and V ) by using rank pruning for W and UV pruning for each rank slice. Furthermore, with rank-sliced computation, we can perform parameter-efficient fine-tuning on the resulting sparse networks while preserving sparsity to retain the sparsity-induced computational efficiency for inference. That is, our rank-sliced weight update preserves the original sparsity structure of each W. Our sparsity-preserving fine-tuning maintains model accuracy under adapter ranks as low as 8, compared to the rank of 150 of the pre-trained pruned model.

We introduce FrameVoting, a voting-based method for real-time, gaze-driven object identification. It is a training-free method that incurs small computation and low processing latency, making the method ideal for wearable devices. In FrameVoting, the Point of Gaze (PoG) in each frame is used to define a potential region of interest. Regions across multiple frames are compared using the Sum of Absolute Differences (SAD) as a similarity measure. Each frame votes for the region from each of the other frames that is most similar to the region in the current frame, and only the region receiving the most votes is considered as the user’s region of interest and sent to a classifier for inference. FrameVoting thus eliminates the need for frame-by-frame bounding box retrieval and object detection required by traditional methods, thereby reducing computation overhead and latency. The method is robust, as it eliminates the need for threshold-tuning to determine whether gaze estimations are focused on a specific object. Further, the method is efficient and fast, as inference is only performed on the most-voted region, and the SAD computation is highly parallelizable. Our experiments on the AEA Dataset demonstrate that FrameVoting reduces the frequency of inferences by 95.6% compared to frame-by-frame object detection, while still accurately identifying the user’s objects of interest in real-time at 30 fps on a Raspberry Pi 5.

We introduce a novel approach to reduce the number of times required for reprogramming memristors on bit-sliced compute-in-memory crossbars for deep neural networks (DNNs). Our idea addresses the limited non-volatile memory endurance, which restricts the number of times they can be reprogrammed.To reduce reprogramming demands, we employ two techniques: (1) we organize weights into sorted sections to schedule reprogramming of similar crossbars, maximizing memristor state reuse, and (2) we reprogram only a fraction of randomly selected memristors in low-order columns, leveraging their bit-level distribution and recognizing their relatively small impact on model accuracy.We evaluate our approach for state-of-the-art models on the ImageNet-1K dataset. We demonstrate a substantial reduction in crossbar reprogramming count by 3.7x for ResNet-50 and 21x for ViT-Base, while maintaining model accuracy within a 1% margin.

We introduce sorted weight sectioning (SWS): a weight allocation algorithm that places sorted deep neural network (DNN) weight sections on bit-sliced compute-in-memory (CIM) crossbars to reduce analog-to-digital converter (ADC) energy consumption. Data conversions are the most energy-intensive process in crossbar operation. SWS effectively reduces the ADC cost by leveraging (1) small weights and (2) zero weights (weight sparsity) present in DNNs.DNN weights follow bell-shaped distributions, with most weights near zero. Under SWS, we only need low-order crossbar columns for sections with low-magnitude weights. This reduces the quantity and resolution of ADCs required without significantly degrading DNN accuracy.Unstructured sparsification further sharpens the weight distribution with small accuracy loss. However, it presents challenges in hardware tracking of zeros: we cannot switch zero rows to other layer weights in unsorted crossbars without index matching. SWS uses offline remapping of zeros into earlier sections to exploit full sparsity potential and maximize energy efficiency.SWS reduces ADC energy use by 89.5% on unstructured sparse BERT models. Overall, this paper introduces a novel algorithm to allow energy-efficient CIM crossbars for unstructured sparse DNN workloads.

We present Alternating Greedy Scheduling (AGS), an algorithm for avoiding overflow, specifically transient overflow, during low-bitwidth accumulation of dot products in neural network computations. In conventional quantized (e.g., 8-bit) dot products, partial results are accumulated into wide (e.g., 32-bit) accumulators to avoid overflows when accumulating intermediate partial sums. However, such wide accumulators increase memory bandwidth usage and reduce energy efficiency. We show that iterative N:M pruning in floating point followed by quantization to 8 (or fewer) bits, and accumulation of partial products in an optimal order (via AGS) allows for accurate, compressed models with a large number of partial products that do not require wide accumulators. We design, analyze, and implement the AGS algorithm to eliminate accumulation overflows at inference time for several neural networks. Our method offers a 2.7x reduction in accumulator bitwidth while achieving model accuracy on par with floating-point baselines for multiple image classification tasks.

We propose StitchNet, a novel neural network cre-ation paradigm that stitches together fragments (one or more consecutive network layers) from multiple pre-trained neural networks. StitchNet allows the creation of high-performing neural networks without the large compute and data requirements needed under traditional model creation processes via backprop-agation training. We leverage Centered Kernel Alignment (CKA) as a compatibility measure to efficiently guide the selection of these fragments in composing a network for a given task tailored to specific accuracy needs and computing resource constraints. We then show that these fragments can be stitched together to create neural networks with accuracy comparable to that of traditionally trained networks at a fraction of computing resource and data requirements. Finally, we explore a novel on-the-fly personalized model creation and inference application enabled by this new paradigm. The code is available at https://github.com/steerapi/stitchnet.

Various approaches have been proposed for out-of-distribution (OOD) detection by augmenting models, input examples, training sets, and optimization objectives. Deviating from existing work, we have a simple hypothesis that standard off-the-shelf models may already contain sufficient information about the training set distribution which can be leveraged for reliable OOD detection. Our empirical study on validating this hypothesis, which measures the model activation's mean for OOD and in-distribution (ID) minibatches, surprisingly finds that activation means of OOD mini-batches consistently deviate more from those of the training data. In addition, training data's activation means can be computed offline efficiently or retrieved from batch normalization layers as a ‘free lunch’. Based upon this observation, we propose a novel metric called Neural Mean Discrepancy (NMD), which compares neural means of the input examples and training data. Leveraging the simplicity of NMD, we propose an efficient OOD detector that computes neural means by a standard forward pass followed by a lightweight classifier. Extensive experiments show that NMD outperforms state-of-the-art OOD approaches across multiple datasets and model architectures in terms of both detection accuracy and computational cost.

We design deep neural networks (DNNs) and corresponding networks' splittings to distribute DNNs' workload to camera sensors and a centralized aggregator on head mounted devices to meet system performance targets in inference accuracy and latency under the given hardware resource constraints. To achieve an optimal balance among computation, communication, and performance, a split-aware neural architecture search framework, SplitNets, is introduced to conduct model designing, splitting, and communication reduction simultaneously. We further extend the framework to multi-view systems for learning to fuse inputs from multiple camera sensors with optimal performance and systemic efficiency. We validate SplitNets for single-view system on ImageNet as well as multi-view system on 3D classification, and show that the SplitNets framework achieves state-of-the-art (SOTA) performance and system latency compared with existing approaches.

Block Floating Point (BFP) can efficiently support quantization for Deep Neural Network (DNN) training by providing a wide dynamic range via a shared exponent across a group of values. In this paper, we propose a Fast First, Accurate Second Training (FAST) system for DNNs, where the weights, activations, and gradients are represented in BFP. FAST supports matrix multiplication with variable precision BFP input operands, enabling incremental increases in DNN precision throughout training. By increasing the BFP precision across both training iterations and DNN layers, FAST can greatly shorten the training time while reducing overall hardware resource usage. Our FAST Multipler-Accumulator (fMAC) supports dot product computations under multiple BFP precisions. We validate our FAST system on multiple DNNs with different datasets, demonstrating a 2-6× speedup in training on a single-chip platform over prior work based on mixed-precision or block floating point number systems while achieving similar performance in validation accuracy.

In this work, we propose the first bit-level sparsity-aware SAR ADC with direct hybrid encoding for signed expressions (HESE) for AIoT applications. ADCs are typically a bottleneck in reducing the energy consumption of analog neural networks (ANNs). For a pre-trained Convolutional Neural Network (CNN) inference, a HESE SAR for an ANN can reduce the number of non-zero signed digit terms to be output, and thus enables a reduction in energy along with the term quantization (TQ). The proposed SAR ADC directly produces the HESE signed-digit representation (SDR) using two thresholds per cycle for 2-bit look-ahead (LA). A prototype in 65nm shows that the HESE SAR provides sparsity encoding with a Walden FoM of 15.2fJ/conv.-step at 45MS/s. The core area is 0.072mm2.

Low-resolution uniform quantization (e.g., 4-bit bitwidth) for both Deep Neural Network (DNN) weights and data has emerged as an important technique for efficient inference. Departing from conventional quantization, we describe a novel training approach to support inference at multiple resolutions by reusing a single set of quantization terms (the same set of nonzero bits in values). The proposed approach streamlines the training and supports dynamic selection of resolution levels during inference. We evaluate the method on a diverse range of applications including multiple CNNs on ImageNet, an LSTM on Wikitext-2, and YOLO-v5 on COCO. We show that models resulting from our multi-resolution training can support up to 10 resolutions with only a moderate performance reduction (e.g., ≤ 1%) compared to training them individually. Lastly, using an FPGA, we compare our multi-resolution multiplier-accumulator (mMAC) against other conventional MAC designs and evaluate the inference performance. We show that the mMAC design broadens the choices in trading off cost, efficiency, and latency across a range of computational budgets.

Deep learning techniques, such as deep neural networks (DNNs), have been used with success in many viral classification problems associated with metagenomics, diagnosis of viral infections, pharmacogenomics, phylogenetic analysis, and others. However, deep learning algorithms require a large number of math operations, and these computations themselves can be a bottleneck for processing the vast number of virus sequences in a short time. Currently, most works in this area use basic DNNs in viral classification, and they are not optimized for computational efficiency. This paper proposes a novel training strategy that simultaneously minimizes both pruning and quantization losses in training compressed models for reducing deep learning computational complexity. In training a compressed convolutional neural network (CNN), the scheme uses weight quantization followed by pruning in each training iteration rather than the pruning followed by quantization. The proposed training strategy scheme has been applied to train compressed models for efficient viral classification of 1600 sequences of four types of viruses associated with three families and one realm. A substantial reduction of DNN weights (77%) and operations (58%) is demonstrated, while maintaining high classification accuracy. These results show that the proposed new training regime of weight quantization followed weight pruning for each training iteration is superior to conventional approaches with weight pruning epochs followed by weight quantization epochs.

The proposed saturation RRAM for in-memory computing of a pre-trained Convolutional Neural Network (CNN) inference imposes a limit on the maximum analog value output from each bitline in order to reduce analog-to-digital (A/D) conversion costs. The proposed scheme uses term quantization (TQ) to enable flexible bit annihilation at any position for a value in the context of a group of weights values in RRAM. This enables a drastic reduction in the required ADC resolution while still maintaining CNN model accuracy. Specifically, we show that the A/D conversion errors after TQ have a minimum impact on the classification accuracy of the inference task. For instance, for a 64×64 RRAM, reducing the ADC resolution from 6 bits to 4 bits enables a 1.58× reduction in the total system power, without a significant impact to classification accuracy.

We offer a novel approach to matrix-matrix multiplication computation on computing platforms with memory hierarchies. Constant-bandwidth (CB) blocks improve computation throughput for architectures limited by external memory bandwidth. Configuring the shape and size of CB blocks operating from within any memory hierarchy level (e.g., internal SRAM), we achieve high throughput while holding external bandwidth (e.g., with DRAM) constant. We explain how, surprisingly, CB blocks can maintain constant external bandwidth as computation throughput increases. Analogous to partitioning a cake into pieces, we dub our CB-partitioned system CAKE.

We present a novel technique, called Term Quantization (TQ), for furthering quantization at run time for improved computational efficiency of deep neural networks (DNNs) already quantized with conventional quantization methods. TQ operates on power-of-two terms in expressions of values. In computing a dot-product computation, TQ dynamically selects a fixed number of largest terms to use from values of the two vectors. By exploiting weight and data distributions typically present in DNNs, TQ has a minimal impact on DNN model performance (e.g., accuracy or perplexity). We use TQ to facilitate tightly synchronized processor arrays, such as systolic arrays, for efficient parallel processing. We evaluate TQ on an MLP for MNIST, multiple CNNs for ImageNet and an LSTM for Wikitext-2. We demonstrate significant reductions in inference computation costs (between 3-10×) compared to conventional uniform quantization for the same level of model performance.

We describe a new approach that improves the training of generative adversarial nets (GANs) for synthesizing diverse images from a text input. Our approach is based on the conditional version of GANs and expands on previous work leveraging an auxiliary task in the discriminator. Our generated images are not limited to certain classes and do not suffer from mode collapse while semantically matching the text input. A key to our training methods is how to form positive and negative training examples with respect to the class label of a given image. Instead of selecting random training examples, we perform negative sampling based on the semantic distance from a positive example in the class. We evaluate our approach using the Oxford-102 flower dataset, adopting the inception score and multi-scale structural similarity index (MS-SSIM) metrics to assess discriminability and diversity of the generated images. The empirical results indicate greater diversity in the generated images, especially when we gradually select more negative training examples closer to a positive example in the semantic space.

We present the Maestro memory-on-logic 3D-IC architecture for coordinated parallel use of a plurality of systolic arrays (SAs) in performing deep neural network (DNN) inference. Maestro reduces under-utilization common for a single large SA by allowing parallel use of many smaller SAs on DNN weight matrices of varying shapes and sizes. In order to buffer immediate results in memory blocks (MBs) and provide coordinated high-bandwidth communication between SAs and MBs in transferring weights and results Maestro employs three innovations. (1) An SA on the logic die can access its corresponding MB on the memory die in short distance using 3D-IC interconnects, (2) through an efficient switch based on H-trees, an SA can access any MB with low latency, and (3) the switch can combine partial results from SAs in an elementwise fashion before writing back to a destination MB. We describe the Maestro architecture, including a circuit and layout design, detail scheduling of the switch, analyze system performance for real-time inference applications using input with batch size equal to one, and showcase applications for deep learning inference, with ShiftNet for computer vision and recent Transformer models for natural language processing. For the same total number of systolic cells, Maestro, with multiple smaller SAs, leads to 16x and 12x latency improvements over a single large SA on ShiftNet and Transformer, respectively. Compared to a floating-point GPU implementation of ShiftNet and Transform, a baseline Maestro system with 4,096 SAs (each with 8x8 systolic cells) provides significant latency improvements of 30x and 47x, respectively.

This paper describes a novel approach of packing sparse convolutional neural networks into a denser format for efficient implementations using systolic arrays. By combining multiple sparse columns of a convolutional filter matrix into a single dense column stored in the systolic array, the utilization efficiency of the systolic array can be substantially increased (e.g., 8x) due to the increased density of nonzero weights in the resulting packed filter matrix. In combining columns, for each row, all filter weights but the one with the largest magnitude are pruned. The remaining weights are retrained to preserve high accuracy. We study the effectiveness of this joint optimization for both high utilization efficiency and classification accuracy with ASIC and FPGA designs based on efficient bit-serial implementations of multiplier-accumulators. We demonstrate that in mitigating data privacy concerns the retraining can be accomplished with only fractions of the original dataset (e.g., 10% for CIFAR-10). We present analysis and empirical evidence on the superior performance of our column combining approach against prior arts under metrics such as energy efficiency (3x) and inference latency (12x).

We present a full-stack optimization framework for accelerating inference of CNNs (Convolutional Neural Networks) and validate the approach with a field-programmable gate array (FPGA) implementation. By jointly optimizing CNN models, computing architectures, and hardware implementations, our full-stack approach achieves unprecedented performance in the trade-off space characterized by inference latency, energy efficiency, hardware utilization, and inference accuracy. An FPGA implementation is used as the validation vehicle for our design, achieving a 2.28ms inference latency for the ImageNet benchmark. Our implementation shines in that it has 9x higher energy efficiency compared to other implementations while achieving comparable latency. A highlight of our approach which contributes to the achieved high energy efficiency is an efficient Selector-Accumulator (SAC) architecture for implementing CNNs with powers-of-two weights. Compared to an FPGA implementation for a traditional 8-bit MAC, SAC substantially reduces required hardware resources (4.85x fewer lookup tables) and power consumption (2.48x).

We present a building block architecture for systolic array 3D-IC implementations of convolutional neural network (CNN) inference. The building block can be part of a library offered by a chip design service provider to support efficient CNN implementations. We describe how the building block can form systolic arrays for implementing low-latency, energy-efficient CNN inference for models of any size, while incorporating advanced packaging features such as “logic-on-logic” 3D-IC (micro-bump/TSV, monolithic 3D or other 3D technology). We present delay and power analysis for 2D and 3D implementations, and argue that as systolic arrays scale in size, 3D implementations based on, e.g., micro-bump/TSV, lead to significant performance improvements over 2D implementations.

We introduce localization convolutional neural networks (CNNs), a data-driven time series-based angle of arrival (AOA) localization scheme capable of coping with noise and errors in AOA estimates measured at receiver nodes. Our localization CNNs enhance their robustness by using a time series of AOA measurements rather than a single-time instance measurement to localize mobile nodes. We analyze real-world noise models, and use them to generate synthetic training data that increase the CNN's tolerance to noise. This synthetic data generation method replaces the need for expensive data collection campaigns to capture noise conditions in the field. The proposed scheme is both simple to use and also lightweight, as the mobile node to be localized solely transmits a beacon signal and requires no further processing capabilities. Our scheme is novel in its use of: (1) CNNs operating on space-time AOA images composed of AOA data from multiple receiver nodes over time, and (2) synthetically-generated perturbed training examples obtained via modeling triangulation patterns from noisy AOA measurements. We demonstrate that a relatively small CNN can achieve state-of-the-art localization accuracy that meets the 5G standard requirements even under high degrees of AOA noise. We motivate the use of our proposed localization CNNs with a tracking application for mobile nodes, and argue that our solution is advantageous due to its high localization accuracy and computational efficiency.

In recent years, convolutional neural networks (CNNs) have been successfully applied for automatic target recognition (ATR) in synthetic aperture radar (SAR) data. However, it is challenging to train a CNN with high classification accuracy when labeled data is limited. This is often the case with SAR ATR in practice, because collecting large amounts of labeled SAR data is both difficult and expensive. Using a simulator to generate SAR images offers a possible solution. Unfortunately, CNNs trained on simulated data may not be directly transferable to real data. In this paper, we introduce a method to refine simulated SAR data based on deep residual networks. We learn a refinement function from simulated to real SAR data through a residual learning framework, and use the function to refine simulated images. Using the MSTAR dataset, we demonstrate that a CNN-based SAR ATR system trained on simulated data under residual network refinements can yield much higher classification accuracy as compared to a system trained on simulated images, and so can training on real data augmented with these simulated data under refinements compared to training with real data alone.

We introduce adaptive tiling, a method of partitioning layers in a sparse convolutional neural network (CNN) into blocks of filters and channels, called tiles, each implementable with a fixed-size systolic array. By allowing a tile to adapt its size so that it can cover a large sparse area, we minimize the total number of tiles, or equivalently, the number of systolic array calls required to perform CNN inference. The proposed scheme resolves a challenge of applying systolic array architectures, traditionally designed for dense matrices, to sparse CNNs. To validate the approach, we construct a highly sparse Lasso-Mobile network by pruning MobileNet trained with an l1 regularization penalty, and demonstrate that adaptive tiling can lead to a 2- 3x reduction in systolic array calls, on Lasso-Mobile, for several benchmark datasets.

We present a clustering-based language model using word embeddings for text readability prediction. Presumably, an Euclidean semantic space hypothesis holds true for word embeddings whose training is done by observing word co-occurrences. We argue that clustering with word embeddings in the metric space should yield feature representations in a higher semantic space appropriate for text regression. Also, by representing features in terms of histograms, our approach can naturally address documents of varying lengths. An empirical evaluation using the Common Core Standards corpus reveals that the features formed on our clustering-based language model significantly improve the previously known results for the same corpus in readability prediction. We also evaluate the task of sentence matching based on semantic relatedness using the Wiki-SimpleWiki corpus and find that our features lead to superior matching performance.

The use of high frequency millimeter wave (mmWave) bands at 28 GHz or higher will be a defining characteristic of next- generation wireless networks, such as 5G and 802.11ad networks. However, communicating over these high frequencies bands often requires directional antennas on base stations to dynamically align their beams with mobile nodes. To quickly align antennas, we propose a data-driven deep neural network (DNN) approach to localize mobile nodes using lower frequency spectrum. Our methods require fewer than 30 real-world sample locations to learn a model that can localize a mobile node to the required 5G indoor sub-meter accuracy. We demonstrate with real-world data in indoor and outdoor experiments that this performance is achievable, even in multipath-rich environments. Further, we show via simulation that the proposed DNN approach is robust to noise and collinearity between antenna arrays. Our primary contributions are: (1) a novel structure for a deep neural network that reflects the impact base station location has on node localization, (2) a quantized loss function for neural network training that improves localization accuracy and reduces the amount of training data needed, and (3) a procedure for using synthetic data to reduce the required number of real-world measurements needed for training the data-driven localization model. Our real-world experiments show that the use of synthetic data can improve localization accuracy by over 3x.

We present HF-ICA, a second-order “Hessian-free” algorithm for Infomax-ICA. Our approach achieves asymptotically quadratic convergence while retaining the memory footprint of first-order methods. Without any hyperparameter tuning, we show better convergence properties than both other approximate Newton-type methods and finely-tuned stochastic Natural Gradient Descent on EEG and fMRI data. A portable, multi-threaded and vectorized C++ implementation is made publicly available along with MATLAB and Python interfaces.

Compressive sensing, which enables signal recovery from fewer samples than traditional sampling theory dictates, assumes that the sampling process is linear. However, this linearity assumption may not hold in the analog domain without significant trade-offs, such as power amplifiers sacrificing substantial power efficiency in exchange for producing linear outputs. Since compressive sensing is most impactful when implemented in the analog domain, it is of interest to integrate the nonlinearity in compressive measurements into the signal recovery process such that nonlinear effects can be mitigated. As such, in this paper, we describe a nonlinear compressive sensing formulation and associated signal recovery algorithms, providing both compression and improved efficiency of a power amplifier simultaneously with one procedure. We present evaluations of the proposed framework using both measurements from real power amplifiers and simulations.

We propose distributed deep neural networks (DDNNs) over distributed computing hierarchies, consisting of the cloud, the edge (fog) and end devices. While being able to accommodate inference of a deep neural network (DNN) in the cloud, a DDNN also allows fast and localized inference using shallow portions of the neural network at the edge and end devices. When supported by a scalable distributed computing hierarchy, a DDNN can scale up in neural network size and scale out in geographical span. Due to its distributed nature, DDNNs enhance sensor fusion, system fault tolerance and data privacy for DNN applications. In implementing a DDNN, we map sections of a DNN onto a distributed computing hierarchy. By jointly training these sections, we minimize communication and resource usage for devices and maximize usefulness of extracted features which are utilized in the cloud. The resulting system has built-in support for automatic sensor fusion and fault tolerance. As a proof of concept, we show a DDNN can exploit geographical diversity of sensors to improve object recognition accuracy and reduce communication cost. In our experiment, compared with the traditional method of offloading raw sensor data to be processed in the cloud, DDNN locally processes most sensor data on end devices while achieving high accuracy and is able to reduce the communication cost by a factor of over 20x.

We propose the use of incomplete dot products (IDP) to dynamically adjust the number of input channels used in each layer of a convolutional neural network during feedforward inference. IDP adds monotonically non-increasing coefficients, referred to as a “profile”, to the channels during training. The profile orders the contribution of each channel in non-increasing order. At inference time, the number of channels used can be dynamically adjusted to trade off accuracy for lowered power consumption and reduced latency by selecting only a beginning subset of channels. This approach allows for a single network to dynamically scale over a computation range, as opposed to training and deploying multiple networks to support different levels of computation scaling. Additionally, we extend the notion to multiple profiles, each optimized for some specific range of computation scaling. We present experiments on the computation and accuracy trade-offs of IDP for popular image classification models and datasets. We demonstrate that, for MNIST and CIFAR-10, IDP reduces computation significantly, e.g., by 75%, without significantly compromising accuracy. We argue that IDP provides a convenient and effective means for devices to lower computation costs dynamically to reflect the current computation budget of the system. For example, VGG-16 with 50% IDP (using only the first 50% of channels) achieves 70% in accuracy on the CIFAR-10 dataset compared to the standard network which achieves only 35% accuracy when using the reduced channel set.

We propose a novel block address allocation method, called the nested buddy system, which can make use of wasted areas in the classical buddy system due to internal fragmentation. While achieving high utilization of address space, our new scheme supports efficient address matching for routers in packet forwarding and for network middleboxes in packet filtering. Specifically, the scheme uses just one prefix rule for each allocated address block in a packet routing/filtering table. We show by analysis and simulation that the increased address utilization can lead to significant reduction in the probability of a denial-of-service under bursty address allocation requests. In contrast, the classical buddy system requires the aggregation of many requests over time to smooth out demand, resulting in service delays undesirable to end users. Our solution is applicable to ISPs in serving mobile users carrying many network connected IoT devices and IasS providers in the cloud in serving tenants with dynamically varying demands for network addresses.

We propose a novel RF signal classification method based on sparse coding, an unsupervised learning method popular in computer vision. In particular, we employ a convolutional sparse coder that can extract high-level features of an unknown received signal by maximal similarity matching against an over-complete dictionary of filter patterns. Such dictionary can be either generated or learned in an unsupervised fashion from measured signal examples conveying no ground-truth labels. The computed sparse code is then applied to train SVM classifiers for discriminating RF signals. As a result, the proposed approach can achieve blind signal classification that requires no prior knowledge (e.g., MCS, pulse shaping) about the signals present in an arbitrary RF channel. Since modulated RF signals undergo pulse shaping to aid the matched filter detection, our method exploits variability in relative similarity against the dictionary atoms as the key discriminating factor for classification. Our experimental results indicate that we can blindly separate different classes of digitally modulated signals with a 0.703 recall and 0.246 false alarm at 20dB SNR. Provided a small labeled dataset for supervised classifier training, we could improve the classification performance to a 0.878 recall and 0.141 false alarm.

Recent advances in clustering have shown that ensuring a minimum separation between cluster centroids leads to higher quality clusters compared to those found by methods that explicitly set the number of clusters to be found, such as k-means. One such algorithm is DP-means, which sets a distance parameter λ for the minimum separation. However, without knowing either the true number of clusters or the underlying true distribution, setting λ itself can be difficult, and poor choices in setting λ will negatively impact cluster quality. As a general solution for finding λ, in this paper we present λ-means, a clustering algorithm capable of deriving an optimal value for λ automatically. We contribute both a theoretically-motivated cluster-based version of λ-means, as well as a faster conflict-based version of λ-means. We demonstrate that λ-means discovers the true underlying value of λ asymptotically when run on datasets generated by a Dirichlet Process, and achieves competitive performance on a real world test dataset. Further, we demonstrate that when run on both parallel multicore computers and distributed cluster computers in the cloud, cluster-based λ-means achieves near perfect speedup, and while being a more efficient algorithm, conflict-based λ-means achieves speedups only a factor of two away from the maximum-possible.

We present Deep Sparse-coded Network (DSN), a deep architecture based on multilayer sparse coding. It has been considered difficult to learn a useful feature hierarchy by stacking sparse coding layers in a straightforward manner. The primary reason is the modeling assumption for sparse coding that takes in a dense input and yields a sparse output vector. Applying a sparse coding layer on the output of another tends to violate the modeling assumption. We overcome this shortcoming by interlacing nonlinear pooling units. Average- or max-pooled sparse codes are aggregated to form dense input vectors for the next sparse coding layer. Pooling achieves nonlinear activation analogous to neural networks while not introducing diminished gradient flows during the training. We introduce a novel backpropagation algorithm to finetune the proposed DSN beyond the pretraining via greedy layerwise sparse coding and dictionary learning. We build an experimental 4-layer DSN with the ℓ1-regularized LARS and the greedy-ℓ0OMP, and demonstrate superior performance over a similarly-configured stacked autoencoder (SAE) on CIFAR-10.

Deep neural networks are state of the art methods for many learning tasks due to their ability to extract increasingly better features at each network layer. However, the improved performance of additional layers in a deep network comes at the cost of added latency and energy usage in feedforward inference. As networks continue to get deeper and larger, these costs become more prohibitive for real-time and energy-sensitive applications. To address this issue, we present BranchyNet, a novel deep network architecture that is augmented with additional side branch classifiers. The architecture allows prediction results for a large portion of test samples to exit the network early via these branches when samples can already be inferred with high confidence. BranchyNet exploits the observation that features learned at an early layer of a network may often be sufficient for the classification of many data points. For more difficult samples, which are expected less frequently, BranchyNet will use further or all network layers to provide the best likelihood of correct prediction. We study the BranchyNet architecture using several well-known networks (LeNet, AlexNet, ResNet) and datasets (MNIST, CIFAR10) and show that it can both improve accuracy and significantly reduce the inference time of the network.

Spoken language recognition requires a series of signal processing steps and learning algorithms to model distinguishing characteristics of different languages. In this paper, we present a sparse discriminative feature learning framework for language recognition. We use sparse coding, an unsupervised method, to compute efficient representations for spectral features from a speech utterance while learning basis vectors for language models. Differentiated from existing approaches in sparse representation classification, we introduce a maximum a posteriori (MAP) adaptation scheme based on online learning that further optimizes the discriminative quality of sparse-coded speech features. We empirically validate the effectiveness of our approach using the NIST LRE 2015 dataset.

Competing Cognitive Radio Network (CCRN) coalesces communicator (comm) nodes and jammers to achieve maximal networking efficiency against adversarial threats. We have previously developed two contrasting approaches based on multiarmed bandit (MAB) and value-iterated Q-learning. Despite their differences, both approaches have demonstrated the efficacy of applying a machine learning technique to jointly compute comm and jammer actions in hypothetical two-network competition for an open dynamic spectrum. When sampled channel reward characteristics are time-invariant-i.e., stationarity of learned information, both MAB and Q-learning based strategies have resulted in the best possible reward empirically.

We propose a data-driven geolocation method on microblog text. Key idea underlying our approach is sparse coding, an unsupervised learning algorithm. Unlike conventional positioning algorithms, we geolocate a user by identifying features extracted from her social media text. We also present an enhancement robust to a random erasure of words in the text and report our experimental results with uniformly or randomly subsampled microblog text. Our solution features a novel two-step procedure consisting of upconversion and iterative refinement by joint sparse coding. As a result, we can reduce the computational cost of geolocation while preserving accuracy. In the light of information preservation and privacy, we remark potential applications of this paper.

We introduce State-Informed Link-Layer Queuing (SILQ), a system that models, predicts, and avoids packet delivery failures caused by temporary wireless outages in everyday scenarios. By stabilizing connections in adverse link conditions, SILQ boosts throughput and reduces performance variation for network applications, for example by preventing unnecessary TCP timeouts due to dead zones, elevators, and subway tunnels. SILQ makes predictions in real-time by actively probing links, matching measurements to an overcomplete dictionary of patterns learned offline, and classifying the resulting sparse feature vectors to identify those that precede outages. We use a clustering method called sparse coding to build our data-driven link model, and show that it produces more variation-tolerant predictions than traditional loss-rate, location-based, or Markov chain techniques.

Orthogonal matching pursuit (OMP) is an efficient approximation algorithm for computing sparse representations. However, prior research has shown that the representations computed by OMP may be of inferior quality, as they deliver suboptimal classification accuracy on several im- age datasets. We have found that this problem is caused by OMP’s relatively weak stability under data variations, which leads to unreliability in supervised classifier training. We show that by imposing a simple nonnegativity constraint, this nonnegative variant of OMP (NOMP) can mitigate OMP’s stability issue and is resistant to noise overfitting. In this work, we provide extensive analysis and experimental results to examine and validate the stability advantage of NOMP. In our experiments, we use a multi-layer deep architecture for representation learning, where we use K-means for feature learning and NOMP for representation encoding. The resulting learning framework is not only efficient and scalable to large feature dictionaries, but also is robust against input noise. This framework achieves the state-of-the-art accuracy on the STL-10 dataset.

This paper describes an adaptation of cognitive radio technology for tactical wireless networking. We introduce Competing Cognitive Radio Network (CCRN) featuring both communicator and jamming cognitive radio nodes that strategize in taking actions on an open spectrum under the presence of adversarial threats. We present the problem in the Multi-armed Bandit (MAB) framework and develop the optimal media access strategy consisting of mixed communicator and jammer actions in a Bayesian setting for Thompson sampling based on extreme value theory. Empirical results are promising that the proposed strategy seems to outperform Lai & Robbins and UCB, some of the most important MAB algorithms known to date.

We propose a spectrum analyzer that leverages many networked commodity sensor nodes, each of which samples its portion in a wideband spectrum. The sensors operate in parallel and transmit their measurements over a wireless network without performing any significant computations such as FFT. The measurements are forwarded to the backend of the system where spectrum analysis takes place. In particular, we propose a solution that compresses the raw measurements in a simple random linear projection and combines the compressed measurements from multiple sensors in-network. As a result, we achieve a substantial reduction in the network bandwidth requirement to operate the proposed system. We discover that the overall communication cost can be independent of the number of sensors and is affected only by sparsity of discretized spectrum under analysis. This principle founds the basis for a claim that our network-based spectrum analyzer can scale up the number of sensor nodes to process a very wide spectrum block potentially having a GHz bandwidth. We devise a novel recovery algorithm that systematically undoes compressive encoding and in-network combining done to the raw measurements, incorporating the least squares and I1-minimization decoding used in compressive sensing, and demonstrate that the algorithm can effectively restore an accurate estimate of the original data suitable for finegrained spectrum analysis. We present mathematical analysis and empirical evaluation of the system with software-defined radios.

This paper presents MIMO/CON, a PHY/MAC cross-layer design for multiuser MIMO wireless networks that delivers throughput scalable to many users. MIMO/CON supports concurrent channel access from uncoordinated and loosely synchronized users. This new capability allows a multi-antenna MIMO access point (AP) to fully realize its MIMO capacity gain. MIMO/CON draws insight from compressive sensing to carry out concurrent channel estimation. In the MAC layer, MIMO/CON boosts channel utilization by exploiting normal MAC layer retransmissions to recover otherwise undecodable packets in a collision. MIMO/CON has been implemented and validated on a 4×4 MIMO testbed with software-defined radios. In software simulations, MIMO/CON achieves a 210% improvement in MAC throughput over existing staggered access protocols in a 5-antenna AP scenario.

We describe a method of integrating Karhunen-Loève Transform (KLT) into compressive sensing, which can as a result improve the compression ratio without affecting the accuracy of decoding. We present two complementary results: 1) by using KLT to find an optimal basis for decoding we can drastically reduce the number of measurements for compressive sensing used in applications such as radio spectrum analysis; 2) by using compressive sensing we can estimate and recover the KLT basis from compressive measurements of an input signal. In particular, we propose CS-KLT, an online estimation algorithm to cope with nonstationarity of wireless channels in reality. We validate our results with empirical data collected from a wideband UHF spectrum and field experiments to detect multiple radio transmitters, using software-defined radios.

We propose a medium access control (MAC) protocol for wireless local area networks (LANs) that leverages the theory of compressive sensing. The proposed compressive sensing MAC (CS-MAC) exploits the sparse property that, at a given time, only a few hosts are expected to request for radio channel access. Under CS-MAC, a central coordinator, such as a wireless access point (AP) can recover a multitude of these requests in one decoding operation, and then schedule multiple hosts accordingly. The coordinator is only required to receive a relatively small number of random projections of host requests, rather than polling individual hosts. This results in an efficient request-grant method. Via a hardware prototype based on a software-defined radio platform, we demonstrate the feasibility of realizing CS-MAC with compressive measurements formed in the air to achieve high efficiency.

We present statistical screening of test vectors for detecting a Trojan, malicious circuitry hidden inside an integrated circuit (IC). When applied a test vector, a Trojan-embedded chip draws extra leakage current that is unfortunately too small for the detector in most cases and concealed by process variation related to chip fabrication. To remedy the problem, we formulate a statistical approach that can screen and select test vectors in detecting Trojans. We validate our approach analytically and with gate-level simulations and show that our screening method leads to a substantial reduction in false positives and false negatives when detecting IC Trojans of various sizes.

Incorporating wireless transceivers with numerous antennas (such as Massive-MIMO) is a prospective way to increase the link capacity or enhance the energy efficiency of future communication systems. However, the benefits of such approach can be realized only when proper channel information is available at the transmitter. Since the amount of the channel information required by the transmitter is large with so many antennas, the feedback is arduous in practice, especially for frequency division duplexing (FDD) systems. This paper proposes channel feedback reduction techniques based on the theory of compressive sensing, which permits the transmitter to obtain channel information with acceptable accuracy under substantially reduced feedback load. Furthermore, by leveraging properties of compressive sensing, we present two adaptive feedback protocols, in which the feedback content can be dynamically configured based on channel conditions to improve the efficiency.

We introduce a joint decoding method for compressive sensing that can simultaneously exploit sparsity of individual components of a composite signal. Our method can significantly reduce the total number of variables decoded jointly by separating variables of large magnitudes in one domain and using only these variables to represent the domain. Furthermore, we enhance the separation accuracy by using joint decoding across multiple domains iteratively. This separation-based approach improves the decoding time and quality of the recovered signal. We demonstrate these benefits analytically and by presenting empirical results.

Wireless data transfer under high mobility, as found in unmanned aerial vehicle (UAV) applications, is a challenge due to varying channel quality and extended link outages. We present FlowCode, an easily deployable link-layer solution utilizing multiple transmitters and receivers for the purpose of supporting existing transport protocols such as TCP in these scenarios. By using multiple transmitters and receivers and by exploiting the resulting antenna beam diversity and parallel transmission effects, FlowCode increases throughput and reception range. In emulation, we show that TCP over FlowCode gives greater goodput over a larger portion of the flight path, compared to an enhanced TCP protocol using the standard 802.11 MAC. In the process, we make a strong case for using trace-modulated emulation when developing distributed protocols for complex wireless environments.

In a distributed sensor network, the goodness of a sensor may change according to its current device status (e.g., health of hardware) and environment (e.g., wireless reception conditions at the sensor location). As a result, it is often necessary to validate periodically sensors in the field, in order to identify those which no longer work properly and eliminate them from applications' use. In this paper, we describe a spectral clustering approach of using peer sensors to identify these bad sensors. Using a simple model problem, we describe how our sensor validation method works and demonstrate its performance in simulation.

We consider the problem of localizing wireless nodes in an outdoor, open-space environment, using ad-hoc radio ranging measurements, e.g., 802.11. We cast these ranging measurements as a set of distance constraints, thus forming an over-determined system of equations suitable for non-linear least squares optimization. However, ranging measurements are often subject to errors, induced by multipath signals and variations in path loss, unreliable hardware or antenna connectors, or imperfection in measurement models. Such potentially large, non-Gaussian errors in the measurement data ultimately produce inaccurate localization solutions. We propose a new error-tolerant localization method, called snap-inducing shaped residuals (SISR), to identify automatically "bad nodes" and "bad links" arising from these errors, so that they receive less weight in the localization process. In particular, SISR snaps "good nodes" to their accurate locations and gives less emphasis to other nodes. While the mathematical techniques used by SISR are similar to robust statistics, SISR's exploitation of the snap-in effect in localization appears to be novel. We provide analysis on the principle of SISR, illustrate errors in real-world measurements, and demonstrate a working SISR implementation in field experiments on a testbed of 37 wireless nodes, as well as show the superior performance of SISR in simulation with a larger number of nodes.

In this paper, we construct a family of block orthogonal Golay sequences that have low peak-to-mean envelope power ratio (PMEPR) as well as block wise orthogonal properties. We then present an application of the sequences to channel estimation of multiple-input multiple-output orthogonal frequency division multiplexing (MIMO-OFDM) systems. We compare the performance of the proposed algorithm with that of a frequency division multiplexing (FDM) piloting algorithm, and investigate the effect of co-channel interference (CCI) on the channel estimation performance.

We consider the task of using one or more unmanned aerial vehicles (UAVs) to relay messages between two distant ground nodes. For delay-tolerant applications like latency-insensitive bulk data transfer, we seek to maximize throughput by having a UAV load from a source ground node, carry the data while flying to the destination, and finally deliver the data to a destination ground node. We term this the "load-carry-and-deliver" (LCAD) paradigm and compare it against the conventional multi-hop, store-and-forward paradigm. We identify and analyze several of the most important factors in constructing a throughput-maximizing framework subject to constraints on both application allowable delay and UAV maneuverability. We report performance measurement results for IEEE 802.11g devices in three flight tests, based on which we derive a statistical model for predicting throughput performance for LCAD. Due to the nature of commercial off-the-shelf systems, this methodology is of essential importance for allowing better flight-path design to achieve high throughput.

In this paper, we propose transmit antenna selection based on receiver feedback of channel information obtained via link-layer probing. Furthermore, we report the performance gain of the proposed antenna selection scheme in an experimental multi-antenna 802.11 network. We built a low-altitude Unmanned Aerial Vehicle (UAV) testbed using commodity dual-antenna 802.11 hardware and performed field experiments to collect traces of link performance using antennas of various types and orientations. Based on the collected traces, we demonstrate that transmit antenna selection can achieve a significant amount of gain using a link-layer channel probing protocol at a relatively low probing rate. The largest improvement we observed with joint transmit/receive antenna selection in 2x2 systems was 32%, about twice as much as that of receive-only antenna selection in 1x2 systems, which achieved 17%. Moreover, a similar improvement is obtained with probing intervals up to about 200 milliseconds, which is infrequently enough to consume only a small fraction of the available 802.11 channel capacity. Since these results require only a low implementation and operational cost, we conclude that transmit antenna selection is a worthwhile technique to use with the kind of multi-antenna mobile ad-hoc networks we examined.

We evaluate the performance impact of adjacent channel interference (ACI) in multi-hop wireless networks based on dual-radio 802.11a nodes. Although these nodes use chipsets that satisfy the transmit-mask requirements set by the IEEE 802.11 standard, the multi-hop performance is still significantly affected by ACI. That is, a node's transmitter can interfere with its own receiver on a different channel; as a result, multi-hop throughput is severely degraded. This degradation is especially pronounced for 802.11a. We use a spectrum analyzer with a signal combiner to quantify ACI under various conditions and propose solutions to mitigate the effect of such interference on multi-hop forwarding. Field experiments with multi-hop relay have validated these findings as well as the effectiveness of our solutions.

We report measured performance of 802.11a wireless links from an unmanned aerial vehicle (UAV) to ground stations. In a set of field experiments, we record the received signal strength indicator (RSSI) and measure the raw link-layer throughput for various antenna orientations, communication distances and ground-station elevations. By comparing the performance of 32 simultaneous pairs of UAV and ground station configurations, we are able to conclude that, in order to achieve the highest throughput under a typical flyover UAV flight path, both the UAV and the ground station should use omni-directional dipole (as opposed to high-gain, narrow- beam) antennas positioned horizontally, with their respective antenna null pointing to a direction perpendicular to the UAV's flight path. In addition, a moderate amount of elevation of the ground stations can also improve performance significantly.

Given a set of wireless access points (APs) geographically distributed in a region, we consider the problem of steering their directional antennas to form multiple overlapping, non-interfering wireless meshes. The resulting multiple wireless meshes provide not only a simultaneously usable, but also a fail-safe, wireless network infrastructure. We describe a mesh construction algorithm, called "beam-crossing grids", that allows the constructed multiple wireless meshes to cover a large common area, while not interfere with each other. This means that, from most locations in the area, wireless terminals can have access to more than one of these meshes for improved network bandwidth and redundancy. By using analysis and simulation, we show that when the AP density is relatively high, the algorithm converges rapidly to a high-performance construction of wireless meshes.

We present an overlay network routing scheme, called path probing relay routing (PPRR), which is capable of promptly switching to alternative paths when the direct paths provided by the underlying IP networks suffer from serious performance degradation or outage. PPRR uses a randomized search algorithm to discover available alternative paths and employs an end-to-end, on-demand probing technique to determine their quality. To assess the effectiveness of PPRR, we conduct performance simulations using four sets of real-world traces, collected by various research groups at different times and places. Our simulation results show that the performance of PPRR is comparable to that of a typical link state relay routing algorithm. Compared with the latter, PPRR has lower probing overhead in the sense that the overhead remains constant as network size grows. In particular, PPRR avoids the need to flood the overlay network with link state updates.

We apply sensor networks to the problem of tracking moving objects. We describe a publish-and-subscribe tracking method, called scalable tracking using networked sensors (STUN), that scales well to large numbers of sensors and moving objects by using hierarchy. We also describe a method, called drain-and-balance (DAB), for building efficient tracking hierarchies, computed from expected characteristics of the objects movement patterns. DAB is shown to perform well by running it on 1D and 2D sensor network topologies, and comparing it to schemes, which do not utilize movement information.

We propose using spectral analysis to identify normal TCP traffic so that it will not be dropped or rate-limited in defense against denial of service (DoS) attacks. The approach can reduce false positives of attacker identification schemes and thus decrease the associated unnecessary slowdown or stoppage of legitimate traffic. For the spectral analysis, we use the number of packet arrivals of a flow in fixed-length time intervals as the signal. We then estimate the power spectral density of the signal, in which information of periodicity, or lack thereof, in the signal reveals itself. A normal TCP flow should exhibit strong periodicity around its round-trip time in both flow directions, whereas an attack flow usually does not. We validate the effectiveness of the approach with simulation and trace analysis. We argue that the approach complements existing DoS defense mechanisms that focus on identifying attack traffic.

This paper describes a congestion control method for TCP that adjusts the transmission rate of a TCP connection not only by changing the congestion window size as in normal TCP, but also by delaying the transmission of packets at the sender. We refer to this mechanism as TCP with sender-based delay control, or simply SDC. SDC can keep the window size of a TCP connection above a certain threshold even when its fair share of bandwidth is arbitrarily small. Since TCP fast retransmit and recovery is likely to work when the window size of the connection is sufficiently large, the new scheme can result in reduced-frequency of TCP timeouts for the connection. In particular, SDC allows many TCP flows to share a link without experiencing many timeouts. In addition, SDC reduces a well-known TCP bias against connections with large round trip times. The paper presents the principle behind SDC and simulation results demonstrating its properties and advantages.

We propose a scalable reservation protocol and admission control algorithm, DEAC, that combines features of both endpoint admission control and DiffServ architectures. We are able to make hard guarantees to individual flows without per-flow management in the network core. By allowing flows to probe the network for available bandwidth and routers to control the amount of simultaneous probe traffic, this scheme addresses the problems that limit the effectiveness of current endpoint admission control schemes. We describe the overall admission control process and our implementation. We give a detailed analysis of the parameters that control the admission control algorithm and present simulation results that verify the analysis.

Active delay control is a novel extension for TCP, where TCP endpoints impose delays on the transmission of packets to improve performance. The amount of delay can be calculated by routers from the level of congestion, or by endpoints from the received congestion signals. In particular, when there are many TCP flows competing for the bandwidth of a link, they can reduce their transmission rates to arbitrary degrees by increasing delays, without experiencing TCP time-outs. Active delay control is therefore useful for those long-lived TCP-based applications that cannot tolerate time-outs. Examples of such applications are video streaming and storage networks. It is also useful for short-lived flows that require short transfer time. Examples of such applications are HTTP transactions. We present the concept and motivation behind active delay control, and evaluate them by simulation.

The widespread use of wireless devices presents new challenges for network operators, who need to provide service to ever larger numbers of mobile end users, while ensuring quality-of-service guarantees. We describe a new distributed routing algorithm that performs dynamic load-balancing for wireless access networks. The algorithm constructs a load-balanced backbone tree, which simplifies routing and avoids per-destination state for routing and per-flow state for QoS reservations. We evaluate the performance of the algorithm using several metrics including adaptation to mobility, degree of load-balance, bandwidth blocking rate, and convergence speed. We find that the algorithm achieves better network utilization by lowering bandwidth blocking rates than other methods.

Ad hoc networks can be formed on highways among moving vehicles, each equipped with a wireless LAN device. However, during times of low traffic density, it is likely that such networks are disconnected. This paper tests the hypothesis that the motion of vehicles on a highway can contribute to successful message delivery, provided that messages can be relayed---stored temporarily at moving nodes while waiting for opportunities to be forwarded further. Using vehicle movement traces from a traffic microsimulator, we measure average message delivery time and find that it is shorter than when the messages are not relayed. We condclude that ad hoc relay wireless networks, based on wireless LAN technologies, have potential for many emerging applications of this kind

Unicasting video streams over TCP connections is a challenging problem because video sources cannot normally adapt to delay and throughput variations of TCP connections. This paper points out a direction on how TCP can be modified such that TCP connections can carry hierarchically-encoded layered video streams well, while being friendly to other competing flows. The method is calledReceiver-based Delay Control(RDC). Under RDC, a TCP connec?tion can slow down its transmission rate to avoid congestion by delaying ACK packet generation at the TCP receiver based on notifications from routers. The paper presents the principle behind RDC, argue that it is TCP-friendly, describe an implementation that uses 1-bit congestion notification from routers, and give our simulation results.

We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet forwarding decisions. GPSR makes greedy forwarding decisions using only information about a router's immediate neighbors in the network topology. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. By keeping state only about the local topology, GPSR scales better in per-router state than shortest-path and ad-hoc routing protocols as the number of network destinations increases. Under mobility's frequent topology changes, GPSR can use local topology information to find correct new routes quickly. We describe the GPSR protocol, and use extensive simulation of mobile wireless networks to compare its performance with that of Dynamic Source Routing. Our simulations demonstrate GPSR's scalability on densely deployed wireless networks.

A TCP trunk is an aggregate traffic stream whose data packets are transported at a rate dynamically determined by the TCP's congestion control. Typically such a trunk is implemented on top of a layer-2 virtual circuit or an MPLS label switched path. A management TCP connection is used to regulate the rate at which the trunk transmits its data packets. Setting up a TCP trunk over a circuit or a path is easy, involving only the two end nodes of a trunk to implement the management TCP connection. A TCP trunk can guarantee minimum bandwidth while being able to grab additional bandwidth when it is available. When carried by a TCP trunk, UDP flows will be constrained in their bandwidth usage, although they themselves do not perform congestion control. Experiments on testbed networks have validated these properties. TCP trunking can be an effective tool for network operators in managing bandwidth sharing between aggregates.

This paper proposes a simple methodology for constructing extensible and high-fidelity TCP/IP simulators in BSD UNIX environments. A simulator constructed under this methodology will simulate multiple network nodes by re-entering the UNIX kernel of the simulation host multiple times. Generated simulation results are derived from executing the native TCP/IP protocol stack on the simulation host. They are thus more accurate than those generated from a TCP/IP network simulator that implements only an abstraction of a real-life TCP/IP implementation. By using this methodology, the simulator architecture creates an illusion for the BSD UNIX kernel that the simulated network is a real network. All existing application programs such as FTP, telnet and HTTP, and all network utilities such as route, ifconfig and tcpdump are immediately applicable to a simulated network for generating network traffic, configuring networks, gathering statistics, etc. Additionally, the network simulator provides the standard UNIX API on every node in a simulated network so that ally existing or future application program can run on any node in a simulated network. This allows a network simulator to be easily extended to study high-level network architecture and application issues.

Zero queueing flow control (ZQFC) is a new credit-based flow control method for ATM networks. The receiving node of such a flow-controlled link will have zero queue-occupancy in the steady state. ZQFC uses both link and VC flow control simultaneously over the link to implement the required rate adaptation for achieving zero queueing. Because of its zero queueing property, ZQFC is able to solve a head-of-the-line blocking problem that may arise when multiple VCs share the same receiver buffer in implementing their flow control. ZQFC works well with TCP traffic. When there is any queue buildup associated with a TCP connection in a shared buffer, ZQFC will identify the connection and take steps to reduce its arrival rate at the buffer. This will allow many TCP connections to share the buffer efficiently and fairly. It makes sense to deploy ZQFC for just a single link where performance improvement is critical. Simulations using real-life TCP code have demonstrated these advantages of ZQFC.

To match an ideal Internet gateway which rigorously enforces fair sharing among competing TCP connections, an ideal TCP sender should possess two properties while obeying congestion avoidance and control principles. First, the TCP sender which under-uses network resources should avoid retransmission time-outs. When experiencing network congestion, a TCP connection should not time-out unless it has already reduced its congestion window to one packet but still cannot survive. Second, the TCP sender which over-uses network resources should lower its bandwidth. The congestion window for a connection should decrease each time a lost packet is detected because an ideal gateway will drop packets, during congestion, with a probability proportional to the bandwidth of the connection. Following these guidelines, we propose network-sensitive Reno (Net Reno), a set of optimizations that can be added to a traditional Reno TCP sender. Using the TCP's self-clocking property and the packet conservation rule, Net Reno improves Reno and its variants (New-Reno and SACK), in reducing TCP retransmission time-outs (RTOs) and in being conservative in network usage during the fast recovery phase. We have shown that over 85% of RTOs are due to small congestion windows that prevent fast retransmission and recovery algorithms from being effective. This implies that sophisticated recovery schemes such as SACK will have limited benefits for these loads. Net Reno overcomes this problem with a small window optimization. Net Reno can recover any number of packet losses without time-outs as long as the network keeps at least one packet alive for the connection.

The network file system protocol (NFS) has been the leading distributed file system for workstations since it was first introduced by Sun Microsystems in 1986. The geographical scale of NFS has been limited to the local area due to its relatively low performance on the wide area Internet. However, with the advent of high bandwidth wide area networks such as ATM, NFS over WANs may become more promising. In this paper, the performance of NFS over various sizes of WAN is studied The effects of ATM flow-control and queueing strategies on NFS are discussed, as are the performance of TCP and UDP as NFS transport protocols. The primary conclusion is that standard NFS over UDP works well over ATM WANs as long as ATM-level flow control keeps the cell loss rate under one percent. In some cases, NFS over TCP works badly with small packets due to unfortunate interactions with TCP's congestion window.

Extensive simulation has demonstrated the effectiveness of credit-based ATM flow control in supporting client-server applications. In particular, request/response protocols used in these applications allow efficient sharing of switch buffer, for the case when all the VCs sharing the same buffer are subject to the same degree of downstream congestion. The required buffer size can be as small as the minimum of bandwidth/sup */RTT for the link and Clients/sup */Reply-Size. Request/response protocols generally tolerate congestion better than greedy loads. Being able to avoid synchronization, FIFO scheduling is sometimes more efficient than VC round-robin scheduling. These findings are derived from an online Web database of simulation results covering more than 10,000 network and load configurations. The Web database approach has proven to be effective in managing and navigating a large set of simulation results.

In credit-based flow control for ATM networks, a buffer is first allocated to each VC (virtual circuit) and then credit control is applied to the VC for avoiding possible buffer overflow. Receiver-oriented, adaptive buffer allocation allows a receiver to allocate its buffer dynamically, to VCs from multiple upstream nodes based on their bandwidth usage. The paper describes, in detail, such an adaptive algorithm capable of supporting a wide range of link speeds and propagation delays, and also packing multiple allocation and credit records in a single message. Analysis and simulation results show that even under highly bursty traffic, the adaptive scheme guarantees no cell loss due to congestion, and achieves excellent performance in utilization, fairness, ramp-up and packing, while requiring only relatively small node memory and bandwidth overhead. The required memory need only be 4*RTT+2*N, where RTT is the link round-trip time in cell cycles and N is the number of VCs.

This paper presents three new results concerning credit-based flow control for ATM networks: (1) a simple and robust credit update protocol (CUP) suited for relatively inexpensive hardware/software implementation; (2) automatic adaptation of credit buffer allocation for virtual circuits (VCs) sharing the same buffer pool; (3) use of credit-based flow control to improve the effectiveness of statistical multiplexing in minimizing switch memory. These results have been substantiated by analysis, simulation and implementation.

Summary form only given. This paper argues that, for high-speed networks such as ATM, it is important to use link-by-link flow control on a per virtual circuit (VC) basis. It can effectively control congestion and maximize network utilization. Three progressively memory-efficient, credit-based flow control schemes, called N123, N123+ and N23, are described, and simulation results of these schemes are presented. An ATM switch, which supports credit-based flow control, is under joint development by BNR and Harvard.>

Link-by-link flow-controlled virtual channels are proposed for asynchronous transfer mode (ATM) networks. The flow control mechanism efficiently uses leftover bandwidth after guaranteed traffic has been served, thus achieving high network utilization. Compatible with existing ATM standards, this proposal is called FCVC, (for flow-controlled virtual channels). Three increasingly memory-efficient credit-based flow control schemes, named N123, N123+ and N23, are described for implementing link-by-link flow control. These credit-based flow control schemes have been used in an experimental 622-Mbps ATM switch currently under development. Simulations based on the switch design have confirmed that the flow control mechanism is indeed able to provide sufficiently rapid feedback to let a network adapt to load changes and maximize its performance.>

The relationship between parallel computation cost and communication cost for performing divide-and-conquer (D&C) computations on a parallel system of p processors is studied. The parallel computation cost is the maximal number of the D&C nodes that any processor in the parallel system may expand, whereas the communication cost is the total number of cross nodes (nodes generated by one processor but expanded by another processor). A scheduling algorithm is proposed, and lower bounds on the communication cost are derived. The proposed scheduling algorithm is optimal with respect to the communication cost, since the parallel computation cost of the algorithm is near optimal.>

Several large applicationshave been paralleli,zed on Nectar, a network-based multicomputer recently developed by Carnegie Mellon.These applications were previously either too large or too complex to be easily implemented on distributed memory parallel systems.Parallelizing these applications was made possible by the cooperative use of many existing general-purpose computers over high-speed networks, and by an implementation methodology based on a clean separation between applicatiionspecific and system-specific code.We illustrate these points using our experience with parallelizing three real-world applications.The success in these applications clearly points out a new direction in parallel processing.The Nectar system [1] developed by Carnegie Mellon is intended to provide general support for parallelizing large applications.The system is a multicomputer built around a high-speed network.The use of existing general-purpose computers as its nodes and the highbandwidth and low-latency network makes the system inherently suited for large applications.The system has allowed us to parallelize applications that were previously either tm complex or too communicationintensive to be suited for parallel processing.This paper describes the Nectar implementation of three applications: (1) COSMOS [4], a switch-level circuit simulator developed by Randy Bryant and his associates at Carnegie Mellon; (2) NOODLES [7], a solid modeling package developed by Professor

This paper describes a new approach for automatic generation of ejj$cien~parallel programsfiom sequential blocked lin-

Multicomputersbuiltaround a general network are now a viable alternative to multicomputersbased on a system-speci~c interconnect because of architectural improvements in two areas.First, the host-network interface overhead can be minimized by reducing copy operations and host interrupts.Second, the network can provide high bandwidth and low latency by using high-speed crossbar switches and efficient protocol implementations.While still enjoying thejexibility of general networks, the resulting network-based multicomputers achieve high performance for typical multicomputer applications that use system-specijic interconnects.We have developed a network-based mtdticomputer called Nectar that supports these claims.

The iWarp processor, which integrates both communication and computation functions on a single VLSI component, is described. The iWarp component and subsystems including it are powerful building blocks for constructing a new generation of application-specific computing systems. These special-purpose systems can achieve very high performance, while maintaining a high degree of flexibility to address different needs of an application. In particular, iWarp systems deliver high computation bandwidth (up to 20 GFLOPS for a 1024 cell system), as well as high communication bandwidth (320 Mbytes/s per cell). Programming these systems is assisted by modern tools such as optimizing compilers and parallel program generators.>

iWarp is a parallel architecture developed jointly by Carnegie Mellon University and Intel Corporation. The iWarp communication system supports two widely used interprocessor communication styles: memory communication and systolic communication. This paper describes the rationale, architecture, and implementation for the iWarp communication system.

Nectar is a “network backplane” for use in heterogeneous multicomputers. The initial system consists of a star-shaped fiber-optic network with an aggregate bandwidth of 1.6 gigabits/second and a switching latency of 700 nanoseconds. The system can be scaled up by connecting hundreds of these networks together.

Warp is a programmable, systolic array computer developed by Carnegie Mellon and produced by GE. A 10-cell Warp machine can perform 100 million floating-point operations per second (10 MFLOPS). A variety of applications have been mapped onto Warp. The experience has been that the mapping is not a real problem; in fact, usually near-optimal mapping is relatively easy to obtain, and the actual implementation of the mapping on the machine can often be automated. This paper explains why this is the case by examining some computational models which are frequently used on Warp. Carnegie Mellon and Intel are jointly developing a VLSI version of Warp, called iWarp. It is expected that many applications can be efficiently mapped onto low-cost iWarp arrays to achieve an effective computation bandwidth of about one GigaFLOPS.

The nature of the deadlock problem for the systolic model of communication is described. This problem does not exist for special-purpose systolic arrays for which the hardware designer can afford providing as many queues as required by the specific computation that the array intends to implement. However, for programmable systolic arrays, the number of messages crossing the interval between two adjacent cells can be arbitrarily large, depending on the program. As a result, the possibility of deadlock always exists, since the number of queues between adjacent cells is fixed. The problem of avoiding queue-induced deadlocks, for deadlock-free programs, at run time is described, and a solution to the problem is given. Schemes for consistent labeling and compatible queue assignment, for which the solution calls, as also described, as is how to take advantage of the buffering capability provided by queues.>

The Warp machine is a systolic array computer of linearly connected cells, each of which is a programmable processor capable of performing 10 million floating-point operations per second (10 MFLOPS). A typical Warp array includes ten cells, thus having a peak computation rate of 100 MFLOPS. The Warp array can be extended to include more cells to accommodate applications capable of using the increased computational bandwidth. Warp is integrated as an attached processor into a Unix host system. Programs for Warp are written in a high-level language supported by an optimizing compiler. The first ten-cell prototype was completed in February 1986; delivery of production machines started in April 1987. Extensive experimentation with both the prototype and production machines has demonstrated that the Warp architecture is effective in the application domain of robot navigation as well as in other fields such as signal processing, scientific computation, and computer vision research. For these applications, Warp is typically several hundred times faster than a VAX 11/780 class computer. This paper describes the architecture, implementation, and performance of the Warp machine. Each major architectural decision is discussed and evaluated with system, software, and application considerations. The programming model and tools developed for the machine are also described. The paper concludes with performance data for a large number of applications.

Warp is a programmable systolic array machine designed by CMU and built together with its industrial partners-GE and Honeywell. The first large scale version of the machine with an array of 10 linearly connected cells will become operational in January 1986. Each cell in the array is capable of performing 10 million 32-bit floating-point operations per second (10 MFLOPS). The 10-cell array can achieve a performance of 50 to 100 MFLOPS for a large variety of signal processing operations such as digital filtering, image compression, and spectral decomposition. The machine, augmented by a Boundary Processor, is particularly effective for computationally expensive matrix algorithms such as solution of linear systems, QR-decomposition and singular value decomposition, that are crucial to many real-time signal processing tasks. This paper outlines the Warp implementation of the 2- dimensional Discrete Cosine Transform and singular value decomposition.

This paper describes the scan line array processor (SLAP), a new architecture designed for high-performance yet low-cost image computation. A SLAP is a SIMD linear array of processors, and hence is easy to build and scales well with VLSI technology; yet appropriate special features and programming techniques make it efficient for a surprisingly wide variety of low and medium level computer vision tasks. We describe the basic SLAP concept and some of its variants, discuss a particular planned implementation, and indicate its performance on computer vision and other applications.

One particular result is that to balance an array of p linearly connected PEs for performing matrix computations such as matrix multiplication and matrix triangularization, the size of each PE's local memory must grow linearly with p . Thus, the larger the array is, the larger each PE's local memory must be.

A high-performance systolic array computer has been designed by CMU and is currently under construction. The first copy of the machine, to be built by CMU together with its industrial partners before the end of 1985, will incorporate a programmable systolic array of ten linearly connected cells. Each cell in the systolic array is capable of performing 10 million floating-point operations per second (10 MFLOPS), giving the total machine a peak performance of 100 MFLOPS, or higher if additional cells are used. This particular systolic array computer is named Warp, suggesting that it can perform computations at a very high speed. The 10-cell systolic array, with one cell implemented on one board, can process 1024-point complex FFTs at a rate of one FFT every 600 µs. Under program control, the same array can perform many other primitive computations in signal, image, and vision processing, including two-dimensional convolution, dynamic programming, and real or complex matrix multiplication, at a rate of 100 million floating-point operations per second. Users may view the systolic array as an array of conventional "array processors," which can efficiently implement not only systolic algorithms where communication between adjacent cells is intensive, but also non-systolic algorithms where each cell operates on its own data independently from the rest. This paper describes the hardware organization of the Warp machine.

Warp is a programmable systolic array processor. One of its objectives is to support computer vision research. This paper shows how the Warp architecture can be used to fulfill the computational needs of low-level vision. We study the characteristics of low-level vision algorithms and show how they lead to requirements for computer architecture. These requirements are met by Warp. We then describe how the Warp system can be used. Warp programs can be classified in two ways: chained versus severed, and heterogeneous versus homogeneous. Chained and severed characterize the degree of interprocessor dependency, while heterogeneous and homogeneous characterize the degree of similarity between programs on individual processors. Taken in combination, these classes give four user models. Sophisticated programming tools are needed to support these user models.

Highly parallel VLSI computing structures consist of many processing elements operating simultaneously. In order for such processing elements to communicate among themselves, some provision must be made for synchronization of data transfer. The simplest means of synchronization is the use of a global clock. Unfortunately, large clocked systems can be difficult to implement because of the inevitable problem of clock skews and delays, which can be especially acute in VLSI systems as feature sizes shrink. For the near term, good engineering and technology improvements can be expected to maintain the feasibility of clocking in such systems; however, clock distribution problems crop up in any technology as systems grow. An alternative means of enforcing necessary synchronization is the use of self-timed asynchronous schemes, at the cost of increased design complexity and hardware cost. Realizing that different circumstances call for different synchronization methods, this paper provides a spectrum of synchronization models; based on the assumptions made for each model, theoretical lower bounds on clock skew are derived, and appropriate or best possible synchronization schemes for large processor arrays are proposed.

The problem of finding a greatest common divisor (GCD) of any two nonzero polynomials is fundamental to algebraic and symbolic computations, as well as to the decoder implementation for a variety of error-correcting codes. This paper describes new systolic arrays that can lead to efricient VLSI solutions to both the GCD problem and the extended GCD problem.

Highly parallel VLSI computing structures consist of many processing elements operating simultaneously. In order for such processing elements to communicate among themselves, some provision must be made for synchronization of data transfer. The simplest means of synchronization is the use of a global clock. Unfortunately, large clocked systems can be difficult to implement because of the inevitable problem of clock skews and delays, which can be especially acute in VLSI systems as feature sizes shrink. For the near term, good engineering and technology improvements can be expected to maintain the feasibility of clocking in such systems; however, clock distribution problems crop up in any technology as systems grow. An alternative means of enforcing necessary synchronization is the use of self-timed, asynchronous schemes, at the cost of increased design complexity and hardware cost. Realizing that different circumstances call for different synchronization methods, this paper provides a spectrum of synchronization models; based on the assumptions made for each model, theoretical lower bounds on clock skew are derived, and appropriate or best-possible synchronization schemes for large processor arrays are proposed. One set of models is based on assumptions that allow the use of a pipelined clocking scheme, where more than one clock event is propagated at a time. In this case, it is shown that even assuming that physical variations along clock lines can produce skews between wires of the same length, any one-dimensional processor array can be correctly synchronized by a global pipelined clock while enjoying desirable properties such as modularity, expandability and robustness. This result cannot be extended to two-dimensional arrays, however—the paper shows that under this assumption, it is impossible to run a clock such that the maximum clock skew between two communicating cells will be bounded by a constant as systems grow. For such cases or where pipelined clocking is unworkable, a synchronization scheme incorporating both clocked and “asynchronous” elements is proposed.

In recent years, many systolic algorithms have been proposed as solutions to computationally demanding problems in signal and image processing and other areas. Such algorithms exploit the regularity and parallelism of problems to achieve high performance and low I/O requirements. Since systolic algorithms generally consist of a few types of simple processors, or systolic cells, connected in a regular pattern, they are less expensive to design and implement than more general machines.

No abstract available.

With VLSI architecture, the chip area and design regularity represent a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a chip with a regular layout in time proportional to log n and with area proportional to n.

In this paper, the red-blue pebble game is proposed to model the input-output complexity of algorithms. Using the pebble game formulation, a number of lower bound results for the I/O requirement are proven. For example, it is shown that to perform the n-point FFT or the ordinary n×n matrix multiplication algorithm with O(S) memory, at least Ω(n log n/log S) or Ω(n3/@@@@S), respectively, time is needed for the I/O. Similar results are obtained for algorithms for several other problems. All of the lower bounds presented are the best possible in the sense that they are achievable by certain decomposition schemes.

The problem of performing multtphcaUon of n-bit binary numbers on a chip is considered Let A denote the ch~p area and T the time reqmred to perform mult~phcation.By using a model of computation which is a realistic approx~mauon to current and anucipated LSI or VLSI technology, ~t is shown thatfor all a ~ [0, 1], where A0 and To are posmve constants which depend on the technology but are mdependent of n.The exponent 1 + a is the best possible A consequence of this result is that binary multiphcatlon is "harder" than binary addmon More precisely, ff(AT2~)M(n) and (AT2~)A(n) denote the mmimum area-time complexity for n-b~t binary multiphcauon and addmon, respectively, then (AT2~)M(n) _ 1 f~(nl-a) for 0 _< a --< na for ~ ,(= fi(nl/2) for all a _> 0).

Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are presented. The methods used are “optimistic” in the sense that they rely mainly on transaction backup as a control mechanism, “hoping” that conflicts between transactions will not occur. Applications for which these methods should be more efficient than locking are discussed.

This paper identifies important steps in the design of a special purpose VLSI chip, and argues that the most crucial step is the design of the underlying algorithm. Because the algorithm determines the degree of parallelism and pipelining that is possible, it largely determines the performance of the chip. Furthermore, if the underlying algorithm has the right properties such as modularity and regularity, then the rest of the design should be routine and thus take little effort. These claims are supported by a concrete example—the design of an efficient pattern matching chip, which has been fabricated for testing.

This paper proposes the use of VLSI technology to perform relational database operations directly in hardware. It is shown that relational compulations, such as intersection, remove-duplicates, union, join, and division, can all be pipelined elegantly and efficiently on networks of processors having an array structure. These (systolic) processor arrays are readily and cost-effectively implementable with present technology, due to the extreme simplicity of their processors, and the high regularity of their interconnection structures.

The chip complexity of a computation is concerned with the chip area, A, and the time, T, required to perform the computation when implemented on a chip. An area-time product ATα,for α ≥ 0, is used as a complexity measure. A particular value of α, which is chosen by the user, reflects the relative importance between A and T. This paper derives lower and upper bounds on the area-time complexity for chips that implement binary arithmetic, assuming a model of computation which is intended to approximate, current and anticipated LSI or VLSI technology.

The concurrent manipulation of a binary search tree is considered in this paper. The systems presented can support any number of concurrent processes which perform searching, insertion, deletion, and rotation (reorganization) on the tree, but allow any process to lock only a constant number of nodes at any time. Also, in the systems, searches are essentially never blocked. The concurrency control techniques introduced in the paper include the use of special nodes and pointers to redirect searches, and the use of copies of sections of the tree to introduce many changes simultaneously and therefore avoid unpredictable interleaving. Methods developed in this paper may provide new insights into other problems in the area of concurrent database manipulation.

A concurrency control mechanism (or a scheduler) is the component of a database system that safeguards the consistency of the database in the presence of interleaved accesses and update requests. We formally show that the performance of a scheduler, i.e., the amount of parallelism that it supports, depends explicitly upon the amount of information that is available to the scheduler. We point out that most previous work on concurrency control is simply concerned with specific points of the base trade-off between performance and information. In fact, several of these approaches are shown to be optimal for the amount of information that they use. (Author)

A maximal vector of a set ~s one which is not less than any other vector m all components We derive a recurrence relation for computing the average number of maxunal vectors m a set of n vectors m d-space under the assumpUon that all (nl) a relative ordermgs are equally probable.Solving the recurrence shows that the average number of maxmaa is O((ln n) a-~) for fixed d We use this result to construct an algorithm for finding all the maxima that have expected running tmae hnear m n (for sets of vectors drawn under our assumptions) We then use the result to find an upper bound on the expected number of convex hull points m a random point set KE~ WORDS AND eHRASES maxtma of a set of vectors, average number of maxtma, expected-tsme algorithms, analysts of algorithms, convex hulls, dynamtc programming CR CATEGORIES" 5 25, 5.39, 5.42 Permtsston to copy without fee all or part of this material ts granted provtded that the copies are not made or distributed for direct commercial advantage, the ACM copyrtght notice and the tRle of the pubhcatlon and its date appear, and notice ts gtven that copying ts by permission of the Assoctatton for Computmg Machinery To copy otherwtse, or to repubhsh, reqmres a fee and/or specific permtsslon This research was supported m part by the Nattonal Soence Foundation under Grant MCS 75-222-55 and the Office of Naval Research under

The classical algorithms require order n ~ operations to compute the first n terms in the reversion of a power series or the composition of two series, and order nelog n operations if the fast Founer transform is used for power series multiplication In this paper we show that the composition and reversion problems are equivalent (up to constant factors), and we give algorithms which require only order (n log n) ~/2 operations In many cases of practical importance only order n log n operations are required, these include certain special functions of power series and power series solution of certain differential equations Applications to root-finding methods which use inverse mterpolauon and to queuemg theory are described, some results on multivariate power series are stated, and several open questions are mentioned KEY WORDS AND PHRASES formal power series, reversion of power series, composition of power series, computational complexity, fast algorithms, special functions of power series, power series solution of dlfferentml equations, queuetng theory, fast Fourier transform CRCATEGORIES 57,5 15,5 17 IntroductionWe are mterested m the complexity of algorithms for mampulatlng formal power series.For example, such algorithms may compute the first n terms in the product, quotient, or composition of two gwen power series.These problems arise in combmatorics and analysis of algorithms, where the desired power series is a generating function, as well as in numerical analysis.See, for example, Knuth [26], Ferguson, Nielsen, and Cook [14], Riordan [35], Gilbert [18], Nwen [31], Jackson and Reilly [25], Levy and Lessman [30], Norman [32], and Henrici [20, 21].Let ~ be the integral domain of formal power series P(s) = po + p~s + p2s 2 + over some field K "Formal" means that we are not concerned with questions of convergence.If F is a set of indetermmates over K, and E is a finite subset of the extension field K(F), then L(E mod F) denotes the number of operations necessary to compute E, starting from K U F and working in K(F).Informally, L(E rood F) is the number of operations required to compute E, given F. If A, B E @ and C is the formal product of A and B, we define M(n) = L(¢o ..... cn mod a0 ..... an, b0 ..... b,,) Informally, M(n) is the number of operations required to compute the

The expansions of algebraic functions can be computed "fast" using the Newton Polygon Process and any "normal" iteration Let M(I) be the number of operations sufficient to multiply two/thdegree polynomials It is shown that the first N terms of an expansion of any algebraic function defined by an nth-degree polynomial can be computed in O(nM(N)) operations, while the classical method needs O(N ~) operations Among the numerous apphcatlons of algebraic functions are symbolic mathematics and combinatorial analysis Reversion, reciprocation, and nth root of a polynomial are all special cases of algebraic functions

An efficient system to perform garbage collection in parallel with list operations is proposed and its correctness is proven. The system consists of two independent processes sharing a common memory. One process is performed by the list processor (LP) for list processing and the other by the garbage collector (GC) for marking active nodes and collecting garbage nodes. The system is derived by using both the correctness and efficiency arguments. Assuming that memory references are indivisible the system satisfies the following properties: No critical sections are needed in the entire system. The time to perform the marking phase by the GC is independent of the size of memory, but depends only on the number of active nodes. Nodes on the free list need not be marked during the marking phase by the GC. Minimum overheads are introduced to the LP. Only two extra bits for encoding four colors are needed for each node. Efficiency results show that the parallel system is usually significantly more efficient in terms of storage and time than the sequential stack algorithm. (Author)

The problem oI evaluatmgxn defined by the linear recurrence x, = x~-lb, + a,+l, t >-1, x0 = al, or equivalently evaluating the HorneT expression ( '(alb~ + a.o)bz + + a,,)b,, + a,,+~ is considered It is shown that by using an rdeahzed k-processor parallel computer the speedup for the problem is at most ~rk + rather than k The bound is essentially sharp

The partial fraction decomposition of a proper rational function whose denominator has degree n and is given in general factored form can be done in $O(n \log^{2}n)$ operations in the worst case. Previous algorithms require $O(n^{3})$ operations, and $O(n \log^{2}n)$ operations for the special case where the factors appearing in the denominator are all linear.

Two algorithms for sorting n2 elements on an n×n mesh-connected processor array that require 0(n) routing and comparison steps are presented. The best previous algorithms take time 0(n log n). Our algorithms are shown to be optimal in time within small constant factors.

The parallel evaluation of rational expressions is considered. New algorithms which minimize the number of multiplication or division steps are given. They are faster than the usual algorithms when multiplication or division takes more time than addition or subtraction. It is shown, for example, that x n can be evaluated in two steps of parallel division and ⌈log 2 n ⌉ steps of parallel addition, while the usual algorithm takes ⌈log 2 n ⌉ steps of parallel multiplication. Lower bounds on the time required are obtained in terms of the degree of the expressions to be evaluated. From these bounds, the algorithms presented in the paper are shown to be asymptotically optimal. Moreover, it is shown that by using parallelism the evaluation of any first-order rational recurrence of degree greater than 1, e.g. y i +1 = 1/2;( y i + a / y i ), and any nonlinear polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used and how large the size of the problem is.

The concept of computers such as C.mmp and ILLIAC IV is to achieve computational speed-up by performing several operations simultaneously with parallel processors. This type of computer organization is referred to as a parallel computer. In this paper, we prove upper bounds on speed-ups achievable by parallel computers for a particular problem, the solution of first order linear recurrences. We consider this problem because it is important in practice and also because it is simply stated so that we might obtain some insight into the nature of parallel computation by studying it.

ASSTRACT.Let U1 , U2, . . ., Ud be totally ordered sets and let V be a set of n d-dimensional vectors In U~ X Us. .X Ud .A partial ordering is defined on V in a natural way The problem of finding all maximal elements of V with respect to the partial ordering ~s considered The computational complexity of the problem is defined to be the number of required comparisons of two components and is denoted by Cd(n).It is tnwal that C~(n) = n -1 and C,~(n) < O(n 2) for d _~ 2 In this paper we show: ( 1) C2(n) = O(n logan) for d = 2, 3 and Cd(n) ~ O(n(log2n) ~-~) for d ~ 4, (2) C,t(n) >_ flog2 n!l for d _> 2 KEY WORDS AND PHRASES: maxima of a set of vectors, computattonal complexity, number of comparisons, algorithm, recurrence CR CATEaOmES.5.25, 5,31, 5.39 IntroductionLet U1, U2_, • • • , Ud be totally ordered sets and let V be a set of n d-dimensional vectors in the Cartesian product Ui X U2 X • • • X Ud.For any vector v in V, let x,(v) denote the zth component of v.A partial ordering < is defined on V in a natural way, that is, for v, u E V, v < u if and only if x,(v) <, x,(u) for all z = 1, ... , d, where _<, is the total ordering on U,. (We shall often write <_ for <,.The context should make clear the meaning of < .)For v C V, v is defined to be a maximal element (or, briefly, a maximum) of V if there does not exist u E V such that u ~ v and u ~ v.We consider the problem of finding all maximal elements of V.The computational complexity of the problem is defined to be Cd(n) = min max Ca(A, V),

Computer Science Department

The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2 n -1 which use n evaluations of ƒ and no derivative evaluations, as well as a second family of iterations of order 2 n -1 based on n — 1 evaluations of ƒ and one of ƒ′. In particular, with four evaluations an iteration of eighth order is constructed. The best previous result for four evaluations was fifth order. It is proved that the optimal order of one general class of multipoint iterations is 2 n -1 and that an upper bound on the order of a multipoint iteration based on n evaluations of ƒ (no derivatives) is 2 n . It is conjectured that a multipoint iteration without memory based on n evaluations has optimal order 2 n -1 .

Let {xi} be a sequence approximating an algebraic number α of degree r, and let [equation], for some rational function @@@@ with integral coefficients. Let M denote the number of multiplications or divisions needed to compute @@@@ and let M¯ denote the number of multiplications or divisions, except by constants, needed to compute @@@@. Define the multiplication efficiency measure of {xi} as [equation] or as [equation], where p is the order of convergence of {xi}. Kung [1] showed that Ē({xi}) ≤ 1 or equivalently, [equation]. In this paper we show that (i) [equation]; (ii) if E({xi}) = 1 then α is a rational number; (iii) if Ē({xi}) = 1 then α is a rational or quadratic irrational number. This settles the question of when the multiplication efficiency E({xi}) or Ē({xi}) achieves its optimal value of unity.

@(xi,x1,...,xi-d+1), define the multiplication efficiency measure E to be p1/M, where p is the order of convergence, and M is the number of multiplications or divisions (except by 2) needed to compute