Search

With the huge demand for graph analytics in many real-world applications, massive iterative graph processing jobs are concurrently performed on the same graphs and suffer from significant high data access cost. To lower the data access cost toward high performance, several out-of-core concurrent graph processing solutions are recently designed to handle concurrent jobs by enabling these jobs to share the accesses of the same graph data. However, the set of active vertices in each partition are usually different for various concurrent jobs and also evolve with time, where some high-degree ones (or called hub-vertices) of these active vertices require more iterations to converge due to the power-law property of real-world graphs. In consequence, existing solutions still suffer from much unnecessary I/O traffic, because they have to entirely load each partition into the memory for concurrent jobs even if most vertices in this partition are inactive and may be shared by a few jobs. In this paper, we propose an efficient structure-aware storage system, called GraphSO, for higher throughput of the execution of concurrent graph processing jobs. It can be integrated into existing out-of-core graph processing systems to promote the execution efficiency of concurrent jobs with lower I/O overhead. The key design of GraphSO is a fine-grained storage management scheme. Specifically, it logically divides the partitions of existing graph processing systems into a series of small same-sized chunks. At runtime, these small chunks with active vertices are judiciously loaded by GraphSO to construct new logical partitions (i.e., each logical partition is a subset of active chunks) for existing graph processing systems to handle, where the most-frequently-used chunks are preferentially loaded to construct the logical partitions and the other ones are delayed to wait to be required by more jobs. In this way, it can effectively spare the cost of loading the graph data associated with the inactive vertices with low repartitioning overhead and can also enable the loaded graph data to be fully shared by concurrent jobs. Moreover, GraphSO also designs a buffering strategy to efficiently cache the most-frequently-used chunks in the main memory to further minimize the I/O traffic by avoiding repeated load of them. Experimental results show that GraphSO improves the throughput of GridGraph, GraphChi, X-Stream, DynamicShards, LUMOS, Graphene, and Wonderland by 1.4-3.5 times, 2.1-4.3 times, 1.9-4.1 times, 1.9-2.9 times, 1.5-3.1 times, 1.3-1.5 times, and 1.3-2.7 times after integrating with them, respectively. [ABSTRACT FROM AUTHOR]

The past decade has seen growing importance being attached to the Completely Independent Spanning Trees (CISTs). The CISTs can facilitate many network functionalities, and the existence and construction schemes of CISTs in various networks can be an indicator of the network's robustness. In this paper, we establish the number of CISTs that can be constructed in the line graph of the complete graph $K_n$ K n (denoted $L(K_n)$ L (K n) , for $n\geq 4$ n ≥ 4 ), and present an algorithm to construct the optimal (i.e., maximal) number of CISTs in $L(K_n)$ L (K n) . The $L(K_n)$ L (K n) is a special class of SWCube [13], an architectural model proposed for data center networks. Our construction algorithm is also implemented to verify its validity. [ABSTRACT FROM AUTHOR]

