Search

The energy and cooling costs of Web server farms are among their main financial expenditures. This paper explores the benefits of dynamic voltage scaling (DVS) for power management in server farms. Unlike previous work, which addressed DVS on individual servers and on load-balanced server replicas, this paper addresses DVS in multistage service pipelines. Contemporary Web server installations typically adopt a three-tier architecture in which the first tier presents a Web interface, the second executes scripts that implement business logic, and the third serves database accesses. From a user's perspective, only the end-to-end response across the entire pipeline is relevant. This paper presents a rigorous optimization methodology and an algorithm for minimizing the total energy expenditure of the multistage pipeline subject to soft end-to-end response-time constraints. A distributed power management service is designed and evaluated on a real three-tier server prototype for coordinating DVS settings in a way that minimizes global energy consumption while meeting end-to-end delay constraints. The service is shown to consume as much as 30 percent less energy compared to the default (Linux) energy saving policy. [ABSTRACT FROM AUTHOR]

The max-bisection problem consists in partitioning the vertices of a weighted undirected graph into two equally sized subsets so as to maximize the sum of the weights of crossing edges. It is an NP-hard combinatorial optimization problem that arises in many applications. In this paper, we present a memetic algorithm for the max-bisection problem, which integrates a new fast local search procedure, a crossover operator, and a pool updating strategy. These strategies achieve a balance between intensification and diversification. Extensive experiments were performed on a number of benchmark instances with 800 to 10,000 vertices from the literature. The proposed memetic algorithm improved the best known solutions for all benchmark instances tested in this paper. The improvement in terms of cut value over the CirCut by Burer et al. refid="ref34"/ ranging from 0.02 to 4.15 percent, and the average time of our proposed memetic algorithm is much lower than that of CirCut. It shows that the proposed memetic algorithm can find high quality solutions in an acceptable running time. [ABSTRACT FROM AUTHOR]

This paper presents a 128-bit CCA2-secure McEliece cryptoprocessor. The existing side-channel vulnerabilities in this regard are also taken care during the implementation of such a post-quantum immune code-based cryptosystem. In order to achieve CCA2 security on original McEliece algorithm, we incorporate a SHA-3 finalist, BLAKE-512 module into the architecture. A complete binary-XGCD algorithm for Goppa field is introduced. The final design on a Virtex-6 FPGA performs an encryption in \bf 4.74\nbsp \mu \mbis and a decryption in \bf 0.92\nbsp \mbims. To the best of our knowledge, this is the first hardware design of McEliece with the above mentioned advanced security features which is also resistant against existing timing attacks. [ABSTRACT FROM AUTHOR]

The theory of regions was introduced in the early nineties as a method to bridge state and event-based models. This paper tackles the problem of deriving a Petri net from a state-based model, using the theory of regions. Some of the restrictions required in the traditional approach are dropped in this paper, together with significant extensions that make the approach applicable in new scenarios. One of these scenarios is Process Mining, where accepting (discovering) additional behavior in the synthesized Petri net is sometimes valued. The algorithmic emphasis used in this paper contributes to the demystification of the theory of regions as been only a good theoretical exercise, opening the door for its application in the industrial domain. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of balancing the on-chip packet latencies in a chip multi-processor (CMP), which is simultaneously executing multiple applications. Specifically, this paper presents a balanced application-to-core mapping algorithm that aims to minimize the maximum on-chip packet latency of all running applications. The paper starts by formulating the balanced mapping problem for CMPs and proving its NP-completeness. Next it presents an efficient heuristic algorithm for solving the aforesaid problem, which utilizes the characteristics of on-chip cache and memory accesses in CMPs and takes into account the workload variations among applications. Simulation results on PARSEC benchmark suite show that the proposed algorithm lowers the maximum average packet latency of all applications by 11 percent while cutting the standard deviation of on-chip packet latencies by 99 percent. This is achieved by very little overhead in terms of the overall packet latency and power consumption averaged over all packets. [ABSTRACT FROM AUTHOR]

Efficient retrieval of replicated data from multiple disks is a challenging problem, especially for heterogeneous storage architectures. Recently, maximum flow based optimal replica selection algorithms were proposed guaranteeing the minimum retrieval time in heterogeneous environments. Although optimality of the retrieval schedule is an important property, execution time of the replica selection algorithm is also crucial since it might significantly affect the performance of the storage sub-system. Current replica selection mechanisms achieve the optimal response time retrieval schedule by performing multiple runs of a maximum flow algorithm in a black-box manner. Such black-box usage of a maximum flow algorithm results in unnecessary flow calculations since previously calculated flow values cannot be conserved. In addition, most new generation multi-disk storage architectures are powered with multi-core processors motivating the usage of multithreaded replica selection algorithms. In this paper, we propose multithreaded and integrated maximum flow based optimal replica selection algorithms handling heterogeneous storage architectures. Proposed and existing algorithms are evaluated using various homogeneous and heterogeneous multi-disk storage architectures. Experimental results show that proposed sequential integrated algorithm achieves 5X speed-up in homogeneous systems, and proposed multithreaded integrated algorithm achieves 21X speed-up using 16 threads in heterogeneous systems over the existing sequential black-box algorithm. [ABSTRACT FROM AUTHOR]

Cayley data centers are well known patterns of completely wireless data centers (WDCs). However, low link reliability and link interference will affect the construction of virtual networks. This paper proposes a virtual resource mapping algorithm on the basis of Cayley structures. First, we analyze the characteristics of Cayley WDCs and model networks in WDCs, where a virtual network is modeled as a traditional undirected graph, while a physical topology is modeled as a directed graph. Second, we propose a virtual resource mapping and coloring algorithm based on link interference called VRMCA-LI. We build a connection interference matrix for each node and use a coloring method to avoid interference. VRMCA-LI uses the same color for the nodes that are within the transmitting angle of a sending node and whose signal-to-noise ratio is less than a threshold. These nodes with the same color cannot be allocated to virtual nodes at the same time. The allocation of nodes and links are concurrent, which performs dynamic adjustment to save mapping time. Third, our experimental results show that VRMCA-LI outperforms WVNEA-LR and PG-VNE in terms of mapping time of virtual nodes, acceptance rate of virtual networks, and average node utilization rate. [ABSTRACT FROM AUTHOR]

