OpenRaiser/Intern-Atlas huggingface dataset:
Cooperative Multi-Cell Networks: Impact of Limited-Capacity Backhaul and Inter-Users Links
Venue: arXiv cs.IT 2007
Year: 2007

Cooperative technology is expected to have a great impact on the performance of cellular or, more generally, infrastructure networks. Both multicell processing (cooperation among base stations) and relaying (cooperation at the user level) are currently being investigated. In this presentation, recent results regarding the performance of multicell processing and user cooperation under the assumption of limited-capacity interbase station and inter-user links, respectively, are reviewed. The survey focuses on related results derived for non-fading uplink and downlink channels of simple cellular system models. The analytical treatment, facilitated by these simple setups, enhances the insight into the limitations imposed by limited-capacity constraints on the gains achievable by cooperative techniques.
Heuristic Solution to Protect Communications in WDM Networks using P-cycles
Venue: arXiv cs.NI 2007
Year: 2007

Optical WDM mesh networks are able to transport huge amount of information. The use of such technology however poses the problem of protection against failures such as fibre cuts. One of the principal methods for link protection used in optical WDM networks is pre-configured protection cycle (p-cycle). The major problem of this method of protection resides in finding the optimal set of p-cycles which protect the network for a given distribution of working capacity. Existing heuristics generate a large set of p-cycle candidates which are entirely independent of the network state, and from then the good sub-set of p-cycles which will protect the network is selected. In this paper, we propose a new algorithm of generation of p-cycles based on the incremental aggregation of the shortest cycles. Our generation of p-cycles depends on the state of the network. This enables us to choose an efficient set of p-cycles which will protect the network. The set of p-cycles that we generate is the final set which will protect the network, in other words our heuristic does not go through the additional step of p-cycle selection
On the Behavior of the Distributed Coordination Function of IEEE 802.11 with Multirate Capability under General Transmission Conditions
Venue: arXiv cs.NI 2007
Year: 2007

The aim of this paper is threefold. First, it presents a multi-dimensional Markovian state transition model characterizing the behavior of the IEEE 802.11 protocol at the Medium Access Control layer which accounts for packet transmission failures due to channel errors modeling both saturated and non-saturated traffic conditions. Second, it provides a throughput analysis of the IEEE 802.11 protocol at the data link layer in both saturated and non-saturated traffic conditions taking into account the impact of both the physical propagation channel and multirate transmission in Rayleigh fading environment. The general traffic model assumed is M/M/1/K. Finally, it shows that the behavior of the throughput in non-saturated traffic conditions is a linear combination of two system parameters; the payload size and the packet rates, $λ^{(s)}$, of each contending station. The validity interval of the proposed model is also derived. Simulation results closely match the theoretical derivations, confirming the effectiveness of the proposed models.
Distributed source coding in dense sensor networks
Venue: arXiv cs.IT 2007
Year: 2007

We study the problem of the reconstruction of a Gaussian field defined in [0,1] using N sensors deployed at regular intervals. The goal is to quantify the total data rate required for the reconstruction of the field with a given mean square distortion. We consider a class of two-stage mechanisms which a) send information to allow the reconstruction of the sensor's samples within sufficient accuracy, and then b) use these reconstructions to estimate the entire field. To implement the first stage, the heavy correlation between the sensor samples suggests the use of distributed coding schemes to reduce the total rate. We demonstrate the existence of a distributed block coding scheme that achieves, for a given fidelity criterion for the reconstruction of the field, a total information rate that is bounded by a constant, independent of the number $N$ of sensors. The constant in general depends on the autocorrelation function of the field and the desired distortion criterion for the sensor samples. We then describe a scheme which can be implemented using only scalar quantizers at the sensors, without any use of distributed source coding, and which also achieves a total information rate that is a constant, independent of the number of sensors. While this scheme operates at a rate that is greater than the rate achievable through distributed coding and entails greater delay in reconstruction, its simplicity makes it attractive for implementation in sensor networks.
Toward Trusted Sharing of Network Packet Traces Using Anonymization: Single-Field Privacy/Analysis Tradeoffs
Venue: arXiv cs.CR 2007
Year: 2007

Network data needs to be shared for distributed security analysis. Anonymization of network data for sharing sets up a fundamental tradeoff between privacy protection versus security analysis capability. This privacy/analysis tradeoff has been acknowledged by many researchers but this is the first paper to provide empirical measurements to characterize the privacy/analysis tradeoff for an enterprise dataset. Specifically we perform anonymization options on single-fields within network packet traces and then make measurements using intrusion detection system alarms as a proxy for security analysis capability. Our results show: (1) two fields have a zero sum tradeoff (more privacy lessens security analysis and vice versa) and (2) eight fields have a more complex tradeoff (that is not zero sum) in which both privacy and analysis can both be simultaneously accomplished.
Bit-interleaved coded modulation in the wideband regime
Venue: arXiv cs.IT 2007
Year: 2007

