ALBERT

Beschreibung: Presents the table of contents for this issue of the magazine.

Beschreibung: Provides a listing of current committee members and society officers.

Beschreibung: Presents information on the conference venue.

Beschreibung: Presents information on the conference venue.

Beschreibung: The 2013 IEEE Radio and Wireless Week (RWW2013) technical program that forms the core of the week has expanded significantly since the first Radio and Wireless Symposium (RWS) in 1998. Over the years, this technical meeting has grown from a single conference, RWS, to a weeklong event, RWW, encompassing five conferences: the IEEE RWS, the IEEE Topical Meeting on Silicon Monolithic Integrated Circuits in Radio Frequency Systems (SiRF), the IEEE Topical Conference on Biomedical Wireless Technologies, Networks, and Sensing Systems (BioWireleSS), the IEEE Topical Conference on RF/Microwave Power Amplifiers (PAWR), and the IEEE Topical Conference on Wireless Sensors and Sensor Networks (WiSNet). The feature articles in this special issue represent the areas covered by the topical conferences BioWireleSS, PAWR, and WiSNet. No other conference brings together the core wireless technologies with this depth and breadth of applications. We hope you enjoy the feature articles and decide to join us at the next in Austin, 20??23 January 2013.

Beschreibung: On opening day, IEEE Radio and Wireless Week 2013 (RWW2013) will host a rump session "Tunable and Reconfigurable Radio Front Ends." On Monday, the RWW2013 will host two panel sessions during lunch: "Wireless Personal Area Networks?? and "Software Piracy." A rump session "Base Station Design Breakthrough Opportunities" will be held on Monday evening. Our Distinguished Lecturer series will start off the week on Monday morning. The plenary session will be held late Tuesday morning, 22 January. It will feature Dr. James Truchard, the cofounder and current president and CEO of National Instruments (NI). Complete information on the panel and focused sessions are available in the 2013 RWS technical program book later in this issue.

Beschreibung: Provides notice of upcoming conference events of interest to practitioners and researchers.

Beschreibung: Provides notice of upcoming conference events of interest to practitioners and researchers.

Beschreibung: Provides a listing of upcoming conference events of interest to practitioners and researchers.

Beschreibung: Prospective authors are requested to submit new, unpublished manuscripts for inclusion in the upcoming event described in this call for papers.

Beschreibung: Industrial automation today is an essential technology underlying our modern society. Advanced positioning and sensor feedback tasks in automation processes often require distance displacement detection, e.g., to measure and track the movement of robots. Furthermore, the detection of mechanical stress in complex industrial machinery through an accurate vibration analysis is often a task of major interest. Therefore, high-resolution distance measurements with short- and long-range positioning are important for a large number of sensing applications and can also be used as a precondition for vibrometer applications. Several automation technologies rely on high precision positioning sensors to track linear as well as rotational movements of various machinery.

Beschreibung: Provides a listing of upcoming conference events of interest to practitioners and researchers.

Beschreibung: Chireix. Doherty. Kahn. These names are widely heard throughout the power amplifier (PA) industry today when the discussion turns to high-power, high-efficiency amplifiers. When one hears “the Doherty PA is operating at 6 dB output power backoff (OBO) with a 6.5 dB peak to average power ratio,” most PA design engineers are interested in these and other important performance specifications, but what about the names behind the amplifiers themselves. Who were these engineers who have widely used communications amplifiers named after them? This article will attempt to shed a little light on the history behind these engineers and to provide an historical context behind their discoveries.

Beschreibung: Silicon (Si) ICs for microwave and millimeterwave (mm-wave) applications [monolithic microwave integrated circuits (MMICs)] are very much mainstream now, a radically different situation from 20 years ago when GaAs ruled supreme. They owe their popularity to dramatic advances in CMOS technology and very much to the advent and speedy market introduction of the Si/SiGe heterojunction bipolar transistor (HBT): the first SiGe ICs for applications in digital enhanced cordless telecommunications (DECT) cordless telephones, which appeared on the market in 1998 [1], a little more than ten years after the realization of the first Si/SiGe HBTs.

Beschreibung: Sudden cardiac arrest (SCA) is one of the leading causes of death worldwide [1]. Studies have shown that roughly 90% of all patients suffering from SCAs die due to ventricular fibrillation. This phenomenon is best described as an electrical chaos in the myocardium leading to fast but at the same time very short movements of the muscle. This results in a total collapse of the blood circulation and after 35 min, the death of gray matter. Without any external help, this will lead to death. In the United States, for instance, 325,000 people are affected each year [1]. It is indisputable that the quality of a cardiopulmonary resuscitation (CPR) can make the difference between life and death. In 2010, the European Resuscitation Council (ERC) as well as the American Heart Association (AHA) submitted official guidelines for resuscitation [2]. According to the ERC and further research results, the basic life support can be significantly improved by a feedback system. The recommendation for CPR feedback systems has subsequently been adopted by the German Medical Association (GMA). A CPR feedback system gives a response to the first aider about the quality of the resuscitation (compression depth and rate) [2].

Beschreibung: What is the probability that the execution state of a given microprocessor running a given application is correct, in a certain working environment with a given soft-error rate? Trying to answer this question using fault injection can be very expensive and time consuming. This paper proposes the baseline for a new methodology, based on microprocessor error probability profiling, that aims at estimating fault injection results without the need of a typical fault injection setup. The proposed methodology is based on two main ideas: a one-time fault-injection analysis of the microprocessor architecture to characterize the probability of successful execution of each of its instructions in presence of a soft-error, and a static and very fast analysis of the control and data flow of the target software application to compute its probability of success. The presented work goes beyond the dependability evaluation problem; it also has the potential to become the backbone for new tools able to help engineers to choose the best hardware and software architecture to structurally maximize the probability of a correct execution of the target software.

Beschreibung: Locality is often characterized by working sets, defined by Denning as the set of distinct addresses referenced within a certain window of time. This definition ignores the fact that dramatic differences exist between the usage patterns of frequently used data and transient data. We therefore propose to extend Denning's definition with that of core working sets, which identify blocks that are used most frequently and for the longest time. The concept of a core motivates the design of dual-cache structures that provide special treatment for the core. In particular, we present a probabilistic locality predictor for L1 caches that leverages the skewed popularity of blocks to distinguish transient cache insertions from more persistent ones. We further present a dual L1 design that inserts only frequently used blocks into a low-latency, low-power, direct-mapped main cache, while serving others from a small fully associative filter. To reduce the prohibitive cost of such a filter, we present a content addressable memory design that eliminates most of the costly lookups using a small auxiliary lookup table. The proposed design enables a 16K direct-mapped L1 cache, augmented with a small 2K filter, to outperform a 32K 4-way cache, while at the same time consumes 70-80 percent less dynamic power and 40 percent less static power.

Beschreibung: On-chip trigger units are employed for detecting events of interest during post-silicon validation and debugging. Their implementation constrains the trigger conditions that can be programmed at runtime. It is often the case that some trigger events of interest, which were not accounted for during design time, cannot be detected due to the constraints imposed by the hardware implementation of the trigger units. To address this issue, we present architectural features that can be included into the trigger units and discuss the algorithmic approach for automatically mapping trigger conditions onto the trigger units.