Performance and energy are now the most dominant objectives for optimization on modern parallel platforms composed of multicore CPU nodes. The existing intra-node and inter-node optimization methods employ a large set of decision variables but do not consider problem size as a decision variable and assume a linear relationship between performance and problem size and between energy consumption and problem size. We demonstrate using experiments of real-life data-parallel applications on modern multicore CPUs that these relationships have complex (non-linear and even non-convex) properties and, therefore, that the problem size has become an important decision variable that can no longer be ignored. This key finding motivates our work in this paper. In this paper, we first formulate the bi-objective optimization problem for performance and energy (BOPPE) for data-parallel applications on homogeneous clusters of modern multicore CPUs. It contains only one but heretofore unconsidered decision variable, the problem size. We then present an efficient and exact global optimization algorithm called ALEPH that solves the BOPPE. It takes as inputs, discrete functions of performance and dynamic energy consumption against problem size and outputs the globally Pareto-optimal set of solutions. The solutions are the workload distributions, which achieve inter-node optimization of data-parallel applications for performance and energy. While existing solvers for BOPPE give only one solution when the problem size and number of processors are fixed, our algorithm gives a diverse set of globally Pareto-optimal solutions. The algorithm has time complexity of $O(m^2 \times p^2)$ where $m$ is the number of points in the discrete speed/energy function and $p$ is the number of available processors. We experimentally study the efficiency and scalability of our algorithm for two data parallel applications, matrix multiplication and fast Fourier transform, on a modern multicore CPU and homogeneous clusters of such CPUs. Based on our experiments, we show that the average and maximum sizes of the globally Pareto-optimal sets determined by our algorithm are 15 and 34 and 7 and 20 for the two applications respectively. Comparing with load-balanced workload distribution solution, the average and maximum percentage improvements in performance and energy respectively demonstrated for the first application are (13%,97%) and (18%,71%). For the second application, these improvements are (40%,95%) and (22%,127%). Assuming 5 percent performance degradation from the optimal is acceptable, the average and maximum improvements in energy consumption demonstrated for the two applications respectively are 9 and 44 and 8 and 20 percent. Using the algorithm and its building blocks, we also present a study of interplay between performance and energy. We demonstrate how ALEPH can be combined with DVFS-based Multi-Objective Optimization (MOP) methods to give a better set of (globally Pareto-optimal) solutions. [ABSTRACT FROM AUTHOR]

Since Edwards curves were introduced to elliptic curve cryptography by Bernstein and Lange in 2007, they have received a lot of attention due to their very fast group law operation. Pairing computation on such curves is slightly slower than on Weierstrass curves. However, in some pairing-based cryptosystems, they might require a number of scalar multiplications which is time-consuming operation and this can be advantageous to use Edwards in this scenario. In this paper, we present a variant of Miller’s algorithm for pairing computation on Edwards curves. Our approach is generic, it is able to compute both Weil and Tate pairings on pairing-friendly Edwards curves of any embedding degree. Our analysis shows that the new algorithm is faster than the previous algorithms for odd embedding degree and as fast as for even embedding degree. Hence, the new algorithm is suitable for computing optimal pairings and in situations where the denominators elimination technique is not possible. [ABSTRACT FROM AUTHOR]

In this paper, we present a design and implementation of FD-Buffer, a cost-based adaptive buffer manager for flash memory devices. Due to flash memory’s unique hardware features, it has an inherent read-write asymmetry: writes involve expensive erase operations, which usually makes them much slower than reads. To address this read-write asymmetry, we revisit buffer management and consider the average I/O cost per page access as the main cost metric, as opposed to the traditional miss rate. While there have been a number of buffer management algorithms that take the read-write asymmetry into consideration, most algorithms fail to effectively adapt to the runtime workload or different degrees of asymmetry. In this paper, we develop a new replacement algorithm in which we separate clean and dirty pages into two pools. The size ratio of the two pools is automatically adapted based on the read-write asymmetry and the runtime workload. We evaluate the FD-Buffer with trace-driven experiments on real flash memory devices. Our trace-driven evaluation results show that our algorithm achieves 4.0-33.4 percent improvement of I/O performance on flash memory, compared to state-of-the-art flash-aware replacement policies. [ABSTRACT FROM PUBLISHER]

This paper presents an on-line admission control methodology for periodic and aperiodic service processes with end-to-end real-time constraints. Both types of service process requests dynamically join and leave a system at run time. During the admission test, the schedulability of a periodic task is determined by using its fixed task capacity. Aperiodic tasks are admitted using the available capacity after admitted periodic tasks. At run time, the earliest deadline first (EDF) scheduling is used to schedule the mixed periodic and aperiodic workloads. Simulation results show that the proposed algorithm may achieve up to 90% in system utilization, while incurring a low admission overhead for each service request. [ABSTRACT FROM PUBLISHER]

This paper presents flott, a fast, low memory T-transform algorithm which can be used to compute the string complexity measure T-complexity. The algorithm uses approximately one third of the memory of its predecessor while reducing the running time by about 20 percent. The flott implementation has the same worst-case memory requirements as state of the art suffix tree construction algorithms. A suffix tree can be used to efficiently compute the Lempel-Ziv production complexity, which is another measure of string complexity. The C-implementation of flott is available as Open Source software. [ABSTRACT FROM PUBLISHER]

The scaling problem in Residue Number System was addressed in many publications. A significant focus was given to scale the three moduli set (2^n-1, 2^n, 2^n+1) by 2^n , where n is a positive integer. This paper presents a scaling structure design for the moduli sets (2^n-1, 2^n+p, 2^n+1) scaled by 2^n , where 0\leq p \leq n . The new design has the delay of a full-adder and a modular adder. The proposed structure is smaller, faster and more power-efficient than the most recent published work for the same moduli set and the same scaling factor. VLSI synthesis results showed an average area reduction of (9.8-27.9) percent, an average time reduction of (13.9-20.8) percent and an average power reduction of (15.9-22.3) scaled by 2^{n+p} , where 1\leq p \leq n$ . The delay of this structure is one half-adder more than the delay of the aforementioned structure. [ABSTRACT FROM AUTHOR]