The wideband regime of bit-interleaved coded modulation (BICM) in Gaussian channels is studied. The Taylor expansion of the coded modulation capacity for generic signal constellations at low signal-to-noise ratio (SNR) is derived and used to determine the corresponding expansion for the BICM capacity. Simple formulas for the minimum energy per bit and the wideband slope are given. BICM is found to be suboptimal in the sense that its minimum energy per bit can be larger than the corresponding value for coded modulation schemes. The minimum energy per bit using standard Gray mapping on M-PAM or M^2-QAM is given by a simple formula and shown to approach -0.34 dB as M increases. Using the low SNR expansion, a general trade-off between power and bandwidth in the wideband regime is used to show how a power loss can be traded off against a bandwidth gain.
Some information-theoretic computations related to the distribution of prime numbers
Venue: arXiv cs.IT 2007
Year: 2007

We illustrate how elementary information-theoretic ideas may be employed to provide proofs for well-known, nontrivial results in number theory. Specifically, we give an elementary and fairly short proof of the following asymptotic result: The sum of (log p)/p, taken over all primes p not exceeding n, is asymptotic to log n as n tends to infinity. We also give finite-n bounds refining the above limit. This result, originally proved by Chebyshev in 1852, is closely related to the celebrated prime number theorem.
Analyzing covert social network foundation behind terrorism disaster
Venue: arXiv cs.AI 2007
Year: 2007

This paper addresses a method to analyze the covert social network foundation hidden behind the terrorism disaster. It is to solve a node discovery problem, which means to discover a node, which functions relevantly in a social network, but escaped from monitoring on the presence and mutual relationship of nodes. The method aims at integrating the expert investigator's prior understanding, insight on the terrorists' social network nature derived from the complex graph theory, and computational data processing. The social network responsible for the 9/11 attack in 2001 is used to execute simulation experiment to evaluate the performance of the method.
A Probabilistic Collocation Method Based Statistical Gate Delay Model Considering Process Variations and Multiple Input Switching
Venue: arXiv cs.AR 2007
Year: 2007

Since the advent of new nanotechnologies, the variability of gate delay due to process variations has become a major concern. This paper proposes a new gate delay model that includes impact from both process variations and multiple input switching. The proposed model uses orthogonal polynomial based probabilistic collocation method to construct a delay analytical equation from circuit timing performance. From the experimental results, our approach has less that 0.2% error on the mean delay of gates and less than 3% error on the standard deviation.
OS Debugging Method Using a Lightweight Virtual Machine Monitor
Venue: arXiv cs.OS 2007
Year: 2007

Demands for implementing original OSs that can achieve high I/O performance on PC/AT compatible hardware have recently been increasing, but conventional OS debugging environments have not been able to simultaneously assure their stability, be easily customized to new OSs and new I/O devices, and assure efficient execution of I/O operations. We therefore developed a novel OS debugging method using a lightweight virtual machine. We evaluated this debugging method experimentally and confirmed that it can transfer data about 5.4 times as fast as the conventional virtual machine monitor.
Why Systems-on-Chip Needs More UML like a Hole in the Head
Venue: arXiv cs.AR 2007
Year: 2007

Let's be clear from the outset: SoC can most certainly make use of UML; SoC just doesn't need more UML, or even all of it. The advent of model mappings, coupled with marks that indicate which mapping rule to apply, enable a major simplification of the use of UML in SoC.
Modeling the Non-Linear Behavior of Library Cells for an Accurate Static Noise Analysis
Venue: arXiv cs.AR 2007
Year: 2007

In signal integrity analysis, the joint effect of propagated noise through library cells, and of the noise injected on a quiet net by neighboring switching nets through coupling capacitances, must be considered in order to accurately estimate the overall noise impact on design functionality and performances. In this work the impact of the cell non-linearity on the noise glitch waveform is analyzed in detail, and a new macromodel that allows to accurately and efficiently modeling the non-linear effects of the victim driver in noise analysis is presented. Experimental results demonstrate the effectiveness of our method, and confirm that existing noise analysis approaches based on linear superposition of the propagated and crosstalk-injected noise can be highly inaccurate, thus impairing the sign-off functional verification phase.
FORAY-GEN: Automatic Generation of Affine Functions for Memory Optimizations
Venue: arXiv cs.PL 2007
Year: 2007

