Scheduling deep learning (DL) models to train on powerful clusters with accelerators like GPUs and TPUs, presently falls short, either lacking fine-grained heterogeneity awareness or leaving resources substantially under-utilized. To fill this gap, we propose a novel task-level heterogeneity-aware scheduler for DL clusters, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i>, based on an optimization framework able to boost cluster resource utilization. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i> leverages the performance traits of DL jobs on a heterogeneous DL cluster to make scheduling decisions across both spatial and temporal dimensions. It characterizes the task-level performance heterogeneity for optimization and involves the primal-dual framework employing a dual subroutine, to solve the optimization problem and guide the scheduling design. Our trace-driven simulation with representative DL model training workloads demonstrates that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i> accelerates the total training time duration by 1.20× when compared with its state-of-the-art heterogeneity-aware counterpart, Gavel. Further, our <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i> scheduler is enhanced to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i>E by forking each job into multiple copies to let a job train concurrently on heterogeneous GPUs resided on separate available cluster nodes (i.e., machines or servers) for resource utilization enhancement. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i>E is evaluated extensively on physical DL clusters for comparison with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i> and Gavel. With substantial enhancement in cluster resource utilization (by 1.45×), <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i>E exhibits considerable speed-ups in DL model training, reducing the total training time duration by 50% (or 80%) on an Amazon’s AWS (or our lab) cluster, while producing trained DL models with consistently better inference quality than those trained by <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Hadar</i>.

Federated Learning (FL) is a promising distributed machine learning framework that allows collaborative learning of a global model across decentralized devices without uploading their local data. However, in real-world FL scenarios, the conventional synchronous FL mechanism suffers from inefficient training caused by slow-speed devices, commonly known as stragglers, especially in heterogeneous communication environments. Though asynchronous FL effectively tackles the efficiency challenge, it induces substantial system overheads and model degradation. Striking for a balance, semi-asynchronous FL has gained increasing attention, while still suffering from the open challenge of stale models, where newly arrived updates are calculated based on outdated weights that easily hurt the convergence of the global model. In this paper, we present SEAFL, a novel FL framework designed to mitigate both the straggler and the stale model challenges in semi-asynchronous FL. SEAFL dynamically assigns weights to uploaded models during aggregation based on their staleness and importance to the current global model. We theoretically analyze the convergence rate of SEAFL and further enhance the training efficiency with an extended variant that allows partial training on slower devices, enabling them to contribute to global aggregation while reducing excessive waiting times. We evaluate the effectiveness of SEAFL through extensive experiments on three benchmark datasets. The experimental results demonstrate that SEAFL outperforms its closest counterpart by up to$\sim 22 \%$in terms of the wall-clock training time required to achieve target accuracy.

Graph neural networks (GNNs) have exhibited superior performance in various classification tasks on graph-structured data. However, they encounter the potential vulnerability from the link stealing attacks, which can infer the presence of a link between two nodes via measuring the similarity of its incident nodes' prediction vectors produced by a GNN model. Such attacks pose severe security and privacy threats to the training graph used in GNN models. In this work, we propose a novel solution, called Graph Link Disguise (GRID), to defend against link stealing attacks with the formal guarantee of GNN model utility for retaining prediction accuracy. The key idea of GRID is to add carefully crafted noises to the nodes' prediction vectors for disguising adjacent nodes as n-hop indirect neighboring nodes. We take into account the graph topology and select only a subset of nodes (called core nodes) covering all links for adding noises, which can avert the noises offset and have the further advantages of reducing both the distortion loss and the computation cost. Our crafted noises can ensure 1) the noisy prediction vectors of any two adjacent nodes have their similarity level like that of two non-adjacent nodes and 2) the model prediction is unchanged to ensure zero utility loss. Extensive experiments on five datasets are conducted to show the effectiveness of our proposed GRID solution against different representative link-stealing attacks under transductive settings and inductive settings respectively, as well as two influence-based attacks. Meanwhile, it achieves a much better privacy-utility trade-off than existing methods when extended to GNNs.

Accurate and timely regional weather prediction is vital for sectors dependent on weather-related decisions. Traditional prediction methods, based on atmospheric equations, often struggle with coarse temporal resolutions and inaccuracies. This article presents a novel machine learning (ML) model, called Micro-Macro (MiMa), that integrates both near-surface observational data from Kentucky Mesonet stations (collected every 5 min, known as Micro data) and hourly atmospheric numerical outputs (termed as Macro data) for fine-resolution weather forecasting. The MiMa model employs an encoder-decoder transformer structure, with two encoders for processing multivariate data from both datasets and a decoder for forecasting weather variables over short time horizons. Each instance of the MiMa model, called a modelet, predicts the values of a specific weather parameter at an individual mesonet station. The approach is extended with Regional MiMa (Re-MiMa) modelets, which are designed to predict weather variables at ungauged locations by training on multivariate data from a few representative stations in a region, tagged with their elevations. Re-MiMa can provide highly accurate predictions across an entire region, even in areas without observational stations. Experimental results show that MiMa significantly outperforms current models, with Re-MiMa offering precise short-term forecasts for ungauged locations, marking a significant advancement in weather forecasting accuracy and applicability.

Adversarial training (AT) can help improve the robustness of Vision Transformers (ViT) against adversarial attacks by intentionally injecting adversarial examples into the training data. However, this way of adversarial injection inevitably incurs standard accuracy degradation to some extent, thereby calling for a trade-off between standard accuracy and adversarial robustness. Besides, the prominent AT solutions are still vulnerable to adaptive attacks. To tackle such shortcomings, this paper proposes a novel ViT architecture, including a detector and a classifier bridged by our newly developed adaptive ensemble. Specifically, we empirically discover that detecting adversarial examples can benefit from the Guided Backpropagation technique. Driven by this discovery, a novel Multi-head Self-Attention (MSA) mechanism is introduced for enhancing our detector to sniff adversarial examples. Then, a classifier with two encoders is employed for extracting visual representations respectively from clean images and adversarial examples, with our adaptive ensemble to adaptively adjust the proportion of visual representations from the two encoders for accurate classification. This design enables our ViT architecture to achieve a better trade-off between standard accuracy and adversarial robustness. Besides, the adaptive ensemble technique allows us to mask off a random subset of image patches within input data, boosting our ViT's robustness against adaptive attacks, while maintaining high standard accuracy. Experimental results exhibit that our ViT architecture, on CIFAR-10, achieves the best standard accuracy and adversarial robustness of 90.3 % and 49.8 %, respectively.

In the current noisy intermediate-scale quantum (NISQ) Era, Quantum Computing faces significant challenges due to noise, which severely restricts the application of computing complex algorithms. Superconducting quantum chips, one of the pioneer quantum computation technologies, introduce additional noise when moving qubits to adjacent locations for operation on designated two-qubit gates. The current compilers rely on decision models that either count the swap gates or multiply the gate errors when choosing swap paths at the routing stage. Our research has unveiled the overlooked situations for error propagations through the circuit, leading to accumulations that may affect the final output.

Long Short-Term Memory (LSTM) deep neural networks are diverse in the tasks they can accomplish, such as image captioning and speech recognition. However, they remain susceptible to transient faults when deployed in environments with high-energy particles or radiation. It remains unknown how the potential transient faults will impact LSTM models. Therefore, we investigate the resilience of the weights and biases of these networks through four implementations of the original LSTM network. Based on the observations made through the fault injection of these networks, we propose an effective method of fault mitigation through Hamming encoding of selected weights and biases in a given network.

Federated learning (FL) is an emerging distributed machine learning paradigm that enables collaborative training of machine learning models over decentralized devices without exposing their local data. One of the major challenges in FL is the presence of uneven data distributions across client devices, violating the well-known assumption of independent-and-identically-distributed (IID) training samples in conventional machine learning. To address the performance degradation issue incurred by such data heterogeneity, clustered federated learning (CFL) shows its promise by grouping clients into separate learning clusters based on the similarity of their local data distributions. However, state-of-the-art CFL approaches require a large number of communication rounds to learn the distribution similarities during training until the formation of clusters is stabilized. Moreover, some of these algorithms heavily rely on a predefined number of clusters, thus limiting their flexibility and adaptability. In this paper, we propose FedClust, a novel approach for CFL that leverages the correlation between local model weights and the data distribution of clients. FedClust groups clients into clusters in a one-shot manner by measuring the similarity degrees among clients based on the strategically selected partial weights of locally trained models. We conduct extensive experiments on four benchmark datasets with different non-IID data settings. Experimental results demonstrate that FedClust achieves higher model accuracy up to ∼ 45% as well as faster convergence with a significantly reduced communication cost up to 2.7 × compared to its state-of-the-art counterparts.

With the wide adoption of deep neural network (DNN) models for various applications, enterprises, and cloud providers have built deep learning clusters and increasingly deployed specialized accelerators, such as GPUs and TPUs, for DNN training jobs. To arbitrate cluster resources among multi-user jobs, existing schedulers fall short, either lacking fine-grained heterogeneity awareness or hardly generalizable to various scheduling policies. To fill this gap, we propose a novel design of a task-level heterogeneity-aware scheduler, Hadar, based on an online optimization framework that can express other scheduling algorithms. Hadar leverages the performance traits of DNN jobs on a heterogeneous cluster, characterizes the task-level performance heterogeneity in the optimization problem, and makes scheduling decisions across both spatial and temporal dimensions. The primal-dual framework is employed, with our design of a dual subroutine, to solve the optimization problem and guide the scheduling design. Extensive trace-driven simulations with representative DNN models have been conducted to demonstrate that Hadar improves the average job completion time (JCT) by 3× over an Apache YARN-based resource manager used in production. Moreover, Hadar outperforms Gavel [1], the state-of-the-art heterogeneity-aware scheduler, by 2.5× for the average JCT, shortens the queuing delay by 13%, and improves FTF (Finish-Time-Fairness) by 1.5%.

Precise crop yield predictions are of national importance for ensuring food security and sustainable agricultural practices. While AI-for-science approaches have exhibited promising achievements in solving many scientific problems such as drug discovery, precipitation nowcasting, etc., the development of deep learning models for predicting crop yields is constantly hindered by the lack of an open and large-scale deep learning-ready dataset with multiple modalities to accommodate sufficient information. To remedy this, we introduce the CropNet dataset, the first terabyte-sized, publicly available, and multi-modal dataset specifically targeting climate change-aware crop yield predictions for the contiguous United States (U.S.) continent at the county level. Our CropNet dataset is composed of three modalities of data, i.e., Sentinel-2 Imagery, WRF-HRRR Computed Dataset, and USDA Crop Dataset, for over 2200 U.S. counties spanning 6 years (2017-2022), expected to facilitate researchers in developing versatile deep learning models for timely and precisely predicting crop yields at the county-level, by accounting for the effects of both short-term growing season weather variations and long-term climate change on crop yields. Besides, we develop the CropNet package, offering three types of APIs, for facilitating researchers in downloading the CropNet data on the fly over the time and region of interest, and flexibly building their deep learning models for accurate crop yield predictions. Extensive experiments have been conducted on our CropNet dataset via employing various types of deep learning solutions, with the results validating the general applicability and the efficacy of the CropNet dataset in climate change-aware crop yield predictions. We have officially released our CropNet dataset on Hugging Face Datasets https://huggingface.co/datasets/CropNet/CropNet and our CropNet package on the Python Package Index (PyPI) https://pypi.org/project/cropnet. Code and tutorials are available at https://github.com/fudong03/CropNet.

The increasing prevalence of smart devices spurs the development of emerging indoor localization technologies for supporting diverse personalized applications at home. Given marked drawbacks of popular chirp signal-based approaches, we aim at developing a novel device-free localization system via the continuous wave of the inaudible frequency. To achieve this goal, solutions are developed for fine-grained analyses, able to precisely locate moving human traces in the room-scale environment. In particular, a smart speaker is controlled to emit continuous waves at inaudible 20kHz , with a co-located microphone array to record their Doppler reflections for localization. We first develop solutions to remove potential noises and then propose a novel idea by slicing signals into a set of narrowband signals, each of which is likely to include at most one body segment’s reflection. Different from previous studies, which take original signals themselves as the baseband, our solutions employ the Doppler frequency of a narrowband signal to estimate the velocity first and apply it to get the accurate baseband frequency, which permits a precise phase measurement after I-Q (i.e., in-phase and quadrature) decomposition. A signal model is then developed, able to formulate the phase with body segment’s velocity, range, and angle. We next develop novel solutions to estimate the motion state in each narrowband signal, cluster the motion states for different body segments corresponding to the same person, and locate the moving traces while mitigating multi-path effects. Our system is implemented with commodity devices in room environments for performance evaluation. The experimental results exhibit that our system can conduct effective localization for up to three persons in a room, with the average errors of 7.49 cm for a single person, with 24.06 cm for two persons, with 51.15 cm for three persons.

