9811102
Four-bend top-down global routing
We propose a new global net distribution approach for high-performance m/spl times/m two-dimensional arrays of very large scale integration and multichip-modules. The objective is to route n nets with minimum density of global cells, using a "small" number of bends. There are a number of applications where it is necessary to limit the number of bends on each wire. For example, it is desirable to limit the number of bends on each microstrip (transmission) line, for mismatches of line impedance can cause reflections from the junction points such as bends and vias. Furthermore, for high-performance routing, intersections of wires cause the use of more vias, which in turn require the use of more routing resources (because of the larger via pitch). This is the first paper that addresses a graph-theoretic framework to solve the bend-constrained global routing problem in two-dimensional arrays. In this paper, at each level of an underlying quad-tree, we present a novel four-bend routing algorithm by decomposing the original problem at level i into two subproblems that can be solved exactly based on a two-stage approach of smaller-sized linear program followed by min-cost flow networks. The overall (i.e., entire level of the four-way partition hierarchy) constraint and variable size for the first stage is O(md/sub o/), while the overall run time for the second stage is O(n/sup 3/ log n/sup 2/). The time complexity of such a hierarchical approach is one order of magnitude less than one of constructing a global routing using the min-cost-flow-based flat design approach. Last, we present an extension that permits a limited degree of control over the number of bends. The proposed algorithm can also be used for estimating the wireability in the early design planning stage for high-level synthesis. Experimental results showed the effectiveness of the proposed algorithm.
16182863
Wiring space and length estimation in two-dimensional arrays
We propose a new global routing area estimation approach for high-performance very large scale integration and multichip modules (MCMs). The objective is to route nets with minimum density of global cells, producing a four-bend routing for each two-terminal net. We propose an approximate upper bound on global cell d/sub H//spl les/2d/sub 0/log(m/(2d/sub 0/)), in an m/spl times/m two-dimensional array, where d/sub 0/ is the estimated lower-bound density. The total wirelength is (2/spl alpha/+/spl beta/)4m/sup 2/d/sub 0//3, where /spl alpha/+/spl beta/=1 and /spl alpha/ is the percentage of diagonal combinations and /spl beta/ is the percentage of adjacent combinations of nets. If /spl alpha//spl les//spl beta/ (this assumption holds since a good placement minimizes the longer wires), then the total wirelength is at most 2m/sup 2/d/sub 0/. By counting on the adjacent and diagonal combinations separately in the cost function, d/sub R//spl les/[4d/sub 0//3]/spl times/log([m/(4d/sub 0//3)]). We verified that the bound obtained are realistic in the worst case. A solution to this problem can be used for quick estimation of necessary wiring space (for standard cell array designs) and difficulty of routing (for gate array designs) in the early design planning stage.
30331490
Robust Watermarking on Polygonal Meshes Using Distribution of Vertex Norms
Most watermarking techniques for 3-D mesh models have mainly focused on robustness against various attacks, such as adding noise, smoothing, simplification, re-meshing, clipping, and so on. These attacks perceptually damage the stego model itself. Unlike watermarking of other multimedia data, serious attacks for 3-D meshes includes similarity transform and vertex re-ordering. They can fatally destroy the watermark without any perceptual degradation of the stego model. In this paper, we propose a new watermarking technique for 3-D polygonal mesh model, which modifies the distribution of vertex norms according to watermark bit to be embedded. In particular, the proposed employs blind watermark detection technique, which extracts the watermark without referring to cover meshes. The simulation results show that the proposed is remarkably robust against similarity transform and vertex re-ordering.
361499
Energy Efficient Broadcast in Wireless Ad hoc Networks with Hitch-hiking
In this paper, we propose a novel concept called Hitch-hiking in order to reduce the energy consumption of broadcast application for wireless networks. Hitch-hiking takes advantage of the physical layer design that facilitates the combining of partial signals to obtain the complete information. The concept of combining partial signals using maximal ratio combiner [15] has been used to improve the reliability of the communication link but has never been exploited to reduce energy consumption in broadcasting over wireless ad hoc networks. We study the advantage of Hitch-hiking for the scenario when the transmission power level of nodes is fixed as well as the scenario when the nodes can adjust their power level. For both scenarios, we show that Hitch-hiking is advantageous and have proposed algorithms to construct broadcast tree with Hitch-hiking taken into consideration. For fixed transmission power case, we propose and analyze a centralized heuristic algorithm called SPWMH (Single Power Wireless Multicast with Hitch-hiking) to construct a broadcast tree with minimum forwarding nodes. For the latter case, we propose a centralized heuristic algorithm called Wireless Multicast with Hitch-hiking (WMH) to construct an energy efficient tree using Hitch-hiking and also present a distributed version of the heuristic. We also evaluate the proposed heuristics through simulation. Simulation results show that Hitch-hiking can reduce the transmission cost of broadcast by as much as 50%. Further, we propose and evaluate a protocol called Power Saving with Broadcast Tree (PSBT) that reduces energy consumption of broadcast by eliminating redundancy in receive operation. Finally, we propose an algorithm that takes advantage of both Hitch-hiking and PSBT in conserving energy.
122713
Joint transmitter and receiver optimization in additive cyclostationary noise
A joint optimization of transmitter and receiver is considered for strictly band-limited linear modulations in additive cyclostationary noise. Under the assumptions that the period of the cyclostationarity of the noise is the same as the inverse of the symbol transmission rate and that the noise has a positive-definite autocorrelation function, the optimum transmitter and receiver waveforms that jointly minimize the mean-squared error at the output of the linear receiver are derived with the data sequence modeled as a wide-sense stationary (WSS) colored random process and the channel modeled as a linear time-invariant system with a general frequency-selective impulse response. Numerical results show that this joint optimization technique leads to a significant performance improvement over the systems with receiver-only optimization and the systems with no transmitter and receiver optimizations.
43684392
Wavelet Analysis Based Blind Watermarking for 3-D Surface Meshes
As most previous wavelet analysis based 3-D mesh watermarking methods embed the watermark information into wavelet coefficients arranged in a certain order, they have not been used as blind schemes since the connectivity information must be exactly known in the watermark extraction process. In this paper, we propose a blind watermarking method based on wavelet analysis for 3-D mesh model. Two new techniques are introduced. One is to exploit the statistical features of scale coefficients on an approximation (low resolution) level for watermark embedding. Another is to extract the hidden watermark, not from the same resolution level as used in embedding process, but directly from the spatial domain. As the proposed watermark detection does not require the wavelet analysis, any pre-processing such as registration and re-sampling, is not needed. These techniques allow to detect the watermark without referring to the original meshes. In addition, the proposed are applicable directly to irregular meshes by using irregular wavelet analysis. Through simulations, we prove that our method is fairly robust against various attacks including topological ones.
5732912
Crawler-Friendly Web Servers
In this paper we study how to make web servers (e.g., Apache) more crawler friendly. Current web servers offer the same interface to crawlers and regular web surfers, even though crawlers and surfers have very different performance requirements. We evaluate simple and easy-to-incorporate modifications to web servers so that there are significant bandwidth savings. Specifically, we propose that web servers export meta-data archives decribing their content.