Pruning and Quantization are two effective Deep Neural Network (DNN) compression methods for efficient inference on various hardware platforms. Pruning refers to removing unimportant weights or nodes, whereas Quantization converts the floating-point parameters to low-bit fixed integer representation. The pruned and low precision models result in smaller and faster inference models on hardware platforms with almost the same accuracy as the unoptimized network. Tensor Cores in Nvidia Ampere 100 (A100) GPU supports (1) 2:4 fine-grained sparse pruning where 2 out of every 4 elements are pruned, and (2) traditional dense multiplication to achieve a good accuracy and performance trade-off. The A100 Tensor Core also takes advantage of 1-bit, 4-bit, and 8-bit multiplication to speed up the inference of a model. Hence, finding the right matrix type (dense or 2:4 sparse) along with the precision for each layer becomes a combinatorial problem. Neural Architecture Search (NAS) can alleviate such problems by automating the architecture design process instead of a brute-force search. In this paper, we propose (i) Mixed Sparse and Precision Search (MSPS), a NAS framework to search for efficient sparse and mixed-precision quantized model within the predefined search space and fixed backbone neural network (Eg. ResNet50), and (ii) Architecture, Sparse and Precision Search (ASPS) to jointly search for kernel size and number of filters, and sparse-precision combination of each layer. We illustrate the effectiveness of our methods targeting A100 Tensor Core on Nvidia GPUs by searching efficient sparse-mixed precision networks on ResNet50 and achieving better accuracy-latency trade-off models compared to the manually designed Uniform Sparse Int8 networks.

Convolutional Neural Networks (CNNs) have exceeded human accuracy in many Computer Vision tasks, such as Image Classification, Object Detection, Image Segmentation, etc. This advancement is due to the efficient manual design of CNNs in initially, followed by automated design through Neural Architecture Search (NAS). In parallel to neural network design, advances in Accelerator hardware design, such as Google’s Tensor Processing Unit (TPU), Eyeriss, etc., also occurred for efficient processing of CNN forward propagation. The heart of these accelerators is an array processor (Systolic Array) of a fixed dimension, that limits the amount of CNN computation that can be carried out in a single clock cycle. While NAS is able to produce efficient neural architectures, the networks need to be co-designed with respect to the underlying array dimensions to obtain the best performance. In this paper, we introduce "Array Aware Neural Architecture Search" to automatically design efficient CNNs for a fixed array-based neural network accelerator. Previous Hardware Aware NAS methods consider a fixed search space for different hardware platforms and search within its predefined space. We explore the search space based on the underlying hardware array dimensions to design a more efficient CNN architectures for optimal performance. We observe that our proposed NAS methods on the CIFAR-10 dataset produce similar accuracy as the baseline network while saving a substantial number of cycles on the Array.

The use of cyclic quorum sets has proved to be an efficient method for distributed systems to solve t asks requiring massive computations. In all-pairs data interaction problem, cyclic quorum sets can be used to avoid communication completely after initial data placement. However, searching for cyclic quorum sets with all-pairs property for a given number of objects, p, in a distributed system is a daunting task that involves massive computations as it is a combinatorial problem requiring full search. No time complexity reduction method has been found thus far. In other applications of cyclic quorum sets such as cycle-based routing problem, different cyclic quorum sets provide similar fault coverage yet generate significant resource utilization difference. Inspired by the need for all cyclic quorum sets with all-pairs property, we develop a methodology to optimize the search process by avoiding the search space where no new set could be found. After studying all possible cyclic quorum sets for a given p, we develop insights into the properties of all quorum sets that helps us to reduce the number of searches significantly. A s a result, for small values of p, when doing brutal-force search, our method not only reduces the time to find the first cyclic quorum base set with all-pairs property but is also able to find a ll of them in a reasonable amount of time. Moreover, we notice that as p grows, up to several orders of magnitude of search reduction could be achieved compared to naïve search. For large values of p, with existing results of base sets, we also propose a heuristic method with constant time complexity that computes a feasible subsets-assigning solution that meets the all-pairs requirement.

Manually architecting Deep Neural Networks (DNNs) has led to the success of Deep Learning in many domains. However, recent DNNs designed using Neural Architecture Search (NAS) have exceeded manually designed architectures and have significantly reduced the human effort to develop complex networks. Current works use NAS to identify a cell architecture constrained by a fixed order of operations that is then replicated throughout the network. The constraints potentially limit the effectiveness of NAS in converging on a more efficient DNN architecture. In the first part of our paper, we propose “Operation Search,” a search on an enlarged topological space for U-net and its variants that retain efficiency. The idea is to allow for custom cells (operations and their sequence) at various levels of the network to maximize image quality while being sensitive to computation cost. In the second part of our paper, we propose custom quantization at various levels resulting in a mixed-precision network. Additionally, we increase the search efficiency by constraining the search space to use the same precision for both weights and activations at any level. This does not result in computational inefficiency because it matches the operand precisions supported by Tensor Core enabled GPUs.

Cycle-based routing is an efficient routing mechanism widely used to achieve fault-tolerant, reliable, and robust network routing. To meet all-to-all source-destination pairs traffic requirements using cycle-based routing, one efficient method is to use quorum sets to establish cycles to serve each source and destination pair on one of the cycles. Quorum-based cycle routing significantly reduces the total number of direct links to be used in the network compared to establishing all point-to-point communication routes. Adopting different quorum sets provides similar flexibility and reliability yet yields significant differences in resource utilization. We compare multiple quorum sets to establish cycle-based routing paths. We then adopt average cycle length (ACL), standard deviation of cycle length (SDCL), and longest cycle length (LCL) of different configurations of cyclic quorum sets as performance metrics. Using NSFnet topology, we conclude that there is no perfect cyclic quorum set that yields optimal performance for all metrics, and trade-offs need to be made based on the most significant network design requirement when choosing a solution.

Operating at lower frequencies than systems such as Wi-Fi, TVWS wireless communication can enable long-range communication in rural communities and can more easily penetrate obstacles (vegetation, terrains). Thus, it is appealing to scenarios where line-of-sight is not always guaranteed. In particular, TVWS communication is a good candidate for supporting precision agriculture such as camera-based plant phenotyping and sensor-based analysis of plant behaviour. Yet there lacks in-depth real-world measurement data on the behavior of TVWS wireless channels in agriculture farms. To fill this gap, we use the field-deployed TVWS network of CyNet to measure TVWS channel behaviour in the Curtiss Research Farm in Ames, Iowa, where the landscape is predominantly composed of soybean and corn fields. We investigate the impact that crop diversity (soybean vs. corn), height and density of corn fields, antennas’ placement and variations of temperature and humidity have on the spatiotemporal behaviour of TVWS channels. This study also helps identify path loss models that best reflect radio propagation characteristics of TVWS systems in corn farms for different antenna heights.

Radio access network (RAN) virtualization is gaining more and more ground and expected to re-architect the next-generation cellular networks. Existing RAN virtualization studies and solutions have mostly focused on sharing communication capacity and tend to require the use of the same PHY and MAC layers across network slices. This approach has not considered the scenarios where different slices require different PHY and MAC layers, for instance, for radically different services and for whole-stack research in wireless living labs where novel PHY and MAC layers need to be deployed concurrently with existing ones on the same physical infrastructure. To enable whole-stack slicing where different PHY and MAC layers may be deployed in different slices, we develop PV-RAN, the first open-source virtual RAN platform that enables the sharing of the same SDR physical resources across multiple slices. Through API Remoting, PV-RAN enables running paravirtualized instances of OpenAirInterface (OAI) at different slices without requiring modifying OAI source code. PV-RAN effectively leverages the inter-domain communication mechanisms of Xen to transport time-sensitive I/Q samples via shared memory, making the virtualization overhead in communication almost negligible. We conduct detailed performance benchmarking of PV-RAN and demonstrate its low overhead and high efficiency. We also integrate PV-RAN with the CyNet wireless living lab for smart agriculture and transportation.

Matching and registration between aerial images and prestored road landmarks are critical techniques to enhance unmanned aerial system (UAS) navigation in the global positioning system (GPS)-denied urban environments. Current registration processes typically consist of two separate stages of road extraction and road registration. These two-stage registration approaches are time-consuming and less robust to noise. To that end, in this article, we, for the first time, investigate the problem of end-to-end Aerial-Road registration. Using deep learning, we develop a novel attention-based neural network architecture for Aerial-Road registration. In this model, we construct two-branch neural networks with shared weights to map two input images into a common embedding space. Besides, considering that road features are sparsely distributed in images, we incorporate a novel multibranch attention module to filter out false descriptor matches from the indiscriminative background in order to improve registration accuracy. Finally, the results from extensive experiments show that compared with state-of-the-art approaches, the mean absolute errors of our approach in rotation angle and the translations in the x - and y -directions are reduced down by a factor of 1.24, 1.38, and 1.44, respectively. Furthermore, as a byproduct, our experimental results prove the feasibility of a neural network multitask learning approach to simultaneously achieve accurate Aerial-Road matching and registration, thus providing an efficient and accurate UAS geolocalization.

Due to the increase in the use of large-sized Deep Neural Networks (DNNs) over the years, specialized hardware accelerators such as Tensor Processing Unit and Eyeriss have been developed to accelerate the forward pass of the network. The essential component of these devices is an array processor which is composed of multiple individual compute units for efficiently executing Multiplication and Accumulation (MAC) operation. As the size of this array limits the amount of DNN processing of a single layer, the computation is performed in several batches serially leading to extra compute cycles along both the axes. In practice, due to the mismatch between matrix and array sizes, the computation does not map on the array exactly. In this work, we address the issue of minimizing processing cycles on the array by adjusting the DNN model parameters by using a structured hardware array dependent optimization. We introduce two techniques in this paper: Array Aware Training (AAT) for efficient training and Array Aware Pruning (AAP) for efficient inference. Weight pruning is an approach to remove redundant parameters in the network to decrease the size of the network. The key idea behind pruning in this paper is to adjust the model parameters (the weight matrix) so that the array is fully utilized in each computation batch. Our goal is to compress the model based on the size of the array so as to reduce the number of computation cycles. We observe that both the proposed techniques results into similar accuracy as the original network while saving a significant number of processing cycles (75%).

Due to an increase in the size of Deep Neural Networks (DNNs), special purpose hardware has gained prominence to accelerate the forward pass of the network like Google's Tensor Processing Unit (TPU) and Eyeriss. The heart of these accelerators is a Matrix Multiplication unit, which is based on systolic array architecture. This array processor has a grid-like structure, made of individual Processing Elements (PEs) that can be extended along row and column. A lot of work has been done on the computing array implementation and its reliability concerns in the past. However, their fault tolerance perspective with respect to DNNs is not yet fully understood with a fault model. We, in this paper, first present a fault model i.e., different sequences in which faults can occur on the array. We classify the fault modes into random, row, and column, and study their impact on the accuracy of DNNs followed by overheads of the mitigation strategies. Pruning is a process of removing redundant parameters in the model to decrease the network size for efficient performance. Although several pruning techniques have been developed to reduce the inference time on general-purpose and special-purpose systems, model compression (pruning) under faulty scenario has not yet been explored. In the second part of our work, we co-design a Fault based and Array size based Pruning (FPAP) algorithm with an intent of bypassing the faults and removing the internal redundancy at the same time for efficient inference. We compare our method with recent pruning methods under different fault scenarios and array sizes. We achieve a mean speedup of 4.2x where the baselines achieved 1.6x on ConvNet, NiN, AlexNet, VGG16 over Eyeriss in the case of random faults.

Deep Learning (DL), a subset of Artificial Intelligence (AI), is growing rapidly with possible applications in different domains such as speech recognition, computer vision etc. Deep Neural Network (DNN), the backbone of DL algorithms is a directed graph containing multiple layers with different number of neurons residing in each layer. The use of these networks has been increased in the last few years due to availability of large data sets and huge computation power. As the size of DNN is growing over the years, researchers have developed specialized hardware accelerators to reduce the inference compute time. An example of such domain specific architecture designed for Neural Network acceleration is Tensor Processing Unit (TPU) which outperforms GPU in the inference stage of DNN execution. The heart of this inference engine is a Matrix Multiplication unit which is based on systolic array architecture. The TPU's systolic array is a grid-like structure made of individual processing elements that can be extended along rows and columns. Due to external environmental factors or internal scaling of semiconductor, these systems are often prone to faults which leads to improper calculations and thereby resulting in inaccurate decisions by the DNN. Although a lot of work has been done in the past on the computing array implementation and it's reliability concerns, their fault tolerance behavior for DNN application is not very well understood. It is not even clear what would be the impact of various different faults on the accuracy. We in this work, first study possible mapping strategies to implement a convolution and dense layer weights on TPU systolic array. Next we consider various faults scenarios that may occur in the array. We divide these fault scenarios into low, high row and column faults (Fig. 1(a) pictorially represents column faults) modes with respect to the multiplication unit. Next, we study the impact of these fault models on the overall accuracy of the DNN performance on a faculty TPU unit. The goal is to study the resiliency and overcome the limitations of earlier work. The previous work was very effective in masking the random faults which used pruning of weights (removing weights or connections in the DNN) plus retraining to mask the faults on the array. However, it failed in the case of column faults which is clearly shown in Fig. 1(b). We also propose techniques to mitigate or bypass the row and column faults. Our mapping strategy follows physical_x(i) = i%N and physical_y(j) = j%N where (i,j) represents the index of dense (FC) weight matrix and (physical x(i), physical y(j)) indicates the actual physical location on the array of size N. The convolution filters are linearized with respect to every channel so as to convert them into proper weight matrix and mapped according to the previous mentioned policy. It was shown that DNNs can up to certain faults in the array while retaining the original accuracy (low row faults). The accuracy of the network decreases even with one column faults if it (column) is in the use. As per the results, it is proved that for the same number of row and column faults, the latter has most impact on the network accuracy because pruning input neuron has very little effect than pruning an output neuron. We experimented with three different networks and found the influence of these different faults to be the same. These faults can be mitigated using techniques like Matrix Transpose and Array Reduction which does not require retraining of weights. For low row faults, the original mapping policy can be retained such that weights can be mapped at their exact locations which does not affect the accuracy. Low column faults can be converted into low row faults by transposing the matrix. In the case of high row (column) faults, the entire row (column) has to be avoided to completely bypass the faulty locations. Static mapping of weights along with retraining the network on the array can be effective in the case of random faults. Adapting to change in the case of structured faults can reduce the burden of retraining which happens outside the TPU.

