Search

A novel serial-in parallel-out finite field multiplier using redundant representation is proposed. It is shown that the proposed architecture has either a significantly lower complexity and comparable critical path delay or a significantly smaller critical path delay and comparable complexity in comparison to the previously proposed architectures using the same representation. For the class of fields where there exists a type I optimal normal basis, the proposed multiplier compares favorably to the normal basis multipliers. A digit-level version for the new multiplier is also presented in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we propose a general framework of the iterative local solution (ILS) for computing a connected dominating set (CDS) in ad hoc wireless networks, which include mobile ad hoc networks (MANETS) and wireless sensor networks (WSNs). This approach uses an iterative application of a selected local solution. Each application of the local solution enhances the result obtained from the previous iteration, but each is based on a different node priority scheme. Then, we integrate this iterative process into the process for handling a dynamic network topology and propose two extensions: cyclic iterative local solution (CILS) and seamless iterative local solution (SILS). CILS offers a natural extension of ILS to the dynamic environment but suffers from a broken CDS and nonadaptiveness. With a novel use of a monotonically increasing sequence number for dynamic node priority, SILS offers an extension with the desirable properties of correctness, progressiveness, locality, and seamlessness. Extensive simulations are conducted under ns-2 and a custom simulator to evaluate the effectiveness of the proposed approach in both static and dynamic environments. [ABSTRACT FROM AUTHOR]

Real-time systems using Rate-Monotonic fixed priority scheduling can be checked for schedulability either by sufficient but pessimistic schedulability conditions or by exact testing. Exact testing provides a more precise result but may not be performed in polynomial time. Audsley et al. proposed one of the earliest methods by iteratively deriving the response times of jobs. Other researchers have improved the exact test method by using different initial values for testing. In this paper, we propose new initial values of pi - pi-1 and pi/2 in a task set of i tasks, where pi is the period of task τi. We show that the new initial values can significantly improve the efficiency of exact testing. These period-dependent initial values can also be used for the schedulability test of multiframe task models and effectively reduce the number of iterations for testing. [ABSTRACT FROM AUTHOR]

A multimedia server requires a real-time disk-scheduling algorithm to deliver isochronous data for real-time streams. Traditional disk-scheduling algorithms focus on providing good quality in a best effort manner. In this paper, we propose a novel real-time disk-scheduling algorithm called WRR-SCAN (Weighted-Round-Robin-SCAN) to provide quality guarantees for all in- service streams encoded at variable bit rates and bounded response times for aperiodic jobs. WRR-SCAN divides a real-time stream into guaranteed jobs and optional jobs. The admission control admits a stream as long as its guaranteed jobs are satisfied. Such a decision is made in O(1) time as WRR-SCAN reserves a fixed weight for each stream. WRR-SCAN incorporates an aggressive policy to dynamically reclaim unused bandwidth during runtime. The reclaimed bandwidth is used to serve optional jobs or more aperiodic jobs. We conducted a set of simulations to compare WRR-SCAN with a set of referred disk-scheduling algorithms. The evaluations are conducted on a commonly used disk simulator with traces from a real multimedia server. The experimental results show that WRR-SCAN provides significantly better quality for real-time streams and yields considerably shorter response times for aperiodic jobs. [ABSTRACT FROM AUTHOR]

Network structure construction and global state maintenance are expensive in large-scale dynamic peer-to-peer (P2P) networks. With inherent topology independence and low state maintenance overhead, random walk is an excellent tool in such network environments. However, the current uses are limited to unguided or heuristic random walks with no guarantee on their converged node visitation probability distribution. Such a convergence guarantee is essential for strong analytical properties and high performance of many P2P applications. In this paper, we investigate an approach for random walks to converge to application- desired node visitation probability distributions while only requiring information about the direct neighbors of each peer. Our approach is guided by the Metropolis-Hastings algorithm for Monte Carlo Markov Chain sampling. Our contributions are threefold. First, we analyze the convergence time of the random walk node visitation probability distribution on common P2P network topologies. Second, we analyze the fault tolerance of our random walks in dynamic networks with potential walker losses. Third, we present the effectiveness of random walks in assisting three realistic network applications: random membership subset management, search, and load balancing. Both search and load balancing desire random walks with biased node visitation distributions to achieve application- specific goals. Our analysis, simulations, and Internet experiment demonstrate the advantage of our random walks compared with alternative topology-independent index-free approaches. [ABSTRACT FROM AUTHOR]