The compaction of test programs for processor-based systems is of utmost practical importance: Software-Based Self-Test (SBST) is nowadays increasingly adopted, especially for in-field test of safety-critical applications, and both the size and the execution time of the test are critical parameters. However, while compacting the size of binary test sequences has been thoroughly studied over the years, the reduction of the execution time of test programs is still a rather unexplored area of research. This paper describes a family of algorithms able to automatically enhance an existing test program, reducing the time required to run it and, as a side effect, its size. The proposed solutions are based on instruction removal and restoration, which is shown to be computationally more efficient than instruction removal alone. Experimental results demonstrate the compaction capabilities, and allow analyzing computational costs and effectiveness of the different algorithms. [ABSTRACT FROM AUTHOR]

The modular multiplication operation is the most time-consuming operation for number-theoretic cryptographic algorithms involving large integers, such as RSA and Diffie-Hellman. Implementations reveal that more than 75 percent of the time is spent in the modular multiplication function within the RSA for more than 1,024-bit moduli. There are fast multiplier architectures to minimize the delay and increase the throughput using parallelism and pipelining. However such designs are large in terms of area and low in efficiency. In this paper, we integrate the fast Fourier transform (FFT) method into the McLaughlin’s framework, and present an improved FFT-based Montgomery modular multiplication (MMM) algorithm achieving high area-time efficiency. Compared to the previous FFT-based designs, we inhibit the zero-padding operation by computing the modular multiplication steps directly using cyclic and nega-cyclic convolutions. Thus, we reduce the convolution length by half. Furthermore, supported by the number-theoretic weighted transform, the FFT algorithm is used to provide fast convolution computation. We also introduce a general method for efficient parameter selection for the proposed algorithm. Architectures with single and double butterfly structures are designed obtaining low area-latency solutions, which we implemented on Xilinx Virtex-6 FPGAs. The results show that our work offers a better area-latency efficiency compared to the state-of-the-art FFT-based MMM architectures from and above 1,024-bit operand sizes. We have obtained area-latency efficiency improvements up to 50.9 percent for 1,024-bit, 41.9 percent for 2,048-bit, 37.8 percent for 4,096-bit and 103.2 percent for 7,680-bit operands. Furthermore, the operating latency is also outperformed with high clock frequency for length-64 transform and above. [ABSTRACT FROM AUTHOR]

In this paper, we propose linear branch entropy, a new metric for characterizing branch behavior. Linear branch entropy is independent of the configuration of a specific branch predictor, but is highly correlated with the branch misprediction rate of any predictor. In particular, we empirically derive a linear relationship between linear branch entropy and branch misprediction rate, which enables predicting miss rates for a range of branch predictors using a single branch entropy profile. Linear branch entropy is more accurate than previously proposed branch classification models, such as taken rate and transition rate. In addition, linear branch entropy provides insight for both analyzing an application’s inherent branch behavior as well as for understanding a branch predictor’s performance for easy-to-predict versus hard-to-predict branches. We present several case studies, ranging from comparing state-of-the-art branch predictors to compiler optimizations. More in particular, we find that the winner of the latest branch predictor competition outperforms the runners-up on easy-to-predict branches, but performs worse on hard-to-predict branches. We also show that using linear branch entropy to guide if-conversion in compilers leads to better performance compared to standard if-conversion heuristics. [ABSTRACT FROM AUTHOR]

In this work, we propose a hardware-friendly reinforcement learning algorithm. The learning algorithm is based on an actor-critic structure implemented with spiking neural networks (SNNs). A biologically plausible and hardware-friendly spike-timing-dependent plasticity learning rule is formulated and employed in the training of SNNs. Several important aspects of applying the learning rule in a reinforcement learning context is studied, especially from the circuit designers’ point of view. Pitfalls of potential noise mixing and correlated spikes are identified and properly addressed. To feature a low-power learning architecture, techniques such as down-sampling data for certain learning blocks, injecting quantization noise as noisy residues in neurons, and proper memory partitioning are proposed. A 1-D state-value function learning problem and a 2-D maze walking problem are examined in this paper to illustrate effectiveness of the proposed algorithm and learning rules. A low-power hardware architecture is proposed and examples are implemented with Verilog. Hardware complexity of the proposed algorithm is analyzed, and potential solutions to breaking memory bottleneck when the size of the problem gets large is also discussed. [ABSTRACT FROM PUBLISHER]

Several task models have been introduced in the literature to describe the intrinsic parallelism of real-time activities, including fork/join, synchronous parallel, DAG-based, etc. Although schedulability tests and resource augmentation bounds have been derived for these task models in the context of multicore systems, they are still too pessimistic to describe the execution flow of parallel tasks characterized by multiple (and nested) conditional statements, where it is hard to decide which execution path to select for modeling the worst-case scenario. To overcome this problem, this paper proposes a task model that integrates control flow information by considering conditional parallel tasks (cp-tasks) represented by DAGs with both precedence and conditional edges. For this task model, a set of meaningful parameters are identified and computed by efficient algorithms and a response-time analysis is presented for different scheduling policies. Experimental results are finally reported to evaluate the efficiency of the proposed schedulability tests and their performance with respect to classic tests based on both conditional and non-conditional existing approaches. [ABSTRACT FROM PUBLISHER]

This paper studies the implementation of Boolean functions by lattices of four-terminal switches. Each switch is controlled by a Boolean literal. If the literal takes the value 1, the corresponding switch is connected to its four neighbors; else it is not connected. A Boolean function is implemented in terms of connectivity across the lattice: it evaluates to 1 iff there exists a connected path between two opposing edges of the lattice. The paper addresses the following synthesis problem: how should one assign literals to switches in a lattice in order to implement a given target Boolean function? The goal is to minimize the lattice size, measured in terms of the number of switches. An efficient algorithm for this task is presented—one that does not exhaustively enumerate paths but rather exploits the concept of Boolean function duality. The algorithm produces lattices with a size that grows linearly with the number of products of the target Boolean function in ISOP form. It runs in time that grows polynomially. Synthesis trials are performed on standard benchmark circuits. The synthesis results are compared to a lower-bound calculation on the lattice size. [ABSTRACT FROM PUBLISHER]