We consider the availability of applications in a large provider network environment. Our primary goal is to design a service provider network for high-availability using multiple components that have different availability. Initially, we model a modern provider architecture that is spread across the access, metro and core regions. We want to answer the specific question as to what amount of over-the-top (OTT) services can be provisioned over a given network while achieving a predesired availability value. To this end, we formulate a constrained optimization model whose objective is revenue maximization subject to availability measures. Two heuristics are also proposed that fathom the breadth of the virtual network function (VNF) deployment parameters: VNF licensing cost and server utilization. A simulation model presents comparative data for efficiency and server utilization as well as validates our optimization model. The results stress the importance of our optimization model in planning the network, as well as planning VNF placement ahead in time.

As DRAM technology continues to evolve towards smaller feature sizes and increased densities, faults in DRAM subsystem are becoming more severe. Current servers mostly use CHIPKILL based schemes to tolerate up-to one/two symbol errors per DRAM beat. Multi-symbol errors arising due to faults in multiple data buses and chips may not be detected by these schemes. In this paper, we introduce Single Symbol Correction Multiple Symbol Detection (SSCMSD) - a novel error handling scheme to correct single-symbol errors and detect multi-symbol ones. Here, we use a hash in combination with ECC to avoid silent data corruptions (SDCs). We employ 32-bit Spookyhash along with Reed-Solomon code to implement SSCMSD for a ×4 based DDRx system. Our simulations show that the proposed scheme effectively prevents SDCs in the presence of multiple symbol errors. For this design, we need 19 chips per rank (storage overhead of 18.75 percent), 76 data bus-lines and additional hash-logic at the memory controller.

All Pairs problems occur in many research fields. The all-pairs problem requires all data elements to be paired with all other data elements. With the advent of new data intensive big data applications and increase in data size, methods to reduce memory foot print and distribute to work equally across compute nodes are needed. In this paper, we propose cyclic quorum sets for all-pairs algorithm computations to reduce memory foot print. We show that the cyclic quorum sets have a unique all-pairs property that allows for minimal data replication. The cyclic quorums set based computing requires only N/√P size memory, up to 50 percent smaller than the dual N/√P array implementations proposed earlier, and significantly smaller than solutions requiring all data in each node. Computation can be distributed efficiently and more importantly and are communication-less after initial data distribution, which is a huge advantage in minimizing computation time. Scaling from 16 to 512 cores (1 to 32 compute nodes), our application experiments on a real dataset demonstrated scalability with greater than 150x (super-linear) speedup with less than 1/4th the memory usage per node in our experiments.

In this paper, we propose a greedy cycle direction heuristic to improve the generalized R redundancy quorum cycle technique. When applied using only single cycles rather than the standard paired cycles, the generalized R redundancy technique has been shown to almost halve the necessary light-trail resources in the network. Our greedy heuristic improves this cycle-based routing technique's fault-tolerance and dependability. For efficiency and distributed control, it is common in distributed systems and algorithms to group nodes into intersecting sets referred to as quorum sets. Optimal communication quorum sets forming optical cycles based on light-trails have been shown to flexibly and efficiently route both point-to-point and multipoint-to-multipoint traffic requests. Commonly cycle routing techniques will use pairs of cycles to achieve both routing and fault-tolerance, which uses substantial resources and creates the potential for underutilization. Instead, we use a single cycle and intentionally utilize R redundancy within the quorum cycles such that every point-to-point communication pairs occur in at least R cycles. Without the paired cycles the direction of the quorum cycles becomes critical to the fault tolerance performance. For this we developed a greedy cycle direction heuristic and our single fault network simulations show a reduction of missing pairs by greater than 30%, which translates to significant improvements in fault coverage.

We propose and design a new Block I/O schedulingscheme called Bulk I/O Dispatch (BID) suited for disk intensiveMapReduce applications. Large data access by such applicationsresult in a large number of block I/O requests which have thepotential to be sequentialized. However, due to contention byother applications and the way current I/O schedulers operate, the opportunities of a large sequential I/Os are missed. SequentialI/Os, which are faster than random I/Os, can lead to saving theCPU wait times and thus better application performance. The proposed scheduler is designed to work with all blockdevices which have superior sequential performance than random. Through simulation based experiments with MapReducebenchmarks we show that the proposed block I/O schedulerresults in about 27% to 52% lesser time for I/O than the currentlyavailable schedulers.

With increasing transistor density on a single chip, processor design in the nanoscale era is hitting power and frequency walls. Due to these challenges, processors not only need to run fast, but remain cool and consume less energy. At this juncture where no further improvement in clock frequency is possible, data dependent latching through timing speculation provides a silver lining. In this paper, (a) we present a novel power level switching mechanism using reliable and aggressive designs that support overclocking. Using the proposed framework, we achieve 40 percent speed-up and also observe 75 percent energy-delay squared product (ED2) savings relative to the base architecture. (b) showcase the loss of efficiency in current chip multiprocessor systems due to excess power supplied. We propose a utilization-aware task scheduling (UTS) - a power management scheme that increases energy efficiency of chip multiprocessors. (c) demonstrate that UTS along with aggressive timing speculation extracts ample performance from the system without loss of efficiency, and also without breaching power and thermal constraints. We demonstrate that UTS improves performance by 12 percent due to aggressive power level switching and over 50 percent in ED2savings in comparing to traditional power management techniques.

Segment routing has recently been proposed in the IETF towards making IP/MPLS networks service-oriented and efficient. Segment routing involves identifying paths at the source node using adjacency identifiers conjoined together to create a source-routed path. To this end, we propose a transport paradigm that will act as an enabler towards implementing segment routing in service provider networks. Specifically, we use Carrier Ethernet that is gaining acceptance as an IP/MPLS carrier technology. We propose the use of our modification of Carrier Ethernet called Omnipresent Ethernet (based on source routed binary labels embedded in an Ethernet frame) towards implementing segment routing. We evaluate segment routing for large service provider networks and understand scalability limitations of source routing. To absolve the scalability issues, a hierarchical segment routing (H-SR) scheme that uses special nodes called Swap-Nodes is proposed. Three techniques for swap-node selection based on centrality paradigms that facilitate and enhance scalability of segment routing are put forth. A test-bed is built to validate segment routing along with a simulation model to evaluate the proposed hierarchical segment routing scheme.

We present a novel approach to use mountain drainage patterns for GPS-Denied navigation of small unmanned aerial systems (UAS such as Scan Eagle), utilizing a down-looking fixed focus monocular imager. We leverage the analogy between mountain drainage patterns, human arteriograms, and human fingerprints. We match local drainage patterns to GPU-rendered parallax occlusion maps of offline geo-registered radar returns (GRRR) in real-time. We represent a given mountain area with a set of spatially distributed minutiae of drainage patterns so that conventional minutiae-based fingerprint matching approaches can be used. We use medical arteriography processing techniques to extract these patterns. The minutiae-based representation of mountains is achieved by exposing mountain ridges/valleys with a series of filters and then extracting mountain minutiae from these ridges/valleys. Effectiveness of minutiae-based mountain representation method is experimentally validated with no human interaction and no human-made geographic objects. Our research was in part funded by Rockwell Collins.

State-of-the-art in duplicate detection in semi-structured data obtains significant improvement by exploiting the schema-related knowledge. Such schema-bound duplicate detection approaches, however, have severe limitations when dealing with multi-sourced, heterogeneous, high-velocity data streams. In this paper, we propose a novel context-aware duplicate detection system which is workload- and complexity-aware, and is adaptable to the underlying computing platform. The system operates in schema-oblivious manner, and relies upon information theory based heuristic and data shaping technique for efficient, and scalable duplicate detection in multi-sourced, heterogeneous data sets. Experiments with real-world data sets show speed up of up to 8X over state of-the-art schemes, while maintaining upto 92 percent accuracy. In addition, our data shaping technique for GPGPU processing speeds up the duplicate detection throughput by up to two orders of magnitude.

Recent events have indicated that attackers are banking on side-channel attacks, such as differential power analysis (DPA) and correlation power analysis (CPA), to exploit information leaks from physical devices. Random dynamic voltage frequency scaling (RDVFS) has been proposed to prevent such attacks and has very little area, power, and performance overheads. But due to the one-to-one mapping present between voltage and frequency of DVFS voltage-frequency pairs, RDVFS cannot prevent power attacks. In this paper, we propose a novel countermeasure that uses reliable and aggressive designs to break this one-to-one mapping. Our experiments show that our technique significantly reduces the correlation for the actual key and also reduces the risk of power attacks by increasing the probability for incorrect keys to exhibit maximum correlation. Moreover, our scheme also enables systems to operate beyond the worst-case estimates to offer improved power and performance benefits. For the experiments conducted on AES S-box implemented using 45 nm CMOS technology, our approach has increased performance by 22 percent over the worst-case estimates. Also, it has decreased the correlation for the correct key by an order and has increased the probability by almost 3.5X times for wrong keys when compared with the original key to exhibit maximum correlation.

The threat of soft error induced system failure in computing systems has become more prominent, as we adopt ultradeep submicron process technologies. In this paper, we propose two efficient soft error mitigation schemes, namely, Soft Error Mitigation (SEM) and Soft and Timing Error Mitigation (STEM), using the approach of multiple clocking of data for protecting combinational logic blocks from soft errors. Our first technique, SEM, based on distributed and temporal voting of three registers, unloads the soft error detection overhead from the critical path of the systems. SEM is also capable of ignoring false errors and recovers from soft errors using in-situ fast recovery avoiding recomputation. Our second technique, STEM, while tolerating soft errors, adds timing error detection capability to guarantee reliable execution in aggressively clocked designs that enhance system performance by operating beyond worst-case clock frequency. We also present a specialized low overhead clock phase management scheme that ably supports our proposed techniques. Timing-annotated gate-level simulations, using 45 nm libraries, of a pipelined adder-multiplier and DLX processor show that both our techniques achieve near 100 percent fault coverage. For DLX processor, even under severe fault injection campaigns, SEM achieves an average performance improvement of 26.58 percent over a conventional triple modular redundancy voter-based soft error mitigation scheme, while STEM outperforms SEM by 27.42 percent.

A cycle could support a SONET ring, a reliable multicast, a multipoint to multipoint traffic request, or service as a dependable connection, backup paths for requested number of pairwise connection or be used as a p-cycle. In this paper we develop a novel and efficient heuristic to find a cycle in a mesh network that includes a specified set of nodes. We allow links to be used only once in a cycle whereas a node may appear multiple times. This cycle, called a non-simple cycle, reduces the total number of links required to form the cycle. The simulation results show that the proposed heuristic outperforms other cycle finding heuristic algorithms like Optimized Collapsed Ring (OCR) and Enumeration in terms of percent blocking.

We consider routing multicast traffic requests originating in a hierarchical optical network architecture with multiple access networks attached to a core network. A request originates in a source access network (also called collection network) and include multiple destinations in different access networks (also called distribution networks). We call them together as collection-distribution networks (CDN). The connection points between a CDN and the core network is an edge node which can groom several multicast connections together. In such an architecture, given a set of multicast requests, our goal is to maximize the amount of multicast destinations and bandwidth served. Therefore, we formulate an optimization problem with an objective of maximizing the product of bandwidth-number of destinations according to partial multicast service discipline. We show that this is an NP-hard problem and present a suboptimal and a heuristic algorithm. We develop a lower bound on the performance. We present numerical results and show that our algorithms achieve a very close performance to the lower bound.

We consider scheduling resources on linear networks where each request is for a set of contiguous resources and for a different amount of time. Allocating spectrum to satisfy variable size data communication requests, utilizing linear resource on a light-trail network for higher efficiency, scheduling communication path for a segmented light-trails network or a multi-hop network with no intermediate storage (receive and forward paradigm), or allocating resources on any linear pipeline, would benefit from such a resource allocation scheme which is proposed here. The problem is similar to a two-dimensional bin packing problem, which is known to be NP-hard, but with an additional constraint that one coordinate location for an object is already fixed. That makes the problem different and interesting to solve. We develop an efficient algorithm and show that it find minimal length schedule with very high probability and demonstrate that a minimum length schedule is not determined by the usage durations of individual resources.