Beschreibung: In this work, we propose a new decimal redundant CORDIC algorithm to manage transcendental functions, using floating-point representation. The algorithms determine the direction of the elementary rotation using sign estimations. Unlike binary redundant CORDIC, repetition of iterations are not required to ensure convergence since novel decimal codes have been carefully selected with sufficient redundancy to prevent any repetition. The algorithms are mapped to a low-cost unit based on a decimal 3-2 carry-save adder which can also be used as a floating-point decimal division unit. Compared to current decimal floating-point units, the implementation of our algorithm involves minor modifications of the native hardware, while providing a huge set of elementary functions.

Beschreibung: We study the online bicriteria load balancing problem in this paper. We choose a system of distributed homogeneous file servers located in a cluster as the scenario and propose three online approximate solutions for balancing their loads and required storage spaces upon placements. We first revisit the best existing solution for simple placement (i.e., without replication and reallocation), and rewrite it in our first algorithm by imposing some flexibilities. Our second algorithm is to apply document replication. The upper bound of load is significantly reduced, without sacrificing that of the storage space. This upper bound contains at least one special case which can never be outperformed by any online simple placement algorithms. Lastly, we show that there exists an online algorithm which allows very little document reallocation, but gives an upper bound result on the load and storage space, which is never reachable by any online algorithms for simple placement. The time complexities of the first two algorithms are in O(log M), and the last algorithm runs in O(log MN) time, where M is the number of servers, and N is the number of existing documents.

Beschreibung: 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.

Beschreibung: Although snoop-based coherence protocols provide fast cache-to-cache transfers with a simple and robust coherence mechanism, scaling the protocols has been difficult due to the overheads of broadcast snooping. In this paper, we propose a coherence filtering technique called subspace snooping, which stores the potential sharers of each memory page in the page table entry. By using the sharer information in the page table entry, coherence transactions for a page generate snoop requests only to the subset of nodes in the system. However, the coherence subspace of a page may evolve, as the phases of applications may change or the operating system may migrate threads to different nodes. To adjust subspaces dynamically, subspace snooping supports two different shrinking mechanisms, which remove obsolete nodes from subspaces. Among the two shrinking mechanisms, subspace snooping with safe shrinking can be integrated to any type of coherence protocols and network topologies, as it guarantees that a subspace always contains the precise sharers of a page. Speculative shrinking breaks the subspace superset property, but achieves better snoop reductions than safe shrinking. We evaluate subspace snooping with Token Coherence on unordered mesh networks. Subspace snooping reduces 58 percent of snoops on average for a set of parallel scientific and server workloads, and 87 percent for our multiprogrammed workloads.

Beschreibung: Ternary content addressable memory (TCAM) is a key component in various digital systems due to its fast lookup operation. Symmetric and asymmetric TCAM cells are two widely used cells for implementing a TCAM array. This paper presents several comparison fault models of TCAMs with asymmetric cells based on electrical defects. Some new comparison faults which do not exist in a TCAM with symmetric cells are found. One march-like test algorithm T_{rm AChbox{-}H} is also proposed to cover the defined comparison faults. The T_{rm AChbox{-}H} consists of 8N Write operations and (3N+2B) Compare operations for an NtimesB-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 D_{rm AChbox{-}H} requires 5N Write operations, 3N Erase operations, and (5N+2B) Compare operations to distinguish 100 percent comparison faults for a TCAM with Hit output only. The second diagnosis algorithm D_{rm AChbox{-}P} requires 3N Write operations, 1N Erase operations, and (5N+2B) Compare operations to distinguish 100 percent comparison faults for a TCAM with Hit and priority address encoder outputs.

Beschreibung: The fundamental challenge of garbage collector (GC) design is to maximize the recycled space with minimal time overhead. For efficient memory management, in many GC designs the heap is divided into large object space (LOS) and normal object space (non-LOS). When either space is full, garbage collection is triggered even though the other space may still have plenty of room, thus leading to inefficient space utilization. Also, space partitioning in existing GC designs implies different GC algorithms for different spaces. This not only prolongs the pause time of garbage collection, but also makes collection inefficient on multiple spaces. To address these problems, we propose Packer, a parallel garbage collection algorithm based on the novel concept of virtual spaces. Instead of physically dividing the heap into multiple spaces, Packer manages multiple virtual spaces in one physical space. With multiple virtual spaces, Packer offers efficient memory management. With one physical space, Packer avoids the problem of an inefficient space utilization. To reduce the garbage collection pause time, we also propose a novel parallelization method that is applicable to multiple virtual spaces. Specifically, we reduce the compacting GC parallelization problem into a discreted acyclic graph (DAG) traversal parallelization problem, and apply it to both normal and large object compaction.

Beschreibung: A major challenge in the design of multicore embedded systems is how to tackle the communications among tasks with performance requirements and precedence constraints. In this paper, we consider the problem of scheduling real-time tasks over multilayer bus systems with the objective of minimizing the communication cost. We show that the problem is cal {NP}-hard and determine the best possible approximation ratio of approximation algorithms. First, we propose a polynomial-time optimal algorithm for a restricted case where one multilayer bus, and the unit execution time and communication time are considered. The result is then extended as a pseudopolynomial-time optimal algorithm to consider multiple multilayer buses with arbitrary execution and communication times, as well as different timing constraints and objective functions. We compare the performance of the proposed algorithm with that of some popular heuristics, and provide further insights into the multilayer bus system design.

Beschreibung: As file systems reach the petabytes scale, users and administrators are increasingly interested in acquiring high-level analytical information for file management and analysis. Two particularly important tasks are the processing of aggregate and top-k queries which, unfortunately, cannot be quickly answered by hierarchical file systems such as ext3 and NTFS. Existing preprocessing-based solutions, e.g., file system crawling and index building, consume a significant amount of time and space (for generating and maintaining the indexes) which in many cases cannot be justified by the infrequent usage of such solutions. In this paper, we advocate that user interests can often be sufficiently satisfied by approximate—i.e., statistically accurate—answers. We develop Glance, a just-in-time sampling-based system which, after consuming a small number of disk accesses, is capable of producing extremely accurate answers for a broad class of aggregate and top-k queries over a file system without the requirement of any prior knowledge. We use a number of real-world file systems to demonstrate the efficiency, accuracy, and scalability of Glance.

Beschreibung: Global Signal Vulnerability (GSV) analysis is a novel method for assessing the susceptibility of modern microprocessor state elements to failures in the field of operation. In order to effectively allocate design for reliability resources, GSV analysis takes into account the high degree of architectural masking exhibited in modern microprocessors and ranks state elements accordingly. The novelty of this method lies in the way this ranking is computed. GSV analysis operates either at the Register Transfer (RT-) or at the Gate-Level, offering increased accuracy in contrast to methods which compute the architectural vulnerability of registers through high-level simulations on performance models. Moreover, it does not rely on extensive Statistical Fault Injection (SFI) campaigns and lengthy executions of workloads to completion in RT- or Gate-Level designs, which would make such analysis prohibitive. Instead, it monitors the behavior of key global microprocessor signals in response to a progressive stuck-at fault injection method during partial workload execution. Experimentation with the Scheduler and Reorder Buffer modules of an Alpha-like microprocessor and a modern Intel microprocessor corroborates that GSV analysis generates a near-optimal ranking, yet is several orders of magnitude faster than existing RT- or Gate-Level approaches.

