IEEE Transactions on Computers

PrePrint: An Interacting Stochastic Models Approach for the Performance Evaluation of DSRC Vehicular Safety Communication

In this paper, an analytic model is proposed for the performance evaluation of vehicular safety related services in the dedicated short range communications (DSRC) system on highways. The generation and service of safety messages in each vehicle is modeled by a generalized M/G/1 queue. The overall model is a set of interacting M/G/1 queues, one queue for each vehicle. The interaction is that the server is shared as it is the contention medium. To make the model scalable, we use semi-Markov process (SMP) model to capture the shared server's behavior from one tagged vehicle's perspective, where the medium contention and backoff behavior for this vehicle and influences from other vehicles are considered. Furthermore, this SMP interacts with the tagged vehicle's own M/G/1 queue through fixed-point iteration. The proof for the existence, uniqueness and convergence of the fixed point is provided. Based on the fixed-point solution, performance indices including mean transmission delay, packet delivery ratio (PDR) and packet reception ratio (PRR) are derived. Analytic-numeric results are verified through extensive simulations under various network parameters. Compared with the existing models, the proposed SMP model facilitates the impact analysis of hidden terminal problem on the PDR and PRR computation in a more precise manner.

PrePrint: Generalizing the Square Root Rule for Optimal Periodic Scheduling in Push-based Wireless Environments

The present work proposes a generalization of the square root rule for optimal periodic scheduling. The rule defines a ratio of item occurrences in a schedule, which minimizes the mean serving time. However, the actual number of each item's occurrences must be an integer. Therefore, the square root rule assumes large schedules, in order for the ratio to hold with acceptable precision. The present work introduces an analysis-derived formula which connects the mean serving time and the size of the schedule. The relation shows that small schedules can also achieve near-optimal serving times. The analysis is validated through comparison with brute force-derived solutions. Finally, it is shown that minimizing the size of the schedule is also an efficient way of optimizing the aggregate scheduling cost.

PrePrint: High Performance Hardware Implementation for RC4 Stream Cipher

RC4 is the most popular stream cipher in the domain of cryptology. In this paper, we present a systematic study of the hardware implementation of RC4, and propose the fastest known architecture for the cipher. We combine the ideas of hardware pipeline and loop unrolling to design an architecture that produces 2 RC4 keystream bytes per clock cycle. We have optimized and implemented our proposed design using VHDL description, synthesized with 130 nm, 90 nm and 65 nm fabrication technologies at clock frequencies 625 MHz, 1.37 GHz and 1.92 GHz respectively, to obtain a final RC4 keystream throughput of 10 Gbps, 21.92 Gbps and 30.72 Gbps in the respective technologies.

PrePrint: Conditional Diagnosability of Alternating Group Graphs

Let $A_n$ be the alternating group of degree $n$ with $n\geq 3$. Set $S=\{(1\ 2\ i), (1\ i\ 2)\ $ $|\ 3\leq i\leq n\}$. The {\em alternating group graph}, denoted by $AG_n$, is defined as the Cayley graph on $A_n$ with respect to $S$. Jwo et al. [Networks 23 (1993) 315-326] introduced alternating group graph $AG_n$ as an interconnection network topology for computing systems. Conditional diagnosability, a new measure of diagnosability introduced by Lai et al. [IEEE Transactions on Computers 54(2) (2005) 165--175] can better measure the diagnosability of regular interconnection networks. This paper determines that under PMC-model the conditional diagnosability of $AG_n$ is $4$ for $n=4$ and $6n-18$ for each $n\geq 5$.

PrePrint: An Efficient Denoising Architecture for Removal of Impulse Noise in Images

Images are often corrupted by impulse noise in the procedures of image acquisition and transmission. In this paper, we propose an efficient denoising scheme and its VLSI architecture for the removal of random-valued impulse noise. To achieve the goal of low cost, a low-complexity VLSI architecture is proposed. We employ a decision-tree-based impulse noise detector to detect the noisy pixels, and an edge-preserving filter to reconstruct the intensity values of noisy pixels. Furthermore, an adaptive technology is used to enhance the effects of removal of impulse noise. Our extensive experimental results demonstrate that the proposed technique can obtain better performances in terms of both quantitative evaluation and visual quality than the previous lower-complexity methods. Moreover, the performance can be comparable to the higher-complexity methods. The VLSI architecture of our design yields a processing rate of about 200 MHz by using TSMC 0.18µm technology. Compared with the state-of-the-art techniques, this work can reduce memory storage by more than 99%. The design requires only low computational complexity and two line memory buffers. Its hardware cost is low and suitable to be applied to many real-time applications.

PrePrint: Preserving Temporal Relationships of Events for Wireless Sensor Actor Networks

In this paper, we present the performance evaluation of an algorithm for preserving temporal relationships of events in Wireless Sensor Actor Networks (WSANs). The algorithm consists of two modules, which deal with the problems of temporal event ordering and time synchronization. These two problems are approached as a whole as they complement each other: in order to temporally order the events, the nodes must be synchronized. The goal of the proposed event ordering algorithm for WSANs is to reduce the overhead in terms of energy dissipation and delay. We also propose a tunable time synchronization algorithm employing a hybrid synchronization scheme suited for clustered topology. The proposed algorithm utilizes the message exchange necessary for event ordering and routing for synchronization purposes by piggybacking messages with synchronization pulses and replies to reduce the communication cost of synchronization. Simulation experiments showed that the event ordering algorithm is capable of reducing the overhead when compared to previously proposed algorithms. The synchronization algorithm demonstrated that the combination of synchronization techniques was well suited for the communication mode utilized in a clustered topology. The approach of piggybacking synchronization pulses and replies resulted in a considerable gain, which we demonstrated in the number of messages that were piggybacked for synchronization purposes.