Semi-supervised learning, which learns with only a small amount of labeled data while collecting voluminous unlabeled data to aid its training, has achieved promising performance lately, but it also raises a serious privacy concern: Whether a user’s data has been collected for use without authorization. In this paper, we propose a novel membership inference method against semi-supervised learning, serving to protect user data privacy. Due to involving both the labeled and unlabeled data, the membership patterns of semi-supervised learning’s training data cannot be well captured by the existing membership inference solutions. To this end, we propose two new metrics, i.e., inter-consistency and intra-entropy, tailored specifically to the semi-supervised learning paradigm, able to respectively measure the similarity and calculate the cross-entropy among prediction vectors from the perturbed versions. By exploiting the two metrics for membership inference, our method can dig out membership patterns imprinted on prediction outputs of semi-supervised learning models, thus facilitating effective membership inference. Extensive experiments have been conducted for comparing our method with five rectified baseline inference techniques across four datasets on six semi-supervised learning algorithms. Experimental results exhibit that our inference method achieves over 80% accuracy under each experimental setting, substantially outperforming all baseline techniques.

Quantum computers in the current noisy intermediate-scale quantum (NISQ) era face two major limitations - size and error vulnerability. Although quantum error correction (QEC) methods exist, they are not applicable at the current size of computers, requiring thousands of qubits, while NISQ systems have nearly one hundred at most. One common approach to improve reliability is to adjust the compilation process to create a more reliable final circuit, where the two most critical compilation decisions are the qubit allocation and qubit routing problems. We focus on solving the qubit allocation problem and identifying initial layouts that result in a reduction of error. To identify these layouts, we combine reinforcement learning with a graph neural network (GNN)-based Q-network to process the mesh topology of the quantum computer, known as the backend, and make mapping decisions, creating a Graph Neural Network Assisted Quantum Compilation (GNAQC) strategy. We train the architecture using a set of four backends and six circuits and find that GNAQC improves output fidelity by roughly 12.7% over pre-existing allocation methods.

Precise crop yield prediction provides valuable information for agricultural planning and decision-making processes. However, timely predicting crop yields remains challenging as crop growth is sensitive to growing season weather variation and climate change. In this work, we develop a deep learning-based solution, namely Multi-Modal Spatial-Temporal Vision Transformer (MMST-ViT), for predicting crop yields at the county level across the United States, by considering the effects of short-term meteorological variations during the growing season and the long-term climate change on crops. Specifically, our MMST-ViT consists of a Multi-Modal Transformer, a Spatial Transformer, and a Temporal Transformer. The Multi-Modal Transformer leverages both visual remote sensing data and short-term meteorological data for modeling the effect of growing season weather variations on crop growth. The Spatial Transformer learns the high-resolution spatial dependency among counties for accurate agricultural tracking. The Temporal Transformer captures the long-range temporal dependency for learning the impact of long-term climate change on crops. Meanwhile, we also devise a novel multi-modal contrastive learning technique to pre-train our model without extensive human supervision. Hence, our MMST-ViT captures the impacts of both short-term weather variations and long-term climate change on crops by leveraging both satellite images and meteorological data. We have conducted extensive experiments on over 200 counties in the United States, with the experimental results exhibiting that our MMST-ViT outperforms its counterparts under three performance metrics of interest. Our dataset and code are available at https://github.com/fudong03/MMST-ViT.

The proliferation of IoT devices, with various capabilities in sensing, monitoring, and controlling, has prompted diverse emerging applications, highly relying on effective delivery of sensitive information gathered at edge devices to remote controllers for timely responses. To effectively deliver such information/status updates, this paper undertakes a holistic study of AoI in multi-hop networks by considering the relevant and realistic factors, aiming for optimizing information freshness by rapidly shipping sensitive updates captured at a source to its destination. In particular, we consider the multi-channel with OFDM (orthogonal frequency-division multiplexing) spectrum access in multi-hop networks and develop a rigorous mathematical model to optimize AoI at destination nodes. Real-world factors, including orthogonal channel access, wireless interference, and queuing model, are taken into account for the very first time to explore their impacts on the AoI. To this end, we propose two effective algorithms where the first one approximates the optimal solution as closely as we desire while the second one has polynomial time complexity, with a guaranteed performance gap to the optimal solution. The developed model and algorithms enable in-depth studies on AoI optimization problems in OFDM-based multi-hop wireless networks. Numerical results demonstrate that our solutions enjoy better AoI performance and that AoI is affected markedly by those realistic factors taken into our consideration.

While deep generative models pave the way for many emerging applications, decreased interpretability for larger model sizes and complexities hinders their generalizability to wide domains such as economy, security, healthcare, etc. Considering this obstacle, a common practice is to learn interpretable representations through latent feature disentanglement, aiming for exposing a set of mutually independent factors of data variations. However, existing methods either fail to catch the trade-off between the synthetic data quality and model interpretability, or consider the first-order feature disentangling only, overlooking the fact that a subset of salient features can carry decomposable semantic meanings and hence be of high-order in nature. Hence, we in this paper propose a novel generative modeling paradigm by introducing a Bayesian network-based regularize on a cascade Variational Auto-Encoder (VAE). Specifically, this regularizer guides the learner to discover a representation space that comprises both first-order disentangled features and high-order salient features, with the feature interplay captured by the Bayesian structure. Experiments demonstrate that this regularizer gives us free control over the representation space and can guide the learner to discover decomposable semantic meanings by capturing the interplay among independent factors. Meanwhile, we benchmark extensive experiments on six widely-used vision datasets, and the results exhibit that our approach outperforms the state-of-the-art VAE competitors in terms of the trade-off between the synthetic data quality and model interpretability. Although our design is framed in the VAE regime, it in effect is generic and can be better amenable to both GANs and VAEs in terms of letting them concurrently enjoy both high model interpretability and high synthesis quality.

With the growing effort to reduce power consumption in machines, fault tolerance becomes more of a concern. This holds particularly for large-scale computing, where execution failures due to soft faults waste excessive time and resources. These large-scale applications are normally parallel in nature and rely on control structures tailored specifically for parallel computing, such as locks and barriers. While there are many studies on resilient software, to our knowledge none of them focus on protecting these parallel control structures. In this work, we present a method of ensuring the correct operation of both locks and barriers in parallel applications. Our method tracks the memory locations used within parallel sections and detects a violation of the control structures. Upon detecting any violation, the violating thread is rolled back to the beginning of the structure and reattempts it, similar to rollback mechanisms in transactional memory systems. We test the method on representative samples of the BigDataBench kernels and find it exhibits a mean error reduction of 93.6% for basic mutex locks and barriers with a mean 6.55% execution time overhead at 64 threads. Additionally, we provide a comparison to transactional memory methods and demonstrate up to a mean 57.5% execution time overhead reduction.

This paper addresses a novel anti-spam gateway targeting multiple linguistic-based social platforms to expose the outlier property of their spam messages uniformly for effective detection. Instead of labeling ground truth datasets and extracting key features, which are labor-intensive and time-consuming, we start with coarsely mining seed corpora of spams and hams from the target data (aiming for spam classification), before reconstructing them as the reference. To catch each word’s rich information in the semantic and syntactic perspectives, we then leverage the natural language processing (NLP) model to embed each word into the high-dimensional vector space and use a neural network to train a spam word model. After that, each message is encoded by using the predicted spam scores from this model for all included stem words. The encoded messages are processed by the prominent outlier techniques to produce their respective scores, allowing us to rank them for making the outlier visible. Our solution is unsupervised, without relying on specifics of any platform or dataset, to be platform-oblivious. Through extensive experiments, our solution is demonstrated to expose spammers’ outlier characteristics effectively, outperform all examined unsupervised methods in almost all metrics, and may even better supervised counterparts.

Collaborative filtering (CF) recommender systems have been extensively developed and widely deployed in various social websites, promoting products or services to the users of interest. Meanwhile, work has been attempted at poisoning attacks to CF recommender systems for distorting the recommend results to reap commercial or personal gains stealthily. While existing poisoning attacks have demonstrated their effectiveness with the offline social datasets, they are impractical when applied to the real setting on online social websites. This paper develops a novel and practical poisoning attack solution toward the CF recommender systems without knowing involved specific algorithms nor historical social data information a priori. Instead of directly attacking the unknown recommender systems, our solution performs certain operations on the social websites to collect a set of sampling data for use in constructing a surrogate model for deeply learning the inherent recommendation patterns. This surrogate model can estimate the item proximities, learned by the recommender systems. By attacking the surrogate model, the corresponding solutions (for availability and target attacks) can be directly migrated to attack the original recommender systems. Extensive experiments validate the generated surrogate model's reproductive capability and demonstrate the effectiveness of our attack upon various CF recommender algorithms.

This paper proposes a novel oversampling approach that strives to balance the class priors with a considerably imbalanced data distribution of high dimensionality. The crux of our approach lies in learning interpretable latent representations that can model the synthetic mechanism of the minority samples by using a generative adversarial network(GAN). A Bayesian regularizer is imposed to guide the GAN to extract a set of salient features that are either disentangled or intensionally entangled, with their interplay controlled by a prescribed structure, defined with human-in-the-loop. As such, our GAN enjoys an improved sample complexity, being able to synthesize high-quality minority samples even if the sizes of minority classes are extremely small during training. Empirical studies substantiate that our approach can empower simple classifiers to achieve superior imbalanced classification performance over the state-of-the-art competitors and is robust across various imbalance settings. Code is released in github.com/fudonglin/IMSIC.

Recent graphic processing units (GPUs) often come with large on-board physical memory to accelerate diverse parallel program executions on big datasets with regular access patterns, including machine learning (ML) and data mining (DM). Such a GPU may underutilize its physical memory during lengthy ML model training or DM, making it possible to lend otherwise unused GPU memory to applications executed concurrently on the host machine. This work explores an effective approach that lets memory-intensive applications run on the host machine CPU with its memory expanded dynamically onto available GPU on-board DRAM, called GPU-assisted memory expansion (GAME). Targeting computer systems equipped with the recent GPUs, our GAME approach permits speedy executions on CPU with large memory footprints by harvesting unused GPU on-board memory on-demand for swapping, far surpassing competitive GPU executions. Implemented in user space, our GAME prototype lets GPU memory house swapped-out memory pages transparently, without code modifications for high usability and portability. The evaluation of NAS-NPB benchmark applications demonstrates that GAME expedites monotasking (or multitasking) executions considerably by up to 2.1× (or 3.1×), when memory footprints exceed the CPU DRAM size and an equipped GPU has unused VDRAM available for swapping use.

While considerable work has addressed the optimal AoI under different circumstances in single-hop networks, the exploration of AoI in multi-hop wireless networks is rarely attempted. More importantly, the inherent relationships between AoI and throughput are yet to be explored, especially in multi-hop networks. This paper studies AoI in multi-hop wireless networks and explores its potential relationships with throughput for the very first time, particularly focusing on the impacts of flexible routes on the two metrics, i.e., AoI and throughput. By developing a rigorous mathematical model with interference, channel allocation, link scheduling, and routing path selection taken into consideration, we build the interrelation between AoI and throughput in multi-hop networks. A multi-criteria optimization problem is formulated with the goal of simultaneously minimizing AoI and maximizing network throughput. By qualitatively analyzing their relationships, we exhibit that the two metrics may conflict with each other, implying the optimal solutions for the multi-criteria problem will include a set of Pareto-optimal points rather than a single point existing in the traditional optimization problem. We resort to a novel approach by transforming the multi-criteria problem into a single objective one so as to find the weakly Pareto-optimal points iteratively, thereby allowing us to screen all Pareto-optimal points for the solution. Through formal proof, our solution is demonstrated to be able to identify all Pareto-optimal points and terminate in a finite number of iterations. We conduct the simulation evaluation to identify the optimal tradeoff points of AoI and throughput, demonstrating that one performance metric may improve at the expense of degrading the other, with the routing path found as one of the key factors in determining such a tradeoff.

This article considers best checkpointing control realizable in real-world systems, whose mean time between failures (MTBFs) often fluctuate. The considered control scheme is based on equating aggregate checkpointing overhead over an activity sequence of interest (θ) and the expected rework amount after a failure recovery for best checkpointing, called “CHORE” (i.e., checkpointing overhead and rework equated), where θ starts from execution resumption after failure recovery and ends after restore from the following failure. CHORE lets its inter-checkpoint intervals in θ follow a pre-determined sequence independent of MTBF to aim at performance optimality and is shown analytically to keep overall execution time overhead upper bounded. When failure occurrences are tracked during job execution for real-time MTBF estimation, an enhanced CHORE (dubbed En-CHORE) is obtained to lower checkpointing overhead by skipping certain checkpoints at the beginning of each θ before taking checkpoints with the most desirable inter-checkpoint intervals determined on-the-fly for best checkpointing control. En-CHORE can outperform optimal checkpointing (which follows a fixed inter-checkpoint interval optimized for one constant global MTBF known a prior) both under synthetic random failures with local MTBF fluctuating markedly and under real failure traces of 22 real HPC systems (whose failure rates actually fluctuate over their trace time spans).

Deep neural networks trained on millions of instances can recognize a wide variety of patterns. It is common to use these pre-trained deep networks in applications where the domain specific training data is not readily available. Once a pre-trained network is deployed to such applications, some of the information contained in the network may be irrelevant due to the difference between the training set and the application data distributions. As a result, parts of the neural network become redundant and slow down inference. This redundancy is unknown until the model is deployed and input data is received. Therefore, it can only be identified and avoided in real-time. Existing works on neural network acceleration can not exploit such redundancy during offline training when the domain-specific datasets are unavailable. In this paper, we study online learning to accelerate neural network inference. We propose traveling classifiers that continuously learn from the activations of two consecutive network layers to accelerate inference in real-time. Traveling classifiers model class conditional probabilities to generate early predictions and bypass unnecessary computation of network layers. The classifiers also adaptively switch the layers they learn from by measuring the feature space differences between the activations. This traveling mechanism automatically adjusts the aggressiveness of the acceleration without sacrificing prediction accuracy. We demonstrate the performance of the proposed algorithm on the ImageNet dataset [10] using the state-of-the-art ResNet-50, ResNet-152 [18] and VGG-16 [38] architectures. Experiments demonstrate that our method significantly outperforms baseline approaches.