The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard to implement using reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size $O(n^{6.42})$ O (n 6. 42) , where $n$ n is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size $O(n^2)$ O (n 2) . The technical tools employed come from a combination of Theoretical Computer Science (Barrington's theorem) and Physics (simulation of fermionic Hamiltonians) techniques. [ABSTRACT FROM AUTHOR]

Index structures can significantly accelerate the data retrieval operations in data intensive systems, such as databases. Tree structures, such as B^+ -tree alike, are commonly employed as index structures; however, we found that the tree structure may not be appropriate for Non-Volatile Memory (NVM) in terms of the requirements for high-performance and high-endurance. This paper studies what is the best index structure for NVM-based systems and how to design such index structures. The design of an NVM-friendly index structure faces a lot of challenges. First, in order to prolong the lifetime of NVM, the write activities on NVM should be minimized. To this end, the index structure should be as simple as possible. The index proposed in this paper is based on the simplest data structure, i.e., linked list. Second, the simple structure brings challenges to achieve high-performance data retrieval operations. To overcome this challenge, we design a novel technique by explicitly building up a contiguous virtual address space on the linked list, such that efficient search algorithms can be performed. Third, we need to carefully consider data consistency issues in NVM-based systems, because the order of memory writes may be changed and the data content in NVM may be inconsistent due to write-back effects of CPU cache. This paper devises a novel indexing scheme, called “Virtual Linear Addressable Buckets” (VLAB). We implement VLAB in a storage engine and plug it into MySQL. Evaluations are conducted on an NVDIMM workstation using YCSB workloads and real-world traces. Results show that write activities of the state-of-the-art indexes are 6.98 times more than ours; meanwhile, VLAB achieves 2.53 times speedup. [ABSTRACT FROM AUTHOR]

The design of high-performance adders has experienced a renewed interest in the last few years; among high performance schemes, parallel prefix adders constitute an important class. They require a logarithmic number of stages and are typically realized using AND-OR logic; moreover with the emergence of new device technologies based on majority logic, new and improved adder designs are possible. However, the best existing majority gate-based prefix adder incurs a delay of 2\mathbflo\mathbfg_2(\boldsymboln) - 1 (due to the \boldsymboln th carry); this is only marginally better than a design using only AND-OR gates (the latter design has a 2\mathbflo\mathbfg_2(\boldsymboln) + 1 gate delay). This paper initially shows that this delay is caused by the output carry equation in majority gate-based adders that is still largely defined in terms of AND-OR gates. In this paper, two new majority gate-based recursive techniques are proposed. The first technique relies on a novel formulation of the majority gate-based equations in the used group generate and group propagate hardware; this results in a new definition for the output carry, thus reducing the delay. The second contribution of this manuscript utilizes recursive properties of majority gates (through a novel operator) to reduce the circuit complexity of prefix adder designs. Overall, the proposed techniques result in the calculation of the output carry of an \boldsymboln -bit adder with only a majority gate delay of \mathbflo\mathbfg_2(\boldsymboln) + 1 . This leads to a reduction of 40percent in delay and 30percent in circuit complexity (in terms of the number of majority gates) for multi-bit addition in comparison to the best existing designs found in the technical literature. [ABSTRACT FROM AUTHOR]

As the performance gap between processors and storage devices keeps increasing, I/O performance becomes a critical bottleneck of modern high-performance computing systems. In this paper, we propose a pattern-directed and layout-aware data replication design, named PDLA, to improve the performance of parallel I/O systems. PDLA includes an HDD-based scheme H-PDLA and an SSD-based scheme S-PDLA. For applications with relatively low I/O concurrency, H-PDLA identifies access patterns of applications and makes a reorganized data replica for each access pattern on HDD-based servers with an optimized data layout. Moreover, to accommodate applications with high I/O concurrency, S-PDLA replicates critical access patterns that can bring performance benefits on SSD-based servers or on HDD-based and SSD-based servers. We have implemented the proposed replication scheme under MPICH2 library on top of OrangeFS file system. Experimental results show that H-PDLA can significantly improve the original parallel I/O system performance and demonstrate the advantages of S-PDLA over H-PDLA. [ABSTRACT FROM AUTHOR]

Projected Sums of Products (PSOPs) are a Generalized Shannon Decomposition (GSD) with remainder that restructures a logic function into three logic blocks corresponding to a logic bi-decomposition plus a reminder generated by a cofactoring function. In this paper we discuss a Boolean synthesis technique for PSOPs, which exploits the fact that the resulting logical structure induces don't care conditions that can be exploited to reduce the problem of area minimization to Boolean relation minimization, with the guarantee that all valid realizations of the circuit are considered. This technique is more general than the algebraic methods investigated so far. Moreover, we characterize the points that are in the remainder with a simple procedure that implies a fast construction of the Boolean relation for important classes of cofactoring functions like the chain of XORs or ANDs. We report experiments confirming the effectiveness in area of the proposed approach based on Boolean relations, with better run times for some cost functions. [ABSTRACT FROM AUTHOR]

Branch-and-bound approaches are promising in pruning fruitless search space during the resource constrained scheduling. However, such approaches only compare the estimated upper and lower bounds of an incomplete schedule to the length of the best feasible schedule at that iteration, which does not fully exploit the potential of the pruning during the search. Aiming to improve the performance of resource constrained scheduling, this paper proposes a parallel structure-aware pruning approach that can traverse the search space significantly faster than state-of-the-art branch-and-bound techniques. This paper makes three major contributions: i) it proposes an efficient pruning technique using the structural scheduling information of the obtained best feasible schedules; ii) it investigates how to perform parallel search to enable efficient multi-directional search and generation of effective fences by tuning the operation enumeration order; and iii) it presents a framework that supports the sharing of minimum upper-bound and fence information among different search tasks to enable efficient parallel structure-aware pruning. The experimental results demonstrate that our parallel pruning approach can drastically reduce the overall resource constrained scheduling time under a wide variety of resource constraints. [ABSTRACT FROM PUBLISHER]