In today's embedded applications a significant portion of energy is spent in the memory subsystem. Several approaches have been proposed to minimize this energy, including the use of scratch pad memories, with many based on static analysis of a program. However, often it is not possible to perform static analysis and optimization of a program's memory access behavior unless the program is specifically written for this purpose. In this paper we introduce the FORAY model of a program that permits aggressive analysis of the application's memory behavior that further enables such optimizations since it consists of 'for' loops and array accesses which are easily analyzable. We present FORAY-GEN: an automated profile-based approach for extraction of the FORAY model from the original program. We also demonstrate how FORAY-GEN enhances applicability of other memory subsystem optimization approaches, resulting in an average of two times increase in the number of memory references that can be analyzed by existing static approaches.
Modeling and Propagation of Noisy Waveforms in Static Timing Analysis
Venue: arXiv cs.OH 2007
Year: 2007

A technique based on the sensitivity of the output to input waveform is presented for accurate propagation of delay information through a gate for the purpose of static timing analysis (STA) in the presence of noise. Conventional STA tools represent a waveform by its arrival time and slope. However, this is not an accurate way of modeling the waveform for the purpose of noise analysis. The key contribution of our work is the development of a method that allows efficient propagation of equivalent waveforms throughout the circuit. Experimental results demonstrate higher accuracy of the proposed sensitivity-based gate delay propagation technique, SGDP, compared to the best of existing approaches. SGDP is compatible with the current level of gate characterization in conventional ASIC cell libraries, and as a result, it can be easily incorporated into commercial STA tools to improve their accuracy.
Stochastic Power Grid Analysis Considering Process Variations
Venue: arXiv cs.AR 2007
Year: 2007

In this paper, we investigate the impact of interconnect and device process variations on voltage fluctuations in power grids. We consider random variations in the power grid's electrical parameters as spatial stochastic processes and propose a new and efficient method to compute the stochastic voltage response of the power grid. Our approach provides an explicit analytical representation of the stochastic voltage response using orthogonal polynomials in a Hilbert space. The approach has been implemented in a prototype software called OPERA (Orthogonal Polynomial Expansions for Response Analysis). Use of OPERA on industrial power grids demonstrated speed-ups of up to two orders of magnitude. The results also show a significant variation of about $\pm$ 35% in the nominal voltage drops at various nodes of the power grids and demonstrate the need for variation-aware power grid analysis.
Statistical Modeling of Pipeline Delay and Design of Pipeline under Process Variation to Enhance Yield in sub-100nm Technologies
Venue: arXiv cs.AR 2007
Year: 2007

Operating frequency of a pipelined circuit is determined by the delay of the slowest pipeline stage. However, under statistical delay variation in sub-100nm technology regime, the slowest stage is not readily identifiable and the estimation of the pipeline yield with respect to a target delay is a challenging problem. We have proposed analytical models to estimate yield for a pipelined design based on delay distributions of individual pipe stages. Using the proposed models, we have shown that change in logic depth and imbalance between the stage delays can improve the yield of a pipeline. A statistical methodology has been developed to optimally design a pipeline circuit for enhancing yield. Optimization results show that, proper imbalance among the stage delays in a pipeline improves design yield by 9% for the same area and performance (and area reduction by about 8.4% under a yield constraint) over a balanced design.
An Application-Specific Design Methodology for STbus Crossbar Generation
Venue: arXiv cs.AR 2007
Year: 2007

As the communication requirements of current and future Multiprocessor Systems on Chips (MPSoCs) continue to increase, scalable communication architectures are needed to support the heavy communication demands of the system. This is reflected in the recent trend that many of the standard bus products such as STbus, have now introduced the capability of designing a crossbar with multiple buses operating in parallel. The crossbar configuration should be designed to closely match the application traffic characteristics and performance requirements. In this work we address this issue of application-specific design of optimal crossbar (using STbus crossbar architecture), satisfying the performance requirements of the application and optimal binding of cores onto the crossbar resources. We present a simulation based design approach that is based on analysis of actual traffic trace of the application, considering local variations in traffic rates, temporal overlap among traffic streams and criticality of traffic streams. Our methodology is applied to several MPSoC designs and the resulting crossbar platforms are validated for performance by cycle-accurate SystemC simulation of the designs. The experimental case studies show large reduction in packet latencies (up to 7x) and large crossbar component savings (up to 3.5x) compared to traditional design approaches.
DVS for On-Chip Bus Designs Based on Timing Error Correction
Venue: arXiv cs.AR 2007
Year: 2007

On-chip buses are typically designed to meet performance constraints at worst-case conditions, including process corner, temperature, IR-drop, and neighboring net switching pattern. This can result in significant performance slack at more typical operating conditions. In this paper, we propose a dynamic voltage scaling (DVS) technique for buses, based on a double sampling latch which can detect and correct for delay errors without the need for retransmission. The proposed approach recovers the available slack at non-worst-case operating points through more aggressive voltage scaling and tracks changing conditions by monitoring the error recovery rate. Voltage margins needed in traditional designs to accommodate worst-case performance conditions are therefore eliminated, resulting in a significant improvement in energy efficiency. The approach was implemented for a 6mm memory read bus operating at 1.5GHz (0.13 $μ$m technology node) and was simulated for a number of benchmark programs. Even at the worst-case process and environment conditions, energy gains of up to 17% are achieved, with error recovery rates under 2.3%. At more typical process and environment conditions, energy gains range from 35% to 45%, with a performance degradation under 2%. An analysis of optimum interconnect architectures for maximizing energy gains with this approach shows that the proposed approach performs well with technology scaling.
Applying UML and MDA to Real Systems Design
Venue: arXiv cs.SE 2007
Year: 2007