Predictive modeling of networked data finds many real-world applications, such as fraud detection in social networks, drug discovery in biomedical networks, paper topic classification in citation networks, and so forth. Although the advanced machine learning approaches can help build reasonably accurate predictive models, their applicability is immensely hindered by the data labeling tasks, which are onerous, time-consuming, and error-prone. In this paper, we propose a novel active learning paradigm for networked data, named topology-and-content-aware (TACA) active learning, aiming to minimize the number of labels while achieving a desirable level of model accuracy. Overall, TACA advances existing works from two aspects: (1) TACA makes no assumption on the network property, whereas most existing works only perform effectively on a locally consistent network in which linked nodes are expected to share the same labels and (2) TACA generates queries without relying on model performance, thereby enjoying robust predictive results even when noises exist in the queried labels. Both theoretical and empirical evidences are presented, substantiating the effectiveness of and optimism our approach.

Learning interpretable representations in an unsupervised setting is an important yet a challenging task. Existing unsupervised interpretable methods focus on extracting independent salient features from data. However they miss out the fact that the entanglement of salient features may also be informative. Acknowledging these entanglements can improve the interpretability, resulting in extraction of higher quality and a wider variety of salient features. In this paper, we propose a new method to enable Generative Adversarial Networks (GANs) to discover salient features that may be entangled in an informative manner, instead of extracting only disentangled features. Specifically, we propose a regularizer to punish the disagreement between the extracted feature interactions and a given dependency structure while training. We model these interactions using a Bayesian network, estimate the maximum likelihood parameters and calculate a negative likelihood score to measure the disagreement. Upon qualitatively and quantitatively evaluating the proposed method using both synthetic and real-world datasets, we show that our proposed regularizer guides GANs to learn representations with disentanglement scores competing with the state-of-the-art, while extracting a wider variety of salient features.

The Age-of-Information (AoI) is a newly introduced metric for capturing information updating timeliness, as opposed to the network throughput, which is a conventional performance metric to measure the network transmission speed and robustness as a whole. While considerable work has addressed either optimal AoI or throughput individually, the inherent relationships between the two performance metrics are yet to be explored, especially in multi-hop networks. In this paper, we explore their relationships in multi-hop networks for the very first time, particularly focusing on the impacts of flexible routes on the two metrics. By developing a rigorous mathematical model with interference, channel allocation, link scheduling, and routing path selection taken into consideration, we build the interrelation between AoI and throughput in multi-hop networks. A multi-criteria optimization problem is formulated with the goal of simultaneously minimizing AoI and maximizing network throughput. To solve this problem, we resort to a novel approach by transforming the multi-criteria problem into a single objective one so as to find the weakly Pareto-optimal points iteratively, thereby allowing us to screen all Pareto-optimal points for the solution. A new algorithm based on the piece-wise linearization technique is then developed to closely linearize the non-linear terms in the single objective problem via their linear approximation segments to make it solvable. We formally prove that our algorithms can find all Pareto-optimal points in a finite number of iterations. From simulation results, we identify the tradeoff points of the optimal AoI and throughput, demonstrating that one performance metric improves at the expense of degrading the other, with the routing path found as one of the key factors in determining such a tradeoff.

This paper studies the freshness of data delivery, measured by the recently proposed Age of Information (AoI) metric, in Internet of Things (IoT) networks. Given IoT networks with plenty of edge devices to upload their sealed packets, re-packing multiple packets into one at each sink node by removing redundant packet headers could significantly improve transmission efficiency. We investigate such packet combination behaviors in transmitting the monitored/collected data from sensing nodes to accelerate data delivery, enabling the IoT edge server to acquire the latest updates timely. Two data acquisition modes, i.e., Periodic Request and Proactive Request, at the IoT edge server are considered. Under each mode, we derive the AoI formula, develop mathematical modeling, formulate the problem, and propose a low-complexity scheduling algorithm by leveraging packet combination with an aim to minimize the Instant AoI at the edge server. Through numerical results, we demonstrate the advantages of packet combination behaviors for AoI performance improvement.

A bufferless network-on-chip (NoC) can deliver high energy efficiency, but such a NoC is subject to growing deflection when its traffic load rises. This article proposes Deflection Containment (DeC) for the bufferless NoC to address its notorious shortcomings of excessive deflection for performance improvement and energy savings. With multiple subnetworks bridged by an added link between two corresponding routers, DeC lets a contending flit in one subnetwork be forwarded to another subnetwork instead of deflected. Microarchitecture of DeC routers is rectified to shorten the critical path and lift network bandwidth. Its Cadence RTL implementations with a 15 - nm process are conducted respectively for mesh-based NoCs and torus-based NoCs. Additionally, different sized DeC-NoCs are evaluated extensively and compared with previous bufferless designs (BLESS and MinBD), uncovering that DeC with two bridged subnetworks (dubbed DeC2) for 8×8 mesh-based NoCs can lower deflection drastically by some 90 percent and energy consumption by upto 51 percent under real benchmark traffic loads, in comparison to BLESS. Under various synthetic traffic models and workloads, 16×16 torus-based DeC2-NoC sustains up to 2.33× loads when compared with its mesh-based counterpart, exhibiting the same clock rate and taking only negligible more power and area according to our full layout results.

The growing popularity of in-memory computing for bigdata analytics often causes performance bottlenecks to memory subsystem resided in operating systems (OS). This article purposes cooperative memory expansion (COMEX), an OS kernel extension. COMEX establishes a stable pool of memory collectively across nodes in a cluster and enhances OS's memory subsystem for memory aggregation from connected machines by allowing process's page table to track remote memory page frames without programmer effort or modifications to application codes. COMEX employs Remote Direct Memory Access (RDMA) for low-latency data transfer with destination kernel bypassed and does not rely on an old design of the I/O block subsystem usually adopted by all known remote paging. COMEX fits soundly in the emerging system design approach of resource disaggregation which breaks hard walls between server-centric machines into a new design paradigm of separated resource pools. The new architecture facilitates both system scaling-up and scaling-out, also eliminates imbalance resources existing in datacenters. We have implemented COMEX based on Linux kernel 3.10.87 and deployed on our 32 networked servers. Performance evaluation results under ten applications from two benchmark suites reveal the speedup of up to 170 times when application execution footprints are 10 times larger than available system memory.

The spammers have been grossly detrimental since the inception of Twitter social networks and keep polluting social environments by hiding themselves among a large amount of normal users. In this paper, we aim to address two challenges existing in the spammer detection problem: 1) monitoring tweets that have a higher probability of including spam messages; 2) providing an accurate solution for spam classification. To address these two challenges, we first propose a pseudo-honeypot framework for efficient tweets monitoring and collection. By taking advantage of users' diversity and selecting normal users as the parasitic body, the pseudo-honeypot can harness normal users with features having much more potentials of attracting spammers. This lets the pseudo-honeypot collect tweets that are far more likely to include spam messages. Furthermore, we design a novel spam classification solution called TweetScore by exploring both the intrinsic attributes' and users' relationships in social networks. TweetScore quantifies such relationships into a vector of numerical values to represent each tweet's score, reflecting the associated user's behaviors. The neural network is then employed to take these vectors as input to classify spams and spammers. Through extensive experiments, we demonstrate the efficiency of the pseudo-honeypot system on spam monitoring and the accuracy of TweetScore on spam classification. Specifically, the spam and spammer ratios collected by our pseudo-honeypot system are four times as much as those of a non pseudo-honeypot counterpart while the TweetScore can achieve, on an average, 93.5% accuracy, 93.71% precision, and 1.52% false positive in online spam classification.

Honeypot-based spammer gathering solutions usually lack attribute variability, deployment flexibility, and network scalability, deemed as their common drawbacks. This paper explores pseudo-honeypot, a novel honeypot-like system to overcome such drawbacks, for efficient and scalable spammer sniffing. The pseudo-honeypot takes advantage of user diversity and selects normal accounts, with attributes that have the higher potential of attracting spammers, as the parasitic bodies. By harnessing such category of users, pseudo-honeypot can monitor their streaming posts and behavioral patterns transparently. When compared with its traditional honeypot counterpart, the proposed solution offers the substantial advantages of attribute variability, deployment flexibility, network scalability, and system portability. Meanwhile, it offers a novel method to collect the social network dataset that has a higher probability of including spams and spammers, without being noticed by advanced spammers. We take the Twitter social network as an example to exhibit its system design, including pseudo-honeypot nodes selection, monitoring, feature extraction, ground truth labeling, and learning-based classification. Through experiments, we demonstrate the efficiency of pseudo-honeypot in terms of spams and spammers gathering. In particular, we confirm our solution can garner spammers at least 19 times faster than the state-of-the-art honeypot-based counterpart.

Chip multiprocessors (CMPs) involve directory storage overhead if cache coherence is realized via sharer tracking. This work proposes a novel framework dubbed non-uniform directory architecture (NUDA), by leveraging our two insights in that the number of “active” directory entries required to stay on chip is usually small for a short execution time window due to high directory locality, and that the fraction of interrogated directory entries drops as the core count rises. Unlike earlier storage overhead reduction techniques that require all cached LLC blocks to have their directory entries fully on chip, NUDA dynamically buffers only most active directory vectors (DVs) on chip while keeping DVs of all LLC blocks in a backing store at low level storage. NUDA attains its superior efficiency via an inventive criticality-aware replacement policy (CARP) for on-chip buffer management and effective prefetching to pre-activate vectors (PAVE) for upcoming coherence interrogations. We have evaluated NUDA by gem5 simulation for 64-core CMPs under PARSEC and SPLASH benchmarks, demonstrating that CARP and PAVE enhance on-chip directory storage efficiency significantly. NUDA with a small on-chip buffer for DVs exhibits negligible performance degradation (to stay within 2.6 percent) compared to a full on-chip directory, while outperforming its previous counterparts for directory area reduction when on-chip directory budget is provisioned scarcely for high scalability.

Video streams, either in the form of Video On-Demand (VOD) or live streaming, usually have to be converted (i.e., transcoded) to match the characteristics of viewers' devices (e.g., in terms of spatial resolution or supported formats). Transcoding is a computationally expensive and time-consuming operation. Therefore, streaming service providers have to store numerous transcoded versions of a given video to serve various display devices. With the sharp increase in video streaming, however, this approach is becoming cost-prohibitive. Given the fact that viewers' access pattern to video streams follows a long tail distribution, for the video streams with low access rate, we propose to transcode them in an on-demand (i.e., lazy) manner using cloud computing services. The challenge in utilizing cloud services for on-demand video transcoding, however, is to maintain a robust QoS for viewers and cost-efficiency for streaming service providers. To address this challenge, in this paper, we present the Cloud-based Video Streaming Services (CVS2) architecture. It includes a QoS-aware scheduling component that maps transcoding tasks to the Virtual Machines (VMs) by considering the affinity of the transcoding tasks with the allocated heterogeneous VMs. To maintain robustness in the presence of varying streaming requests, the architecture includes a cost-efficient VM Provisioner component. The component provides a self-configurable cluster of heterogeneous VMs. The cluster is reconfigured dynamically to maintain the maximum affinity with the arriving workload. Simulation results obtained under diverse workload conditions demonstrate that CVS2 architecture can maintain a robust QoS for viewers while reducing the incurred cost of the streaming service provider by up to 85 percent.

In multicore systems, a large portion of checkpoint time overhead can be hidden from the execution critical path by resorting to a dedicated checkpointing thread run concurrently with regular execution threads for compressing checkpoint files to lower checkpointing overhead. On the other hand, the restore time is on the critical path that cannot be hidden, making it most important to accelerate execution restore upon failures. This work pursues a restore-express (REX) strategy for multi-level checkpointing (MLC), applicable to any incremental checkpointing (IC). Oblivious to application codes, REX employs adaptive IC (AIC) for local (L1) checkpointing and follows our runtime control for second-level (L2) checkpointing, with its aim at express restore from failures while holding down the overall execution time. It takes advantage of two unique insights for overhead reduction: (1) the modified pages of an incremental checkpoint file are likely to exist in a subsequent checkpoint file, and (2) many data patterns (on an average, some 40 percent of them) stay unchanged from one L2 checkpoint file to the next. These insights enable REX to (1) coalesce IC files (by involving only the last copy of every dirty page among files) and (2) boost file compression across multiple L2 checkpoints. Time and storage overhead results of REX during normal job execution are gathered for 16 benchmarks from SPEC, PARSEC, and NPB suites. The evaluation outcomes of the execution restore time confirm that REX is fast and able to quicken restore by a factor of 4.5× when compared with its IC counterpart (without utilizing the unique insights), while incurring same execution time overhead.