Beschreibung: This paper considers the problem of dynamic cluster reconfiguration for computation intensive services. In order to provide a quality-of-service in terms of overload probability, we formulate the problem of energy consumption as a constrained optimization problem, i.e., minimizing the number of active servers to reduce the energy consumption while keeping the overload probability below a desired threshold. An overload probability estimation model is derived by applying large deviation principle, and an online measurement based algorithm is developed to decide the number of servers to power on/off, which makes decision based on current workload without any prior knowledge of the workload statistics. Moreover, the proposed dynamic cluster reconfiguration algorithm iteratively adjusts the number of the active servers, instead of directly determining the number of active servers that is hard to guarantee optimality for the nonstationary workloads. Since the distribution of the workloads among the servers has an impact on potential active servers to turn off, a server scheduling strategy is proposed to collaborate with the proposed decision algorithm to achieve better energy conservation. In order to provide an integrated solution, we present an event model-based implementation to demonstrate the practical application of the proposed approach. Finally, we evaluate the performance of the scheme by using real workloads. The experimental results show the adaptability of the proposed approach to the variations in the workload and robustness of quality-of-service for nonstationary workloads.

Beschreibung: In this work, we assume a geographic area populated by tiny sensors, each perhaps no larger than a dime. In order to save their energy, the sensors spend most of their lifetime in sleep mode and wake up for short periods of time to participate in various tasks supportive of the overall mission of the network. We assume that the tasks to be performed stipulate QoS parameters expressed in terms of the minimum number of sensors that need to monitor their sensing area. Since only awake sensors participate in tasks, the Effective Sensor Density (ESD), defined as the density of awake sensors, is an important network parameter that obviously depends on the sleep schedules adopted in the network. The first main contribution of this work is to provide a mathematical analysis of ESD from the perspective of the monitored events. We also provide design guidelines to determine deployment-time sensor density and an associated sleep schedule that probabilistically keeps the ESD at a level needed by QoS requirements. We also propose a fully distributed sleep schedule which adaptively adjusts the duty cycles of sensors within the same sensing area based on the relative difference in their remaining energy budget. The main advantage of the proposed adaptive scheme is to balance energy consumption among sensors, thus promoting the functional longevity of the sensor network without adversely affecting the ESD.

Beschreibung: Limiting the peak power consumption of chip multiprocessors (CMPs) has recently received a lot of attention. In order to enable chip-level power capping, the peak power consumption of last-level (e.g., L2) on-chip caches in a CMP often needs to be constrained by dynamically transitioning selected cache banks into low-power modes. However, dynamic cache resizing for power capping may cause undesired long cache access latencies, and even thread starving and thrashing, for the applications running on the CMP. In this paper, we propose a novel cache management strategy that can limit the peak power consumption of L2 caches and provide fairness guarantees, such that the cache access latencies of the application threads coscheduled on the CMP are impacted more uniformly. Our strategy is also extended to provide differentiated cache latency guarantees that can help the OS to enforce the desired thread priorities at the architectural level and achieve desired rates of thread progress for coscheduled applications. Our solution features a two-tier control architecture rigorously designed based on advanced feedback control theory for guaranteed control accuracy and system stability. Extensive experimental results demonstrate that our solution can achieve the desired cache power capping, fair or differentiated cache sharing, and power-performance tradeoffs for many applications.

Beschreibung: Many network processing applications require wirespeed access to large data structures or a large amount of packet and flow-level data. Therefore, it is essential for the memory system of a router to be able to support both read and write accesses to such data at link speeds. As link speeds continue to increase, router designers are constantly grappling with the unfortunate trade-offs between the speed and cost of SRAM and DRAM. The capacity of SRAMs is woefully inadequate in many cases and it proves too costly to store large data structures entirely in SRAM, while DRAM is viewed as too slow for providing wirespeed updates at such high speed. In this paper, we analyze a robust pipelined memory architecture that can emulate an ideal SRAM by guaranteeing with very high probability that the output sequence produced by the pipelined memory architecture is the same as the one produced by an ideal SRAM under the same sequence of memory read and write operations, except time shifted by a fixed pipeline delay of Delta. Given a fixed pipeline delay abstraction, no interrupt mechanism is required to indicate when read data are ready or a write operation has completed, which greatly simplifies the use of the proposed solution. The design is based on the interleaving of DRAM banks together with the use of a reservation table that serves in part as a data cache. In contrast to prior interleaved memory solutions, our design is robust under all memory access patterns, including adversarial ones, which we demonstrate through a rigorous worst case theoretical analysis using a combination of convex ordering and large deviation theory.

Beschreibung: Coverage problem is a fundamental issue in wireless ad hoc and sensor networks. Previous techniques for coverage scheduling often require accurate location information or range measurements, which cannot be easily obtained in resource-limited ad hoc and sensor networks. Recently, a method based on algebraic topology is proposed to achieve coverage verification using only connectivity information. The topological method sheds some light on the issue of location-free coverage. Unfortunately, the needs of centralized computation and rigorous restriction on sensing and communication ranges greatly limit the applicability in practical large-scale distributed sensor networks. In this work, we make the first attempt toward establishing a graph theoretical framework for connectivity-based coverage with configurable coverage granularity. We propose a novel coverage criterion and scheduling method based on cycle partition. Our method is able to construct a sparse coverage set in a distributed manner, using purely connectivity information. Compared with existing methods, our design has a particular advantage, which permits us to configure or adjust the quality of coverage by adequately exploiting diverse sensing ranges and specific requirements of different applications. We formally prove the correctness and evaluate the effectiveness of our approach through extensive simulations and comparisons with the state-of-the-art approaches.

Beschreibung: Compression, as a popular technique to reduce data size by exploiting data redundancy, can be used in delay sensitive wireless sensor networks (WSNs) to reduce end-to-end packet delay as it can reduce packet transmission time and contention on the wireless channel. However, the limited computing resources at sensor nodes make the processing time of compression a nontrivial factor in the total delay a packet experiences and must be carefully examined when adopting compression. In this paper, we first study the effect of compression on data gathering in WSNs under a practical compression algorithm. We observe that compression does not always reduce packet delay in a WSN as commonly perceived, whereas its effect is jointly determined by the network configuration and hardware configuration. Based on this observation, we then design an adaptive algorithm to make online decisions such that compression is only performed when it can benefit the overall performance. We implement the algorithm in a completely distributed manner that utilizes only local information of individual sensor nodes. Our extensive experimental results show that the algorithm demonstrates good adaptiveness to network dynamics and maximizes compression benefit.

Beschreibung: The IEEE P1687 (IJTAG) standard proposal aims at providing a standardized interface between the IEEE Standard 1149.1 test access port (TAP) and on-chip embedded test, debug and monitoring logic (instruments), such as scan chains and temperature sensors. A key feature in P1687 is to include Segment Insertion Bits (SIBs) in the scan path to allow flexibility both in designing the instrument access network and in scheduling the access to instruments. This paper presents algorithms to compute the overall access time (OAT) for a given P1687 network. The algorithms are based on analysis for flat and hierarchical network architectures, considering two access schedules, i.e., concurrent schedule and sequential schedule. In the analysis, two types of overhead are identified, i.e., network configuration data overhead and JTAG protocol overhead. The algorithms are implemented and employed in a parametric analysis and in experiments on realistic industrial designs.