PrePrint: Testing and Diagnosing Comparison Faults of TCAMs with Asymmetric Cells

This paper presents several comparison fault models of TCAMs with asymmetric cells based on electrical defects. One march-like test algorithm TAC-H is also proposed to cover the defined comparison faults. The TAC-H consists of 8N Write operations and (3N +2B) Compare operations for an N×B-bit TCAM with Hit output only. We also propose two march-like diagnosis algorithms to identify the defined comparison faults of TCAMs with asymmetric cells. The first diagnosis algorithm DAC-H requires 5N Write operations, 3N Erase operations, and (5N +2B) Compare operations to distinguish 100% comparison faults for a TCAM with Hit output only. The second diagnosis algorithm DAC-P requires 3N Write operations, 1N Erase operations, and (5N +2B) Compare operations to distinguish 100% comparison faults for a TCAM with Hit and priority address encoder outputs.

PrePrint: Power and Delay Aware Management of Packet Switches

Due to increasing circuit densities and data throughput rates, power consumption has become a significant concern in the design and operation of high-performance packet switches. We extend the idea of Dynamic Power Management (DPM) to input queued switches, allowing operators to tradeoff power and delay in a useful way. We frame the problem as a dynamic program and solve a relaxation using techniques from Linear Quadratic Regulation (LQR). This optimal policy is combined with existing, non-power-aware switch controls to generate two novel scheduling algorithms: (a) LQR Power Aware Maximum Weight Matching (LQR PA MWM) and (b) LQR Power Aware Projective Cone Scheduling (LQR PA PCS). Simulation results suggest that our algorithms result in significant power savings compared to MWM and previous power control schemes with little performance degradation.

PrePrint: Variability-Aware Task Allocation for Energy-Efficient Quality of Service Provisioning in Embedded Streaming Multimedia Applications

Multimedia streaming applications running on next-generation parallel multiprocessor arrays in sub-45nm technology face new challenges related to device and process variability, leading to performance and power variations across the cores. In this context, Quality of Service (QoS), as well as energy efficiency, could be severely impacted by variability. In this work we propose a run-time variability-aware workload distribution technique for enhancing real-time predictability and energy efficiency based on an innovative Linear-Programming + Bin-Packing formulation which can be solved in linear time. We demonstrate our approach on the virtual prototype of a next-generation industrial multi-core platform running a multithread MPEG2 decoder. Experimental results confirm that our technique compensates variability, while improving energy-efficiency and minimizing deadline violations in presence of performance and power variations across the cores.

PrePrint: vCUDA: GPU-Accelerated High-Performance Computing in Virtual Machines

This paper describes vCUDA, a general-purpose graphics processing unit (GPGPU) computing solution for virtual machines (VMs). vCUDA allows applications executing within VMs to leverage hardware acceleration, which can be beneficial to the performance of a class of high-performance computing (HPC) applications. The key insights in our design include API call interception and redirection and a dedicated RPC system for VMs. With API interception and redirection, Compute Unified Device Architecture (CUDA) applications in VMs can access a graphics hardware device and achieve high computing performance in a transparent way. In the current study, vCUDA achieved a near-native performance with the dedicated RPC system. We carried out a detailed analysis of the performance of our framework. Using a number of unmodified official examples from CUDA SDK and third-party applications in the evaluation, we observed that CUDA applications running with vCUDA exhibited a very low performance penalty in comparison with the native environment, thereby demonstrating the viability of vCUDA architecture.

PrePrint: Comments on "Provably Sublinear Point Multiplication on Koblitz Curves and Its Hardware Implementation"

In 2008, Dimitrov et al. proposed a point multiplication algorithm on Koblitz curves using multiple-base expansions. They claimed that their algorithm is the first provably sublinear point multiplication algorithm on Koblitz curves. In this paper, we show that the well-known tau-adic NAF method is already sublinear and also guarantees a better average performance.

PrePrint: A Classified Multi-Suffix Trie for IP Lookup and Update

In this paper, a new data structure, called the classified multi-suffix trie (CMST), is proposed for designing dynamic router-tables. CMST achieves a better performance than existing data structures because each node can store more than one prefix and the longest matching prefix may be found in an internal node rather than on a leaf. Furthermore, with the classification in each node, the dynamic router-table operations can be performed efficiently. To reduce the memory requirement, we store each prefix's corresponding suffix in a CMST node, instead of storing a full binary string. Experiments using real IPv4 routing databases demonstrate that the proposed data structure is efficient in terms of memory usage and it performs well in terms of the lookup, insert and delete operations. We report the results of experiments conducted to compare the performance of the proposed data structure with that of other structures using the benchmark IPv4 prefix databases AS4637, AS6447, and AS65000 with 219,581, 296,552, and 226,847 prefixes respectively.

PrePrint: New Design For Testability Approach for Clock Fault Testing

We propose a new design for testability approach for testing clock faults of next generation high performance microprocessors. In fact, it has been shown that conventional manufacturing test is unable to guarantee their detection, although they could compromise the effectiveness of delay fault testing, as well as the microprocessor correct operation in the field. These conditions will of course worsen with technology scaling, due to the expected increase in fault likelihood, included clock faults. To deal with these problems we propose a new design for testability approach that, by means of simple modifications to conventional clock buffers, allows clock fault detection through any conventional manufacturing test approach. This is achieved at the cost of very low increase in area and power consumption of clock buffers, and with no additional test cost or impact on the microprocessor performance and infield operation. We then introduce a possible further modification to clock buffers that, at additional limited cost allows their calibration after fabrication in order to compensate for parameter variations possibly occurring during manufacturing, thus minimizing the likelihood of either false test fails, or test misses. We show the application of our approach to the clock network of the Pentium 4 microprocessor.

