Search

Automatically predicting performance of parallel applications has been a long-standing goal in the area of high performance computing. However, accurate performance prediction is challenging, since the execution time of parallel applications is determined by several factors, such as sequential computation time, communication time and their complex interactions. Despite previous efforts, accurately estimating the sequential computation time in each process for large-scale parallel applications remains an open problem. In this paper, we propose a novel approach to acquiring accurate sequential computation time using a parallel debugging technique called deterministic replay. The main advantage of our approach is that we only need a single node of a target platform but the whole target platform does not need to be available. Therefore, with this approach we can simply measure the real sequential computation time on a target node for each process on by one. Moreover, we observe that there is great computation similarity in parallel applications, not only within each process but also among different processes. Based on this observation, we further propose representative replay that can significantly reduce replay overhead, because we only need to replay partial iterations for representative processes instead of all of them. Finally, we implement a complete performance prediction system, called Phantom, which combines the above computation-time acquisition approach and a trace-driven simulator. We validate our approach on both traditional HPC platforms and the latest Amazon EC2 cloud platform. On both types of platforms, prediction error of our approach is less than 7 percent on average up to 2,500 processes. [ABSTRACT FROM AUTHOR]

Access control is an indispensable security component of cloud computing, and hierarchical access control is of particular interest since in practice one is entitled to different access privileges. This paper presents a hierarchical key assignment scheme based on linear-geometry as the solution of flexible and fine-grained hierarchical access control in cloud computing. In our scheme, the encryption key of each class in the hierarchy is associated with a private vector and a public vector, and the inner product of the private vector of an ancestor class and the public vector of its descendant class can be used to derive the encryption key of that descendant class. The proposed scheme belongs to direct access schemes on hierarchical access control, namely each class at a higher level in the hierarchy can directly derive the encryption key of its descendant class without the need of iterative computation. In addition to this basic hierarchical key derivation, we also give a dynamic key management mechanism to efficiently address potential changes in the hierarchy. Our scheme only needs light computations over finite field and provides strong key indistinguishability under the assumption of pseudorandom functions. Furthermore, the simulation shows that our scheme has an optimized trade-off between computation consumption and storage space. [ABSTRACT FROM PUBLISHER]

In this paper, a new family of formats to deal with real number for applications requiring round to nearest is proposed. They are based on shifting the set of exactly represented numbers which are used in conventional radix- $\beta$ number systems. This technique allows performing radix complement and round to nearest without carry propagation with negligible time and hardware cost. Furthermore, the proposed formats have the same storage cost and precision as standard ones. Since conversion to conventional formats simply require appending one extra-digit to the operands, standard circuits may be used to perform arithmetic operations with operands under the new format. We also extend the features of the RN-representation system and carry out a thorough comparison between both representation systems. We conclude that the proposed representation system is generally more adequate to implement systems for computation with real number under round-to-nearest. [ABSTRACT FROM PUBLISHER]

Software Transactional Memory (STM) has recently emerged as a promising synchronization abstraction for multicore architectures. State-of-the-art STM algorithms, however, suffer from performance challenges due to contention and spinning on locks during the transaction commit phase. In this paper, we introduce Remote Transaction Commit (or RTC), a mechanism for executing commit phases of STM transactions. RTC dedicates server cores to execute transactional commit phases on behalf of application threads. This approach has two major benefits. First, it decreases the overheads of spinning on locks during commit, such as the number of cache misses, blocking of lock holders, and CAS operations. Second, it enables exploiting the benefits of coarse-grained locking algorithms (simple and fast lock acquisition, reduced false conflicts) and bloom filter-based algorithms (concurrent execution of independent transactions). Our experimental study on a 64-core machine with four sockets shows that RTC solves the problem of performance degradation due to spin locking on both micro-benchmarks (red-black trees), and macro-benchmarks (STAMP), especially when the commit phase is relatively long and when thread contention increases. [ABSTRACT FROM PUBLISHER]