This paper presents a comprehensive study of the computation of square roots over finite extension fields. We propose two novel algorithms for computing square roots over even field extensions of the form \BBF{q^2}, with q = p^n, p an odd prime and n \geq 1. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in \BBF{q^2}. The first algorithm is devoted to the case when q \equiv 1\, mod\, 4, whereas the second one handles the case when q \equiv 3\, mod\,4. Numerical comparisons show that the two algorithms presented in this paper are competitive and in some cases more efficient than the square root methods previously known. [ABSTRACT FROM AUTHOR]

Recent smart devices have adopted heterogeneous multi-core processors which have high-performance big cores and low-power small cores. Unfortunately, the conventional task scheduler for heterogeneous multi-core processors does not provide appropriate amount of CPU resources for multimedia applications (whose QoS is important to users), resulting in energy waste; it often executes multimedia applications and non-multimedia applications on the same core. In this paper, we propose an advanced task scheduler for heterogeneous multi-core processors, which provides appropriate amount of CPU resources for multimedia applications. Our proposed task scheduler isolates multimedia applications from non-multimedia applications at runtime, exploiting the fact that multimedia applications have a specific thread for video/audio playback (to play video/audio, a multimedia application should use a function that generates the specific thread). Since multimedia applications usually require a smaller amount of CPU resources than non-multimedia applications due to dedicated hardware decoders, our proposed task scheduler allocates the former to the small cores and the latter to the big cores. In our experiments on an Android-based development board, our proposed task scheduler saves system-wide (not just CPU) energy consumption by 8.9 percent, on average, compared to the conventional task scheduler, preserving QoS of multimedia applications. In addition, it improves performance of non-multimedia applications by 13.7 percent, on average, compared to the conventional task scheduler. [ABSTRACT FROM PUBLISHER]

Sorting is one of the most fundamental topics in computer science. Since partial sorting with lower costs would be much more feasible than the complete sorting method for some applications, this paper focuses on the architecture sorting N values from M inputs. To meet the real-time processing requirement, hardware acceleration is commonly employed to enhance the performance. However, high-speed computation usually raises power consumption drastically.To overcome that problem, a low-power, high-throughput, and modular hardware design of partial sorting network is presented. By applying a pointer-like design, the comparing modules move the indexes of samples instead of moving the input data directly. Power dissipation is reduced by minimizing switching activities and signal transitions. To prevent unnecessary comparing of the large data set, an iterative architecture is proposed which uses both the low-power sorting module and a novel clipping mechanism. The proposed design was simulated with a 90-nm cell library and the results are compared to those of other works on hardware sorting. Experiment results show that power consumption is reduced by 64.9 percent and high-throughput performance can also be achieved. [ABSTRACT FROM AUTHOR]

The decreasing lifetime of NAND flash memory, as a side effect of recent advanced semiconductor process scaling, is emerging as one of major barriers to the wide adoption of SSDs in high-performance computing systems. In this paper, we propose Dynamic Erase Voltage and Time Scaling (DeVTS), an integrated approach to extend the lifetime (particularly, endurance) of NAND flash memory. DeVTS is motivated by our key observation that erasing a NAND block with a lower voltage or at a slower speed can significantly improve NAND endurance. However, using a lower erase voltage causes adverse side effects on the write performance and retention capability of NAND flash memory. In order to improve NAND endurance without affecting the other NAND requirements, we take advantage of idle times between write requests and variations of the retention requirement when writing data to a NAND block erased with a lower voltage. We have implemented a DeVTS-aware FTL, called dvsFTL, which exploits the tradeoff relationship between the endurance and erase voltages/times by accurately predicting the write performance and retention requirements. Our experimental results show that dvsFTL can improve NAND endurance by 94 percent, on average, over an existing DeVTS-unaware FTL while all the NAND requirements are preserved. [ABSTRACT FROM PUBLISHER]

Tons of online user behavior data are being generated every day on the booming and ubiquitous Internet. Growing efforts have been devoted to mining the abundant behavior data to extract valuable information for research purposes or business interests. However, online users’ privacy is thus under the risk of being exposed to third-parties. The last decade has witnessed a body of research works trying to perform data aggregation in a privacy-preserving way. Most of existing methods guarantee strong privacy protection yet at the cost of very limited aggregation operations, such as allowing only summation, which hardly satisfies the need of behavior analysis. In this paper, we propose a scheme PPSA, which encrypts users’ sensitive data to prevent privacy disclosure from both outside analysts and the aggregation service provider, and fully supports selective aggregate functions for online user behavior analysis while guaranteeing differential privacy. We have implemented our method and evaluated its performance using a trace-driven evaluation based on a real online behavior dataset. Experiment results show that our scheme effectively supports both overall aggregate queries and various selective aggregate queries with acceptable computation and communication overheads. [ABSTRACT FROM PUBLISHER]