PrePrint: Minimizing Eavesdropping Risk by Transmission Power Control in Multihop Wireless Networks

To defend against reconnaissance activity in adhoc wireless networks, we propose transmission power control as an effective mechanism for minimizing the eavesdropping risk. Our main contributions are as follows: First, we cast the w-th order eavesdropping risk as the maximum probability of packets being eavesdropped when there are w adversarial nodes in the network. Second, we derive the closed-form solution of the first order eavesdropping risk as a polynomial function of the normalized transmission radius. This derivation assumes a uniform distribution of user nodes. Then we generalize the model to allow arbitrary user nodes distribution and prove that the uniform user distribution minimizes the first order eavesdropping risk. This result plays an essential role in deriving analytical bounds for the eavesdropping risk given arbitrary user distributions. Our simulation results show that for a wide range of non-uniform traffic patterns, the difference of their eavesdropping risk values from the corresponding lower bounds is 3dB or less.

PrePrint: Performance-Driven Load Balancing with Primary-Backup Approach for Computational Grids with Low Communication Cost and Replication Cost

Computational grids provide a massive source of processing power, providing the means to support processor intensive applications. The strong burstiness and unpredictability of the available resources raise the need to make applications robust against the dynamics of grid environment. The two main techniques that are most suitable to cope with the dynamic nature of the grid are load balancing and job replication. In this work, we develop a load balancing algorithm by juxtaposes the strong points of neighbour-based and cluster-based load balancing methods. We then integrate the proposed load balancing approach with fault-tolerant scheduling namely MinRC and develop a performance-driven fault-tolerant load balancing algorithm or PD_MinRC for independent jobs. In order to improve system flexibility, reliability and save system resource, PD_MinRC employs passive replication scheme. Our main objective is to arrive at job assignments that could achieve minimum response time, maximum resource utilization and a well balanced load across all the resources involved in a grid. Experiments were conducted to show the applicability of PD_MinRC. One advantage of our approach is the relatively low overhead and robust performance against resource failures and inaccuracies in performance prediction information.

PrePrint: A Memory Efficient Tables-and-Additions Method for Accurate Computation of Elementary Functions

The tables-and-additions methods for accurate computation of elementary functions are fast in computation speed but require large memory. A memory efficient method named as the integrated Add-Table Lookup-Add (iATA) is proposed in this paper. In iATA, the mathematical formulation for computing the elementary functions is derived without using the central difference formulation to save memory. Three additional techniques, specifically the carry select technique, symmetry property exploitation and unequal partitioning of input with the aid of error analysis, are integrated in iATA to further reduce the memory size. The experimental results show that the proposed method is able to achieve higher memory efficiency than the best existing tables-and-additions methods. For the reciprocal and the natural logarithm function, iATA saves 23.63% and 61.39% of memory when compared to the best existing results obtained respectively by the unified Multipartite Table Method [39] and the Symmetric Table Addition Method [37].

PrePrint: Hardware-Based Generation of Independent Subtraces of Instructions in Clustered Processors

Multicore chips are currently dominating the microprocessor market as designs that improve performance and sustain power consumption. However, complex core features must be still considered to provide good performance for existing sequential applications. An effective approach to reduce core complexity without dramatically sacrificing performance is to distribute critical processor structures by using clustered microarchitectures. In these designs, communication latency among clusters is a critical performance bottleneck, and a good steering algorithm is required to reduce inter-cluster communication. In this paper, we propose a new energy-efficient microarchitectural approach that reduces inter-cluster communication by detecting and generating independent chains of instructions, referred to as subtraces, from the execution of sequential programs. The devised mechanism has been modeled on an x86-based trace-cache processor, where subtraces are built in the fill unit, stored in a trace cache, and individually steered to different clusters. Experimental results show that the proposal reaches performance speedups around 7% and 15% for point-to-point and bus-based interconnects, respectively, while achieving energy savings of up to 12%.

PrePrint: SEED: A Statically-Greedy and Dynamically-Adaptive Approach for Speculative Loop Execution

This paper introduces a SEED (Statically GrEEdy and Dynamically Adaptive) approach for thread-level speculation on loops that is quite different from most other existing techniques. SEED relies on the compiler to select and optimize loop candidates greedily (possibly in an input-independent way) and provides a runtime scheduler to schedule loop iterations adaptively. To select loops for parallelization at run time (subject to program inputs), loop iterations are prioritized in terms of their potential benefits rather than their degree of speculation as in many prior studies. In our current implementation, the benefits of speculative threads are estimated by a simple yet effective cost model. It comprises a mechanism for efficiently tracing the loop nesting structures of the program and a mechanism for predicting the outcome of speculative threads. We have evaluated SEED using a set of SPECint2000 and Olden benchmarks. Compared to existing techniques with a program's loop candidates being ideally selected a priori, SEED can achieve comparable or better performance while aututomating the entire loop candidate selection process.

PrePrint: Computation and Formal Verification of SRT Quotient and Square Root Digit Selection Tables

We present a comprehensive, self-contained, and mechanically verified proof of correctness of a maximally redundant SRT design for floating-point division and square root extraction, supported by verified procedures that (a) test the admissibility of a proposed digit selection table, (b) determine the minimal dimensions of an admissible table for a given arbitrary radix, and (c) generate these tables. For square root extraction, we also provide a verified procedure for generating an initial approximation that meets the accuracy requirement of the algorithm and also ensures that the digit selection index derived from successive partial roots remains static throughout the computation. A radix-8 instantiation of these algorithms has been implemented in the floating-point unit of the AMD processor code-named Steamroller. To ensure their correctness, all of our results and procedures have been formalized and mechanically checked by the ACL2 prover. We present evidence of the value of this approach by comparing it to that of a more conventional published paper that reports similar results, which are shown to be fatally flawed.