Light-trails based solutions have been proposed and demonstrated as a means of traffic grooming and optical multicasting in a LAN/MAN, where multiple nodes use time division multiple access on a unidirectional optical bus. When compared to light paths or having nodes relaying traffic using optical-electronic-optical conversion there are advantages and disadvantages to light-trails in terms of bandwidth, hardware requirements and latency. Given that a light-trail of a specific length has been identified, we develop an approach to increase its capacity utilization. In particular, we show that splitting a longer light-trail in shorter segments results into more effective and efficient utilization of bandwidth. However, we do not believe that splitting a light-trail into segments of lengths one is preferable as it will increase the overall delay.

The merging, management and utilization of pervasive, idle computing devices using a dynamic communication infrastructure leads to the concept of computational grids. A computational grid enables enterprises to efficiently use distributed computing entities in a cost-effective setup for emerging com

The threat of soft error induced system failure in high performance computing systems has become more prominent, as we adopt ultra-deep submicron process technologies. In this paper, we propose two techniques, namely soft error mitigation (SEM) and soft and timing error mitigation (STEM), for protecting combinational logic blocks from soft errors. Our first technique (SEM), based on distributed and temporal voting of three registers, unloads the soft error detection overhead from the critical path of the systems. Our second technique (STEM) adds timing error detection capability to guarantee reliable execution in aggressively clocked designs that enhance system performance by operating beyond worst-case clock frequency. We also present a specialized low overhead clock generation scheme that ably supports our proposed techniques. Timing annotated gate level simulations, using 45 nm libraries, of a pipelined adder-multiplier and DLX processor show that both our techniques achieve near 100% fault coverage. For DLX processor, even under severe fault injection campaigns, SEM achieves an average performance improvement of 26.58% over a conventional triple modular redundancy voter based soft error mitigation scheme, while STEM outperforms SEM by 27.42%.

LiTPiCs were proposed as a marriage of two innovative technologies - light-trails and photonic integrated circuits - as a solution to extend metro networks in regional domains and provide dynamism in bandwidth allocation for emerging services. Light-trails which are a generalized lightpath, essentially formed by an optical bus provide sub-wavelength optical grooming and facilitate dynamic bandwidth allocation amongst constituent nodes. Communication within a light-trail is all-optical thereby limiting their reach to a few node-spans. In parallel, photonic integrated circuits were developed that proposed the system on a chip concept enabling 3R regeneration of optical signal using embedded lasers and receivers on a single Indium Phosphide substrate. PIC technology has given rise to the concept of digital optical networks which have the capability to increase reach and commoditize metro networks. By conjoining the light-trail and PIC technologies we proposed LiTPiC which is essentially preserves light-trail properties while enhancing their reach. In this paper we study algorithms for scheduling traffic in a LiTPiC. We consider both the static case and the dynamic case - when traffic is known and not known apriori. Further we will establish a lower and upper bound that would facilitate an evaluation procedure of our algorithms.

This paper presents a novel indoor navigation and ranging strategy by using a monocular camera. The proposed algorithms are integrated with simultaneous localization and mapping (SLAM) with a focus on indoor aerial vehicle applications. We experimentally validate the proposed algorithms by using a fully self-contained micro aerial vehicle (MAV) with on-board image processing and SLAM capabilities. The range measurement strategy is inspired by the key adaptive mechanisms for depth perception and pattern recognition found in humans and intelligent animals. The navigation strategy assumes an unknown, GPS-denied environment, which is representable via corner-like feature points and straight architectural lines. Experimental results show that the system is only limited by the capabilities of the camera and the availability of good corners.

Look-up table based FPGAs have migrated from a niche technology for design prototyping to a valuable end-product component and, in some cases, a replacement for general purpose processors and ASICs alike. One way architects have bridged the performance gap between FPGAs and ASICs is through the inclusion of specialized components such as multipliers, RAM modules, and microcontrollers. Another dedicated structure that has become standard in reconfigurable fabrics is the arithmetic carry chain. Currently, it is only used to map arithmetic operations as identified by HDL macros. For non-arithmetic operations, it is an idle but potentially powerful resource

This paper considers link based protection where backup capacity is preconfigured into various patterns. When the amount of backup capacity available on a link is constrained, the choice of patterns under consideration can determine if a given network is protectable. This paper gives an ILP that can be used in calculating preconfigurations, even when p-Cycles with p-lines or non-simple p-Cycles alone may not be able to. This ILP includes constraints that will cause backup capacity to be distributed in a somewhat even fashion when possible. When considering networks with dynamic traffic, this may offer the advantage of lower blocking probability over schemes that concentrate backup capacity on a few links. The advantage is demonstrated by a simulation of NSFnet comparing blocking probability of a distribution computed by this ILP vs. a Hamiltonian p-Cycle which is a capacity optimal way to protect the network.

Traffic grooming continues to be a rich area of research in WDM optical networks. In this paper, we identify four kinds of path level traffic aggregation/grooming strategies - point to point (P2P), point to multi-point (P2MP), multi-point to point (MP2P), and multi-point to multi-point (MP2MP). We develop an auxiliary graph based approach as a generic network dimensioning solution for these architectures. Using our model, we compare the performance of various architectures employing path level aggregation in both single hop and multi-hop scenarios. For the studied scenarios, we observe the following - (1) MP2MP outperforms other architectures by multiple orders of magnitude in single hop networks, (2) P2P performs the best in multi-hop transceiver constrained scenarios, and (3) P2MP performs the best in multi-hop wavelength constrained scenarios.

Energy management is the key issue in the design and operation of wireless network applications like sensor networks, pervasive computing and ubiquitous computing where the network is primarily driven by battery-powered embedded devices. This paper studies network coding as an energy minimization technique. Network coding reduces the energy consumption by minimizing the number of transmissions required to communicate a given amount of information across the network. However, aggressive application of network coding adversely affects the network lifetime. We illustrate this trade off in this paper, and show that the existing throughput based network coding approaches cannot be applied to energy-constrained networks. Specifically, we address the following routing problem. Given a set of traffic demands the goal is to route the demands across the network with the objective of minimizing the total energy consumption while providing guarantees on the lifetime of individual nodes. This paper studies multi-path variation of the above routing problem. We present analytical formulations to solve the problem optimally. Evaluation results indicate that the proposed solution is 35% more energy efficient than no-network- coding solution while still meeting required lifetime constraints.

Reliability has become a serious concern as systems embrace nanometer technologies. In this paper, we propose a novel approach for organizing redundancy that provides high degree of fault tolerance and enhances performance. We replicate both the pipeline registers and the pipeline stage combinational logic. The replicated logic receives its inputs from the primary pipeline registers while writing its output to the replicated pipeline registers. The organization of redundancy in the proposed conjoined pipeline system supports overclocking, provides concurrent error detection and recovery capability for soft errors, intermittent faults and timing errors, and flags permanent silicon defects. The fast recovery process requires no checkpointing and takes three cycles. Back annotated post-layout gate level timing simulations, using 45 nm technology, of a conjoined two stage arithmetic pipeline and a conjoined five stage DLX pipeline processor, with forwarding logic, show that our approach achieves near 100% fault coverage, under a severe fault injection campaign, while enhancing performance, on an average by about 20%, when dynamically overclocked and 35%, when maximally overclocked.

Capacity Balanced Efficient Protection and Grooming Architecture for Optical Networks

Synchronous circuits are typically clocked considering worst case timing paths so that timing errors are avoided under all circumstances. In the case of a pipelined processor, this has special implications since the operating frequency of the entire pipeline is limited by the slowest stage. Our goal, in this paper, is to achieve higher performance in superscalar processors by dynamically varying the operating frequency during run time past worst case limits. The key objective is to see the effect of overclocking on superscalar processors for various benchmark applications, and analyze the associated overhead, in terms of extra hardware and error recovery penalty, when the clock frequency is adjusted dynamically. We tolerate timing errors occurring at speeds higher than what the circuit is designed to operate at by implementing an efficient error detection and recovery mechanism. We also study the limitations imposed by minimum path constraints on our technique. Experimental results show that an average performance gain up to 57% across all benchmark applications is achievable.

Recent research has focused on designing new architectures and protocols for pure optical grooming without resorting to fast optical switching. This is achieved in three steps: (1) the circuit is configured in the form of a path or a tree (2) optical devices like couplers/splitters are used to allow a wavelength to aggregate traffic from multiple transmitters and/or receivers through one of the following means - point to point, point to multi-point, multi-point to point and multipoint to multi-point (3) an arbitration mechanism is provided to avoid contention among end users of the circuit. In this paper, we focus on design of mesh networks that aggregate traffic at the path level. We develop a shared, mixed protection algorithms for guaranteed survival from single link failures in the context of dynamic traffic for mesh networks. Based on our simulations on random graphs, we conclude that light-trails, that enable multi-point to multi-point aggregation, performs multiple orders of magnitude better than lightpaths that allow point to point aggregation.

High efficiency in capacity utilization and fast restoration are two primary goals of survivable design in optical networks. Shared backup path protection has been shown to be efficient in terms of capacity utilization, due to the sharing of backup capacity. However, sharing of backup capacity also complicates the restoration process, and leads to slow recovery. Ring-type protection in mesh topology, on the other hand, has the advantage of fast restoration. The p-cycle scheme is the most efficient ring-type protection method in terms of capacity utilization. Recently, the concept of pre-cross-connected protection was proposed to increase the recovery speed of shared path protection. We overview these protection methods and their failure recovery processes. The recovery time of these schemes are compared analytically. To compare the capacity efficiency, we formulate integer programming optimization problems for three protection methods in static traffic scenario, considering wavelength continuity constraint. We investigate the effect of network connectivity on the performance of capacity utilization of the methods by experimenting on topologies with different average nodal degrees.

Reconfigurable fabrics cater to a wide variety of applications, but have adopted specialized components to allow efficient implementation of performance-critical arithmetic operations. Carry chains have been integrated into the fabric typically as an optimized ripple-carry chain. However, in non-arithmetic operations the carry chain goes unused, when it could be a valuable adjacent-cell interconnect resource. This paper presents a cell architecture facilitating reuse, as well as an analysis of the potential benefits of reuse for an sampling of common of algorithms using commercial FPGAs. Technology map experiments indicate that a variety of applications can benefit from reuse, with utilized routing resources reduced by up to 13% and maximum clock frequency increased by up to 47%.

Traffic grooming continues to be a rich area of research in the context of WDM optical networks. We provide an overview of the optical and electronic grooming techniques available with focus on IP as the client layer. We discuss the various architectural alternatives available: peer, overlay and augmented models. We first provide a survey on the research work in the area of traffic grooming in optical circuit switched networks. We then identify problems with electronic grooming in terms of high speed router design and bring out the merits of optical grooming. Next, we describe the shared wavelength optical network technology called light-trails and compare its performance with electronic grooming networks for both the peer and overlay models. Based on our simulations on random graphs of various diameters, we identify the threshold router speeds at which light-trails can compete with the electronic grooming solution for a given network scenario. We conclude that since the present router capacities are below the threshold speed or such routers are likely to remain expensive for some time, light-trails is an appealing candidate solution.

In this paper, we consider a circuit-switched optical wavelength division multiplexed (WDM) network that offers protection services to the connections established in the network. A dynamic traffic model, where connection requests arrive based on some stochastic arrival process, is considered. In earlier work, the notion of partial protection was introduced for a WDM network with sub-wavelength capacity allocation capabilities, as in TDM-WDM networks, for a dynamic traffic model. Here, instead of setting up a backup path with the same capacity as the primary, the backup path is established with capacity that is less than the primary path's capacity, where the amount of backup path capacity is specified by the user. Intuitively, this will reduce backup path requirements, thereby increasing the number of connections accepted. In (J. Fang et al., 2005), the mechanism presented attempted to provide the maximum available protection bandwidth while ensuring that the minimum backup requirements are met. However, this can still result in wasted protection bandwidth if failures do not occur. In this paper, we present a mechanism to further improve the performance of partial protection schemes for dynamic traffic. When failure occurs, the connection is carried on the backup with reduced capacity. However, the system tries to identify additional spare capacity on the same backup path, on either the same wavelength or a different wavelength. The objective is to increase the amount of backup capacity at the time of failure, so that the connection's end user does not see a noticeable drop in bandwidth allocated. We present a heuristic connection admission control algorithm that prevents backup contention that occurs when backup paths of connections affected by a failure contend (share) for resources. A detailed performance evaluation of the mechanisms for different network topologies and other system parameters is presented. For one of the cases studied, the connection acceptance probability is increased from 95% to 99%, while providing nearly 100% backup capacity, when failure occurred. The mechanism proposed to counter backup contention is seen to provide an average of 120% reduction in the contention among backup paths of connections traversing a link, especially when the number of wavelengths in each link is small.

Ripple-carry architectures are the norm in today's reconfigurable fabrics. They are simple, require minimal routing, and are easily formed across arbitrary cells in a fabric. However, their computation delay grows linearly with operand width. Many different fabric carry-chains have been presented in literature offering non-linear delays, but generally require a significant investment in routing and processing area. Carry-skip chains are well-known in arithmetic logic design, and although they too possess a linear delay, their performance is 2times or more faster than simple ripple-carry schemes. They require an expanded carry chain and minimal extra logic, but offer impressive speed-ups for arithmetic. This paper presents a reconfigurable cell that supports carry-skip arithmetic using a multi-bit carry chain achieving 2 middot k middot b+ n/b performance, where b is the block size and k is an architecture constant. The cell is specialized for arithmetic and Boolean operations with reduced configuration memory. Additional resources are provided to reuse the multi-bit carry chain for 3-source operand arithmetic to explore how multi-bit chains can be reused