Modern chip multiprocessors (CMPs) employ on-chip networks to enable communication between the individual cores. Operations such as coherence and synchronization generate a significant amount of the on-chip network traffic, and often create network requests that have one-to-many (i.e., a core multicasting a message to several cores) or many-to-one (i.e., several cores sending the same message to a common hotspot destination core) flows. As the number of cores in a CMP increases, one-to-many and many-to-one flows result in greater congestion on the network. To alleviate this congestion, prior work provides hardware support for efficient one-to-many and many-to-one flows in buffered on-chip networks. Unfortunately, this hardware support cannot be used in bufferless on-chip networks, which are shown to have lower hardware complexity and higher energy efficiency than buffered networks, and thus are likely a good fit for large-scale CMPs.

To lower on-chip SRAM area overhead for chip multiprocessors (CMPs), this work treats a novel directory design which compresses present-bit vectors (PVs) by dropping “runs of zeros” commonly existing and lets PVs be transformed to their variations after sharer relinquishment for hashing alternative table sets to lift table utilization. Featured with relinquishment coherence and compressed sharer tracking (ReCoST), the proposed design attains superior directory efficiency and maintains “exact” directory representations, as a result of dropping abound long runs of zeros present in PVs. According to full-system simulation using gem5 for a range of core counts under PARSEC benchmarks, ReCoST is found to enjoy 3.21χ (or 2.64χ) more efficiency in directory storage than conventional bit-tracking directories (or the best directory known so far, called SCD) for a 64-core CMP under monotasking (or multitasking) workloads while ensuring execution slowdowns to stay within 2.4 percent (or 3.3 percent).

A directory-based chip multiprocessor (CMP) suffers from excessive directory area overhead when its size grows. This work leverages novel relinquishment coherence and superior directory efficiency (RECODE) to lower area overhead. Relinquishment coherence boosts the utilization of a hash-based, set-associative table which holds distinct present-bit vectors (PVs), as it transforms a conflict PV to its variations after sharer relinquishment for hashing alternative sets. Superior directory efficiency is resulted from both boosted table utilization and table width shrunk via dropping “runs of zeros” commonly found in PVs. RECODE Table utilization is elevated by relinquishment coherence, which transforms a conflict PV to its variations after sharer relinquishment for hashing alternative sets. RECODE maintains “exact” directory representations for simple coherent logics and low coherent traffic. RECODE is found to enjoy 3.21× more storage efficiency than conventional bit-tracking directories for a CMP with 64 cores and it is 2.64× more storage efficient than the best directory SCD known so far.

In a network-on-chip (NoC) based system, the NoC is a shared resource among multiple processor cores. Network requests generated by different applications running on different cores can interfere with each other, leading to a slowdown in performance of each application. The degree of slowdown introduced by this interference varies for each application, as it depends on (1) the sensitivity of the application to NoC performance, and (2) network traffic induced by other applications running concurrently on the system. In modern systems, NoC interference is largely uncontrolled, and therefore some applications unfairly slow down much more than others. This can lead to overall system performance degradation, prevent fair progress of different applications, and cause starvation of unfairly-treated applications. Our goal is to accurately model the slowdown of each application executing on the system due to NoC interference at runtime, and to use this information to improve system performance and reduce unfairness. To this end, we propose the NoC Application Slowdown (NAS) Model, the first online model that accurately estimates how much network delays due to interference contribute to the overall stall time of each application. The key idea of NAS is to determine how the delays induced at each level of network data transmission overlap with each other, and to use the overlap information to calculate the net impact of the delays on application stall time. Our model determines the application slowdowns at runtime with a very low error rate, averaging 4.2% over 90 multiprogrammed workloads for an 8×8 mesh network. We use NAS to develop Fairness-Aware Source Throttling (FAST), a mechanism that employs slowdown predictions to control the network injection rates of applications in a way that minimizes system unfairness. Our results over a variety of multiprogrammed workloads show that FAST improves average system fairness and performance by 9.5% and 5.2%, respectively.

Without buffers in its constituent routers to reduce power consumption and hardware complexity, the bufferless network-on-chip (NoC) is subject to growing deflection when the traffic load rises, leading to severe performance degradation and squandering the power-saving potential as well. This work proposes Deflection Containment (DeC) for the bufferless NoC to address its notorious shortcoming of excessive deflection for performance improvement and power reduction. With a link added to each router for bridging subnetworks (whose aggregated link width equals a given value, say, 128b), DeC lets a contending flit in one subnetwork be forwarded to another subnetwork instead of deflected, yielding extraordinary deflection reduction and greatly enriching path diversity. In addition, router microarchitecture under DeC is rectified to shorten the critical path and lift network bandwidth. We evaluate the proposed DeC design using multiprogrammed SPEC CPU2006 benchmarks and various synthetic traffic loads, for 4×4, 8×8, and 16×16 mesh-based NoCs. The results reveal that DeC comprising two bridged subnetworks can substantially contain deflection by up to 75%, yielding network power reduction by 60% and the weighted speedup of 28% averaged across all experiments.

Cloud computing users are most concerned about the application turnaround time and the monetary cost involved. For lower monetary costs, less expensive services, like spot instances offered by Amazon, are often made available, albeit to their relatively frequent resource unavailability that leads to on-going execution being evicted, thereby undercutting execution performance. Meanwhile, multithreaded applications may take advantage of elastic resource availability and cost fluctuation inherent to the systems. However, their potential gains on utilizing spot instances would be contingent upon how they handle resource unavailability, calling for an effective checkpointing. This work presents design and implementation of our enhanced adaptive incremental checkpointing (EAIC) for multithreaded applications on the RaaS clouds under spot instance pricing. EAIC model takes into account spot instance revocation events, besides hardware failures, for fast and accurately predicting the desirable points of time to take checkpoints so as to markedly reduce the expected job turnaround time and the monetary cost. The experimental results from our established test bed on PARSEC benchmarks under real spot instance price traces from Amazon EC2 show that EAIC lowers both the application turnaround time and the monetary cost markedly (by up to 58% and 59%, respectively) in comparison to its recent checkpointing counterpart.

Multithreaded applications are common in high performance cloud computing systems, able to take advantage of elastic resource availability and cost fluctuation inherent to the systems. When applications involve many threads over more cores leased from the RaaS (Resource-as-a-Service) cloud under spot instance pricing for faster execution, resource unavailability are more likely to occur, undercutting execution performance gains potentially offered by those more cores. As a result, checkpointing is required to lower the adverse impact of resource unavailability on execution performance of such multithreaded applications. Given checkpointing often incurs expensive I/O to remote storage, this work presents design and implementation of our adaptive incremental checkpointing (AIC) for multithreaded applications on the RaaS clouds. AIC utilizes the idle cores for adaptive delta compression and remote checkpointing, significantly reducing the expected job turnaround time and the aggregated file size at remote storage. To ensure high compatibility and portability for AIC, we exploit techniques to avoid using kernel-specific data structures. AIC has been evaluated using PARSEC benchmarks on our established testbed, which resembles a multicore system acquired from the RaaS cloud. The results show that AIC noticeably reduces the expected turnaround time (by up to 37%) and the aggregated file size (by up to 8.3×) when compared to a recent multi-level checkpointing scheme with fixed checkpoint intervals.

Checkpointing has been widely adopted in support of fault-tolerance and job migration, with checkpoint files preferably kept also at remote storage to withstand unavailability/failures of local nodes in networked systems. Lately, I/O bandwidth to remote storage becomes the bottleneck for checkpointing on a large-scale system. This paper proposes an adaptive incremental checkpointing (AIC), aiming to reduce the checkpointing file size considerably so that its involved overhead is lowered and thus the expected job turnaround time drops. Given production multicore systems are observed to have unused cores often available, we design AIC to make use of separate cores for carrying out multi-level checkpointing with delta compression at desirable points of time adaptively. We develop a new Markov model for predicting the performance of such multi-level concurrent checkpointing, with AIC performance evaluated using six SPEC benchmarks under various system sizes. AIC is observed to lower the normalized expected turnaround time substantially (by up to 47%) when compared to its static counterpart and a recent multi-level checkpointing scheme with fixed checkpoint intervals.

This paper pursues RFID support for localization, aiming to pinpoint an object in 3D space. Given a set of RFID tags and/or readers deployed as reference points at known locations in a hexahedron (like shipping container or storage room), a passive and an active localization schemes are considered in this paper. Being the very first range-free 3D localization, our schemes depend solely on RFID tags and readers without other devices or sensors, and it avoids the need of distance estimation according to received wireless signal strength or phase difference. Our passive scheme locates an RFID tag attached to the target object, with both tags and readers as reference points. The active scheme locates an RFID reader, by iteratively determining a 3D sphere best covering the activated reference tags, referred to as the decision boundary optimization scheme (DeB). Results by simulations and testbed experiments using Alien RFID kits have been obtained, and they reveal that DeB outperforms its passive counterpart and achieves the localization error of 0.07 ft. Additionally, DeB yields better location accuracy and yet is much faster than a previous counterpart. With enhanced DeB (EDeB), accuracy of an object located near a hexahedron side or corner is improved considerably.

This article pursues speedy packet classification with low on-chip memory requirements realized on Xilinx Virtext-6 FPGA. Based on hashing round-down prefixes specified in filter rules (dubbed HaRP), our implemented classifier is demonstrated to exhibit an extremely low on-chip memory requirement (lowering the byte count per rule by a factor of 8.6 in comparison with its most recent counterpart [2]), taking only 50% of Virtex-6 on-chip memory to store every large rule dataset (with some 30K rules) examined. In addition, it achieves a higher throughput than any known FPGA implementation, reaching more than 200 MPPS (millions packet lookups per second) with 8 processing units and 8 memory banks in the HaRP pipeline to support the line rate over 130 Gbps under bi-directional traffic in the worst case with 40-byte packets. By reducing memory probes per lookup, enhanced HaRP can further boost the classification speed to 255 MPPS.

Existing virtual clusters and computer clouds usually depend on small groups of (or even single) data repositories for their virtual machine and software deployments. This paper proposes a Peer-to-Peer (P2P)-based approach for publishing, querying, and deploying both virtual machine (VM) images and application-specific packages, dubbed the P2P Virtual Cluster Deployment System (PVC-DS). The approach is built upon typical Distributed Hash Table (DHT) infrastructures, using a modified content distribution system to allow for extensible VM definitions and range query capabilities. Evaluation results demonstrate its significant reduction in VM operating-system image and application-specific package download times at the expense of negligible traffic overhead.

This article proposes a runtime model that relates server energy consumption to its overall thermal envelope, using hardware performance counters and experimental measurements. While previous studies have attempted system-wide modeling of server power consumption through subsystem models, our approach is different in that it links system energy input to subsystem energy consumption based on a small set of tightly correlated parameters. The proposed model takes into account processor power, bus activities, and system ambient temperature for real-time prediction on the power consumption of long running jobs. Using the HyperTransport and QuickPath Link structures as case studies and through electrical measurements on example server subsystems, we develop a chaotic time-series approximation for runtime power consumption, arriving at the Chaotic Attractor Predictor (CAP). With polynomial time complexity, CAP exhibits high prediction accuracy, having the prediction errors within 1.6% (or 3.3%) for servers based on the HyperTransport bus (or the QuickPath Links), as verified by a set of common processor benchmarks. Our CAP is a superior predictive mechanism over existing linear auto-regressive methods, which require expensive and complex corrective steps to address the nonlinear and chaotic aspects of the underlying physical system.