PrePrint: Least-Latency Routing over Time-Dependent Wireless Sensor Networks

We consider the problem of least-latency end-to-end routing over adaptively duty-cycled wireless sensor networks. Such networks exhibit a time-dependent feature, where the link cost and transmission latency from one node to other nodes vary constantly in different discrete time moments. We model the problem as time-dependent Bellman-Ford problem. We show that such networks satisfy the FIFO property, which makes the time-dependent Bellman-Ford problem solvable in polynomial-time. Using the $\beta$-synchronizer, we propose a fast distributed algorithm to construct all-to-one shortest paths with polynomial message complexity and time complexity. The algorithm determines the shortest paths for all discrete times in a single execution, in contrast with multiple executions needed by previous solutions. We further propose an efficient distributed algorithm for time-dependent shortest path maintenance. The proposed algorithm is loop-free with low message complexity and low space complexity of $O(maxdeg)$, where $maxdeg$ is the maximum degree for all nodes. We also discuss a sub-optimal implementation of our proposed algorithms to reduce the memory requirement. The performance of our algorithms are experimentally evaluated under diverse network configurations. The results reveal that our algorithms are more efficient than previous solutions in terms of message cost and space cost.

PrePrint: High Speed Parallel Decimal Multiplication with Redundant Internal Encodings

The decimal multiplication is one of the most important decimal arithmetic operations which have a growing demand in the area of commercial, financial, and scientific computing. In this paper, we propose a parallel decimal multiplication algorithm with three components, which are a partial product generation, a partial product reduction, and a final digit-set conversion. First, a redundant number system is applied to recode not only the multiplier, but also multiples of the multiplicand in signed-digit (SD) numbers. Furthermore, we present a multi-operand SD addition algorithm to reduce the partial product array. Finally, a digit-set conversion algorithm with a hybrid prefix network to decrease the number of the logic gates on the critical path is discussed. An analysis of the timing delay and an HDL model synthesized under 90 nm technology show that by considering the trade-off of designs among three components, the overall delay of the proposed 16x16-digit multiplier takes about 11 percent less timing delay with 2 percent less area compared to the current fastest design.

PrePrint: SMT Malleability in IBM POWER5 and POWER6 Processors

While several hardware mechanisms have been proposed to control the interaction between hardware threads in an SMT processor, few have addressed the issue of software-controllable SMT performance. The IBM POWER5 and POWER6 are the first high-performance processors implementing a software-controllable hardware-thread prioritization mechanism that controls the rate at which each hardware-thread decodes instructions. This paper shows the potential of this basic mechanism to improve several target metrics for various applications on POWER5 and POWER6 processors. Our results show that although the software interface is exactly the same, the software-controlled priority mechanism has a different effect on POWER5 and POWER6. For instance, hardware-threads in POWER6 are less sensitive to priorities than in POWER5 due to the in order design. We study the SMT thread malleability to enable user-level optimizations that leverage software-controlled thread priorities. We also show how to achieve various system objectives such as parallel application load balancing, in order to reduce execution time. Finally, we characterize user-level transparent execution on POWER5 and POWER6, and identify the workload mix that best benefits from it.

PrePrint: mRT-PLRU: A General Framework for Real-Time Multi-Task Executions on NAND Flash Memory

This paper proposes a novel technique called "mRT-PLRU" (Multi-tasking Real-Time constrained combination of Pinning and LRU), which forms a generic framework to use inexpensive nonvolatile NAND flash memory for storing and executing real-time programs in multi-tasking environments. In order to execute multiple real-time tasks stored in NAND flash memory with the minimal usage of expensive RAM, the mRT-PLRU is optimally configured in two steps. In the first step, the "per-task analysis" finds the function of RAM size vs. execution time (and the corresponding optimal pinning/LRU combination) for each individual task. Using these functions for all the tasks as inputs, the second-step called a "stochastic-analysis-in-loop optimization" conducts an iterative convex optimization with the stochastic analysis for the probabilistic schedulability check. As a result, the optimization loop can optimally determine the RAM sizes for multiple tasks such that their deadlines are probabilistically guaranteed with the minimal size of total RAM. The usefulness of the developed technique is intensively verified through both simulation and actual implementation. Our experimental study shows that mRT-PLRU can save up to 80% of RAM required by the industry-common shadowing approach. industry-common shadowing approach.

PrePrint: Edge-Directed Hardware Architecture for Real-Time Disparity Map Computation

Stereo Vision, a technique aimed at inferring depth information from stereo images, has been used in a wide range of computer vision applications, with real-time requirements in emerging embedded vision systems. Computation of the disparity map, a vital step in extracting depth information from stereo images, requires a significant amount of computational resources. As such, existing software implementations require high-end hardware platforms to achieve real-time frame rates, suggesting that dedicated hardware mechanisms might be more suitable for embedded applications. In this paper, we present a disparity map computation architecture targeting embedded stereo vision applications with hard real-time requirements. The architecture integrates a hardware edge detection mechanism that reduces the search space, improving the overall performance, and is configurable in terms of various application parameters, making it suitable for a number of application environments. The paper also presents a study on the impact of the various parameters in terms of the performance and hardware/power overheads. An experimental prototype of the architecture was implemented on the Xilinx ML505 FPGA Evaluation Platform, achieving 50 frames per second for 1280x1024 image sizes. Moreover, the quality of the disparity maps generated by the proposed system is comparable to other existing hardware implementations featuring local correspondence methods.

PrePrint: DRINA: A Lightweight and Reliable Routing Approach for in-Network Aggregation in Wireless Sensor Networks