Functional Units that are designed to receive inputs and produce outputs using a non-redundant format typically exhibit an inferior performance. In order to overcome this limitation, the carry-save and partial carry-save formats have been proposed. Both approaches are very suitable when implementing addition trees. Nevertheless, if there are multiplications in the datapath, the inputs to the multiplier must be reduced to a non-redundant form, to avoid applying the distributive property. In this paper we present a multiplier able to receive two numbers in partial carry-save format, and produce a result in partial carry-save format as well. This is done by modifying the Booth encoder and leveraging the generate and propagate group signals that are available because of the partial carry-save format. Hence, this can allow to fully implement datapaths without additional penalty cycles due to reductions to non-redundant forms. Experiments show that our proposed multiplier has 15 percent shorter delay with respect to a conventional Booth radix-4 multiplier. Moreover, when combining it with partial carry-save adders it is possible to reduce 36 percent execution time on average for several benchmarks, achieving a 32.7 percent reduction in the Energy Delay Product at the same time. [ABSTRACT FROM AUTHOR]

In network on chips (NoCs) design, reconfiguration of NoC is a very effective option for minimizing power consumption, and Gaussian networks can provide significant advantage over the mesh networks in terms of network diameter, average hop distance and so on. In this paper, based on the special topology structure and the static connection rules within Gaussian networks, we present the reconfiguration representation for Gaussian networks and the nature of reconfigurable Gaussian networks. Furthermore, reconfigurable rules of Gaussian networks are proposed to design the constraints for automatic reconfiguration of NoC. [ABSTRACT FROM PUBLISHER]

Architecting PCM, especially MLC PCM, as main memory for MCUs is a promising technique to replace conventional DRAM deployment. However, PCM/MLC PCM suffers from long write latency and large write energy. Recent work has proposed a compiler directed dual-write (CDDW) scheme to combat the drawbacks of PCM by adopting fast or slow mode for different write operations. For large-scale loops, we observe that write instances' lifetime is very long and can only be written by the expensive slow mode. This paper proposes a write mode aware loop tiling approach to effectively reduce the lifetime of write instances and maximize the number of efficient fast writes in loops. The experimental results show that the proposed approach improves performance by 50.8 percent and reduces dynamic energy by 32.0 percent across a set of benchmarks compared to the CDDW approach on average. [ABSTRACT FROM AUTHOR]

Scratchpad memories in GPU architectures are employed as software-controlled caches to increase the effective GPU memory bandwidth. Through the use of well-known optimization techniques, such as privatization and tiling, they are properly exploited. Typically, they are banked memories which are addressed with a \textmod(2^N) bank indexing scheme. Although their bandwidth is fully exploited for linear memory accesses, their performance is burdened when non-unit strides appear in memory access patterns because they provoke bank conflicts. This paper explores the use of configurable bit-vector and bitwise XOR-based hash functions to evenly distribute memory addresses of the access patterns over the memory banks, reducing the number of bank conflicts. An exhaustive, but lightweight, search is used to configure bit-vector hash functions. Bitwise hash functions are configured with heuristics. Hardware and software implementations are carried out. For the hardware approach, the experimental results show 24 percent performance speed-up for 22 benchmarks on GPGPU-Sim, a Fermi-like simulator. Bank conflicts are reduced by 96 percent with bit-vector hash functions, and 97 percent with bitwise hash functions using our proposed Minimum Imbalance Heuristic. The software approach, using bit-vector hash functions, demonstrates 23 percent speed-up and 96 percent bank conflict reduction on a Fermi GPU, and 33 percent speed-up and 99 percent bank conflict reduction on a Kepler GPU. [ABSTRACT FROM AUTHOR]

Fairness is an important property of computer networks and systems. In a wide range of these systems such as distributed multi-hop wireless networks, multihomed networks, and cloud computing, each user may be allocated a number of system resources; this resembles a many-to-many relationship between the sets of users and resources, which raises the problem of system-wide fair resource allocation. In this paper, we assume that each user/node can be allocated a number of resources, which could be either in its neighborhood or far from it. As a key difference with previous works and through incorporating the concept of “flow”, we model near/far resources allocated to nodes. To attain fair flow control in such systems, first we model this situation by introducing a new multi-server system called multi-ring, in which a server that represents a resource, can serve only a subset of either neighboring or far nodes in the system. Then, we define a centralized optimization problem to attain weighted proportional fairness among all nodes meaning that the sum of allocated capacities from all servers to each node (while considering its flow) is fair. We evaluate fairness properties of multi-ring networks and provide conditions on system parameters under which a system can have a fair resource allocation. Moreover, we present a distributed method to attain fairness in distributed environments, and its stability/convergence is evaluated by non-linear discrete dynamical systems. We present conditions under which the system is stable, and through numerical analysis, we show how to obtain stable system parameters for large systems. The effectiveness of the presented method is studied through extensive numerical evaluation. Results show the success of our method in attaining fairness for various topologies and system parameters, and confirm our stability analysis. A number of systems with fairness issues are also studied as potential applications of our model. [ABSTRACT FROM AUTHOR]

