6555367
Selecting Error Correcting Codes to Minimize Power in Memory Checker Circuits
The approach proposed in this paper reduces power consumption in single-error correcting, double error-detecting checker circuits that perform memory ECC. Power is minimized with little or no impact on area and delay, using the degrees of freedom in selecting the parity check matrix of the error correcting code. The non-linear power optimization problem is solved using two methods, genetic algorithms and simulated annealing. Both the methods are applied to two 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 along with 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. Experiments are also performed to motivate the choice of parameters of the non-linear optimization algorithms, using sensitivity analysis of the low-power solutions to the choice of the different parameters of each algorithm.
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.
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.
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.
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.
6735470
FraNtiC: A Fractal Geometric Framework for Mesh-Based Wireless Access Networks
The design of the access networks of next generation broadband wireless systems requires special attention in the light of changing network characteristics. In this paper, we present a mesh-based distributed radio access network (RAN) framework for future wireless systems. Using short, high bandwidth optical wireless links to interconnect the various network elements, we identify a generic fractal or self similar structure in the network. A mathematical model for the framework is presented and the benefits of its scale-invariant properties on robustness, reliability and flexibility analyzed. We focus on three design parameters - carrier-class network reliability, network exposure due to failure conditions and system cost. The dynamics of these parameters on our proposed architecture are studied and compared against existing access network topologies like tree/ring and square-grid. The generality and recursive nature of our framework lends itself to be applied in interconnecting various heterogeneous broadband wireless access networks of the future
7750491
Revisiting correlations and scheduling in Web servers
Mathematical models play an important role in the design, analysis, control, optimization, management andplanning of Web server systems. To be most effective in each of these areas, such models must capture in sufficient detail the key characteristics of Web server workloads, the key characteristics of Web server scheduling policies for executing these workloads, and the impact of these workload and scheduling policy characteristics on Web server performance and related measures . Of particular interest in our study are very efficient mathematical methods that can be exploited online to support an increasingly important range of real-time applications (e .g., dynamic control of quality of service in Web servers to best satisfy service-level agreements), as well as in efficient interactive tools often used offline for many different purposes (e.g., what-ifanalysis and stochastic optimization for capacity planning). A significant body of research has investigated the workloads found in practice at a wide variety of Web server environments ; e.g ., see [1, 8, 18]. Most of these studies have demonstrated that the client request patterns exhibited at many different types of Web server environments have strong dependence structures and that the requested files sizes at these Web servers are independent and identically distributed (i .i .d.) according to a heavy-tailed or subexponential distribution . However, the vast majority of these studies appear to have completely ignored the issue of whether there is any correlation between the client request arrival times and the requested file sizes or the request service times. This includes studies of Web server workload characterization and generation, Web server performance models, and Web server scheduling policies . In this study, we consider data from various commercial Web server environments to revisit the issues of different forms of correlation in these Web server workloads and their implications on Web server performance and scheduling policies . Theresults ofour data analysis demonstrate the existence ofsignificant dependencies between the client request interarrival times and the corresponding file sizes and service times. Our analysis also shows a strong dependence structure within the interarrival process of client requests, whereas the sequence of service times is essentially i .i .d . To the best ofour knowledge, this is the first study to identify and quantify significant dependencies between the arrival and service processes in Web server environments (as opposed to network environments, where this issue goes all the way back to Kleinrock [15]). We then investigate the source of this cross correlation between the client request interarrival times and the corresponding file sizes and service times. The results of our data analysis support the view that such cross correlations are primarily due to certain mixing effects involving the superposition of different classes of client requests each with different service requirements . We next turn to consider a mathematical analysis of queueing Mark S. Squillante Mathematical Sciences Department IBM Thomas J. Watson Research Center Yorktown Heights, NY 10598, USA mss@watson .ibm .com
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.
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.

62100403
Scalable self-stabilization
The paper presents a method by which an asynchronous non-reactive distributed system can stabilize from a k-faulty configuration in a time that is a monotonically increasing function of k and independent of the size of the system. In the proposed methodology processes first measure the size of the faulty regions, and then use this information to schedule actions in such a way that the faulty regions progressively shrink, until they completely disappear. When k contiguous processes fail, the stabilization time is O(k/sup 3/). Otherwise, for small values of k, the stabilization time can be exponential in k, but it has an upper bound of O(n/sup 3/). The added space complexity per process is O(/spl delta/ log/sub 2/n), where /spl delta/ is the maximum degree of a node.