Large scale dense wireless sensor networks (WSNs) will be increasingly deployed in different classes of applications for accurate monitoring. Due to the high density of nodes in these networks, it is likely that redundant data will be detected by nearby nodes when sensing an event. Since energy conservation is a key issue in WSNs, data fusion and aggregation should be exploited in order to save energy. In this case, redundant data can be aggregated at intermediate nodes reducing the size and number of exchanged messages and, thus, decreasing communication costs and energy consumption. In this work we propose a novel Data Routing for In-Network Aggregation, called DRINA, that has some key aspects such as a reduced number of messages for setting up a routing tree, maximized number of overlapping routes, high aggregation rate, and reliable data aggregation and transmission. The proposed DRINA algorithm was extensively compared to two other known solutions: the InFRA and SPT algorithms. Our results indicate clearly that the routing tree built by DRINA provides the best aggregation quality when compared to these other algorithms. The obtained results show that our proposed solution outperforms these solutions in different scenarios and in different key aspects required by WSNs.

IEEE Transactions on Computers - March 2012 (Vol. 61, No. 3)

IEEE Transactions on Computers

PrePrint: Runtime Application Behavior Prediction Using a Statistical Metric Model

Adaptive computing systems rely on accurate predictions of application behavior to understand and respond to the dynamically-varying characteristics. In this study, we present a Statistical Metric Model (SMM) that is system- and metric--independent for predicting application behavior. SMM is a probability distribution over application patterns of varying length and it models how likely a specific behavior occurs. Maximum Likelihood Estimation (MLE) criterion is used to estimate the parameters of SMM. We also propose an extension to SMM (i.e. SMM-Interp) to handle sudden short-term changes in application behavior. SMM learns the application patterns during runtime, and at the same time predicts the upcoming application phases based on what it has learned up to that point. We demonstrate several key features of SMM: i) adaptation, ii) variable length sequence modeling and iii) long-term memory. An extensive and rigorous series of prediction experiments show the superior performance of the SMM predictor over existing predictors on a wide range of benchmarks. For some of the benchmarks, SMM reduces the prediction error rate by 10X and 3X, compared to last value and table-based prediction approaches respectively. SMM's improved prediction accuracy results in superior power-performance trade-offs when it is applied to an adaptive dynamic power management scheme.

PrePrint: Exploiting Application/System-dependent Ambient Temperature for Accurate Microarchitectural Simulation

In the early design stage of processors, Dynamic Thermal Management (DTM) schemes should be evaluated to avoid excessively high temperature, while minimizing performance overhead. In this paper, we show that conventional thermal simulations using the fixed ambient temperature may lead to the wrong conclusions in terms of temperature, performance, reliability, and leakage power. Though ambient temperature converges to a steady state value after hundreds of seconds when we run SPEC CPU2000 benchmark suite, the steady state ambient temperature is significantly different depending on applications and system configuration. To overcome inaccuracy of conventional thermal simulations, we propose that microarchitectural thermal simulations should exploit application/system-dependent ambient temperature. Our evaluation results reveal that performance, thermal behavior, reliability, and leakage power of the same DTM scheme are different when we use the application/system-dependent ambient temperature instead of the fixed ambient temperature. For accurate simulation results, future microarchitectural thermal researchers are expected to evaluate their proposed DTM schemes based on application/system-dependent ambient temperature.

PrePrint: Exploiting Cooperative Relay for High Performance Communications in MIMO Ad Hoc Networks

Multiple-input-multiple-output (MIMO) technology can provide significantly higher data rate in ad hoc networks where nodes are equipped with multi-antenna arrays. Although MIMO technique itself can support diversity transmission when channel condition degrades, the use of diversity transmission often compromises the multiplexing gain and is also not enough to deal with extremely weak channel. In this work, we exploit the use of cooperative relay transmission in a MIMO-based ad hoc network to cope with harsh channel condition. We design both centralized and distributed scheduling algorithms to support adaptive use of cooperative relay transmission when the direct transmission cannot be successfully performed. Our algorithm effectively exploits the cooperative multiplexing gain and cooperative diversity gain to achieve higher data rate and higher reliability under various channel conditions. Our scheduling scheme can efficiently invoke relay transmission without introducing significant signaling overhead as conventional relay schemes, and seamlessly integrate relay transmission with multiplexed MIMO transmission. We also design a MAC protocol to implement the distributed algorithm. Our performance results demonstrate that the use of cooperative relay in a MIMO framework could bring in a significant throughput improvement in all the scenarios studied, with the variation of node density, link failure ratio, packet arrival rate and retransmission threshold.

PrePrint: Low Complexity Multiplier Architectures for Single and Hybrid-Double Multiplications in Gaussian Normal Bases

The extensive rise in the number of resource constrained wireless devices and the needs for secure communications with the servers imply fast and efficient cryptographic computations for both parties. Efficient hardware implementation of arithmetic operations over finite field using Gaussian normal basis is attractive for public key cryptography as it provides free squarings. In this paper, we first present two low-complexity digit-level multiplier architectures. It is shown that the proposed multipliers outperform the existing Gaussian normal basis (GNB) multiplier structures available in the literature. Then, for the first time, using these two architectures, we propose a new digit-level hybrid multiplier which performs two successive multiplications with the same latency as the one for one multiplication. We have studied the efficiency of the proposed hybrid architecture in terms of area and time delay for different digit sizes. The main advantage of this new hybrid architecture is to speed up exponentiation and point multiplication whenever double-multiplication is required and the traditional schemes fail due to the data dependencies. We have investigated the applicability of the the proposed hybrid structure to reduce the latency of exponentiation-based cryptosystems. Our analysis and timing results show that the expected acceleration in double-exponentiation is considerable.