We present a distinct longest prefix matching (LPM) lookup scheme able to achieve exceedingly concise lookup tables (CoLT), suitable for scalable routers. Based on unified hash tables for handling both IPv4 and IPv6 simultaneously, CoLT excels over previous mechanisms in: 1) lower on-chip storage for lookup tables; 2) simpler table formats to enjoy richer prefix aggregation and easier implementation; and 3) most importantly, deemed the only design able to accommodate both IPv4 and IPv6 addresses uniformly and effectively. As its hash tables permit multiple possible buckets to hold each prefix (following a migration rule to avoid false positives altogether), CoLT exhibits the best memory efficiency and can launch parallel search over tables during every LPM lookup, involving fewer cycles per lookup when on-chip memory is used to implement hash tables. With 16 (or 32) on-chip SRAM blocks clocked at 500 MHz (achievable in today's 65-nm technology), it takes 2 (or 1.6) cycles on average to complete a lookup, yielding 250 (or 310+) millions of packets per second (MPPS) mean throughput. Being hash-oriented, CoLT well supports incremental table updates, besides its high table utilization and lookup throughput.

Packet classification is central to a wide array of Internet applications and services, with its approaches mostly involving either hardware support or optimization steps needed by software-oriented techniques (to add precomputed markers and insert rules in the search data structures). Unfortunately, an approach with hardware support is expensive and has limited scalability, whereas one with optimization fails to handle incremental rule updates effectively. This work deals with rapid packet classification, realized by hashing round-down prefixes (HaRP) in a way that the source and the destination IP prefixes specified in a rule are rounded down to “designated prefix lengths” (DPL) for indexing into hash sets. HaRP exhibits superb hash storage utilization, able to not only outperform those earlier software-oriented classification techniques but also well accommodate dynamic creation and deletion of rules. HaRP makes it possible to hold all its search data structures in the local cache of each core within a contemporary processor, dramatically elevating its classification performance. Empirical results measured on an AMD 4-way 2.8 GHz Opteron system (with 1 MB cache for each core) under six filter data sets (each with up to 30 K rules) obtained from a public source unveil that HaRP enjoys up to some 3.6× throughput level achievable by the best known decision tree-based counterpart, HyperCuts (HC).

This paper deals with decentralized, QoS-aware middleware for checkpointing arrangement in Mobile Grid (MoG) computing systems. Checkpointing is more crucial in MoG systems than in their conventional wired counterparts due to host mobility, dynamicity, less reliable wireless links, frequent disconnections, and variations in mobile systems. We've determined the globally optimal checkpoint arrangement to be NP-complete and so consider Reliability Driven (ReD) middleware, employing decentralized QoS-aware heuristics, to construct superior checkpointing arrangements efficiently. With ReD, an MH (mobile host) simply sends its checkpointed data to one selected neighboring MH, and also serves as a stable point of storage for checkpointed data received from a single approved neighboring MH. ReD works to maximize the probability of checkpointed data recovery during job execution, increasing the likelihood that a distributed application, executed on the MoG, completes without sustaining an unrecoverable failure. It allows collaborative services to be offered practically and autonomously by the MoG. Simulations and actual testbed implementation show ReD's favorable recovery probabilities with respect to Random Checkpointing Arrangement (RCA) middleware, a QoS-blind comparison protocol producing random arbitrary checkpointing arrangements.

This paper describes the deployment and evaluation of a 700MHz WiFi-based Wireless Mesh Network (WMN) testbed. To our knowledge, this is the world's first WiFi-based testbed using the recently-released 700MHz frequency band and deployed under both indoor and outdoor environments, including open space and a Louisiana swamp with dense cypress trees. Initial experimental results show that the 700MHz WMN has a significantly larger transmission range and better penetration ability compared to a traditional 2.4GHz WMN, which indicates that utilizing the 700MHz frequency band will considerably enhance the performance of WMNs, including the ability to support real-time applications.

A distributed hash table (DHT) with replicated objects enjoys improved performance and fault-tolerance but calls for effective replica management. This paper deals with proximity-aware distributed mutual exclusion (PADME) for P2P replica management on a DHT. Three main components are involved in PADME: (1) a few nodes designated as the sink candidates for collecting and consolidating replica updates, (2) a node selected from sink candidates to execute gathered replica updates, and (3) a proximity-sorted replica list to guide propagating the updated result effectively and reliably across all replica holders. Simulation results demonstrate that PADME exhibits at least two orders of magnitude less update message traffic than known leading distributed mutual exclusion-based algorithms for DHT replica management (namely, Sigma and E2E) under various cases examined. As a result, PADME outperforms Sigma (or E2E) by an order of magnitude (or up to 50%) in terms of the update throughput, while drastically lowering its update latency by up to 3 orders (or an order) of magnitude.

This work deals with an architectural framework to enable application-layer packet processing for lowered processing latency and enhanced throughput. Creating an "Ethereal memory" shared by application programs and network interface drivers, the proposed framework realizes application-layer packet processing through Ethereal memory (APPEAL). Unlike earlier solutions based on network processors or field programmable gate arrays, APPEAL supports packet processing software execution in regular OS environments (like Linux) on general-purpose multi-core processors (like Intelreg Core 2 Extreme and Broadcom BCM1480 SoC products). It facilitates fast packet processing code development and lets applications have direct accesses to data contained in Ethereal memory, totally eliminating the need of packet copies between user space and kernel space and of system calls. Without kernel overhead during application layer packet processing, APPEAL is shown by our empirical results obtained from a hardware platform comprising three BCM 1480 SoC's, to enjoy far smaller latency (dropped by as much as 58%) and to more than double throughput, when carrying out network address and port translation.

Distributed grid resource discovery (ReD) systems lack the ability to adapt efficiently to an increase in the number of attributes. The main contribution of this paper is a fast and scalable ReD mechanism, dubbed FaSReD, which composes a resource key via bit string encoding. We establish close-to-optimal FaSReD and a lower bound on the mean number of search hops under FaSReD. Through extensive simulation, our ReD is demonstrated to accommodate effectively an increase in the number of attributes with respect to such performance metrics as overlay hops, total messages, mean query response time, and throughput. FaSReD is further shown to outperform the leading prior distributed ReD range query schemes.

While extensive studies have been carried out in the past several years for many sensor applications, the main approach for sensor networking cannot be applied to the sceonarios with extremely low and intermittent connectivity, dubbed the Delay/Fault-Tolerant Mobile Sensor Network (DFT-MSN). Without end-to-end connections due to sparse network density and sensor node mobility, routing in DFT-MSN becomes localized and ties closely to medium access control, which naturally calls for merging Layer 3 and Layer 2 protocols in order to reduce overhead and improve network efficiency. Due to the unique characteristics of DFT-MSN, the communication links exist only with certain probabilities and become the scarcest resource. At the same time, the sensor nodes in DFT-MSN have very limited battery power like those in other sensor networks. Clearly, there is a tradeoff between link utilization and energy efficiency. In order to address the trade-off, we develop a cross-layer data delivery protocol for DFT-MSN, which includes two phases, i.e., the asynchronous phase and the synchronous phase. In the first phase, the sender contacts its neighbors to identify a set of appropriate receivers. Since no central control exists, the communication in the first phase is contention-based. In the second phase, the sender gains channel control and multicasts its data message to the receivers. Furthermore, several optimization issues in these two phases are identified, with solutions provided to reduce the collision probability and to balance between link utilization. Our results show that the proposed cross-layer data delivery protocol for DFT-MSN achieves a high message delivery ratio with low energy consumption and an acceptable delay.

As the demand for bandwidth grows, Internet routers must run faster. Ternary Content Addressable Memory (TCAM) has been known as a promising device in composing simple and efficient solutions for fast forwarding table lookups. However, most existing TCAM-based IP lookup solutions suffer from lengthy update durations imposed by TCAM entry shifts for maintaining the prefix order constraint. In this paper, a TCAM-based longest prefix search design is proposed in support of prompt and stable incremental updates. This is achieved by converting a conventional prefix table into multiple Bounded Minimum Independent Prefix Sets (B-MIPS) using a technique called Bounded Prefix Expansion and Compression (BPEC). Experimental results show its significant performance improvement in both the worst and the average cases when compared with previous TCAM-based IP lookup solutions. Additionally, the design exhibits considerable forwarding table size reduction, by more than 25%.

The discovery and management of energy resources, especially at locations in the Gulf of Mexico, requires an economic but technically enhanced infrastructure. Research teams from Louisiana State University, University of Louisiana at Lafayette, and Southern University Baton Rouge are engaged in a collaborative effort to create a ubiquitous computing and monitoring system (UCoMS) for the discovery and management of energy resources. The UCoMS team has sucessfully addressed two difficult issues in this research: (1) the computational challenges faced by compute-intensive simulations for reservoir uncertainty analysis that requires thousands of simulations and deals with terabytes, and even petabytes, of data, (2) the development of a prototype wireless sensor network (WSN) infrastructure to collect and process realtime data from production locations. While the former requires the intensive computational power of the UCoMS grid resources, the latter requires efficient interfacing between WSN & grid. A unified workflow analysis has been performed to ensure smooth operation of both efforts and a unified portal has been created. This paper integrates the above two workflows and portals into a single platform. It illustrates the need for such integration for users with similar (but not same) goals and describes how to partition users among different groups with different access rights to ensure security within subgroups. Such a system can easily integrate future UCoMS sub-projects into a unified whole. Hence, our portal prototype serves as a good example of the benefit that may accrue from integrated workflows.

This paper deals with a novel, distributed, QoS-aware, peer-to-peer checkpointing arrangement component for Mobile Grid (MoG) computing systems middleware. Checkpointing is more crucial in MoG systems than in their wired counterparts due to node mobility and less reliable wireless links resulting in frequent and dynamic connections and disconnections. Having determined the globally optimal checkpoint arrangement to be NP-complete, we consider ReD, our Reliability Driven (ReD) protocol, employing QoS-aware heurisitcs, for constucting superior peer-to-peer checkpointing arrangements efficiently.

While extensive studies have been carried out in the past several years for many sensor applications, they cannot be applied to the network with extremely low and intermittent connectivity, dubbed the delay/fault-tolerant mobile sensor network (DFT-MSN). Without end-to-end connections due to sparse network density and sensor node mobility, routing in DFT-MSN becomes localized and ties closely to medium access control, which naturally calls for merging Layer 3 and Layer 2 protocols in order to reduce overhead and improve network efficiency. DFT-MSN is fundamentally an opportunistic network, where the communication links exist only with certain probabilities and become the scarcest resource. At the same time, the sensor nodes in DFT-MSN have very limited battery power like those in other sensor networks. Clearly, there is a tradeoff between link utilization and energy efficiency. To address this tradeoff, we develop a cross-layer data delivery protocol for DFT-MSN, which includes two phases, i.e., the asynchronous phase and the synchronous phase. In the first phase, the sender contacts its neighbors to identify a set of appropriate receivers. Since no central control exists, the communication in the first phase is contention-based. In the second phase, the sender gains channel control and multicasts its data message to the receivers. Furthermore, several optimization issues in these two phases are identified, with solutions provided to reduce the collision probability and to balance between link utilization and energy efficiency. Our results show that the proposed cross-layer data delivery protocol for DFT-MSN achieves a high message delivery ratio with low energy consumption and an acceptable delay.

This article deals with communication performance of a multiprocessor system implemented using award-wining BCM 1480 multi-core chips. Our system uses high-performance HyperTransport links to interconnect constituent chips, realizing cache-coherent non-uniform memory access. It takes advantage of hardware support from the BCM 1480 chip to attain very impressive communication performance among constituent BCM 1480 chips. This is achieved via an extension to global memory, so that small messages can be pushed quickly across chips in less than one us by the CPU cores through DMA to achieve zero-copy message buffering. It eliminates all overhead associated with the kernel and protocol processing for the utmost interconnect bandwidth in data transfers.

This article deals with distributed address determination for mobile Grids, realized by ADENS (address determination via neighboring states), where a new mobile host (MH) determines a conflict-free address for itself efficiently according to state information only from neighboring MHs. With low traffic overhead, ADENS achieves higher address space utilization than the best known approach. The optimal design of basic ADENS has been derived analytically for the first time. Enhanced ADENS can be achieved by designating appropriate MHs (instead of permitting all MHs) to respond to address requests of newly arrived MHs, further improving address space utilization markedly while lowering traffic overhead drastically. Our simulation results reveal that enhanced ADENS enables a mobile Grid to operate practically as long as it needs.

This research focuses on RFID-based 3-D positioning schemes, aiming to locate an object in a 3-dimensional space, with reference to a predetermined arbitrary coordinates system, by using RFID tags and readers. More specifically, we consider a hexahedron which may be a shipping container, a storage room, or other hexahedral shape spaces. A number of RFID tags and/or readers with known locations are deployed as reference nodes. We propose two positioning schemes, namely, the active scheme and the passive scheme. The former scheme locates an RFID reader. For example, it may be employed to locate a mobile person who is equipped with an RFID reader or an object that is approached by an RFID reader. The passive scheme locates an RFID tag, which is attached to the target object. Both approaches are based on a Nelder-Mead nonlinear optimization method that minimizes the error objective functions. We have carried out analyses and extensive simulations to evaluate the proposed schemes. Our results show that both schemes can locate the targets with acceptable accuracy. The active scheme usually results in smaller errors and has a lower hardware cost compared to its passive counterpart. On the other hand, the passive scheme is more efficient when locating multiple targets simultaneously. The effectiveness of our proposed approaches is verified experimentally using the IDENTEC RFID kits.

This article deals with a novel architecture for IP routing table construction, on the basis of a single set-associative hash table to support fast longest prefix matching (LPM). The proposed architecture uses two key techniques to lower table storage required drastically: (1) storing transformed prefix representations and (2) accommodating multiple prefixes per table entry via prefix aggregation. Given a set of chosen prefix lengths (called "treads"), all prefixes are rounded down to nearest treads before hashed to the table using their transformed representations so that prefix aggregation opportunities abound in hash entries. Significant table storage reduction makes it possible to fit a large routing table in on-chip SRAM, solving both the memory and bandwidth- intensive problems faced by IP routing. Simulation results on real routing tables show that the proposed architecture saves at least two folds of storage when compared with most known hash table- based design or trie-based design. In addition, our design enjoys fast lookups and incremental updates, with the worst-case lookup time upper-bounded theoretically by the number of treads (zeta) but found experimentally to be 4 memory accesses when zeta equals 8.

Excessive power consumption is deemed one of the major drawbacks of TCAM-based IP search engines. This paper proposes a simple and yet efficient forwarding table partitioning algorithm aiming to achieve significant TCAM power savings. Our algorithm partitions the IP address space into a set of adjoining but non-overlapping search ranges comprising an exactly identical number of prefixes to be accommodated in a TCAM segment, dubbed exact table partitioning (ETAP). During a search operation, only one single range is examined to reduce overall TCAM power consumption substantially.

Hardware approaches for speedy IP lookups can be realized by making use of TCAMs (Ternary Content Addressable Memories), whose lookups utilize IP addresses as search keys with each search requiring only a single memory access. However, most existing TCAM-based forwarding engines involve shifting TCAM entries when the forwarding table is updated, typically incurring a lengthy update duration. In this paper, a TCAM-based longest prefix forwarding engine with fast updating is proposed. The key idea behind the design is to maintain the forwarding table in a TCAM according to the Minimum Independent Prefix Set (MIPS), totally avoiding the need to shift TCAM entries during updating. Experimental results show that our design is capable of supporting fast TCAM updates, lowering the adverse impact of table updates on IP lookup performance. In addition, our MIPS approach exhibits considerable forwarding table compression.

Most of the high-performance routers available commercially these days equip each of their line cards (LCs) with a forwarding engine (FE) to perform table lookups locally. This work introduces and evaluates a technique for speedy packet lookups, called SPAL, in such routers. The BGP routing table under SPAL is fragmented into subsets which constitute forwarding tables for different FEs so that the number of table entries in each FE drops as the router grows. This reduction in the forwarding table size drastically lowers the amount of SRAM (e.g., L3 data cache) required in each LC to hold the trie constructed according to the prefix matching algorithm. SPAL calls for caching the lookup result of a given IP address at its home LC (denoted by LC/sub ho/, using the LR-cache), such that the result can satisfy the lookup requests for the same address from not only LC/sub ho/, but also other LCs quickly. Our trace-driven simulation reveals that SPAL leads to improved mean lookup performance by a factor of at least 2.5 (or 4.3) for a router with three (or 16) LCs, if the LR-cache contains 4K blocks. SPAL achieves this significant improvement, while greatly lowering the SRAM (i.e., the L3 data cache plus the LR-cache combined) requirement in each LC and possibly shortening the worst-case lookup time (thanks to fewer memory accesses during longest-prefix matching search) when compared with a current router without partitioning the routing table. It promises good scalability (with respect to routing table growth) and exhibits a small mean lookup time per packet. With its ability to speed up packet lookup performance while lowering overall SRAM substantially, SPAL is ideally applicable to the new generation of scalable high-performance routers.

In this paper, we propose a novel medium access control protocol with a separate control channel (MAC-SCC) to increase the channel efficiency and address the unfairness and instability problems of IEEE 802.11 MAC protocol. In MAC-SCC, the available bandwidth is partitioned into two channels: a data channel and a control channel, each associated with a network allocation vector (NAV). To reduce hardware complexity, the station transmits or receives on one channel only at any given time. In the network employing MAC-SCC, the next data frame can be pre-scheduled during the current data transmission via the separate control channel, and thus reducing the frame collision probability and the bandwidth wasted during backoff. Moreover the use of the separate control channel helps to achieve fair medium access and solve the instability problem resulted from frequent link failures. The optimal bandwidth partitioning between the two channels is analyzed via a statistical model, which shows 10% bandwidth for the control channel and 90% bandwidth for the data channel. The performance of MAC-SCC is quantified via extensive simulations in both a stand-alone simulator developed by using PARSEC and a comprehensive network simulator called QualNet with whole protocol stack. Our results show that MAC-SCC can effectively reduce the link failure probability, achieve fair medium access when running multiple TCP sessions, and yield a throughput gain up to 60% under high traffic load

A shared tree with a lower end-to-end delay carries out multicast packet delivery more efficiently. This article introduces efficient multicast shared trees via restricted search (STRESS) realized by means of locating the closest on-tree nodes for new group members to join the trees. Such a tree ensures an end-to-end delay shorter than that in a tree built by connecting new members always to a fixed tree node (like CBT or PIM-SM). STRESS is shaped only by multicast group members to yield a tree as small as possible, totally avoiding the difficult task of determining a fixed tree node for member joining. It requires no centralized point to keep track of all on-tree nodes, therefore creating no performance or reliability bottleneck. Two mechanisms for restricted search over multicast trees plus local search are considered and evaluated by simulation. STRESS is shown to be more efficient than CBT, as a result of connecting new members to their nearest known on-tree nodes.

Geographic location information can effectively improve the performance (e.g., in routing or intelligent coordination) of large wireless networks. In this paper, we propose a novel self-configurable positioning technique for multihop wireless networks, based on a Euclidean distance estimation model and a coordinates establishment scheme. A number of nodes serve as the landmarks to establish a coordinates system. Specifically, any pair of landmarks estimate their Euclidean distance according to the shortest path length between them and establish the coordinates system by minimizing an error objective function. Other nodes in the network can accordingly contact the landmarks and determine their own coordinates. The proposed technique is independent of the Global Navigation Satellite Systems (GNSSs), and the established coordinates can be easily tuned to GNSS if at least one node in the network is equipped with GNSS receiver. Our simulation results show that the proposed self-configurable positioning technique is highly fault-tolerable to measurement inaccuracy and can effectively establish the coordinates for multihop wireless networks. More landmarks yield more accurate results. With the rectification of our Euclidean distance estimation model, four to seven landmarks are usually sufficient to meet the accuracy requirement in a network with hundreds of nodes. The computing time for coordinates establishment is in the order of milliseconds for a GHz CPU, acceptable for most applications in the mobile ad hoc networks as well as the sensor networks.

In this paper, we propose a grid-based working node (WN) selection approach for wireless sensor networks. Due to coverage redundancy, it is highly desirable to identify a minimum subset of sensors in a wireless sensor network to serve as WNs, while the remaining sensors are deactivated to save power and reduce potential interference. The basic idea of our solution approach is to represent the coverage of the sensors by a number of sample points, i.e., the intersection points of the established grid. A simple approximation algorithm and a linear programming method are employed to select as few sensors as possible to cover all sample points. In order to reduce the computational time, clusters are formed and WN selection is performed within each cluster. The performance of the proposed WN selection schemes is quantified and the tradeoff among accuracy, communication overhead and computational time is evaluated via analyses and simulations.

This work introduces and evaluates a technique for speedy packet lookups, called SPAL, in high-performance routers, realized by fragmenting the BGP routing table into subsets. Such a router contains multiple line cards (LCs), each of which is equipped with a forwarding engine (FE) to perform table lookups locally based on its forwarding table (which is a fragmented subset). The number of table entries in each FE drops as the number of LCs in a router grows. This reduction in the forwarding table size drastically lowers the amount of SRAM (e.g., L3 data cache) required in each LC to hold the trie constructed according to the matching algorithm. SPAL calls for caching the lookup result of a given IP address at its home LC (denoted by LC/sub ho/, using the LR-cache), such that the result can satisfy the lookup requests for the same address from not only LC/sub ho/ but also other LCs quickly, when the switching fabric for interconnecting LCs has a low latency. Lookup results obtained from remote LCs are also held in the LR-cache of a local LC. Our trace-driven simulation reveals that SPAL indeed leads to substantial improvement in mean lookup performance. SPAL may possibly shorten the worst-case lookup time (thanks to fewer memory accesses during longest-prefix matching search) when compared with a current router without partitioning the routing table. It takes no specific traffic into consideration when selecting the partitioning bits, promising good scalability and a small mean lookup time per packet.

Rapidly growing demand for high-speed networks has prompted the investigation into scalable routers that are capable of forwarding data at the aggregate rate of multiterabits per second. Such a router contains many line cards (LCs) for admitting external links of various speeds. Those LCs are interconnected by a switching fabric to provide paths for packets to travel from arrival LCs to their respective departure LCs. The switching fabric employed in a router dictates the scalability and the overall performance of the router. It is thus crucial for future multiterabit routers to incorporate scalable switching fabrics capable of interconnecting large numbers of LCs. This work considers switching fabrics with distributed packet routing to achieve high scalability and low costs. Our fabrics are based on a multistage structure with different recirculation designs, where adjacent stages are interconnected according to the indirect n-cube connection style. They all compare favorably with an earlier multistage-based counterpart according to extensive simulation, in terms of performance measures of interest and hardware complexity. When queues are incorporated in the output ports of switching elements (SEs), the total number of stages required in our proposed fabrics to achieve a given performance level can be reduced substantially. The performance of those fabrics with output queues is evaluated under different "speedups" of the queues, where the speedup is the operating clock rate ratio of that at the SE core to that over external links. It is found via our simulation results that a small speedup of two is adequate for buffered switching fabrics comprising 4/spl times/8 SEs to deliver better performance than their nonbuffered counterparts with 50 percent more stages of SEs, when the fabric size is 256. The buffered switching fabrics under different traffic patterns are evaluated and discussed as well. Being scalable and of low costs, the proposed switching fabrics are ideally suitable for routers with large numbers of LCs.

Data delivery to multiple recipients in networks can be achieved effectively via multicast based on a shared tree structure. This paper deals with a network-layer framework for efficient multicast through shared trees which are developed with an aid of guided information for locating nearest known on-tree nodes to connect upon receiving group join requests. Such information helps to shorten end-to-end delay over a multicast shared tree so developed, called a guided shared tree (GST). A designated node, known as guidance information node (GIN), is employed to provide guidance for a group, and the GIN is found by joining nodes through the group ID indexing into a list of candidate GINs, in a way similar to automatic core discovery for CBT. The proposed multicast framework is evaluated by simulation and is shown to be efficient, readily suitable for large networks where group members account for a fraction of total nodes and are sparsely located.

A hardware-assisted design, dubbed cache-oriented multistage structure (COMS), is proposed for fast packet forwarding. COMS incorporates small on-chip cache memory in its constituent switching elements (SEs) for a parallel router to interconnect its line cards (LCs) and forwarding engines (FEs, where table lookups are performed). Each lookup result in COMS is cached in a series of SEs between the FE (which performs the lookup) and the LC (where the lookup request originates). The cached lookup results fulfill subsequent lookup requests for identical addresses immediately without resorting to FEs for (time-consuming) lookups, thus reducing the mean lookup time tremendously. COMS calls for partitioning the set of prefixes in a routing table into subsets (of roughly equal sizes) so that each subset involves only a small fraction of the table for one FE. This leads to a substantial savings of SRAM required in each FE to hold its forwarding table, and the total savings of SRAM in a parallel router far exceeds the amount of SRAM employed in all SE's of COMS combined. A COMS-based router of size 16 exhibits over 10 times faster mean packet forwarding than its compatible router without caching nor table partitioning. The worst case lookup time in COMS depends on the matching algorithm employed in FE's and can often be shorter than that in a compatible router. With its ability to forward packets swiftly, COMS is ideally suitable for the new generation of parallel routers.

This paper deals with scalable switching fabrics for high-performance routers with large numbers of ports for connecting external links operating at various speeds to arrive at aggregate rates up to multi-terabits per second. The proposed switching fabrics employ no centralized scheduling and consist of small routing units (RUs), which are interconnected by multistage-based connecting components (CCs) in accordance with grid structures, with routing decisions made by RUs and CCs individually in a simple, distributed manner. They are referred to as grid-oriented, multistage-connected RUs, dubbed GRM. With distributed routing, GMR enjoys good scalability and low hardware complexity. It is found, based on our extensive simulation, that GMR outperforms not only their crossbar counterparts for small sizes, but also their compatible designs aiming at large sized construction (built from multiple stages of small crossbars), despite its lower hardware complexity. Two types of chips are sufficient to permit any sized construction; one for RUs and another for CCs. The proposed switching fabrics are cost-effective, readily suitable for scalable routers.

Switching fabrics with distributed control for scalable routers have been proposed recently. Such a fabric consists of small routing units (RU's) interconnected by multistage-based connecting components (CC's) according to grid structures, thereby referred to as a grid-oriented, Multistage-connected RU's, dubbed GMR, and is a direct interconnect with distributed routing. Performance of GMR is evaluated analytically and by simulation, with the packet mean latency being a key performance measure of interest. Under simplified assumptions and uniform traffic distributions, our analytic results are found to be very close to the simulation results (usually within 3% of each other) for a wide range of sizes, providing confidence to our simulation tool. Our simulation study demonstrates that GMR can deliver packets to their destination ports effectively in practical settings even when many ports run at a high-speed rate of 40 Gbps and non-uniform traffic exists. GMR is readily applicable to scalable routers with large numbers of high-speed ports.

This work considers switching fabrics with distributed packet routing to achieve high scalability and low costs. The considered switching fabrics are based on a multistage structure with different re-circulation designs, where adjacent stages are interconnected according to the indirect n-cube connection style. They all compare favorably with an earlier multistage-based counterpart according to extensive simulation, in terms of performance measures of interest and hardware complexity. When queues are incorporated in the output ports of switching elements (SEs), the total number of stages required in our proposed fabrics to reach a given performance level can be reduced substantially. The performance of those fabrics with output queues is evaluated under different "speedups" of the queues, where the speedup is the operating clock rate ratio of that at the SE core to that over external links. Our simulation reveals that a small speedup of 2 is adequate for buffered switching fabrics comprising 4/spl times/8 SEs to deliver better performance than their unbuffered counterparts with 50% more stages of SEs, when the fabric size is 256. The buffered switching fabrics under our consideration are scalable and of low costs, ideally suitable for constructing high-performance routers with large numbers of line cards.

Fault-tolerant techniques that can cope with system failures in software distributed shared memory (SDSM) are essential for creating productive and highly available parallel computing environments on clusters of workstations. We propose a new, efficient coordinated checkpointing technique, called coherence-based coordinated checkpointing (CCC), for SDSM. Our CCC minimizes both the checkpointing overhead during failure-free execution and the cost of recovery from failures by leveraging existing coherence information maintained by SDSM. In the presence of system failures, it allows SDSM to recover from the most recent checkpoint, saving the re-computation time. We have performed experiments on a cluster of eight Sun Ultra-5 workstations, comparing our CCC technique against both simple coordinated checkpointing (SCC) and incremental coordinated checkpointing (ICC) techniques by actually implementing these techniques in TreadMarks, a stare-of-the-art SDSM system. The experimental results demonstrate that our CCC technique consistently outperforms both SCC and ICC techniques. In particular our technique increases the execution time slightly by 0.5% to 4% for a 2-minute checkpointing interval during failure-free execution, while SCC and ICC techniques result in the execution time overhead of 4% to 100% and 3% to 64%, respectively for the same checkpointing interval.

This work considers the use of an SMT (simultaneous multithreading) processor in lieu of the conventional processor(s) in a router and evaluates quantitatively the potential gains as a result. An SMT processor exploits the benefits of both ILP (instruction level parallelism) and TLP (thread-level parallelism), suitable for the next generation routers, in which an increased number of functions are to be implemented. The use of an SMT processor not only allows router functions to be decomposed into multiple threads but also designates separate threads to handle different incoming traffic streams of a router to exploit TLP, potentially attaining performance improvement. Additionally, an SMT processor may admit new router functions or added traffic streams relatively easily without compromising much existing performance levels, via including a new thread (or threads) to perform one newly added function or traffic stream. This router design appears to have better flexibility and adaptability. In order to assess the benefits of this design approach, we implemented three key router functions (i.e., packet header extraction, packet header manipulation, and longest-prefix matching) as threads using an SMT simulator (SMTSIM) for performance evaluation. The results of this router design approach are collected and compared with those of conventional routers.

In this paper, we present a cost-effective design for ATM switching fabrics based on multistage structures, which involve no internal buffers at the constituent switching elements (SEs). The design consists of repeated copies of multiple stages of SEs, that are interconnected according to the indirect n-cube connection style between stages and that provide outlets for cells to terminate at their respective output queues when they reach their destined SEs, referred to as the I-Cubeout. This I-Cubeout makes use of far simpler SEs and requires fewer stages to achieve a given cell drop rate than the earlier design known as the shuffleout. It routes cells in a distributed manner and exhibits low hardware complexity, making it suitable for the ATM switch residing in wireless base stations.

The probability of failures in software distributed shared memory (SDSM) increases as the system size grows. This paper introduces a new, efficient message logging technique, called the coherence-centric logging (CCL) and recovery protocol, for home-based SDSM. Our CCL minimizes failure-free overhead by logging only data necessary for correct recovery and tolerates high disk access latency by overlapping disk accesses with coherence-induced communication existing in home-based SDSM, while our recovery reduces the recovery time by prefetching data according to the future shared memory access patterns, thus eliminating the memory miss idle penalty during the recovery process. To the best of our knowledge, this is the very first work that considers crash recovery in home-based SDSM. We have performed experiments on a cluster of eight SUN Ultra-5 workstations, comparing our CCL against traditional message logging (ML) by modifying TreadMarks, a state-of-the-art SDSM system, to support the home-based protocol and then implementing both our CCL and the ML protocols in it. The experimental results show that our CCL protocol consistently outperforms the ML protocol: Our protocol increases the execution time negligibly, by merely 1% to 6%, during failure-free execution, while the ML protocol results in the execution time overhead of 9% to 24% due to its large log size and high disk access latency. Our recovery protocol improves the crash recovery speed by 55% to 84% when compared to re-execution, and it outperforms ML-recovery by a noticeable margin, ranging from 5% to 18% under parallel applications examined.

Software distributed shared memory (DSM) improves the programmability of message-passing machines and workstation clusters by providing a shared memory abstract (i.e., a coherent global address space) to programmers. As in any distributed system, however; the probability of software DSM failures increases as the system size grows. This paper presents a new efficient logging protocol for adaptive software DSM (ADSM), called adaptive logging (AL). It is suitable for both coordinated and independent checkpointing since it speeds up the recovery process and eliminates the unbounded rollback problem associated with independent checkpointing. By leveraging the existing coherence data maintained by ADSM, our AL protocol adapts to log only unrecoverable data (which cannot be recreated or retrieved after a failure) necessary for correct recovery, reducing both the number of messages logged and the amount of logged data. We have performed experiments on a cluster of eight Sun Ultra-5 workstations, comparing our AL protocol against the previous message logging (ML) protocol by implementing both protocols in TreadMarks-based ADSM. The experimental results show that our AL protocol consistently outperforms the ML protocol: Our protocol increases the execution time slightly by 2% to 10% during failure-free execution, while the ML protocol lengthens the execution time by many folds due to its larger log size and higher number of messages logged. Our AL-based recovery also outperforms ML-based recovery by 9% to 17% under parallel application examined.

Compaction relocates active subcubes in a fragmented hypercube so as to produce a contiguous free region and eliminate the adverse impact of fragmentation on performance. The overhead of compaction is often contributed primarily by task migration, which makes use of disjoint paths for transmitting migrated data. Since task migration usually involves transmitting a large amount of data, the time required for migration with single paths is long, making compaction an undesirably lengthy process. This paper considers fast compaction through the use of all disjoint paths in existence for migration simultaneously from a source subcube to its target subcube, effectively reducing the size of data transmitted over a path and shortening the migration time. This approach leads to considerable savings in the compaction time for hypercubes which support circuit switching or wormhole routing, when compared with that using single migration paths.

As a software-based distributed shared memory (DSM) system is especially sensitive to the traffic amount over the network, we propose a new software DSM model. The model postpones the enforcement of data coherence at the time of the first shared memory access after an acquire, instead of at the time of the acquire like the lazy release consistency (LRC) model. This leads to an aggressive implementation of release consistency and thus a reduced number of messages transferred over the network when compared with LRC. Our model is evaluated on the basis of the TreadMarks framework using three applications, where TreadMarks is a software DSM implementation following LRC. The experimental results on a network of workstations indicate that our model leads to fewer messages transmitted across the network than LRC, by over 16% for one application and over 12% for the other two.

This paper introduces an efficient barrier synchronization algorithm based on the binomial spanning tree (BST) and proposes a data transfer reduction technique for distributed shared memory systems under release consistency.The introduced BST-based barrier algorithm parallelizes and distributes the workload amongs participating processors, alleviating network contention and yielding less retransmission.As a result, performance improves, and the degree of improvement increases quickly as the number of participants grows.Our barrier algorithm and data transfer reduction technique are incorporated in TreadMarks for evaluation using various benchmarks on a network of workstations and the IBM SP machine.Experimental results are gathered and demonstrated.

Repeated subcube allocation and deallocation in hypercubes tend to cause fragmentation, which can be taken care of by task migration. Earlier task migration dealt with the establishment of a single path from each participating node for transmitting migrated information. The time required for migration with single paths is long, if a large amount of information is moved in hypercubes. This paper considers speedy task migration in that two disjoint paths are created between every pair of corresponding nodes for delivering migrated information simultaneously, reducing the size of data transmitted over a path. All migration paths selected are pairwise disjoint and contain no link of active subcubes, so that task migration can be performed quickly and on-line without interrupting the execution of other jobs. Our approach could lead to a considerable savings in the migration time for contemporary hypercube systems, where circuit switching or wormhole routing is implemented.

A hypercube may operate in a gracefully degraded manner, after faults arise, by supporting the execution of parallel algorithms in smaller fault-free subcubes. In order to reduce execution slowdown in a hypercube with given faults, it is essential to identify the maximum healthy subcubes in the faulty hypercube because the time for executing a parallel algorithm tends to depend on the dimension of the assigned subcube. The paper describes an efficient procedure capable of determining all maximum fault-free subcubes in a faulty hypercube. The procedure is a distributed one, since every healthy node next to a failed component performs the same procedure independently and concurrently. Based on interesting properties of faulty hypercubes, this procedure exhibits empirically polynomial time complexity with respect to the system dimension and the number of faults, for a practical range of dimensions. It compares favorably with prior methods when the number of faults is in the order of the system dimension. This procedure can deal with node failures and link failures uniformly and equally efficiently.

An incomplete hypercube possesses virtually every advantage of complete hypercubes, including simple deadlock-free routing, a small diameter, bounded link traffic density, a good support of parallel algorithms, and so on. It is natural to reconfigure a faulty hypercube into a maximum incomplete cube so as to lower potential performance degradation, because a hypercube so reconfigured often results in a much larger system than what is attainable according to any conventional reconfiguration scheme which identifies only complete subcubes. A maximum incomplete subcube involves one maximum complete subcube, plus certain smaller complete subcubes, and, thus, may accommodate multiple jobs of different sizes simultaneously, delivering a higher performance level. This paper proposes an efficient approach for identifying all the maximum incomplete subcubes present in a faulty hypercube. The proposed approach is on the basis of manipulating Boolean expressions, with the search space reduced considerably by taking advantage of the basic properties of faulty hypercubes during expression manipulation. It is distributed, in that every healthy node executes the same identification algorithm independently, at the same time, it is confirmed by fault simulation that our approach indeed gives rise to significantly larger reconfigured systems and requires short execution times.

Mutual exclusion in shared-memory multiprocessors is realized by employing a lock to determine the processor among those which compete for the critical section. Accesses to such a mutual exclusion lock may create heavy synchronization traffic and/or serious contention over the network, thereby degrading system performance considerably. In this paper, we introduce an efficient scheme which keeps synchronization traffic low and avoids serious hot-spot contention. This is made possible by constructing a circular list of the processors waiting for the critical section and by dispersing accesses to the lock. Extensive simulation of the proposed approach was conducted and the lower bound on the elapsed time was derived. Our simulation results demonstrate that the proposed scheme indeed achieves better performance than prior techniques, with its elapsed time close to the lower bound for the whole range of simulated system sizes, thus promising good scalability for large systems.

Distributed shared memory (DSM) systems could overcome major obstacles of the widespread use of distributed-memory multiprocessors, while retaining the attractive features of low cost and good scalability common to distributed-memory machines. A DSM system allows a natural and portable programming model on distributed-memory machines, making it possible to construct a relatively inexpensive and scalable parallel system on which programmers can develop parallel application codes. Due to its potential advantages, DSM has received increasing attention. In this panel, challenges in building efficient DSM systems for a wide range of applications are addressed and discussed.

After faults arise in a hypercube, it is often desirable to reconfigure the faulty hypercube in such a way as to retain as many fault-free nodes as possible, because system performance tends to be in proportion to the computational power, and a reconfigured hypercube with more nodes is likely to retain performance better. This inspires us to identify maximum incomplete subcubes in a faulty hypercube, as the subcube so reconfigured is often much larger than that reconfigured according to earlier schemes. Here we propose an efficient algorithm for determining maximum incomplete subcubes in faulty hypercubes. The basic idea is to construct a maximum incomplete subcube from a number of healthy complete subcubes of distinct sizes. To this end, an efficient procedure for finding all maximum fault-free complete subcubes in a faulty hypercube is introduced, and then an efficient algorithm for determining maximum incomplete subcubes is presented.

When multiple copies of a certain resource exist in a cube network system, it is desirable that every nonresource node can reach the resource in a given number of hops. In this paper, we introduce systematic approaches to resource allocation in a cube system so that each nonresource node is connected with a specified number of resource copies and that the allocation performance measure of interest is optimized. The methodology used is based on the covering radius results of known codes. These codes aid in constructing desired linear codes whose codewords address nodes where resource copies are placed. The resource allocation problem is translated to an integer nonlinear program whose best possible solution can be identified quickly by taking advantage of basic properties derived from the known codes, yielding an optimal or near-optimal allocation result. Those basic properties lead to drastic time complexity reduction (up to several orders of magnitude smaller), in particular for large system sizes. Our approaches are applicable to any cube size, often arriving at more efficient allocation outcomes than what are attainable using prior schemes.

The incomplete hypercube with arbitrary nodes provides far better incremental flexibility than the complete hypercube, whose size is restricted to exactly a power of 2. After faults arise in a complete hypercube system, it is desirable to reconfigure the system so as to retain as many healthy nodes as possible, often leading to an incomplete hypercube of arbitrary size. In this paper, the highest traffic density over links in an incomplete hypercube under uniform message distribution is shown to be bounded by 2 (messages per link per cycle), independent of its size and despite its structural nonhomogeneity. As a result, it is easily achievable to construct an incomplete hypercube with sufficient link communication capability where any potential points of congestion are avoided, ensuring high performance. Simulation results for the incomplete hypercube reveal that mean latency for delivering messages is roughly the same in an incomplete hypercube as in a compatible complete hypercube under both packet-switching and wormhole routing. The incomplete hypercube thus appears to be an attractive and practical architecture, since it shares every advantage of complete hypercubes while eliminating the restriction on the system size.

While a certain resource in the hypercube may be shared by cube nodes to lower the cost, multiple copies of a shared resource often exist in the hypercube to reduce contention, and thus the potential delay, in fetching any shared copy. It is desirable that one employs as few resource copies as possible to ensure that every node is able to reach the resource in a given number of hops, achieving efficient resource placement. This placement method also keeps system performance degradation minimal after one resource copy becomes unavailable due to a fault. First, we consider placing multiple copies of a certain resource in a way that every cube node without the resource is adjacent to a specified number of resource copies. The use of our developed perfect and quasiperfect multiple-adjacency codes makes it possible to arrive at efficient solutions to this placement problem in a simple and systematic manner for an arbitrary hypercube. We then deal with the generalized resource placement in the hypercube such that every node without the resource can reach no less than a specified number of resource copies in no more than a certain number of hops, using as few resource copies as possible. Our placement results yield lowest potential access contention for a given number of resource copies (i.e., cost), particularly useful for large-scale hypercubes.>

Since the butterfly network possesses various attractive topological properties and its constituent node has a fixed degree, independent of the system size, interconnecting processors in accordance with the butterfly topology to construct a distributed-memory multiprocessor is advantageous, especially for a large sized system. Every butterfly node in a multiprocessor so constructed is a processor, not simply a switch. In this paper, we examine a reliable butterfly-based multiprocessor that preserves its full rigid butterfly configuration even in the presence of faults. The proposed butterfly parallel system can tolerate any single and many multiple node/link failures, giving rise to significantly improved reliability. Reconfiguration in response to an operational fault in our design is easy and may be performed in a distributed manner. A system after reconfiguration is ensured to provide the same high performance. Reliability results show that our design compares favorably with an earlier design. An extension to this reliable design is also addressed.>

Since the hypercube is not incrementally scalable, a variant hypercube topology with more flexibility in the system size, called an incomplete hypercube, is examined. An incomplete hypercube may also result from a complete hypercube which operates in a degraded manner after some nodes fail. Elementary properties, including diameter, mean internode distance, and traffic density, of incomplete hypercubes with size 2/sup n/+2/sup k/, 0/spl les/k/spl les/n, are derived. Interestingly, traffic density over links in such an incomplete hypercube is found to be bounded by 2 (messages per link per unit time), despite its structural nonhomogeneity. Thus, cube links can easily be constructed so as to avoid any single point of congestion, guaranteeing good performance. The minimum incomplete hypercubes able to embed binary trees with node adjacencies preserved are determined.>

We propose a new processor allocation strategy that applies to any mesh system and recognizes submeshes of arbitrary sizes at any locations in a mesh system. The proposed strategy allocates a submesh of exactly the size requested by an incoming task, completely avoiding internal fragmentation. Because of its efficient allocation, this strategy exhibits better performance than an earlier allocation strategy based on the buddy principle. An efficient implementation of this strategy is presented. Extensive simulation runs are carried out to collect experimental cost and performance measures of interest under different allocation schemes.>

With all of the salient features of hypercubes, the cube-connected cycles (CCC) structure is an attractive parallel computation network suited for very large scale integration (VLSI) implementation because of its layout regularity. Unfortunately, the classical CCC structure tends to suffer from considerable performance degradation in the presence of faults. The authors deal with a fault-tolerant CCC structure obtained by incorporating a spare PE in each cycle and by adding extra links among PE's to realize dimensional substitutes for failed PE's in the immediate lower dimension. A unique feature of this design lies in that a faulty PE and its laterally connected PE are always replaced at the same time by their immediate vertical successor pair, achieving pairwise substitution to elegantly maintain the rigid full CCC structure after faulty PE's arise. The proposed structure improves reliability substantially without incurring large overhead in layout area. This design is compared with earlier fault-tolerant CCC designs in terms of normalized reliability, which takes area overhead into account. An extension to this fault-tolerant structure is also discussed.>

The incomplete hypercube provides far better incremental flexibility than the complete hyper cube, whose size is restricted to exactly a power of 2. In this paper, the performance of incomplete hypercube sys tems is evaluated empirically. The simulation results reveal that mean latency for delivering messages is roughly the same in an incomplete hypercube as in a com patible complete hypercube, unless the message genera tion rate is extremely high (. 0.9). It is also found that mean latency for messages traversing links with heavy traffic can be appreciably larger than the mean latency of overall messages. When the link communication capabil ity is doubled, mean message latency becomes virtually uniform no matter whether or not the message traverses a link with heavy traffic, confirming that the incomplete hypercube can be made congestion-free easily to guaran tee high performance under any traffic load.

We introduce systematic approaches to resource allocation in a cube system so that each non resource node is connected with one resource copy and that the allocation performance measure of interest is optimized.

The cube-connected cycles (CCC) architecture is an attractive parallel computation network, because it is suitable for VLSI implementation while preserving all the desired features of hypercubes. However, the CCC tends to suffer from considerable performance degradation when a fault arises. In this work, a fault-tolerant CCC which exhibits significantly enhanced reliability is proposed. Reconfiguration in response to an operational fault in this fault-tolerant CCC is simple and can be performed in a distributed manner. When compared with the CCC, the proposed design in the absence of faults gets performance improvement as a result of faster broadcasting and PE-to-PE communication. The layout of this structure is discussed, and its area overhead is found to be moderate if the PE size is much larger than the link/switch size. Therefore, this design approach is particularly useful for situations where the PE is relatively complex.>

The Gamma interconnection network (GIN) is composed of 3*3 basic building blocks, with interconnecting patterns between stages following the plus-minus-2/sup i/ functions. The authors consider modifications to the GIN by altering the interconnecting patterns between stages so as to achieve high terminal reliability between any source-destination pair, resulting in the reliable GIN (REGIN). A type of REGIN's ensures totally disjoint paths in existence from any source to any destination, thereby capable of tolerating an arbitrary single fault. If several building blocks (i.e., 3*3 switches) are fabricated in one chip with very large scale integrated (VLSI) technology, the layout area and the pin count are less for the REGIN than for its GIN counterpart as a result of the change in the interconnecting patterns, giving rise to potential cost reduction. The terminal reliability of the REGIN is derived and compared with that of a compatible GIN. In addition, the performance of the REGIN is evaluated using simulation.>

The butterfly parallel system has a regular and simple interconnection pattern, making it suitable for VLSI or WSI implementation. The authors propose an effective fault-tolerant technique for the circular butterfly parallel system to ensure its rigid full butterfly structure even in the presence of failures, addressing reconfiguration in detail. The resulting butterfly system has L levels, involves (1/log/sub 2/ L)% spare processing elements (PEs), and approximately 50% additional links. The reconfiguration process of the design in response to any operational fault is easy and can be performed in a distributed manner. The reliability and layout of this proposed design are evaluated analytically. This design, due to its specific configuration, exhibits significant improvement in reliability while taking only moderately more layout area.>

Fully recognizing various subcubes in a hypercube computer efficiently is addressed. A method with much less complexity than the multiple-GC strategy in generating the search space, while achieving complete subcube recognition, is proposed. This method is referred to as a dynamic processor allocation scheme because the search space generated is dependent on the dimension of the requested subcube dynamically. The basic idea lies in collapsing the binary tree representations of a hypercube successively so that the nodes which form a subcube but are distant are brought close to each other for recognition. The strategy can be implemented efficiently by using right rotating operations on the notations of the sets of subcubes corresponding to the nodes at a certain level of binary tree representations. Results of extensive simulation runs carried out to collect performance measures for different allocation strategies are discussed. It is shown that this strategy compares favorably in most situations with other known allocation schemes capable of achieving complete subcube recognition.>

A cost-effective combining structure to alleviate hot-spot contention is proposed. The key idea is that the combining function is separated from the routing function, so that a binary tree-based combining configuration becomes feasible. The combining element for realizing the new structure has only one wait buffer and one combining logic, involving less hardware than the element used in earlier combining networks. More importantly, the number of constituent combining elements in such a structure with size N is reduced to O(1/log/sub 2/ N) of that required in the previous design. The proposed combining structure in conjunction with a regular multistage interconnection network can remove hot-spot contention effectively in any sized system at a considerably lower cost, and appears readily suitable for use in some applications.>

A processor allocation strategy is proposed which can apply to any mesh system and recognize submeshes with arbitrary sizes at any location in a mesh system. The proposed strategy allocates a submesh of exactly the size requested by an incoming task, completely avoiding internal fragmentation. Because of its efficient allocation, this strategy exhibits better performance than an earlier allocation strategy based on the buddy principle. An efficient implementation of this strategy is presented. Extensive simulation runs were carried out to collect experimental performance measures of interest under different allocation schemes for comparison.>

The cube-connected cycles (CCC) architecture is an attractive .supercomputersystem, because it not

A hypercube with extra connections added between pairs of nodes through otherwise unused links is investigated. The extra connections are made in a way that maximizes the improvement of the performance measure of interest under various traffic distributions. The resulting hypercube, called the enhanced hypercube, requires a simple routing algorithm and is guaranteed not to create any traffic-congested points or links. The enhanced hypercube achieves noticeable improvement in diameter, mean internode distance, and traffic density, and it also is more cost effective than a regular hypercube. An efficient broadcast algorithm that can considerably speed up the broadcast process in enhanced hypercubes is provided.>

Efficient solutions to the problem of optimally selecting recovery points are developed. The solutions are intended for models of computation in which task precedence has a tree structure and a task may fail due to the presence of faults. An algorithm to minimize the expected computation time of the task system under a uniprocessor environment has been developed for the binary tree model. The algorithm has time complexity of O(N/sub 2/), where N is the number of tasks, while previously reported procedures have exponential time requirements. The results are generalized for an arbitrary tree model.>

The VLSI layouts of most fault-tolerant binary tree architectures are based on the classical H-tree layout, resulting in low area utilization and an unnecessarily high manufacturing cost due to the waste of a significant portion of silicon area. An area-efficient approach to the reconfigurable binary tree architecture is presented. Area utilization and interconnection complexity of the proposed design compare favorably with other known approaches. The use of the coverage factor makes it possible to analyze the system reliability by means of the Markov model. Unlike previous reliability studies in which chips are assumed to be defect-free, this analysis considers the fact that an accepted chip may have used spares to replace manufacturing defects, and the number of spares available for tolerating operational faults may thus vary from chip to chip. The developed analytical model for reliability is readily extended to other VSLI/WIS-based multiprocessor systems.>

Incomplete hypercubes are analyzed. The elementary properties of complete hypercubes and a routing algorithm for incomplete hypercubes are briefly reviewed. Structural properties, including diameter, mean message traversal, and traffic density, of incomplete hypercube computers with size 2/sup n/+2/sup k/, 0>

Each node of a hypercube system, when fabricated, comes with a fixed number of links designed for a maximum sized construction. Very often, there are links left unused at each node in a real system. In this article, we study the hypercube in which extra connections are added between pairs of nodes through otherwise unused links. Those extra connections are made in order to maximize the improvement of the performance measure of interest under various traffic distributions. The resulting hypercube, called the variant hypercube, requires a simple routing algorithm and is guaranteed not to create any traffic-congested point or link. The variant hypercube is found to achieve considerable reduction in diameter, and noticeable improvement in mean internode distance and traffic density. In addition, a variant hypercube is more cost-effective than a regular hypercube and does not suffer from practical implementation difficulty. As a result, it also appears advantageous for hypercube systems with no available unused links to augment each node so as to accommodate an extra link, provided that the building block is not pin limited and is allowed to do so.

Fully recognizing various subcubes in a hypercube computer efficiently is nontrivial due to the specific structure of the hypercube. We propose a method with much less complexity than the multiple-GC strategy in generating the search space, while achieving complete subcube recognition. This method is referred to as a dynamic processor allocation scheme because the search space generated is dependent upon the dimension of the requested subcube dynamically, rather than being predetermined and fixed. The basic idea of this strategy lies in collapsing the binary tree representations of a hypercube successively so that the nodes which form a subcube but are distant would be brought close to each other for recognition. The strategy can be implemented efficiently by using shuffle operations on the leaf node addresses of binary tree representations. Extensive simulation runs are carried out to collect experimental performance measures of interest of different allocation strategies. It is shown from analytic and experimental results that this strategy compares favorably in many situations to any other known allocation scheme capable of achieving complete subcube recognition.

A scheme applicable to a wide class of multistage interconnection networks to enhance their fault-tolerant capability is proposed. Multiple paths between each input-output pair of a network are created by connecting switching elements within the same stage. This scheme provides a network with alternative paths at every stage, requires a simple self-routing algorithm, and allows a network to become more robust as its size increases. An analysis is performed to obtain a quantitative measurement of the reliability improvement of the scheme.>

When a large number of processors try to access a common variable, referred to as hot-spot accesses in [6], not only can the resulting memory contention seriously degrade performance, but it can also cause tree saturation in the interconnection network which blocks both hot and regular requests alike. It is shown in [6] that even if only a small percentage of all requests are to a hot-spot, these requests can cause very serious performances problems, and networks that do the necessary combining of requests are suggested to keep the interconnection network and memory contention from becoming a bottleneck.

A scheme is proposed to enhance the fault-tolerance of multistage interconnection networks which only have a unique path between each input/output pair (e.g.Omega networks, Baseline networks, etc.).It is done by creating multiple paths between each input/output pair of the network through extra links between switching elements in the same stage.This scheme requires a simple routing algorithm and allows a network to become more robust as its size increases.A reliability analysis is presented to provide a quantitative measurement on the improvement of its fault-tolerance capability.In terms of reliability, a network implemented with this scheme is more cost-effective than a regular one.