The physical security of application-specific embedded processors such as those found in smart-cards has become increasingly important since they are used more and more as conduits for sensitive financial and identity information. The advent of side-channel attacks has meant that a combination of algorithm, software, and hardware defense is required. In this paper, we reexamine the issue of nondeterministic processors, simplifying previous designs using a multithreaded architecture. From this simplification, we are able to construct a formally reasoned assessment of the security level offered by such a device. [ABSTRACT FROM AUTHOR]

This paper presents an efficient adaptive online routing algorithm for the computation of bandwidth-guaranteed paths in Multiprotocol Label Switching (MPLS)-based networks by using a learning scheme that computes an optimal ordering of routes. The contribution of this work is twofold. The first is that we propose a new class of solutions other than those available in the literature, incorporating the family of stochastic Random Races (RR) algorithms. The most popular previously proposed MPLS-based Traffic Engineering (TE) solutions attempt to find a superior path to route an incoming setup request. Our algorithm, on the other hand, tries to learn an optimal ordering of the paths through which requests can be routed according to the rank of the paths in the order learned by the algorithm. The second contribution of our work is that we have proposed a routing algorithm that has a performance superior to the important algorithms in the literature. Our conclusions are based on three important performance criteria: 1) the rejection ratio, 2) the percentage of accepted bandwidth, and 3) the average route computation time per request. Although some of the previously proposed algorithms were designed to achieve low rejection and high throughput of route requests, they are unreasonably slow. Our algorithm, on the other hand, in general attempts to reject the least number of requests, achieves the highest throughput, and computes routes in the fastest possible time when compared to the algorithms that we used as benchmarks for comparison. [ABSTRACT FROM AUTHOR]

In many emerging time-critical applications, the exact time of event occurrences may not be known. In such cases, events can be represented as a probabilistic occurrence within a time interval. Thus, monitoring of timing constraints, generally used in time-critical systems, needs to incorporate the uncertainty of event occurrences. In this paper, we propose mechanisms to monitor the satisfaction/violation of timing constraints that can be assessed probabilistically. We assume a uniform distribution of event occurrence within a time interval. Our proposed algorithm determines whether the probability that a timing constraint has been satisfied exceeds a specified threshold value. A confidence threshold is a minimum satisfaction probability of the timing constraint. A timing constraint is violated if the confidence threshold is not reached. We design an efficient monitoring algorithm for detecting timing violations of a set of timing constraints by finding the earliest expiration time (EET) for each timing constraint. Since it is critical to derive implicit constraints for early detection of violation of timing constraints, we present the derivation of the implicit constraints under uncertainty using an all-pairs shortest path algorithm. Further, we propose pruning techniques to discard unnecessary implicit constraints. We present the properties and proofs of our approach. [ABSTRACT FROM AUTHOR]

In this paper, we propose load distribution strategies for divisible loads for networked computing environments where computation and communication resource characteristics are unknown and/or vary with time. The principle on which our strategies are formulated is based on using probing loads to estimate the network characteristics and using them to determine the best possible load distribution. This work extends the adaptive strategies proposed in an earlier work to multilevel general networks. These networks, while being more challenging, also offer several opportunities that can be exploited to make the probing phase more efficient. We propose two strategies, one static, which caters to the presence of unknown parameters, and the other dynamic, which caters to both unknown as well as time-varying network parameters. The proposed strategies are robust, resilient, and easily adaptable to network fluctuations. The algorithms are also shown to have a tracking ability, a property that is important in dynamic environments. Examples are presented to illustrate the salient features of these strategies. [ABSTRACT FROM AUTHOR]