Hardware support for decimal computer arithmetic is regaining popularity. One reason is the recent growth of decimal computations in commercial, scientific, financial, and Internet-based computer applications. Newly commercialized decimal arithmetic hardware units use radix-10 sequential multipliers that are rather slow for multiplication-intensive applications. Therefore, the future relevant processors are likely to host fast parallel decimal multiplication circuits. The corresponding hardware algorithms are normally composed of three steps: partial product generation (PPG), partial product reduction (PPR), and final carry-propagating addition. The state of the art is represented by two recent full solutions with alternative designs for all the three aforementioned steps. In addition, PPR by itself has been the focus of other recent studies. In this paper, we examine both of the full solutions and the impact of a PPR-only design on the appropriate one. In order to improve the speed of parallel decimal multiplication, we present a new PPG method, fine-tune the PPR method of one of the full solutions and the final addition scheme of the other; thus, assembling a new full solution. Logical Effort analysis and 0.13 µm synthesis show at least 13 percent speed advantage, but at a cost of at most 36 percent additional area consumption. [ABSTRACT FROM AUTHOR]

Most packet scheduling algorithms for input-queued switches operate on fixed-sized packets known as cells. In reality, communication traffic in many systems such as Internet runs on variable-sized packets. Motivated by potential savings of segmentation and reassembly, there has been increasing interest in scheduling variable-sized packets in a nonpreemptive manner known as packet-mode scheduling. This paper studies frame-based packet-mode scheduling for better scalability. It first shows that the admissible condition is no longer sufficient for packet-mode scheduling. Then, a relation between the frame size and packet sizes is derived that classifies under what conditions the packet-mode scheduling problem is polynomial solvable or is NP-hard. This relation reveals an interesting result that under various packet size distributions, it may be polynomial solvable even if many different packet sizes occur in the packet set, whereas it may be NP-hard with just two packet sizes present. Finally, as a practical solution, this paper studies how a speedup can help packet-mode scheduling. It is shown that the admissible condition becomes sufficient also when a speedup of two is used. A simple algorithm with a speedup of two is presented. [ABSTRACT FROM AUTHOR]

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]

The Parallel Disks Model (PDM) has been proposed to alleviate the I/O bottleneck that arises in the processing of massive data sets. Sorting has been extensively studied on the PDM model due to the fundamental nature of the problem--several asymptotically optimal algorithms are known for sorting. Although randomization has been frequently exploited, most of the prior algorithms suffer from complications in memory layouts, implementation, restrictions in range of parameters, and laborious analysis. In this paper, we present a randomized mergesort algorithm based on a simple idea that sorts using an asymptotically optimal number of I/O operations with high probability and has all of the desirable features for practical implementation. In the second part of the paper, we also present several novel algorithms for sorting on the PDM that take only a small number of passes through the data. Recently, considerable interest has been shown by researchers in developing algorithms for problem sizes of practical interest and we are able to obtain several improvements and simplification, in particular for random input. [ABSTRACT FROM AUTHOR]

Advances in clock synchronization techniques allow an approximated global time in ubiquitous environments. This paper presents an event stream-based online algorithm that fuses the data reported from the processors in such a network to detect time-based predicates. The algorithm has low space, time, and message complexities. The paper also considers the detection of simultaneous events as a special case. [ABSTRACT FROM AUTHOR]

Improving cache performance requires understanding cache behavior. However, measuring cache performance for one or two data input sets provides little insight into how cache behavior varies across all data input sets and all cache configurations. This paper uses locality analysis to generate a parameterized model of program cache behavior. Given a cache size and associativity, this model predicts the miss rate for arbitrary data input set sizes. This model also identifies critical data input sizes where cache behavior exhibits marked changes. Experiments show this technique is within 2 percent of the hit rate for set associative caches on a set of floating-point and integer programs using array and pointer-based data structures. Building on the new model, this paper presents an interactive visualization tool that uses a three-dimensional plot to show miss rate changes across program data sizes and cache sizes and its use in evaluating compiler transformations. Other uses of this visualization tool include assisting machine and benchmark-set design. The tool can be accessed on the Web at http://www.cs.rochester.edu/research/locality. [ABSTRACT FROM AUTHOR]

A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy consumption is a superlinear function of the transmission distance. One approach to prolonging network lifetime while preserving network connectivity is to deploy a small number of costly, but more powerful, relay nodes whose main task is communication with other sensor or relay nodes. In this paper, we assume that sensor nodes have communication range r > 0, while relay nodes have communication range R ≥ r, and we study two versions of relay node placement problems. In the first version, we want to deploy the minimum number of relay nodes so that, between each pair of sensor nodes, there is a connecting path consisting of relay and/or sensor nodes. In the second version, we want to deploy the minimum number of relay nodes so that, between each pair of sensor nodes, there is a connecting path consisting solely of relay nodes. We present a polynomial time 7-approximation algorithm for the first problem and a polynomial time (5 + ϵ)-approximation algorithm for the second problem, where ϵ > 0 can be any given constant. [ABSTRACT FROM AUTHOR]

This paper investigates the task scheduling problem for real-time systems that provide rate of progress guarantees on task execution. A parameterized task system model, called the (r, g) task system, is introduced that allows rate of progress requirements to be specified in terms of two simple parameters: an execution rate r and a granularity g. The granularity parameter is a new metric that allows the specification of "fine-grain" timing constraints on the task's execution and is a generalization of the stretch metric used in recent research on task scheduling. It is shown that the product rlg(1/g) is an important determiner of the existence of good online scheduling algorithms. Specifically, there is an upper bound on this product above which there are no good online algorithms, but below which an online algorithm with logarithmic competitive ratio exists. This paper also demonstrates a fundamental difference between two contrasting strategies for admission control: greedy versus nongreedy. It is shown that "greed does not pay": there is a scheduling algorithm with a nongreedy admission policy that provably outperforms the well-known Greedy EDF scheduling algorithm. [ABSTRACT FROM AUTHOR]

