16405002
The fat-stack and universal routing in interconnection networks
This paper shows that a novel network called the fat-stack is universally efficient and is suitable for use as an interconnection network in parallel computers. A requirement for the fat-stack to be universal is that link capacities double up the levels of the network. The fat-stack resembles the fat-tree and the fat-pyramid in hardware structure, but it has unique strengths. It is a construct of an atomic subnetwork unit consisting of one ring and one or more upward links to an upper subnetwork. This simple structure entails easy wirability. The network also uses fewer wires. More importantly, it has the capability to scale up to represent a large-scale distributed network. We developed efficient routing algorithms specific to the fat-stack. Our universality proof shows that a fat-stack variant with increased links and of area @Q(A) can simulate any competing network of area A with O(logA) overhead independently of wire delay. The universality result implies that the augmented fat-stack of a given size is nearly the best routing network of that size. The augmented fat-stack is the minimal universal network for an O(logA) overhead in terms of hardware usage. Actual simulations show that the performance of the augmented fat-stack approaches that of the fat-pyramid and is far higher than that of the fat-tree.
2853176
Loop Fusion via Retiming for DSP Applications
17091320
Universal routing in distributed networks
We show that universal routing can be achieved with low overhead in distributed networks. The validity of our results rests on a new network called the fat-stack. We show that from a routing perspective the fat-stack is efficient and is suitable for use as a baseline distributed network We prove that the fat-stack is universal by routing efficiency. A requirement for the fat-stack to be universal is that link capacities double up the levels of the network. We use methods developed in the areas of VLSI and processor interconnect for much of our analysis. Our universality proof shows that a fat-stack of area /spl Theta/(A) can simulate any competing network of area A with O(log/sup 3/2/ A) overhead independently of wire delay. The universality result implies that the fat-stack of a given size is nearly the best routing network of that size. The fat-stack is also the minimal universal network for an O(log/sup 3/2/ A) overhead in terms of number of links.
27656613
Multi-level Loop Fusion with Minimal Code Size
10353520
Finding Self-Similarities in Opportunistic People Networks
Opportunistic network is a type of delay tolerant networks (DTN) where network communication opportunities appear opportunistic. In this study, we investigate opportunistic network scenarios based on public network traces, and our contributions are the following: First, we identify the censorship issue in network traces that usually leads to strongly skewed distribution of the measurements. Based on this knowledge, we then apply the Kaplan-Meier Estimator to calculate the survivorship of network measurements, which is used in designing our proposed censorship removal algorithm (CRA) that is used to recover censored data. Second, we perform a rich set of analysis illustrating that UCSD and Dartmouth network traces show strong self-similarity, and can be modeled as such. Third, we pointed out the importance of these newly revealed characteristics in future development and evaluation of opportunistic networks.
5211158
Finding Frequent Items in Data Streams
We present a 1-pass algorithm for estimating the most frequent items in a data stream using limited storage space. Our method relies on a data structure called a COUNT SKETCH, which allows us to reliably estimate the frequencies of frequent items in the stream. Our algorithm achieves better space bounds than the previously known best algorithms for this problem for several natural distributions on the item frequencies. In addition, our algorithm leads directly to a 2-pass algorithm for the problem of estimating the items with the largest (absolute) change in frequency between two data streams. To our knowledge, this latter problem has not been previously studied in the literature. c © 2003 Elsevier B.V. All rights reserved.
15381679
A Modular Neural Network Architecture for Pattern Classification Based on Different Feature Sets
We propose a novel connectionist method for the use of different feature sets in pattern classification. Unlike traditional methods, e.g., combination of multiple classifiers and use of a composite feature set, our method copes with the problem based on an idea of soft competition on different feature sets developed in our earlier work. An alternative modular neural network architecture is proposed to provide a more effective implementation of soft competition on different feature sets. The proposed architecture is interpreted as a generalized finite mixture model and, therefore, parameter estimation is treated as a maximum likelihood problem. An EM algorithm is derived for parameter estimation and, moreover, a model selection method is proposed to fit the proposed architecture to a specific problem. Comparative results are presented for the real world problem of speaker identification.
18568401
Capture inter-speaker information with a neural network for speaker identification
Many speaker identification systems are created by model-based approaches, where a statistical model is used to characterize a speaker's voice and no inter-speaker information is used in parameter estimation. It is well known that inter-speaker information is very helpful in discrimination of different speakers. We propose a method for the use of inter-speaker information to improve performance of a model-based speaker identification system. A neural network is employed to capture inter-speaker information from output space of those statistical models. In order to sufficiently utilize inter-speaker information, a rival penalized encoding rule is proposed to design supervised learning pairs for training the neural network. Comparative results in the KING speech corpus show that our method leads to a considerable improvement for a model-based speaker identification system.
12064638
SDD: Secure Distributed Diffusion Protocol for Sensor Networks
A sensor network is a collection of tiny sensor nodes, which consists of sensing, data processing and communicating components. Directed Diffusion is an important data-centric routing protocol of sensor networks. In this paper we present the design of a new secure Directed Diffusion protocol (SDD), which provides a secure extension for the Directed Diffusion protocol. We mainly focus on secure routing and give a simple scheme to securely diffuse data. We have not considered with the in-network aggregation as a goal. In order to support the use of SDD for sensor nodes with extremely limited CPU processing capability, we use an efficient one-way chain and do not use asymmetric cryptographic operations in this protocol. Our security analyses show that SDD is robust against any active attackers or compromised nodes in the network.