Foundation models such as SARATR-X have advanced Synthetic Aperture Radar (SAR) Automatic Target Recognition (ATR) by learning generalizable representations. Unlike standard Vision Transformers (ViTs), SARATR-X employs a hierarchical transformer with multi-stage feature extraction, deeper attention layers, and Relative Positional Encoding (RPE). While these enhancements improve SAR target recognition, they introduce significant challenges for real-time deployment: increased memory traffic, complex data layout transformations, and irregular memory access for RPE computation. To address these challenges, we present FASTR, the first FPGA accelerator for hierarchical transformer-based SAR foundation models. We introduce four key innovations: (1) a Hierarchical Multi-Purpose Buffer Architecture (HMBA) that reorganizes on-chip memory across stages without reallocation, (2) a data-layout transformation that enables implicit patch merging, (3) structured RPE bias integration that avoids irregular memory accesses, and (4) a Unified Processing Engine (UPE) that supports convolutions, linear projections, attention, and non-linear operations within a single compute core. We implement FASTR using high-level synthesis (HLS) targeting an AMD Xilinx defense-grade XQVU9P FPGA. Compared to CPU and GPU baselines, FASTR achieves 818× and 3× improvements in energy-delay product while delivering comparable latency to prior ViT accelerators despite processing a complex hierarchical Transformer architecture.

Convolutional Neural Networks (CNNs) have achieved state-of-the-art accuracy in Synthetic Aperture Radar (SAR) Automatic Target Recognition (ATR), but their high computational cost, latency, and memory usage make it challenging on resource-constrained platforms such as small satellites. While adversarial robustness is critical for real-world SAR ATR, it is often overlooked in system-level optimizations. Addressing both challenges requires more than model compression or accelerator design alone, demanding joint optimization in a unified framework.

Synthetic Aperture Radar (SAR) Automatic Target Recognition (ATR) is a fundamental technique in remote-sensing image recognition. SAR ATR systems demand real-time performance and low power consumption, particularly when operating in resource-constrained environments such as small satellites. This paper presents SMART, a model-architecture co-design on FPGA to address the challenges of high latency, large memory footprint, and high power consumption in state-of-the-art SAR ATR models. Model design: We develop a compact CNN with integrated spatial, channel and cross attention mechanisms, optimized through a softmax-free attention approach and quantization for improved computational efficiency and reduced latency. Architecture design: We implement a customized FPGA accelerator with a streaming dataflow architecture using high-level synthesis (HLS) on the Xilinx Alveo U280 FPGA. The design optimizes the dataflow through parameterized hardware kernels for key operations. Experimental results on the widely used MSTAR (99.84%), SynthWakeSAR (94.85%) and GBSAR (99.92%) datasets, demonstrate that our model achieves superior classification accuracy. Our design delivers up to 29× lower latency and 66× higher energy efficiency compared to implementations on state-of-the-art CPU and GPU platforms.

We examine an uplink cell-free (CF) massive multiple-input multiple-output (MIMO) system in which multiple-antenna access points (APs) are connected to a central processing unit (CPU) via unlimited capacity front-haul links, and each user equipment (UE) is equipped with a single antenna. In such a system, optimizing AP selection to maximize the sum spectral efficiency (SE) while meeting real-time communication requirements is challenging. To address this, we develop a novel approach using a heterogeneous graph neural network (HetGNN), which effectively captures the complex relationships between AP and UE nodes. Given the difficulty in obtaining ground truth for optimal AP selection, we employ an unsupervised HetGNN model that directly optimizes AP selection through its loss function. Simulation results demonstrate that our approach achieves an average improvement of at least 8% compared to existing methods and surpasses an offline approach using the Simulated Annealing method. Our approach also results in high fairness scores on Jain's Fairness Index; averaging greater than 0.845 per UE and exceeding 0.9 as the system scales. Our computation time analysis shows that the average inference time remains low and within acceptable limits for communication systems.

Several organizations have built multiple datacenters connected via dedicated wide area networks over which large inter-datacenter transfers take place. Since many such transfers move the same data from one source to multiple destinations, using multicast forwarding trees can reduce bandwidth needs and improve completion times. However, using a single forwarding tree per transfer can lead to poor performance as the slowest receiver dictates the completion time for all receivers. Using multiple forwarding trees per transfer alleviates this concern-the average receiver could finish early; however, if done naively, bandwidth usage would also increase and it is apriori unclear how best to partition receivers, how to construct the multiple trees and how to determine the rate and schedule of flows on these trees. This paper presents QuickCast, a first solution to these problems. Using simulations on real-world network topologies, we see that QuickCast can speed up the average receiver's completion time by as much as 10× while only using 1.04× more bandwidth; further, the completion time for all receivers also improves by as much as faster at high loads. Thereby, while some implementation challenges remain, we advocate using a cohort of forwarding trees.

Datacenters provide the infrastructure for cloud computing services used by millions of users everyday. Many such services are distributed over multiple datacenters at geographically distant locations possibly in different continents. These datacenters are then connected through high speed WAN links over private or public networks. To perform data backups or data synchronization operations, many transfers take place over these networks that have to be completed before a deadline in order to provide necessary service guarantees to end users. Upon arrival of a transfer request, we would like the system to be able to decide whether such a request can be guaranteed successful delivery. If yes, it should provide us with transmission schedule in the shortest time possible. In addition, we would like to avoid packet reordering at the destination as it affects TCP performance. Previous work in this area either cannot guarantee that admitted transfers actually finish before the specified deadlines or use techniques that can result in packet reordering. In this paper, we propose DCRoute, a fast and efficient routing and traffic allocation technique that guarantees transfer completion before deadlines for admitted requests. It assigns each transfer a single path to avoid packet reordering. Through simulations, we show that DCRoute is at least 200 times faster than other traffic allocation techniques based on linear programming (LP) while admitting almost the same amount of traffic to the system.

Graphs are a key form of Big Data, and performing scalable analytics over them is invaluable to many domains. There is an emerging class of inter-connected data which accumulates or varies over time, and on which novel algorithms both over the network structure and across the time-variant attribute values is necessary. We formalize the notion of time-series graphs and propose a Temporally Iterative BSP programming abstraction to develop algorithms on such datasets using several design patterns. Our abstractions leverage a sub-graph centric programming model and extend it to the temporal dimension. We present three time-series graph algorithms based on these design patterns and abstractions, and analyze their performance using the Offish distributed platform on Amazon AWS Cloud. Our results demonstrate the efficacy of the abstractions to develop practical time-series graph algorithms, and scale them on commodity hardware.

This paper describes a method for learning coordination policies in body sensor networks. The learning of a compact coordination policy is important for implementing the policy in sensor nodes with limited memory. We present a novel algorithm, Reinforcement Learning Average Approximation (RLAA), to learn local coordination policies for each sensor node from globally joint rewards. These local policies are obtained by reinforcement learning and averaging state-action tables under a stochastic process model. We show results on a simulation of an existing body sensor network interfaced with transdermal sensors that demonstrate the performance of this learning scheme. Experimental results show that the performance of the RLAA algorithm is significantly better than a random policy and is close to the optimal policy that can be obtained from solving a global Markov Decision Process while the learning step is fast. The results also show that the RLAA algorithm is scalable to networks represented by large state spaces (in terms of number s of sensors and degree of discretization).

We describe efforts to integrate in-situ sensing, space-borne sensing, hydrological modeling, active control of sensing, and automatic data product generation to enhance monitoring and management of flooding. In our approach, broad coverage sensors and missions such as MODIS, TRMM, and weather satellite information and in-situ weather and river gauging information are all inputs to track flooding via river basin and sub-basin hydrological models. While these inputs can provide significant information as to the major flooding, targetable space measurements can provide better spatial resolution measurements of flooding extent. In order to leverage such assets we automatically task observations in response to automated analysis indications of major flooding. These new measurements are automatically processed and assimilated with the other flooding data. We describe our ongoing efforts to deploy this system to track major flooding events in Thailand.

In this paper, we propose an efficient multi-party signature scheme for wireless networks where a given number of signees can jointly sign a document, and it can be verified by any entity who possesses the certified group public key. Our scheme is based on an efficient threshold key generation scheme which is able to defend against both static and adaptive adversaries. Specifically, our key generation method employs the bit commitment technique to achieve efficiency in key generation and share refreshing; our share refreshing method provides proactive protection to long-lasting secret and allows a new signee to join a signing group. We demonstrate that previous known approaches are not efficient in wireless networks, and the proposed multi-party signature scheme is flexible, efficient, and achieves strong security for low-power devices in wireless networks.

Delay tolerant networks are a class of networks characterized by intermittent connectivity, long delays, and noncontemporaneous end-to-end paths between nodes. Standard Internet protocols do not fare well in these situations and special protocols have been developed to handle routing, broadcasting and other mechanisms for transporting data. In this paper, we discuss a mechanism for energy efficient broadcast - the k-neighbor broadcast scheme. Nodes do not broadcast all the time, but wait for an opportunity to reach multiple nodes with one transmission, thereby reducing the number of transmissions overall. We performed a simulation based study and found our scheme performs efficiently in a predictable manner.