PrePrint: An Efficient Formulation of the Real-time Feasibility Region for Design Optimization

In the design of time-critical applications, schedulability analysis is used to define the feasibility region of tasks with deadlines, so that optimization techniques can find the best design solution within the feasibility region. The formulation of the feasibility region based on response time calculation requires many integer variables and is too complex for solvers. Approximation techniques have been used to define a convex subset of the feasibility region, used in conjunction with branch and bound approach to compute sub-optimal solutions for the optimal task period selection, priority assignment, or placement of tasks onto CPUs. In this paper, we provide an improved and simpler real-time schedulability test that allows an exact and efficient definition of the feasibility region in Mixed Integer Linear Programming (MILP) optimization. Our method requires a significantly smaller number of binary variables and is viable for the treatment of industrial-size problems as shown by the experiments.

PrePrint: µ*-Tree: An Ordered Index Structure for NAND Flash Memory with Adaptive Page Layout Scheme

As NAND flash memory is gaining popularity as a storage medium for mobile embedded devices, many flash-aware file systems, flash-aware DBMSes, and flash translation layers (FTLs) require an flash-efficient index structure. This paper proposes a novel index structure called µ*-Tree which natively works on NAND flash memory, aiming at improving performance over B+-Tree. µ*-Tree stores all the nodes along the path from the root to the leaf into a single flash memory page in order to minimize the number of flash write operation when a node is updated. Furthermore, µ*-Tree has an adaptive page layout scheme which dynamically adjusts the page layout according to the workload characteristics on-the-fly. µ*-Tree also allows flash pages with different page layouts to co-exist in the same tree. Our evaluation results with real workload traces show that µ*-Tree outperforms B+-Tree by up to 55% in terms of the time needed for flash operations. With a small in-memory cache of 32 KB, µ*-Tree improves the overall performance by up to 5 times compared to B+-Tree with the same cache size.

PrePrint: The Conditional Diagnosability of k-Ary n-Cubes Under the Comparison Diagnosis Model

Processor fault diagnosis plays an important role in measuring the reliability of multi-processor systems and the diagnosis of many well-known interconnection networks. Conditional diagnosability is a novel measure of diagnosability, which adds the additional condition that any faulty set cannot contain all of the neighbors of any vertex in a system. In this paper we study some topological properties of $k$-ary $n$-cubes, where $k \geq 4$ and $n \geq 4$, from which we can show that the conditional diagnosability of $k$-ary $n$-cubes under the comparison diagnosis model is $6n-5.

PrePrint: Multi-Level Diskless Checkpointing

Extreme scale systems available before the end of this decade are expected to have 100 million to 1 billion CPU cores. The probability that a failure occurs during an application execution is expected to be much higher than today's systems. Counteracting this higher failure rate may require a combination of disk-based checkpoints, diskless checkpoints, and algorithmic fault tolerance. Diskless checkpointing is an efficient technique to tolerate a small number of process failures in large parallel and distributed systems. In literature, a simultaneous failure of no more than $N$ processes is often tolerated by using a one-level Reed-Solomon checkpointing scheme for $N$ simultaneous process failures, whose overhead often increases quickly as $N$ increases. We introduce an $N$-level diskless checkpointing scheme that reduces the overhead for tolerating a simultaneous failure of up to $N$ processes. Each level is a diskless checkpointing scheme for a simultaneous failure of $i$ processes, where $i=1, 2, \ldots, N$. Simulation results indicate the proposed $N$-level diskless checkpointing scheme achieves lower fault tolerance overhead than the one-level Reed-Solomon checkpointing scheme for $N$ simultaneous processor failures.

PrePrint: Cycle-Efficient LFSR Implementation on Word-based Micro-architecture

Cycle-efficient implementation of the linear feedback shift register (LFSR) algorithm on a word-based micro-architecture is investigated. This work examines an algorithm transformation method, called term-preserving look-ahead transformation (TePLAT), that transforms the bit-serial LFSR algorithm into a bit parallel format while maintaining the overhead of the original LFSR algorithm. Detailed implementation methodologies as well as extensive simulation results are presented. We apply TePLAT to 25 commonly used LFSRs and test the resulting parallel formulations on two popular word-based micro-processor development platforms: a Texas Instrument C6416 Code Composition Simulator and an ARM-9 Simulator. In all 25 cases, TePLAT transformed LFSR formulations consistently achieve much higher throughput than those of a na\"{\i}ve implementation and a traditional look-ahead transformation based implementation.

PrePrint: A Symmetric Load Balancing Algorithm with Performance Guarantees for Distributed Hash Tables

Peers participating in a {\it distributed hash table} (DHT) may host different numbers of virtual servers and are enabled to balance their loads in the reallocation of virtual servers. Most decentralized load balance algorithms designed for DHTs based on virtual servers require the participating peers to be asymmetric, where some serve as the rendezvous nodes to pair virtual servers and participating peers, thereby introducing another load imbalance problem. While state-of-the-art studies intend to present symmetric load balancing algorithms, they introduce significant algorithmic overheads and guarantee no rigorous performance metrics. In this paper, a novel symmetric load balancing algorithm for DHTs is presented by having the participating peers approximate the system state with histograms and cooperatively implement a global index. Each peer independently reallocates in our proposal its locally hosted virtual servers by publishing and inquiring the global index based on their histograms. Unlike competitive algorithms, our proposal exhibits analytical performance guarantees in terms of the load balance factor and the algorithmic convergence rate, and introduces no load imbalance problem due to the algorithmic workload. Through computer simulations, we show that our proposal clearly outperforms existing distributed algorithms in terms of load balance factor with a comparable movement cost.

PrePrint: Handauth: Efficient Handover Authentication with Conditional Privacy for Wireless Networks