In wireless local area networks (WLANs), link-layer multicast is a promising technology for many multimedia applications, e.g., video streaming, as multicast frames can reach multiple clients simultaneously. However, the efficiency of multicast in WLANs is usually low since multicast frames are transmitted at a basic data rate to reach clients with poor channel quality. Moreover, the reliability of multicast cannot be guaranteed either, as multicast transmissions are not acknowledged. Some recent works have utilized smart antennas to improve multicast performance. However, most of them require customized hardware and are not designed for the latest IEEE 802.11 standard, 802.11n WLANs. More importantly, these works did not consider the impact of AP association strategies on the performance of link-layer multicast. In this paper, we study the problem of link-layer multicast in large-scale 802.11n WLANs where each AP is equipped with a smart antenna that supports multiple antenna patterns. Based on channel gains of various antenna patterns from different APs, we choose the associated AP for multicast clients, partition associated clients of each AP into multiple groups, select an antenna pattern and data rate for each group of client, and transmit multicast frames to each group once. We first examine the limitation of multicast in 802.11n WLANs and the benefits of smart antennas to multicast via experiments. We then introduce the system model and formulate the problem into an optimization problem, and prove its NP-hardness. The objective is to minimize the time to transmit a multicast frame to all clients while guaranteeing high packet reception ratio (PRR) for each client. For generic WLANs where APs are sparsely deployed, we propose an optimal algorithm under the condition that the PRR of antenna patterns and data rates are known for every client. For generic large-scale WLANs, we further propose an on-line algorithm in which the AP association strategy, the partition of clients, the antenna pattern and data rate of each group are adapted dynamically, based on PRR reports from clients. We have implemented the on-line algorithm on off-the-shelf WLAN products, and conducted extensive experiments and simulations to evaluate the performance. The results show that the proposed algorithm can significantly improve multicast performance compared to other schemes, and at the same time guarantee high PRR for all clients. [ABSTRACT FROM PUBLISHER]

Task period selection is often used to adjust the workload to the available computational resources. In this paper, we propose a model where each selected period is not restricted to be a natural number, but can be any rational number within a range. Under this generalization, we contribute a period selection algorithm that yields a much smaller hyperperiod than that of previous works: with respect to the largest period, the hyperperiod with integer constraints is exponentially bounded; with rational periods the worst case is only quadratic. By means of an integer approximation at each task activation, we show how our rational period approach can work under system clock granularity; it is thus compatible with scheduling analysis practice and implementation. Our finding has practical applications in several fields of real-time scheduling: lowering complexity in table driven schedulers, reducing search space in model checking analysis, generating synthetic workload for statistical analysis of real-time scheduling algorithms, etc. [ABSTRACT FROM AUTHOR]

When complex functions, for example, substitution boxes of block ciphers, are realized in hardware, timing attributes of the underlying combinational circuit depend on the input/output changes of the function. These characteristics can be exploited by the help of a relatively new scheme called fault sensitivity analysis. A collision timing attack which exploits the data-dependent timing characteristics of combinational circuits is demonstrated in this paper. The attack is based on an also recently published correlation collision attack, which avoids the need for a hypothetical timing model for the underlying combinational circuit to recover the secret materials. The target platforms of our proposed attack are 14 AES ASIC cores of the SASEBO LSI chips in three different process technologies, 13 nm, 90 nm, and 65 nm. Successfully breaking all cores including the DPA-protected and fault attack protected cores indicates the strength of the attack. [ABSTRACT FROM AUTHOR]