Wireless sensor networks consist of a group of nodes, each equipped with sensing, actuating, computation, communication, and storage resources. These sensor nodes are powered by batteries, which are considered as limited resources. Many applications of sensor networks, such as surveillance systems in both civil and military area, habitual monitoring etc., won't allow the replacement of battery supplies. Therefore, to reduce the energy consumption is the key to prolong the lifetime of sensor networks. In this paper, we present two energy efficient data gathering models to achieve longer lifetime in a structured multiclustered topology. The local homogeneous sensor nodes are grouped together to form clusters and a special processing and relaying node is designated to be responsible for communication among local groups. Such models are developed for power transmission line monitoring systems. The goal is to achieve uninterrupted monitoring over a long time using power constrained sensor nodes because the replacement of battery is a major issue in such applications. We use Markov chain process to analyse the proposed two models and comparison shows that the two level communication model consumes less power and is more suitable than single level communication model on the power transmission line monitoring systems.

We investigate the characteristics and performance of architectures that allow statistical sharing of wavelengths in the optical layer. The bandwidth of a light-wave circuit can be shared in the optical layer by multiple nodes that are along a linear path in a network through the inclusion of simple but flexible hardware overlaid with control software. We consider three types of architectures - lightpath (LP), light-trail (LT) and source based light-trail (SLT) networks. The three differ in their level of optical sharing, in their hardware and software requirements and in their performance. We study the interplay between statistical sharing at the optical layer and circuit switched sharing at the electronic layer. We develop a generic auxiliary graph model for traffic grooming in heterogeneous WDM mesh networks that can accommodate constraints related to transceivers, wavelengths, and groomers for architectures with different levels of statistical sharing and for both static and dynamic scenarios. We conclude based on our simulation results that sharing wavelength in the optical domain is beneficial and can lead to reduced blocking

Internet computing is emerging as an important new distributed computing paradigm in which resource intensive computing is integrated over Internet-scale networks. Over these large networks, different users and organizations share their computing resources, and computations take place in a distributed fashion. In such an environment, a framework is needed in which the resource providers are given incentives to share their resources. CompuP2P is a lightweight architecture for enabling Internet computing. It uses peer-to-peer networks for sharing of computing resources. CompuP2P create dynamic markets of network accessible computing resources, such as processing power, memory storage, disk space, etc., in a completely distributed, scalable, and fault-tolerant manner. This paper discusses the system architecture, functionality, and applications of the proposed CompuP2P architecture. We have implemented a Java-based prototype, and our results show that the system is light-weight and can provide almost a perfect speedup for applications that contain several independent compute-intensive tasks

The Radon transform (RT) is a widely studied algorithm used to perform image pattern extraction in fields such as computer graphics, medical imagery, and avionics. Real time implementation of the discrete RT (DRT) is extremely difficult due to its use of complex trigonometric functions and O(N/sup 3/) time complexity, making its use in video applications difficult. A O(N/sup 2/lgN) approximate discrete (ADRT) has been presented in literature (Brady, 1998) that allows highly parallel computation. This paper presents an architecture that uses the ADRT to create a computation architecture known as the xADRT. Performance analysis indicates that it can achieve a refresh rate of 10 frames per second for use in real time image processing applications.

We explore network design principles for next-generation all-optical wide-area networks, employing light-trail technology. Light-trail is a light-wave circuit that allows multiple nodes to share the optical bandwidth through the inclusion of simple but flexible hardware overlaid with a lightweight control protocol. We develop light-trails as a novel and amenable control and management solution to address IP-centric communication problems at the optical layer. We propose optical switch architectures that allow seamless integration of lightpath and light-trail networks, and assess their costs and capabilities. We formulate the static light-trail RWA problem as an integer linear program. Since this programming problem is computationally intractable, we split it into two subproblems: (a) trail routing, for which we provide three heuristics, (b) wavelength assignment, for which we use the largest first heuristic available in literature. The objective of our design is to minimize the optical layer and electronic layer costs in terms of the number of wavelengths and communication equipment required. We illustrate our approach by comparing the performance of our trail design heuristics on some test networks.

The peer-to-peer technology offers many advantages, but at the same time, it poses many novel challenges for the research community. Modern peer-to-peer systems are characterized by large scale, poor reliability, and extreme dynamism of the participating nodes, with a continuous flow of nodes joining and leaving the systems. Selection of an optimal network requires estimation of its rank using attributes such as storage, average load, cost, reliability etc. There are multiple networks, each vying for users business by providing them novel services. The user in turn has to decide which network best meets its service requirements and accordingly join a network. In this paper, we propose a model with two ranking schemes, one being network-specific and the other user-specific. The schemes use fuzzy logic to rank different networks based on their attributes. The difference between the two ranking schemes lie in the dynamism offered by them. The user-specific ranking criteria is flexible while the network-specific scheme uses a fixed criteria. The network-specific scheme helps in providing a structure to visualize the overall performance index of the networks. The user-specific scheme is adaptive in the sense that it caters to the specific needs of the users. The simulations performed by us show that the two schemes are light-weight, highly accurate and easily implementable

Internet computing is emerging as an important new paradigm in which resource intensive computing is integrated over Internet-scale networks. Over these large networks, different users and organizations share their computing resources, and computations take place in a distributed fashion. In such an environment, a framework is needed in which the resource providers are given incentives to share their resources. CompuP2P is a light weight architecture for enabling Internet computing. It uses peer-to-peer networks for sharing of computing resources. CompuP2P create dynamic markets of network accessible computing resources, such as processing power, memory storage, disk space, etc., in a completely distributed, scalable, and fault-tolerant manner. This paper discusses the system architecture, functionality, and applications of the proposed CompuP2P architecture. We have implemented a Java based prototype, and our results show that the system is light-weight and can provide almost a perfect speedup for applications that contain several independent compute-intensive tasks

In this paper, we consider the problem of survivable network design in traffic groomed optical WDM mesh networks with sub-wavelength capacity connections. In typical survivable network designs, individual sessions are provided either full protection or no protection. We consider a quality of protection (QoP) framework where a connection is provided partial protection, i.e. when a link failure occurs on the primary path, the protection bandwidth provided on the backup path is less than or equal to the primary bandwidth. Each connection request specifies the primary bandwidth and a minimum backup bandwidth required. The network will guarantee at least the minimum backup bandwidth and, if capacity is available, higher backup bandwidth up to the primary path's bandwidth. The advantage of such a model is that it can reduce backup capacity requirements based on connection needs leading to lower blocking probability and lower network costs. We consider two scenarios: (i) a network with static traffic and formulate the problem of providing partial protection in groomed networks as an integer linear program (ILP); and (ii) a network with dynamic traffic that is analyzed using discrete-event simulation models. The results quantify the gain in blocking probability for different partial protection scenarios.

Achieving both high capacity efficiency and fast restoration speed is a primary goal of survivable design in WDM network. The p-cycle method aims to benefit from the fast restoration of ring-like protection and high capacity efficiency of mesh protection. In this paper, we first present a p-cycle based method to deal with dynamic traffic in survivable WDM network design. In this method, we first find an optimal set of p-cycles for the given network topology. Next, we propose three routing strategies for accommodating dynamic requests upon their arrival time. The performance of our p-cycle based design using different routing strategies are compared with that of the shared backup path protection (SBPP). The results show that proposed p-cycle based design method performs better than SBPP in dense networks. Whereas SBPP performs better than the p-cycle based design in sparse networks.

Recently, a new architecture called light-trails has been proposed that provides a novel control and management solution to address IP-centric issues at the optical layer. By inclusion of simple hardware that performs drop and continue functionality, overlaid with a light-weight control protocol, light-trails enable efficient sharing of network resources, improve bandwidth utilization and minimize network costs. Due to power budget constraints in such networks, it may not always be possible to have end to end communication in pure optical domain and requests may be required to traverse multiple intermediate transit points called hub nodes before reaching the final destination. The hub nodes need to be equipped with special hardware for switching and grooming connections. We investigate the problem of designing networks where such hubs are sparsely located. We show through our simulation results that by carefully designing heuristics for hub node placement and trail routing, it is possible to achieve high throughput with minimal number of hub nodes.

The light-trail architecture provides a novel solution to address IP-centric issues at the optical layer. By incorporating drop and continue functionality, overlaid with a lightweight control protocol, light-trails enable efficient sharing of network resources, support subwavelength traffic and minimize costs. In this work, we investigate network design and survivability issues in such networks in the presence of multi-granularity subwavelength traffic subject to nonbifurcation constraints. We first establish the NP-Hardness of the light-trail routing problem by reduction from a Hamiltonian path problem. We propose three heuristics for lighttrail network design and study their performance with limited network resources. We observe the effect of tunable and fixed transceiver equipment on network throughput. We observe that our heuristics yield excellent wavelength utilization under moderate to high loads even in the presence of heavily fractional traffic.We propose two additional heuristics for shared and dedicated protection and conclude that with only a modest amount of spare capacity, full protection can be achieved for all single link failures.

An important issue in modern cache designs is bridging the gap between wire and device delays. This warrants the use of more regular and modular structures to mask wire latencies. This paper advances the basic concepts of shadow caching to offer protection against both data corruption and micro-network disruption in partitioned architectures. Network disruption is tolerated by sending shadow packet along a different route than the original packet, whereas the data corruption problem is addressed by reserving a small portion of the overall cache capacity for in-cache shadow space. Our results show that an average of 96% in data error coverage for Spec2K benchmarks can be achieved and more than 99% of the transient faults on the underlying switched micro-network can also be protected while incurring less than 3% performance degradation in most of the above benchmarks.

One of the central issues in router performance is IP address lookup based on longest prefix matching. IP address lookup algorithms can be evaluated on a number of metrics-lookup time, update time, memory usage, and to a less important extent, the time to construct the data structure used to support lookups and updates. Many of the existing methods are geared toward optimizing a specific metric, and do not scale well with the ever expanding routing tables and the forthcoming IPv6 where the IP addresses are 128 bits long. In contrast, our effort is directed at simultaneously optimizing multiple metrics and provide solutions that scale to IPv6, with its longer addresses and much larger routing tables. In this paper, we present two IP address lookup schemes-Elevator-Stairs algorithm and logW-Elevators algorithm. For a routing table with N prefixes, The Elevator-Stairs algorithm uses optimal O(N) memory, and achieves better lookup and update times than other methods with similar memory requirements. The logW-Elevators algorithm gives O(logW) lookup time, where W is the length of an IP address, while improving upon update time and memory usage. Experimental results using the MAE-West router with 29 487 prefixes show that the Elevator-Stairs algorithm gives an average throughput of 15.7 Million lookups per second (Mlps) using 459KB of memory, and the logW-Elevators algorithm gives an average throughput of 21.41Mlps with a memory usage of 1259KB.

The effects of an attack connection can propagate quickly to different parts of an all-optical transparent network. Such attacks affect the normal traffic and can either cause service degradation or outright service denial. Quick detection and localization of an attack source can avoid losing large amounts of data in an all-optical network. Attack monitors can collect the information from connections and nodes for diagnostic purpose. However, to detect attack sources, it is not necessary to put monitors at all nodes. Since those connections affected by the attack connection would provide valuable information for diagnosis, we show that by placing a relatively small number of monitors on a selected set of nodes in a network is sufficient to achieve the required level of performance. However, the actual monitor placement, routing, and attack diagnosis are challenging problems that need research attention. In this paper, we first develop our models of crosstalk attack and monitor node. With these models, we prove the necessary and sufficient condition for one-crosstalk-attack diagnosable networks. Next, we develop a scalable diagnosis method which can localize the attack connection efficiently with sparse monitor nodes in the network.

Failure resilience is one of the desired features of the Internet. Most of the traditional restoration architectures are based on single-failure assumption which is unrealistic. Multiple link failure models, in the form of shared-risk link groups (SRLG's) and shared risk node groups (SRNG's) are becoming critical in survivable optical network design. We classify both these form of failures under a common heading of shared-risk resource groups (SRRG) failures. In our research, we propose graph transformation techniques for tolerating multiple failures arising out of shared resource group (SRRG) failures. Diverse routing in such multi-failure scenario essentially necessitates finding out two paths between a source and a destination that are SRRG disjoint. The generalized diverse routing problem has been proved to be NP-complete. The proposed transformation techniques however provide a polynomial time solution for certain restrictive failure sets. We study how restorability can be achieved for dependent or shared risk link failures and multiple node failures and prove the validity of our approach for different network scenarios.

The enabling technology for supporting IP centric traffic over optical transport networks evolves as the amount of traffic grows. In this paper, we first review a recently proposed concept called light trails. Light trails can enable high speed provisioning, accommodate multigranularity traffic, support high data rates and offer a good candidate for carrying IP traffic over optical networks. Next, we focus on light trail design. We propose a two-step approach for solving the light trail design problem. The first step is called traffic matrix preprocessing, it divides single long hop paths into several shorter paths that satisfy the hop-length constraint. In the second step, the light trail design problem is formulated as an integer linear programming (ILP) optimization problem. The results obtained from our experiments show that the resulting light trail network has high wavelength utilization.