Traditionally system design has been made from a black box/functionality only perspective which forces the developer to concentrate on how the functionality can be decomposed and recomposed into so called components. While this technique is well established and well known it does suffer fromsome drawbacks; namely that the systems produced can often be forced into certain, incompatible architectures, difficult to maintain or reuse and the code itself difficult to debug. Now that ideas such as the OMG's Model Based Architecture (MDA) or Model Based Engineering (MBE) and the ubiquitous modelling language UML are being used (allegedly) and desired we face a number of challenges to existing techniques.
The Challenges of Hardware Synthesis from C-Like Languages
Venue: arXiv cs.PL 2007
Year: 2007

MANY TECHNIQUES for synthesizing digital hardware from C-like languages have been proposed, but none have emerged as successful as Verilog or VHDL for register-transfer-level design. This paper looks at two of the fundamental challenges: concurrency and timing control.
Functional Equivalence Checking for Verification of Algebraic Transformations on Array-Intensive Source Code
Venue: arXiv cs.LO 2007
Year: 2007

Development of energy and performance-efficient embedded software is increasingly relying on application of complex transformations on the critical parts of the source code. Designers applying such nontrivial source code transformations are often faced with the problem of ensuring functional equivalence of the original and transformed programs. Currently they have to rely on incomplete and time-consuming simulation. Formal automatic verification of the transformed program against the original is instead desirable. This calls for equivalence checking tools similar to the ones available for comparing digital circuits. We present such a tool to compare array-intensive programs related through a combination of important global transformations like expression propagations, loop and algebraic transformations. When the transformed program fails to pass the equivalence check, the tool provides specific feedback on the possible locations of errors.
Exact Synthesis of 3-Qubit Quantum Circuits from Non-Binary Quantum Gates Using Multiple-Valued Logic and Group Theory
Venue: arXiv cs.LO 2007
Year: 2007

We propose an approach to optimally synthesize quantum circuits from non-permutative quantum gates such as Controlled-Square-Root-of-Not (i.e. Controlled-V). Our approach reduces the synthesis problem to multiple-valued optimization and uses group theory. We devise a novel technique that transforms the quantum logic synthesis problem from a multi-valued constrained optimization problem to a group permutation problem. The transformation enables us to utilize group theory to exploit the properties of the synthesis problem. Assuming a cost of one for each two-qubit gate, we found all reversible circuits with quantum costs of 4, 5, 6, etc, and give another algorithm to realize these reversible circuits with quantum gates.
SAT-Based Complete Don't-Care Computation for Network Optimization
Venue: arXiv cs.LO 2007
Year: 2007

This paper describes an improved approach to Boolean network optimization using internal don't-cares. The improvements concern the type of don't-cares computed, their scope, and the computation method. Instead of the traditionally used compatible observability don't-cares (CODCs), we introduce and justify the use of complete don't-cares (CDC). To ensure the robustness of the don't-care computation for very large industrial networks, a optional windowing scheme is implemented that computes substantial subsets of the CDCs in reasonable time. Finally, we give a SAT-based don't-care computation algorithm that is more efficient than BDD-based algorithms. Experimental results confirm that these improvements work well in practice. Complete don't-cares allow for a reduction in the number of literals compared to the CODCs. Windowing guarantees robustness, even for very large benchmarks on which previous methods could not be applied. SAT reduces the runtime and enhances robustness, making don't-cares affordable for a variety of other Boolean methods applied to the network.
A Way Memoization Technique for Reducing Power Consumption of Caches in Application Specific Integrated Processors
Venue: arXiv cs.AR 2007
Year: 2007

This paper presents a technique for eliminating redundant cache-tag and cache-way accesses to reduce power consumption. The basic idea is to keep a small number of Most Recently Used (MRU) addresses in a Memory Address Buffer (MAB) and to omit redundant tag and way accesses when there is a MAB-hit. Since the approach keeps only tag and set-index values in the MAB, the energy and area overheads are relatively small even for a MAB with a large number of entries. Furthermore, the approach does not sacrifice the performance. In other words, neither the cycle time nor the number of executed cycles increases. The proposed technique has been applied to Fujitsu VLIW processor (FR-V) and its power saving has been estimated using NanoSim. Experiments for 32kB 2-way set associative caches show the power consumption of I-cache and D-cache can be reduced by 40% and 50%, respectively.