Abstract A specific characteristic of sensor network applications is that the major traffic consists of data collection from various sensor source nodes to a sink via a unidirectional tree. In this paper, we propose DMAC, an energy efficient and low latency MAC that is designed and optimized for such data gathering trees in wireless sensor networks. We first show that previously proposed MAC protocols for sensor networks that utilize activation/sleep duty cycles suffer from a data forwarding interruption problem, whereby not all nodes on a multihop path to the sink can be notified of data delivery in progress, resulting in significant sleep delay. DMAC is designed to solve the interruption problem, by giving the active/sleep schedule of a node an offset that depends upon its depth on the tree. This scheme allows continuous packet forwarding because all nodes on the multihop path can be notified of the data delivery in progress. DMAC also adjusts node duty cycles adaptively according to the traffic load in the network by varying the number of active slots in an schedule interval. We further propose a data prediction mechanism and the use of more to send (MTS) packets in order to alleviate problems pertaining to channel contention and collisions. Our simulation results as well as experimental results with the Mote platform show that by exploiting the application‐specific structure of data gathering trees in sensor networks, DMAC provides significant energy savings and latency reduction while ensuring high data reliability. Copyright © 2007 John Wiley & Sons, Ltd.

Traditionally, ad hoc networks have been viewed as a connected graph over which end-to-end routing paths had to be established.Mobility was considered a necessary evil that invalidates paths and needs to be overcome in an intelligent way to allow for seamless ommunication between nodes.However, it has recently been recognized that mobility an be turned into a useful ally, by making nodes carry data around the network instead of transmitting them. This model of routing departs from the traditional paradigm and requires new theoretical tools to model its performance. A mobility-assisted protocol forwards data only when appropriate relays encounter each other, and thus the time between such encounters, called hitting or meeting time, is of high importance.In this paper, we derive accurate closed form expressions for the expected encounter time between different nodes, under ommonly used mobility models. We also propose a mobility model that can successfully capture some important real-world mobility haracteristics, often ignored in popular mobility models, and alculate hitting times for this model as well. Finally, we integrate this results with a general theoretical framework that can be used to analyze the performance of mobility-assisted routing schemes. We demonstrate that derivative results oncerning the delay of various routing s hemes are very accurate, under all the mobility models examined. Hence, this work helps in better under-standing the performance of various approaches in different settings, and an facilitate the design of new, improved protocols.

Hyperspectral images have correlation at the level of pixels; moreover, images from neighboring frequency bands are also closely correlated. In this paper, we propose to use distributed source coding to exploit this correlation with an eye to a more efficient hardware implementation. Slepian-Wolf and Wyner-Ziv based correlated coding theorems have quantified how much additional rate reduction can be obtained. In order to better exploit these correlations, we first propose a prediction model to align images. This model is based on linear prediction techniques and it is simple and shown to be effective for hyperspectral images. We then propose a coding scheme to exploit these correlations. A set-partitioning approach is used on wavelet transformed data to extract bitplanes. Under our correlation model, bitplanes from neighboring bands are correlated and we then use a low-density parity-check based Slepian-Wolf code to exploit this bitplane level correlation. This scheme is appealing for hardware implementation as it is easy to parallelize and it has modest memory requirements. As for coding performance, our preliminary results for high correlation spectral bands from the NASA AVIRIS dataset show, at medium to high reconstructed qualities, gains of about a factor of 3 in compression efficiency as compared to encoding the spectral bands independently using SPIHT.

In-network processing is an appealing principle for resource conservation for sensor network applications. We propose a scheme to compress sensor array data in which one sensor has to send its readings to multiple neighbor sensors. This proposed scheme uses low-density parity-check code based Slepian-Wolf codes to compress these bit-planes extracted from wavelet coefficients with flexible rates, and each receiver uses the sum-product algorithm to decode the progressive transmission. A priori correlation statistic is not required in this scheme, and the reception rate of each receiver is close to conditional entropy with regard to the sender.

In this paper, we propose a compression scheme called spatial set-partitioning in hierarchical trees which exploits the spatial and temporal correlations present in sensor data. This scheme allows progressive transmission and provides scalability in adapting to the underlying correlation structure of sensed data. It uses flexible Slepian-Wolf coding based on low density parity-check codes. Two different decoding schemes are proposed for different types of resource constrained sensor nodes. This scheme outperforms known codecs by a large margin of decibel in terms of the signal-to-noise ratio. This scheme has O(n) complexity for encoding and O(nlog(n)) complexity for decoding using message passing, where n is the codeword length. Experiments and simulation results with field data sets demonstrate the viability of our proposed scheme to wireless sensor networks.

This paper proposes a new routing paradigm for sensor networks called X visiting-pattern routing (XVR) that decouples visiting-patterns of packets from the routing core. Visiting-patterns indicate where to forward packets as next hops in a network and are essential to any routing service. With XVR, the visiting-patterns are defined in a separate module from the routing core, thus enabling them to be changed independently. The overhead of changing routing behavior is further reduced significantly by parameterizing usual visiting-patterns; different routing services can be obtained by simply changing the visiting-pattern parameters. In addition, with the extensive routing behavior space and the separate visiting-pattern module, XVR furnishes a desirable base to realize automatic and concurrent routing services that adapt to application and network dynamics. Discussions and extensive simulations show that by systematically testing different visiting-patterns XVR provides a unique environment and a comprehensive approach to study both existing and new routing algorithms.

Group based transactions are becoming common via handhelds. Single key based systems may not be able to meet various security requirements. In this paper, we propose a threshold signature scheme based on Pedersen distributed key generation principle which is suitable for handheld devices and ad-hoc networks. Existing distributed key generation protocols use either cryptosystems based on the hardness of discrete logarithm over a finite field or integer factorization. Elliptic curve cryptosystems provide a promising alternative with efficiency which is suitable for low-power devices in terms of memory and processing overhead. In the proposed scheme, the public key from the key generation protocol follows a uniform distribution in the elliptic curve additive group, and the signature can be generated and verified efficiently. We evaluated the proposed key generation protocol and signature scheme using PARI/GP, and the key generation time takes a fraction of a second and the signature signing and verifying can be finished in a few milliseconds on the LINUX Intel PXA 255 processor.

IEEE 802.15.4 is a new standard to address the need for low-rate low-power low-cost wireless networking. We provide in this paper one of the first simulation-based performance evaluations of the new medium access protocol in IEEE 802.15.4, focusing on its beacon-enabled mode for a star-topology network. We describe its key features such as the superframe structure, which allows devices to access channels in a contention access period (CAP) or a collision free period (CFP) and the beacon-based synchronization mechanism. Our performance evaluation study reveals some of the key throughput-energy-delay tradeoffs inherent in this MAC protocol. We provide an analysis comparing the energy costs of beacon tracking and non-tracking modes for synchronization, showing that the optimum choice depends upon the combination of duty cycles and data rates.

Summary form only given. In many sensor network applications the major traffic pattern consists of data collected from several source nodes to a sink through a unidirectional tree. We propose DMAC, an energy efficient and low latency MAC that is designed and optimized for such data gathering trees in wireless sensor networks. We first show that previously proposed MAC protocols for sensor networks that utilize activation/sleep duty cycles suffer from a data forwarding interruption problem, whereby not all nodes on a multihop path to the sink are notified of data delivery in progress, resulting in significant sleep delay. DMAC is designed to solve the interruption problem and allow continuous packet forwarding by giving the sleep schedule of a node an offset that depends upon its depth on the tree. DMAC also adjusts the duty cycles adaptively according to the traffic load in the network. We further propose a data prediction mechanism and the use of more-to-send (MTS) packets in order to alleviate problems pertaining to channel contention and collisions. Our simulation results show that by exploiting the application-specific structure of data gathering trees in sensor networks, DMAC provides significant energy savings and latency reduction while ensuring high data reliability.

A novel coding scheme is proposed for applications over wireless microsensor networks to meet both wireless link bandwidth and node energy constraints. First, an analysis is performed on the energy efficiency of coding schemes in wireless microsensor networks. Based on this analysis, we devise a power aware coding scheme, called EESPIHT which exploits the spatio-temporal correlation of multiple sensor readings. It is also made resilient to channel errors: it selects an error correcting code based on source coding information and transmission power so that energy dissipation is minimized. Experimental results on a LINUX implementation and simulation results based on OPNET using field data sets show that the proposed scheme can reduce energy on communication by more than 60% and maintain a signal-to-noise ratio (SNR) gain of 24 dB or better compared to the non-coded case.

Sensor readings in a wireless microsensor network are correlated both spatially and temporally. Various coding and storage schemes and also other applications have been developed to exploit these correlations; therefore it is crucial to efficiently track the correlations. In this paper, a linear prediction algorithm is developed to initially establish the correlations, and the order of linear prediction has been derived from the prediction error power distribution. A tracking algorithm uses discrete Kalman filter to track the correlation once it is initially obtained. This Kalman filter based algorithm uses the gradient computed at each step as the input control vector. This approach is suitable for quantifying geographical spatial correlation and multimodality correlation. Experimental results using various data sets have shown that the proposed scheme can accurately obtain the correlation and consumes much less energy as compared to known schemes.