One of the solutions to improve mobile Delay Tolerant Network (DTN) performance is to place additional stationary nodes, called throwboxes, to create a greater number of contact opportunities. In this paper, we study a key optimization problem in a time-evolving throwbox-assisted DTN: throwbox selection, to answer the questions such as “how many active throwboxes do I need?” and “which throwboxes should be activated?” We formally define two throwbox optimization problems: min-throwbox problem and k-throwbox problem for time-evolving DTNs modeled by weighted space-time graphs. We show that min-throwbox problem is NP-hard and propose a set of greedy algorithms which can efficiently provide quality solutions for both challenging problems. [ABSTRACT FROM AUTHOR]

IP address lookup operation determines the longest prefix matching each incoming destination address. As a fundamental operation for packet forwarding at Internet routers, search speed for routing table lookup is the most important performance metric. Previous researches have shown that the search performance of trie-based algorithms can be improved by adding on-chip Bloom filters. In these algorithms, an on-chip Bloom filter identifies the membership of a node in an off-chip trie, and the number of trie accesses is reduced, because the Bloom filter can filter out accesses to non-existing nodes in the trie. In this paper, we propose a new method of utilizing a Bloom filter for the IP address lookup problem. In the previous Bloom filter-based approach, false positiveness has to be identified by accessing the off-chip trie for every positive result, since false positives can produce wrong results. In our proposed approach, the false positiveness of a Bloom filter is not necessarily identified by making false positives not mislead the search. Hence the number of off-chip trie accesses are significantly reduced. Simulation results show that the best matching prefix can be found with a single off-chip access in average and in the worst-case with the reasonable size of a Bloom filter in our proposed method. [ABSTRACT FROM AUTHOR]

The Hierarchical Real-Time Scheduling (HiRTS) technique helps improve overall resource utilization in real-time embedded systems. With HiRTS, a computation resource is divided into a group of temporal resource partitions, each of which accommodates multiple real-time tasks. Besides the computation resource partitioning problem, real-time task scheduling on resource partitions is also a major problem of HiRTS. The existing scheduling techniques for dedicated resources, like schedulability tests and utilization bounds, are unable to work without changes on temporal resource partitions in most cases. In this paper, we show how to achieve maximal transparency for task scheduling on Regular Partitions, a type of resource partition introduced by the Regularity-based Resource Partition (RRP) Model. We show that several classes of real-time scheduling problems on a regular partition can be transformed into equivalent problems on a dedicated single resource, such that comprehensive single-resource scheduling techniques provide optimal solutions. Furthermore, this transformation method could be applied to different types of real-time tasks such as periodic tasks, sporadic tasks and aperiodic tasks. [ABSTRACT FROM AUTHOR]

Sharing resources in hierarchical real-time systems implemented with reservation servers requires the adoption of special budget management protocols that preserve the bandwidth allocated to a specific component. In addition, blocking times must be accurately estimated to guarantee both the global feasibility of all the servers and the local schedulability of applications running on each component. This paper presents two new local schedulability tests to verify the schedulability of real-time applications running on reservation servers under fixed priority and EDF local schedulers. Reservation servers are implemented with the BROE algorithm. A simple extension to the SRP protocol is also proposed to reduce the blocking time of the server when accessing global resources shared among components. The performance of the new schedulability tests are compared with other solutions proposed in the literature, showing the effectiveness of the proposed improvements. Finally, an implementation of the main protocols on a lightweight RTOS is described, highlighting the main practical issues that have been encountered. [ABSTRACT FROM AUTHOR]

With the rapid proliferation of RFID technologies, RFID has been introduced into applications such as inventory and sampling inspection. Conventionally, in RFID systems, the reader usually identifies all the RFID tags in the interrogation region with the maximum power. However, some applications may only need to identify the tags in a specified area, which is usually smaller than the reader’s default interrogation region. An example could be identifying the tags in a box, while ignoring the tags out of the box. In this paper, we respectively present two solutions to identify the tags in the specified area. The principle of the solutions can be compared to the picture-taking process of an auto-focus camera, which firstly focuses on the target automatically and then takes the picture. Similarly, our solutions first focus on the specified area and then shoot the tags. The design of the two solutions is based on the extensive empirical study on RFID tags. Realistic experiment results show that our solutions can reduce the execution time by $44$ percent compared to the baseline solution, which identifies the tags with maximum power. Furthermore, we improve the proposed solutions to make them work well in more complex environments. [ABSTRACT FROM AUTHOR]

DRAM is widely adopted as a cache for secondary storage due to its small access latency. Compared with DRAM, PRAM draws a lot of attention recently, since it provides higher density and has no need to refresh the capacitor charge periodically. The non-volatile nature of PRAM can even reduce compulsory miss, which cannot be avoided by DRAM cache. However, PRAM cache cannot replace DRAM cache due to its endurance issue. Thus DRAM/PRAM hybrid cache becomes a good alternative for traditional DRAM cache. Least recently used (LRU) replacement algorithm and CLOCK-Pro algorithm work well for traditional DRAM cache. But these algorithms shall not be directly applied to DRAM/PRAM hybrid cache since the characteristics of PRAM are not considered. This paper proposed a double circular caching scheme (DCCS) to manage DRAM/PRAM hybrid cache. In our scheme, cached data migrate between DRAM cache and PRAM cache adaptively to achieve good hit ratio while frequent writes to PRAM cache are avoided for endurance concern. The experimental results showed that our scheme can reduce up to 87.10 percent PRAM write accesses for read-intensive access pattern and up to 44.90 percent energy consumption for write-intensive access pattern, compared with other caching schemes. [ABSTRACT FROM PUBLISHER]