Double link failure models, in which any two links in the network fail in an arbitrary order, are becoming critical in survivable optical network design. A significant finding is that designs offering complete dual-failure restorability require almost triple the amount of spare capacity. In this paper, networks are designed to achieve 100% restorability under single link failures, while maximizing coverage against any second link failure in the network. In the event of a single link failure, the restoration model attempts to dynamically find a second alternate link-disjoint end-to-end path to provide coverage against a sequential overlapping link failure. Sub-graph routing (M. T. Frederick et al., Feb. 2003) is extended to provide dual-failure restorability for a network provisioned to tolerate all single-link failures. This strategy is compared with shared-mesh protection. The results indicate that sub-graph routing can achieve overlapping second link failure restorability for 95-99% of connections. It is also observed that sub-graph routing can inherently provide complete dual-failure coverage for ~72-81% of the connections

Large register file with multiple ports, but with a minimal access time, is a critical component in a superscalar processor. Analysis of the lifetime of a logical to physical register mapping reveals that there are long latencies between the times a physical register is allocated, consumed, and released. In this paper, we propose a TriBank register file, a novel register file organization that exploits such long latencies, resulting in a larger register bandwidth and a smaller register access time. Implementation of the TriBank register file organization, as compared to a conventional monolithic register file in an 8-wide out-of-order issue superscalar processor reduced the register access time up to 34%, even while enhancing the throughput in instructions per cycle (IPC) by 3% and 14%, for SpecInt2000 and SpecFP2000, respectively.

We propose a reputation management framework for large-scale peer-to-peer (P2P) networks, wherein all nodes are assumed to behave selfishly. The proposed framework has several advantages. It enables a form of virtual currency, such that the reputation of nodes is a measure of their wealth. The framework is scalable and provides protection against attacks by malicious nodes. The above features are achieved by developing trusted communities of nodes whose members trust each other and cooperate to deal with the problem of nodes' selfishness and possible maliciousness.

The demand for higher computing power and, thus, more on-chip computing resources; is ever increasing. The size of on-chip cache memory has also been consistently increasing to keep up with developments in implementation technology. However, some applications may not utilize full cache capacity and, on the contrary, require more computing resources. To efficiently utilize silicon real-estate on the chip, we exploit the possibility of using a part of cache memory for computational purposes to strike a balance in the usage of memory and computing resources for various applications. In an earlier part of our work, the idea of adaptive balanced computing (ABC) architecture was evolved, where a module of an L1 data cache is used as a coprocessor controlled by main processor. A part of an L1 data cache is designed as a reconfigurable functional cache (RFC) that can be configured to perform a selective core function in the media application whenever such computing capability is required. ABC architecture provides speedups ranging from 1.04x to 5.0x for various media applications. We show that a reduced number of cache accesses and lesser utilization of other on-chip resources, due to a significant reduction in execution time of application, will result in power savings. For this purpose, we first develops a model to compute the power consumed by the RFC while accelerating the computation of multimedia applications. The results show that up to a 60 percent reduction in power consumption is achieved for MPEG decoding and a reduction in the range of 10 to 20 percent for various other multimedia applications. Besides, beyond the discussions in earlier work on ABC architecture, we present a detailed circuit level implementation of the core functions in the RFC modules. Further, we go much further and study the impact of converting the conventional cache into RFC on both access time and energy consumption. The analysis is performed on a wide spectrum of cache organizations with size varying from 8KB to 256KB for varying set associativity.

Traffic grooming in optical networks employing wavelength division multiplexing (WDM) has gained prominence due to the prevailing disparity between the user requirement and wavelength capacity. Nodes in an optical network get upgraded to the latest grooming technology slowly with time. Hence, WDM grooming networks are expected to employ heterogeneous grooming architectures. In this paper, we develop an analytical model to evaluate the blocking performance of WDM grooming networks with heterogeneous grooming capabilities. We demonstrate the accuracy of the analytical model by comparing the analytical results with that of the simulation. We observe that analytical models with and without precise knowledge of the grooming architectures predict similar performance. The proposed analytical model can be employed by resource placement algorithms that identify a set of nodes and links that need to be upgraded when the resources are limited.

We consider the effect of multiple fibers on wavelength division multiplexing networks without wavelength conversion. We study networks with dynamic wavelength routing and develop accurate analytical models to compare various possible options using single- and multiple-fiber networks. We use results of an analytical model and simulation-based studies to evaluate the blocking performance and cost of multifiber networks. The number of fibers required providing high performance in multifiber networks and their costs are compared. A case is made for using multiple fibers in each link with fewer wavelengths instead of using a single fiber with many wavelengths. In particular, we show that a network with four fibers per link and with four wavelengths on each fiber without any wavelength conversion on any node yields similar same performance as the networks with one fiber per link and 16 wavelengths per fiber on each link and with full wavelength conversion capability on all nodes. In addition, the multifiber network may also offer the cost advantage depending on the relative cost of components. We develop a parametric cost model to show that multiple fibers in each link are an attractive option. Finally, such multifiber networks also has fault tolerance, with respect to a single fiber failure, already built into the system.

The explosion of data traffic and the availability of huge bandwidth using WDM optical network make it important to study optical layer networking restoration design. This paper addresses problem of enabling traffic grooming in mesh survivable WDM optical network design. Traffic grooming in optical network is defined as the act of multiplexing, demultiplexing and switching lower rate traffic onto high capacity lightpaths. The path selection and wavelength assignment schemes are formulated as integer linear programming (ILP) optimization problems. Two exact formulations are given for employing backup multiplexing and dedicated backup reservation with minimizing the total link-primary-sharing.

We consider path-based protection methods for two-link failures in mesh optical networks. Two link-disjoint backup paths are pre-computed for each source and destination node pair. We identify the scenarios where the backup paths can share their wavelengths without violating 100% restoration guarantee (backup multiplexing). We use integer programming to optimize the total capacity requirement for both dedicated-and shared-path protection schemes. Our results indicate that backup multiplexing significantly improves the efficiency of total capacity utilization. For the randomly generated demand sets, the shared-path scheme provides up to 37.5% saving in total capacity utilization over dedicated-path scheme. Backup multiplexing provides more saving for the demand set that has connection requests distributed more evenly. For the double link failure recovery methods, path-based methods are more efficient in capacity utilization than link-based methods. Dedicated-path scheme performs better than shared-link scheme in total capacity utilization on average.

An all-optical network (AON) is a network in which data does not undergo optical-to-electrical and electrical-to-optical conversion within the network. Transparency and non-regeneration features make attack detection and localization in AONs difficult. Among all attack methods, crosstalk attack has higher damage capability. In this paper, we make the following contributions. (1) We provide the crosstalk attack model and monitor model. (2) Based on these models, we prove necessary and sufficient conditions for k-crosstalk attacks diagnosable network. The key ideas used in our solution are to employ the status of connections as diagnostic data. (3) We propose an efficient monitor placement policy, a test connection setup policy, and a routing policy for such network. These conditions will lead to efficient k-attack detection and diagnosis algorithms.

IP address lookup algorithms can be evaluated on a number of metrics lookup time, update time, memory usage, and to a lesser extent, the time to construct the data structure used to support lookups and updates. Many of the existing methods are geared towards optimizing a specific metric, and hence do not scale well with the ever expanding routing tables and the forthcoming IPv6 with 128 bit long IP address. In contrast, our effort is directed at simultaneously optimizing multiple metrics and provide solutions that scale well to IPv6. In this paper, we present two IP address lookup schemes Elevator - Stairs algorithm and logW - Elevators algorithm. For a routing table with N prefixes, The Elevator - Stairs algorithm uses optimal O(N) memory, and achieves better lookup and update times than other methods with similar memory requirements. The logW - Elevators algorithm gives O(log W) lookup time, where W is the length of an IP address, while improving upon update time and memory usage. Experimental results using the MAE-West router with 29,487 prefixes show that the Elevator - Stairs algorithm gives an average throughput of 15.7 Million lookups per second (Mlps) using 459 KB of memory, and the logW - Elevators algorithm gives an average throughput of 21.41 Mlps with a memory usage of 1259 KB.

In the wireless networks, a packet flow may experience channel errors and results in unsuccessful transmission The bursty channel errors can render the existing algorithms for wireless ad-hoc networks inapplicable. This study develops a fair scheduling algorithm to deal with channel error in wireless ad-hoc networks. The throughput of the network will be improved and the long-term fairness still maintained. The simulation results show our revised SZD algorithm achieves higher throughput and higher fairness than IEEE 802.11 MAC protocol and the original SZD algorithm.

Fairness is an important design criterion for medium access control protocol in multihop wireless networks. It is a complex problem due to its many dimensions that include consideration of location-dependent contention, spatial reuse of channels, and desire to achieve fully distributed scheduling in the wireless communication systems. This paper presents a localized and fully distributed algorithm with fair scheduling in multihop wireless networks. The proposed algorithm incorporates start time fair queuing (STFQ) into the distributed coordination function (DCF) in IEEE 802.11. Our algorithm accounts for the services that have already been received by the sender to adjust the backoff timer to ensure that every flow gets a fair service. We propose a simple data structure that every node (sender or receiver) needs to maintain and an update mechanism that achieves fairness. We illustrate through simulations that the proposed algorithm achieves the desired fairness.

With a rapid increase in the data transmission link rates and an immense continuous growth in the Internet traffic, the demand for routers that perform Internet protocol packet forwarding at high speed and throughput is ever increasing. The key issue in the router performance is the IP address lookup mechanism based on the longest prefix matching scheme. Earlier work on fast Internet protocol version 4 (IPv4) routing table lookup includes, software mechanisms based on tree traversal or binary search methods, and hardware schemes based on content addressable memory (CAM), memory lookups and the CPU caching. These schemes depend on the memory access technology which limits their performance. The paper presents a binary decision diagrams (BDDs) based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The results show that the BDD hardware engine gives a throughput of up to 175.7 million lookups per second (Ml/s) for a large AADS routing table with 33 796 prefixes, a throughput of up to 168.6 Ml/s for an MAE-West routing table with 29 487 prefixes, and a throughput of up to 229.3 Ml/s for the Pacbell routing table with 6822 prefixes. Besides the performance of the scheme, routing table update and the scalability to Internet protocol version 6 (IPv6) issues are discussed.

Channel access has been an active research area for the past two decades. Several protocols have been proposed in the literature to utilize channel bandwidth efficiently. Some of the recently proposed protocols achieve a near-ideal channel utilization. However, the efficiency in utilization comes at the expense of certain unfairness in delay characteristics. A new channel-access protocol, called access mechanism for efficient sharing in broadcast medium networks (AMES-BM), is developed based on a deterministic binary tree-splitting technique to achieve efficient sharing of bandwidth. In AMES-BM, the stations are dynamically mapped to leaf nodes of a binary tree. The stations are then divided into smaller groups that mimic the behavior of an ideal transmission queue. Collisions are allowed to occur within these groups and are resolved using a variation of the conventional binary tree-splitting technique. The performance of AMES-BM is similar to that of a collision-based protocol under low loads and to that of a collision-free protocol under high loads. Besides achieving a near-optimal channel utilization, the proposed protocol also guarantees fairness with respect to delay for messages of varying lengths. The deterministic nature of the protocol makes it more attractive for real-time applications.

This paper presents an empirical investigation on the soft error sensitivity (SES) of microprocessors, using the picoJava-II as an example, through software simulated fault injections in its RTL model. Soft errors are generated under a realistic fault model during program run-time. The SES of a processor logic block is defined as the probability that a soft error in the block causes the processor to behave erroneously or enter into an incorrect architectural state. The SES is measured at the functional block level. We have found that highly error-sensitive blocks are common for various workloads. At the same time soft errors in many other logic blocks rarely affect the computation integrity. Our results show that a reasonable prediction of the SES is possible by deduction from the processor's microarchitecture. We also demonstrate that the sensitivity-based integrity checking strategy can be an efficient way to improve fault coverage per unit redundancy.

Sub-wavelength traffic grooming in optical networks has gained significant importance due to the prevailing fractional wavelength traffic requirement of end-users. Dynamic routing schemes improve the performance of WDM grooming networks compared to static routing as they can adapt to changes in the network state. In this paper, the significance of dynamic routing of fractional wavelength traffic based on request characteristics is illustrated. We propose a request-specific routing scheme, called available shortest path routing, and study its performance. The results are compared against other routing schemes that do not use request characteristics in selecting a path. It Is shown that request-specific routing can improve the network performance with respect to utilization and fairness metrics.

The task of an Internet router is to scan the IP headers for the destination address and make a routing decision based on the information. If the processing capability of a router is enhanced to support computation on a datagram, some of the host computation may be delegated to the intermediate routers. The instructions about how to do the processing may be provided by the end hosts. We propose a reliable transport layer protocol, Intermediate Processing Protocol (IPP) for processing within the Internet. The protocol design makes provisions for connection set up handshake, router reservation, intermediate processing, data acknowledgement, buffering and retransmission, flow and congestion control, ordered delivery and security issues.