System-level diagnosis aims at the identification of faulty units in a system by the analysis of the system syndrome, that is, the outcomes of a set of interunit tests. For any given syndrome, it is possible to produce a correct (although possibly incomplete) diagnosis of the system if the number of faults is below a syndrome-dependent bound and the degree of diagnosis completeness, that is, the number of correctly diagnosed units, is also dependent on the actual syndrome σ. The worst-case diagnosis completeness is a syndrome-independent bound that represents the minimum number of units that the diagnosis algorithm correctly diagnoses for any syndrome. This paper provides a lower bound to the worst-case diagnosis completeness for regular graphs for which vertex- isoperimetric inequalities are known and it shows how this bound can be applied to toroidal grids. These results prove a previous hypothesis about the influence of two topological parameters of the diagnostic graph, that is, the bisection width and the diameter, on the degree of diagnosis completeness. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel sensor deployment algorithm, called the adaptive triangular deployment (ATRI) algorithm, for large-scale unattended mobile sensor networks. The ATRI algorithm aims at maximizing coverage area and minimizing coverage gaps and overlaps by adjusting the deployment layout of nodes close to equilateral triangulation, which is proven to be the optimal layout to provide the maximum no-gap coverage. The algorithm only needs the location information of nearby nodes, thereby avoiding communication cost for exchanging global information. By dividing the transmission range into six sectors, each node adjusts the relative distance to its one-hop neighbors in each sector separately. The distance threshold strategy and the movement state diagram strategy are adopted to avoid the oscillation of nodes. The simulation results show that the ATRI algorithm achieves a much larger coverage area and smaller average moving distance of nodes than existing algorithms. We also show that the ATRI algorithm is applicable to practical environments and tasks such as working in both bounded and unbounded areas and avoiding irregularly shaped obstacles. In addition, the density of nodes can be adjusted adaptively to different requirements of tasks. [ABSTRACT FROM AUTHOR]

A fundamental challenge in improving file system performance is to design effective block replacement algorithms to minimize buffer cache misses. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively, without taking into account file system prefetching, which exists in all modern operating systems. This paper shows that such kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk I/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. Moreover, since prefetching can increase the number of blocks clustered for each disk I/O and, hence, the time to complete the I/O, the reduction in the number of disk I/Os may not translate into proportional reduction in the total I/O time. These results demonstrate the importance of buffer caching research taking file system prefetching into consideration and comparing the actual disk I/Os and the execution time under different replacement algorithms. [ABSTRACT FROM AUTHOR]

Two high-speed bit-serial word-parallel or comb-style finite field multipliers are proposed in this paper. The first proposal utilizes a redundant representation for any binary field and the other uses a reordered normal basis for the binary field where a type-II optimal normal basis exists. The proposed redundant representation architecture has a smaller critical path delay compared to the previous methods while the complexities remain about the same. The proposed reordered normal basis multiplier has a significantly smaller critical path delay compared to the previous methods using the same basis or normal basis. Field-programmable gate array (FPGA) implementation results of the proposed multipliers are compared to those of the previous methods using the same basis, which confirms that the proposed multipliers allow a much higher clock rate. [ABSTRACT FROM AUTHOR]

Alternating group graphs AGn, studied by Jwo and others, Constitute a class of Cayley graphs that possess certain desirable properties compared with other regular networks considered by researchers in parallel and distributed computing. A different form, ANn, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AGn. For example, ANn has a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AGn, is maximally fault-tolerant, and shares some of the positive structural attributes of the well-known star graph. In this paper, we characterize the distance between any two nodes in ANn and present an optimal (shortest-path) routing algorithm for this class of networks. [ABSTRACT FROM AUTHOR]