Adaptive array antennas have the ability to respond automatically to an unknown interference environment, in real time, by steering nulls and reducing side lobe levels in the direction of interference, while retaining some desired signal beam characteristics. We present a protocol (ADAPT) that enables nodes in an ad hoc network to utilize adaptive array antennas efficiently to communicate. We compare our adaptive antenna configuration {ADAPT, adaptive array antennas} to both an omni-directional setting {802.11, omni-directional antennas} and a directional one {DMAC protocol, directional antennas} in terms of network throughput and end-to-end delay. The DMAC protocol is described by M. Takai et al. (see Proc. ACM MobiHoc, 2002) and R. Roychoudhury et al. (see Proc. MOBICOM 2002). Our protocol achieves up to a 60% throughput and 2-3 times delay improvement over the omni-directional case and up to a 40% throughput and 55% delay improvement over the directional one, in most scenarios considered.

Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from source to destination, or such a path is highly unstable and may break soon after it has been discovered. In this context, conventional routing schemes would fail. To deal with such networks we propose the use of an opportunistic hop-by-hop routing model. According to the model, a series of independent, local forwarding decisions are made, based on current connectivity and predictions of future connectivity information diffused through nodes' mobility. The important issue here is how to choose an appropriate next hop. To this end, we propose and analyze via theory and simulations a number of routing algorithms. The champion algorithm turns out to be one that combines the simplicity of a simple random policy, which is efficient in finding good leads towards the destination, with the sophistication of utility-based policies that efficiently follow good leads. We also state and analyze the performance of an oracle-based optimal algorithm, and compare it to the online approaches. The metrics used in the comparison are the average message delivery delay and the number of transmissions per message delivered.

Directional and smart antennas can be useful in increasing the capacity of wireless ad hoc networks. A number of media access and routing protocols have been recently proposed for use with such antennas, and have shown significant performance improvements over the omni-directional case. However, it is important to explore if and how different directional and smart antenna designs affect the asymptotic capacity bounds, derived by Kumar and Gupta (2000). These bounds are inherent to specific ad-hoc network characteristics, like the shared nature of the wireless media and multihop connectivity, and may pose major scalability limitations for such networks. In this paper, we look into how directional and smart antennas can affect the asymptotic behavior of an ad-hoc network's capacity. Specifically, we perform a capacity analysis for an ideal flat-topped antenna, a linear phased-array antenna, and a fully adaptive array antenna model. Finally, we explain how an ad-hoc network designer can manipulate different antenna parameters to mitigate the scalability problem of ad-hoc networks.

Directional antennas can be useful in significantly increasing the capacity of wireless ad hoc networks. With directional antennas, independent communications between nodes can occur in parallel, even if the nodes are within range of each other. However, mutual interference by simultaneous transmissions limits the maximum number of such concurrent communications. Furthermore, it poses bounds on the amount of capacity gain one can achieve by using directional antennas instead of omni-directional ones. These bounds depend on the specific antenna type and its parameters, as well as higher layer protocol requirements. In this paper, we calculate interference based capacity bounds for a generic antenna model as well as a real-world antenna model and analyze how these bounds are affected by important antenna parameters like gain and beamwidth.

Sensor networks are used in a variety of applications for event monitoring, environmental sensing and outer space exploration. An important application is detecting a target in the field using sensors gathering acoustic data. In this target detection application (ATR), a cluster of wireless sensors collected acoustic data and perform signal processing. In the algorithm used for signal processing, acoustic data collected by the sensors need to be communicated to a designated head node for determining the target direction of bearing. The data collected by geometrically closely distributed sensors show high spatial correlation. In this paper, our focus is on energy efficient coding schemes for wireless sensor networks. First we give an analysis to show why conventional compression scheme give poor performance when energy consumption for encoding and decoding processing overheads are considered. We then describe a new coding scheme called EEADSC, which minimizes the Lagrangian cost function. The proposed scheme fully exploits spatial correlation in wireless sensor network and is adaptive according to tracking signal strength. We evaluated the proposed scheme using datasets from an ATR application, which achieved up to a factor of 8 data compression. EEADSC uses TCQ quantization and trellis encoding to represent a 16 bit data value by as few as 2 bits. With the scheme, we reduce the overall energy cost for communication in this application by a factor of 2.53, including the overhead processing cost in encoding/decoding. The scheme also fits well for general sensor network applications in which some data collection and aggregation are performed.

Directional antennas can be useful in significantly increasing node and network lifetime in wireless ad hoc networks. In order to utilize directional antennas, an algorithm is needed that will enable nodes to point their antennas to the right place at the right time. In this paper we present an energy-efficient routing and scheduling algorithm that coordinates transmissions in ad hoc networks where each node has a single directional antenna. Using the topology consisting of all the possible links in the network, we first find shortest cost paths to be energy efficient. Then, we calculate the amount of traffic that has to go over each link and find the maximum amount of time each link can be up, using end-to-end traffic information to achieve that routing. Finally, we schedule nodes' transmissions, trying to minimize the total time it takes for all possible transmitter-receiver pairs to communicate with each other. We formulate this link problem as solving a series of maximal-weight matching in a graph. Furthermore, we propose a method that can enable our scheduling algorithm to work in a distributed and adaptive fashion. We demonstrate that our algorithm achieves all the possible transmitter/receiver gains possible from using directional antennas. In addition, we illustrate through simulation that our routing scheme achieves up to another 45% improvement in energy cost for routing.

Gathering sensed information in an energy efficient manner is critical to operating the sensor network for a long period of time. The LEACH protocol presented by Heinzelman et al. (2000) is an elegant solution where clusters are formed to fuse data before transmitting to the base station. In this paper, we present an improved scheme, called PEGASIS (power-efficient gathering in sensor information systems), which is a near-optimal chain-based protocol that minimizes energy. In PEGASIS, each node communicates only with a close neighbor and takes turns transmitting to the base station, thus reducing the amount of energy spent per round. Simulation results show that PEGASIS performs better than LEACH. For many applications, in addition to minimizing energy, it is also important to consider the delay incurred in gathering sensed data. We capture this with the energy /spl times/ delay metric and present schemes that attempt to balance the energy and delay cost for data gathering from sensor networks. We present two new schemes to minimize energy /spl times/ delay using CDMA and non-CDMA sensor nodes. We compared the performance of direct, LEACH, and our schemes with respect to energy /spl times/ delay using extensive simulations for different network sizes. Results show that our schemes perform 80 or more times better than the direct scheme and also outperform the LEACH protocol.

Ad hoc wireless networks and sensor networks have nodes with limited battery power, and broadcasting is an important operation in such networks. In this paper, we consider energy efficient one-to-all and all-to-all broadcast communications in such power constrained networks. It is assumed that nodes have power control and can adjust the range of their transmissions. Given a network of N nodes in a playing field of size D/spl times/D, we establish a lower bound and present a simple scheme for a source-to-all broadcast operation. Using simulations we show that the average energy cost of broadcasting from any source is within 25% of this lower bound in a network of 100 nodes in a 500 m/spl times/500 m and a 1000 m/spl times/1000 m area. In the situation awareness application, each node periodically transmits a small packet of 60 bytes to all other nodes in the network. For this all-to-all broadcast communication, we present a cluster scheme when nodes are allowed to transmit long distances, and a chain based scheme when nodes are limited to short distances. Our schemes for situation awareness significantly improve the life of the network compared to schemes with direct transmissions.

a set of independent tasks compete for the shared resources of a Grid environment. Tasks have resource co-allocation requirements. Each task requires multiple and different resources to be allocated simultaneously. At run-time, a task may release its allocated resources during its execution and before its completion time. Our objective is to minimize the overall schedule length of all submitted tasks while satisfying all resource sharing constraints among them. We develop a two-phase mapping approach for solving this problem. The first phase of our approach is off-line planning phase where a schedule plan, which gives a scheduling order and resource assignments of tasks, is generated at compile-time. The second phase is run-time adaptation phase. The goal of the second phase is to improve the performance of the schedule plan by adapting to run-time changes such as the early release of resources and the variation in computation and communication costs. Adaptation may involve changing the scheduling order and resource assignments of the original schedule plan. Our experimental results demonstrate the effectiveness of our approach compared to a baseline algorithm that performs no adaptation at run-time and to a dynamic algorithm that performs no planning at compile-time. Our two-phase mapping approach outperforms both algorithms by up to 20% with respect to the overall schedule length.

In this paper we consider the problem of data collection from a sensor web consisting of N nodes, where nodes have packets of data in each round of communication that need to be gathered and fused with other nodes' packets into one packet and transmitted to a distant base station. Nodes have power control in their wireless communications and can transmit directly to any node in the network or to the base station. With unit delay cost for each packet transmission, if all nodes transmit data directly to the base station, then both high energy and high delay per round will occur. In our prior work [6], we developed an algorithm to minimize the energy cost per round, where a linear chain of all the nodes are formed to gather data, and nodes took turns to transmit to the base station. If the goal is to minimize the delay cost, then a binary combining scheme can be used to accomplish this task in about log N units of delay with parallel communications and incurring a slight increase in energy cost. The goal is to find data gathering schemes that balance the energy and delay cost, as measured by energy*delay. We conducted extensive simulation experiments with a number of schemes for this problem with 100 nodes in playing fields of 50m x 50m and 100m x 100m and the base station located at least 100 meters and 200 meters, respectively, from any node. With CDMA capable sensor nodes, a chain-based binary scheme performs best in terms of energy*delay. If the sensor nodes are not CDMA capable, then parallel communications are possible only among spatially separated nodes, and a chain-based 3 level hierarchy scheme performs well. These schemes perform 60 to 100 times better than direct scheme and also outperform a cluster based scheme, called LEACH [3]. 1.