Multi-channel wireless data broadcast is an appropriate approach to disseminate data to a mass number of mobile clients. In this paper, we present a global optimization for multi-channel wireless data broadcast with Alphabetic Huffman Tree (AH-Tree) Indexing scheme, which can deal with skewed access frequencies well. We present three novel designs to reduce the access latency and tuning time of the broadcast system. Firstly, we design a dynamic programming for AH-Tree construction with low time complexity. Compared with traditional Hu-Tucker algorithm in $O(n^k)$ , our algorithm can build a $k$ -ary AH-Tree index in $O(n^2)$ . Next, we depict a new control table design, which eliminates up to 50 percent redundant entries while keeps the searching efficiency. We also theoretically prove that an optimal alphabetic tree has the minimum average tuning time among all tree-based index structures for skewed data broadcast. Thirdly, we design the new index and data allocation algorithms to further reduce the tuning time and access latency. The simulation results validate the effectiveness of our algorithms. In all, our global optimization mechanism can greatly improve the system performance and time efficiency for wireless data broadcast applications. [ABSTRACT FROM AUTHOR]

As a result of huge advancements in VLSI technology, more and more complex circuits are being implemented making not only the whole digital system more prone to faults, but also the fault detector itself susceptible to faults resulting in the requirement of concurrent fault detection architecture of the encoders and decoders. In this paper, we present a multiple-bit parity-based fault detection architecture for parallel CRC computation. After analyzing the parallel implementation of CRC, we present a formulation to generate a multiple-bit parity prediction structure to incorporate the fault detection architecture. Using the formulations of digit level CRC architecture, the checksum is divided into few blocks and predicted multiple-bit parity of the blocks are compared with the actual parity bits. Finally, with the help of software simulation and ASIC implementation, we show that the proposed scheme is highly efficient in terms of fault detection capability whereas it involves small area and time overhead. As an example, we have shown that the worst case area overhead is $25.7$ percent for CRC $-32$ with four parity bits, and corresponding time overhead is $15.6$ percent. [ABSTRACT FROM PUBLISHER]

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]

Networks-on-chip (NoCs) have been increasingly adopted in recent years due to the extensive integration of many components in modern multicore processors and system-on-chip designs. At the same time, transistor reliability is becoming a major concern due to the continuous scaling of silicon. As the sole medium of on-chip communication, it is critical for a NoC to be able to tolerate many permanent transistor failures. In this paper, we propose uDIREC, a unified framework for permanent fault diagnosis and subsequent reconfiguration in NoCs, which provides graceful performance degradation with an increasing number of faults. Upon in-field transistor failures, uDIREC leverages a fine-resolution diagnosis mechanism to disable faulty components very sparingly. At its core, uDIREC employs MOUNT, a novel routing algorithm to find reliable and deadlock-free routes that utilize all the still-functional links in the NoC. We implement uDIREC's reconfiguration as a truly-distributed hardware solution, still keeping the area overhead at a minimum. We also propose a software-implemented reconfiguration that provides greater integration with our software-based diagnosis scheme, at the cost of distributed nature of implementation. Regardless of the adopted implementation scheme, uDIREC places no restriction on topology, router architecture and number and location of faults. Experimental results show that uDIREC, implemented in a 64-node NoC, drops 3 $\times$ fewer nodes and provides greater than 25 percent throughput improvement (beyond 15 faults) when compared to other state-of-the-art fault-tolerance solutions. uDIREC's improvement over prior-art grows further with more faults, making it a effective NoC reliability solution for a wide range of fault rates. [ABSTRACT FROM AUTHOR]

