53245552
Simultaneous shield insertion and net ordering for capacitive and inductive coupling minimization
In this article, we first show that existing net ordering formulations to minimize noise are no longer sufficient with the presence of inductive noise, and shield insertion is needed to minimize inductive noise. Using a Keff model as the figure of merit for inductive coupling, we then formulate two simultaneous shield insertion and net ordering (SINO) problems: the optimal SINO/NF problem to find a minimal area SINO solution that is free of capacitive and inductive noise, and the optimal SINO/NB problem to find a minimal area SINO solution that is free of capacitive noise and is under the given inductive noise bound. We reveal that both optimal SINO problems are NP-hard, and propose effective approximate algorithms for the two problems. Experiments show that our SINO/NB algorithm uses from 51p to 82p fewer shields compared to uniform shield insertion and net ordering (US + NO), and uses from 4p to 47p fewer shields compared to separated net ordering and shield insertion (NO + SI). Furthermore, the SINO/NB solutions under practical noise bounds use from 38p to 61p fewer shields compared to SINO/NF solutions, and use up to 36p fewer shields compared to the theoretical lower bound for optimal SINO/NF solutions. Moreover, we show that the Keff model has a high fidelity versus the noise voltage computed using accurate RLC circuit models and SPICE simulations. To the best of our knowledge, it is the first work that presents an in-depth study on the automatic layout optimization of multiple nets to minimize both capacitive and inductive noise.
441080
An efficient model for frequency-dependent on-chip inductance
this paper, we propose an ecient table-based model for frequency-dependent on-chip inductance, and apply it to com- pute mutual inductance between random wires and loop induc- tance for cascade wires, respectively. Our inductance computa- tion achieves around 5% error when compared to the numerical solution, and matches frequency-dependent impact very well. We also apply the inductance model to generate RLC circuit models for on-chip interconnects, and present a complexity- ecient normalized RLC circuit model for multiple parallel wires. These results are extremely ecient, and can be eectively used during iterative design procedure. Further, the table-based in- ductance model has been implemented as a Web-based tool to generate inductance matrix for given random wires.
1971121
A "flight data recorder" for enabling full-system multiprocessor deterministic replay
Debuggers have been proven indispensable in improving software reliability. Unfortunately, on most real-life software, debuggers fail to deliver their most essential feature --- a faithful replay of the execution. The reason is non-determinism caused by multithreading and non-repeatable inputs. A common solution to faithful replay has been to record the non-deterministic execution. Existing recorders, however, either work only for datarace-free programs or have prohibitive overhead.As a step towards powerful debugging, we develop a practical low-overhead hardware recorder for cachecoherent multiprocessors, called Flight Data Recorder (FDR). Like an aircraft flight data recorder, FDR continuously records the execution, even on deployed systems, logging the execution for post-mortem analysis.FDR is practical because it piggybacks on the cache coherence hardware and logs nearly the minimal threadordering information necessary to faithfully replay the multiprocessor execution. Our studies, based on simulating a four-processor server with commercial workloads, show that when allocated less than 7% of system's physical memory, our FDR design can capture the last one second of the execution at modest (less than 2%) slowdown.
1185541
A serializability violation detector for shared-memory server programs
We aim to improve reliability of multithreaded programs by proposing a dynamic detector that detects potentially erroneous program executions and their causes. We design and evaluate a Serializability Violation Detector (SVD) that has two unique goals: (I) triggering automatic recovery from erroneous executions using backward error recovery (BER), or simply alerting users that a software error may have occurred; and (II) helping debug programs by revealing causes of error symptoms.Two properties of SVD help in achieving these goals. First, to detect only erroneous executions, SVD checks serializability of atomic regions, which are code regions that need to be executed atomically. Second, to improve usability, SVD does not require a priori annotations of atomic regions; instead, SVD approximates them using a heuristic. Experimental results on three widely-used multithreaded server programs show that SVD finds real bugs and reports modest false positives. The goal of this paper is to develop a detector suitable for (I) BER-based avoidance of erroneous program executions; and (II) alerting users as software errors occur. We argue that such a detector should have the following two properties.
11401451
A regulated transitive reduction (RTR) for longer memory race recording
Now at VMware. Multithreaded deterministic replay has important applications in cyclic debugging, fault tolerance and intrusion analysis. Memory race recording is a key technology for multithreaded deterministic replay. In this paper, we considerably improve our previous always-on Flight Data Recorder (FDR) in four ways: •Longer recording by reducing the log size growth rate to approximately one byte per thousand dynamic instructions. •Lower hardware cost by reducing the cost to 24 KB per processor core. •Simpler design by modifying only the cache coherence protocol, but not the cache. •Broader applicability by supporting both Sequential Consistency (SC) and Total Store Order (TSO) memory consistency models (existing recorders support only SC).These improvements stem from several ideas: (1) a Regulated Transitive Reduction (RTR) recording algorithm that creates stricter and vectorizable dependencies to reduce the log growth rate; (2) a Set/LRU timestamp approximation method that better approximates timestamps of uncached memory locations to reduce the hardware cost; (3) an order-value-hybrid recording methodthat explicitly logs the value of potential SC-violating load instructions to support multiprocessor systems with TSO.
13407089
Event detection and period extraction using multi-scale symmetry and entropy
We present a system for detecting discrete periodic events over a short interval and in the presence of interference. In the first stage symmetries are identified using scale-space representation. This process detects signal events with a low signal-to-noise ratio but has the potential to introduce a number of false responses. This process is followed by an entropy-based algorithm that can robustly extract periodicities from a set of observed discrete events in the presence of a large number of false alarms. The event detection and period extraction processes have a low computational cost and can extract signal periodicity after a short observation time. This scheme was evaluated against four previously reported methods. Results demonstrate that the period extraction algorithm presented here is more reliable than three of the previously reported algorithms. The reliability of the algorithm presented here was similar to that of the fourth method but the computational cost was much less.
15417765
The proof of a conjecture of Bouabdallah and Sotteau
Let G be a connected graph of order n. A routing in G is a set of n(n 1) fixed paths for all ordered pairs of vertices of G. The edge-forwarding index of G, (G), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G, and ,n is the minimum of (G) taken over all graphs of order n with maximum degree at most . To determine n 2p 1,n for 4p 2p/3 1 ≤ n ≤ 6p, A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249–255]. The set 3 {1, 2, . . . , (4p)/3} can be partitioned into 2p pairs plus singletons such that the set of differences of the pairs is the set 2 {1, 2, . . . , p}. This article gives a proof of this conjecture and determines that n 2p 1,n is equal to 5 if 4p 2p/3 1 ≤ n ≤ 6p and to 8 if 3p p/3 1 ≤ n ≤ 3p (3p)/5 for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004
39351233
Note on Infinite Families of Trivalent Semisymmetric Graphs
A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. This paper uses the groups PSL (2, p) and PGL (2, p), where p is a prime, to construct two new infinite families of trivalent semisymmetric graphs.
10480954
Isomorphisms of Finite Cayley Digraphs of Bounded Valency
LetGbe a finite group,Sa subset ofG\{1}, and let Cay(G,S) denote the Cayley digraph ofGwith respect toS. If, for all subsetsS,TofG\{1} of size at mostm, Cay(G,S)?Cay(G,T) implies thatS?=Tfor some??Aut(G), thenGis called anm-DCI-group. In this paper, we prove that, form?2, allm-DCI-groups are of the formU×V, where (|U|, |V|)=1,Uis abelian andVbelongs to an explicitly determined list of groups. Moreover Sylow subgroups of such groups satisfy some very restrictive conditions.
19879470
The multiscale medial properties of interfering image structures
The multiscale medial axis (MMA) is a robust shape representation in analysing objects in greylevel images. It is computed as ridges in the medialness scale-space of an image. In this paper the multiscale medial properties of overlapping objects are investigated, the result of which is novel to the community in that the existing studies only concentrated on isolated objects. To improve the distinguishability of these objects, a sliding window algorithm is proposed to detect locally optimal scale ridges in scale space. When used in the medialness scale-space of an image, this efficient method can extract a complete set of MMAs for interfering objects, in contrast with the globally optimal scale ridge definition which has been widely used. This is demonstrated in the applications in medical images.