In this paper, we present an architecture of an AdaptiveCommunication System (ACS) that provides applicationswith programmable communication, control, andmanagement services that can be adopted dynamicallyto maximize application performance at runtime. ACSsupports adaptive and scalable communication servicesthat select the appropriate multicast/broadcast algorithmsfor a given class of applications. These algorithms takeinto consideration both the application requirements andthe load of computing and communication systems.We overview the ACS architecture and then describe ourapproach to implement the ACS group communication services.We introduce two procedures (Resource Aware procedureand Application Aware procedure) to build the appropriatemulticast tree that takes into consideration both thecharacteristics and load conditions of machines as well asthe group communication patterns of a given application.We develop analytical techniques and new metric measuresto characterize and quantify the performance of a multicasttree. We also present our preliminary performance resultsthat show significant performance gain can be achievedfrom using ACS multicast algorithms.

Multistage network based input-buffered ATM switches, which have been studied extensively, are cheaper compared to crossbar designs but suffer from elaborate cell selection methods or expensive network setup. In this paper, a fast cell selection method is proposed to avoid slow cell selection and costly network setup for these designs. In particular, we propose network hardware specific selection techniques for cell selection in input buffered Banyan network with an internal speed twice that of the external links. Our simulation results show that cell selection by looking at up to 10 cells in each input queue for switch sizes up to N=64 yields 95% or higher switch utilization.

The Information Power Grid (IPG) is emerging as an infrastructure that will enable distributed applications-such as videoconferencing and distributed interactive simulation-to seamlessly integrate collections of heterogeneous workstations, multiprocessors, and mobile nodes over heterogeneous wide-area networks. This paper introduces a framework for developing efficient collective communication schedules in such systems. Our framework consists of analytical models of the heterogeneous system, scheduling algorithms for the collective communication pattern, and performance evaluation mechanisms. We show that previous models, which considered node heterogeneity but ignored network heterogeneity, can lead to solutions which are worse than the optimal by an unbounded factor. We then introduce an enhanced communication model, and develop three heuristic algorithms for the broadcast and multicast patterns. The completion time of the schedule is chosen as the performance metric. The heuristic algorithms are FEF (Fastest Edge First), ECEF (Earliest Completing Edge First), and ECEF with look-ahead. For small system sizes, we find the optimal solution using exhaustive search. Our simulation experiments indicate that the performance of our heuristic algorithms is close to optimal. For performance evaluation of larger systems, we have also developed a simple lower bound on the completion time. Our heuristic algorithms achieve significant performance improvements over previous approaches.

Run-time array redistribution is necessary to enhance the performance of parallel programs on distributed memory supercomputers. In this paper, we present an efficient algorithm for array redistribution from cyclic(x) on P processors to cyclic(Kx) on Q processors. The algorithm reduces the overall time for communication by considering the data transfer, communication schedule, and index computation costs. The proposed algorithm is based on a generalized circulant matrix formalism. Our algorithm generates a schedule that minimizes the number of communication steps and eliminates node contention in each communication step. The network bandwidth is fully utilized by ensuring that equal-sized messages are transferred in each communication step. Furthermore, the time to compute the schedule and the index sets is significantly smaller. It takes O(max(P, Q)) time and is less than 1 percent of the data transfer time. In comparison, the schedule computation time using the state-of-the-art scheme (which is based on the bipartite matching scheme) is 10 to 50 percent of the data transfer time for similar problem sizes. Therefore, our proposed algorithm is suitable for run-time array redistribution. To evaluate the performance of our scheme, we have implemented the algorithm using C and MPI on an IBM SP2. Results show that our algorithm performs better than the previous algorithms with respect to the total redistribution time, which includes the time for data transfer, schedule, and index computation.

Heterogeneous network-based systems are emerging as attractive computing platforms for HPC applications. We discuss fundamental research issues that must be addressed to enable network-aware communication at the application level. We present a uniform framework for developing adaptive communication schedules for various collective communication patterns. Schedules are developed at run-time, based on network performance information obtained from a directory service. We illustrate our framework by developing communication schedules for total exchange. Our first algorithm develops a schedule by computing a series of matchings in a bipartite graph. We also present a O(P/sup 3/) heuristic algorithm, whose completion time is within twice the optimal. This algorithm is based on the open shop scheduling problem. Simulation results show performance improvements of a factor of 5 over well known homogeneous scheduling techniques.

The routing and signaling protocols for supporting multipoint-to-multipoint connections in ATM networks have been presented earlier. VP-merge and VC-merge techniques have been proposed as the likely candidates for resolving the sender identification problem associated with these connections. The additional buffer requirements in the VC-merge mechanism and the excessive rise of VPI/VCI space in the VP-merge mechanism have been the main reasons for concern about their effective utility. We propose improvements to the traditional VC-merge technique to minimize the need for additional buffers at intermediate merge points. Aptly named dynamic multiple VC-merge (DMVC), fixed multiple VC-merge (FMVC) and selective multiple VC-merge (SMVC), these mechanisms define a generic scheme for merging the data from multiple senders onto one or more outgoing links. By appropriately choosing the number of connection identifiers per connection, these schemes lead to a large reduction in the buffer requirements and an effective utilization of the VPI/VCI space. Based on extensive simulations, we show that by using two connection identifiers per connection, there is an 80% reduction in buffer requirements for DMVC and FMVC when compared to the buffer required for traditional VC-merge.

In this paper we present a case for using new power-aware metrics for determining routes in wireless ad hoc networks. We present five different metrics based on battery power consumption at nodes. We show that using these metrics in a shortest-cost routing algorithm reduces the cost/packet of routing packets by 5-30% over shortest-hop routing (this cost reduction is on top of a 40-70% reduction in energy consumption obtained by using PAMAS, our MAClayer protocol) . Furthermore, using these new metrics ensures that the mean time to node failure is increased significantly. An interesting property of using shortest-cost routing is that packet delays do not increase. Finally,we note that our new metrics can be used in most traditional routing protocols for ad hoc networks. 1 Introduction AdHoc networks are multi-hop wireless networks where all nodes cooperatively maintain network connectivity. These types of networks are useful in any situation where temporary network connectivityisneede...

In this paper we develop a new multi-access protocol for multi-hop radio networks. The unique feature of our protocol is that it is energy conserving. Radios that are not actively transmitting or receiving a packet power themselves off. The manner in which nodes power themselves off does not influence the delay or throughput characteristics of our protocol. Simulation results indicate that power savings of between 10% and 70% are attainable in most systems.

Run-time array redistribution is necessary to enhance the performance of parallel programs on distributed memory supercomputers. In this paper, we present an efficient algorithm for array redistribution from cyclic(x) on P processors to cyclic(Kx) on Q processors. The algorithm reduces the overall time for communication by considering the data transfer, communication schedule, and index computation costs. The proposed algorithm is based on a generalized circulant matrix formalism. Our algorithm generates a schedule that minimizes the number of communication steps and eliminates node contention in each communication step. The network bandwidth is fully utilized by ensuring that equal-sized messages are transferred in each communication step. Furthermore, the procedure to compute the schedule and the index sets is extremely fast. It takes O(max(P, Q)) time. Therefore, our proposed algorithm is suitable for run-time array redistribution. To evaluate the performance of our scheme, we have implemented the algorithm using C and MPI. The experiments were conducted on the IBM SP2. The experimental results show that the proposed algorithm outperforms well- known algorithms with respect to the total redistribution time including the data transfer and schedule and index computation times.

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of resource deadlocks has not been addressed in many previously proposed wormhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. We provide upper bounds for the number of consumption channels required to avoid deadlocks. In addition, we present a new multicast routing algorithm, column-path, which is based on the well-known dimension-order routing used in many multicomputers and multiprocessors. Therefore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multicast routing algorithms. Our results show that for multicast traffic, the column-path routing offers higher throughputs, while the multipath algorithm offers lower message latencies. Another result of our study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good performance provided the number of destinations is small.

In this paper, we develop algorithms in order of efficiency for all-to-all broadcast problem in an N=2/sup n/-node n-dimensional faulty SIMD hypercube, Q/sub n/, with up to n-1 node faults. The algorithms use a property of a certain ordering of dimensions. Our analysis includes startup time (/spl alpha/) and transfer time (/spl beta/). We have established the lower bound for such an algorithm to be n/spl alpha/+(2N-3)L/spl beta/ in a faulty hypercube with at most n-1 faults (each node has a value of L bytes). Our best algorithm requires 2n/spl alpha/+2NL/spl beta/ and is near-optimal. We develop an optimal algorithm for matrix multiplication in a faulty hypercube using all-to-all broadcast and compare the efficiency of all-to-all broadcast approach with broadcast approach and global sum approach for matrix multiplication. The algorithms are congestion-free and applicable in the context of available hypercube machines.