Traffic grooming in optical networks employing wavelength division multiplexing has gained prominence due to the prevailing sub-wavelength capacity requirements of users. One approach to achieving wavelength sharing is through time division multiplexing. Connection requests can have a varying number of time slot requirements. Analytical modeling for computing the blocking performance of establishing multi-rate connections in WDM grooming networks involves extensive combinatorial complexity and thus requires prohibitively large state-space for solution. In this paper, we develop an analytical model that employs an approximation to the exact distribution of number of calls of a certain bandwidth requirement on a wavelength. We validate the approximation through simulation results for two different networks that have high and low link-load correlation. It is observed that up to an order of magnitude performance improvement is obtained by improving the grooming capability in the network for calls that require two time slots.

A general-purpose computing processor performs a wide range of functions. Although the performance of general-purpose processors has been steadily increasing, certain software technologies like multimedia and digital signal processing applications demand ever more computing power. If the computing resources are variable to the needs of an application, a better performance can be achieved. Adaptive Balanced Computing (ABC) performs a dynamic resource configuration of on-chip cache memory by converting the cache into a specialized computing unit. With a small amount of additional logic and slightly modified microarchitecture, a part of the cache memory can be configured to perform specialized computations in a conventional processor. In this paper, we evaluate the ABC using RFCs in various cache organizations to see the impact of resource reconfiguration. The simulations with multimedia and DSP applications show that the resource configuration speedups ranging from 1.04X to 3.94X in overall applications and from 2.61X to 27.4X in the core computations.

Several methods have been developed for joint working and spare capacity planning in survivable wavelength-division-multiplexing (WDM) networks. These methods have considered a static traffic demand and optimized the network cost assuming various cost models and survivability paradigms. Our interest primarily lies in network operation under dynamic traffic. We formulate various operational phases in survivable WDM networks as a single integer linear programming (ILP) optimization problem. This common framework avoids service disruption to the existing connections. However, the complexity of the optimization problem makes the formulation applicable only for network provisioning and offline reconfiguration. The direct use of this method for online reconfiguration remains limited to small networks with few tens of wavelengths. Our goal in this paper is to develop an algorithm for fast online reconfiguration. We propose a heuristic algorithm based on LP relaxation technique to solve this problem. Since the ILP variables are relaxed, we provide a way to derive a feasible solution from the relaxed problem. The algorithm consists of two steps. In the first step, the network topology is processed based on the demand set to be provisioned. This preprocessing step is done to ensure that the LP yields a feasible solution. The preprocessing step in our algorithm is based on: (a) the assumption that in a network, two routes between any given node pair are sufficient to provide effective fault tolerance and (b) an observation on the working of the ILP for such networks. In the second step, using the processed topology as input, we formulate and solve the LP problem. Interestingly, the LP relaxation heuristic yielded a feasible solution to the ILP in all our experiments. We provide insights into why the LP formulation yields a feasible solution to the ILP We demonstrate the use of our algorithm on practical size backbone networks with hundreds of wavelengths per link. The results indicate that the run time of our heuristic algorithm is fast enough (in order of seconds) to be used for online reconfiguration.

The advances in photonic switching have paved the way for realizing all-optical time switched networks. The current technology of wavelength division multiplexing (WDM) offers bandwidth granularity that matches peak electronic transmission speed by dividing the fiber bandwidth into multiple wavelengths. However, the bandwidth of a single wavelength is too large for certain traffic. Time division multiplexing (TDM) allows multiple traffic streams to share the bandwidth of a wavelength efficiently. While introducing wavelength converters and time slot interchangers to improve network blocking performance, it is often of interest to know the incremental benefits offered by every additional stage of switching. As all-optical networks in the future are expected to employ heterogeneous switching architectures, it is necessary to have a generalized network model that allows the study of such networks under a unified framework. A network model, called the trunk switched network (TSN), is proposed to facilitate the modeling and analysis of such networks. An analytical model for evaluating the blocking performance of a class of TSNs is also developed. With the proposed framework, it is shown that a significant performance improvement can be obtained with a time-space switch with no wavelength conversion in multiwavelength TDM switched networks. The framework is also extended to analyze the blocking performance of multicast tree establishment in optical networks. To the best of our knowledge, this is the first work that provides an analytical model for evaluating the blocking performance for tree establishment in an optical network. The analytical model allows a comparison between the performance of various multicast tree construction algorithms and the effects of different switch architectures.

Future reliability of general-purpose processors (GPPs) is threatened by a combination of shrinking transistor size, higher clock rates, reduced supply voltages, and other factors. It is predicted that the occurrence of arbitrary transient faults, or soft errors, will dramatically increase as these trends continue. The authors develop and evaluate a fault-tolerant microprocessor architecture that detects soft errors in its own data pipeline. This architecture accomplishes soft error detection through time redundancy, while requiring little execution time overhead. Our approach, called REESE (REdundant Execution using Spare Elements), first minimizes this overhead and then decreases is even further by strategically adding a small number of functional units to the pipeline. This differs from similar approaches in the past that have not addressed ways of reducing the overhead necessary to implement time redundancy in GPPs.

Traffic grooming in optical networks is defined as the act of multiplexing, demultiplexing and switching lower rate traffic streams onto high capacity lightpaths. WDM networks with grooming capabilities can be classified into two basic types: constrained grooming networks, which perform grooming only at OADMs in the nodes and sparse grooming networks, which, in addition to grooming at OADMs, perform traffic stream switching between wavelengths at the nodes. In this paper, we propose a new capacity correlation model which takes into account the capacity distribution on the wavelength, the arrival rates of the calls of varying capacity, and the load correlation on neighbouring links to compute the blocking performance on a multi-hop single wavelength path. We also show that the capacity correlation model can be used to study the blocking performance of constrained grooming networks of arbitrary topologies. The results indicate that the capacity correlation model is more accurate than the link independence model proposed in Thiagarajan and Somani (2000).

With an immense continuous growth in Internet traffic, the demand for routers that perform IP routing at high speed and throughput is ever increasing. The key issue in the router performance is the IP routing lookup mechanism based on the longest prefix matching scheme. Earlier works on fast IPv4 routing table lookup are based on content addressable memory (CAM), memory lookups and CPU caching. These schemes depend on the memory access technology which limits their performance. Besides, these address lookup schemes designed for the IPv4 32-bit address mostly are not extensible to adapt to the forthcoming IPv6 where the IP address is 128 bits long. The paper presents a binary decision diagrams based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The experimental results show that, for the 32-bit IP address large MAE-east routing table, the number of redundant nodes is more than 99.99% in constructing the binary decision tree. With the binary encoding of the output port, an additional 36% reduction is obtained in the number of effective nodes. Besides the performance of the scheme, issues relating to routing table update and the scalability to IPv6 are discussed.

Traditionally, the random logic of most microprocessors is not checked for soft errors due to the great overhead, while regularly-structured memory arrays are often protected with error-correcting codes. This paper presents a low-cost reliability enhancement scheme for the processor's control logic. We classify control logic signals into static and dynamic control, depending on their changeability for a given instruction, and we employ different mechanisms for each. For static control, the signals used in each pipeline stage are integrated into a signature and verified with a cached check code at commit time; the concept of caching signatures is introduced. Dynamic control is examined on-the-spot; the signals are created using component-level duplication. Fault injection simulations on the RTL model of a MIPS-like processor demonstrate that our scheme can achieve more than 99% coverage on average, with a very small addition of hardware. We have also investigated the criticality of errors in the processor logic, which provides direction for devising an efficient allocation of redundancy.

Previous advances in photonic switching have paved the way for realizing all-optical time switched networks. The current technology of wavelength division multiplexing (WDM) offers bandwidth granularity that match peak electronic transmission speed by dividing the fiber bandwidth into multiple wavelengths. However, the bandwidth of a single wavelength is too large for certain traffic. Time division multiplexing (TDM) allows multiple traffic streams to share the bandwidth of a wavelength efficiently. While introducing wavelength converters and time slot interchangers improve the network blocking performance, it is often of interest to know the incremental benefits offered by every additional stage of switching. As all-optical networks in future are expected to employ heterogeneous switching architectures, it is necessary to have generalized network model that allows one to study these networks under a unified framework. In this paper, a network model, called the Trunk Switched Network (TSN), is proposed to facilitate modeling and analysis of such networks. An analytical model for evaluating the blocking performance of a class of TSN's has also been developed. Using the analytical model, it is shown that a significant performance improvement is obtained with a time-space switch with no wavelength conversion at each node in a multi-wavelength TDM switched network.

In real-time systems, tasks have deadlines to be met despite the presence of faults. Primary-Backup (PB) scheme is one of the most common schemes that has been employed for fault-tolerant scheduling of real-time tasks, wherein each task has two versions and the versions are scheduled on two different processors with time exclusion. There have been techniques proposed for improving schedulability of the PB-based scheduling. One of the more popular ones include Backup-Backup (BB) overloading, wherein two or more backups can share/overlap in time on a processor. In this paper we propose a new schedulability enhancing technique, called primary-backup (PB) overloading, in which the primary of a task can share/overlap in time with the backup of another task an a processor. The intuition is that, for both primary and backup of a task, the PB-overloading can assign an earlier start time than that of the BB-overloading, thereby increasing the schedulability. We conduct schedulability and reliability analysis of PB- and BB-overloading techniques through simulation and analytical studies. Our studies show that PB-overloading offers better schedulability (25% increase in the guarantee ratio) than that of BB-overloading, and offers reliability comparable to that of BB-overloading. The proposed PB-overloading is a general technique that can be employed in any static or dynamic fault-tolerant scheduling algorithm.

The paper proposes an integrity checking architecture for superscalar processors that can achieve fault tolerance capability of a duplex system at much less cost than the traditional duplication approach. The pipeline of the CPU core (P-pipeline) is combined in series with another pipeline (V-pipeline), which re-executes instructions processed in the P-pipeline. Operations in the two pipelines are compared and any mismatch triggers the recovery process. The V-pipeline design is based on replication of the P-pipeline, and minimized in size and functionality by taking advantage of control flow and data dependency resolved in the P-pipeline. Idle cycles propagated from the P-pipeline become extra time for the V-pipeline to keep up with program re-execution. For a large-scale superscalar processor, the proposed architecture can bring up to 61.4% reduction in die area and the average-execution time increase is 0.3%.

We consider the problem of establishing dependable connections in WDM networks with dynamic traffic demands. We call a connection with fault-tolerant requirements a dependable connection (D-connection). We consider the single-link failure model in our study and recommend the use of a proactive approach, wherein a D-connection is identified with the establishment of the primary lightpath and a backup lightpath at the time of honouring the connection request. We develop algorithms to select routes and wavelengths to establish D-connections with improved blocking performance. The algorithms use the backup multiplexing technique to efficiently utilize the wavelength channels. To further improve channel utilization, we propose a new multiplexing technique called primary-backup multiplexing. Here, a connection may not have its backup lightpath readily available throughout its existence. We develop algorithms based on this technique to route D-connections with a specified restoration guarantee. We present an efficient and computationally simple heuristic to estimate the average number of connections per link that do not have backup lightpaths readily available upon a link failure. We conduct extensive simulation experiments on different networks to study the performance of the proposed algorithms.

A considerable portion of a microprocessor chip is dedicated to cache memory. However, not all applications need all the cache storage all the time, especially the computing bandwidth-limited applications. In addition, some applications have large embedded computations with a regular structure. Such applications may be able to use additional computing resources. If the unused portion of the cache could serve these computation needs, the on-chip resources would be utilized more efficiently. This presents an opportunity to explore the reconfiguration of a part of the cache memory for computing. Thus, we propose adaptive balanced computing (ABC)-dynamic resource configuration on demand from application-between memory and computing resources. In this paper, we present a cache architecture to convert a cache into a computing unit for either of the following two structured computations: finite impulse response and discrete/inverse discrete cosine transform. In order to convert a cache memory to a function unit, we include additional logic to embed multibit output lookup tables into the cache structure. The experimental results show that the reconfigurable module improves the execution time of applications with a large number of data elements by a factor as high as 50 and 60.

A considerable portion of a chip is dedicated to a cache memory in a modern microprocessor chip. However, some applications may not actively need all the cache storage, especially the computing bandwidth limited applications. Instead, such applications may be able to use some additional computing resources. If the unused portion of the cache could serve these computation needs, the on-chip resources would be utilized more efficiently. This presents an opportunity to explore the reconfiguration of a part of the cache memory for computing. In this paper, we present a cache architecture to convert a cache into a computing unit for either of the following two structured computations, FIR and DCT/IDCT. In order to convert a cache memory to a function unit, we include additional logic to embed multi-bit output LUTs into the cache structure. Therefore, the cache can perform computations when it is reconfigured as a function unit. The experimental results show that the reconfigurable module improves the execution time of applications with a large number of data elements by a large factor (as high as 50 and 60). In addition, the area overhead of the reconfigurable cache module for FIR and DCT/IDCT is less than the core area of those functions. Our simulations indicate that a reconfigurable cache does not take a significant delay penalty compared with a dedicated cache memory. The concept of reconfigurable cache modules can be applied at Level-2 caches instead of Level-1 caches to provide an active-Level-2 cache similar to active memories.