Existing mechanisms for handover authentication mainly focus on designing a secure authentication module, little attention has been paid to protect users' privacy when they are authenticated by the access points for data access. Further, most existing approaches do not support user revocation. In this paper, we present a secure and efficient authentication protocol named Handauth. Similar to the mechanisms of this field, Handauth provides user authentication and session key establishment. However, compared to other well known approaches, Handauth not only enjoys both computation and communication efficiency, but also achieves strong user anonymity and untraceablility, forward secure user revocation, conditional privacy-preservation, AAA server anonymity, access service expiration management, access point authentication, easily scheduled revocation, dynamic user revocation and attack-resistance. Experimental results show that the proposed approach is feasible for real applications.

PrePrint: A Distributed TCAM Coprocessor Architecture for Integrated Longest Prefix Matching, Policy Filtering and Content Filtering

Longest Prefix Matching (LPM), Policy Filtering (PF) and Content Filtering (CF) are three important tasks for Internet nowadays. It is both technologically and economically important to develop integrated solutions to the effective execution of the three tasks. To this end, in this paper, we propose a distributed Ternary Content Addressable Memory (TCAM) coprocessor architecture. The integrated solution exploits the complementary lookup load and storage load requirements of the three tasks to balance the lookup load and storage load among the TCAMs. A prefix filtering based CF algorithm is designed to reduce the lookup load and a novel cache system is developed to dynamically handle the lookups from overloaded TCAMs. Simulations based on real-world traffic traces show that the proposed solution can perform all three tasks given a 10 Gbps line rate using only the resources required to perform just the CF task given a 10 Gbps line rate.

PrePrint: On Resource Placement in Gaussian and EJ Interconnection Networks

...

PrePrint: WLAN Location Service with TXOP

The provision of location based services with high positional accuracy requires the use of Time of Arrival (TOA) based techniques. However, existing TOA based WLAN location service schemes are inefficient due to the individual query and response ranging method employed. We present a highly efficient WLAN location service architecture which includes a modification to the Transmit Opportunity (TXOP) technique in the IEEE 802.11e standard. Our Location Service with TXOP (LSOP) scheme achieves high efficiency by minimizing the number of TOA transmissions and eliminating the contention overhead for TOA messages. The adaptation of TXOP technique also improves location accuracy by protecting TOA messages from collision and by grouping the TOA messages into one compact burst. Our analysis shows that the LSOP scheme achieves the highest location update rate compared to previous schemes. Our simulation results show that the LSOP scheme has minimum impact on data traffic and achieves higher accuracy than the previous schemes. Experimental results demonstrate the degradation in localization performance caused by packet collisions. These results validate that our LSOP scheme, which implements contention free broadcast of TOA messages with a modified TXOP, provides the best combination of high location update rate, low network load and high location accuracy compared to other schemes.

PrePrint: Fault Models and Test Methods for Subthreshold SRAMs

Due to the increasing demand of an extra-low-power system, a great amount of research effort has been spent in the past to develop an effective and economic subthreshold-SRAM design. However, the test methods regarding those newly developed subthreshold-SRAM designs have not yet been fully discussed. In this paper, we first categorize the subthreshold-SRAM designs into three types, study the faulty behavior of open defects and address decoders faults on each type of designs, and then identify the faults which may not be covered by a traditional SRAM test method. We will also discuss the impact of open defects and threshold-voltage mismatch on sense amplifiers under subthreshold operations. A discussion about the temperature at test will be also provided.

PrePrint: Parallel AES Encryption Engines for Many-Core Processor Arrays

By exploring different granularities of data-level and task-level parallelism, we map 16 implementations of an Advanced Encryption Standard (AES) encipher with both online and offline key expansion on a fine-grained many-core system. The smallest design utilizes only 6 cores for offline key expansion and 8 cores for online key expansion, while the largest requires 107 cores and 137 cores, respectively. The throughput of each design is examined by both synchronous dataflow models and measurements from a fabricated chip. In comparison with published AES encipher implementations on general purpose processors, our design has 3.5-15.6 times higher throughput per area and 8.2-18.1 times higher energy efficiency. Moreover, the design shows 2.0 times higher throughput than the TI DSP C6201, and 3.3 times higher throughput per area and 2.9 times higher energy efficiency than the GeForce 8800 GTX.

PrePrint: NoC-based FPGA Acceleration for Monte Carlo Simulations with Applications to SPECT Imaging

As the number of transistors that are integrated onto a silicon die continues to increase, the compute power is becoming a commodity. This has enabled a whole host of new applications that rely on high-throughput computations. Recently, the need for faster and cost-effective applications in form-factor constrained environments has driven an interest in on-chip acceleration of algorithms based on Monte Carlo simulations. Though Field Programmable Gate Arrays (FPGAs), with hundreds of on-chip arithmetic units, show significant promise for accelerating these embarrassingly parallel simulations, a challenge exists in sharing access to simulation data amongst many concurrent experiments. This paper presents a compute architecture for accelerating Monte Carlo simulations based on the Network-on-Chip (NOC) paradigm for on-chip communication. We demonstrate through the complete implementation of a Monte Carlo-based image reconstruction algorithm for Single-Photon Emission Computed Tomography (SPECT) imaging that this complex problem can be accelerated by two orders of magnitude on even a modestly-sized FPGA over a 2GHz Intel Core 2 Duo Processor. The architecture and the methodology that we present in this paper is modular and hence it is scalable to problem instances of different sizes, with application to other domains that rely on Monte Carlo simulations.

PrePrint: Dynamic Bit Encoding for Privacy Protection Against Correlation Attacks in RFID Backward Channel