This paper proposes novel techniques for scheduling radar dwells in phased array radar systems. In order to handle complex physical characteristics such as dwell interleaving, transmitting duty cycle constraint, and energy constraint, we propose a notion of schedulability envelope. The schedulability envelope designed offline hides the details of complex radar dwell scheduling and provides a simple measure for the schedulability check. Using the schedulability envelope, the proposed technique can efficiently perform the admission control for dynamic target tracking tasks. The simulation results show that the proposed approach can significantly improve the system utilization by taking advantage of dwell interleaving while guaranteeing the schedulability and physical constraints. [ABSTRACT FROM AUTHOR]

This paper establishes the state of the art in both deterministic and randomized online permutation routing in the POPS network. Indeed, we show that any permutation can be routed online on a POPS(d, g) network either with O(d/g log g) deterministic slots, or, with high probability, with 5c[d/g] + o(d/g) + O(log log g) randomized slots, where constant c = exp(1 + e-1) ≈ 3.927. When d = ϴ(g), which we claim to be the ‘interesting’ case, the randomized algorithm is exponentially faster than any other algorithm in the literature, both deterministic and randomized ones. This is true in practice as well. Indeed, experiments show that it outperforms its rivals even starting from as small a network as a POPS(2, 2) and the gap grows exponentially with the size of the network. We can also show that, under proper hypothesis, no deterministic algorithm can asymptotically match its performance. [ABSTRACT FROM AUTHOR]

A Taylor Expansion Diagram (TED) is a compact, word-level, canonical representation for data flow computations that can be expressed as multivariate polynomials. TEDs are based on a decomposition scheme using Taylor series expansion that allows one to model word-level signals as algebraic symbols. This power of abstraction, combined with the canonicity and compactness of TED, makes it applicable to equivalence verification of dataflow designs. The paper describes the theory of TEDs and proves their canonicity. It shows how to construct a TED from an HDL design specification and discusses the application of TEDs in proving the equivalence of such designs. Experiments were performed with a variety of designs to observe the potential and limitations of TEDs for dataflow design verification. Application of TEDs to algorithmic and behavioral verification is demonstrated. [ABSTRACT FROM AUTHOR]

In this paper, we present a bit-parallel multiplier for GF(2m) defined by an irreducible pentanomial ixm + xk3 + xk2 + xk1 + 1, where 1 ≤ k1 < k2 < k3 ≤ m/2. In order to design an efficient bit-parallel multiplier, we introduce a shifted polynomial basis and modify a reduction matrix presented by Reyhani-Masoleh and Hasan. As a result, the time complexity of the proposed multiplier is TA + (3 + [log2(m - 1)])Tx, where TA and Tx are the delay of one AND and one XOR gate, respectively. This result matches or outperforms the previously known results. On the other hand, the proposed multiplier has the same space complexity as the previously known multipliers except for special types of irreducible pentanomials. Note that its hardware architecture is similar to that presented by Reyhani-Masoleh and Hasan. [ABSTRACT FROM AUTHOR]

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. This paper proposes a (t, k)-diagnosis algorithm for matching composition networks, which include many well-known interconnection networks such as hypercubes, crossed cubes, twisted cubes, and Möbius cubes. It is shown that matching composition networks of n dimensions are (Ω(...), n), diagnosable, where n > 5. [ABSTRACT FROM AUTHOR]

This paper presents an enhanced architecture of on-chip pseudorandom test pattern generators, test data decompressors, and test response compactors based on ring generators. The new structure is aimed at improving layout and routing properties while, at the same time, reducing propagation delays introduced by associated phase shifters. [ABSTRACT FROM AUTHOR]