This paper considers the problem of dynamically establishing dependable connections (D-connections) with specified failure restoration guarantees in wavelength-routed wavelength division multiplexed (WDM) networks. We call a connection with fault-tolerant requirements a D-connection. We recommend using a proactive approach to fault-tolerance wherein a D-connection is identified with the establishment of a primary and a backup lightpath at the time of honoring the connection request. However, the backup lightpath may not be available to a connection throughout its existence. Upon occurrence of a fault, a failed connection is likely to find its backup path available with a certain specified guarantee. We develop algorithms to select routes and wavelengths to establish D-connections with specified failure restoration guarantees. The algorithms are based on a technique called primary-backup multiplexing. We present an efficient and computationally simple method to estimate the average number of connections per link for which the backup paths are not readily available upon occurrence of a link failure. This measure is used for selecting suitable primary and backup lightpaths for a connection. We conduct extensive simulation experiments to evaluate the effectiveness of the proposed algorithms on different networks. The results show that the blocking performance gain is attractive enough to allow some reduction in guarantee. In particular, under the light load conditions, more than 90% performance gain is achieved at the expense of less than 10% guarantee reduction.

We study the effect of multiple fibers in circuit-switched all-optical wavelength-routing networks. A new analytical model-the multifiber link-load correlation (MLLC) model-is developed to evaluate the blocking performance of such networks. To our knowledge, the MLLC model is the first model that takes the link-load correlation into account in multifiber WDM networks. We show that the MLLC model is accurate for a variety of network topologies by comparing the analytical results to simulation results. We observed that a small number of fibers are sufficient to guarantee high network performance in multifiber WDM networks.

Most custom computing machine (CCM) design has centered around field-programmable gate array (FPGA) technology and rapid prototyping applications. FPGAs are reconfigured to map parts of the application. The performance of an FPGA when used as a virtual hardware engine depends on its reconfiguration granularity. We study the striped FPGA and propose a hybrid mechanism to process a large amount of data using a combination of data and configuration caching.

The number of transistors on chip has dramatically increased within the last decade. A considerable portion of a chip is dedicated to a cache memory in a modern microprocessor chip. However, some applications may not need all the caches for storage. In addition, some applications have embedded computations with a regular structure. The behavior of the applications is static, which implies that a specialized function unit could be beneficial for the application. This presents an opportunity to explore the use of a part of a cache for performing these regular computations. In this paper, we show one such design to convert a cache into a function unit to improve the performance of an application. A reconfigurable cache takes less area than the area of a cache and a function unit together and imposes no time overhead. In order to convert a cache memory to a function unit, we mapped multi-bit output look-up tables (LUTs) into the cache structure. Therefore, the cache can perform computations When it is reconfigured as a function unit.

Striped FPGA [1], or pipeline-reconfigurable FPGA provides hardware virtualization by supporting fast run-time reconfiguration. In this paper we show that the performance of striped FPGA depends on the reconfiguration pattern, the run time scheduling of configurations through the FPGA. We study two main configuration scheduling approaches: Configuration Caching and Data Caching. We present the quantitative analysis of these scheduling techniques to compute their total execution cycles taking into account the overhead caused by the IO with the external memory. Based on the analysis we can determine which scheduling technique works better for the given application and for the given hardware parameters.

An important issue in the design of future personal communication services (PCS) networks is the efficient management of location information. In this paper, we consider a distributed database architecture for location management in which update and query loads of the individual databases are balanced. An important issue to consider in load balanced location management algorithms is the number of databases a mobile host's location information is updated in. To have the same replication for all mobiles is not optimal. In this paper we present a dynamic load balanced algorithm which replicates mobile hosts according to their level of activity. We analyze the algorithms and derive expressions for the cost of the algorithm. We compare the algorithm with an existing algorithm and show the effectiveness of the proposed algorithm.

An important problem in multifiber WDM networks is to decide how many fibers per link are required to guarantee high network performance. The fiber requirement may depend on many factors, e.g., the network topology, traffic patterns, the number of wavelengths per fiber, and the routing algorithm employed in the network. We study the fiber requirement under dynamic traffic in different topologies with alternate path routing (APR) in this paper. A new analytical model is developed to evaluate the blocking performance of such networks. Our analytical and simulation results show that the number of required fibers per link to provide high network performance is slightly higher in the APR than the fixed-path routing (FPR). However, a small number of fibers per link are still sufficient to guarantee high network performance in both the regular mesh-torus networks and the irregular NSFnet with APR. Since multiple fibers have the same effect as limited wavelength conversion, our analytical model is also applicable in networks with limited wavelength conversion.

This paper describes an algorithm for optimally placing a given number of wavelength converters in all-optical networks (AONs) with arbitrary topologies. We first introduce the simple network model upon which the algorithm is based. We explain how the blocking performance of the network can be obtained when a given number of converters are placed at the network nodes. We then present our optimal converter placement algorithm and illustrate its working using a simple example. The savings in calculation of the blocking performance offered by our algorithm is analyzed. Finally the benefits of our optimal converter placement algorithm is studied through network examples such as the path, NSFnet and the mesh-torus.

Information integrity in cache memories is a fundamental requirement for dependable computing. Conventional architectures for enhancing cache reliability using check codes make it difficult to trade between the level of data integrity and the chip area requirement. We focus on transient fault tolerance in primary cache memories and develop new architectural solutions to maximize fault coverage when the budgeted silicon area is not sufficient for the conventional configuration of an error checking code. The underlying idea is to exploit the corollary of reference locality in the organization and management of the code. A higher protection priority is dynamically assigned to the portions of the cache that are more error-prone and have a higher probability of access. The error-prone likelihood prediction is based on the access frequency. We evaluate the effectiveness of the proposed schemes using a trace-driven simulation combined with software error injection using four different fault manifestation models. From the simulation results, we show that for most benchmarks the proposed architectures are effective and area efficient for increasing the cache integrity under all four models.

AlliedSignal's Avionics & Lighting business unit is expanding the performance of its flight safety avionics by means of functional integration (added functionality enabled by exchanging information between traditionally stand-alone subsystems), as well as physical integration (sharing of system resources) and full dual redundancy. Major performance goals of this integrated modular architecture are a significant increase in system dispatchability and reduction of the loss-of-function probability of individual junctions. Success of this architectural migration depends on the scheme that is used to fully interconnect the various processing and input/output modules. Two of the considered interconnect schemes are discussed: a dual LAN and a dual-dual LAN. In both schemes, all modules can receive data from all LANs. In the prior scheme, all system modules have time-multiplexed transmit privileges on both LANs. In the latter scheme (patent pending), the modules are grouped into two identical sets. The modules in a set can only transmit on two of the four LANs. Dependability of the system has been modeled and analyzed with the HIMAP tool for both schemes, and the results are presented.

Cache data errors read by a processor may cause CPU control flow error and force the system to enter a CPU-cache reintegration process in redundant processor systems. The reintegration process degrades the system performance and reliability. To reduce the occurrences of such an event, we propose a real-time error recovery scheme that provides effective fault-containment for data errors in cache memories. The scheme is based on cache data broadcasting of a dirty line after modification. It effectively exploits the redundancy of a fault-tolerant system using hardware voting. The scheme recovers from erroneous cache data written by a processor with full coverage. This error recovery feature remedies the insufficiency of error-correcting codes that are unable to prevent such an error. In addition, more than 60 percent of cache lines are fully covered for recovery due to errors originated from the cache itself, including unrecoverable ECC errors. The protocol can also be used to speedup the CPU-cache reintegration process for a temporarily failed processor. The performance overhead of the protocol is to broadcast only 2-3 percent of the total memory references.

We present two dynamic routing algorithms based on path and neighborhood link congestion in all-optical networks. In such networks, a connection request encounters higher blocking probability than in circuit-switched networks because of the wavelength-continuity constraint. Much research has focused on the shortest-path routing and alternate shortest-path routing. We consider fixed-paths least-congestion (FPLC) routing in which the shortest path may not be preferred to use. We then extend the algorithm to develop a new routing method: dynamic routing using neighborhood information. It is shown by using both analysis and simulation methods that FPLC routing with the first-fit wavelength-assignment method performs much better than the alternate routing method in mesh-torus networks (regular topology) and in the NSFnet T1 backbone network (irregular topology). Routing using neighborhood information also achieves good performance when compared to alternate shortest-path routing.

Wavelength converters increase the traffic-carrying capacity of circuit-switched optical networks by relaxing the wavelength continuity constraints. We consider the problem of optimally placing a given number of wavelength converters on a path to minimize the call-blocking probability. Using a simple performance model, we first prove that uniform spacing of converters is optimal for the end-to-end performance when link loads are uniform and independent. We then show that significant gains are achievable with optimal placement compared to random placement. For nonuniform link loads, we provide a dynamic programming algorithm for the optimal placement and compare the performance with random and uniform placement. Optimal solutions for bus and ring topologies are also presented. Finally, we discuss the effect of the traffic model on the placement decision.

An important issue in the design of future personal communication services (PCS) networks is the efficient management of location information. The current IS-41 standard PCS architecture uses a centralized database, the home location register (HLR), to store service and location information of each mobile registered in the PCS network. If the HLR fails, all incoming calls to a mobile from hosts which are not in the same location area as the mobile are lost. Location updates from mobiles to the HLR are also lost. Once the HLR is functional it can not direct calls to mobiles immediately as mobiles could have changed their location during the HLR's failure. Fast recovery from a failure of the HLR is hence important. A link failure in the network could partition the network resulting in a loss of location updates from mobiles affected by the failed link. We present a new protocol for fast recovery of the HLR after a HLR failure or an intermediate link failure. The protocol does not require use of wireless bandwidth during the recovery process, has a bounded recovery period and is simple to implement making it an appealing choice in the design of future mobile networks. We analyze the protocol in order to find a medium between protocol cost and the recovery interval.

We consider the problem of optimally placing a given number of wavelength converters on a path to minimize the call blocking probability. Using a simple performance model, we first prove that uniform spacing of converters is optimal for the end-to-end performance when the link loads are uniform and statistically independent. We then show that significant gains are achievable with optimal placement compared to random placement. For non-uniform link loads, we provide a dynamic programming algorithm for the optimal placement and compare the performance with random and uniform placement. Optimal solutions for bus and ring topologies are also presented.

Article Free Access Share on Optimal location management algorithms for mobile networks Authors: Govind Krishnamurthi Department of Electrical and Computer Engineering, Iowa State University, Ames, IA Department of Electrical and Computer Engineering, Iowa State University, Ames, IAView Profile , Murat Azizoğlu Department of Electrical Engineering, University of Washington, Seattle WA Department of Electrical Engineering, University of Washington, Seattle WAView Profile , Arun K. Somani Department of Electrical and Computer Engineering, Iowa State University, Ames, IA Department of Electrical and Computer Engineering, Iowa State University, Ames, IAView Profile Authors Info & Claims MobiCom '98: Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networkingOctober 1998 Pages 223–232https://doi.org/10.1145/288235.288300Online:25 October 1998Publication History 20citation622DownloadsMetricsTotal Citations20Total Downloads622Last 12 Months7Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper formulates the wavelength assignment issues an interconnecting optical broadcast-star local area networks (LANs) through a wavelength routing bridge. Static and dynamic approaches to partitioning of wavelengths for local and global traffic are compared using analysis and simulations. It is found that static wavelength assignment, the easiest algorithm to implement, is significantly outperformed by dynamic algorithms. Several dynamic assignment algorithms are developed, and architectural issues in interconnecting optical networks are discussed. The dependence of the call blocking performance on system parameters, such as the traffic rate, the local and global traffic statistics, and the number of available wavelengths is examined in detail. A simple, yet accurate approximation is also developed to predict the blocking performance with an arbitrary number of LANs.

This paper makes the first known attempt to study wavelength-routing networks and the effects of wavelength conversion under dynamic non-Poisson traffic. An approximation that characterizes any non-Poisson traffic by its first two moments is utilized. The arrival occupancy distribution of busy wavelengths for this approximate process is derived and is used to analyze the effects of wavelength conversion. The model predicts that traffic peakedness plays an important role in determining the blocking performance, and also that wavelength conversion gain is insensitive to traffic peakedness over a large range.

The heart of a massively parallel computer is its interconnection network. In this article we present a reconfigurable multiple bas network to support circuit switching as means of communication between processors of a multiprocessor machine. The main contribution of the papers is in demonstrating the simplicity of the routing hardware whilst still providing modularity and full utilization of the multiple bus system. A comparison with major interconnection network is also presented.

Wavelength-routing networks offer the advantages of wavelength re-use and scalability over broadcast-and-select networks and are therefore suitable for wide area networks (WANs). We study the effects of topological connectivity and wavelength conversion in circuit-switched all-optical wavelength-routing networks. An approximate blocking analysis of such network is performed. We first propose an improved framework for the analysis of networks with arbitrary topology. We introduce a simple model for networks with a variable number of converters and analyze the effect of wavelength converter density on blocking probability. We then apply this framework to two sparse network topologies, the ring and the mesh-torus, and obtain the blocking performance. The results show that, in most cases, only a fraction of the network nodes need to be equipped with wavelength conversion capability for good performance. Finally, the tradeoff between physical connectivity, wavelength conversion, and the number of available wavelengths is studied through networks with random topologies.

Many architecture features are available for improving the performance of a cache-based system. These hardware techniques include cache memories, processor stalling characteristics, memory cycle time, the external databus width of a processor, and pipelined memory system, etc. Each of these techniques affects the cost, design, and performance of a system. We present a powerful approach to assess the performance trade-offs of these architecture techniques based on the equivalence of mean memory delay time. For the same performance point, we demonstrate how each of these features can be traded off and report the ranking of the achievable performance of using them.