Nowadays Radio Frequency Identification (RFID) technologies are applied in many fields for a variety of applications. Though bringing great productivity gains, RFID systems may cause new security and privacy threats to individuals or organizations. Therefore, it is important to protect the security of RFID systems and the privacy of RFID tag owners. Unfortunately, none of the existing solutions provide a complete defense against eavesdroppers who could monitor the communication between RFID readers and tags and recover the contents of tags. Based on our research, we propose two novel RFID backward channel protection protocols, namely dynamic bit encoding and optimized dynamic bit encoding. Our schemes are able to achieve high anonymity with limited communication overhead. Our extensive simulations show that both proposed schemes provide much stronger backward channel protection than existing techniques. In addition, analytical models were created and validated through comparisons with simulation results.

PrePrint: A Novel Heuristic Method for Application Dependent Testing of a SRAM-Based FPGA Interconnect

This paper presents a new method for generating configurations for application dependent testing of a SRAM-based FPGA interconnect. This method connects an activating input to multiple nets, thus generating activating test vectors for detecting stuck-at, open and bridging faults. This arrangement permits a reduction in the number of redundant configurations, thus also achieving a reduction in test time for application-dependent testing at full fault coverage. As the underlying solution requires an exponential complexity, a heuristic algorithm that is polynomial and greedy in nature (based on sorting) is used for net selection in the configuration generation process. It is proved that this algorithm has an execution complexity of O(L^3) (where L is the number of LUTs in the design). The proposed method requires at most log2(M+2) configurations (where M denotes the number of activating inputs) as Walsh coding is employed. Moreover, it is scalable with respect to LUT inputs. Extensive logic based simulation results are provided for ISCAS89 sequential benchmark designs implemented on Xilinx Virtex4 FPGAs; these results shows that the proposed method achieves a considerable reduction in the number of test configurations compared with methods found in the technical literature (on average, a reduction of 49.5%).

PrePrint: Low Cost NBTI Degradation Detection & Masking Approaches

Performance degradation of integrated circuits due to aging effects, such as Negative Bias Temperature Instability (NBTI), is becoming a great concern for current and future CMOS technology. In this paper we propose two monitoring and masking approaches that detect late transitions due to NBTI degradation in the combinational part of critical data-paths and guarantee the correctness of the provided output data by adapting the clock frequency. Compared to recently proposed alternative solutions, one of our approaches (denoted as Low Area and Power (LAP) approach) requires lower area overhead and lower, or comparable, power consumption, while exhibiting the same impact on system performance, while the other proposed approach (denoted as High Performance (HP) approach) allows us to reduce the impact on system performance, at the cost of some increase in area and power consumption.

PrePrint: Privacy-Preserving Public Auditing for Secure Cloud Storage

Using Cloud Storage, users can remotely store their data and enjoy the on-demand high quality applications and services from a shared pool of configurable computing resources, without the burden of local data storage and maintenance. However, the fact that users no longer have physical possession of the outsourced data makes the data integrity protection in Cloud Computing a formidable task, especially for users with constrained computing resources. Moreover, users should be able to just use the cloud storage as if it is local, without worrying about the need to verify its integrity. Thus, enabling public auditability for cloud storage is of critical importance so that users can resort to a third party auditor (TPA) to check the integrity of outsourced data and be worry-free. To securely introduce an effective TPA, the auditing process should bring in no new vulnerabilities towards user data privacy, and introduce no additional online burden to user. In this paper, we propose a secure cloud storage system supporting privacy-preserving public auditing. We further extend our result to enable the TPA to perform audits for multiple users simultaneously and efficiently. Extensive security and performance analysis show the proposed schemes are provably secure and highly efficient.

PrePrint: Minimizing Probing Cost and Achieving Identifiability in Probe Based Network Link Monitoring

Continuously monitoring link performance is important to network diagnosis. In this paper, we address the problem of minimizing the probing cost and achieving identifiability in probe based network link monitoring. Given a set of links to monitor, our objective is to select the minimum number of probing paths that can uniquely determine all identifiable links and cover all unidentifiable links. We propose an algorithm based on a linear system model to find out all irreducible sets of probing paths that can uniquely determine an identifiable link, and we extend the bipartite model to reflect the relationship between a set of probing paths and an identifiable link. Since our optimization problem is NP-hard, we propose a heuristic based algorithm to greedily select probing paths. Our method eliminates two types of redundant probing paths, i.e., those that can be replaced by others and those without any contribution to achieving identifiability. Simulations based on real network topologies show that our approach can achieve identifiability with very low probing cost. Compared with prior work, our method is more general and has better performance.

PrePrint: Integer Codes Correcting Burst Errors Within A Byte

This paper presents a class of integer codes that can correct any burst of length ≤ / within a b-bit byte. Their main advantages lie in linear complexity of encoding and decoding procedures, as well as in the fact that a look-up table based error control procedure requires relatively small memory resources.

PrePrint: A General Framework of Side-Channel Atomicity for Elliptic Curve Scalar Multiplication

Simple power attack (SPA) is a type of side-channel attack (SCA). In literature, many SPA-resistant scalar multiplication algorithms have been proposed, but most are inefficient and not interoperable with other coding methods. To prevent SPA, Chevallier-Mames et al. proposed a technique called side-channel atomicity for pure binary number systems. Using their method, extra costs for preventing SPA can be limited. Even though many researchers have extended this technique to other number systems, their algorithms are for specific cases and few provide implementation results. In this paper, we generalize the atomicity technique to protect nearly all existing fast coding methods/number systems. Our general framework provides security and flexibility while its efficiency is coupled to that of the coding methods. Moreover, we utilize our framework to protect the known fastest scalar multiplications by exploring application on the GLV method for GLS curves. Proof of concept programs are written in the C language along with assembly for fast field operations and run on AMD Athlon X2 245 based hardware.