In this paper, we present a scalable dynamic multicast routing algorithm based on a dynamic Steiner tree approach. First, we analyze a hierarchical multicast routing algorithm which introduced the use of core nodes in each peer-group to support multicasting under the private network-network interface (PNNI) framework. Based on this analysis, we conclude that finding near-optimal multicast trees in each peer-group is important. Our proposed algorithm produces improved results by computing better multicast trees within each peer-group. This scheme also eliminates the dependency of core node selection, on the quality of overall multicast tree generated. We compare the two schemes based on simulations on several randomly generated graphs of size ranging from 115 to 170 nodes. Based on these simulations, we show that our algorithm performs 35% better than the hierarchical algorithm. Our algorithm is scalable, allows incorporation of fault-tolerance and can easily be extended to incorporate a QoS criterion in routing.

Ray tracing is a well known technique to generate life-like images. Unfortunately, ray tracing complex scenes can require large amounts of CPU time and memory storage. Distributed memory parallel computers with large memory capacities and high processing speeds are ideal candidates to perform ray tracing. However, the computational cost of rendering pixels and patterns of data access cannot be predicted until runtime. To parallelize such an application efficiently on distributed memory parallel computers, the issues of database distribution, dynamic data management and dynamic load balancing must be addressed. In this paper, we present a parallel implementation of a ray tracing algorithm on the Intel Delta parallel computer. In our database distribution, a small fraction of database is duplicated on each processor, while the remaining part is evenly distributed among groups of processors. In the system, there are multiple copies of the entire database in the memory of groups of processors. Dynamic data management is acheived by an ALRU cache scheme which can exploit image coherence to reduce data movements in ray tracing consecutive pixels. We balance load among processors by distributing subimages to processors in a global fashion based on previous workload requests. The success of our implementation depends crucially on a number of parameters which are experimentally evaluated. © 1997 John Wiley & Sons, Ltd.

A significant barrier inhibiting the use of parallel computing is the difficulty of writing parallel software. One solution to this problem is to build tools that can automatically convert sequential programs to parallel programs. In this paper we describe the implementation of a system that is designed to perform a semantic level analysis and transformation of algorithms in sequential programs. Our approach is based on pattern matching and has been inspired by recent research on reverse engineering and program understanding. We describe the architecture of our system, a pattern matching language that we have designed, our pattern matching strategy, and illustrate the approach and implementation using examples. This paper is a summary of the work.

We consider the problem of computing a global commutative and associative operation, also known as semi-group operation, (such as addition and multiplication) on a faulty hypercube. In particular, we study the problem of performing such an operation in an n-dimensional SIMD hypercube, Q/sub n/, with up to n-1 node and/or link faults. In an SIMD hypercube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. Given a set of at most n-1 faults, we develop an ordering d/sub 1/,d/sub 2/,...,d/sub 1/ of n dimensions, depending on where the faults are located. An important and useful property of this dimension ordering is the following: if the n-cube is partitioned into k-subcubes using the first k dimensions of this ordering, namely d/sub 1/, d/sub 2/,..., d/sub n/ for any 2/spl les/k/spl les/n, then each k-subcube in the partition contains at most k-1 faults. We use this result to develop algorithms for global sum. These algorithms use 3n-2, n+3 log n+3 log log n, and n+log n+d/sub 2/ log log n+O(log log log n) time steps, respectively.

This paper presents an accurate analytical model for evaluating the performance of the join the shortest queue (JSQ) policy. The system considered consists of N identical queues each of which may have single or multiple servers. A birth-death Markov process is used to model the evolution of the number of jobs in the system. Our results show that this method provides very accurate estimates of the average job response times.

We consider the problem of embedding and reconfiguring binary tree structures in faulty hypercubes. We assume that the number of faulty nodes is at most (n-2), where n is the number of dimensions of the hypercube; we further assume that the location of faulty nodes are known. Our embedding techniques are based on a key concept called free dimension, which can be used to partition a cube into subcubes such that each subcube contains at most one faulty node. Using this approach, two distributed schemes are provided for embedding and reconfiguration in faulty hypercubes. We extend the free dimension concept to degree of occupancy and use this to develop a distributed scheme for reconfiguration of binary tree in faulty hypercubes with up to [3n/2] node faults.

In a sort-last polygon rendering system, the efficiency of image composition is very important for achieving fast rendering. In this paper, the implementation of a sort-last rendering system on a general purpose multicomputer system is described. A two-phase sort-last-full image composition scheme is described first, and then many variants of it are presented for 2D mesh message-passing multicomputers, such as the Intel Delta and Paragon. All the proposed schemes are analyzed and experimentally evaluated on Caltech's Intel Delta machine for our sort-last parallel polygon renderer. Experimental results show that sort-last-sparse strategies are better suited than sort-last-full schemes for software implementation on a general purpose multicomputer system. Further, interleaved composition regions perform better than coherent regions. In a large multicomputer system. Performance can be improved by carefully scheduling the tasks of rendering and communication. Using 512 processors to render our test scenes, the peak rendering rate achieved on a 282,144 triangle dataset is dose to 4.6 million triangles per second which is comparable to the speed of current state-of-the-art graphics workstations.

Hypercube network is an attractive structure for parallel processing due to its symmetry and regularity. We use the concept of free dimensions to achieve fault tolerance in hypercubes without requiring additional spare processing nodes; such additional redundancy requires modification of hypercube structure. A free dimension is defined to be a dimension across which both end nodes are not faulty. Given an n-dimensional hypercube, Qn, and a set of f/spl les/n faulty nodes, we present an efficient algorithm to find free dimensions, and show that at least n-f+1 free dimensions exist. Free dimensions can be used to partition Q/sub n/ into subcubes such that each subcube contains at most one fault. Such a partitioning helps in achieving fault tolerance via emulation, embedding, reconfiguration. It also helps in designing efficient routing and broadcasting algorithms in faulty hypercubes.>

Self-routing interconnection networks with their low processing-overhead delay and decentralized routing, are an attractive option for switching fabrics in high speed networks. These interconnection networks, however, realize only a subset of all possible input-output permutations in a non-blocking fashion. The non-blocking property of these networks is an extensively studied area in interconnection network theory field and efficient algorithms exist to check if any given permutation is passable by such networks without blocking. One of the most common interconnection network structures is the inverse omega network and is topologically equivalent to the reverse banyan network. The authors show how to check the passability by the inverse omega network of any given connection set and list some of the very general patterns passable by this network. They also show that the concentrate operation passable by the inverse omega network is just a special case of the more general alternate sequence operation that they show as being passable. These non-blocking properties will be useful for cell routing in switches built with blocking networks in parallel or in cascade.>

We address a significant problem in parallel processing research, namely, how to port existing sequential programs to run efficiently on parallel machines (the dusty deck problem). Conventional domain-independent techniques are inadequate for solving this problem because they miss significant opportunities of parallelism. We present experimental evidence to support our claim, analyze why current techniques are inadequate, and propose a knowledge-based reverse engineering approach for attacking this problem. >

Ray tracing is one of the computer graphics techniques used to render high quality images. Unfortunately, ray tracing complex scenes can require large amounts of CPU time, making the technique impractical for everyday use. Parallel ray tracing algorithms could potentially be used to reduce the high computational cost. However, pixel computation times can vary significantly, and naive attempts at parallelization give poor speedups due to load imbalance between the processors. In this paper, we evaluate the performance of three load balancing schemes for ray tracing on parallel processors, and propose two new load balancing strategies. To evaluate the performance, we implement all these strategies on the 512 processor Intel Touchstone Delta at Caltech.