Massive computation power and storage capacity of cloud computing systems enable users to either store large generated scientific datasets in the cloud or delete and then regenerate them whenever reused. Due to the pay-as-you-go model, the more datasets we store, the more storage cost we need to pay, alternatively, we can delete some generated datasets to save the storage cost but more computation cost is incurred for regeneration whenever the datasets are reused. Hence, there should exist a trade-off between computation and storage in the cloud, where different storage strategies lead to different total costs. The minimum cost, which reflects the best trade-off, is an important benchmark for evaluating the cost-effectiveness of different storage strategies. However, the current benchmarking approach is neither efficient nor practical to be applied on the fly at runtime. In this paper, we propose a novel Partitioned Solution Space based approach with efficient algorithms for dynamic yet practical on-the-fly minimum cost benchmarking of storing generated datasets in the cloud. In this approach, we pre-calculate all the possible minimum cost storage strategies and save them in different partitioned solution spaces. The minimum cost storage strategy represents the minimum cost benchmark, and whenever the datasets storage cost changes at runtime in the cloud (e.g. new datasets are generated and/or existing datasets’ usage frequencies are changed), our algorithms can efficiently retrieve the current minimum cost storage strategy from the partitioned solution space and update the benchmark. By dynamically keeping the benchmark updated, our approach can be practically utilised on the fly at runtime in the cloud, based on which the minimum cost benchmark can be either proactively reported or instantly responded upon request. Case studies and experimental results based on Amazon cloud show the efficiency, scalability and practicality of our approach. [ABSTRACT FROM AUTHOR]

In peer-to-peer file sharing systems, file replication helps to avoid overloading file owners and improve file query efficiency. There exists a tradeoff between minimizing the number of replicas (i.e., replication overhead) and maximizing the replica hit rate (which reduces file querying latency). More replicas lead to increased replication overhead and higher replica hit rates and vice versa. An ideal replication method should generate a low overhead burden to the system while providing low query latency to the users. However, previous replication methods either achieve high hit rates at the cost of many replicas or produce low hit rates. To reduce replicas while guaranteeing high hit rate, this paper presents SWARM, a file replication mechanism based on swarm intelligence. Recognizing the power of collective behaviors, SWARM identifies node swarms with common node interests and close proximity. Unlike most earlier methods, SWARM determines the placement of a file replica based on the accumulated query rates of nodes in a swarm rather than a single node. Replicas are shared by the nodes in a swarm, leading to fewer replicas and high querying efficiency. In addition, SWARM has a novel consistency maintenance algorithm that propagates an update message between proximity-close nodes in a tree fashion from the top to the bottom. Experimental results from the real-world PlanetLab testbed and the PeerSim simulator demonstrate the effectiveness of the SWARM mechanism in comparison with other file replication and consistency maintenance methods. SWARM can reduce querying latency by 40-58 percent, reduce the number of replicas by 39-76 percent, and achieves more than 84 percent higher hit rates compared to previous methods. It also can reduce the consistency maintenance overhead by 49-99 percent compared to previous consistency maintenance methods. [ABSTRACT FROM AUTHOR]

Increasing geographical spreads of modern distributed interactive applications (DIAs) make distributed server deployment vital for combating network latency and improving the interactivity among participants. In this paper, we investigate the server provisioning problem that concerns where to place servers for DIAs. We formulate the server provisioning problem with an objective of reducing the network latency involved in the interaction between participants. We prove that the problem is NP-hard under several scenarios. We analyze the performance of the classical $k$ -median server placement for DIAs and propose a new greedy server provisioning heuristic for DIAs. Theoretical analysis shows that the approximation ratio of the proposed greedy algorithm is much lower than that of the $k$ -median placement. Experiments using real Internet latency data also show that our proposed algorithm significantly outperforms the $k$ -median and other baseline server placements. [ABSTRACT FROM AUTHOR]

This paper proposes a computational method for 2D 8×8 DCT based on algebraic integers. The proposed algorithm is based on the Loeffler 1D DCT algorithm, and it is shown to operate with exact computation—i.e., error-free arithmetic—up to the final reconstruction step (FRS). The proposed algebraic integer architecture maintains error-free computations until an entire block of DCT coefficients having size 8×8 is computed, unlike algorithms in the literature which claim to be error-free but in fact introduce arithmetic errors between the column- and row-wise 1D DCT stages in a 2D DCT operation. Fast algorithms are proposed for the final reconstruction step employing two approaches, namely, the expansion factor and dyadic approximation. A digital architecture is also proposed for a particular FRS algorithm, and is implemented on an FPGA platform for on-chip verification. The FPGA implementation operates at 360 MHz, and is capable of a real-time throughput of $3.6\cdot 10^8$ 2D DCTs of size 8×8 every second, with corresponding pixel rate of $2.3\cdot 10^{10}$ pixels per second. The digital architecture is synthesized using 180 nm CMOS standard cells and shows a chip area of 7.41 mm $^2$ . The CMOS design is predicted to operate at 893 MHz clock frequency, at a dynamic power consumption 13.22 mW/MHz $\cdot$ V $_{sup}^2$ . [ABSTRACT FROM AUTHOR]

The cube attack is a powerful cryptanalytic technique and is especially powerful against stream ciphers. Since we need to analyze the complicated structure of a stream cipher in the cube attack, the cube attack basically analyzes it by regarding it as a blackbox. Therefore, the cube attack is an experimental attack, and we cannot evaluate the security when the size of cube exceeds an experimental range, e.g., 40. In this paper, we propose cube attacks on non-blackbox polynomials. Our attacks are developed by using the division property, which is recently applied to various block ciphers. The clear advantage is that we can exploit large cube sizes because it never regards the cipher as a blackbox. We apply the new cube attack toTrivium, Grain128a, ACORN and Kreyvium. As a result, the secret keys of 832-roundTrivium, 183-round Grain128a, 704-round ACORN and 872-round Kreyvium are recovered. These attacks are the current best key-recovery attack against these ciphers. [ABSTRACT FROM AUTHOR]