Flow-level bandwidth provisioning (FBP) achieves fine-grained bandwidth assurance for individual flows. It is especially important for virtualization-based computing environments such as data centers. However, existing flow-level bandwidth provisioning solutions suffer from a number of drawbacks, including high implementation complexity, poor performance guarantees, and inefficiency to process variable length packets. In this paper, we study flow-level bandwidth provisioning for Combined Input Crosspoint Queued (CICQ) switches in the OpenFlow context. First, we propose the Flow-level Bandwidth Provisioning algorithm for CICQ switches, which reduces the switch scheduling problem to multiple instances of fair queuing problems, each utilizing a well-studied fair queuing algorithm. We theoretically prove that FBP can closely emulate the ideal Generalized Processing Sharing model, and accurately guarantee the provisioned bandwidth. Furthermore, we implement FBP in the OpenFlow software switch to obtain realistic performance data by a prototype. Leveraging the capability of OpenFlow to define and manipulate flows, we experimentally demonstrate a practical flow-level bandwidth provisioning solution. Finally, we conduct extensive simulations and experiments to evaluate the design. The simulation data verify the correctness of the analytical results, and show that FBP achieves tight performance guarantees. The experiment results demonstrate that our OpenFlow-based prototype can conveniently and accurately provision bandwidth at the flow level. [ABSTRACT FROM AUTHOR]

Flexible Chip Multiprocessor (CMP) systems are implemented on field programmable devices to exploit both task-level parallelism and architecture customization for parallel programs. The idea is to simultaneously allocate processor resources, map and schedule tasks to them, and to allocate one or several intertask communication resources such that the throughput or execution time is optimized. The design space of such systems is huge, requiring means to automatically optimize design parameters so as to facilitate wide and disciplined explorations. The complexity resulting from corresponding system modeling necessitates the use of optimization heuristics to cope with excessively long runtime for large problem instances. This paper provides a formal proof for the existence of optimum linear time synthesis algorithms for one of two classes of problem instances, and proceeds to present three greedy-like heuristics which exploit the structure of the synthesis problem. A comparison of results for real-time and non-real-time parallel programs is given against integer linear programming, where a synthesis strategy is proposed to achieve good results. [ABSTRACT FROM AUTHOR]

Hard real-time systems always choose not to use garbage collection in order to avoid its unpredictable executions. Much effort has been expended trying to build predictable garbage collectors which can provide both temporal and spatial guarantees. Unfortunately, most existing work leads to systems that cannot easily achieve a balance between temporal and spatial performances. Moreover, the scheduling of garbage collectors has not been integrated into modern real-time scheduling frameworks, which makes the benefits provided by the advancement of scheduling techniques very difficult to obtain. This paper argues that the existing design criteria for real-time garbage collectors do not reflect the unique requirements of flexible hard real-time systems. As a part of our design criteria, a new performance indicator is proposed to describe the capability of a real-time garbage collector to achieve a better balance between temporal and spatial performances. A hybrid garbage collection algorithm is designed accordingly which also uses dual priority scheduling algorithm to reclaim spare capacity while guaranteeing deadlines. [ABSTRACT FROM AUTHOR]

There are increasing interest and big challenges in designing a scalable and robust multicast routing protocol in a mobile ad hoc network (MANET) due to the difficulty in group membership management, multicast packet forwarding, and the maintenance of multicast structure over the dynamic network topology for a large group size or network size. In this paper, we propose a novel Robust and Scalable Geographic Multicast Protocol (RSGM). Several virtual architectures are used in the protocol without need of maintaining state information for more robust and scalable membership management and packet forwarding in the presence of high network dynamics due to unstable wireless channels and node movements. Specifically, scalable and efficient group membership management is performed through a virtual-zone-based structure, and the location service for group members is integrated with the membership management. Both the control messages and data packets are forwarded along efficient tree-like paths, but there is no need to explicitly create and actively maintain a tree structure. The stateless virtual-tree-based structures significantly reduce the tree management overhead, support more efficient transmissions, and make the transmissions much more robust to dynamics. Geographic forwarding is used to achieve further scalability and robustness. To avoid periodic flooding of the source information throughout the network, an efficient source tracking mechanism is designed. Furthermore, we handle the empty-zone problem faced by most zone-based routing protocols. We have studied the protocol performance by performing both quantitative analysis and extensive simulations. Our results demonstrate that RSGM can scale to a large group size and a large network size, and can more efficiently support multiple multicast groups in the network. Compared to existing protocols ODMRP and SPBM, RSGM achieves a significantly higher delivery ratio under all circumstances, with different moving speeds, node densities, group sizes, number of groups, and network sizes. RSGM also has the minimum control overhead and joining delay. [ABSTRACT FROM AUTHOR]