We propose a general design technique for high-performance fault-tolerant networks in multiprocessor systems. The proposed technique called extra link multistage interconnection network (ELMIN) can distribute the load evenly and tolerate faults by providing maximal independent paths at the expense of some additional hardware (extra links), which is much smaller than most of the networks proposed earlier. In this paper, the technique is applied to some specific networks, i.e., the CIN (cube interconnection network) and the d-dilated CIN, to show how to maximize the number of redundant paths. The routing algorithms for the ELMIN have the same simplicity as that of the original MIN. We analyze the performance of the proposed networks and also simulate them along with several others under the buffered and unbuffered packet switching environment. Both analysis and simulation show the high performance of the proposed networks without regard to the presence of faults.

The classical diagnosability approach has its limitation when dealing with large fault sets in large multiprocessor systems. This is due to limited diagnosability of large multiprocessor systems connected using regular interconnection structures. We propose an alternative approach to system diagnosis by allowing a few upper bounded number of units to be diagnosed incorrectly. This measure is called t/k-diagnosability. Using this new measure, it is possible to increase the degree of diagnosability of large system considerably. The t/k-diagnosis guarantees that all the faulty units (processors) in a system are detected (provided the number of faulty units does not exceed t) while at most k units are incorrectly diagnosed. We provide necessary and sufficient conditions for t/k-diagnosability and discuss their implication. To demonstrate the power of this approach, we analyze the diagnosability of large systems connected as hypercube, star-graph, and meshes. It is shown that a substantial increase in the degree of diagnosability of these structures is achieved, compared with the degree of diagnosability achieved using the classic diagnosability approach, at the cost of a comparably small number of incorrectly diagnosed units.

We investigate cache write generate, our cache mode invention. We demonstrate that for parallel image processing applications, the new mode improves main memory bandwidth, CPU efficiency, cache hits, and cache latency. We use register level simulations validated by the UW-Proteus system. Many memory, cache, and processor configurations are evaluated.

Unlike broadcast-and-select networks, wavelength-routing networks offer the advantages of wavelength reuse and scalability and are thus suitable for wide-area networks (WANs) We study the effects of topological connectivity and wavelength conversion in circuit-switched all-optical wavelength-routing networks. A blocking analysis of such networks is given. We first propose an analytical framework for accurate analysis of networks with arbitrary topology. We then introduce a model for networks with a variable number of converters and analyze the effect of wavelength converter density on the blocking probability. This framework is applied to three regular network topologies that have varying levels of connectivity: the ring, the mesh-torus, and the hypercube. The results show that either a relatively small number of converters is sufficient for a certain level of performance or that conversion does not offer a significant advantage. The benefits of conversion are largely dependent on the network load, the number of available wavelengths, and the connectivity of the network. Finally, the tradeoff between physical connectivity, wavelength conversion, and the number of available wavelengths is studied through networks with random topologies.

In this paper, we discuss the problem of establishing multicast connections using self-routing multistage interconnection networks (MINs). We examine the issue of multicasting and propose various schemes to accomplish it. Multicasting using recycling of cells has been suggested in the literature recently. We propose a multicast switch architecture that requires a few simple enhancements over a MIN and describe the process of setting up a multicast connection. The size of the routing tables limit the number of copies per cell that can be generated per pass through the network. We assume that no more than two copies per cell can be generated per pass through the routing network and provide detailed cell-level simulation results for the average delay of a cell. The results show that recycling is a practicable option for multicasting and that the delay does not increase drastically when cells are recycled.

No abstract available.

Abstract The binary cube is a popular interconnection structure due to its desirable properties such as symmetry, regularity, low diameter, and high fault‐tolerance characteristics. The biggest drawback of this structure, however, is that the number of nodes in this structure grows only as an integer power of two. To remove this deficiency, a number of alternatives have been suggested, each with some limitations. in this paper, we introduce a variation of this interconnection structure called the helical cube. The proposed structure withKnodes strives to preserve all desirable properties of the binary cube such as regularity, simplicity of routing, and fault tolerance (connectivity of the graph). It removes the restriction on the number of nodes being a power of two while maintaining connectivityc, where ⌊logK⌋ ≤c≤ ⌈logK⌉. The degree of each node remains either ⌈logK⌉ or ⌊logK⌋ depending on the location of a node and total number of nodes in the structure.

Several schemes for detecting faults at the processor level in a multiprocessor system have been discussed in the past. One such scheme (A. Dahbura et al., 1989) works by running secondary versions of jobs on the unused or spare processors of the system and uses the comparison approach (J. Maeng and M. Malek, 1981) to detect faults. We build upon this scheme and propose three new multiprocessor allocation strategies that run a variable number of versions per job. These schemes permit online detection and, in many cases, location of faulty processors in a system with nominal degradation in its delay/throughput performance; these delays are limited chiefly to the delays associated with job preemptions. Two new metrics, the fault detection capability (FDC) and the fault location capability (FLC), are introduced to evaluate these schemes. Extensive simulation results are performed to obtain performance figures for the various schemes. Stochastic Petri net models are also developed to obtain approximate performance results. The results show that these schemes utilize spare capacity more efficiently, thereby improving upon the fault detection and location capabilities of the system.>

The authors propose MaTPi, a new media-access protocol for the efficient utilization of resources in a local-area optical WDMA network. Most of the earlier work on reservation based media access protocols for single-hop optical networks has assumed the availability of state-of-the-art transmitters and/or receivers which are capable of tuning to the required wavelengths within nanoseconds. Their protocol operates in the region where the tuning times of the end-devices are of the same order of magnitude as the transmission time of a packet. In the basic MaTPi protocol, network throughput is improved by effectively overlapping the tuning duration of a transmitter in a node with the transmitting times of lasers in other nodes. They extend this basic protocol to the mult-MaTPi protocol, where each node has more than one transmitter to further improve the bandwidth efficiency of the network. Preliminary simulation results indicate that this practical protocol is indeed capable of achieving high throughput with low-cost, off-the-shelf components. A number of extensions to this protocol are also discussed.>

Presents a unified approach to assess the tradeoff of architecture techniques that affect mean memory access time. The architectural features considered include cache hit ratio, processor stalling features, line size, memory cycle time, the external data bus width of a processor, pipelined memory system, and read bypassing write buffers. The authors demonstrate how each of these features can be traded off to achieve the desired performance. The performance of an architecture feature is quantified in terms of cache hit ratio based on the equivalence of mean memory delay time. They investigate the implication of architectural tradeoffs on the pin count, memory system design, and on-chip cache area for microprocessor systems.>

Most reliability analysis techniques and tools assume that a system is used for a mission consisting of a single phase. However, multiple phases are natural in many missions. The failure rates of components, system configuration, and success criteria may vary from phase to phase. In addition, the duration of a phase may be deterministic or random. Recently, several researchers have addressed the problem of reliability analysis of such systems using a variety of methods. We describe a new technique for phased-mission system reliability analysis based on Boolean algebraic methods. Our technique is computationally efficient and is applicable to a large class of systems for which the failure criterion in each phase can be expressed as a fault tree (or an equivalent representation). Our technique avoids state space explosion that commonly plague Markov chain-based analysis. We develop a phase algebra to account for the effects of variable configurations and success criteria from phase to phase. Our technique yields exact (as opposed to approximate) results. We demonstrate the use of our technique by means of an example and present numerical results to show the effects of mission phases on the system reliability.

Synchronizing distributed networks allows nodes to share resources efficiently, run synchronous programs and vote on redundant results in fault tolerant systems. Due to the low connectivity of hypercube networks, neither the fault tolerant hardware synchronization schemes, phased locked loops nor multistage synchronizers can be used without adding additional links. We describe a new hardware method developed to synchronize hypercube networks. Our analysis shows that the method can sustain one fault if the connectivity of the hypercube, n, is at least three, and it can tolerate up to m/spl ges/2 Byzantine faults as long as the connectivity of the hypercube, n, is greater than max{2m+1,3m-2). This scheme has been implemented in an ASIC design for a hypercube of dimension five. It will be used in the Proteus parallel computer system to synchronize the circuit switching communication network.>

The Proteus architecture is a highly parallel MIMD, multiple instruction, multiple-data machine, optimized for large granularity tasks such as machine vision and image processing. The system can achieve 20 Giga-flops (80 Giga-flops peak). It accepts data via multiple serial links at a rate of up to 640 megabytes/second. The system employs a hierarchical reconfigurable interconnection network with the highest level being a circuit switched Enhanced Hypercube serial interconnection network for internal data transfers. The system is designed to use 256 to 1024 RISC processors. The processors use one megabyte external Read/Write Allocating Caches for reduced multiprocessor contention. The system detects, locates, and replaces faulty subsystems using redundant hardware to facilitate fault tolerance.>

Describes an implementation of a processor node on a Texas Instruments EVM16 microprogrammable machine. In addition, the authors give an algorithm for performing morphological image processing-a commonly used image processing tool today-on such a distributed control architecture. Finally, they give an overview of a software simulator being implemented for simulating the whole pyramid machine. A simulator is essential for testing the working of the architecture and the algorithms before building the hardware.>

We present, Generate, a new cache write handling scheme that avoids unnecessary reads from main memory, reduces bus contention, and increases the available bandwidth of the memory. Cache Write Generate increases the amount of CPU execution and memory load/store overlap, and decreases the memory cycle time. We compare the performance of cache write generate with write around and write allocate in single processor and shared bus multiprocessors and demonstrate a speedup of 1.2 to 1.5 over allocate and write around.

A distributed diagnosis algorithm to locate faulty processing elements in large-scale regular interconnected structures based on the concepts of system-level diagnosis is developed. This algorithm can either operate in a systolic manner or may be executed on a supervisory processor to locate the faulty processors. The computational complexity of the algorithm is linear when run on a supervisory processor and constant when run in parallel systolic manner. The implementation complexity and diagnosis capability of the algorithm are also analyzed without restricting the fault set size. The probability of correct diagnosis is shown to be very high even in the presence of large fault sets.>

Abstract We present an enhanced hypercube architecture and develop a corresponding routing scheme to realize arbitrary permutations in this paper. In particular, we design a rearrangeable and reconfigurable static hypercube architecture called the Generalized Folding‐Cube in the circuit switching environment. In the proposed hypercube, we show that if each connection between two neighboring nodes consists of two pairs of links (two full‐duplex communication lines) the hypercube can handle two independent permutations simultaneously. This hypercube architecture can also be used as an efficient reconfigurable network.

No abstract available.

In a classical system-level diagnosis model, a complex multiprocessor system is characterized to be uniquely diagnosable under the presence of any arbitrary fault set of size up to t. Fault occurrence, however, is usually a sequential process in real-life systems, i.e. multiple faults occur one after another. Any faulty location is immediately diagnosed and the system is reconfigured before any further fault occurs. Systems which are designed under the assumption of sequential fault occurrences and reconfiguration are discussed and their test interconnection assignment for unique diagnosability is characterized. A theorem is developed for sequential k/t-diagnosability, where the system is allowed to have up to t faults but not more than k of them occur at a time. For most practical cases, k has a value of 1. The t-diagnosability theorem is then a special case of this theorem for k=Kt. The results of this theorem are more useful in the design practical systems where the system is reconfigured after every fault is detected and located, and they do not have to satisfy the constraints n>2>

The complexity of the single-fault (SF) set diagnosability and SF-diagnosis problems under the symmetric invalidation models is discussed. It is shown that the SF-diagnosis problem under both these models is co-NP-complete and the SF-diagnosability problem is also co-NP-complete under the asymmetric invalidation model. The SF-diagnosability problem is also studied under the symmetric-invalidation model and a polynomial time-complexity algorithm is presented. These results are in contrast with the corresponding t-diagnosability and t-diagnosis problems, which are known to have polynomial time-complexity algorithms.>

System-level diagnosis appears to be a viable alternative to circuit-level testing in complex multiprocessor systems. A completely new generalization of the characterization problem in the system-level diagnosis area is developed in this paper. This generalized characterization theorem provides necessary and sufficient conditions for any fault-pattern of any size to be uniquely diagnosable, under the symmetric, and asymmetric invalidation models with or without the intermittent faults. Moreover, it is also shown that the well known t-characterization theorems under these models can be derived as special cases. In addition to the generalization provided by these results, it is hoped that these results will also have a great impact on the diagnosis of faulty units in uniform structures based on the system-level diagnosis concepts and would be particularly useful in the diagnosis of WSI-oriented multiprocessor systems.

A systolic binary tree machine which can handle all the dictionary machine and priority queue operations such as Insert, Delete, Extract-Min, Extract-Max, Member, and Near is designed in this paper. The operations can be fed into the tree machine in a pipeline manner at a constant rate and the output is correspondingly generated in a pipeline manner. Each processor in the machine stores at most one data element, which consists of a key value and a record associated with the key. The machine has optimal performance since if the number of data elements present in the tree is n, then each operation takes O(log n) steps. Unlike some recent designs, this machine does not use any links other than the binary tree links, provides optimal performance without the need to store data elements in any sorted order by exploiting dynamic rebalancing, has higher throughput, and keeps the logical last level of the tree on one physical level of the tree.