The reconfigurable mesh is a parallel model of computation, which exploits a massive amount of rather simple processing elements connected through a reconfigurable interconnection network. During the last decades, the model received strong interest and many researchers have devised algorithms for it. However, most of this work focuses on theoretical aspects. Due to some idealistic modeling assumptions only a few attempts have been made to implement the model and to study the practical use of reconfigurable meshes. In this paper, we leverage the reconfigurable mesh model to study potential architectures and programming models for future many-cores. We design a reconfigurable mesh in form of a scalable soft core array with a reconfigurable interconnect and implement it on FPGA technology in order to create a prototype platform. We present an overall hardware/software tool flow for generating and programming reconfigurable mesh prototypes. The new language ARMLang and a corresponding compiler facilitate the programming of the massively parallel processor arrays. To our knowledge, this work is the first practical study of word-level reconfigurable meshes. To analyze the performance of our implementation we study four algorithmic kernels from the application domains arithmetic, sorting, graph algorithms and imaging. For each kernel, we devise a reconfigurable mesh program in ARMLang, compile it to our soft core array and measure its runtime depending on the mesh size. Then, we compare the runtimes to two sequential implementations of the algorithms, which are executed on two single core systems. The results show that many-cores leveraging the reconfigurable mesh model can efficiently use a vast number of processing elements and that, for the chosen algorithms, they come close to optimally parallelized programs. [ABSTRACT FROM AUTHOR]

This paper presents an instruction scheduling algorithm for clustered very long instruction words (VLIW) architectures. It exploits a path-dividing-based technique to decide a more appropriate processing order of instructions, and utilizes a more global view to generate the scheduling result by simultaneously considering the influence of both data dependence relations between instructions and distribution of instructions among clusters. The algorithm is composed of two stages. The first stage virtually schedules all the instructions based on the path-dividing technique. The cluster virtually assigned in the first stage is delivered to the second stage. While the cycle virtually scheduled in the first stage is only used in this stage for the purpose of taking into account the implications between cluster assignment and cycle scheduling. The second stage performs actual scheduling according to the cluster assignment decisions made in the first stage and generates final scheduling results. The proposed algorithm is implemented and evaluated with benchmarks extracted from UTDSP and MediaBench. Results show that the improvement is impressive. Besides producing a large reduction in energy consumption, the algorithm can also make a remarkably performance speed-up. The average energy consumption ranges from 28.1% (4-Clusters) to 37.3% (8-Clusters). And the average speed-up ranges from 29.9% (4-Clusters) to 39.1% (8-Clusters). [ABSTRACT FROM AUTHOR]

Finding \mbi k shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen’s algorithm and its variants have polynomial worst-case time complexity, but their average-case running time is very high. The heuristic algorithm MPS can run significantly faster in practice. However, it requires an excessive amount of memory space. In this paper, we provide a new heuristic algorithm that achieves high space efficiency while maintaining similar average-case running time. We first propose a sidetrack representation of path, with which a path can be stored in \mbi O\bf (1) space. We then show how to categorize a candidate path as either partial or complete, and restrict the number of paths added to the queue. In addition, we provide an empirical equation that can very accurately predict the \mbi kth shortest path length, provided that a much smaller number of shortest paths have been found. Extensive experiments prove that our algorithm can achieve an \mbi O(n) speedup in practice over Yen’s algorithm. In comparison with MPS, it runs up to three times faster and uses less space by an order of magnitude. [ABSTRACT FROM AUTHOR]

Ternary content-addressable memory (TCAM) is a simple hardware device for fast IP lookups that can perform a lookup per cycle. However, prefixes may be inserted into or deleted from the TCAM because of changes in Internet topology. Traditional TCAM coprocessors maintain the enclosure relationship among prefixes by using an extended binary trie and perform TCAM movements based on an update algorithm (e.g., CAO_OPT) which runs on a local CPU to maintain the speed and correctness of the TCAM search process. In this paper, we propose a memory-efficient TCAM coprocessor architecture for updates that require only small memory size compared with the extended binary trie. The average number of TCAM movements per update is almost the same as that of CAO_OPT. However, the time to compute how to move TCAM entries in the proposed TCAM coprocessor is less than that in CAO_OPT. Only a small part of total TCAM search cycles is used to complete our update process. The proposed TCAM architecture can also be made smaller and faster because large off-chip memory for the extended binary trie and a local CPU are no longer necessary. [ABSTRACT FROM PUBLISHER]

A key challenge in chip multiprocessor (CMP) design is to optimize the performance within a power budget limited by the CMP’s cooling, packaging, and power supply capacities. Most existing solutions rely solely on dynamic voltage and frequency scaling (DVFS) to adapt the power consumption of CPU cores, without coordinating with the last-level on-chip (e.g., L2) cache. This paper proposes DPPC, a chip-level power partitioning and control strategy that can dynamically and explicitly partition the chip-level power budget among different CPU cores and the shared last-level cache in a CMP based on the workload characteristics measured online. DPPC features a novel performance-power model and an online model estimator to quantitatively estimate the performance contributed by each core and the cache with their respective local power budgets. DPPC then re-partitions the chip-level power budget among them for optimized CMP performance. The partitioned local power budgets for the CPU cores and cache are precisely enforced by power control algorithms designed rigorously based on feedback control theory. Our extensive experimental results demonstrate that DPPC achieves better CMP performance, within a given power budget, than several state-of-the-art power control solutions for both SPEC CPU2006 benchmarks and multi-threaded SPLASH-2 workloads. [ABSTRACT FROM PUBLISHER]

Mobile social networks (MSNs) are a kind of delay tolerant network that consists of lots of mobile nodes with social characteristics. Recently, many social-aware algorithms have been proposed to address routing problems in MSNs. However, these algorithms tend to forward messages to the nodes with locally optimal social characteristics, and thus cannot achieve the optimal performance. In this paper, we propose a distributed optimal Community-Aware Opportunistic Routing (CAOR) algorithm. Our main contributions are that we propose a home-aware community model, whereby we turn an MSN into a network that only includes community homes. We prove that, in the network of community homes, we can still compute the minimum expected delivery delays of nodes through a reverse Dijkstra algorithm and achieve the optimal opportunistic routing performance. Since the number of communities is far less than the number of nodes in magnitude, the computational cost and maintenance cost of contact information are greatly reduced. We demonstrate how our algorithm significantly outperforms the previous ones through extensive simulations, based on a real MSN trace and a synthetic MSN trace. [ABSTRACT FROM PUBLISHER]