Phase-change memory (PCM) has emerged as a candidate that overcomes the physical limitations faced by DRAM and NAND flash memory. While PCM has desirable properties in terms of scalability and density, it suffers from limited endurance. Repeated writes cause PCM cells to wear out and get permanently stuck at a specific value. Recovering from stuck-at faults through a proactive error correcting scheme is essential for the widespread adoption of PCM. In this paper, we propose Symbol Shifting as a practical technique to increase the number of faults that an error correcting code can cover in single and multilevel cells memory chips. Since stuck-at cells can still be read, errors are manifested only when a worn-out cell is to be programmed with a symbol value different than the value it is stuck at. After a write operation fails for a given block of data, another write operation is attempted with all original data symbols shifted to another memory level. Shifting the data is likely to bring the number of errors within the nominal capability of the deployed error correcting code. Requiring only one additional auxiliary cell, Symbol Shifting can increase the number of faults that an error correcting code can cover by up to double the nominal capability and extends the lifetime by up to 37 percent. [ABSTRACT FROM AUTHOR]

The non-volatile memory (NVM) which can provide DRAM-like performance and disk-like persistency has the potential to build single-level systems by replacing both DRAM and disk. Keeping data consistency in such systems is non-trivial because memory writes may be reordered by CPU. Although ordered memory writes for achieving data consistency can be implemented using the memory fence and the CPU cache line flush instructions, they introduce a significant overhead (more than 10X slower in performance). In this paper, we focus on an important and common data structure, B $^+$ Tree. Based on our quantitative analysis for consistent tree structures, we propose NV-Tree, a consistent, cache-optimized and workload-adaptive B $^+$ Tree variant with significantly reduced consistency cost (up to 96 percent reduction in CPU cache line flush). To further optimize NV-Tree under various workloads, we propose a workload-adaptive scheme in which the sizes of individual nodes can be dynamically adjusted to improve the performance over time. We implement and evaluate NV-Tree and NV-Store, a key-value store based on NV-Tree, on an NVDIMM server. NV-Tree outperforms the state-of-art consistent tree structures by up to 12X under write-intensive workloads. NV-Store increases the throughput by up to 7.3X under YCSB workloads compared to Redis. [ABSTRACT FROM AUTHOR]

In modern SoCs embedded memories should be protected by ECC against field failures to achieve acceptable reliability. They should also be repaired after fabrication to achieve acceptable fabrication yield. In technologies affected by high defect densities, conventional repair induces very high costs. To reduce it, we can use ECC-based repair, consisting in using the ECC for fixing words comprising a single faulty cell and self-repair to fix all other faulty words. However, as we show in this paper, for high defect densities the diagnosis circuitry required for ECC-based repair may induce very large hardware cost. To fix this issue, we introduce a new family of memory test algorithms that exhibit a property we termed as “single-read double-fault detection”. This approach gains interest in ultimate CMOS and post-CMOS technologies, where the defect densities are expected to increase significantly, and/or in very-low power design, as very-low voltage sharply increases defect densities. [ABSTRACT FROM PUBLISHER]

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]

Given a chip that produced a faulty output response to a test set, a defect diagnosis procedure produces a set of candidate faults that is expected to identify the defects that are present in the chip. The accuracy of the set of candidate faults is higher when the set is smaller or when its overlap with the defects that are present in the chip is larger. To increase the accuracy of a set of candidate faults, this paper describes an approach where several sets of candidate faults are computed based on different subsets of the test set. The subsets are obtained by removing small numbers of tests from the complete test set. The result is sets of candidate faults that are similar but not identical. The number of sets where a fault appears yields a confidence level that the fault actually belongs in a set of candidate faults. New sets of candidate faults are defined based on the confidence levels obtained. The smallest set of candidate faults can be used as the final result of defect diagnosis, or the sets can be used for ranking the candidates. Experimental results for benchmark circuits demonstrate the effectiveness of this approach. [ABSTRACT FROM PUBLISHER]

While Generalized Feistel Networks (GFNs) have been widely studied in the literature as a building block of a block cipher, we recall in this paper the results of [1] where a unified vision to easily represent them through a matrix representation is proposed. We also introduce a new class of such schemes called Extended Generalized Feistel Networks well suited for cryptographic applications. We instantiate this particular construction into a lightweight block cipher called Lilliput analyzing its security and its hardware performances. [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]

This paper introduces a systematic approach to designing high-performance parallel adders based on Counter Tree Diagrams (CTDs). By using CTDs, we can describe addition algorithms at various levels of abstraction. A high-level CTD represents a network of coarse-grained components associated with word-level operands, whereas a low-level CTD represents a network of primitive components that can be directly mapped onto physical devices. The level of abstraction in circuit representation can be changed by decomposition of CTDs. We can derive possible variations of adder structures by decomposing a high-level CTD into low-level CTDs in a formal manner. In this paper, we focus on an application of CTDs to the design of redundant arithmetic adders with limited carry propagation. For any redundant number representation, we can obtain the optimal adder structure by trying every possible CTD decomposition and CTD variable encoding. The potential of the proposed approach is demonstrated through an experimental synthesis of Redundant-Binary (RB) adders with CMOS standard cell libraries. We can successfully obtain RB adders that achieve an about 30-40 percent improvement in terms of power-delay product compared with conventional designs. [ABSTRACT FROM AUTHOR]