Elliptic curve cryptosystems (ECC) are suitable for memory-constraint devices like smart cards due to their small key-size. A standard way of computing elliptic curve scalar multiplication, the most frequent operation in EGG, is window methods, which enhance the efficiency of the binary method at the expense of some precomputation. The most established window methods are sliding window on NAF (NAF+SW), WNAF, and MOF, where NAF and MOF are acronyms for nonadjacent form and mutually opposite form, respectively. A common drawback of these schemes is that only a small portion of the numbers an possible sizes for precomputation tables. Therefore, in practice, it is often necessary to waste memory because there is no table fitting exactly the available storage. In the case of wNAF, there exists a variant that allows arbitrary table sizes, the so-called fractional wNAF (Frac-wOF). In this paper, we give a comprehensive proof using Markov theory for the estimation of the average nonzero density of the Frac-wNAF representation. Then, we propose the fractional wMOF (Frac-wMOF), which is a left-to-right analogue of Frac-wNAF. We prove that Frac-wMOF inherits the outstanding properties of Frac-wNAF. However, because of its left-to-right nature, Frac-wMOF is preferable as it reduces the memory consumption of the scalar multiplication. Finally, we show that the properties of all discussed previous schemes can be achieved as special instances of the Frac-wMOF method. To demonstrate the practicability of Frac-wMOF, we develop an on-the-fly algorithm for computing elliptic curve scalar multiplication with a flexibly chosen amount of memory. [ABSTRACT FROM AUTHOR]