Beschreibung: This paper addresses the problem of determining the feasible speeds and voltages of multicore processors with hard real-time and temperature constraints. This is an important problem, which has applications in time-critical execution of programs like audio and video encoding on application-specific embedded processors. Two problems are solved. The first is the computation of the optimal time-varying voltages and speeds of each core in a heterogeneous multicore processor, that minimize the makespan—the latest completion time of all tasks, while satisfying timing and temperature constraints. The solution to the makespan minimization problem is then extended to the problem of determining the feasible speeds and voltages that satisfy task deadlines. The methods presented in this paper also provide a theoretical basis and analytical relations between speed, voltage, power and temperature, which provide greater insight into the early-phase design of processors and are also useful for online dynamic thermal management.

Beschreibung: This paper presents a novel test point insertion method for pseudorandom built-in self-test (BIST) to reduce the area overhead. The proposed method replaces dedicated flip-flops for driving control points by existing functional flip-flops. For each control point, candidate functional flip-flops are identified by using logic cone analysis that investigates the path inversion parity, logical distance, and reconvergence from each control point. Four types of new control point structures are introduced based on the logic cone analysis results to avoid degrading the testability. Experimental results indicate that the proposed method significantly reduces test point area overhead by replacing the dedicated flip-flops and achieves essentially the same fault coverage as conventional test point implementations using dedicated flip-flops driving the control points.

Beschreibung: We address content discovery in wireless networks with infrastructure, where mobile nodes store, advertise, and consume content while Broker entities running on infrastructure devices let demand and offer meet. We refer to this paradigm as match-making, highlighting its features within the confines of the standard publish-and-subscribe paradigm. We study its performance in terms of success probability of a content query, a parameter that we strive to increase by acting as follows: 1) We design a credit-based scheme that makes it convenient for rational users to provide their content (thus discouraging free-riding behavior), and it guarantees them a fair treatment. 2) We increase the availability of either popular or rare content, through an efficient caching scheme. 3) We counter malicious nodes whose objective is to disrupt the system performance by not providing the content they advertise. To counter the latter as well as free riders, we introduce a feedback mechanism that enables a Broker to tell apart well- and misbehaving nodes in a very reliable manner, and to ban the latter. The properties of our match-making scheme are analyzed through game theory. Furthermore, via ns-3 simulations, we show its resilience to different attacks by malicious users and its good performance with respect to other existing solutions.

Beschreibung: With the popularity of wireless devices and the increasing demand of network applications, it is emergent to develop more effective communications paradigm to enable new and powerful pervasive applications, and to allow services to be accessed anywhere, at anytime. However, it is extremely challenging to construct efficient and reliable networks to connect wireless devices due to the increasing communications need and the dynamic nature of wireless communications. In order to improve transmission throughput, many efforts have been made in recent years to reduce traffic and hence transmission collisions by constructing backbone networks with the minimum size. However, many other important issues need to be considered. Instead of simply minimizing the number of backbone nodes or supporting some isolated network features, in this work, we exploit the use of algebraic connectivity to control backbone network topology design for concurrent improvement of backbone network robustness, capacity, stability and routing efficiency. In order to capture other network features, we provide a general cost function and introduce a new metric, connectivity efficiency, to trade off algebraic connectivity and cost for backbone construction. We formally prove the problem of formulating a backbone network with the maximum connectivity efficiency that is NP-hard, and design both centralized and distributed algorithms to build more robust and efficient backbone infrastructure to better support the application needs. We have made extensive simulations to evaluate the performance of our work. Compared to literature studies on constructing wireless backbone networks, the incorporation of algebraic connectivity into the network performance metric could achieve much higher throughput and delivery ratio, and much lower end-to-end delay and routing distances under all test scenarios. We hope our work could stimulate more future research in designing more reliable and efficient networks. Our perf- rmance studies demonstrate that, compared to peer work, the incorporation of algebraic connectivity into network performance metric could achieve much higher throughput and delivery ratio, and much lower end-to-end delay and routing distances under all test scenarios. We hope our work could stimulate more future research in designing more reliable and efficient networks.

Beschreibung: Provides instructions and guidelines to prospective authors who wish to submit manuscripts.

Beschreibung: Financial transactions are specified in decimal arithmetic. Until the introduction of IEEE 754-2008, specialized software/hardware routines were used to perform these transactions but it incurred a penalty on performance. In this paper, we show that if binary arithmetic is used to emulate decimal operations, then arbitrary error sequences can be generated by carefully chosen sequences of transactions which can lead to monotonically increasing/decreasing capitalization errors. In addition, we describe methods for correctly performing basic decimal operations, such as addition, subtraction, multiplication, and division, on binary machines, which are not conformant with IEEE 754-2008 decimal floating point standard (ISO/IEC/IEEE 60559:2011), at high speed.

Beschreibung: The choice of radix is crucial for multivalued logic synthesis. Practical examples, however, reveal that it is not always possible to find the optimal radix when taking into consideration actual physical parameters of multivalued operations. In other words, each radix has its advantages and disadvantages. Our proposal is to synthesize logic in different radices, so it may benefit from their combination. The theory presented in this paper is based on Reed-Muller expansions over Galois field arithmetic. The work aims to first estimate the potential of the new approach and to second analyze its impact on circuit parameters down to the level of physical gates. The presented theory has been applied to real-life examples focusing on cryptographic circuits where Galois Fields find frequent application. The benchmark results show that the approach creates a new dimension for the trade-off between circuit parameters and provides information on how the implemented functions are related to different radices.

Beschreibung: Beginning with Amdahl's law, we derive a general objective function that links parallel processing performance gains at the system level, to energy and delay in the subsystem microarchitecture structures. The objective function employs parameterized models of computation and communication to represent the characteristics of processors, memories, and communications networks. The interaction of the latter microarchitectural elements defines global system performance in terms of energy-delay cost. Following the derivation, we demonstrate its utility by applying it to the problem of Chip Multiprocessor (CMP) architecture exploration. Given a set of application and architectural parameters, we solve for the optimal CMP architecture for six different architectural optimization examples. We find the parameters that minimize the total system cost, defined by the objective function under the area constraint of a single die. The analytical formulation presented in this paper is general and offers the foundation for the quantitative and rapid evaluation of computer architectures under different constraints including that of single die area.

Beschreibung: The problem of extracting the highest possible amount of key-related information using the lowest possible number of measurements is one of the central questions in side-channel attacks against embedded implementations of cryptographic algorithms. To address it, this work proposes a novel framework enhancing side-channel collision attacks with divide-and-conquer attacks such as differential power analysis (DPA). An information-theoretical metric is introduced for the evaluation of collision detection efficiency. Improved methods of dimension reduction for side-channel traces are developed based on a statistical model of euclidean distance. Experimental results confirm that DPA-combined collision attacks are superior to both DPA-only and collision-only attacks. The new methods of dimension reduction lead to further complexity improvements. All attacks are treated for the case of AES-128 and are practically validated on a widespread 8-bit RISC microcontroller.