This paper describes the theory and design of digital high-radix multiplier-dividers (Patent Pending). The theory of high-radix division is extended to high-radix multiplier-dividers that can perform fused multiplication and division operations using a single recurrence relation. With the fused implementation of multiplication and division, the two operations can be executed using a single instruction, implying only a single rounding operation. The recurrence relation is described, the quotient digit selection function derived, and important design parameters together with their optimal values and relations are defined. Efficient design procedure and implementation hardware are described and important system parameter values for various radix systems computed. Compared to pure dividers, the multiplier-divider requires a slightly more complex data path and quotient digit selection function. [ABSTRACT FROM AUTHOR]

On-chip networks (OCNs) have been proposed to solve the increasing scale and complexity of the designs in nanoscale multicore VLSI designs. The concept of irregular meshes is an important issue because lPs of different sizes may be supported by various vendors. In order to solve routing problems in irregular meshes, modified routing algorithms to detour oversized IPs (OIPs) are needed. However, directly applying fault-tolerant routing algorithms may cause two serious problems: 1) heavy traffic loads around OIPs and 2) unbalanced traffic loads in irregular meshes. In this paper, we propose an OIP Avoidance Prerouting (OAPR) algorithm to solve the aforementioned problems. The proposed OAPR can make traffic loads evenly spread on the networks and shorten the average paths of packets. Therefore, the networks using the OAPR have lower latency and higher throughput than those using faulttolerant routing algorithms. In our experiments, four different cases are simulated to demonstrate that the proposed OAPR improves 13.3 percent to 100 percent sustainable throughputs than two previous fault-tolerant routing algorithms. Moreover, the hardware overhead of the OAPR is less than 1 percent compared to the cost of a whole router. Hence, the proposed OAPR algorithm has good performance and is practical for irregular mesh-based OCNs. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional synthesis tools. Also, the Boolean satisfiability problem finds new solution approaches when described in terms of majority decisions. To support computer logic applications based on majority, a sound and complete set of axioms is required. Most of the recent advances in majority logic deal only with ternary majority (MAJ-3) operators because the axiomatization with solely MAJ-3 and complementation operators is well understood. However, it is of interest extending such axiomatization to n-ary majority operators (MAJ-n) from both the theoretical and practical perspective. In this work, we address this issue by introducing a sound and complete axiomatization of MAJ-n logic. Our axiomatization naturally includes existing MAJ-3 and MAJ-5 axiomatic systems. Based on this general set of axioms, computer applications can now fully exploit the expressive power of majority logic. [ABSTRACT FROM PUBLISHER]

We consider a competitive environment for reward-based scheduling of periodic tasks, where the execution of each task consists of a mandatory and an optional part. Each task obtains a value if the processor successfully schedules all its mandatory part, and also an additional reward value if the processor successfully schedules a part of its optional execution. Each task is owned by a self-interested agent who has multiple choices for its requests based on its optional part. We model the reward-based scheduling problem by considering such multi-minded agents. However, the agent may try to manipulate the system to obtain an unfair optional allocation. We address this challenge by designing novel truthful mechanisms in which it is always in the agent's best interest to report their true task characteristics. We propose two truthful mechanisms (an exact and approximate) for selecting a feasible subset of agents and an allocation of optional execution that maximizes the total reward obtained by the selected tasks. To address the pseudo-polynomial complexity of the exact mechanism, we show that our proposed approximate mechanism is a polynomial-time approximation scheme (PTAS). Our extensive experiments show that our proposed approximation mechanism is capable of finding near-optimal solutions efficiently while guaranteeing truthfulness. [ABSTRACT FROM PUBLISHER]

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]