Recently, implementations of normal basis multiplication over the extended binary field GF(2m) have received considerable attention. A class of low complexity normal bases called Gaussian normal bases has been included in a number of standards, such as IEEE [1] and NIST [21 for an elliptic curve digital signature algorithm. The multiplication algorithms presented there are slow in software since they rely on bit-wise inner product operations. In this paper, we present two vector-level software algorithms which essentially eliminate such bit-wise operations for Gaussian normal bases; Our analysis and timing results show that the software implementation of the proposed algorithm is faster than previously reported normal basis multiplication algorithms. The proposed algorithm is also more memory efficient compared with its look-up table-based counterpart. Moreover, two new digit-level multiplier architectures are proposed and it is shown that they outperform the existing normal basis multiplier structures. As compared with similar digit-level normal basis multipliers, the proposed multiplier with serial output requires the fewest number of XOR gates and the one with parallel output is the fastest multiplier. [ABSTRACT FROM AUTHOR]

Due to cost, time, and flexibility constraints, computer architects use simulators to explore the design space when developing new processors and to evaluate the performance of potential enhancements. However, despite this dependence on simulators, statistically rigorous simulation methodologies are typically not used in computer architecture research. A formal methodology can provide a sound basis for drawing conclusions gathered from simulation results by adding statistical rigor and, consequently, can increase the architect's confidence in the simulation results. This paper demonstrates the application of a rigorous statistical technique to the setup and analysis phases of the simulation process. Specifically, we apply a Plackett and Burman design to: 1) identify key processor parameters, 2) classify benchmarks based on how they affect the processor, and 3) analyze the effect of processor enhancements. Our results showed that, out of the 41 user-configurable parameters in SimpleScalar, only 10 had a significant effect on the execution time. Of those 10, the number of reorder buffer entries and the L2 cache latency were the two most significant ones, by far. Our results also showed that instruction Precomputation-a value reuse-like microarchitectural technique-primarily improves the processor's performance by relieving integer ALU contention. [ABSTRACT FROM AUTHOR]

In this paper, we present a new concurrent error-detection scheme by hybrid signature to the online detection of program memory and control flow errors caused by transient and intermittent faults. The proposed hybrid signature-monitoring technique combines the vertical signature with the horizontal signature schemes. We first develop a new vertical signature based on linear additive code whose signature length could be easily adjusted. The attribute of adjustable length in vertical signature offers the feasibility to integrate the vertical signature, horizontal signature, and length of block into a single signature word. The horizontal signature mechanism can compensate for the coverage degradation due to the reduction of vertical signature length and significantly decrease the error-detection latency as well. The extensive block-based bit-error simulation and hardware-based simulated fault injection experiment are conducted to validate the effectiveness of the proposed technique. Compared to the continuous signature monitoring (CSM) scheme, there are several notable enhancements accomplished in our work. One is the fault model used in our work is more realistic than the model employed in CSM. Another is the hardware-based experiments are performed so as to measure the design parameters more accurately. The final one is our scheme does not require being equipped with SEC-DED code in program memory in order to achieve the horizontal signatures if instruction bit correction is not an essential demand; as a result, our scheme is more flexible than CSM. [ABSTRACT FROM AUTHOR]

Allowing higher-priority requests to preempt ongoing disk IOs is of particular benefit to delay-sensitive and real-time systems. In this paper, we present Semi-preemptible IO, which divides disk IO requests into small temporal units of disk commands to improve the preemptibility of disk access. We first lay out main design strategies to allow preemption of each component of a disk access-seek, rotation, and data transfer, namely, seek-splitting, JIT-seek, and chunking. We then present the preemption mechanisms for single and multidisk systems-JIT-preemption and JIT-migration. The evaluation of our prototype system showed that Semi-preemptible IO substantially improved the preemptibility of disk access with little loss in disk throughput and that preemptive disk scheduling could improve the response time for high-priority interactive requests. [ABSTRACT FROM AUTHOR]

Wire delays are a major concern for current and forthcoming processors. One approach to deal with this problem is to divide the processor into semi-independent units referred to as clusters. A cluster usually consists of a local register file and a subset of the functional units, while the L1 data cache typically remains centralized in what we call partially distributed architectures. However, as technology evolves, the relative latency of such a centralized cache will increase, leading to an important impact on performance. In this paper, we propose partitioning the L1 data cache among clusters for clustered VLIW processors. We refer to this kind of design as fully distributed processors. In particular, we propose and evaluate three different configurations: a snoop-based cache coherence scheme, a word-interleaved cache, and flexible L0 buffers managed by the compiler. For each alternative, instruction scheduling techniques targeted to cyclic code are developed. Results for the Mediabench suite show that the performance of such fully distributed architectures is always better than the performance of a partially distributed one with the same amount of resources. In addition, the key aspects of each fully distributed configuration are explored. [ABSTRACT FROM AUTHOR]

Reducing the energy consumption of a real-time system has emerged as an important design concern. In this paper, we propose GAARP, an adaptive scalable architecture targeted toward algorithm-specific tasks for just-in-time performance using the right amount of power. The architecture consists of Globally Asynchronous and Locally Synchronous (GALS) building blocks, where the processing hardware is realized by a set of smaller slices of similar structure, each running synchronously with independent clocks. We demonstrate that, for different real-time commercial applications with algorithm-specific jobs like online transaction processing, digital filtering, Fourier transform, etc., the proposed architecture allows dynamic load-balancing and adaptive intertask voltage scaling based on the load in each of the processing units. Compared to a synchronous implementation of the same functionality, we show that the proposed hardware can achieve higher efficiency in terms of power and performance by exploiting the flexibility to balance the load and change the supply voltage. The architecture also lends itself to process tolerance since it can detect process-shifts for the individual processing units and determine the appropriate operating voltage/frequency for each unit. Simulation results for two representative applications show that, for a modest system configuration and random job distribution, we obtain up to 67 percent improvement in MOPS/W (millions of operations per second per watt) over a fully synchronous implementation. [ABSTRACT FROM AUTHOR]

Designing energy-efficient clusters has recently become an important concern to make these systems economically attractive for many applications. Since the cluster interconnect is a major part of the system, the focus of this paper is to characterize and optimize the energy consumption in the entire interconnect. Using a cycle-accurate simulator of an InfiniBand Architecture (IBA) compliant interconnect fabric and actual designs of its components, we investigate the energy behavior on regular and irregular interconnects. The energy profile of the three major components (switches, network interlace cards (NICs), and links) reveals that the links and switch buffers consume the major portion of the power budget. Hence, we focus on energy optimization of these two components. To minimize power in the links, first we investigate the dynamic voltage scaling (DVS) algorithm and then propose a novel dynamic link shutdown (DLS) technique. The DLS technique makes use of an appropriate adaptive routing algorithm to shut down the links intelligently. We also present an optimized buffer design for reducing leakage energy in 70nm technology. Our analysis on different networks reveals that, while DVS is an effective energy conservation technique, it incurs significant performance penalty at low to medium workload. Moreover, energy saving with DVS reduces as the buffer leakage current becomes significant with 70nm design. On the other hand, the proposed DLS technique can provide optimized performance-energy behavior (up to 40 percent energy savings with less than 5 percent performance degradation in the best case) for the cluster interconnects. [ABSTRACT FROM AUTHOR]

This tutorial paper examines architectural and circuit design techniques for a microsensor node operating at power levels low enough to enable the use of an energy harvesting source. These requirements place demands on all levels of the design. We propose an architecture for achieving the required ultra-low energy operation and discuss the circuit techniques necessary to implement the system. Dedicated hardware implementations improve the efficiency for specific functionality, and modular partitioning permits fine-grained optimization and power-gating. We describe modeling and operating at the minimum energy point in the subthreshold region for digital circuits. We also examine approaches for improving the energy efficiency of analog components like the transmitter and the ADC. A microsensor node using the techniques we describe can function in an energy-harvesting scenario. [ABSTRACT FROM AUTHOR]

Due to deterministic and fast lookup performance, Ternary Content Addressable Memory (TCAM) has recently been gaining popularity in general policy filtering (PF) for packet classification in high-speed networks: However, the PF table update poses significant challenges for efficient use of TCAM. To avoid erroneous and inconsistent rule matching, the traditional approach is to lock the PF table during the rule update period, but table locking has a negative impact on data path processing. In this paper, we propose a novel scheme, called Consistent Policy Table Update Algorithm (CoPTUA), for TCAM. Instead of minimizing the number of rule moves to reduce the locking time, CoPTUA maintains a consistent PF table throughout the update process, thus eliminating the need for locking the PF table while ensuring correctness of rule matching. Our analysis and simulation show that, even for a PF table with 100,000 rules, an arbitrary number of rules can be updated simultaneously within 1 second in the worst case, provided that 2 percent of the PF table entries are empty. Thus, CoPTUA enforces any new rule in less than 1 second for practical PF table size with high memory utilization and without impacting data path processing. [ABSTRACT FROM AUTHOR]

A Multiple Bus Network (MBN) connects a set of processors via a set of buses. Two important parameters of an MBN are its loading (largest number of connections on a bus) and its degree (largest number of connections to a processor). These parameters determine the cost, speed, and implementability of the MBN. The smallest degree that any useful MBN can have is 2. In this paper, we study the relationship between running time, degree, and loading of degree-2 MBNs running a fundamental class of algorithms called binary tree algorithms. (A binary tree algorithm reduces 2n inputs at the leaves of a balanced binary tree to a single result at the root of the tree.) Specifically, we establish a nontrivial Ω(n/log n) loading lower bound for any degree-2 MBN running a 2n input binary tree algorithm optimally in n steps. We show that this bound does not hold if the restriction on the degree or the running time is relaxed. That is, optimal-time, degree-3, constant loading MBNs and suboptimal-time, degree-2, constant loading MBNs exist for binary tree algorithms. We also derive a lower bound on the additional time (beyond the optimal) needed to run binary tree algorithms on a degree-2, loading-L MBN, for any L&ges; 3. [ABSTRACT FROM AUTHOR]

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks have been explored. In this paper, we consider the diagnosability of a family of networks, called the Matching Composition Network (MCN); two components are connected by a perfect matching. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the Hypercube Qn, the Crossed cube CQn the Twisted cube TQn and the Möbius cube MQn, can all be-proven to be n, for n ≥4. In particular, we show that the diagnosability of the four- dimensional Hypercube Q4 is 4, which is not previously known. [ABSTRACT FROM AUTHOR]

Choosing the pipeline depth of a microprocessor is one of the most critical design decisions that an architect must make in the concept phase of a microprocessor design. To be successful in today's cost/performance marketplace, modern CPU designs must effectively balance both performance and power dissipation. The choice of pipeline depth and target clock frequency has a critical impact on both of these metrics. In this paper, we describe an optimization methodology based on both analytical models and detailed simulations for power and performance as a function of pipeline depth. Our results for a set of SPEC2000 applications show that, when both power and performance are considered for optimization, the optimal clock period is around 18 FO4. We also provide a detailed sensitivity analysis of the optimal pipeline depth against key assumptions of our energy models. Finally, we discuss the potential risks in design quality for overly aggressive or conservative choices of pipeline depth. [ABSTRACT FROM AUTHOR]

Energy conservation without performance degradation is an important goal for battery-operated computers, such as laptops and hand-held assistants. In this paper, we study application-supported device management for optimizing energy and performance. In particular, we consider application transformations that increase device idle times and inform the operating system about the length of each upcoming period of idleness. We use modeling and experimentation to assess the potential energy and performance benefits of this type of application support for a laptop disk. Furthermore, we propose and evaluate a compiler framework for performing the transformations automatically. Our main modeling results show that the transformations are potentially beneficial. However, our experimental results with six real laptop applications demonstrate that, unless applications are transformed, they cannot accrue any of the predicted benefits. In addition, they show that our compiler can produce almost the same performance and energy results as hand-modifying applications. Overall, we find that the transformations can reduce disk energy consumption from 55 percent to 89 percent with a degradation in performance of at most 8 percent. [ABSTRACT FROM AUTHOR]

Real-time scheduling theory offers constant-time schedulability tests for periodic and sporadic tasks based on utilization bounds. Unfortunately, the periodicity or the minimal interarrival-time assumptions underlying these bounds make them inapplicable to a vast range of aperiodic workloads such as those seen by network routers, Web servers, and event-driven systems. This paper makes several important contributions toward real-time scheduling theory and schedulability analysis. We derive the first known bound for schedulability of aperiodic tasks. The bound is based on a utilization-like metric we call synthetic utilization, which allows implementing constant-time schedulability tests at admission control time. We prove that the synthetic utilization bound for deadline-monotonic scheduling of aperiodic tasks is 1/1+√ ½. We also show that no other time-independent scheduling policy can have a higher schedulability bound. Similarly, we show that EDF has a bound of 1 and that no dynamic-priority policy has a higher bound. We assess the performance of the derived bound and conclude that it is very efficient in hit-ratio maximization. [ABSTRACT FROM AUTHOR]

The OpenGL geometry pipeline lighting stage requires raising a number in the range [0, 1] to a power between [1, 128] to compute specular reflections and spotlights. The result need only be accurate to a number of bits related to the color depth of the output device. This paper describes a hardware implementation of such an exponentiation unit based on a logarithm lookup table, a multiplier, and an inverse log table. The inputs arrive in IEEE single-precision floating-point format and the output is a floating-point color component in the range [0, 1] with 8-10 bits of accuracy. The log lookup table is partitioned into subintervals to reduce table size and each subinterval is computed from a bipartite table to further reduce size. A synthesized design uses 32k gates to achieve 10-bit accuracy with a latency of 9.4 ns in a 180 nm process. Although the system is tailored to the OpenGL application, the same principles can be applied to the design of other exponentiation units. [ABSTRACT FROM AUTHOR]

In this paper, we show that subsets of Cohorts coteries proposed in [5] are nondominated (ND) k-coteries, which are candidates to achieve the highest availability when utilized to solve the distributed k-mutual exclusion problem and the distributed h-out of-k mutual exclusion problem. [ABSTRACT FROM AUTHOR]

Two architectures for modulo 2^n+1 adders are introduced in this paper. The first one is built around a sparse carry computation unit that computes only some of the carries of the modulo 2^n+1 addition. This sparse approach is enabled by the introduction of the inverted circular idempotency property of the parallel-prefix carry operator and its regularity and area efficiency are further enhanced by the introduction of a new prefix operator. The resulting diminished-1 adders can be implemented in smaller area and consume less power compared to all earlier proposals, while maintaining a high operation speed. The second architecture unifies the design of modulo 2^n\pm 1 adders. It is shown that modulo 2^n+1 adders can be easily derived by straightforward modifications of modulo 2^n-1 adders with minor hardware overhead. [ABSTRACT FROM PUBLISHER]