Beschreibung: Multimedia streaming applications running on next-generation parallel multiprocessor arrays in sub-45 nm 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 runtime 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 multicore platform running representative multimedia applications. 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. The proposed policy can save up to 33 percent of energy with respect to the state-of-the-art policies and 65 percent of energy with respect to one variability-unaware task allocation policy while providing better QoS.

Beschreibung: A cut vertex is defined as a network node whose removal increases the number of network components. Failure of a cut vertex disconnects a network component and downgrades the network performance. Overlay networks are resilient to the failure of random nodes, but cut vertices that have been observed in real-world overlay traces make the network very vulnerable to well-constructed and targeted attacks. Traditional methods of detecting cut vertices are centralized and are very difficult, if not impossible, to be applied to large-scale and highly dynamic overlay networks. We aim to provide a practical solution by proposing a distributed mechanism that detects the cut vertices and neutralizes them to noncut vertices before they fail. The proposed mechanism not only minimizes the possibility of network decomposition on the cut vertex failure but also offloads the traffic that is handled by the cut vertices. We prove that our proposed method can correctly identify the cut vertices. We evaluate the performance of our design through trace-driven simulations. The results show that our method can successfully locate all cut vertices in the network and greatly offload the traffic processed by cut vertices.

Beschreibung: This paper proposes an analytical model for accurately predicting the impact of contention on cache miss rates. The focus is multiprogrammed workloads running on multithreaded manycore architectures. This work addresses a key challenge facing earlier cache contention models as the number of concurrent threads exceeds the associativity of shared caches. The memory access characteristics of individual applications are obtained in isolation by profiling their circular sequences and two new measures of access locality are proposed. An evaluation of this model in the context of a Niagara processor shows that it achieves an average 8.7 percent error in miss rate predictions which improves upon the best prior model by 48.1x. This paper also presents a novel Markov chain throughput model. When combining the contention model with the Markov chain model, throughput is estimated with an average error of 8.3 percent compared to detailed simulation. Moreover, the combined model tracks throughput sufficiently well to find the same optimized design point for application-specific workloads 65 times faster than detailed simulation. This paper also shows that the models accurately predict cache contention and throughput trends across various workloads on real hardware.

Beschreibung: For an undirected and weighted graph G=(V,E) and a terminal set Ssubseteq V, the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has important applications in design of survivable networks and fault-tolerant communication, and is known MAXSNP-hard , a harder subclass of NP-hard problems for which no polynomial-time approximation scheme (PTAS) is known. This paper presents an efficient algorithm of O(vert Vvert^{2}vert Svert^{3}) time for computing a 2-vertex connected Steiner network (2VSN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2VSMN). It compares favorably with the currently known 2--approximation solution to the 2VSMN problem based on that to the survivable network design problem], with a time complexity reduction of O(vert Vvert^{5}vert Evert^{7}) for strongly polynomial time and O(vert Vvert^{5}gamma ) for weakly polynomial time where gamma is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2VSN through progressive improvement on a set of vertex-disjoint shortest path pairs incident with each terminal of S. The algorithm can be directly deployed to solve the 2-edge connected SMN problem at the same approximation ratio within time O(vert Vvert^{2}vert Svert^{2}). To the best of our knowledge, this result presents currently the most efficient 2-approximation algorithm for the 2-connected Steiner minimal network problem.

Beschreibung: This paper proposes four logic-chain bridging fault models, which involve one net in the combinational logic and the other net in the scan chain. Test results of logic-chain bridging faults, unlike existing scan chain fault models, depend on the previous scan inputs as well as primary inputs. A bridging pair extraction algorithm is proposed to quickly extract bridging pairs from the layout. The paper proposed two sets of structural reduction techniques so that runtime is very short. Experimental results on ISCAS benchmark circuits show that, on the average, logic-chain bridging faults can be diagnosed within an accuracy of four bridging pairs. The techniques are still applicable when there are only 10 failing patterns due to limited ATE failure memory. This paper demonstrates the feasibility to diagnose logic-chain bridging faults by software.

Beschreibung: We present the design, implementation and evaluation of a high-performance architecture for regular expression matching (REM) on field-programmable gate array (FPGA). Each regular expression (regex) is first parsed into a concise token list representation, then compiled to a modular nondeterministic finite automaton (RE-NFA) using a modified version of the McNaughton-Yamada algorithm. The RE-NFA can be mapped directly onto a compact register-transistor level (RTL) circuit. A number of optimizations are applied to improve the circuit performance: 1) spatial stacking is used to construct an REM circuit processing mge 1 input characters per clock cycle; 2) single-character constrained repetitions are matched efficiently by parallel shift-register lookup tables; 3) complex character classes are matched by a BRAM-based classifier shared across regexes; 4) a multipipeline architecture is used to organize a large number of RE-NFAs into priority groups to limit the I/O size of the circuit. We implemented 2,630 unique PCRE regexes from Snort rules (February 2010) in the proposed REM architecture. Based on the place-and-route results from Xilinx ISE 11.1 targeting Virtex5 LX-220 FPGAs, the proposed REM architecture achieved up to 11 Gbps concurrent throughput for various regex sets and up to 2.67x the throughput efficiency of other state-of-the-art designs.

Beschreibung: Low-level computer vision algorithms have extreme computational requirements. In this work, we compare two real-time architectures developed using FPGA and GPU devices for the computation of phase-based optical flow, stereo, and local image features (energy, orientation, and phase). The presented approach requires a massive degree of parallelism to achieve real-time performance and allows us to compare FPGA and GPU design strategies and trade-offs in a much more complex scenario than previous contributions. Based on this analysis, we provide suggestions to real-time system designers for selecting the most suitable technology, and for optimizing system development on this platform, for a number of diverse applications.

Beschreibung: Fault-based attacks, which recover secret keys by deliberately introducing fault(s) in cipher implementations and analyzing the faulty outputs, have been proved to be extremely powerful. In this paper, we propose a novel Concurrent Error Detection (CED) scheme to counter fault-based attack against RSA by exploiting its multiplicative homomorphic property. Specifically, the proposed CED scheme verifies if Pi _{i = 1}^k E(m_i ) equiv E(Pi _{i = 1}^k m_i bmod n) (bmod n) where E could be either RSA encryption, or decryption, or signature, or verification process. Upon a mismatch, all the ciphertexts will be suppressed. The time overhead is 1/k and k can be used to trade-off the time overhead with memory overhead and output latency. Recognizing that an RSA device could be subject to a combination of several side-channel attacks, the proposed scheme enables an easy divide-and-concur solution—any fine-tuned architecture, for example, a power-attack-resistant architecture, can be equipped with fault-attack resistance easily without disturbing its original resistance. This advantage distinguishes the proposed scheme over the existing countermeasures.

Beschreibung: This paper presents a novel fast algorithm for digital convolutions. It is able to compute arbitrary-length convolutions more efficiently via transforming the convolution into a first-order moment. Although many additions are required, the proposed algorithm has some advantages such as the avoidance of multiplications, simple computation structure, and only integer additions. These advantages contribute to this algorithm being so easy that it can compute convolutions rapidly. Based on the proposed algorithm a very simple and scalable systolic array without multipliers and ROM has been developed leading to more efficient VLSI implementation of convolutions.