During the past decade there has been an explosive growth in the areas of parallel and distributed computing.Several commercial parallel machines became available in the market including machines from Intel, KSR, IBM, to name a few.At least a dozen types of workstaition are available for general purpose computing which are inexpensive and quite powerful.In any organization, we can find dozens of such high-end workstations.As the parallel machines are still relatively expensive in comparison to a cluster of workstations, a recent trend is to use a collection of idle workstations as a virtual parallel machine.Such a networked configuration can be used to achieve high performance for computationallyintensive applications.Some researchers are predicting that these 'network computers' will be the future supercomputers.Clearly, use of a number of workstations for a common task is a cost-effective way of obtaining parallel computing.It is possible to include a parallel machine as a node in such networked configurations.In order for this network or cluster computing to be useful for many applications, there must be progress in a number of areas.These include development of highspeed networks, software tools for porting applications, tools and language support for programming, high performance YO etc.The IEEE Symposium on High-performance Distributed Computing was established in 1992 for exchange of ideas among researchers working in various aspects of this emerging area of technology.In HlPDC environments, parallel or distributed computing techniques are applied to the solution of computationally-intensive applications across networks of high-performance computers.The challenging tasks to be addressed by the HPDC community include portabillity of efficient software within the HPDC environment, low latency utilizing current advances in gigabit networks and processing technology, development of HPDC tools and techniques for parallelizing applications over a network of machines.There is scope for conducting research on all these aspects and we invite researchers to take on the challenge in this emerging area of research.This special issue consists of selected papers presented at the Second International Symposium on High-Performance Distributed Computing (HPDC-2) sponsored by the IEEE Computer Society, Syracuse University, and Washington State University, held in Spokane, WA, in July 1993.These papers are selected so that they all address some key aspect of the problems that are critical in high performance distributed computing environments.These papers cover programming of distributed systems, communication issues, design of distributed environments, and transport services.Soluitions to computationally-intensive applications, such as climate prediction, need high performance parallel and distributed system technology.In order to utilize successfully such advanced systems, it is important to develop parallel software for such applications.In the paper 'Object-Based Approach to Programming Distributed Systems' (A. S. 'Tanenbaum, H. E. Bal, S. Ben Hassen and M. Frans Kaashoek), a hybrid model with object-based shared memory is presented.They have also constructed a prototype system and programmed applications for this system using their approach.

Fault tolerance in hypercubes is achieved by exploiting inherent redundancy and executing tasks on faulty hypercubes. The authors consider tasks that require linear chain, ring, mesh, and torus structure, which are quite useful in parallel and pipeline computations. They assume the number of faults is on the order of the number of dimensions of the hypercube. The techniques are based on a key concept called free dimension, which can be used to partition a cube into subcubes such that each subcube contains, at most, one faulty node. Subgraphs are embedded in each subcube and then merged to form the entire graph.>

The authors describe a fully distributed, parallel algorithm for ray-tracing problem. Load balancing is achieved through the use of comb distribution to roughly assign the same amount of pixels to each processor first, and then dynamically redistribute excessive loads among processors to keep each processor busy. In this model, there is no need for a master node to be responsible for dynamic scheduling. When each node finishes its job, it just requests an extra job from one of its neighbors. The authors implement their algorithm on Intel Delta Touchstone machine with 2-D mesh network topology and provide simulation results. With their scheme, they can get good speedup and high efficiency without much communication overhead.>

Exact performance analyses of dynamic load-balancing policies for distributed systems are very difficult because the state space is multidimensional and load-balancing decisions are state-dependent. A state-aggregation method is proposed to analyze the performance of dynamic load-balancing policies. Those states with the same number of jobs are aggregated into a single state. The number of jobs in the system is modeled by a birth-death Markov process. The state transition rates are estimated by an iterative procedure. The proposed state-aggregation method is applied to analyze the performance of a particular dynamic load-balancing policy, namely a symmetric policy with threshold value equal to one. Extensive simulations were performed to study the accuracy of the state-aggregation method. This method provides accurate performance estimates for the symmetric policy for systems of various sizes when the mean job transfer delay is small compared to the average job service time.>

The fundamental question addressed in this paper is that of computing the parallel prefix operation. In particular, we study the problem of performing such an operation in an n-dimensional SIMD hypercube, Q_n, with up to n-1 node faults. In an SIMD hypercube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. We exhibit an n+5 logn algorithm for this problem. The development of the algorithm is based on the existence of two so-called free dimensions in such a faulty hypercube [6].

The ARIES reliability model, which models a class of repairable and nonrepairable fault-tolerant systems by a continuous-time Markov chain and uses the Lagrange-Sylvester interpolation formula to directly compute the exponential of the state transition rate matrix (STRM) that appears in the solution of the Markov chain, is discussed. The properties of the STRM for ARIES repairable systems are analyzed. Well-established results in matrix theory are used to find an efficient solution for reliability computation when the eigenvalues of the STRM are distinct. A class of systems that ARIES models for which the solution technique is inapplicable is identified. Several transformations which are known to be numerically stable are used in the solution method. The solution method also offers a facility for incrementally computing reliability when the number of spares in the fault-tolerant system is increased by one.>

In an n-dimensional hypercube Qn, with the fault set mod F mod>

An analytical method is developed to analyze the performance of the join the shortest queue (JSQ) policy for systems with N identical queues, N>or=2. No simulation result is used to refine the analytical model. A birth-death Markov process is used to model the evolution of the total number of jobs in the system. An iterative procedure is developed to estimate the average service rates for different states. The average job response time is then obtained. Extensive simulations are performed to study the accuracy of the analysis. Results show that this method provides estimates within 3.5% of the average job response times for N up to 64.>

A dynamic load-balancing policy is proposed with a central job dispatcher called the LBC policy for distributed systems. The design of this policy is motivated by the operation of a single-queue multiserver queueing system, and the average job response time is the same as that of a single-queue multiserver system, which is the best achievable performance when the communication delay is reduced to zero. Hence, near-minimum average job response time is expected for distributed systems with high-speed communication subnets. The performance is studied for systems with nonnegligible job transfer delays in the following three aspects: average job response time, overhead due to information exchanges, and sensitivity to heterogeneous load.>

A set of routing criteria is proposed for circuit-switched hypercubes that exploit the flexibility provided by the hypercube. The routing criteria are provably deadlock-free and route messages along shortest paths. The number of shortest paths allowed by the routing criteria is more than one for most source-destination pairs. It is shown that the flexibility provided by the routing criteria can be used to limit the negative effects due to component-failures. The exact number of disrupted source-destination pairs are derived in the presence of a single faulty link or a single faulty node. It is shown that these numbers can be minimized using the relabeling techniques proposed. It is shown that the criteria, if used effectively, lead to a significant improvement in performance over the e-cube routing strategy for non-uniform traffic.>

A dynamic load balancing policy with a central job dispatcher, called the LBC policy, is proposed for distributed systems. The design of this policy is motivated by the operation of a single-queue-multi-server queuing system. The average job response time of this policy is the same as that of a single-queue-multi-server system which is the best achievable performance when the communication delay is reduced to zero. Hence, this policy is expected to provide near minimum average job response time for distributed systems with high-speed communication subnets. The performance of this policy is studied for systems with non-negligible job transfer delays in the following three aspects: average job response time, overhead due to information exchanges, and sensitivity to heterogeneous load.>

A study is made of three dynamic load balancing policies in distributed systems with service interruptions, namely, sender initiated, receiver initiated, and a combination of the two, in different cases: performing and not performing load-balancing functions while the computers are in the middle of interruptions. The policies are analyzed by using decomposition approximation and matrix-geometric solution techniques. Simulations are used to validate the analytical results. The policies are compared to each other and to no load balancing. Sensitivities of the performance to the characteristics of interruptions and design parameters are studied. It is concluded that load balancing has a significant advantage in improving performance. Performing load-balancing functions while the computers are in the middle of interruptions also provides considerable performance improvement.>

The authors present self-routing algorithms for realizing the class of linear permutations in various multistage networks such as Benes and 2n-stage shuffle-exchange. Linear permutations are useful in providing fast access of data arrays. In the first half of the network, switches are set by comparing the destination tags at their inputs, and, in the second half, switches are set using the Omega self-routing algorithm. It is shown that the comparison operations can be implemented in bit-serial networks without loss of time. In contrast, with the well-known Benes network self-routing algorithm of D. Nassimi and S. Sahni (1981), switches are set by giving priority to the destination tag at the upper input to them. The algorithms presented are useful in providing fast access of various data patterns using interconnection networks cheaper than crossbars.>

The authors introduce a novel class of networks based on the de Bruijn graph. These directed graphs are regular of degree, have N=k/sup n/ vertices for some n, and can tolerate up to k-2 node faults. Their fault-free diameter is n=log/sub k/N, and this is increases by at most 1 hop in the presence of k-2 faults. This class is very rich: for any given N=k/sup n/, one can construct at least 2/sup N/ different graphs. This is in sharp contrast to most other such constructions (including the de Bruijn graph), in which only one graph exists for each N. It is also shown how to implement certain algorithms on these networks.>

Optimal allocation of redundant resources in distributed computing systems is studied. In the model, the triple module redundancy (TMR) scheme is adopted to enhance the reliability of the operations. A retrieval request from a site for a database will be processed by three database servers. The output results will be obtained by majority voting. The objective is to find the number of database copies and their locations that optimize the total operation cost. Both static and dynamic allocation environments are considered. The problem is formulated as a zero/one integer programming problem. Preliminary test results show that the algorithm has fast convergence and provides a tight lower bound for the optimal operational cost. In particular, it offers high flexibility in terms of termination criteria, which makes it useful in a dynamic allocation environment.>

The authors study methods for routing data in supercomputers that use multistage interconnection networks (MINs) in the presence of faulty components in the network. These methods are applicable to existing multiprocessors such as the IBM GF11 and RP3. These methods are based on the concept of dynamic full-access (DFA) which refers to the ability of the network to route data from any processor in the system to any other processor in a finite number of passes through the network. The authors introduce a graph-model called the DFA graph of a MIN and show how it can be used to determine the DFA capability of the MIN under a given set of network faults. When the faults in the network satisfy certain special properties, algorithms for routing any arbitrary permutation in a faulty Benes network and any Omega permutation in a faulty Omega network are presented.>

It is observed that a large number of closed fault-tolerant systems modeled by a continuous-time Markov model referred to as the ARIES model have repeated eigenvalues. It is proven that the rate matrix representing the system is diagonalizable for every closed fault tolerant system modeled by ARIES. Consequently, the Lagrange-Sylvester interpolation formula is applicable to all closed fault-tolerant systems which ARIES models. Since the proof guarantees that the rate matrix is diagonalizable, general methods for solving arbitrary Markov chains can be tailored to solve the ARIES model for the closed systems directly.>

A linear systolic array with fault-tolerant capabilities is described. Fault tolerance is achieved by using triple time redundancy. The array is capable of undergoing reconfiguration and can operate in a gracefully degradable mode. The concept of algorithm remapping on degraded (smaller) arrays is integrated with that of graceful degradation to obtain a general fault-tolerance technique. A new technique for restructuring algorithms and executing them on a degraded array is discussed. The requisite modifications of the interconnection, switching, and control structures to achieve fault tolerance are discussed. Reliability analysis of the system is carried out, and the reliability is compared to that of nonredundant systolic arrays. Finally, the average performance of the system, with running time and throughput as performance metrics, is estimated.>

A new resource allocation model is presented in which a given number of copies of a single resource are allocated to the processing sites in such a way that the total communication cost incurred is minimized. The accessing scheme considers both the communication costs and the load levels at the resource sites. Load leveling is imposed as a constraint. This improves system throughput as well as response time. The allocation provided by the model reflects the realistic environment more accurately and therefore gives a better dynamic performance. It is shown that the model can be extended to include other costs such as installation cost and communication cost due to 'write' accesses.>

The fault tolerance of multiprocessor systems with multistage interconnection networks under multiple faults in the network is studied. The fault tolerance is analyzed with respect to the criterion of dynamic full access (DFA) property of the processors in the system. A characterization of multiple faults in the Omega network is introduced and used to develop simple tests for the DFA capability under a given set of faults. It is shown that the DFA capability is maintained under a large number of faults. A maximum of three passes is shown to be sufficient for communication between any two processors in the system when the faults satisfy certain conditions which can be checked easily. For cases in which these conditions do not hold, at most log/sub 2/N-2 passes through the network are shown to be sufficient if a set of weaker conditions is satisfied. Techniques for routing data between processing elements through the faulty network are described. Extension of the results to general k-stage shuffle/exchange networks with k>

Two pseudo-concurrent fault diagnostic approaches, namely, a roving spare technique and an inverse residue checking technique, and a testing strategy for processing elements in a high-speed signal processing system, are studied. The system consists of an array of identical (differing only in programmable coefficients) chips that perform complex arithmetic operations. Expressions for fault coverage and average fault latency using random tests for the two diagnostic techniques are obtained. A tradeoff between hardware overhead and average fault latency is identified. A comparison of the two techniques with respect to a set of attributes is presented. The fault-diagnostic techniques described were found to be suitable for implementation on a generalized-sidelobe-cancellor architecture mainly because of the memoryless property of the computations.>

The authors describe an example signal-processing design which illustrates partitioning, performance, cost, and fault-tolerance tradeoffs. They focus on high-performance multiplication using the power-of-two number representation as implemented in the POTATO (power of two arithmetic time-optimized) chip architecture. The implementation is compared to more conventional designs, and performance estimates are given. It is concluded that the design compares favourably to more conventional implementations.>

Optimal allocation of redundant resources in distributed computing systems is studied. In this model, a request from a processing site for a resource can be satisfied by any one of the copies. Among the redundant copies of the resources, the least-expensive and the second-least-expensive ones are considered for accessing by each processing site, which is measured in terms of communication cost. This access scheme offers to encompass some of the intrinsically important features, such as graceful degradation and reliability consideration, in the design model. The increase of communication cost due to the failures of resources should be gradual to maintain the system performance. With the present formulation, the goal of the allocation is to minimize the total communication cost incurred. The Lagrangian relaxation and subgradient methods are applied to solve this problem. An efficient algorithm based on these techniques, and computational results, are presented.>

Double-loop networks have a higher connectivity and therefore a higher potential for fault tolerance than single-loop networks. The authors present distributed routing schemes that fully utilize that fault-tolerance potential, and that are applicable in particular to a specific class of double-loop networks, characterized by a forward loop connecting all the adjacent nodes, and a backward loop connecting nodes separated by a distance that depends on N, the number of nodes. A nice feature of these schemes is that for a given node, only local knowledge on the status of the neighboring nodes and links is required. Yet the schemes detect faulty nodes and links and adapt to the situation, so that a packet will eventually reach its destination, if there exists a path. A simulation has shown that the average overhead resulting from the schemes, in terms of number of hops, does not exceed 17%, for values of N around 16.>

The load balancing and routing problems are combined as a single problem to capture the interaction between them. An optimization problem for joint load balancing and routing is formulated using a linear combination of the average job response time and average message delay as the performance criterion. Given an initial feasible solution, the Frank-Wolfe method is applied to solve the problem. An algorithm which gives an optimal solution is obtained. The algorithm is then extended to solve the same problem with multiple types of jobs.>

Reliability of a distributed processing system is an important design parameter that can be described in terms of the reliability of processing elements and communication links and also of the redundancy of programs and data files. The traditional terminal-pair reliability does not capture the redundancy of programs and files in a distributed system. Two reliability measures are introduced: distributed program reliability, which describes the probability of successful execution of a program requiring cooperation of several computers, and distributed system reliability, which is the probability that all the specified distributed programs for the system are operational. These two reliability measures can be extended to incorporate the effects of user sites on reliability. An efficient approach based on graph traversal is developed to evaluate the proposed reliability measures.>

Although a theoretical lower bound of (2 log/sub 2/N-1) stages for rearrangeability of a network with N=2/sup n/ inputs and outputs has been known, the sufficiency of (2 log/sub 2/N-1) stages has neither been proved nor disproved. The best known upper bound for rearrangeability is (3 log/sub 2/N-3) stages. It is proved that if (2 log/sub 2/R-1) shuffle/exchange stages are sufficient for rearrangeability of a network with R=2/sup r/ inputs and outputs, then for any N>R, (3 log/sub 2/N-(r+1)) stages are sufficient for a network with N inputs and outputs. This result is established by setting some of the middle stages of the network to realize a fixed permutation and showing the reduced network to be topologically equivalent to a member of the Benes class of rearrangeable networks. From the known result that five stages are sufficient for rearrangeability when N>or=8, an upper bound of (3 log/sub 2/N-4) is obtained. Any increase in the network size R for which the rearrangeability of (2 log/sub 2/R-1) stages can be shown results in corresponding improvements in the upper bound for all N>or=R. As a result of the one-to-one correspondence that exists between the switches in the reduced shuffle/exchange network and those in the Benes network, the former network can be controlled by the well-known looping algorithm.>

In this paper we study the rearrangeability of multistage shuffle/exchange networks. Although a theoretical lower bound of (2 log2N - 1) stages for rearrangeability of a network with N = 2n inputs and outputs has been known, the sufficiency of (2 log2N - 1) stages has neither been proved nor disproved. The best known upper bound for rearrangeability is (3 log2N - 3) stages. We prove that, if (2 log2R - 1) shuffle/exchange stages are sufficient for rearrangeability of a network with R = 2' inputs and outputs, then, for any N > R, 3 log2N - (r + 1) stages are sufficient for a network with N inputs and outputs. This result is established by setting some of the middle stages of the network to realize a fixed permutation and showing the reduced network to be topologically equivalent to a member of the Benes class of rearrangeable networks. We first characterize equivalence to Benes networks in set-theoretic terms and use this to prove equivalence of the reduced shuffle/exchange network to the Benes network. From the known result that 5 stages are sufficient for rearrangeability when N = 8, we obtain an upper bound of (3 log2N - 4) stages for rearrangeability when N ≥ 8. Further, any increase in the network size R for which the rearrangeability of (2 log2R - 1) stages could be shown, results in a corresponding improvement in the upper bound for all N ≥ R.

Symbolic terminal reliability algorithms are important for analysis and synthesis of computer networks. In this paper, we present a simple and efficient algorithm, SYREL, to obtain compact terminal reliability expressions between a terminal pair of computers of complex networks. This algorithm incorporates conditional probability,, set theory, and Boolean algebra in a distinct approach in which most of the computations performed are directly executable Boolean operations. The conditibnal probability is used to avoid applying at each iteration the most time consuming step in reliability algorithms, which is making a set of events mutually exclusive. The algorithm has been implemented on a VAX 11/750 and can analyze fairly large networks with modest memory and time requirements.

In this paper we prove the rearrangeubility of a multistage shuffle/exchange network with eight inputs and outputs consisting of five stages. A lower bound of (2 log_{2} N - 1) stages for rearrangeability of a Shuffle/exchange network withN = 2^{n}inputs and outputs is known; we show its sufficiency forN = 8. We not only prove the rearrangeability, but also describe an algorithm for routing arbitrary permutations on the network and prove its correctness. In contrast to previous efforts to prove rearrangeability, which rely on topological equivalence to the Benes class of rearrangeable networks, our approach is based on first principles. We also show that two switches in the network are redundant. The results in this paper are useful for establishing an upper bound of (3 log_{2} N - 4) stages for rearrangeability of a multistage shuffle/exchange network withN \geq 8, as demonstrated in [12].

Performing permutations of data on SIMD computers efficiently is important for high-speed execution of parallel algorithms. In this correspondence we consider realizing permutations such as perfect shuffle, matrix transpose, bit-reversal, the class of bit-permute- complement (BPC), the class of Omega, and inverse Omega permutations on N = 2n processors with Illiac IV-type interconnection network, where each processor is connected to processors at distances of ± 1 and ± N. The minimum number of data transfer operations required for realizing any of these permutations on such a network is shown to be 2(N − 1). We provide a general three-phase strategy for realizing permutations and derive routing algorithms for performing perfect shuffle, Omega, Inverse Omega, bit reversal, and matrix-transpose permutations in 2(N − 1) steps. Our approach is quite simple, and unlike previous approaches, makes efficient use of the topology of the Illiac IV-type network to realize these permutations using the optimum number of data transfers. Our strategy is quite powerful: any permutation can be realized using this strategy in 3(N − 1) steps.

In this paper, we study fault-tolerant multiprocessor systems employing redundant-path multistage interconnection networks. Such systems permit interprocessor communication in the presence of faulty components in the network. The interconnection network considered is a delta network augmented with an extra switching stage in front. When the first and last stages are fault-free, the extra-stage delta networks continue to provide full access in the presence of all single and many multiple faults in switching elements of the intermediate stages. In this paper, we use graph-theoretic techniques to study the problem of routing permutations in extra-stage delta networks when faults are present in the network. We first formulate the problem of performing an arbitrary permutation on the fault-free network as a vertex-coloring problem and later extend this to networks with noncritical faults. Although the general problem of realizing a permutation in the minimum number of passes is intractable, classes of permutations with some regularity can be routed optimally. To illustrate the idea, we consider the class of BPC (bit permute-complement) permutations: algorithms for performing arbitrary permutations in this class on the extra-stage delta network are given, both for the fault-free network and for a network with noncritical faults.

The reliability of distributed processing systems can be expressed in terms of the reliability of the processing elements that run the programs, the reliability of the processing elements holding the required files, and the reliability of the communication links used in file transfers. The authors introduce two reliability measures, namely distributed program reliability and distributed system reliability, to accurately model the reliability of distributed systems. The first measure describes the probability of successful execution of a distributed program which runs on some processing elements and needs to communicate with other processing elements for remote files, while the second measure describes the probability that all the programs of a given set can run successfully. The notion of minimal file spanning trees is introduced to efficiently evaluate these reliability measures. Graph theory techniques are used to systematically generate file spanning trees that provide all the required connections. The technique is general and can be used in a dynamic environment for efficient reliability evaluation.

article Free Access Share on Array processor with multiple broadcasting Authors: V. K. Prasanna Kumar Department of Electrical Englneerlng-Systems, University of Southern California, Los Angeles, CA Department of Electrical Englneerlng-Systems, University of Southern California, Los Angeles, CAView Profile , C. S. Raghavendra Department of Electrical Englneerlng-Systems, University of Southern California, Los Angeles, CA Department of Electrical Englneerlng-Systems, University of Southern California, Los Angeles, CAView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 2–10https://doi.org/10.1145/327070.327110Published:01 June 1985Publication History 27citation230DownloadsMetricsTotal Citations27Total Downloads230Last 12 Months14Last 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A new approach to the design of gracefully degradable processor arrays is discussed. Fault tolerance and graceful degradation are achieved by simultaneously reconfiguring the processor array and the algorithm in execution. Two types of algorithm reconfigurability are considered, namely, row reconfigurability (RR) and row-column reconfigurability (RCR). correspondingly, two array reconfiguration schemes are discussed, i.e., successive row elimination (SRE) and alternate row-column elimination (ARCE). It is shown that the computations of any algorithm executable in a processor array can always be (re) organized so that the resultant algorithm has the RR and/or RCR properties. Upper bounds on the increase in execution time of an algorithm due to reorganization of computations for reconfigurability are derived. Detailed analysis of performance and reliability is done for both SRE and ARCE reconfiguration schemes. These reconfiguration techniques are applicable to any processor array and suitable for VLSI technology.

Single-loop networks tend to become unreliable when the number of nodes in the network becomes large. Reliability can be improved using double loops. In this paper a highly reliable and efficient double-loop network architecture is proposed and analyzed. This network is based on forward loop backward hop topology, with a loop in the forward direction connecting all the neighboring nodes, and a backward loop connecting nodes that are separated by a distance ⌊√N⌋where N is the number of nodes in the network. It is shown that this topology is optimal, among this class of double-loop networks, in terms of diameter, average hop distance, processing overhead, delay, throughput, and reliability. The paper includes derivation of closed form expressions for diameter and average hop distance, throughput, and number of distinct routes between two farthest nodes. For fault-tolerance study, the effect of node and link failures on the performance of the network is analyzed. A simple distributed routing algorithm for reliable loop network operation is also presented.

Single loop networks tend to become unreliable and suffer from poor performance when the number of nodes in the network becomes large. One approach to increasing reliability and improving performance is to use a double loop. In this paper, the performance (using analytical and simulation models) of a class of highly reliable double loop network architectures is presented. The richer topology of double loop networks allows more sophisticated routing algorithms to be used. Several routing algorithms are studied, including: fixed, adaptive to failure, and fully adaptive to failure and traffic load conditions.

The reliability of a distributed system depends on the reliabilities of its communication links and computing elements, as well as on the distribution of its resources, such as programs and data files. A useful measure of reliability in distributed systems is the terminal reliability between a pair of nodes which is the probability that at least one communication path exists between these nodes. An interesting optimization problem is that of maximizing the terminal reliability between a pair of computing elements under a given budget constraint. Analytical techniques to solve this problem are applicable only to special forms of reliability expressions. In this paper, three iterative algorithms for terminal reliability maximization are presented. The first two algorithms require the computation of terminal reliability expressions, and are therefore efficient for only small networks. The third algorithm, which is developed for large distributed systems, does not require the computation of terminal reliability expressions; this algorithm maximizes approximate objective functions and gives accurate results. Several examples are presented to illustrate the approximate optimization algorithm and an estimation of the error involved is also given.

The Gamma network is an interconnection network connecting N = 2n inputs to N outputs. It is a multistage network with N switches per stage, each of which is a 3 input, 3 output crossbar. The stages are linked via "power of two" and identify connections in such a way that redundant paths exist between the input and output terminals. In this network, a path from a source to a destination may be represented using one of the redundant forms of the difference between the source and destination numbers. The redundancy in paths may thus be studied using the theory of redundant number systems. Results are obtained on the distribution of paths connecting inputs and outputs, and the permuting capabilities of the Gamma network. Frequently used permutations and control mechanisms are discussed briefly. We also perform a detailed terminal reliability analysis of the Gamma network, deriving expressions for the reliability between an input and output terminal.

Binary tree network architectures are applicable in the design of hierarchical computing systems and in specialized high-performance computers. In this correspondence, the reliability and fault tolerance issues in binary tree architecture with spares are considered. Two different fault-tolerance mechanisms are described and studied, namely: 1) scheme with spares; and 2) scheme with performance degradation. Reliability analysis and estimation of the fault-tolerant binary tree structures are performed using the interactive ARIES 82 program. The discussion is restricted to the topological level, and certain extensions of the schemes are also discussed.

