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.
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.
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.
40944529
Symmetric Graphs of Order a Product of Two Distinct Primes
A simple undirected graph ? is said to be symmetric if its automorphism group Aut ? is transitive on the set of ordered pairs of adjacent vertices of ?, and ? is said to be imprimitive if Aut ? acts imprimitively on the vertices of ?. Let k and p be distinct primes with k < p. This paper gives a classification of all imprimitive symmetric graphs on kp vertices for k ? 5. The cases k < 5 have been treated previously by Cheng and Oxley (k = 2) and the second and third authors (k = 3), and the classification of primitive symmetric graphs on kp vertices with k ? 5 was done by the first and third authors.
43124802
On the Isomorphisms of Cayley Graphs of Abelian Groups
Let G be a finite group, S a subset of G\{1}, and let Cay (G, S) denote the Cayley digraph of G with respect to S. If, for any subset T of G\{1}, Cay(G, S) ≅ Cay(G, T) implies that Sα = T for some α ∈ Aut(G), then S is called a CI-subset. The group G is called a CIM-group if for any minimal generating subset S of G, S ∪ S-1 is a CI-subset. In this paper, CIM-abelian groups are characterized.
206570343
Vertex-Primitive Graphs of Order a Product of Two Distinct Primes
Abstract Let k and p be odd primes with k p . All vertex-primitive graphs of order kp are classified, and those which are symmetric, or are edge-transitive but not symmetric. or are not Cayley graphs are identified. In addition, a classification is given of all vertex-primitive, edge-transitive lantisymmetric) directed graphs or order kp . The classification of the vertex-primitive symmetric graphs of order kp is used by the authors and others to complete the classification of symmetric graphs or order kp . The classification of the vertex-primitive non-Cayley graphs of order kp is used by B.D. McKay and the first author in an investigation of vertex-transitive non-Cayley graphs.
7849638
Edge-fault-tolerant edge-bipancyclicity of hypercubes
In this paper, we consider the problem embedding a cycle into the hypercube Q"n with existence of faulty edges and show that for any edge subset F of Q"n with |F|==4 and all edges in F are not incident with the same vertex. This result improves some known results.
1797921
Arc-transitive circulant digraphs of odd prime-power order
In this paper, the full automorphism group of a circulant digraph of prime-power order is investigated, and as a result, a complete classification of arc-transitive circulant graphs of odd prime-power order is given.