Beschreibung: Computation of peak supply current is central to power rail design and analysis of power supply switching noise. Traditionally, peak switching current from all CMOS gates is added together to compute peak supply current. This approach can be improved significantly if temporal and Boolean relationships are taken into consideration. Previously, it was shown that worst case switching current in a subset of gates may imply that some other gates may not have the worst case switching condition due to logical relationship between input patterns of a gate. In this paper, we also take integer gate delays into consideration to show that gate switching events may be spaced out in time leading to lower peak current. Further, it is found that taking gate delays into account actually simplifies the size of individual problem instances to be solved, leading to both a faster and more accurate solution. Finally, we compare peak current waveform generated by the proposed solver against SPICE simulation to demonstrate effectiveness of the proposed solution.

Beschreibung: Memory efficiency and dynamically updateable data structures for Internet Protocol (IP) lookup have regained much interest in the research community. In this paper, we revisit the classic tree-based approach for solving the longest prefix matching (LPM) problem used in IP lookup. In particular, we target our solutions for a class of large and sparsely distributed routing tables, such as those potentially arising in the next-generation IPv6 routing protocol. Due to longer prefix lengths and much larger address space, preprocessing such routing tables for tree-based LPM can significantly increase the number of prefixes and/or memory stages required for IP lookup. We propose a prefix partitioning algorithm (DPP) to divide a given routing table into k groups of disjoint prefixes (k is given). The algorithm employs dynamic programming to determine the optimal split lengths between the groups to minimize the total memory requirement. Our algorithm demonstrates a substantial reduction in the memory footprint compared with those of the state of the art in both IPv4 and IPv6 cases. Two proposed linear pipelined architectures, which achieve high throughput and support incremental updates, are also presented. The proposed algorithm and architectures achieve a memory efficiency of 1 byte of memory for each byte of prefix for both IPv4 and IPv6. As a result, our design scales well to support either larger routing tables, longer prefix lengths, or both. The total memory requirement depends solely on the number of prefixes. Implementations on 45 nm ASIC and a state-of-the-art FPGA device (for a routing table consisting of 330K prefixes) show that our algorithm achieves 980 and 410 million lookups per second, respectively. These results are well suited for 100 Gbps lookup. The implementations also scale to support larger routing tables and longer prefix length when we go from IPv4 to IPv6. Additionally, the proposed architectures can easily interface with external SRAMs to ease th- limitation of on-chip memory of the target devices.