Large, high-performance computers are too costly to allow full replication for fault detection and error correction in the communication and processing of numerical information. For this reason more cost-effective arithmetic error code applications offer an attractive alternative.

The Gamma network is an interconnection network connecting N=2' inputs to N outputs. It consists of log 2 N stages with N switches per stage, each of which is a 3 input, 3 output crossbar. The stages are linked via “power of two” and identity connections in such a way that redundant paths exist between the input and output terminals. In this network, a path from a source to a destination may be represented using one of the redundant forms of the difference between the source and destination numbers. The redundancy in paths may thus be studied using the theory of redundant number systems. Results are obtained on the distribution of paths connecting inputs to outputs, and the permuting capabilities of the Gamma network. Switch settings for certain frequently used permutations and control mechanisms are also considered in this paper. This network has an interesting application in solving tridiagonal systems using the odd-even elimination algorithm.

On-line arithmetic is a special class of serial arithmetic where algorithms produce results with the most significant digit first during the serial input of the operands. Speedup of computations can be achieved by overlapping or pipelining successive operations with small delays. This paper describes the design and implementation of a simulator for on-line arithmetic algorithms. The simulator was designed primarily to serve as 1) an experimental tool for synthesis of on-line algorithms; 2) a performance evaluation tool of on-line arithmetic; 3) an on-line calculator in solving some problems involving linear and non-linear recurrences. The simulator evaluates arithmetic expressions given in a highly functional form. Presently, the set of operations supported include addition, subtraction, multiplication, division, and square root. Several examples are presented in this paper to illustrate the usage of the simulator. The simulator package is implemented in ‘C’ language on a VAX 11/780 system.

Double loop network architectures offer higher performance and reliability than single loop networks. In this paper, a double loop network which is optimal among all double loops is described. This network topology consists of a loop in the forward direction connecting all the neighboring nodes, and a backward loop connecting nodes that are separated by a distance @@@@@@@@N@@@@, where N is the number of nodes in the network. We show that this network is optimal in terms of hop distance between nodes, delay, throughput, and terminal reliability. The paper includes derivation of closed form expressions for the maximum and average hop distance between nodes, number of distinct routes between two farthest nodes, and throughput. The effect of node and link failures on network performance is also considered.