15935373
Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs
Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set of pairs of matchings must each produce Hamilton cycles (with suitable restrictions on the prescribed set of pairs). We also show how the result with four matchings implies that a random d-regular graph for fixed even d?4 asymptotically almost surely decomposes into d/2 Hamilton cycles. This completes a general result on the edge-decomposition of a random regular graph into regular spanning subgraphs of given degrees together with Hamilton cycles and verifies conjectures of Janson and of Robinson and Wormald.
14012710
Interference-Minimizing Colorings of Regular Graphs
Communications problems that involve frequency interference, such as the channel assignment problem in the design of cellular telephone networks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too similar. The paper considers situations modeled by vertex-coloring d-regular graphs with n vertices using a color set 1, 2,..., n, where colors i and j are said to interfere if their circular distance $\min \{ | i-j | , n- | i-j | \}$ does not exceed a given threshold value $\alpha$. Given a d-regular graph G and threshold $\alpha$, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfere. Let $I_\alpha (G)$ denote the minimum number of interfering edges in such a coloring of $G$. For most triples $(n, \alpha ,d),$ we determine the minimum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain it. In determining when this minimum value is 0, we prove that for $r \geq 3$ there exists a d-regular graph G on n vertices that is r-colorable whenever $d \leq (1- \frac{1}{r}) n-1$ and nd is even. We also study the maximum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain this maximum in many cases.
2320085
Generating random regular graphs
Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d=O(n1/3-ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd2). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author.Besides being perhaps the only algorithm which works for relatively large d in practical time, our result also has a significant theoretical value, as it can be used to derive many properties of uniform random regular graphs.
12050804
On the asymmetry of random regular graphs and random graphs
This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 ≤ d ≤ n - 4 the random d-regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13].
6225887
Hamiltonian decompositions of random bipartite regular graphs
We prove a complete hamiltonian decomposition theorem for random bipartite regular graphs, thereby verifying a conjecture of Robinson and Wormald. The main step is to prove contiguity (a kind of asymptotic equivalence) of two probabilistic models of 4-regular bipartite graphs; namely, the uniform model, and the model obtained by taking the union of two independent, uniformly chosen bipartite Hamilton cycles, conditioned on forming no multiple edges. The proof uses the small subgraph conditioning method to establish contiguity, while the differential equation method is used to analyse a critical quantity.
10769698
Regular subgraphs of random graphs
In this paper, we prove that there exists a function ρk = (4 + o(1))k such that G(n, ρ/n) contains a k-regular graph with high probability whenever ρ > ρk. In the case of k = 3, it is also shown that G(n, ρ/n) contains a 3-regular graph with high probability whenever ρ > λ ≈ 5.1494. These are the first constant bounds on the average degree in G(n, p) for the existence of a k-regular subgraph. We also discuss the appearance of 3-regular subgraphs in cores of random graphs.
1972714
Fast color image processing using quantized color instruction set
The paper describes the Quantized Color Pack eXtension (QCPX) instruction set that can accelerate color-image processing applications. QCPX employs heterogeneous-subword-parallel instructions, which utilize the microprocessor's 16-bit wide datapaths to process a packed, quantized 16-bit color data type in YCbCr (Y: luminance, Cr and Cb: chrominance) format in parallel. Unlike typical multimedia instruction set extensions (e.g. MMX, SSE, ALTIVEC), QCPX obtains performance and code density improvements through implicit support for color pixel processing rather than depending solely upon generic subword parallelism. Five time-critical color image processing algorithms are coded with and without QCPX to fully measure its impact upon programming techniques. Simulation results indicate that the applications using QCPX achieve significant speedups in execution time over non-QCPX. In addition, QCPX results in higher system utilization (in excess of 94% in all cases) due to significant reduction of conditional instructions.
1710897
A low latency router supporting adaptivity for on-chip interconnects
The increased deployment of system-on-chip designs has drawn attention to the limitations of on-chip interconnects. As a potential solution to these limitations, networks-on-chip (NoC) have been proposed. The NoC routing algorithm significantly influences the performance and energy consumption of the chip. We propose a router architecture which utilizes adaptive routing while maintaining low latency. The two-stage pipelined architecture uses look ahead routing, speculative allocation, and optimal output path selection concurrently. The routing algorithm benefits from congestion-aware flow control, making better routing decisions. We simulate and evaluate the proposed architecture in terms of network latency and energy consumption. Our results indicate that the architecture is effective in balancing the performance and energy of NoC designs.
686623
Self-biased, high-bandwidth, low-jitter 1-to-4096 multiplier clock-generator PLL
A self-biased PLL uses a sampled feed-forward filter network and a multi-stage inverse-linear programmable current mirror for constant loop dynamics that scale with reference frequency and are independent of multiplication factor, output frequency, and PVT. The PLL achieves a multiplication range of 1 to 4096 with < 3.8% period jitter at 1.5V supply. Fabricated in 0.13/spl mu/m CMOS, the area is 0.182mm/sup 2/ and the supply is 1.5V.
16103417
Designs in Additive Codes over GF(4)
The purpose of this paper is to study designs in additive codes over GF(4). There are two types of designs. One is a classical t-design with repeated blocks. In this case we have an analog of the Assmus–Mattson Theorem for additive codes over GF(4). The other is a generalized t-design first introduced by Delsarte [4]. As an example, we consider the dodecacode, which is the unique additive even self-dual (12, 212, 6) code. We show that there exists a 5-(12, 6, 3) design in the dodecacode with either 3 distinct blocks or 3 repeated blocks covering a 5-set. We also find a new simple 3-(11, 5, 4) design in the shortened dodecacode by a computer search. Additionally we show that any extremal additive even self-dual code over GF(4) is homogeneous.
10217893
Adaptive Compiler Directed Prefetching for EPIC Processors
The widely acknowledged performance gap between processors and memory has been the subject of much research. In the Explicitly Parallel Instruction Computing (EPIC) paradigm, the combination of in-order issue and the presence of a large number of parallel functional units exacerbate the problem. Prefetching, by hardware, software, or a combination of both, is one of the primary mechanisms advocated to alleviate this problem. In this paper, we propose a new software-based data prefetching mechanism that is the Adaptive Markovian Predictor ( AMP). AMP is suitable for implementation in EPIC processors without significant hardware overhead. Specifically, we introduce a predicated prefetch operation which leverages the concept of an informing load to dynamically adapt to runtime memory behaviors. Furthermore, we employ predicated prefetching in a new optimization framework that also consists of data remapping and off-line learning of Markovian predictors. This distinguishes our approach from early software prefetching techniques that only involve static program analysis. Our experiments show that the proposed framework can effectively remove 10%-30% of the stall cycles due to cache misses for benchmarks from the well-known SPEC and OLDEN suites. The results also show that the framework performs better than pure stride predictors and has lower bandwidth and instruction overheads.