Beschreibung: In this paper, we present multioperand radix-2 online addition using different data representations (signed-digit, two's complement, and carry-save), in particular cases in which operands with different representations are added. We use the previously defined online full adder (olFA) as a component to build different multioperand online architectures. To merge data with different representations, an inner conversion of data is performed, eliminating any conversion stage and penalty time. We propose a technique to build multioperand trees efficiently and give six practical rules to deal with different kinds of data in the same adder. For addition of a stream of data, we determine the minimum number of separation cycles required to isolate two successive computations and propose a novel hardware technique that eliminates completely the separation cycles, resulting in the maximum throughput possible.

Beschreibung: In a recent paper, Lima, Panario, and Wang have provided a new method to multiply polynomials expressed in Chebyshev basis which reduces the total number of multiplication for small degree polynomials. Although their method uses Karatsuba's multiplication, a quadratic number of operations are still needed. In this paper, we extend their result by providing a complete reduction to polynomial multiplication in monomial basis, which therefore offers many subquadratic methods. Our reduction scheme does not rely on basis conversions and we demonstrate that it is efficient in practice. Finally, we show a linear time equivalence between the polynomial multiplication problem under monomial basis and under Chebyshev basis.

Beschreibung: Reliability is a key challenge to be understood to turn the vision of exascale supercomputing into reality. Inevitably, large-scale supercomputing systems, especially those at the peta/exascale levels, must tolerate failures, by incorporating fault-tolerance mechanisms to improve their reliability and availability. As the benefits of fault-tolerance mechanisms rarely come without associated time and/or capital costs, reliability will limit the scalability of parallel applications. This paper introduces for the first time the concept of "Reliability Wall” to highlight the significance of achieving scalable performance in peta/exascale supercomputing with fault tolerance. We quantify the effects of reliability on scalability, by proposing a reliability speedup, defining quantitatively the reliability wall, giving an existence theorem for the reliability wall, and categorizing a given system according to the time overhead incurred by fault tolerance. We also generalize these results into a general reliability speedup/wall framework by considering not only speedup but also costup. We analyze and extrapolate the existence of the reliability wall using two representative supercomputers, Intrepid and ASCI White, both employing checkpointing for fault tolerance, and have also studied the general reliability wall using Intrepid. These case studies provide insights on how to mitigate reliability-wall effects in system design and through hardware/software optimizations in peta/exascale supercomputing.

Beschreibung: Object detection applications are often associated with real-time performance constraints that stem from the embedded environment that they are often deployed in. Consequently, researchers have proposed dedicated hardware architectures, utilizing a variety of classification algorithms targeting object detection. Support Vector Machines (SVMs) is among the most popular classification algorithms used in object detection yielding high accuracy rates. However, existing SVM hardware implementations attempting to speed up SVM classification, have either targeted only simple applications, or SVM training. As such, there are limited proposed hardware architectures that are generic enough to be used in a variety of object detection applications. Hence, this paper presents a parallel array architecture for SVM-based object detection, in an attempt to show the advantages, and performance benefits that stem from a dedicated hardware solution. The proposed hardware architecture provides parallel processing, resource sharing among the processing units, and efficient memory management. Furthermore, the size of the array is scalable to the hardware demands, and can also handle a variety of applications such as multiclass classification problems. A prototype of the proposed architecture was implemented on an FPGA platform and evaluated using three popular detection applications, demonstrating real-time performance (40-122 fps for a variety of applications).

Beschreibung: Maximum Parsimony phylogenetic tree reconstruction is based on finding the breakpoint median, given a set of species, and is represented by a bounded edge-weight graph model. This reduces the breakpoint median problem to one of solving multiple instances of the Traveling Salesman Problem (TSP), which is a classical NP-complete problem in graph theory. Exponential time algorithms that apply efficient runtime heuristics, such as branch-and-bound, to dynamically prune the search space are used to solve TSP. In this paper, we present the design and performance evaluation of a network-on-chip (NoC)-based implementation for solving TSP under the bounded edge-weight model, as used in the computation of breakpoint phylogeny. Our approach takes advantage of fine-grain parallelism from the multiple processing elements (PEs) and uses efficient NoC architecture for inter-PE communication. To accelerate the application on hardware, our PE design optimizes a particular lower bound calculation operation which typically tends to be the serial bottleneck in computation of a TSP solution. We also explore two representative NoC architectures—mesh and quad-tree—and show that the latter is more energy-efficient for this application domain. Experimental results show that this new implementation is able to achieve speedups of up to three orders of magnitude over state-of-the-art multithreaded software implementations.

Beschreibung: In many network applications, Bloom filters are used to support exact-matching membership query for their randomized space-efficient data structure with a small probability of false answers. In this paper, we extend the standard Bloom filter to Locality-Sensitive Bloom Filter (LSBF) to provide Approximate Membership Query (AMQ) service. We achieve this by replacing uniform and independent hash functions with locality-sensitive hash functions. Such replacement makes the storage in LSBF to be locality sensitive. Meanwhile, LSBF is space efficient and query responsive by employing the Bloom filter design. In the design of the LSBF structure, we propose a bit vector to reduce False Positives (FP). The bit vector can verify multiple attributes belonging to one member. We also use an active overflowed scheme to significantly decrease False Negatives (FN). Rigorous theoretical analysis (e.g., on FP, FN, and space overhead) shows that the design of LSBF is space compact and can provide accurate response to approximate membership queries. We have implemented LSBF in a real distributed system to perform extensive experiments using real-world traces. Experimental results show that LSBF, compared with a baseline approach and other state-of-the-art work in the literature (SmartStore and LSB-tree), takes less time to respond AMQ and consumes much less storage space.

Beschreibung: Real-time systems modeled by timed automata are often symbolically verified using Difference Bound Matrix (DBM) and Binary Decision Diagram (BDD) operations. When designing concurrent real-time systems with two or more processes sharing a resource, priorities are often used to schedule processes and to resolve conflicting resource requests. Concurrent real-time systems can thus be modeled by timed automata with priorities. However, model checking timed automata with priorities needs the DBM subtraction operation, whose result may not be convex, i.e., DBMs are not closed under subtraction. Thus, a partition of the resulting DBM is required. In this work, we propose Prioritized Timed Automata (PTA) and resolve all the issues related to the model checking of PTA. Two algorithms are proposed including an optimal DBM subtraction algorithm that produces the minimal number of DBM partitions, and a DBM merging algorithm that reduces the DBM partitions after a series of DBM subtractions. Application examples show the advantages of the proposed method in terms of support for the efficient verification of prioritized timed systems.

Beschreibung: This paper describes a fast procedure for identifying undetectable transition faults under functional broadside tests. By using reachable states as scan-in states, functional broadside tests avoid overtesting that may occur when scan-based tests are used for detecting delay faults. The proposed procedure is based only on logic simulation, and does not perform test generation of any type. In one of its variations, the procedure uses logic simulation of fully unspecified primary input vectors starting from a known initial state in order to identify a superset of broadside tests that covers all the functional broadside tests. It then uses this superset to identify undetectable transition faults. The procedure identifies large numbers of undetectable transition faults in certain benchmark circuits.

Beschreibung: Wireless Sensor Networks (WSNs) are widely recognized as a promising solution to build next-generation monitoring systems. Their industrial uptake is however still compromised by the low level of trust on their performance and dependability. Whereas analytical models represent a valid mean to assess nonfunctional properties via simulation, their wide use is still limited by the complexity and dynamicity of WSNs, which lead to unaffordable modeling costs. To reduce this gap between research achievements and industrial development, this paper presents a framework for the assessment of WSNs based on the automated generation of analytical models. The framework hides modeling details, and it allows designers to focus on simulation results to drive their design choices. Models are generated starting from a high-level specification of the system and by a preliminary characterization of its fault-free behavior, using behavioral simulators. The benefits of the framework are shown in the context of two case studies, based on the wireless monitoring of civil structures.

Beschreibung: Continuous Data Protection (CDP) has become increasingly important as digitization continues. This paper presents a new architecture and an implementation of CDP in Linux kernel. The new architecture takes advantages of both traditional snapshot technology and recent Timely Recovery to Any Point-in-time (TRAP) architecture [CHECK END OF SENTENCE]. The idea is to periodically insert snapshots within the parity logs of changed data blocks in order to ensure fast and reliable data recovery in case of failures. A mathematical model is developed as a guide to designers to determine when and how to insert snapshots to optimize performance in terms of space usage and recovery time. Based on the mathematical model, we have designed and implemented a CDP module in the Linux system. Our implementation is at block level as a device driver that is capable of recovering data to any point-in-time in case of various failures. Extensive experiments have been carried out to show that the implementation is fairly robust and numerical results demonstrate that the implementation is efficient.

Beschreibung: Diagnosability of a system directly refers to the maximum number of faulty vertices that can be identified by the system. Somani et al. [CHECK END OF SENTENCE] proposed a generalized measure to increase the degree of diagnosability of the hypercubes and star graphs. This paper provides counterexamples for the results of diagnosability of star graphs.

Beschreibung: 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.

Beschreibung: We study the information brokerage schemes in wireless sensor networks, which allow consumers to obtain data from producers by replicating and retrieving data in a certain set of sensors, and propose a novel information brokerage scheme, termed RDRIB. Unlike existing information brokerage schemes, RDRIB guarantees successful data retrieval without using any boundary detection algorithm and the geographic location information acquired by the global positioning system (GPS). In RDRIB, the double-ruling technique is used to replicate and retrieve the data within a constructed virtual boundary, and simulations show that RDRIB has good performance in terms of the replication memory overhead, the replication message overhead, the retrieval message overhead, the retrieval latency, and the construction message overhead.

Beschreibung: Functional test sequences have several advantages over structural tests when they are applied at-speed. A large pool of functional test sequences may be available for a circuit due to the application of a simulation-based design verification process. This paper describes a versatile procedure that uses a pool of functional test sequences as a basis for forming a single compact functional test sequence that achieves the same or higher gate-level fault coverage than the given pool. The procedure extracts test subsequences from the test sequences in the pool and concatenates them to form a single test sequence. It also employs an enhanced static test compaction process aimed at improving the fault coverage in addition to reducing the test sequence length.

Beschreibung: The 12 papers in this special issue focus on energy efficient computing applications and technologies.

Beschreibung: Energy-efficient scheduling of sequential tasks with precedence constraints on multiprocessor computers with dynamically variable voltage and speed is investigated as combinatorial optimization problems. In particular, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint are considered. Our scheduling problems contain three nontrivial subproblems, namely, precedence constraining, task scheduling, and power supplying. Each subproblem should be solved efficiently so that heuristic algorithms with overall good performance can be developed. Such decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. Three types of heuristic power allocation and scheduling algorithms are proposed for precedence constrained sequential tasks with energy and time constraints, namely, prepower-determination algorithms, postpower-determination algorithms, and hybrid algorithms. The performance of our algorithms are analyzed and compared with optimal schedules analytically. Such analysis has not been conducted in the literature for any algorithm. Therefore, our investigation in this paper makes initial contribution to analytical performance study of heuristic power allocation and scheduling algorithms for precedence constrained sequential tasks. Our extensive simulation data demonstrate that for wide task graphs, the performance ratios of all our heuristic algorithms approach one as the number of tasks increases.

Beschreibung: Moore's Law improvement in transistor density is driving a rapid increase in the number of cores per processor. DRAM device capacity and energy efficiency are increasing at a slower pace, so the importance of DRAM power is increasing. This problem presents system designers with two nominal options when designing future systems: 1) decrease off-chip memory capacity and bandwidth per core or 2) increase the fraction of system power allocated to main memory. Reducing capacity and bandwidth leads to imbalanced systems with poor processor utilization for noncache-resident applications, so designers have chosen to increase DRAM power budget. This choice has been viable to date, but is fast running into a memory power wall. To address the looming memory power wall problem, we propose a novel iso-power tiered memory architecture that supports 2-3X more memory capacity for the same power budget as traditional designs by aggressively exploiting low-power DRAM modes. We employ two "tiers” of DRAM, a "hot” tier with active DRAM and a "cold” tier in which DRAM is placed in self-refresh mode. The DRAM capacity of each tier is adjusted dynamically based on aggregate workload requirements and the most frequently accessed data are migrated to the "hot” tier. This design allows larger memory capacities at a fixed power budget while mitigating the performance impact of using low-power DRAM modes. We target our solution at server consolidation scenarios where physical memory capacity is typically the primary factor limiting the number of virtual machines a server can support. Using iso-power tiered memory, we can run 3 {times} as many virtual machines, achieving a 250 percent improvement in average aggregate performance, compared to a conventional memory design with the same power budget.

Beschreibung: The rapid advancements in the computational capabilities of the graphics processing unit (GPU) as well as the deployment of general programming models for these devices have made the vision of a desktop supercomputer a reality. It is now possible to assemble a system that provides several TFLOPs of performance on scientific applications for the cost of a high-end laptop computer. While these devices have clearly changed the landscape of computing, there are two central problems that arise. First, GPUs are designed and optimized for graphics applications resulting in delivered performance that is far below peak for more general scientific and mathematical applications. Second, GPUs are power hungry devices that often consume 100-300 watts, which restricts the scalability of the solution and requires expensive cooling. To combat these challenges, this paper presents the PEPSC architecture—an architecture customized for the domain of data parallel dense matrix style scientific application where power efficiency is the central focus. PEPSC utilizes a combination of a 2D single-instruction multiple-data (SIMD) datapath, an intelligent dynamic prefetching mechanism, and a configurable SIMD control approach to increase execution efficiency over conventional GPUs. A single PEPSC core has a peak performance of 120 GFLOPs while consuming 2 W of power when executing modern scientific applications, which represents an increase in computation efficiency of more than 10X over existing GPUs.

Beschreibung: MapReduce is a distributed computing paradigm widely used for building large-scale data processing applications. When used in cloud environments, MapReduce clusters are dynamically created using virtual machines (VMs) and managed by the cloud provider. In this paper, we study the energy efficiency problem for such MapReduce clouds. We describe a unique spatio-temporal tradeoff that includes efficient spatial fitting of VMs on servers to achieve high utilization of machine resources, as well as balanced temporal fitting of servers with VMs having similar runtimes to ensure a server runs at a high utilization throughout its uptime. We propose VM placement algorithms that explicitly incorporate these tradeoffs. Further, we propose techniques that dynamically scale MapReduce clusters to further improve energy consumption while ensuring that jobs meet or improve their expected runtimes. Our algorithms achieve energy savings over existing placement techniques, and an additional optimization technique further achieves savings while simultaneously improving job performance.

Beschreibung: 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, nonpower-aware switch controls to generate two novel scheduling algorithms: 1) LQR Power Aware Maximum Weight Matching (LQR PA MWM) and 2) 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.