Efficient exact schedulability tests are required both for online admission of applications to dynamic systems and as an integral part of design tools for complex distributed real-time systems. This paper addresses performance issues with exact response time analysis (RTA) for fixed priority preemptive systems. Initial values are introduced that improve the efficiency of the standard RTA algorithm 1) when exact response times are required and 2) when only exact schedulability need be determined. This paper also explores modifications to the standard RTA algorithm, including the use of a response time upper bound to determine when exact analysis is needed, incremental computation aimed at faster convergence, and checking tasks in reverse priority order to identify unschedulable tasksets early. The various initial values and algorithm implementations are compared by means of experiments on a PC recording the number of iterations required and execution time measurements on a real-time embedded microprocessor. Recommendations are provided for engineers tasked with the problem of implementing exact schedulability tests as part of online acceptance tests and spare capacity allocation algorithms or as part of offline system design tools. [ABSTRACT FROM AUTHOR]

This paper compares the System Performance Evaluation Cooperative (SPEC) Integer and Floating-Point suites to a set of real-world applications for high-performance computing at Sandia National Laboratories. These applications focus on the high-end scientific and engineering domains; however, the techniques presented in this paper are applicable to any application domain. The applications are compared in terms of three memory properties: 1) temporal locality (or reuse overtime), 2) spatial locality (or the use of data ‘near’ data that has already been accessed), and 3) data intensiveness (or the number of unique bytes the application accesses). The results show that real-world applications exhibit significantly less spatial locality, often exhibit less temporal locality, and have much larger data sets than the SPEC benchmark suite. They further quantitatively demonstrate the memory properties of real supercomputing applications. [ABSTRACT FROM AUTHOR]

Grid computing is a newly emerging technology aimed at large-scale resource sharing and global-area collaboration. It is the next step in the evolution of parallel and distributed computing. Due to the largeness and complexity of the grid system, its performance and reliability are difficult to model, analyze, and evaluate. This paper presents a model that relaxes some assumptions made in prior research on distributed systems that were inappropriate for grid computing. The paper proposes a virtual tree-structured model of the grid service. This model simplifies the physical structure of a grid service, allows service performance (execution time) to be efficiently evaluated, and takes into account data dependence and failure correlation. Based on the model, an algorithm for evaluating the grid service time distribution and the service reliability indices is suggested. The algorithm is based on Graph theory and probability theory. Illustrative examples and a real case study of the BioGrid are presented. [ABSTRACT FROM AUTHOR]

As the demand for high-quality Internet increases, emerging network applications are spurring the need for faster, feature-rich, and cost-effective routers. Multifield packet classification in routers has been a computation-intensive data path function for software implementation. Therefore, solutions for packet classification based on hardware design, such as Ternary Content Addressable Memory (TCAM), are necessary to sustain gigabit line processing rate. Traditionally, TCAMs have been designed for storing prefixes. However, multifield packet classification usually involves two fields of arbitrary ranges that are TCP/IP layer 4 source and destination ports. Storing ranges in TCAMs relies on decomposing each individual range into multiple prefixes, which leads to range-to-prefix blowout. To reduce the total number of prefixes needed to represent all ranges, this paper proposes a 2-level TCAM architecture and two range-to-prefix conversion schemes. In the first proposed scheme, designed for disjoint ranges, the maximum number of entries needed in TCAM is 2m - 1 for m disjoint ranges. In the second proposed scheme, designed for contiguous ranges, only m TCAM entries are needed. In a general case of n arbitrary ranges, all ranges can first be converted into disjoint ranges or contiguous ranges and then the proposed algorithms can be applied. As a result, only 4n - 3 TCAM entries are needed for the disjoint ranges and only 2n + 1 TCAM entries are needed for contiguous ranges. This paper also proposes insertion and deletion algorithms to accommodate incremental changes to the range sets. The experiments made show that the proposed range-to-prefix conversion schemes perform better than the existing schemes in terms of the number of required TCAM entries and execution time for range update operations. [ABSTRACT FROM AUTHOR]