Phase-change memory (PCM) is a promising alternative of DRAM. Nonetheless, it has a well-known problem that is the limited number of writes to storage cells. Thus, wear-leveling, which makes the writes uniform, is crucial to boost PCM’s lifetime. This paper proposes multi-way wear leveling (MWWL) to increase both endurance and security of PCM. MWWL can efficiently distribute writes to physical addresses uniformly from a multiple of ways while incurring little write overhead and almost no extra hardware overhead. More important, MWWL is a fundamental scheme that can be applied to existing leveling algorithms. As a case study, we extended a state-of-the-art technique, Security Refresh, to its multi-way version, Multi-Way Security Refresh (MWSR). The experimental results show that MWSR can achieve the same or better lifetime than that of the original two-level Security Refresh but with much less write overhead (from 11.7% down to 1.5%). [ABSTRACT FROM AUTHOR]

In application-specific SoCs, the irregularity of the topology ends up in a complex and customized implementation of the routing algorithm, usually relying on routing tables implemented with memory structures at source end nodes. As system size increases, the routing tables also increase in size with nonnegligible impact on power, area, and latency overheads. In this paper, we present a routing implementation for application-specific SoCs able to implement in an efficient manner (with no routing tables and using a small logic block in every switch) a deadlock-free routing algorithm in these irregular networks. The mechanism relies on a tool that maps the initial irregular topology of the SoC system into a logical regular structure where the mechanism can be applied. We provide details for both the mapping tool and the proposed routing mechanism. Evaluation results show the effectiveness of the mapping tool as well as the low area and timing requirements of the mechanism. With the mapping tool and the routing mechanism, complex irregular SoC topologies can now be supported without the need for routing tables. [ABSTRACT FROM PUBLISHER]

On-chip photonic waveguides have been proposed as a feasible replacement for the long interconnects that cause speed and power bottlenecks. Along with recent advancements in nanophotonic technologies, we believe that combining on-chip waveguides with high-radix Network on Chip (NoC) topologies is a promising way to improve NoC performance. In this paper, we propose the BufferLess phOtonic ClOs Network (BLOCON) to exploit silicon photonics. We propose a scheduling algorithm named Sustained and Informed Dual Round-Robin Matching (SIDRRM) to solve the output contention problem, a path allocation scheme named Distributed and Informed Path Allocation (DIPA) to solve the Clos network routing problem, and a methodology to achieve an optimal off-chip laser-power budget. In the simulation results, we show that with SIDRRM and DIPA, BLOCON improves the delay and on-chip power performance of the compared electrical and photonic NoC architectures over synthetic traffic patterns and SPLASH-2 traces. [ABSTRACT FROM PUBLISHER]

In heterogeneous networks, devices communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available ones, each device might establish several connections. A connection may be established when the devices at its endpoints share at least one active interface. In this paper, we consider two fundamental optimization problems. In the first one (Maximum Flow in Multi-Interface Networks, MFMI), we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In the second problem (Minimum-Cost Flow in Multi-Interface Networks, (MCFMI)), we look for activating the cheapest set of interfaces among a network to guarantee a minimum bandwidth $(B)$ of communication between two specified nodes. We show that MFMI is polynomially solvable while MCFMI is $(NP)$-hard even for a bounded number of different interfaces and bounded degree networks. Moreover, we provide polynomial approximation algorithms for MCFMI and exact algorithms for relevant subproblems. Finally, we experimentally analyze the proposed approximation algorithm, showing that in practical cases it guarantees a low approximation ratio. [ABSTRACT FROM PUBLISHER]

Reuse distance is an important metric for analytical estimation of cache miss rate. To find the miss rate of a particular cache, the reuse distance profile has to be measured for that particular level and configuration of the cache. Significant amount of simulation time and overhead can be reduced if we can find the miss rate of higher level cache like L2 cache from the RD profile with respect to a lower level cache (i.e., cache that is closer to the processor) such as L1. The objective of this paper is to give an analytical method to find the miss rate of L2 cache for various configurations from the RD profile with respect to L1 cache. We consider all three types of cache inclusion policies namely (i) Strictly Inclusive, (ii) Mutually Exclusive and (iii) Non-Inclusive Non-Exclusive policy. We first prove some general results relating the RD profile of L1 cache to that of L2 cache. We use probabilistic analysis for our derivations. We validate our model against simulations, using the multi-core simulator Sniper with the PARSEC and the SPLASH benchmark suites. [ABSTRACT FROM PUBLISHER]

Grids have been extensively deployed to handle various scientific and engineering applications that can be structured as bag-of-tasks (BoT). The scheduling of BoT applications on Grids is an important issue for achieving high performance. Grid scheduling involves a number of challenging issues, mainly due to the dynamic nature of the Grid. To deal with this dynamic nature, in this paper, we propose an online scheduling algorithm called prudent algorithm with replication (PAR) for scheduling Grid applications. PAR is shown to prudently make scheduling decisions in such a way that it can tolerate inaccurate performance predictions. Another point to note is that PAR adopts task duplication as an attempt to reduce serious schedule increases. Moreover, since the applications to be performed may widely vary in terms of their required hardware and software, we also capture the loads' various processing requirements in our algorithms, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus, in our problem formulation each application can only be processed by certain processors as both the applications and processing nodes are heterogeneous. We then present a task selection policy, referred to as requirement-aware load selection (RALS) policy to handle the contention of multiple applications that have various processing requirements but share the same computing resources. Based on RALS and PAR, we develop two scheduling algorithms: requirement-aware prudent algorithm with replication (RAPAR), and requirement-aware knowledge-free algorithm with replication (RAKAR). RAPAR and RAKAR address the scheduling of multiple BoT applications with heterogeneous processing requirements on Grids. RAPAR works in scenarios where inaccurate performance prediction information is provided whereas RAKAR works without any prediction information. Performance evaluation results are presented to demonstrate the effectiveness and competitiveness of our approaches when compared to existing algorithms. [ABSTRACT FROM AUTHOR]