616417
Synthesis of low power CED circuits based on parity codes
An automated design procedure is described for synthesizing circuits with low power concurrent error detection. It is based on pre-synthesis selection of a parity-check code followed by structure constrained logic optimization that produces a circuit in which all single point faults are guaranteed to be detected. Two new contributions over previous work include (1) the use of a k-way partitioning algorithm combined with local search to select a parity-check code, and (2) a methodology for minimizing power consumption in the CED circuitry. Results indicate significant reductions in area overhead due to the new code selection procedure as well as the ability to find low power implementations for use in power conscious applications.
11538916
Reducing power consumption in memory ECC checkers
A method is proposed for reducing power consumption in memory ECC checker circuitry that provides SEC-DED. The degrees of freedom in selecting the parity check matrix are used to minimize power with little or no impact on area and delay. The power minimization method is applied to two popular SEC-DED codes: standard Hamming codes and odd-column-weight Hsiao codes. Experiments on actual memory traces of Spec and MediaBench benchmarks indicate that considering power in addition to area and delay when selecting the parity check matrix can result in power reductions of up to 27% for Hsiao codes and up to 41% for Hamming codes.
748684
Detection probabilities of interconnect breaks: an analysis
An interconnect break is a break that occurs in the interconnect wiring, resulting in logic gate inputs being disconnected from the drivers and causing the wire to float. Interconnect breaks are the most common types of breaks in modern CMOS integrated circuits, so testing and detecting these breaks has become very important. This paper proposes a model by which standard tests for stuck-at-faults can be used to detect interconnect breaks in a circuit. This paper presents a worst-case analysis of the detection of these breaks and calculate the minimum number of test vectors required to detect breaks with a specified confidence level, using n-detection principles. To enhance the understanding of the breaks in the circuit, we present a statistical model based on the length distribution of the wires surrounding the floating wire where the break occurs. From the model we compute the detection probabilities of such breaks and show that the worst case of detection is when the bias voltage is the same as the logic threshold voltage.
5608135
Low-power weighted pseudo-random BIST using special scan cells
In this paper, a technique for weighted pseudo-random built-in self-test (BIST) of VLSI circuits is proposed, which uses special scan cells and a new weight selection algorithm to achieve low power dissipation. It is based on weighted pseudo-random scan testing in which only 3 weight values are used - 2 fixed values (0 or 1) and 1 random value (0.5). A new weight selection algorithm is used to select a set of weights that achieves high fault coverage while reducing power. The idea is to minimize power by careful selection of the set of scan cells having fixed values (0 or 1) in order to reduce switching activity. To implement this in hardware, a new scan cell design is proposed that can do scan and capture in the normal mode as well as fixed-bit mode. The new scan cell hardware increases the area of a typical circuit by less than 4%, but reduces power by as much as 96%, as indicated in experiments performed on benchmark circuits.
25755124
An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon

AbstractAbstract. In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature(i.e., constrained to have curvature at most 1), moving in the plane inside an n -sided simple polygon P . Given two points sand tinside Pand two directions of travel, one at sand one at t , the problem is to compute a convex and simple path of bounded curvature inside Pfrom sto tconsisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at sis tangent to the path at sand (iv) the given final direction at tis tangent to the path at t . We propose an O(n4)time algorithm for this problem. Using the notion of complete visibility, Pis pruned to another polygon P'such that any convex and simple path from sto tinside Palso remains inside P' . Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of P'and, using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in O(n)time to a minimalconvex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a minimalbounded curvature path is located in O(n4)time whose length, except in special situations involving arcs of length greater than π , is at most twice the length of a shortest convex and simple path of bounded curvature.

33976120
Concurrent Reading and Writing with Mobile Agents
This paper presents a method using which a set of reading and writing agents concurrently read and update the global state of the network. In addition to the consistency of the snapshot and the reset states, our protocol preserves the atomicity of the reads and writes, despite the fact these operations are non-blocking. Potential applications include the design of multi-agent protocols for self-stabilization, self-healing and adaptation.
9120365
A self-stabilizing algorithm for the maximum flow problem
Summary. The maximum flow problem is a fundamental problem in graph theory and combinatorial optimization with a variety of important applications. Known distributed algorithms for this problem do not tolerate faults or adjust to dynamic changes in network topology. This paper presents a distributed self-stabilizing algorithm for the maximum flow problem. Starting from an arbitrary state, the algorithm computes the maximum flow in an acyclic network in finitely many steps. Since the algorithm is self-stabilizing, it is inherently tolerant to transient faults. It can automatically adjust to topology changes and to changes in other parameters of the problem. The paper presents results obtained by extensively experimenting with the algorithm. Two main observations based on these results are (1) the algorithm requires fewer than n2 moves for almost all test cases and (2) the algorithm consistently performs at least as well as a distributed implementation of the well-known Goldberg-Tarjan algorithm for almost all test cases. The paper ends with the conjecture that the algorithm correctly computes a maximum flow even in networks that contain cycles.
15460911
Polyhedral sampling for multiattribute preference elicitation
A basic requirement for running multiattribute auctions is knowledge of the utility function of the buyer that trades off nonprice attributes against price. We present and study an approach that elicits this preference structure based on a markovian polyhedral sampling scheme called the "Hit-and-Run" algorithm. An advantage of this technique is its relative simplicity - it relies only on matrix algebra as opposed to the use of nonlinear optimization techniques by other methods in the literature. Computational results suggest that this method is fast and accurate.
6238215
Fault-containing self-stabilizing algorithms
Self-stabilization provides a non-masking approach to fault tolerance. Given this fact, one would hope that in a self-stabilizing system, the amount of disruption caused by a fault is proportional to the severity of the fault. However, this is not true for many self-stabilizing systems. Our paper addresses this weakness of distributed self-stabilizing systems by introducing the notion of fault containment. Informally, a fault-containing self-stabilizing algorithm is one that contains the effects of limited transient faults while retaining the property of self-st abilization. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. Then, it is shown that self-stabilization and fault containment are goals that can conflict. For example, it is shown that imposing a O(1) bound on the worst case recovery time from a l-faulty state necessitates added overhead for stabilization: for some tasks, the O(1) recovery time implies sfiabilization time cannot be within O(1) rounds from the optimum value. The paper then presents a transformer T that maps any non-reactive self-stabilizing algorithm P into an equivalent fault-containing self-stabilizing algorithm Pf that can repair any l-faulty state in O(1) time with O(1) space overhead. This transformation is baaed on a novel stabilizing timer paradigm that significantly simplifies the ti=k of fault containment. The paper concludes by generalizing the transformer ‘T into a parameterized transformer 7(k) such that for varying k we obtain varying performance measures for Pf.