Beschreibung: As technology is reaching physical limits, reducing power consumption is a key issue on our path to sustained performance. In this paper, we study fundamental tradeoffs and limits in efficiency (as measured in energy per operation) that can be achieved for an important class of kernels, namely the level-3 Basic Linear Algebra Subprograms (BLAS). It is well-accepted that specialization is the key to efficiency. This paper establishes a baseline by studying GEneral Matrix-matrix Multiplication (GEMM) on a variety of custom and general-purpose CPU and GPU architectures. Our analysis shows that orders of magnitude improvements in efficiency are possible with relatively simple customizations and fine-tuning of memory hierarchy configurations. We argue that these customizations can be generalized to perform other representative linear algebra operations. In addition to exposing the sources of inefficiencies in current CPUs and GPUs, our results show our prototype Linear Algebra Processor (LAP) implementing Double-precision GEMM (DGEMM) can achieve 600 GFLOPS while consuming less than 25 Watts in standard 45 nm technology, which is up to 50times more energy efficient than cutting-edge CPUs.

Beschreibung: Voltage and frequency island (VFI) was recently adopted as an effective energy management technique for multicore processors. For a set of periodic real-time tasks that access shared resources running on a VFI-based multicore system with dynamic voltage and frequency scaling (DVFS) capability, we study both static and dynamic synchronization-aware energy management schemes. First, based on the enhanced MSRP resource access protocol with a suspension mechanism, we devise a synchronization-aware task mapping heuristic for partitioned-EDF scheduling, which assigns tasks that access similar set of resources to the same core to reduce the synchronization overhead and thus improve schedulability. Then, static schemes that assign uniform and different scaled frequencies for tasks on different VFIs are studied. To further exploit dynamic slack, we propose an integrated synchronization-aware slack management framework to appropriately reclaim, preserve, release and steal slack at runtime to slow down the execution of tasks subject to the common voltage/frequency limitation of VFIs and timing/synchronization constraints of tasks. Taking the additional delay due to task synchronization into consideration, the new scheme allocates slack in a fair manner and scales down the execution of both noncritical and critical sections of tasks for more energy savings. Simulation results show that, the synchronization-aware mapping can significantly improve the schedulability of tasks. The energy savings obtained by the static scheme with different frequencies for tasks on different VFIs is close to that of an optimal Integer Nonlinear Programming (INLP) solution. Moreover, compared to the simple extension of existing solutions for uniprocessor systems, our schemes can obtain much better energy savings (up to 40 percent) with comparable DVFS overhead.

Beschreibung: This paper presents low cost techniques for error detection and correction in Ternary Content Addressable Memories (TCAMs). The techniques exploit the inherent redundancy of TCAM cells to allow for protection at lower cost. A fault detection technique with the cost of parity but with about the half probability of silent data corruption is proposed. This technique is then applied at both horizontal and vertical dimensions of the TCAM array, and a low cost error correction scheme is derived. Last, another error correction scheme is proposed, which employs a SECDED ECC of the half complexity, by making use of the TCAM redundancy, without compromising single bit error correction. The proposed schemes come with minimal area, power, and critical path overheads, in comparison with standard schemes, and they are good alternatives for TCAM arrays protection.

Beschreibung: In this paper, we define a new subclass of integer linear programming problems called the composition problem. We shall propose efficient algorithms for solving this problem and its variants. Moreover, as an application of the composition problem, those algorithms are applied to solve the P-constrained secure set problem, which is a variation of the secure set problem introduced in [CHECK END OF SENTENCE], on trees. A P-constrained secure set problem is to find a minimum secure set containing a set of vert Pvert predetermined vertices.

Beschreibung: Energy consumption of wireless data transmission, a significant part of the overall energy consumption on a mobile device, is context-dependent—it depends on both internal and external contexts, such as application workload and wireless signal strength. In this paper, we propose an event-driven framework that can be used for efficient power management on mobile devices. The framework adapts the behavior of a device component or an application to the changes in contexts, defined as events, according to developer-specified event-condition-action (ECA) rules that describe the power management mechanism. In contrast to previous work, our framework supports complex event processing. By correlating events, complex event processing helps to discover complex events that are relevant to power consumption. Using our framework developers can implement and configure power management applications by editing event specifications and ECA rules through XML-based interfaces. We evaluate this framework with two applications in which the data transmission is adapted to traffic patterns and wireless link quality. These applications can save roughly 12 percent more energy compared to normal operation.