In ad hoc wireless networks, to compute the transmission power of each wireless node such that the resulting network is connected and the total energy consumption is minimized is defined as a Minimum Energy Network Connectivity (MENC) problem, which is an NP-complete problem. In this paper, we consider the approximated solutions for the MENC problem in ad hoc wireless networks. We present a theorem that reveals the relation between the energy consumption of an optimal solution and that of a spanning tree and propose an optimization algorithm that can improve the result of any spanning tree-based topology. Two polynomial time approximation heuristics are provided in the paper that can be used to compute the power assignment of wireless nodes in both static and low mobility ad hoc wireless networks. The two heuristics are implemented and the numerical results verify the theoretical analysis. [ABSTRACT FROM AUTHOR]

Wearable computing has recently gained much popularity as an ambitious vision for future personalized mobile systems. Its aim is intelligent, environment aware systems unobtrusively embedded into the mobile environments of their users. With the combination of complex processing requirements, the necessity of placing sensors and input/output modules at different locations on the user's body, and stringent limits on size, weight, and battery capacity, the design of such systems is an inherently challenging problem. This paper demonstrates how systematic design and quantitative analysis can be applied to wearable architectures. We first present a model that allows various factors influencing the design of a wearable system to be incorporated into formal cost metrics. In particular, we show how to consistently incorporate specific wearable factors such as device placement requirements, ergonomics, and dynamic workload profiles into the model. We then discuss how efficient estimation algorithms can be extended and applied to the evaluation of different architectures with respect to our cost metrics. Finally, we discuss quantitative results from a proof-of-concept case study showing the trade offs between different architectures for a given wearable scenario. Summarized, this paper demonstrates how the description and the design of wearable systems can be put on a systematic, formal basis allowing us to treat them similar as conventional embedded systems. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of characterizing and exploiting the complete flexibility of a special logic architecture, called P-circuits, which realize a Boolean function by projecting it onto overlapping subsets given by a generalized Shannon decomposition. P-circuits are used to restructure logic by pushing some signals towards the outputs. The algorithms proposed so far for exploiting the structural flexibility of P-circuits do not guarantee to find the best implementation, because they cast the problem as the minimization of an incompletely specified function. Instead, here we show that to explore all solutions we must set up the problem as the minimization of a Boolean relation, because there are don’t care conditions that cannot be expressed by single cubes. Finally we report the results obtained using a minimizer of Boolean relations, which improve in a major way with respect to the previous literature. [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]

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]

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]

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]

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]

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]

In testing from a Finite State Machine (FSM), the generation of test suites which guarantee full fault detection, known as complete test suites, has been a long-standing research topic. In this paper, we present conditions that are sufficient for a test suite to be complete. We demonstrate that the existing conditions are special cases of the proposed ones. An algorithm that checks whether a given test suite is complete is given. The experimental results show that the algorithm can be used for relatively large FSMs and test suites. [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]

In this paper, we study the upper bounds of memory storage for two different allocators. In the first case, we consider a general allocator that can allocate memory blocks anywhere in the available heap space. In the second case, a more economical allocator constrained by the address-ordered first-fit allocation policy is considered. We derive the upper bound of memory usage for all allocators and present a systematic approach to search for allocation/deallocation patterns that might lead to the largest fragmentation. These results are beneficial in embedded systems where memory usage must be reduced and predictable because of lack of swapping facility. They are also useful in other types of computing systems. [ABSTRACT FROM AUTHOR]

Preventing silicon chips from negative, even disastrous thermal hazards has become increasingly challenging these days; Considering thermal effects early in the design cycle is thus required. To achieve this, an accurate yet fast temperature model together with an early-stage, thermally optimized, design flow are needed. In this paper, we present an improved block-based compact thermal model (HotSpot 4.0) that automatically achieves good accuracy even under extreme conditions. The model has been extensively validated with detailed finite-element thermal simulation tools. We also show that properly modeling package components and applying the right boundary conditions are crucial to making full-chip thermal models like HotSpot accurately resemble what happens in the real world. Ignoring or oversimplifying package components can lead to inaccurate temperature estimations and potential thermal hazards that are costly to fix in later design stages. Such a full-chip and package thermal model can then be incorporated into a thermally optimized design flow, where it acts as an efficient communication medium among computer architects, circuit designers, and package designers in early microprocessor design stages to achieve early and accurate design decisions and also faster design convergence. For example, the temperature-leakage interaction can be readily analyzed within such a design flow to predict potential thermal hazards such as thermal runaway. An example SoC design illustrates the importance of adopting such a thermally optimized design flow in early design stages. [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]