Deep neural networks (DNNs) have become an important tool for bringing intelligence to mobile and embedded devices. The increasingly wide deployment, sharing and potential commercialization of DNN models create a compelling need for intellectual property (IP) protection. Recently, DNN watermarking emerges as a plausible IP protection method. Enabling DNN watermarking on embedded devices in a practical setting requires a black-box approach. Existing DNN watermarking frameworks either fail to meet the black-box requirement or are susceptible to several forms of attacks. We propose a watermarking framework by incorporating the author's signature in the process of training DNNs. While functioning normally in regular cases, the resulting watermarked DNN behaves in a different, predefined pattern when given any signed inputs, thus proving the authorship. We demonstrate an example implementation of the framework on popular image classification datasets and show that strong watermarks can be embedded in the models.

Secure group-oriented communication is crucial to a wide range of applications in Internet of Things (IoT). Security problems related to group-oriented communications in IoT-based applications placed in a privacy-sensitive environment have become a major concern along with the development of the technology. Unfortunately, many IoT devices are designed to be portable and light-weight; thus, their functionalities, including security modules, are heavily constrained by the limited energy resources (e.g., battery capacity). To address these problems, we propose a group key management scheme based on a novel physically unclonable function (PUF) design: multistage interconnected PUF (MIPUF) to secure group communications in an energy-constrained environment. Our design is capable of performing key management tasks such as key distribution, key storage and rekeying securely and efficiently. We show that our design is secure against multiple attack methods and our experimental results show that our design saves 47.33% of energy globally comparing to state-of-the-art Elliptic-curve cryptography (ECC)-based key management scheme on average.

Today's mobile devices are equipped with cameras capable of taking very high-resolution pictures. For computer vision tasks which require relatively low resolution, such as image classification, sub-sampling is desired to reduce the unnecessary power consumption of the image sensor. In this paper, we study the relationship between subsampling and the performance degradation of image classifiers that are based on deep neural networks (DNNs). We empirically show that subsampling with the same step size leads to very similar accuracy changes for different classifiers. In particular, we could achieve over 15x energy savings just by subsampling while suffering almost no accuracy lost. For even better energy accuracy trade-offs, we propose AdaSkip, where the row sampling resolution is adaptively changed based on the image gradient. We implement AdaSkip on an FPGA and report its energy consumption.

VLSI intellectual property (IP) reuse based design methodology was adopted by the semiconductor industry in the early 1990's and how to protect design IPs from piracy and misuse has since been a challenging problem. 2017 marks the 20th anniversary of the IP protection development and working group was founded and the first series of IP watermarking papers were published. In this paper, we survey the efforts from industry, government, and academia on securing the design IPs in the past 20 years with focus on development from academia side.

Physical unclonable functions (PUFs) take advantage of the effect of process variation on hardware to obtain their unclonability. Traditional PUF design only focuses on the analog signals of circuits. An arbiter PUF, for example, generates responses by racing delay signals. Implementations of such PUFs usually employ large area and power consumption while providing very low throughput. To address this problem, we propose an energy efficient PUF design in such a way that it races analog signals and computes digital logic simultaneously. More importantly, the analog portion of the circuit (racing) shares a large amount of hardware resources with the digital portion of the circuit (computing) by introducing only small overhead in terms of area and power. Our test results on Spartan-6 field-programmable gate array (FPGA) platforms indicate that by combining the two outputs, our design enables much larger PUF output throughput, better randomness and less power consumption compared to traditional PUFs.

Low energy, as one of the most important metrics in modern design, has also been considered as an important criterion to many DSP applications. To address the low energy issue of DSP applications, in this work, we have proposed a new energy minimization approach which optimally combines the dual-supply voltage (dual-Vdd) with the retiming technique. We have specifically focused on various hardware-implemented transforms and filters such as the fast Fourier transform (FFT) and the discrete cosine transform (DCT) which are widely used in DSP applications. Our key idea is to use a maximum-flow/min-cut strategy to reduce the required number of flip-flop logic and while maintaining the delay of the circuit in such a way that to enable efficient Vdd allocation in the subsequent stage. The effectiveness of our approach is demonstrated on both FFT and DCT applications using an industrial cell library. Given a target delay, a significant energy saving using our approach is observed.

Fault tolerance (FT) is essential in many Internet of Things (IoT) applications, in particular in the domains such as medical devices and automotive systems where a single fault in the system can lead to serious consequences. Non-volatile memory (NVM), on the other hand, is commonly used to improve system reliability due to its unique properties to retain data even if the power supply is lost. However, one of the most important drawbacks of NVM is that it imposes significant overhead regarding timing and energy. In this paper, we have proposed a unique technique with the use of NVM to create FT application specific architecture with almost no timing overhead and low energy overhead. We address the implementation of applications that are specified using synchronous data flow model of computation. We combine the use of NVM and classical CMOS transistors so that NVM judiciously stores selected complete states of the pertinent program. It allows the program to resume from the saved state in NVM when faults occur. The frequency of the state selection can be flexibly adjusted for an arbitrarily specified FT timing/energy overhead. Moreover, to find an optimal state selection (with low overhead), we have applied an improved min-cut max-flow algorithm. On a variety of typical benchmarks, the simulation results indicate that our approach incurs only a small overhead over lower bounds. It is also generic in a sense that it can be applied to a wide spectrum of underlying IoT architectures and computational models.

Physical unclonable functions (PUFs) take advantage of the effect of process variation on hardware to obtain their unclonability. Traditional PUF design only focuses on the analog signals of circuits. An arbiter PUF, for example, generates responses by racing delay signals. Implementations of such PUFs usually employ large area and power consumption while providing very low throughput.

It is commonly known that physical unclonable functions (PUFs) are hard to predict and hard to emulate. However, in this paper, we propose to use statistical models to adaptively characterize the delay-based PUFs, and use this as a starting point to emulate a delay-based PUF. The essential idea is that for any challenge CA of a delay-based PUF A, there is a high probability of finding a paired challenge CB. When apply CB to another delay-based PUF B, it can produce the same output as applying CA on PUF A. Our simulation results indicate more than 99% correctness for the PUF response prediction using characterization and 96% correctness using emulation. Finally, we implement and test the feasibility of our approach on the Xilinx Spartan-6 Field Programmable Gate Array (FPGA).

Data security and privacy have emerged to become an important issue in various types of applications. Although many cryptographic cyphers are proposed to leverage the issue, they normally suffer from the problems of either requiring large power/bandwidth consumption or employing linear system which is easy to break. To solve the problem of traditional cyphers, we have proposed a new hardware security primitive: recursive inverse function (RIF) designed on the field-programmable gate array (FPGA). The RIF takes advantage of a pair of inverse functions, building a recursive scheme for message encryption and decryption. The inverse functions are defined as a pair of functions where each function implements a mapping being inverse to the mapping of the other function. On the top of it, the recursive structure guarantees the input-output mapping to be statistically extremely hard to predict. The RIF can be easily implemented using hierarchical lookup-table (LUT) structures with low delay and power overhead. Using our proposed RIF structure, we have demonstrated how the RIF can be incorporated into a processor design to enable the data protection. Finally, we implement our scheme on a Xilinx Spartan-6 FPGA device to analyze the performance and the overhead.

Modern applications, such as video and audio processing, employ many linear transforms and filters, such as the discrete cosine transform (DCT) and fast Fourier transform (FFT). There is a need to drastically reduce the energy consumption of these applications in order to enable their ultralow energy realization on mobile devices. It is well known that all of these applications can be implemented using multiple constant multiplication (MCM). As of now, there has been no effort to synthesize ultralow energy implementations of these systems, in particular, through the use of near-threshold computing (NTC). In order to synthesize MCM in NTC systems, we propose techniques that include minimizing the critical path through load reduction along with the creation of deep combinational logic in order to reduce the impact of process variation. We have demonstrated the effectiveness of our new techniques on both FFT and DCT applications and show up to an order of magnitude reduction in energy for the target delay.

Design automation (DA) is at a historical moment where it has a chance - after mathematics, statistics, and computer science - to establish itself as the fourth universal approach with widespread applications in a variety of scientific, engineering, and economic domains. We start by outlining some of the most important research contributions and industrial applications of the design automation; we identify key conceptual DA techniques and describe how they interact to form synthesis and analysis flows. Next, we discuss the most attractive emerging and pending DA domains by analyzing several recent technologies, applications, and conceptual trends. Our emphasis is not just on the most challenging research or the most lucrative application areas but also on the technological trends relevant to DA. Furthermore, we elaborate on the types of new DA techniques and tools that are required for further fundamental progress and improved practical relevance. In order to provide a balanced picture of DA, we also identify the most pronounced dangers in false starts and false research in DA. Finally, we briefly discuss the need for a DA educational reform and community social reorganization that are beneficial for rapid and impactful research and development contributions.

The modern secure systems are designed to require ultra-low power secure solutions due to their energy constraints. Compared to the classical cryptography approaches, the physical unclonable functions (PUFs) have emerged as a novel security primitive with the property of low power/energy, small area, and high speed. Among the family of PUFs, delay-based PUF takes advantage of the process variation on the gate delays. However, it suffers the problem of instability against operational variations. In this paper, we have proposed to use device-aging to improve the stability of the delay-based PUF which induces negligible energy and area cost. We test to compare the stability of PUFs before and after device-aging against temperature and supply voltage variations.

Security and low power have emerged to become two essential requirements to modern design. In this paper, we have proposed a new hardware security primitive: digital bidirectional function (DBF) designed on FPGA to meet both criteria. The DBF has two forms of functions and implements two mappings of opposite directions. The DBF can be easily implemented using hierarchical lookup-table (LUT) structures with low delay and power overhead. In terms of applications, we demonstrate how DBF is applied in the protocol of secure message transfer and compare its power/bandwidth consumption with other cryptographic approaches. Our results indicate that the energy consumption of DBF outperforms the traditional ciphers by averagely two to three orders of magnitude.

Information security has emerged as an important system and application metric. Classical security solutions use algorithmic mechanisms that address a small subset of emerging security requirements, often at high-energy and performance overhead. Further, emerging side-channel and physical attacks can compromise classical security solutions. Hardware security solutions overcome many of these limitations with less energy and performance overhead. Nanoelectronics-based hardware security preserves these advantages while enabling conceptually new security primitives and applications. This tutorial paper shows how one can develop hardware security primitives by exploiting the unique characteristics such as complex device and system models, bidirectional operation, and nonvolatility of emerging nanoelectronic devices. This paper then explains the security capabilities of several emerging nanoelectronic devices: memristors, resistive random-access memory, contact-resistive random-access memory, phase change memories, spin torque-transfer random-access memory, orthogonal spin transfer random access memory, graphene, carbon nanotubes, silicon nanowire field-effect transistors, and nanoelectronic mechanical switches. Further, the paper describes hardware security primitives for authentication, key generation, data encryption, device identification, digital forensics, tamper detection, and thwarting reverse engineering. Finally, the paper summarizes the outstanding challenges in using emerging nanoelectronic devices for security.

Small form, mobile, and remote sensor network systems require secure and ultralow power data collection and communication solutions due to their energy constraints. The physical unclonable function (PUF) has emerged as a popular modern low power security primitive. However, current designs are analog in nature and susceptible to instability and difficult to integrate into existing circuitry. In this paper, we present the digital PUF which is stable in the same sense that digital logic is stable, has a very small footprint and very small timing overhead, and can be easily integrated into existing designs. We demonstrate the use of the digital PUF on two applications that are crucial for sensor networks: trusted remote sensing and logic obfuscation. We present our security analysis using standard randomness tests and confusion and diffusion analysis, and apply our new obfuscation approach on a set of standard design benchmarks.

In this paper we present an architecture for a secure embedded system that is resilient to tempering and code injection attacks and offers anti-piracy protection for the software and hardware Intellectual Property (IP). We incorporate digital Physical Unclonable Functions (PUFs) in an authentication mechanism at the machine code level. The digital PUFs are used to de-obfuscate, at run time, a firmware that's issued by a central authority with very little performance and resource overhead. Each PUF is unique to the hosting device, and at the same time can be reconfigured with new seeds. The reconfigurable digital PUFs (drPUFs) have much lower risks of side-channel attacks and vastly higher number of usable challenge-response pairs, while retaining the speed and ease to implementation of digital PUFs.

Customization and adaptation have emerged as the most effective paradigms for energy minimization. We employ these paradigms to address coordinated power gating and dynamic voltage scaling for energy minimization of real-time tasks in both application-specific and programmable systems. For a given hardware platform, the first task in adaptation is to determine which hardware allocations and supply voltages should be used to execute a given set of tasks. In the case where tasks induce constant capacitance and are of sufficient length to render power gating and voltage scaling overheads negligible, we obtain the provably optimal solution using a combination of convex enclosure and convex optimization. Our next goal is to relax these two assumptions to consider overheads and non-uniformity in capacitance by subdividing each task into multiple subtasks at a fine granularity. In this case, we use another dynamic programming formulation to find a solution which is optimal in most practical cases. We have also developed a dynamic programming-based approach to minimize overheads of configuration switching.

This paper investigates and addresses the vulnerabilities of existing physical unclonable functions (PUFs). We first develop a PUF reverse engineering approach by conducting gate-level characterization (GLC). Based on the gate-level delay properties, we emulate the target PUF by designing a functionally equivalent PUF replication. Furthermore, in order to prevent such an attack, we develop a new sequential PUF architecture that is resilient to side channel-based reverse engineering. We obtain accurate results in emulating the timing behavior of the existing arbiter-based PUFs. Also, the randomness obtained from the sequential PUFs is significantly higher compared to the existing PUFs.

Foundry identification is essential for many tasks including intellectual property protection, trust, and preventing counterfeiting. In this paper, we introduce statistical techniques for foundry detection, specifically for identifying from which foundry a particular chip originates from. The key idea is to consider the distributions of channel lengths and threshold voltages after employing a variant of SAT that extracts these two metrics. We apply Kolmogorov-Smirnov and other statistical tests for comparing the two empirical distributions. Finally, we study the effects of sample size and measurement error on the correct identification rate and establish an interval of confidence using resubstitution techniques.

Both energy and execution speed can be greatly impacted by clock and power gating, nonlinear voltage scaling, and leakage energy. We address the problem of coordinated power gating and dynamic voltage scaling (DVS) to minimize the overall energy consumption of an application under user-specified timing constraints. We prove that a solution provided by our convex programming formulation that uses at most two versions of hardware, where each version uses its own constant voltages, is optimal. Comprehensive evaluation of the new approach demonstrates energy improvements over traditional DVS and DVS and power gating techniques by factors of 1.44X-2.97X and 1.44X-2.82X, respectively.

The physical unclonable function (PUF) has emerged as a popular and widely studied security primitive based on the randomness of the underlying physical medium. To date, most of the research emphasis has been placed on finding new ways to measure randomness, hardware realization and analysis of a few initially proposed structures, and conventional secret-key based protocols. In this work, we present our subjective analysis of the emerging and future trends in this area that aim to change the scope, widen the application domain, and make a lasting impact. We emphasize on the development of new PUF-based primitives and paradigms, robust protocols, public-key protocols, digital PUFs, new technologies, implementations, metrics and tests for evaluation/validation, as well as relevant attacks and countermeasures.

As remote health monitoring BASN technology matures and begins to proliferate, several issues related to the secure sharing of the resulting medical electronic data have come to the fore. This includes the need to provide the data owner (BASN user / patient) and the data consumers (healthcare providers, insurance companies, medical research facilities) secure control over the medical data as it is shared between these various stakeholders. In this paper, we focus on three secure sharing use-cases: proof of ownership, wherein the data owner must prove that she/he is the originator of the data, data tracking, wherein the data owner must trace unauthorized sharing of her/his bio signal data, and content authentication, wherein the data owner must prove whether the bio signal data has been maliciously altered. To address these use-cases, we develop a robust watermarking technique to embed security information into bio signal data such that the semantic fidelity of the data is unaffected, the bio-signal waveforms are altered imperceptibly, and the watermark is not easily corrupted, recovered or spoofed by malicious data consumers. Based on experimentally collected datasets from a gait-stability monitoring BASN, we show that our watermarking technique can robustly and effectively embed up to 1000 bit watermarks under these constraints.

We have developed the first FPGA-based digital physical unclonable function (PUF) by leveraging the reconfigurability of an FPGA and introducing a new way of using the standard analog delay PUF. The key observation is that for any analog delay PUF, there is a subset of challenge inputs for which the PUF output is stable regardless of operation and environmental conditions. We use only such stable inputs to initialize the look-up tables (LUTs) that are configured in such a way that the digital PUF is formed. We demonstrate the effectiveness of the new security primitive using extensive simulation and experimental results. For example, we show that the new PUF is resistant against a wide spectrum of security attacks and its output stream passes all the NIST randomness tests.

In this paper we present a secure and unclonable embedded system design that can target either an FPGA or an ASIC technology. The premise of the security is that the executed machine code and the executing environment (the embedded processor) will authenticate each other at a per-instruction basis using Physical Unclonable Functions (PUFs) that are built into the processor. The PUFs ensure that the execution of the binary code may only proceed if the binary is compiled with the correct intrinsic knowledge of the PUFs, and that such intrinsic knowledge is virtually unique to each processor and therefore unclonable. We will explain how to implement and integrate the PUFs into the processor's execution environment such that each instruction is authenticated and de-obfuscated on-demand and how to transform an ordinary binary executable into PUF-aware, obfuscated binaries. We will also present a prototype system on a Xilinx Spartan6-based FPGA board.

There is a great need to develop universal and robust techniques for intellectual property protection of integrated circuits. In this paper, we introduce techniques for the obfuscation of an arbitrary circuit by using physical unclonable functions (PUFs) and programmable logic. Specifically, we introduce the notion of PUF-based logic which can be configured to be functionally equivalent to any arbitrary design, as well as a new architecture for wire merging that obfuscates signal paths exponentially. We systematically apply our techniques in such a way so as to maximize obfuscation while minimizing area and delay overhead. We analyze our techniques on popular benchmark circuits and show them to be resilient against very powerful reverse engineering attacks in which the adversary has knowledge of the complete netlist along with the ability to read and write to any flip-flop in the circuit.

Computer-aided design (CAD), in its quest to facilitate new design revolutions, is again on the brink of changing its scope. Following both historical and recent technological and application trends, one can identify several emerging research and development directions in which CAD approaches and techniques may have major impacts. Among them, due to the potential to fundamentally alter everyday life as well as how science and engineering systems are designed and operated, the Internet of Things (IoT) stands out. IoT also poses an extraordinary system replete with conceptual and technical challenges. For instance, greatly reduced quantitative bounds on acceptable area and energy metrics require qualitative breakthroughs in design and optimization techniques. Most likely the most demanding of requirements for the widespread realization of many IoT visions is security. IoT security has an exceptionally wide scope in at least four dimensions. In terms of security scope it includes rarely addressed tasks such as trusted sensing, computation, communication, privacy, and digital forgetting. It also asks for new and better techniques for the protection of hardware, software, and data that considers the possibility of physical access to IoT devices. Sensors and actuators are common components of IoT devices and pose several unique security challenges including the integrity of physical signals and actuating events. Finally, during processing of collected data, one can envision many semantic attacks. Our strategic objective is to provide an impetus for the development of IoT CAD security techniques. We start by presenting a brief survey of IoT challenges and opportunities with an emphasis on security issues. Next, we discuss the potential of hardware-based IoT security approaches. Finally, we conclude with several case studies that advocate the use of stable PUFs and digital PPUFs for several IoT security protocols.

One of the most important infrastructure requirements in the domain of remote health monitoring BASNs is the secure collection and dissemination of the user's medical data. Data security desiderata in this application domain are not limited to ensuring the confidentiality and integrity of medical data that has been logged to a data sink. Requirements also arise from the need to provide the data owner (BAN user / patient) and the data consumers (healthcare providers, insurance companies, medical research facilities) secure control over the data as it is shared between these various stakeholders. Here, we study a robust watermarking technique to embed security information into biosignal data such that the semantic fidelity of the data is unaffected, while simultaneously ensuring that the watermark is not easily erased or corrupted by malicious data consumers. In doing so, we address three use-cases: proof of ownership, wherein the data owner can prove that she/he is the originator of the data; data tracking, wherein the data owner can trace unauthorized sharing of her/his biosignal data; and content authentication, wherein the data owner can prove whether the biosignal data has been maliciously altered. Based on experimentally collected datasets from a gait-stability monitoring BASN, we show that the embedding of 800 bit watermarks can be achieved robustly and effectively, with near-imperceptible changes to the signal waveform and no loss in the the signal's diagnostic quality.

Although vehicular sensing where mobile users in vehicles continuously gather, process, and share location-sensitive and context-sensitive sensor data (e.g., street images, road condition, traffic flow) is emerging, little effort has been investigated in a model-based energy-efficient network paradigm of sensor information sharing in vehicular environments. Upon these optimization frameworks, a suite of optimization subproblems: a program partitioning and network resource allocation problem, we propose a distributed vehicular sensing platform, called VeSense where mobile users in vehicles publish/access sensor data via a cloud computing-based distributed P2P overlay network. The key objective is to satisfy the vehicular sensing application’s quality of service requirements by modeling each subsystem: mobile clients, wireless network medium, and distributed cloud services. By simulations based on experimental data, we present the proposed system can achieve up to 37 times more energy-efficient and 73 times faster compared to a standalone mobile application, in various vehicular sensing scenarios applying a realistic mobility model.

A physical unclonable function (PUF) is an integrated circuit (IC) that serves as a hardware security primitive due to its complexity and the unpredictability between its outputs and the applied inputs. PUFs have received a great deal of research interest and significant commercial activity. Public PUFs (PPUFs) address the crucial PUF limitation of being a secret-key technology. To some extent, the first generation of PPUFs are similar to SIMulation Possible, but Laborious (SIMPL) systems and one-time hardware pads, and employ the time gap between direct execution and simulation. The second PPUF generation employs both process variation and device aging which results in matched devices that are excessively difficult to replicate. The third generation leaves the analog domain and employs reconfigurability and device aging to produce digital PPUFs. We survey representative PPUF architectures, related public protocols and trusted information flows, and related testing issues. We conclude by identifying the most important, challenging, and open PPUF-related problems.

With our approach, for the synthesis and energy-efficient operation of a pressure sensor-based soft keyboard, energy is optimized at five levels of abstraction: 1) architecture of sensor systems, 2) sensing schedule, 3) sensor data processing, 4) use of semantic information, and 5) customization. We have been able to achieve up to a factor of 63 energy reduction in a keyboard case study over the standard using various techniques. For example, when each sensor senses several keyboard events and each event is sensed by three sensors, sensing and data processing results in a 12- to 42-fold energy savings depending on typing speeds. Customization techniques accounting for user typing speed and duration of typing pulses support another 1.5-fold savings. We demonstrate using a proof of concept prototype evaluation with five participants.

Hardware Trojans (HTs) have become a major concern in the modern integrated circuit (IC) industry, especially with the fast growth in IC outsourcing. HT detection and diagnosis are challenging due to the huge number of gates in modern IC designs and the high cost of testing. We propose a scalable and efficient HT detection and diagnosis scheme based on segmentation and consistency analysis of gate-level properties. In addition, we employ a self-consistency-based approach, where we conduct variable elimination and create subsegments from a fixed set of power measurements of the entire IC to minimize the number of power measurements. We evaluate our HT detection and diagnosis schemes on a set of ISCAS and ITC benchmarks.

Hardware security has emerged as an important field of study aimed at mitigating issues such as piracy, counterfeiting, and side channel attacks. One popular solution for such hardware security attacks are physical unclonable functions (PUF) which provide a hardware specific unique signature or identification. The uniqueness of a PUF depends on intrinsic process variations within individual integrated circuits. As process variations become more prevalent due to technology scaling into the nanometer regime, novel nanoelectronic technologies such as memristors become viable options for improved security in emerging integrated circuits. In this paper, we provide an overview of memristor based PUF structures and circuits that illustrate the potential for nanoelectronic hardware security solutions.

We have developed an approach for automatic embedding of customizable hardware Trojan horses (HTHs) into an arbitrary finite state machine. The HTH can be used to facilitate a variety of security attacks and does not require any additional gates, because it is morphed into the specified design. Even after the HTH induces provable damage, one is not capable of proving that any malicious circuitry is embedded into the design. The main ramification of the developed HTH is that hardware and system techniques should move from HTH detection toward synthesis for trusted systems.

The impact of process variation (PV) in deep submicron CMOS technologies has raised major concerns for energy optimization efforts in FPGAs. We have developed a post-silicon leakage energy optimization scheme that raises the threshold voltage (by way of negative bias temperature instability (NBTI) aging) of the components that are either unused or not on the critical timing paths, thereby reducing the total leakage energy consumption. In order to obtain the input vectors for aging only the targeted transistors, we map the problem of minimizing leakage energy under timing constraints to an instance of the satisfiability (SAT) problem. We implemented low power designs targeting Xilinx Spartan6 FPGAs and analyzed the potential leakage power savings over a set of ITC99 and Opencores benchmarks. The analysis of the experimental results shows a substantial amount of potential leakage energy reduction with very small performance degradation.

The presence of process variation (PV) in deep submicron technologies has become a major concern for energy optimization attempts on FPGAs. We develop a negative bias temperature instability (NBTI) aging-based post-silicon leakage energy optimization scheme that stresses the components that are not used or are off the critical paths to reduce the total leakage energy consumption. Furthermore, we obtain the input vectors for aging by formulating the aging objectives into a satisfiability (SAT) problem. We synthesize the low energy design on Xilinx Spartan6 FPGA and evaluate the leakage energy savings on a set of ITC99 and Opencores benchmarks.

Accurate thermal knowledge is essential for achieving ultra low power in deep sub-micron CMOS technology, as it affects gate speed linearly and leakage exponentially. We propose a temperature-aware synthesis technique that efficiently utilizes input vector control (IVC), dual-threshold voltage gate sizing (GS) and pin reordering (PR) for performing simultaneous delay and leakage power optimization. To the best of our knowledge, we are the first to consider these techniques in a synergistic fashion with thermal knowledge. We evaluate our approach by showing improvements over each method when considered in isolation and in conjunction. We also study the impact of employing considered techniques with/without accurate thermal knowledge. We ran simulations on synthesized ISCAS-85 and ITC-99 circuits on a 45 nm cell library while conforming to an industrial design flow. Leakage power improvements of up to 4.54X (2.14X avg.) were achieved when applying thermal knowledge over equivalent methods that do not.

We have developed a new security hardware primitive named digital bimodal function (DBF) that enables ultra low energy security protocols. DBF allows the computation of legitimate communicating sides to be compact and low-energy while it requires any attacker exponential computational effort and energy expense. Our new approach is competitive with the energy efficiency of traditional security key cryptographic security technique (e.g., AES) while more than three orders of magnitude more energy efficient than RSA. The implementation is demonstrated using the Xilinx FPGA platform.

We introduce a novel gate sizing approach that considers both the gate switching activity (SA) and gate input vector control leakage (IVC). We first extract SA using simulation and find promising input vectors. Next, in an iterative framework, we interchangeably conduct gate sizing and refining the IVC. As dictated by the new objective function, our algorithm conducts iterative gate freezing and unlocking with cut-based search for the most beneficial gate sizes under delay constraints. We evaluate our approach on standard benchmarks in 45 nm technology, showing promising improvement, achieving up to 62% (29% avg.) energy savings compared to the traditional objective function.

Devices manufactured in 20 nm and smaller geometry technologies will potentially be very large by today's standards, they will also have new characteristics implied by things like process variability and adoption of FinFET transistors. The industry has cumulatively adopted more and more sophisticated fault models that use timing as well as layout information. There is a growing body of experimental data showing it is still insufficient. The next area of focus will be the quality of test. Cell-aware test is one of the most promising approaches developed over the last five years aimed at improving the quality of test while maintaining the efficiency of gate-level approach. This approach combines two levels of abstraction to provide trade-offs between accuracy and efficiency. The first step creates the cell-aware test library models. It starts with standard cell libraries and performs layout extraction. Realistic defects (bridges and opens) are injected into the SPICE netlist, and analog fault simulation is performed to determine the conditions under which the defects are detected. Those conditions are aggregated to create a compact and efficient representation of the libraries for ATPG done at the gate-level. Generation of library views for cell-aware test is performed only once for a given standard cell library. The final cell-aware ATPG generates the high quality test patterns based on the cell-aware library views. This guarantees that the investment in gate-level ATPG infrastructure could be efficiently utilized. The technology has been used on a number of high-volume industrial designs. The experimental data show a significant increase of defect coverage and the corresponding improvement of defect rate.

Although vehicular sensing where mobile users in vehicles continuously gather, process, and share location-sensitive and context-sensitive sensor data (e.g., street images, road condition, traffic flow) is emerging, little effort has been investigated in a model-based energy-efficient network paradigm of sensor information sharing in vehicular environments. Upon these optimization framework, a suite of optimization subproblems: a program partitioning and network resource allocation problem, we propose a distributed vehicular sensing platform, called VeSense where mobile users in vehicles publish/access sensor data via a cloud computing-based distributed P2P overlay network. The key objective is to satisfy the vehicular sensing application's quality of service requirements by modeling each subsystem: mobile clients, wireless network medium, and distributed cloud services. By simulations based on experimental data, we present the proposed system can achieve up to 37 times more energy-efficient and 73 times faster compared to a standalone mobile application, in various vehicular sensing scenarios applying a realistic mobility model.

This paper addresses the energy attacks towards wireless systems, where energy is the most critical constraint to lifetime and reliability. We for the first time propose a hardware-based energy attack, namely energy hardware Trojans (HTs), which can be well hidden in the wireless systems and trigger ultra-high energy increases at runtime. Then, we develop a non-destructive HT detection approach to identify the energy attack by remotely sampling the power profiles of the system and characterizing the gate-level temperatures. Our evaluation results on ISCAS benchmarks indicate the effectiveness of the proposed energy attacks and defense techniques.

Hardware metering, the extraction of unique and persistent identifiers (IDs), is a crucial process for numerous integrated circuit (IC) intellectual property protection tasks. The currently known hardware metering approaches, however, are subject to alternations due to device aging, since they employ unstable manifestational IC properties. We, on the other hand, have developed the first robust hardware metering approach by using physical-level gate proprieties for ID generation. By using effective channel length, which is resilient to aging, and threshold voltage, which is essentially independent across gates and suitable for calculating the uniqueness of the IDs, we overcome the limitations of the existing approaches. Also, despite the increase in threshold voltage that occurs with aging, the original threshold voltage value can be extracted through intentional IC aging. Our ID generation procedure first employs two types of side channels, namely switching power and leakage power, to extract metering results for each gate. Next, we show that localized delay measurements alone are sufficient for accurate characterization of large sets of gates. Finally, by using threshold voltage for ID creation, we are able to obtain low probabilities of coincidence between legitimate and pirated ICs. The application of the approach to a set of benchmarks quantitatively establishes the effectiveness of the new hardware metering approach.

Wearable sensing systems have recently enabled a variety of medical monitoring and diagnostic applications in wireless health. The need for multiple sensors and constant monitoring leads these systems to be power hungry and expensive with short operating lifetimes. We introduce a novel methodology that takes advantage of contextual and semantic properties in human behavior to enable efficient design and optimization of such systems from the data and information point of view. This, in turn, directly influences the wireless communication and local processing power consumption. We exploit intrinsic space and temporal correlations between sensor data while considering both user and system contextual behavior. Our goal is to select a small subset of sensors that accurately capture and/or predict all possible signals of a fully instrumented wearable sensing system. Our approach leverages novel modeling, partitioning, and behavioral optimization, which consists of signal characterization, segmentation and time shifting, mutual signal prediction, and a simultaneous minimization composed of subset sensor selection and opportunistic sampling. We demonstrate the effectiveness of the technique on an insole instrumented with 99 pressure sensors placed in each shoe, which cover the bottom of the entire foot, resulting in energy reduction of 72% to 97% for error rates of 5% to 17.5%.

The Semiconductor Industry Associates (SIA) estimates that counterfeiting costs the US semiconductor companies $7.5B in lost revenue, and this is indeed a growing global problem. Repackaging the old ICs, selling the failed test parts, as well as gray marketing, are the most dominant counterfeiting practices. Can technology do a better job than lawyers? What are the technical challenges to be addressed? What EDA technologies will work: embedding IP protection measures in the design phase, developing rapid post- silicon certification, or counterfeit detection tools and methods?

We devise new coding methods to minimize Phase Change Memory write energy. Our method minimizes the energy required for memory rewrites by utilizing the differences between PCM read, set, and reset energies. We develop an integer linear programming method and employ dynamic programming to produce codes for uniformly distributed data. We also introduce data-aware coding schemes to efficiently address the energy minimization problem for stochastic data. Our evaluations show that the proposed methods result in up to 32% and 44% reduction in memory energy consumption for uniform and stochastic data respectively.

This paper proposes Hardware Trojan (HT) placement techniques that yield challenging HT detection benchmarks. We develop three types of one-gate HT benchmarks based on switching power, leakage power, and delay measurements that are commonly used in HT detection. In particular, we employ an iterative searching algorithm to find rarely switching locations, an aging-based approach to create ultra-low power HT, and a backtracking-based reconvergence identification method to determine the non-observable delay paths. The simulation results indicate that our HT attack benchmarks provide the most challenging representative test cases for the evaluation of side-channel based HT detection techniques.

The recent development of non-volatile memory (NVM), such as spin-torque transfer magnetoresistive RAM (STT-RAM) and phase-change RAM (PRAM), with the advantage of low leakage and high density, provides an energy-efficient alternative to traditional SRAM in cache systems. We propose a novel reconfigurable hybrid cache architecture (RHC), in which NVM is incorporated in the last-level cache together with SRAM. RHC can be reconfigured by powering on/off SRAM/NVM arrays in a way-based manner. In this work, we discuss both the architecture and circuit design issues for RHC. Furthermore, we provide hardware-based mechanisms to dynamically reconfigure RHC on-the-fly based on the cache demand. Experimental results on a wide range of benchmarks show that the proposed RHC achieves an average 63%, 48% and 25% energy saving over non-reconfigurable SRAM-based cache, non-reconfigurable hybrid cache, and reconfigurable SRAM-based cache, while maintaining the system performance (at most 4% performance overhead).

Instrumented Medical Shoes (MSs) are equipped with a variety of sensors for measurement of quantities such as pressure, acceleration, and temperature which are often greatly beneficial in numerous diagnosis, monitoring, rehabilitation, and other medical tasks. One of primary limiting factors of MSs is their energy sensitivity. In order to overcome this limitation, we have developed an optimization intensive approach for energy harvesting. Our goal is to size and position a single piezoelectric transducer for energy generation in a medical shoe in such a way that maximal energy is collected and/or specified maximal voltage is achieved while collecting energy. We propose a scenario approach that provides statistically sound solution and evaluate our approach using our medical shoe simulator for subject specific energy harvesting and generic MS scavenging. We could get 3.7X energy gain compare to smallest size sensor and 1.3X energy gain compared to sensor with the size of a shoe.

Localized multisensory systems for medical diagnostics are becoming increasingly important due to the prevalence of lightweight sensors and new collection, storage, and communication platforms such as mobile phones and tablets. These systems are often comprised of multisensory arrays that can be inefficient in terms of energy and cost both in sensing and transmission. We make the following two key observations: (i) the raw sensed data itself is unimportant, only those metrics relevant to diagnosis are needed, and (ii) it is often the case that the information relevant to medical diagnosis can be easily derived from the raw sensed data. Therefore, we drive our energy optimization procedure by selecting a subset of sensors that can predict these metrics well, eliminating all others and ultimately reducing the number of required sensors. We also develop a novel procedure for combining adjacent sensors to further reduce cost and sensing energy while increasing prediction strength. Finally, we present an algorithm for sub sampling the selected sensors that leverages the observations that: (i) most sensors need only be sampled after a physiological event is triggered, and (ii) such events tend to be predictable from semantic information and therefore a high sampling rate is unnecessary.

The continuously widening gap between the Non-Recurring Engineering(NRE) and Recurring Engineering (RE) costs of producing Integrated Circuit (IC) products in the past few decades gives high incentives to unauthorized cloning and reverse-engineering of ICs. Existing IC Digital Rights Management (DRM) schemes often demands high overhead in area, power, and performance, or require non-volatile storage. Our goal is to develop a novel Intellectual Property (IP) protection technique that offers universal protection to both Application-Specific Integrated Circuits (ASIC) and Field-Programmable Gate-Arrays (FPGAs) from unauthorized manufacturing and reverse engineering. In this paper we show a proof-of-concept implementation of the basic elements of the technique, as well as a case study of applying the anti-cloning technique to a nontrivial FPGA design.

In this paper we present the use of Benign Hardware Trojans (BHT) as a security measure for an embedded system with a software component and a hardware execution environment. Based on delay logic, process variation, and selective transistor aging, the BHT can be incorporated into an embedded system for the software and the hardware components to authenticate each other before functional execution. We will demonstrate an implementation of such a BHT within an embedded system on a Xilinx Spartan-6 FPGA platform. Using the same platform we will also show that the BHT security measurement has a low to modest amount of performance overhead basing on the test results from a variety of synthetic and real world benchmarks.

Hardware-based physically unclonable functions (PUFs) are elegant security primitives that leverage process variation inherent in modern integrated circuits. Recently proposed matched public PUFs (mPPUFs) use a combination of coordinated device aging and gate disabling to create two PUFs that securely realize identical input-output mappings. However, mPPUFs of any reasonable size allow for protocols between only a very limited number of parties. We propose quantization of possible delay values to enable matching of an unbounded number of arbitrary PPUF instances, improving stability in the presence of fluctuations in temperature or supply voltage while maintaining resiliency against a wide number of attacks.

This paper proposes a novel minimal test point insertion methodology that provisions a provably complete detection of hardware Trojans by noninvasive timing characterization. The objective of test point insertion is to break the reconvergent paths so that target routes for Trojan delay testing are specifically observed. We create a satisfiability-based input vector selection for sensitizing and characterizing each single timing path. Evaluations on benchmark circuits demonstrate that the test point-based Trojan detection can cover all circuit locations and can detect Trojans accurately with less than 5% performance overhead.

Traditional optimization methods for large multisensory networks often use sensor array reduction and sampling techniques that attempt to reduce energy while retaining full predictability of the raw sensed data. For systems such as medical sensor networks, raw data prediction is unnecessary, rather, only relevant semantics derived from the raw data are essential. We present a new method for sensor fusion, array reduction, and subsampling that reduces both energy and cost through semantics-driven system configuration. Using our method, we reduce the energy requirements of a medical shoe by a factor of 17.9 over the original system configuration while maintaining semantic relevance.

This paper addresses the hardware Trojan (HT) attacks that impose severe threats to the security and integrity of wireless networks and systems. We first develop HT attack models by embedding a single HT gate in the target design that triggers advanced malicious attacks. We place the one-gate HT trigger in such a way that it exhibits rare switching activities, consumes ultra-low leakage power, and hides from delay characterizations. Therefore, the HT attack models are capable of bypassing the widely used side channel-based HT detection schemes. Furthermore, based on the HT attack models, we investigate the potential on-line threat models during the system operation and develop an in-field trusted HT detection approach using physical unclonable functions (PUFs). We evaluate the effectiveness of the HT attack and defense models on a set of ISCAS'85, ISCAS'89, and ITC'99 benchmarks.

The Guest Editors' primary objective in organizing this Special Issue was to provide additional impetus for research in hardware security. Currently, the field is heavily dominated by testing, CAD, and IC researchers. They hope that researchers from other security fields will find the problems and the proposed solutions published here both interesting and important. Ten Special Issue papers are represented in this collection.

Modern hardware security has a very broad scope ranging from digital rights management to the detection of ghost circuitry. These and many other security tasks are greatly hindered by process variation, which makes each integrated circuit (IC) unique, and device aging, which evolves the IC throughout its lifetime. We have developed a singular value decomposition (SVD)-based procedure for gate-level characterization (GLC) that calculates changes in properties, such as delay and switching power of each gate of an IC, accounting for process variation and device aging. We employ our SVD-based GLC approach for the development of two security applications: hardware metering and ghost circuitry (GC) detection. We present the first robust and low-cost hardware metering scheme, using an overlapping IC partitioning approach that enables rapid and scalable treatment. We also map the GC detection problem into an equivalent task of GLC consistency checking using the same overlapping partitioning. The effectiveness of the approaches is evaluated using the ISCAS85, ISCAS89, and ITC99 benchmarks. In hardware metering, we are able to obtain probabilities of coincidence in the magnitude of 10-8or less, and we obtain zero false positives and zero false negatives in GC detection.

Hardware Trojans (HTs) pose a significant threat to the modern and pending integrated circuit (IC). Due to the diversity of HTs and intrinsic process variation (PV) in IC design, detecting and locating HTs is challenging. Several approaches have been proposed to address the problem, but they are either incapable of detecting various types of HTs or unable to handle very large circuits. We have developed a scalable HT detection and diagnosis approach that uses segmentation and gate level characterization (GLC). We ensure the detection of arbitrary malicious circuitry by measuring the overall leakage current for a set of different input vectors. In order to address the scalability issue, we employ a segmentation method that divides the large circuit into small sub-circuits using input vector selection. We develop a segment selection model in terms of properties of segments and their effects on GLC accuracy. The model parameters are calibrated by sampled data from the GLC process. Based on the selected segments we are able to detect and diagnose HTs by tracing gate level leakage power. We evaluate our approach on several ISCAS85/ISCAS89/ITC99 benchmarks. The simulation results show that our approach is capable of detecting and diagnosing HTs accurately on large circuits.

To improve resiliency against reverse engineering we propose dynamic physically unclonable functions (DPUFs) whose physical properties are subject to unpredictable changes between uses. We demonstrate this idea using device aging to alter delay characteristics according to user instructions.

We have developed an ultra low power (well below 1 nano-joule per transaction), ultra high speed (less than 1 nanosecond), and low cost (a few hundred gates) public physically unclonable function (PPUF). We have also developed the first PPUF-based smart card (SC). We analyze and demonstrate the security of this new SC against several families of potential security attacks.

This paper addresses integrated circuit (IC) security issues by using supply voltage based gate-level characterization (GLC). Our GLC scheme is capable of characterizing both manifestation and physical level properties of an IC accurately using variable supply voltage. We demonstrate that the proposed scheme can detect three types of IC attacks with low false positives and false negatives.

Digital rights management (DRM) of integrated circuits (ICs) is a crucially important task both economically and strategically. Several IC metering techniques have been proposed, but until now their effectiveness for royalty management has not been quantified. IC auditing is an important DRM step that goes beyond metering; it not only detects that a pirated IC has been produced but also determines the quantity of pirated ICs. Our strategic objective is to create a new intrinsic passive metering technique as well as the first IC auditing technique, and to maximize and quantify their effectiveness using statistical analysis and IC characterization techniques. Our main technical innovations include physical level gate characterization, a Bayesian approach for coincidence analysis, and an adaptation of animal counting techniques for IC production estimation. We evaluate the accuracy of the IC metering and auditing approach using simulations on a set of ISCAS benchmarks.

Current hardware metering techniques, which use manifestational properties of gates for ID extraction, are weakened by the non-uniform effects of aging in conjunction with variations in temperature and supply voltage. As an integrated circuit (IC) ages, the manifestational properties of the gates change, and thus the ID used for hardware metering can not be valid over time. Additionally, the previous approaches require large amounts of costly measurements and often are difficult to scale to large designs. We resolve the deleterious effects of aging by going to the physical level and primarily targeting the characterization of threshold voltage. Although threshold voltage is modified with aging, we can recover its original value for use as the IC identifier. Another key aspect of our approach involves using IC segmentation for gate-level characterization. This results in a cost effective approach by limiting measurements, and has a significant effect on the approach scalability. Finally, by using threshold voltage for ID creation, we are able to quantify the probability of coincidence between legitimate and pirated ICs, thus for the first time quantitatively and accurately demonstrating the effectiveness of a hardware metering approach.

Hardware Trojans (HTs) have become a major concern in modern IC industry, especially with the fast growth in IC outsourcing. HT detection and diagnosis are challenging due to the huge number of gates in modern IC designs and the high cost of testing. We propose a scalable and efficient HT detection and diagnosis scheme based on segmentation and consistency analysis of the gate-level properties. Furthermore, we develop a HT masking approach that prevents the HTs from functioning using selective device aging. We evaluate our HT detection and diagnosis schemes on a set of ISCAS and ITC benchmarks.

Gate-level characterization (GLC) is the process of quantifying physical and manifestational properties for each gate of an integrated circuit (IC). It is a key step in many IC applications that target cryptography, security, digital rights management, low power, and yield optimization. However, GLC is a challenging task due to the size and structure of modern circuits and insufficient controllability of a subset of gates in the circuit. We have developed a new approach for GLC that employs thermal conditioning to calculate the scaling factors of all the gates by solving a system of linear equations using linear programming (LP). Therefore, the procedure captures the complete impact of process variation (PV). In order to resolve the correlations in the system of linear equations, we expose different gates to different temperatures and thus change their corresponding linear coefficients in the linear equations. We further improve the accuracy of GLC by applying statistical methods in the LP formulation as well as the post-processing steps. In order to enable non-destructive hardware Trojan horse (HTH) detection, we generalize our generic GLC procedure by manipulating the constraint of each linear equation. Furthermore, we ensure the scalability of the approaches for GLC and HTH detection using iterative IC segmentation. We evaluate our approach on a set of ISCAS and ITC benchmarks.

We have developed the first technique for synthesis of trustable ICs using untrusted CAD tools. The approach enables the use of CAD tools for difficult synthesis tasks and very simple trusted tools developed by the designer for checking results and modifying specifications. The main idea is to specify the pertinent design in such a way that there is no room for the untrusted tool to add any malicious circuitry.

Gate-level characterization (GLC) is the process of characterizing each gate of an integrated circuit (IC) in terms of its physical and manifestation properties. It is a key step in the IC applications regarding cryptography, security, and digital rights management. However, GLC is challenging due to the existence of manufacturing variability (MV) and the strong correlations among some gates in the circuit. We propose a new solution for GLC by using thermal conditioning techniques. In particular, we apply thermal control on the process of GLC, which breaks the correlations by imposing extra variations concerning gate level leakage power. The scaling factors of all the gates can be characterized by solving a system of linear equations using linear programming (LP). Based on the obtained gate level scaling factors, we demonstrate an application of GLC, hardware Trojan horse (HTH) detection, by using constraint manipulation. We evaluate our approach of GLC and HTH detection on several ISCAS85/89 benchmarks. The simulation results show that our thermally conditioned GLC approach is capable of characterizing all the gates with an average error less than the measurement error, and we can detect HTHs with 100% accuracy on a target circuit.

Hardware Trojans (HTs) pose a significant threat to the modern and pending integrated circuit (IC). Several approaches have been proposed to detect HTs, but they are either incapable of detecting HTs under the presence of process variation (PV) or unable to handle very large circuits in the modern IC industry. We develop a scalable HT detection and diagnosis scheme by using segmentation techniques and gate level characterization (GLC). In order to address the scalability issue, we propose a segmentation method which divides the large circuit into small sub-circuits by using input vector control. We propose a segment selection model in terms of properties of segments and their effects on GLC accuracy. The model parameters are calibrated by sampled data from the GLC process. Based on the selected segments we are able to detect and diagnose HTs correctly by tracing gate level leakage power. We evaluate our approach on several ISCAS85/ISCAS89/ITC99 benchmarks. The simulation results show that our approach is capable of detecting and diagnosing HTs accurately on large circuits.

Network-wide broadcast has been extensively studied. In this paper, we introduce the problem of all-to- one-hop broadcast. Specifically, we are interested in the required time slots within which all nodes can receive unit-size messages from all one-hop neighbors and aim to minimize the broadcast latency. To this end, we decompose the optimal broadcast latency problem into two methodical sub-problems and present a scheduling method. To complete collision-free transmission in minimum time slots a graph-coloring scheme is used, and to reduce the overall waiting latency a linear arrangement scheme is used. Simulation studies show that the novel one-hop broadcast scheduling method can reduce the latency from 4% to 19% depending on the network size and density.

We have developed a system architecture, measuring and modeling techniques, and algorithms for on-line power and energy optimization and thermal management. The starting point for our approach is a simple and small gate-level network that can be used for real-time and low overhead measurement of temperature on chip positions where our network gates are placed. We use linear programming and interpolation to calculate the temperature at any arbitrary point of the integrated circuit. The periodic calculations of the temperature are used to estimate locally dissipated energies, which are consequently used to derive the most efficient use of operational times to minimize the overall leakage energy. All concepts and algorithms are experimentally validated using a simulation platform that consists of the Alpha 21364 processor and the SPEC benchmarks.

Due to the energy-constrained nature of wireless sensor networks (WSNs), a variety of communication protocols which rely on cluster-based topologies to enhance network capacity or to prolong network operational lifetime have been well studied heretofore. In this paper, we instead study a comprehensive perspective that searches for an optimal operation that considers backbone node placement and communication scheduling methods, as well as network connectivity properties. Specifically, we aim to answer the following three questions: how many backbone nodes are necessary, where to position these nodes, and which backbone nodes can communicate simultaneously to maximally serve the networks. We study the scalability of our approach and its dependency on parameters such as network size and density and present simulation results.

Depression is one of the leading causes of disability. Methods are needed to quantitatively classify emotions in order to better understand and treat mood disorders. This research proposes techniques to improve communication in body sensor network (BSN) that gathers data on the affective states of the patient. These BSNs can continuously monitor, discretely quantify, and classify a patient's depressive states. In addition, data on the patient's lifestyle can be correlated with his/her physiological conditions to identify how various stimuli trigger symptoms. This continuous stream of data is an improvement over a snapshot of localized symptoms that a doctor often collects during a medical examination. Our research first quantifies how the body interferes with communication in a BSN and detects a pattern between the line of sight of an embedded device and its reception rate. Then, a mathematical model of the data using linear programming techniques determines the optimal placement and number of sensors in a BSN to improve communication. Experimental results show that the optimal placement of embedded devices can reduce power cost up to 27% and reduce hardware costs up to 47%. This research brings researchers a step closer to continuous, real-time systemic monitoring that will allow one to analyze the dynamic human physiology and understand, diagnosis, and treat mood disorders.

Hardware Trojan horses (HTHs) are the malicious altering of hardware specification or implementation in such a way that its functionality is altered under a set of conditions defined by the attacker. There are numerous HTHs sources including untrusted foundries, synthesis tools and libraries, testing and verification tools, and configuration scripts. HTH attacks can greatly comprise security and privacy of hardware users either directly or through interaction with pertinent systems and application software or with data. However, while there has been a huge research and development effort for detecting software Trojan horses, surprisingly, HTHs are rarely addressed. HTH detection is a particularly difficult task in modern and pending deep submicron technologies due to intrinsic manufacturing variability.

Reliable and verifiable hardware, software and content usage metering (HSCM) are of primary importance for wide segments of e-commerce including intellectual property and digital rights management. We have developed the first HSCM technique that employs intrinsic aging properties of components in modern and pending integrated circuits (ICs) to create the first self-enforceable HSCM approach. There are variety of hardware aging techniques that range from electro-migration in wires to slow-down of crystal-based clocks. We focus on transistor aging due to negative bias temperature instability (NBTI) effects where the delay of gates increases proportionally to usage times. We address the problem of how we can measure the amount of time a particular licensed software (LS) is used by designing an aging circuitry and exposing it to the unique inputs associated with each LS. If a particular LS is used longer than specified, it automatically disables itself. Our novel HSCM technique uses a multi-stage optimization problem of computing the delays of gates, their aging degradation factors, and finally LS usage using convex programming. The experimental results show not just viability of the technique but also surprisingly high accuracy in the presence of measurement noise and imperfect aging models. HSCM can be used for many other business and engineering applications such as power minimization, software evaluation, and processor design.

We present an optimal methodology for dynamic voltage scheduling problem in the presence of realistic assumption such as leakage-power and intra-task overheads. Our contribution is an optimal algorithm for energy minimization that concurrently assumes the presence of (1) non-convex energy-speed models as opposed to previously studied convex models, (2) discrete set of operational modes (voltages) and (3) intra-task energy and delay overhead. We tested our algorithm on MediaBench and task sets used in previous papers. Our simulation results show an average of 22% improvement in energy reduction in comparison with optimal algorithms for convex models without switching overhead and on average of 24% with consideration for energy and delay overheads. This analysis lays the groundwork for improving functionality in CAD design through non-convex techniques for discrete models.

Technology scaling to nanometer nodes causes growing increase in power density and especially leakage that in turn result in locally hot regions on the chip. In this paper, we introduce a novel methodology for temperature-aware design. The methodology embeds N-versions of the scheduler and binder such that the thermal profiles of the versions are distant from each other. Next, instead of using only one version of the scheduler and binder, a rotation of N-versions of the scheduler and binder is constructed for balancing the thermal profile of the chip. We propose a linear programming framework that takes the multiple versions as the input, and constructs the thermal-aware rotational scheduling and binding by selecting the N most efficient versions and by determining the duration of each version. Our experimental evaluation shows a very low overhead and an average 5% decrease in the steady-state peak temperature produced on the benchmark designs compared to using a schedule that balances the amount of usage of different modules.

We explore the effect of certain network properties for energy balancing in wireless ad-hoc networks. We report the extent to which the improvement on energy balancing can be achieved by strategic placements of an additional relaying node in networks running energy-efficient routing protocols.

Physically unclonable functions (PUFs) provide a basis for many security and digital rights management protocols. PUF-based security approaches have numerous comparative strengths with respect to traditional cryptography-based techniques, including resilience against physical and side channel attacks and suitability for lightweight protocols. However, classical delay-based PUF structures have a number of drawbacks including susceptibility to guessing, reverse engineering, and emulation attacks, as well as sensitivity to operational and environmental variations. To address these limitations, we have developed a new set of techniques for FPGA-based PUF design and implementation. We demonstrate how reconfigurability can be exploited to eliminate the stated PUF limitations. We also show how FPGA-based PUFs can be used for privacy protection. Furthermore, reconfigurability enables the introduction of new techniques for PUF testing. The effectiveness of all the proposed techniques is validated using extensive implementations, simulations, and statistical analysis.

In this paper we present a mathematical programming formulation of the integer time budgeting problem for directed acyclic graphs. In particular, we formally prove that our constraint matrix has a special property that enables a polynomial-time algorithm to solve the problem optimally with a guaranteed integral solution. Our theory can be directly applied to solving a scheduling problem in behavioral synthesis with the objective of minimizing the system power consumption. Given a set of scheduling constraints and a collection of convex power-delay tradeoff curves for each type of operation, our scheduler can intelligently schedule the operations to appropriate clock cycles and simultaneously select the module implementations that lead to low-power solutions. Experiments demonstrate that our proposed technique can produce near-optimal results (within 6% of the optimum by the ILP formulation), with 40x+ speedup.

We present the first approach for post-silicon leakage power reduction through input vector control (IVC) that takes into account the impact of the manufacturing variability (MV). Because of the MV, the integrated circuits (ICs) implementing one design require different input vectors to achieve their lowest leakage states. We address two major challenges. The first is the extraction of the gatelevel characteristics of an IC by measuring only the overall leakage power for different inputs. The second problem is the rapid generation of input vectors that result in a low leakage for a large number of unique ICs that implement a given design, but are different in the post-manufacturing phase. Experimental results on a large set of benchmark instances demonstrate the efficiency of the proposed methods. For example, the leakage power consumption could be reduced in average by more than 10.4%, when compared to the previously published IVC techniques that did not consider MV.

We propose the use of functional magnetic resonance imaging (fMRI) systems, techniques, and tools to observe the neuron-level activity of the brains of designers or CAD tool developers. The objective is to enable designers and developers to complete their task in a faster and more creative way with significantly reduced number of logical and design errors. While fMRI techniques are already used in economics, decision and several other social sciences, until now their potential for closing the design productivity-silicon productivity (DPSP) gap has not been recognized. By compounding the new approach with techniques for designing integrated circuits and system within fMRI data collection and analysis, we will establish a positive productivity and creativity feedback loop that may permanently close the DPSP gap. As a preliminary and presently feasible step, we propose the creation of behavioral CAD research and development techniques. The usage of judiciously selected verbal, visual information and reintroduction of successful design paradigm and exposure to beneficial synthesis templates may help current and future designers to learn and design more effectively.

To ensure security and robustness of the next generation of Physically Unclonable Functions (PUFs), we have developed a new methodology for PUF design. Our approach employs integration of three key principles: (i) inclusion of multiple delay lines for creation of each response bit; (ii) transformations and combination of the challenge bits; and (iii) combination of the outputs from multiple delay lines; to create modular, easy to parameterize, secure and reliable PUF structures. Statistical analysis of the new structure and its comparison with existing PUFs indicates a significantly lower predictability, and higher resilience against circuit faults, reverse engineering and other security attacks.

System security has emerged as a premier design requirement. While there has been an enormous body of impressive work on testing integrated circuits (ICs) desiderata such as manufacturing correctness, delay, and power, there is no reported effort to systematically test IC security in hardware. Our goal is to provide an impetus for this line of research and development by introducing techniques and methodology for rigorous testing of physically unclonable functions (PUFs). Recently, PUFs received a great deal of attention as security mechanisms due to their flexibility to form numerous security protocols and intrinsic resiliency against physical and side channels attacks. We study three classes of PUFs properties to design pertinent test methods: (i) predictability, (ii) sensitivity to component accuracy, and (iii) susceptibility to reverse engineering. As our case studies, we analyze two popular PUF structures, linear and feed-forward, and show that their security is not adequate from several points of view. The technical highlights of the paper are the first non-destructive technique for PUF reverse engineering and a new PUF structure that is capable of passing our security tests.

We have created the first comprehensive and challenging benchmark data set for the ad-hoc location discovery (LD). The benchmark is a collection of representative real-life distance measurement data that establishes a common basis for understanding, characterization, evaluation and comparison of the LD algorithms and solvers. It is constructed using a novel analysis methodology that systematically establishes the difficulty of discovering the locations. Presence of measurement noise renders the problem difficult even in dense networks. The noise impacts the continuous optimization underlying the LD calculations. We focus on the difficulty of node localization in dense networks. In such networks, the location calculation is viewed as a continuous optimization problem instance with an objective function and a set of constraints. We devise a number of new metrics that evaluate the difficulty of the continuous optimization based on the data set properties. For the LD optimization, a fast simulation methodology is devised for rapid analysis of the sensitivity of the goodness with respect to the data set properties. We present a number of applications for the benchmark data and use it for evaluation and comparison of six popular LD algorithms. The LD benchmarks are publicly available at: http://www.ece.rice.edu/~mm7/benchLD/.

Power consumption has emerged as the premier and most constraining aspect in modern microprocessor and application-specific designs. Gate sizing has been shown to be one of the most effective methods for power (and area) reduction in CMOS digital circuits. Recently, as the feature size of logic gates (and transistors) is becoming smaller and smaller, the effect of soft-error rates caused by single-event upsets (SEUs) is becoming exponentially greater. As a consequence of technology feature size reduction, the SEU rate for typical microprocessor logic at sea level will go from one in hundred years to one every minute. Unfortunately, the gate sizing requirements of power reduction and resiliency against SEU can be contradictory. 1) We consider the effects of gate sizing on SEU and incorporate the relationship between power reduction and SEU resiliency to develop a new method for power optimization under SEU constraints. 2) Although a nonlinear programming approach is a more obvious solution, we propose a convex programming formulation that can be solved efficiently. 3) Many of the optimal existing techniques for gate sizing deal with an exponential number of paths in the circuit. We prove that it is sufficient to consider a linear number of constraints. 4) We generalize our methodology to include nonlinear delay models and leakage power as well. As an important preprocessing step, we apply statistical modeling and validation techniques to quantify the impact of fault masking on the SEU rate. Furthermore, we adapt our method to incorporate process variation and evaluate our gate sizing technique under uncertainty. We evaluate the effectiveness of our methodology on ISCAS benchmarks and show that error rates can be reduced by a factor of 100%-200% while, on average, the power reduction is simultaneously decreased by less than 6%-10%, respectively, compared to the optimal power saving with no error rate constraints.

Manufacturing variability is inherent to many silicon and nano-scale technologies and can be manifested in many different ways and modalities (e.g. power and delay). We propose a flow that starts with gate-level integrated circuit (IC) characterization which results in unique identification (ID). The ID's are an integrated part of the design functionality and software and provide a basis for conceptually new CAD-based security protocols. As an examples, we present a new IC metering schemes that ensure very low overhead and digital right management in horizontally integrated IC market. Therefore, after many years of CAD importing and benefiting from many other areas such as numerical analysis, theoretical CS, VLSI design, computer architectures, and compilers, CAD has its historical chance to impact many fields of computer science and engineering through manufacturing variability-based security and right management.

There is a wide consensus that performance and power consumption of IC designs in deep submicron technologies is mainly dictated by interconnect requirements. Our goal is demonstrate how compilation and architectural techniques can be used to minimize and balance interconnect requirements. Specifically, we target the use of bypass units to reduce routing congestion and eliminate long interconnections while essentially preserving or even improving the throughput requirements. We formulate the bypassing problem, establish its complexity and develop an efficient integer-linear programming (ILP) formulation. In addition to satisfying user specified interconnect requirements, we simultaneously optimize the number of operations and, therefore runtime of the targeted application. The approach is prototyped and evaluated using a platform consisting of the Trimaran architecture and compilation tools and the CPLEX ILP solver.

We introduce a remote activation scheme that aims to protect integrated circuits (IC) intellectual property (IP) against piracy. Remote activation enables designers to lock each working IC and to then remotely enable it. The new method exploits inherent unclonable variability in modern manufacturing for unique identification (ID) and integrate the IDs into the circuit functionality. The objectives are realized by replication of a few states of the finite state machine (FSM) and adding control to the state transitions. On each chip, the added control signals are a function of the unique IDs and are thus unclonable. On standard benchmark circuits, the experimental results show that the novel activation method is stable, unclonable, attack-resilient, while having a low overhead and a unique key for each IC.

We have developed a new statistical timing analysis approach that does not impose any assumptions on the nature of manufacturing variability and takes into account an arbitrary model of spatial correlation as well as all types of functional correlations (e.g. reconvergence-based correlations). The starting point for statistical timing analysis is small scale Monte Carlo (MC) simulation. In order to speed-up the MC simulation process we use stratified balanced sampling and postprocessing of the simulation data using non-parametric kernel estimation. The MC simulation and the statistical analysis procedure are interleaved with the calculation of the critical paths. In order to speed up simulation, we identify and simulate only gates relevant for calculation of the clock cycle time. The application of statistical techniques enable not only accurate statistical timing analysis, but also stability and scalability analysis. The approach is evaluated using MCNC benchmarks and yields more than six orders of magnitude speed improvement compared with the standard MC simulation.

This paper presents a new approach to reduce energy consumption of DRAM/flash memory system by lowering the frequency of DRAM refreshes. The approach is based on two ideas: (1) a DRAM based swap-cache that reduces the number of writes to the flash memory by keeping dirty pages as long as possible; and (2) OS-controlled page allocation/aging policy that stops refreshing for banks, whose pages are clean and not accessed for a long time. Simulations show that the approach can reduce the DRAM refresh energy by 59-74% and the overall energy of DRAM/flash memory system by 8-24% without increase in the execution.

Distributed wireless systems (DWSs) are emerging as the enabler for next-generation wireless applications. There is a consensus that DWS-based applications, such as pervasive computing, sensor networks, wireless information networks, and speech and data communication networks, will form the backbone of the next technological revolution. Simultaneously, with great economic, industrial, consumer, and scientific potential, DWSs pose numerous technical challenges. Among them, two are widely considered as crucial: autonomous localized operation and minimization of energy consumption. We address the fundamental problem of how to maximize the lifetime of the network using only local information, while preserving network connectivity. We start by introducing the care-free sleep (CS) Theorem that provides provably optimal conditions for a node to go into sleep mode while ensuring that global connectivity is not affected. The CS theorem is the basis for an efficient localized algorithm that decides which nodes will go to into sleep mode and for how long. We have also developed mechanisms for collecting neighborhood information and for the coordination of distributed energy minimization protocols. The effectiveness of the approach is demonstrated using a comprehensive study of the performance of the algorithm over a wide range of network parameters. Another important highlight is the first mathematical and Monte Carlo analysis that establishes the importance of considering nodes within a small number of hops in order to preserve energy.

We have developed statistical error modeling techniques for acoustic signal detection-based ranging measurements in the framework of wireless ad-hoc sensor networks (WASNs). The models are used as the basis for solving the location discovery problem in sensor networks. We first demonstrate that the major difficulty in location discovery is how to treat errors by proving the location discovery in presence of noisy measurements is a NP-complete problem, even in onedimensional space. Consequently, we formulate the location discovery as an instance of nonlinear function minimization that optimizes each of the empirically derived statistical error models. The minimization problem is then solved using a conjugate gradient-based nonlinear function optimization solver.\n We validate the efficiency of the approach by conducting comprehensive experiments on both deployed and simulated WASNs. The results indicate that the statistical model-based approach significantly improves the location accuracy compared with the approaches using the traditional optimization objectives. In addition, the localized version of our location discovery algorithm is capable of finding competitive solutions using significantly lower communication cost.

Abstract — We address the problem of energy efficient sensing by adaptively coordinating the sleep schedules of sensor nodes while guaranteeing that values of sleeping nodes can be recovered from the awake nodes within a user’s specified error bound. Our approach has two phases. First, development of models for predicting measurement of one sensor using data from other sensors. Second, creation of the maximal number of subgroups of disjoint nodes, each of whose data is sufficient to recover the measurements of the entire sensor network. For prediction of the sensor measurements, we introduce a new optimal non-parametric polynomial time isotonic regression. Utilizing the prediction models, the sleeping coordination problem is abstracted to a domatic number problem and is optimally solved using an ILP solver. To capture evolving dynamics of the instrumented environment, we monitor the prediction errors occasionally to trigger adaptation of the models and domatic partitions as needed. Experimental evaluations on traces of a medium size network with temperature and humidity sensors indicate that the method can extend the lifetime of the network by a factor of 4 or higher even for a strict error target. I.

Sensor coverage is a fundamental sensor networking design and use issue that in general tries to answer the questions about the quality of sensing (surveillance) that a particular sensor network provides. Although isotropic sensor models and coverage formulations have been studied and analyzed in great depth recently, the obtained results do not easily extend to, and address the coverage of directional and field-of-view sensors such as imagers and video cameras. In this paper, we present an optimal polynomial time algorithm for computing the worst-case breach coverage in sensor networks that are comprised of directional "field-of-view" (FOV) sensors. Given a region covered by video cameras, a direct application of the presented algorithm is to compute "breach", which is defined as the maximal distance that any hostile target can maintain from the sensors while traversing through the region. Breach translates to "worst-case coverage" by assuming that in general, targets are more likely to be detected and observed when they are closer to the sensors (while in the field of view). The approach is amenable to the inclusion of any sensor detection model that is either independent of, or inversely proportional to distance from the targets. Although for the sake of discussion we mainly focus on square fields and model the sensor FOV as an isosceles triangle, we also discuss how the algorithm can trivially be extended to deal with arbitrary polygonal field boundaries and sensor FOVs, even in the presence of rigid obstacles. We also present several simulation-based studies of the scaling issues in such coverage problems and analyze the statistical properties of breach and its sensitivity to node density, locations, and orientations. A simple grid-based approximation approach is also analyzed for comparison and validation of the implementation

We have developed a new error modeling and optimization-based localization approach for sensor networks in presence of distance measurement noise. The approach is solely based on the concept of consistency. The error models are constructed using non-parametric statistical techniques; they do not only indicate the most likely error, but also provide the likelihood distribution of particular errors occurring. The models are evaluated using the learn-and-test techniques and serve as the objective functions for the task of localization. The localization problem is formulated as task of maximizing consistency between measurements and calculated distances. We evaluated the approach in (i) both GPS-based and GPS-less scenarios; (ii) 1-D, 2-D and 3-D spaces, on sets of acoustic ranging-based distance measurements recorded by deployed sensor networks. The experimental evaluation indicates that localization of only a few centimeters is consistently achieved when the average and median distance measurement errors are more than a meter, even when the nodes have only a few distance measurements. The relative performance in terms of location accuracy compare favorably with respect to several state-of-the-art localization approaches. Finally, several insightful observations about the required conditions for accurate localization are deduced by analyzing the experimental results

Deep submicrometer technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, an ultrahigh level of integration mandates design of systems-on-chip that encompass numerous design blocks of decreased functional granularity and increased communication demands. The convergence of these two factors emphasizes the importance of the on-chip bus network as one of the crucial high-performance enablers for future systems-on-chip. An on-chip bus-network design methodology and corresponding set of tools which, for the first time, close the synthesis loop between system and physical design have been developed. The approach has three components: a communication profiler, a bus-network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus-network design component optimizes the bus-network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan; it also sends feedback about the most constrained parts of the network. The effectiveness of our bus-network design approach on a number of multicore designs is demonstrated

Task preemption is a critical enabling mechanism in multitask very large scale integration (VLSI) systems. On preemption, data in the register files must be preserved for the task to be resumed. This entails extra memory to preserve the context and additional clock cycles to save and restore the context. In this paper, techniques and algorithms to incorporate micropreemption constraints during multitask VLSI system synthesis are presented. Specifically, algorithms to insert and refine preemption points in scheduled task graphs subject to preemption latency constraints, techniques to minimize the context switch overhead by considering the dedicated registers required to save the state of a task on preemption and the shared registers required to save the remaining values in the tasks, and a controller-based scheme to preclude the preemption-related performance degradation by: 1) partitioning the states of a task into critical sections; 2) executing the critical sections atomically; and 3) preserving atomicity by rolling forward to the end of the critical sections on preemption have been developed. The effectiveness of all approaches, algorithms, and software implementations is demonstrated on real examples. Validation of all the results is complete in the sense that functional simulation is conducted to complete layout implementation.

Recently, design reuse has emerged as a dominant design and system-integration paradigm for modern systems on silicon. However, the intellectual-property-business model is vulnerable to many dangerous obstructions, such as misappropriation and copyright fraud. The authors propose a new method for intellectual-property protection that relies upon design watermarking at the combinational-logic-synthesis level. They introduce two protocols for embedding user- and tool-specific information into a logic network while performing multilevel logic minimization and technology mapping, two standard-optimization processes during logic synthesis. The hidden information can be used to protect both the design and the synthesis tool. The authors demonstrate that the difficulty of erasing or finding a valid signature in the synthesized design can be made arbitrarily computationally difficult. In order to evaluate the developed-watermarking method, the authors applied it to a standard set of real-life benchmarks, where high probability of authorship was achieved with negligible overhead on solution quality

In this paper, the classic wire-length estimation problem is addressed and a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing is proposed. These types of models are highly instrumental in formalizing a complete and consistent probabilistic approach to design automation and design closure where, along with optimizing the pertinent cost function, the associated prediction error is also considered. The wire-length prediction model was developed using a combination of parametric and nonparametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics after placement will have a particular length. The model is validated using the learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound, and therefore realistic, instances of designs. The net models were applied to the probabilistic buffer-insertion problem and substantial improvement was obtained in net delay after routing (~ 20%) when compared to a traditional bounding box (BBOX)-based buffer-insertion strategy

ASIC provides more than an order of magnitude advantage in terms of density, speed, and power requirement per gate. However, economic (cost of masks) and technological (deep micron manufacturability) trends favor FPGA as an implementation platform. In order to combine the advantages of both platforms and alleviate their disadvantages, recently a number of approaches, such as structured ASIC/regular fabrics, have been proposed. Our goal is to introduce an approach that has the same objective, but is orthogonal to those already proposed. The idea is to implement several ASIC designs in such a way that they share the datapath, memory structure, and several bottom layers of interconnect, while each design has only a few unique metal layers. We identified and addressed two main problems in our quest to develop a CAD flow for realization of such designs. They are: (i) the creation of the datapath, and (ii) the identification of common and unique interconnects for each design. Both problems are solved optimally using ILP formulations. We assembled a design flow platform using two new programs and the Trimaran and Shade tools. We quantitatively analyzed the advantages and disadvantages of the approach using the Mediabench benchmark suite.

Context-aware applications pose new challenges, including a need for new computational models, uncertainty management, and efficient optimization under uncertainty. Uncertainty can arise at two levels: multiple and single tasks. When a mobile user changes environments, the context changes resulting in the possibility of the user requesting tasks which are specific for the new environment. However as the user moves these requested tasks may no longer be context relevant. Additionally, the runtime of each task is often highly dependent on the input data. We introduce an hierarchical multi-resolution statistical task model that captures relevant aspects at the task and intertask levels, and captures not only uncertainty, but also introduces the notion of utility for the user. We have developed a system of nonparametric statistical techniques for modeling the runtime of a specific task. This model is a framework where we define problems of design and optimization of statistical soft real-time systems (SSRTS). The main algorithmic novelty is a cumulative potential-based task scheduling heuristic for maximizing utility. The heuristic conducts global optimization and induces low runtime overhead. We demonstrate the effectiveness of the scheduling heuristic using a Trimaran-based evaluation platform.

Recently, several wireless sensor network studies demonstrated large discrepancies between experimentally observed communication properties and properties produced by widely used simulation models. Our first goal is to provide sound foundations for conclusions drawn from these studies by extracting relationships between location (e.g. distance) and communication properties (e.g. reception rate) using non-parametric statistical techniques. The objective is to provide a probability density function that completely characterizes the relationship. Furthermore, we study individual link properties and their correlation with respect to common transmitters, receivers and geometrical location. The second objective is to develop a series of wireless network models that produce networks of arbitrary sizes with realistic properties. We use an iterative improvement-based optimization procedure to generate network instances that are statistically similar to empirically observed networks. We evaluate the accuracy of our conclusions using our models on a set of standard communication tasks, like connectivity maintenance and routing.

Recently, several studies have analyzed the statistical properties of low power wireless links in real environments, clearly demonstrating the differences between experimentally observed communication properties and widely used simulation models. However, most of these studies have not performed in depth analysis of the temporal properties of wireless links. These properties have high impact on the performance of routing algorithms.Our first goal is to study the statistical temporal properties of links in low power wireless communications. We study short term temporal issues, like lagged autocorrelation of individual links, lagged correlation of reverse links, and consecutive same path links. We also study long term temporal aspects, gaining insight on the length of time the channel needs to be measured and how often we should update our models.Our second objective is to explore how statistical temporal properties impact routing protocols. We studied one-to-one routing schemes and developed new routing algorithms that consider autocorrelation, and reverse link and consecutive same path link lagged correlations. We have developed two new routing algorithms for the cost link model: (i) a generalized Dijkstra algorithm with centralized execution, and (ii)a localized distributed probabilistic algorithm.

Rapid prototyping and development of in-circuit and FPGA-based emulators as key accelerators for fast time-to-market has resulted in a need for efficient error correction mechanisms. Fabricated or emulated prototypes upon error diagnosis require an effective engineering change (EC). We introduce a novel design methodology which consists of pre- and post-processing techniques that enable EC with minimal perturbation. Initially, in a synthesis preprocessing step, the original design specification is augmented with additional design constraints which ensure flexibility for future correction. Upon alteration of the initial design, a new post-processing technique achieves the desired functionality with near-minimal perturbation of the initially optimized design. The key contribution is a constraint manipulation technique which enables the reduction of an arbitrary EC problem into its corresponding classical synthesis problem. As a result, in both pre- and post-processing for EC, classical synthesis algorithms can be used to enable flexibility and perform the correction process. We demonstrate the developed EC methodology on a set of behavioral and system synthesis tasks.

Wireless ad hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Here, we address one of the fundamental problems, namely, coverage. Sensor coverage, in general, answers the questions about the quality of service (surveillance) that can be provided by a particular sensor network. We briefly discuss the definition of the coverage problem from several points of view and formally define the worst and best-case coverage in a sensor network. By combining computational geometry and graph theoretic techniques, specifically the Voronoi diagram and graph search algorithms, we establish the main highlight of the paper - an optimal polynomial time worst and average case algorithm for coverage calculation for homogeneous isotropic sensors. We also present several experimental results and analyze potential applications, such as using best and worst-case coverage information as heuristics to deploy sensors to improve coverage.

We introduce dynamic watermarking techniques for protecting the value of intellectual property of CAD and compilation tools and reusable design components. The essence of the new approach is the addition of a set of design and timing constraints which encodes the author's signature. The constraints are selected in such a way that they result in a minimal hardware overhead while embedding a unique signature that is difficult to remove and forge. Techniques are applicable in conjunction with an arbitrary behavioral synthesis task such as scheduling, assignment, allocation, transformation, and template matching.On a large set of design examples, studies indicate the effectiveness of the new approach that results in signature data that is highly resilient, difficult to detect and remove, and yet is easy to verify and can be embedded in designs with very low hardware overhead. For example, the probability that the same design with the embedded signature is obtained by any other designers by themselves is less than 1 in 10 102 , and no register overhead was incurred. The probability of tampering, the probability that part of the embedded signature can be removed by random attempts, is shown to be extremely low, and the watermark is additionally protected from such tampering with error-correcting codes.

We address the classic wire-length estimation problem and propose a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing. The wire-length prediction model was developed using a combination of parametric and non-parametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics obtained after placement will have a particular length. The model is validated using both learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound and therefore realistic instances of designs. We applied the net models to the probabilistic buffer insertion problem and obtained substantial improvement in net delay after routing.

We propose the use of multiple gateways to significantly reduce latency and energy consumption in multi-hop wireless sensor networks during data aggregation. We have derived efficient integer linear programming formulations as well as a novel negative selection statistically-tuned heuristics. The heuristics are based on newly developed relaxation based lower bounds that are also used to quantify the effectiveness of the proposed heuristics. Our simulation study indicates that the use of gateways can often reduce latency and energy consumption by several times.

Fingerprinting is an approach that assigns a unique and invisible ID to each sold instance of the intellectual property (IP). One of the key advantages fingerprinting-based intellectual property protection (IPP) has over watermarking-based IPP is the enabling of tracing stolen hardware or software. Fingerprinting schemes have been widely and effectively used to achieve this goal; however, their application domain has been restricted only to static artifacts, such as image and audio, where distinct copies can be obtained easily. In this paper, we propose the first generic fingerprinting technique that can be applied to an arbitrary synthesis (optimization or decision) or compilation problem and, therefore to hardware and software IPs. The key problem with design IP fingerprinting is that there is a need to generate a large number of structurally unique but functionally and timing identical designs. To reduce the cost of generating such distinct copies, we apply iterative optimization in an incremental fashion to solve a fingerprinted instance. Therefore, we leverage on the optimization effort already spent in obtaining previous solutions, yet we generate a uniquely fingerprinted new solution. This generic approach is the basis for developing specific fingerprinting techniques for four important problems in VLSI CAD: partitioning, graph coloring, satisfiability, and standard-cell placement. We demonstrate the effectiveness of the new fingerprinting-based IPP techniques on a number of standard benchmarks.

We have developed a new optimization paradigm for solving computationally intractable combinatorial optimization and synthesis problems. The technique, named probabilistic constructive, combines the advantages of both constructive and probabilistic optimization mechanisms. Since it is a constructive approach, it has a relatively short runtime and is amenable for the inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible tradeoff between runtime and the quality of solution, suitability for the superimposition of a variety of control strategies, and simplicity of implementation. After presenting the generic technique, we apply it to a generic NP-complete problem (maximum independent set) and a synthesis and compilation problem (sequential code covering). Extensive experimentation indicates that the new approach provides very attractive tradeoffs between the quality of solution and runtime, often outperforming the best previously published approaches.

Computational forensic engineering (CFE) aims to identify the entity that created a particular intellectual property (IP). Specifically, our goal is to identify the synthesis tool or compiler which was used to produce a specific design or program. Rather than relying on watermarking content or designs, the generic CFE methodology analyzes the statistics of certain features of a given IP and quantizes the likelihood that a well known source has created it. In this paper, we describe the generic methodology of CFE and present a set of techniques that, given a set of compilation tools, identify the one used to generate a particular hardware/software design. The generic CFE approach has four phases: 1) feature and statistics data collection; 2) feature extraction; 3) entity clustering; and 4) validation. In addition to IP protection, the developed CFE paradigm can have other potential applications: optimization algorithm selection and tuning, benchmark selection, and source-verification for mobile code.

Watermarking is one of the most effective mechanisms for intellectual property protection (IPP) of hardware and software artifacts. Numerous watermarking-based IPP techniques have been proposed that satisfy a spectrum of IPP desiderata, including full preservation of functionality, low timing, area and power overhead, transparency to the synthesis and compilation process, and resilience against attacks. Two objectives that are very important, but, until now have not yet been properly addressed, are credibility and fairness. We present a new watermarking technique that specifically targets credibility and fairness. Using a combinatorial result by Valiant and Vazirani, we demonstrate how these two desiderata can be achieved during the watermarking of a satisfiability (SAT) instance. The effectiveness of the technique is demonstrated on both specially created examples, where the number of solutions is known, as well as on common computer-aided design and operational research SAT benchmark instances.

This paper introduces hot potato behavioral synthesis transformation techniques. These techniques add deflection operations in the behavioral description of a computation in such a way that the requirements for two important components of the final implementation cost, the number of registers and the number of interconnects, are significantly reduced. Moreover, we demonstrate how hot potato techniques can be effectively used during behavioral synthesis to minimize the partial scan overhead to make the synthesized design testable.

Recently, a number of watermarking-based intellectual property protection techniques have been proposed. Although they have been applied to different stages in the design process and have a great variety of technical and theoretical features, all of them share two common properties: 1) they are applied solely to optimization problems and 2) do not involve any optimization during the watermarking process. In this paper, we propose the first set of optimization-intensive watermarking techniques for decision problems. In particular, we demonstrate, by example of the Boolean satisfiability (SAT) problem, how one can select a subset of superimposed watermarking constraints so that the uniqueness of the signature and the likelihood of satisfying the satisfiability problem are simultaneously maximized. We have developed three SAT watermarking techniques: adding clauses, deleting literals, and push-out and pull-back. Each technique targets different types of signature-induced constraint superimposition on an instance of SAT problem. In addition to comprehensive experimental validation, we theoretically analyze the potentials and limitations of the proposed watermarking techniques. Furthermore, we analyze the three proposed optimization-intensive watermarking SAT techniques in terms of their suitability for copy detection.

Summary and Conclusions -A novel methodology is proposed for designing fault-tolerant real-time multi-processor systems-on-a-chip to achieve optimal productivity. The methodology employs the heterogeneous built-in-self-repair (BISR) based on graceful degradation and yield enhancement techniques as an embedded optimization engine. The technique exploits the flexibility provided in task-level scheduling and algorithm selection steps. A hardware fault model is developed for modern super-scalar processors and multi-processors which enables an efficient treatment of the synthesis and compilation goals. For the first time, heterogeneous BISR is used at the task level. The key idea is to adapt scheduling and algorithm selection to the available nonfaulty resources. If there is a fault in memory, the algorithms that use less memory are selected and the scheduler exploits the other abundant resource, viz, the processors, more vigorously to compensate for the loss of part of memory. Similarly, a fault in a processor is backed up by memory. The synthesis approach minimizes the degradation in performance for single or multiple faults using simulated annealing-based algorithm selection, scheduling, and assignment algorithms. On the large set of examples this adaptive algorithm selection and scheduling technique has achieved important improvement of throughput compared to conventional nonadaptive schemes. The experimental results also indicate that important improvement in productivity can be achieved by using the extra throughput gained from the technique.

The majority of modern multimedia and mobile systems have two common denominators: quality-of-service (QoS) requirements, such as latency and synchronization, and strict energy constraints. However, until now no synthesis techniques have been proposed for the design and efficient use of such systems. We have two main objectives: conceptual and synthesis. The conceptual objective is to develop a generic practical technique for the automatic development of online adaptive algorithms from efficient off-line algorithms using statistical techniques. The synthesis objective is to introduce the first design technique for QoS low-power synthesis. We introduce a system of provably-optimal techniques that minimize energy consumption of stream-oriented applications under two main QoS metrics: latency and synchronization. Specifically, we study how multiple voltages can be used to simultaneously satisfy hardware constraints and minimize power consumption while preserving the requested level of QoS. The purpose of the off-line algorithm is threefold. First, it is used as input to statistical software which is used to identify important and relevant parameters of the processes. Second, the algorithm provides buffer occupancy rate indicators. Lastly, it provides a way to combine buffer occupancy and QoS metrics to form a fast and efficient online algorithm. The effectiveness of the algorithms is demonstrated on a number of standard multimedia benchmarks.

Majority of modern mobile systems have two common denominators: quality-of-service (QoS) requirements, such as latency and synchronization, and strict energy constraints. However, until now no synthesis techniques have been proposed for the design and efficient use of such systems. We have two main objectives: synthesis and conceptual. The synthesis goal is to introduce the first design technique for quality-of-service (QoS) low power synthesis. The conceptual objective is to develop a generic technique for the automatic development of on-line algorithms from efficient off-line algorithms using statistical techniques.We first summarize a system of provably-optimal techniques that minimize energy consumption of stream-oriented applications under two main QoS metrics: latency and synchronization. Specifically, we study how multiple voltages can be used to simultaneously satisfy hardware requirements and minimize power consumption, while preserving the requested level of QoS in terms of latency and synchronization. The off-line algorithm is used as input to statistical software used to identify important relevant parameters of the processes, buffer occupancy rate indicators, and a way how combine them to form a fast and efficient on-line algorithm which decides which task to run at which voltage. The effectiveness of the algorithms is demonstrated on a number of standard multimedia benchmarks.

We propose the first systematic, sensor-centric approach for quantitative design of sensor network appliances. We demonstrate its use by designing light appliance devices and the associated middleware. We have developed five models which are required to make this problem tractable and to undertake the challenging task of designing light sensor appliances: (i) physical world, (ii) light sensor, (iii) physical phenomenon, (iv) appliance design, and (v) computational model. With these models in place, we present the new design methodology that consists of two mains steps: (1) a procedure for placement of individual sensors of the appliance, and (2) error minimization-based sensor data interpretation middleware. We have developed new optimization techniques for both tasks. A portable light sensor system was designed using the optimization intensive procedure, and its effectiveness demonstrated.

The prediction by partial matching (PPM) algorithm uses a cumulative frequency count of input symbols in different contexts to estimate its probability distribution. Compression ratios yielded by the PPM algorithm have not instigated broader use of this scheme mainly because of its high demand for computational resources. An algorithm that improves the memory usage by the PPM model is presented. The algorithm identifies and removes portions of the PPM model, which are not contributing toward better modeling of the input data. As a result, our algorithm improves the average compression ratio up to 7% under the memory limitation constraint at the expense of increased computation. Under the constraint of maintaining the same level of compression ratios, the algorithm reduces the memory usage up to 70%.

Distributed wireless ad-hoc networks (DWANs) pose numerous technical challenges. Among them, two are widely considered as crucial: autonomous localized operation and minimization of energy consumption. We address the fundamental problem of how to maximize life-time of the network by using only local information while preserving network connectivity. We start by introducing the Care-Free Sleep (CS) Theorem that provides provably optimal necessary and sufficient conditions for a node to turn off its radio while ensuring that global connectivity is not affected.The CS theorem is the basis for an efficient localized algorithm that decides which node will turn its radio off, and for how long. The effectiveness of the approach is demonstrated using numerous simulations of the performance of the algorithm over a wide range of network parameters.

We present a technique for compression of shortest paths routing tables for wireless ad hoc networks. The main characteristic of such networks is that geographic location of nodes determines network topology. As opposed to encoding individual node locations, at each node our approach groups the remaining nodes in the network into regions. All shortest paths to nodes in a specific region are routed via the same neighboring node. In this paper, we propose an algorithm for dividing a network field into distinct regions to minimize routing table size while guaranteeing shortest path routes. We show that this problem is NP-hard, propose a heuristic to find efficient solutions, and empirically demonstrate the resulting system performance from the perspective of compression ratio and scalability. In our experiments, routing tables compressed using this technique, require 88.9% to 97.9% less storage than uncompressed tables.In order to achieve energy efficient routing, we propose an augmentation to the original routing mechanism that enables load balancing flexibility along with guaranteed shortest path routing at the expense of larger routing tables. Preliminary experiments estimate 10% lifetime extension of network nodes with a tradeoff of an increase in the size of routing tables. Finally, we propose a compression technique that aims at representing trajectories in a sensing network in a compact manner. This approach relies on trajectory prediction using three weighted Markov models, a local, regional and global one, all of them with context-length equal to one. Finally, we discuss a range of possible applications that rely on the developed prediction and routing models.

Sensor networks not only have the potential to change the way we use, interact with, and view computers, but also the way we use, interact with, and view the world around us. In order to maximize the effectiveness of sensor networks, one has to identify, examine, understand, and provide solutions for the fundamental problems related to wireless embedded sensor networks. We believe that one of such problems is to determine how well the sensor network monitors the instrumented area. These problems are usually classified as coverage problems. There already exist several methods that have been proposed to evaluate a sensor network's coverage.We start from one of such method and provide a new approach to complement it. The method of using the minimal exposure path to quantify coverage has been optimally solved using a numerical approximation approach. The minimal exposure path can be thought of as the worst-case coverage of a sensor network. Our first goal is to develop an efficient localized algorithm that enables a sensor network to determine its minimal exposure path. The theoretical highlight of this paper is the closed-form solution for minimal exposure in the presence of a single sensor. This solution is the basis for the new and significantly faster localized approximation algorithm that reduces the theoretical complexity of the previous algorithm. On the other hand, we introduce a new coverage problem - the maximal exposure path - which is in a sense the best-case coverage path for a sensor network. We prove that the maximal exposure path problem is NP-hard, and thus, we provide heuristics to generate approximate solutions.In addition, we demonstrate the effectiveness of our algorithms through several simulations. In the case of the minimal single-source minimal exposure path, we use variational calculus to determine exact solutions. For the case of maximal exposure, we use networks with varying numbers of sensors and exposure models.

Recently, the electronic design automation industry has adopted the intellectual property (IP) business model as a dominant system-on-chip development platform. Since copyright fraud has been recognized as the most devastating obstruction to this model, a number of techniques for IP protection have been introduced. Most of them rely on a selection of a global solution to a design optimization problem according to a unique user-specific digital signature. Although such techniques provide strong proof of authorship, they fail to provide an effective procedure for watermark detection when a protected core design is augmented into a larger design. To address this fundamental issue, we introduce local watermarks, an IP protection technique which facilitates watermark detection in many realistic design and adversarial scenarios, while satisfying the demand for low overhead and design transparency. We demonstrate the efficiency of the new IP protection paradigm by applying its principles to a set of behavioral synthesis tasks such as operation scheduling and template matching.

Modern system design is being increasingly driven by applications such as multimedia and wireless sensing and communications, which have intrinsic quality of service (QoS) requirements, such as throughput, error-rate, and resolution. One of the most crucial QoS guarantees that the system has to provide is the timing constraint among the interacting media (synchronization) and within each media (latency). We have developed the first framework for system design with timing QoS guarantees. In particular, we address how to design system-on-chip with minimum silicon area to meet both latency and synchronization constraints. The proposed design methodology consists of two phases: hardware configuration selection and on-chip memory/storage minimization. In the first phase, we use silicon area and system performance as criteria to identify all the competitive hardware configurations (i.e., Pareto points) that facilitate the needs of synchronous applications. In the second phase, we determine the minimum on-chip memory requirement to meet the timing constraints for each Pareto point. An overall system evaluation is conducted to select the best system configuration. We have developed optimal algorithms that schedule a priori specified applications to meet their synchronization requirements with the minimum size of memory. We have also implemented on-line heuristics for real-time applications. The effectiveness of our algorithms has been demonstrated on a set of simulated MPEG streams from popular movies.

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, while running, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. Existing techniques address this problem by trying to detect the intrusion at run-time or by formally verifying that the software is not prone to a particular attack.We take a radically different approach to this problem. We aim at intrusion prevention as the core technology for enabling secure computing systems. Intrusion prevention systems force an adversary to solve a computationally hard task in order to create a binary that can be executed on a given machine. In this paper, we present an exemplary system--SPEF--a combination of architectural and compilation techniques that ensure software integrity at run-time. SPEF embeds encrypted, processor-specific constraints into each block of instructions at software installation time and then verifies their existence at run-time. Thus, the processor can execute only properly installed programs, which makes installation the only system gate that needs to be protected. We have designed a SPEF prototype based on the ARM instruction set and validated its impact on security and performance using the MediaBench suite of applications.

We have developed a generic integer linear programming(ILP)-based engineering change(EC) methodology. The EC methodology has three components: enabling, fast, and preserving. Enabling EC provides a user with the means to specify the amount of flexibility and how this flexibility should be distributed throughout the solution so that one can guarantee that a specific set of EC demands can be satisfied while preserving the quality of the initially obtained solution. Fast EC conducts changes in a fraction of the time needed to solve the problem while preserving or in some cases improving the quality of the initial solution. Preserving EC maintains either user specified components of the solution or as much as possible of the initial solution while still guaranteeing an optimal solution to the altered problem instance. We applied the generic methodology to Boolean Satisfiability (SAT) problem. The effectiveness of all proposed approaches and algorithms is demonstrated on standard benchmarks.

Linear programming (LP) in its many forms has proven to be an indispensable tool for expressing and solving optimization problems in numerous domains. We propose the first set of generic watermarking techniques for integer-LP (ILP). The proof of authorship by watermarking is achieved by introducing additional constraints to limit the solution space and can be used as effective means of intellectual property protection (IPP) and authentication. We classify and analyze the types of constraints in the ILP watermarking domain and show how ILP formulations provide more degrees of freedom for embedding signatures than other existing approaches. To demonstrate the effectiveness of the proposed ILP watermarking techniques, the generic discussion is further concretized using two examples, namely Satisfiability and Scheduling.

The effectiveness of traditional CAD optimization algorithms is proportional to the accuracy of the targeted objective functions. However, behavioral synthesis tools are not used in isolation; they form a strongly connected design flow where each tool optimizes its own objective function without considering the consequences on the optimization goals of the subsequently applied tools. Therefore, efforts to optimize one aspect of a design often have unforeseen negative impacts on other phases of the design process.

We address location discovery problem in ad-hoc wireless Networks. Location discovery is a task with fundamental role in multi-hop wireless networks since many other middleware tasks, such as coverage, tracking and routing, as well as many applications need accurate location of nodes. We have developed simple, yet accurate mathematical abstraction of the problem. We have also developed an atomic tri-lateration procedure for calculating the position of a node in presence of measurements errors. We have statistically analyzed the procedure with respect to a number of parameters, such as error distribution and relative positions of the nodes and used that information for improving effectiveness of the location discovery procedure. Furthermore, we have developed randomized iterative improvement algorithm for fast location discovery in wireless ad-hoc networks. We experimentally verified the exceptional effectiveness of the procedure in presence of errors for both cetralized and localized version of the algorithm.

Recently embedded wireless sensor networks (EWSN) have emerged as a solution to bridge the gap between the physical (and chemical and biological) world and the information world of the Internet. Deployment and effective use of EWSN posses numerous conceptual and technological challenges. In particular, there is a genuine need for the coordinated use of techniques from a variety of scientific and engineering fields, including DSP, computer science, information theory, communication, and applied mathematics. We address the problem of search in sensor networks using techniques from DSP and computer science. The search problem encompasses tasks such as indexing, stream searching, information filtering, semantic and syntax compression, profiling and recommending. The development of search tools will greatly facilitate efforts in many application of sensor networks, including event monitoring, low power operation, and physical space modelling. EWSN also poses unique challenges. For example, in the case of power and storage limitations, the key requirement is distributed space localized processing. The technical highlights of the paper include the first statistical stream search technique, the first technique for simultaneous search of correlated streams and the first technique for effective acquisition of correlated information under bandwidth and power constraints.

Our goal is to identify the key architectural and design issues related to Sensor Networks (SNs), evaluate the proposed solutions, and to outline the most challenging research directions. The evaluation has three scopes ndividual components on SN nodes (processor, communication, storage, sensors, actuators, and power supply), node level and networked system level. The special emphasis is placed on architecture and system software, and on new challenges related to the usage of new types of components in networked systems. The evaluation is guided by anticipated technology trends and both current and future applications. The main conclusion of the analysis is that the architectural and synthesis emphasis will be shifted from computation and to some extent communication components to sensors and actuators.

The authors introduce an Intellectual Property Protection (IPP) technique for graph partitioning which watermarks solutions to the graph partitioning problems so that they carry an author's signature. This technique is completely transparent to the actual computer-aided design tool which does the partitioning and is implemented by preprocessing and postprocessing alone. The authors propose five different schemes for the watermarking of partitioning solutions. The goal is to construct a partitioning solution which not only has a small edge cut, but also encodes the signature of the author. The key idea of all of our schemes is to map the signature into a set of constraints and then satisfy a disproportionate number of these constraints. Four of our schemes are based upon the idea of encouraging groups of vertices to be in the same partition. The fifth is based upon the encouragement of certain edges to be cut by the partitioning. The fifth scheme shows superior performances on all of the cases which we tested, including both two-way and multiway partitioning. The watermarking scheme produces solutions that have very low-quality degradation levels, yet carry signatures that are convincingly unambiguous, extremely unlikely to be present by coincidence and difficult to detect or remove without completely resolving the partitioning problem.

The performance of many modern computer and communication systems is dictated by the latency of communication pipelines. At the same time, power/energy consumption is often another limiting factor in many portable systems. We address the problem of how to minimize the power consumption in system-level pipelines under latency constraints. In particular, we apply fragmentation technique to achieve parallelism and exploit advantages provided by variable voltage design methodology to optimally select voltage and, therefore, speed of each pipeline stage. We focus our study on the practical case when each pipeline stage operates at a fixed speed. Unlike the conventional pipeline system, where all stages run at the same speed, our system may have different stages running at different speeds to conserve energy while providing guaranteed latency. For a given latency requirement, we find explicit solutions for the most energy efficient fragmentation and and voltage setting. We further study a less practical case when each stage can dynamically change its speed to get further energy saving. We define the problem and transform it to a nonlinear system whose solution provides a lower bound for energy consumption.

Recently, the Internet revolutionized many activities from entertainment to marketing and business. Two key underlying Internet technologies, efficient data delivery and hypertext, demonstrated exceptional potential as new application enablers. In this paper, we present a novel Hypermedia-Aided Design (HAD) collaboration framework that facilitates new communication and data presentation paradigms to improve the effectiveness of typical EDA applications. The framework leverages on the advantages of using semantic multicast as a communication backbone and quantized hypermedia presentations as an efficient data organization, retrieval, and presentation model. Semantic multicast is a global communication tool that relies on an inter-network of proxies to provide content discovery and semantics-based profile-driven data dissemination services. We introduce the notion of a quant, an atomic interactive multimedia information primitive with embedded hyperlinks. We demonstrate how interest-specific quant retrieval and concatenation can enable more focused collaboration.

Currently, hardware intellectual property (IP) is delivered at three levels of abstraction: hard, firm, and soft. In order to further enhance performance, efficiency, and flexibility of IP design, we have developed a new approach for designing hardware and software IP called MetaCores. The new design approach starts at the algorithm level and leverages on the algorithms intrinsic optimization degrees of freedom. The approach has four main components: (i) problem formulation and identification of optimization degrees of freedom, (ii) objective functions and constraints, (iii) cost evaluation engine, and (iv) multiresolution design space search. From the algorithmic viewpoint, the main contribution is the introduction of multiresolution search in algorithm optimization and synthesis process. We have applied the approach to the development of Viterbi and IIR MetaCores. Experimental results demonstrate the effectiveness of the new approach.

Trends in the semiconductor industry towards extensive design and code reuse motivate a need for adequate Intellectual Property Protection (IPP) schemes. We offer a new general IPP scheme called constraint-based watermarking and analyize it in the context of the graph partitioning problem. Graph partitioning is a critical optimization problem that has many applications, particularly in the semiconductor design process. Our IPP technique for graph partitioning watermarks solutions to graph partitioning problems so that they carry an author's signature. Our technique is transparent to the actual CAD tool which does the partitioning. Our technique produces solutions that have very low quality degradation levels, yet carry signatures that are convincingly unambiguous, extremely unlikely to be present by coincidence, and difficult to detect or remove without completely resolving the partitioning problem.

Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical environments. One of the major challenges in devising such networks lies in the constrained energy and computational resources available to sensor nodes. These constraints must be taken into account at all levels of the system hierarchy. The deployment of sensor nodes is the first step in establishing a sensor network. Since sensor networks contain a large number of sensor nodes, the nodes must be deployed in clusters, where the location of each particular node cannot be fully guaranteed a priori. Therefore, the number of nodes that must be deployed in order to completely cover the whole monitored area is often higher than if a deterministic procedure were used. In networks with stochastically placed nodes, activating only the necessary number of sensor nodes at any particular moment can save energy. We introduce a heuristic that selects mutually exclusive sets of sensor nodes, where the members of each of those sets together completely cover the monitored area. The intervals of activity are the same for all sets, and only one of the sets is active at any time. The experimental results demonstrate that by using only a subset of sensor nodes at each moment, we achieve a significant energy savings while fully preserving coverage.

We propose a new optimization paradigm for solving intractable combinatorial problems. The technique, named Probabilistic Constructive (PC), combines the advantages of both constructive and probabilistic algorithms. The constructive aspect provides relatively short runtime and makes the technique amenable for the inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible trade-off between runtime and the quality of solution. In addition to presenting the generic technique, we apply it to the Maximal Independent Set problem. Extensive experimentation indicates that the new approach provides very attractive trade-offs between the quality of the solution and runtime, often outperforming the best previously published approaches.

Wireless ad-hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Some, such as location, deployment, and tracking, are fundamental issues, in that many applications rely on them for needed information. We address one of the fundamental problems, namely coverage. Coverage in general, answers the questions about quality of service (surveillance) that can be provided by a particular sensor network. We first define the coverage problem from several points of view including deterministic, statistical, worst and best case, and present examples in each domain. By combining the computational geometry and graph theoretic techniques, specifically the Voronoi diagram and graph search algorithms, we establish the main highlight of the paper-optimal polynomial time worst and average case algorithm for coverage calculation. We also present comprehensive experimental results and discuss future research directions related to coverage in sensor networks.

Wireless ad-hoc sensor networks will provide one of the missing connections between the Internet and the physical world. One of the fundamental problems in sensor networks is the calculation of coverage. Exposure is directly related to coverage in that it is a measure of how well an object, moving on an arbitrary path, can be observed by the sensor network over a period of time. In addition to the informal definition, we formally define exposure and study its properties. We have developed an efficient and effective algorithm for exposure calculation in sensor networks, specifically for finding minimal exposure paths. The minimal exposure path provides valuable information about the worst case exposure-based coverage in sensor networks. The algorithm works for any given distribution of sensors, sensor and intensity models, and characteristics of the network. It provides an unbounded level of accuracy as a function of run time and storage. We provide an extensive collection of experimental results and study the scaling behavior of exposure and the proposed algorithm for its calculation. I.

Despite enormous progress in networking and computing technologies, their application has remained restricted to conventional person-to-person and person-to-computer communication. However, continual reduction in cost and form factor is now making it possible to imbed networking - even wireless networking - and computing capabilities not just in our PCs and laptops but also other objects. Further, a marriage of these ever tinier and cheaper processors and wireless network interfaces with emerging micro-sensors based on MEMS technology is allowing cheap sensing, processing, and communication capabilities to be unobtrusively embedded in familiar physical objects. The result is an emerging paradigm shift where the primary role of information technology would be to enhance or assist in "person to physical world communication via familiar physical objects with embedded (a) micro-sensors to react to external stimuli, and (b) wireless networking and computing engines for tetherless communication with compute servers and other networked embedded objects. In this paper we present the application of sensor-based wireless networks to a "Smart Kindergarten that we are developing to target developmental problem-solving environments for early childhood education. This is a natural application as young children learn by exploring and interacting with objects such as toys in their environment. Our envisioned system would enhance the education process by providing a childhood learning environment that is individualized to each child, adapts to the context, coordinates activities of multiple children, and allows continual unobtrusive evaluation of the learning process by the teacher. This would be done by wirelessly-networked, sensor-enhanced toys and other classroom objects with back-end middleware services and database techniques. We explore wireless networking, middleware, and data management technologies for realizing this application, and describe challenges arising from ad hoc distributed structure, unreliable sensing, large scale/density, and novel sensor data types that are characteristic of such deeply instrumented environments with inter-networked physical objects.

The development of practical, localization algorithms is probably the most needed and most challenging task in wireless ad-hoc sensor networks (WASNs). Localized algorithms are a special type of distributed algorithms where only a subset of nodes in the WASN participate in sensing, communication, and computation. We have developed a generic localized algorithm for solving optimization problems in wireless ad-hoc networks that has five components: (i) data acquisition mechanism, (ii) optimization mechanism, (iii) search expansion rules, (iv) bounding conditions and (v) termination rules. the main idea is to request and process data only locally and only from nodes who are likely to contribute to rapid formation of the final solution. The approach enables two types of optimization: The first, guarantees the fraction of nodes that are contacted while optimizing for solution quality. The second, provides guarantees on solution qualities while minimizing the number of nodes that are contacted and/or amount of communication. The localized optimization approach is applied to two fundamental problems in sensor networks: location discovery and exposure-based coverage. We demonstrate its effective-ness on a number of examples

Digital system designs are the product of valuable effort and know-how. Their embodiments, from software and hardware description language program down to device-level netlist and mask data, represent carefully guarded intellectual property (IP). Hence, design methodologies based on IP reuse require new mechanisms to protect the rights of IP producers and owners. This paper establishes principles of watermarking-based IP protection, where a watermark is a mechanism for identification that is: (1) nearly invisible to human and machine inspection; (2) difficult to remove; and (3) permanently embedded as an integral part of the design. Watermarking addresses IP protection by tracing unauthorized reuse and making untraceable unauthorized reuse as difficult as recreating given pieces of IP from scratch. We survey related work in cryptography and design methodology, then develop desiderata, metrics, and concrete protocols for constraint-based watermarking at various stages of the very large scale integration (VLSI) design process. In particular, we propose a new preprocessing approach that embeds watermarks as constraints into the input of a black-box design tool and a new postprocessing approach that embeds watermarks as constraints into the output of a black-box design tool. To demonstrate that our protocols can be transparently integrated into existing design flows, we use a testbed of commercial tools for VLSI physical design and embed watermarks into real-world industrial designs. We show that the implementation overhead is low-both in terms of central processing unit time and such standard physical design metrics as wirelength, layout area, number of vias, and routing congestion. We empirically show that the placement and routing applications considered in our methods achieve strong proofs of authorship and are resistant to tampering and do not adversely influence timing.

Symbolic debuggers are system-development tools that can accelerate the validation speed of behavioral specifications by allowing a user to interact with an executing code at the source level. In response to a user query, the debugger must retrieve and display the value of a source variable in a manner consistent with user expectations with respect to the source statement where execution has halted. However, when a behavioral specification has been optimized using transformations, values of variables may either be inaccessible in the runtime state or inconsistent with user expectations. We address the problem that pertains to the retrieval of source values for the globally optimized behavioral specifications. We present a new approach for symbolic debugging. The implementation of the new debugging approach poses several optimization tasks. We formulate the optimization tasks and develop heuristics to solve them. We demonstrate the effectiveness of the proposed approach on a set of designs.

As current computer-aided design (CAD) tool and very large scale integration technology capabilities create a new market of reusable digital designs, the economic viability of this new core-based design paradigm is pending on the development of techniques for intellectual property protection. This work presents the first technique that leverages the unique characteristics of field-programmable gate arrays (FPGAs) to protect commercial investment in intellectual property through fingerprinting. A hidden encrypted mark is embedded into the physical layout of a digital circuit when it is placed and routed onto the FPGA. This mark uniquely identifies both the circuit origin and original circuit recipient, yet is difficult to detect and/or remove, even via recipient collusion. While this approach imposes additional constraints on the backend CAD tools for circuit place and route, experiments indicate that the performance and area impacts are minimal.

We evaluate the validity of the fundamental assumption behind application-specific programmable processors: that applications differ from each other in key parameters which are exploitable, such as the available instruction-level parallelism (ILP), demand on various hardware resources, and the desired mix of function units. Following the tradition of the CAD community, we develop an accurate chip area estimate and a set of aggressive hardware optimization algorithms. We follow the tradition of the architecture community by using comprehensive real-life benchmarks and production quality tools. This combination enables us to build a unique framework for system-level synthesis and to gain valuable insights about design and use of application-specific programmable processors for modern applications. We explore the application-specific programmable processor (ASSP) design space to understand the relationship between performance and area. The architecture model we used is the Hewlett Packard PA-RISC with single level caches. The system, including all memory and bus latencies, is simulated and no other specialized ALU or memory structures are being used. The experimental results reveal a number of important characteristics of the ASSP design space. For example, we found that in most cases a single programmable architecture performs similarly to a set of architectures that are tuned to individual application. A notable exception is highly cost sensitive designs, which we observe need a small number of specialized architectures that require smaller areas. Also, it is clear that there is enough parallelism in the typical media and communication applications to justify use of high number of function units. We found that the framework introduced in this paper can be very valuable in making early design decisions such as area and architectural configuration tradeoff, cache and issue width tradeoff under area constraint, and the number of branch units and issue width.

No abstract available.

Article A technique for QoS-based system partitioning Share on Authors: Johnson S. Kin Electrical Engineering Department, University of California at Los Angeles, Los Angeles, CA Electrical Engineering Department, University of California at Los Angeles, Los Angeles, CAView Profile , Chunho Lee Computer Science Department, University of California at Los Angeles, Los Angeles, CA Computer Science Department, University of California at Los Angeles, Los Angeles, CAView Profile , William H. Mangione-Smith Electrical Engineering Department, University of California at Los Angeles, Los Angeles, CA Electrical Engineering Department, University of California at Los Angeles, Los Angeles, CAView Profile , Miodrag Potkonjak Computer Science Department, University of California at Los Angeles, Los Angeles, CA Computer Science Department, University of California at Los Angeles, Los Angeles, CAView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 241–246https://doi.org/10.1145/368434.368620Published:28 January 2000 0citation1,245DownloadsMetricsTotal Citations0Total Downloads1,245Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Many intellectual property protection (IPP) techniques have been proposed. Their primary objectives are providing convincible proof of authorship with least degradation of the quality of the intellectual property (IP), and achieving robustness against attacks. These are also well accepted as the most important criteria to evaluate different IPP techniques. The essence of such techniques is to limit the solution space by embedding signatures as constraints. One key issue that should be addressed but has not been discussed is the fairness of the techniques: what is the quality of the solution subspace for different signatures, that is, how large the solution subspace is (uniqueness), and how difficulty it is to get a solution from such subspace (hardness)? In this paper, we introduce fairness as one of the metrics for good IPP techniques and post the challenge problem of how to design fair watermarking techniques. We claim that all fair techniques have to be instanceoriented and due to the complexity of the problem itself, we propose an approach that utilizes the statistical information of the problem instance. We use the satisfiability (SAT) problem as an example to illustrate how fairness could be achieved. We make the observation that the unfairness of the previous watermarking techniques comes from the global embedding of the signature and propose fair watermarking techniques. We test the uniqueness and hardness on a model with full knowledge of the solution and real life benchmarks as well. The experimental results show fairness can be achieved. 1

The proliferation of the Internet has affected the business model of almost all semiconductor and VLSI CAD companies that rely on intellectual property (IP) as their main source of revenues. The fact that IP has become more accessible and easily transferable, has influenced the emergence of copyright infringement as one of the most common obstructions to e-commerce of IP.

Simulations for modern designs are often performed on Field Programmable Gate Array technology in a functional test and debugging process known as emulation, allowing for more complex simulations than possible in software. One drawback to emulation is the lengthy time spent in the back-end CAD tools for each debugging iteration, including debugging changes and the introduction of control and observation logic. We have developed a technique that confines the re-place-and-route area to only the portions of the design affected by the introduction of the test logic and by the debugging changes. Therefore, the back-end CAD effort for error detection, localization, and correction is reduced. This benefit is achieved by partitioning the design at the physical level into independent blocks, and the test logic and design changes are localized to the affected blocks. The result is a shortened time between debugging iterations, and thus a shortened time-to-market for the design.

In many modern designs, timing is either a key optimization goal and/or a mandatory constraint. We propose the first intellectual property protection technique using watermarking that guarantees preservation of timing constraints by judiciously selecting parts of the design specification on which watermarking constraints can be imposed. The technique is applied during the mapping of logical elements to instances of realization elements in a physical library. The generic technique is applied to two steps in the design process: combinational logic mapping in logic synthesis and template matching in behavioral synthesis. The technique is fully transparent to the synthesis process, and can be used in conjunction with arbitrary synthesis tools. Several optimization problems associated with the application of the technique have been solved. The effectiveness of the technique is demonstrated on a number of designs at both logic synthesis and behavioral synthesis.

We have developed a function-level power estimation methodology for predicting the power dissipation of embedded software. For a given microprocessor core, we empirically build the “power data bank”, which stores the power information of the built-in library functions and basic instructions. To estimate the average power of an embedded software on this core, we first get the execution information of the target software from program profiling/tracing tools. Then we evaluate the total energy consumption and execution time based on the “power data bank”, and take their ratio as the average power. High efficiency is achieved because no power simulator is used once the “power data bank” is built. We apply this method to a commercial microprocessor core and get power estimates with an average error of 3%. With this method, microprocessor vendors can provide users the “power data bank” without releasing details of the core to help users get early power estimates and eventually guide power optimization.

Recently, intellectual property protection (IPP) techniques attracted a great deal of attention from semiconductor, system integration and software companies. A number of watermarking-based techniques have been proposed for IPP. One of the key limitations of watermarking is that it does not facilitate tracing of illegally resold intellectual property (IP). Fingerprinting resolves this problem by providing each customer with a unique instance of functionally identical IP. We propose a general technique which enables fingerprinting at all level of design process and is applicable to an arbitrary optimization step. In particular, we address the following fingerprinting problem: How to generate a large number of high quality solution for a given optimization problem by solving the initial problem only once. In addition we also discuss how to select a subset of k solutions from the pool of n solutions so that the solutions are maximally different.

The semiconductor industry has adopted the intellectual property (IP) business model as a dominant system-on-chip development platform. Since copyright fraud has been recognized as the most devastating obstruction to this model, a number of techniques for IP protection have been introduced. Most of them rely on a selection of a global solution to an optimization problem according to a unique user-specific digital signature. Although such techniques may provide convincing proof of authorship with little hardware overhead, they fail to protect design partitions, do not provide an easy procedure for watermark detection, and are not capable of detecting the watermark when the design or its part is augmented in another larger design. Since these demands are of the highest interest for the IP business, we introduce localized watermarking as an IP protection technique which enables these features while satisfying the demand for low-cost and transparency. We have applied the new watermarking technology to template mapping, a behavioral synthesis task. This watermarking method has been tested on a set of real-life benchmarks where high likelihood of authorship has been achieved with negligible overhead in solution quality.

Deep submicron technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, ultra high level of integration mandates design of systems-on-chip that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. To address these issues we have developed an on-chip bus network design methodology and corresponding set of tools which, for the first, time, close the synthesis loop between system and physical design. The approach has three components: a communication profiler, a bus network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus network design component optimizes the bus network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan and to communicate information about the most constrained parts of the network.

Symbolic debuggers are system development tools that can accelerate the validation speed of behavioral specifications by allowing a user to interact with an executing code at the source level. In response to a user query, the debugger retrieves the value of a source variable in a manner consistent with respect to the source statement where execution has halted. However, when a behavioral specification has been optimized using transformations, values of variables may be inaccessible in the run-time state. We have developed a set of techniques that, given a behavioral specification CDFG, enforce computation of a selected subset V/sub cut/ of user variables such that (i) all other variables /spl upsi//spl isin/CDFG can be computed from V/sub cut/ and (ii) this enforcement has minimal impact on the optimization potential of the computation. The implementation of the new debugging approach poses several optimization tasks. We have formulated the optimization tasks and developed heuristics to solve them. The effectiveness of the approach has been demonstrated on a set of benchmark designs.

Communication designs form the fastest growing segment of the semiconductor market. Both network processors and wireless chipsets have been attracting a great deal of research attention, financial resources and design efforts. However, further progress is limited by lack of adequate system methodologies and tools. Our goal in this paper is to provide impetus for development of communication design techniques and tools. The first part addresses network processors (NP) that we study from three viewpoints: application, architecture, and system software and compilation tools. In addition to summary of main issues and representative case studies, we identify main system design issues. The second part of the tutorial focuses on wireless design. The main emphasis is on platform-based design methodology that leverages on functional profiling, architecture exploration, and orthogonalization of concerns to facilitate low-power wireless communication systems. The highlight of the paper, an in-depth study of the state-of-the-art wireless design, PicoRadio, is used as explanatory design example.

Mobile processors form a large and very fast growing segment of semiconductor market. Although they are used in a great variety of embedded systems such as personal digital organizers (PDAs), smart cards, internet appliances, laptops, smart badges, cellular phones, wearable computers, and sensor networks, they share the common need for low power, code density, security, cost sensitivity and multimedia and communication processing. The goal of this paper is to review the field of processors for mobile applications. We survey a spectrum of processors, their system software, and the accompanying hardware components. The emphasis is on classification and identification of major technology and architecture trends. Companion to this paper is a WWW page [Mob00] which provides comprehensive additional material about mobile processors.

Quality of service (QoS) is one of the key features for new Internet-based multimedia and other applications. meanwhile, energy remains as a big concern for systems that perform such applications. we address the isssue of combining system design concerns and QoS requirements to design systems that can deliver QoS quarantees. In this paper, we discuss how to satisfy QoS requirements and minimize the system's energy consumption. Specifically, we consider the following problem: Given a set of applications each specifying its required amount of computation and service time, how we allocate CPU time and determine the voltage profile on a variable voltage system, such that all the applications' requirements are satisfied and the system's total energy consumption is minimized. We optimally solve several basic cases and propse a dynamic programming procedure for the general case. Simulation shows that the new approach saves 38.75% energy over the system shut-down technique.

Energy is one of the limited resources for modern systems, especially the battery-operated devices and personal digital assistants. The backlog in new technologies for more powerful battery is changing the traditional system design philosophies. For example, due to the limitation on battery life, it is more realistic to design for the optimal benefit from limited resource rather than design to meet all the applications' requirement. We consider the following problem: a system achieves a certain amount of utility from a set of applications by providing them certain levels of quality of service(QoS). We want to allocate the limited system resources to get the maximal system utility. We formulate this utility maximization problem, which is NP-hard in general, and propose heuristic algorithms that are capable of finding solutions provably arbitrarily close to the optimal. We have also derived explicit formulae to guide the allocation of resources to actually achieve such solutions. Simulation shows that our approach can use 99.9% of the given resource to achieve 25.6% and 32.17% more system utilities over two other heuristics, while providing QoS guarantees to the application program.

Application Specific Programmable Processors (ASPP) provide efficient implementation for any of m specified functionalities. Due to their flexibility and convenient performance-cost trade-offs, ASPPs are being developed by DSP, video, multimedia, and embedded lC manufacturers. In this paper, we present two low-cost approaches to graceful degradation-based permanent fault tolerance of ASPPs. ASPP fault tolerance constraints are incorporated during scheduling, allocation, and assignment phases of behavioral synthesis: Graceful degradation is supported by implementing multiple schedules of the ASPP applications, each with a different throughput constraint. In this paper, we do not consider concurrent error detection. The first ASPP fault tolerance technique minimizes the hardware resources while guaranteeing that the ASPP remains operational in the presence of all k-unit faults. On the other hand, the second fault tolerance technique maximizes the ASPP fault tolerance subject to constraints on the hardware resources. These ASPP fault tolerance techniques impose several unique tasks, such as fault-tolerant scheduling, hardware allocation, and application-to-faulty-unit assignment. We address each of them and demonstrate the effectiveness of the overall approach, the synthesis algorithms, and software implementations on a number of industrial-strength designs.

By establishing a relationship between the basic properties of linear computations and eight optimizing transformations (distributivity, associativity, commutativity, inverse and zero element law, common subexpression replication and elimination, constant propagation), a computer-aided design platform is developed to optimally speed-up an arbitrary instance from this large class of computations with respect to those transformations. Furthermore, arbitrarily fast implementation of an arbitrary linear computation is obtained by adding loop unrolling to the transformations set. During this process, a novel Horner pipelining scheme is used so that the area-time (AT) product is maintained constant, regardless of achieved speed-up. We also present a generalization of the new approach so that an important subclass of nonlinear computations, named feedback linear computations, is efficiently, maximally, and arbitrarily sped-up.

Block-processing can decrease the time and power required to perform any given computation by simultaneously processing multiple samples of input data. The effectiveness of block-processing can be severely limited, however, if the delays in the dataflow graph of the computation are placed suboptimally. In this paper we investigate the application of retiming for improving the effectiveness of block-processing in computations. In particular, we consider the k-delay problem : Given a computation dataflow graph and a positive integer k , we wish to compute a retimed computation graph in which the original delays have been relocated so that k data samples can be processed simultaneously and fully regularly. We give an exact integer linear programming formulation for the k -delay problem. We also describe an algorithm that solves the k -delay problem fast in practice by relying on a set of necessary conditions to prune the search space. Experimental results with synthetic and random benchmarks demonstrate the performance improvements achievable by block-processing and the efficiency of our algorithm.

The expanded use of field programmable gate arrays (FPGA) in remote, long life, and system-critical applications requires the development and implementation of effective, efficient FPGA fault-tolerance techniques. FPGA have inherent redundancy and in-the-field reconfiguration capabilities, thus providing alternatives to standard integrated circuit redundancy-based fault-recovery techniques. Runtime reliability can be enhanced by using such unique features. Recovery from permanent logic and interconnect faults without runtime computer-aided design (CAD) support can be efficiently performed with the use of fine-grained and physical design partitioning. Faults are localized to small partitioned blocks that have fixed interfaces to the surrounding portions of the design, and the affected blocks are reconfigured with previously generated, functionally equivalent block instances that do not use the faulty resources. This technique minimizes the post-fault-detection system downtime, while requiring little area overhead. Only the finely located faulty portions of the FPGA are removed from use. In addition, the end user need not have access to CAD tools, making the algorithm completely transparent to system users. This approach has been efficiently implemented on a diverse set of FPGA architectures. The algorithm's flexibility is also apparent from the variable emphases that can be placed on system reliability, area overhead, timing overhead, design effort, and system memory. Given user-defined emphases, the algorithm can be modified to specific application requirements. Experiments using random s-independent and s-correlated fault models reveal that the approach enhances system reliability, while minimizing area and timing overhead.

Due to the growth of both design complexity and the number of gates per pin, functional debugging has emerged as a critical step in the development of a system-on-chip (SOC). Traditional approaches, such as system emulation and simulation, are becoming increasingly inadequate to address the system debugging needs. Design simulation is two to ten orders of magnitude slower than emulation and, thus, is used primarily for short, focused test sequences. Emulation has the required speed but imposes strict limitations on signal observability and controllability. We introduce a new debugging approach for programmable SOC's that leverages the complementary advantages of emulation and simulation. We propose a set of tools, transparent to both the design and debugging process, that enables the user to run long test sequences in emulation and, upon error detection, roll back to an arbitrary instance in execution time and switch over to simulation-based debugging for full design visibility and controllability. The efficacy of the developed approach is dependent upon the method for transferring the computation from one execution domain to another. Although the approach can be applied to any computational model, we have developed a suite of optimization techniques that enable computation transfer in a mixed synchronous data flow semi-infinite stream random-access machine computation model. This computation model is frequently used in many communications and multimedia SOCs. The effectiveness of the developed debugging methodology has been demonstrated on a set of multicore designs where combined emulation-simulation has been enabled with low hardware and performance overhead.

While previous watermarking-based approaches to intellectual property protection (IPP) have asymmetrically emphasized the IP provider's rights, the true goal of IPP is to ensure the rights of both the IP provider and the IP buyer.Symmetric fingerprinting schemes have been widely and effectively used to achieve this goal; however, their application domain has been restricted only to static artifacts, such as image and audio.In this paper, we propose the first generic symmetric fingerprinting technique which can be applied to an arbitrary optimization/synthesis problem and, therefore, to hardware and software intellectual property.The key idea is to apply iterative optimization in an incremental fashion to solve a fingerprinted instance; this leverages the optimization effort already spent in obtaining a previous solution, yet generates a uniquely fingerprinted new solution.We use this approach as the basis for developing specific fingerprinting techniques for four important problems in VLSI CAD: partitioning, graph coloring, satisfiability, and standard-cell placement.We demonstrate the effectiveness of our fingerprinting techniques on a number of standard benchmarks for these tasks.Our approach provides an effective tradeoff between runtime and resilience against collusion.

Many modern multimedia applications such as image and video processing are characterized by a unique combination of arithmetic and computational features: fixed-point arithmetic, a variety of short data types, high degree of instruction-level parallelism, strict timing constraints, and high computational requirements.Computationally intensive algorithms usually boost device's power dissipation which is often key to the efficiency of many communications and multimedia applications.Although recently virtually all general-purpose processors have been equipped with multiprecision operations, the current generation of behavioral synthesis tools for application-specific systems does not utilize this power/performance optimization paradigm.In this paper, we explore the potential of using multiple precision arithmetic units to effectively support synthesis of low-power application-specific integrated circuits.We propose a new architectural scheme for collaborate addition of sets of variable precision data.We have developed a novel resource allocation and computation assignment methodology for a set of multiple precision arithmetic units.The optimization algorithms explore the trade-off of allocating low-width bus structures and executing multiple-cycle operations.Experimental results indicate strong advantages of the proposed approach.

1 The economic viability of the reusable core-based design paradigm depends on the development of techniques for intellectual property protection. We introduce the first dynamic watermarking technique for protecting the value of intellectual property of CAD and compilation tools and reusable core components. The essence of the new approach is the addition of a set of design and timing constraints which encodes the author's signature. The constraints are selected in such a way that they result in minimal hardware overhead while embedding the signature which is unique and difficult to detect, remove and forge. We establish the first set of relevant metrics which forms the basis for the quantitative analysis, evaluation, and comparison of watermarking techniques. We develop a generic approach for signature data hiding in designs, which is applicable in conjunction with an arbitrary behavioral synthesis task, such as scheduling, assignment, allocation, and transformations. Error correcting...

Article Power efficient mediaprocessors: design space exploration Share on Authors: Johnson Kin Department of Electrical Enginerring, UCLA Department of Electrical Enginerring, UCLAView Profile , Chunho Lee Department of Computer Science, UCLA Department of Computer Science, UCLAView Profile , William H. Mangione-Smith Department of Electrical Enginerring, UCLA Department of Electrical Enginerring, UCLAView Profile , Miodrag Potkonjak Department of Computer Science, UCLA Department of Computer Science, UCLAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 321–326https://doi.org/10.1145/309847.309943Published:01 June 1999 11citation528DownloadsMetricsTotal Citations11Total Downloads528Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Due to the unavoidable need for system debugging, performance tuning, and adaptation to new standards, the engineering change (EC) methodology has emerged as one of the crucial components in synthesis of systems-on-chip.We introduce a novel design methodology which facilitates design-for-EC and post-processing to enable EC with minimal perturbation.Initially, as a synthesis pm-processing step, the original design specification is augmented with additional design constraints which ensure flexibility for future correction.Upon alteration of the initial design, a novel post-processing technique achieves the desired functionality with a near-minimal perturbation of the initially optimized design.The key contribution we introduce is a constraint manipulation technique which enables reduction of an arbitrary EC problem into its corresponding classical synthesis problem.As a result, in both pre-and post-processing for EC, classical synthesis algorithms can be used to enable flexibility and perform the correction process.We demonstrate the developed EC methodology on a set of behavioral and system synthesis tasks.

A number of researchers have proposed using digital marks to provide ownership identification for intellectual property. Many of these techniques share three specific weaknesses: complexity of copy detection, vulnerability to mark removal after revelation for ownership verification, and mark integrity issues due to partial mark removal. This paper presents a method for watermarking field programmable gate array (FPGA) intellectual property (IP) that achieves robustness by responding to these three weaknesses. The key technique involves using secure hash functions to generate and embed multiple small marks that are more detectable, verifiable, and secure than existing IP protection techniques.

Recently, a number of watermarking-based intellectual property protection techniques have been proposed. Although they have been applied to different stages in the design process and have a great variety of technical and theoretical features, all of them share two common properties: they all have been applied solely to optimization problems and do not involve any optimization during the watermarking process. In this paper, we propose the first set of optimization-intensive watermarking techniques for decision problems. In particular, we demonstrate how one can select a subset of superimposed watermarking constraints so that the uniqueness of the signature and the likelihood of satisfying an instance of the satisfiability problem are simultaneously maximized. We have developed three watermarking SAT techniques: adding clauses, deleting literals, push-out and pull-back. Each technique targets different types of signatureinduced constraint superimposition on an instance of the SAT proble...

No abstract available.

The convergence of applications (Internet and embedded applications) and technology (reuse and very high integration level) trends resulted in a strong need for design of soft real-time DSP systems-on-silicon. We developed a new hierarchical modular approach for synthesis of area efficient soft real-time DSP systems-on-silicon. This synthesis strategy employs a number of optimization intensive scheduling, performance monitoring, and allocation steps. The backbone of the optimization approach is a novel online scheduling algorithm which uses meta-algorithmic techniques for on-the-fly heuristic selection and parameter tuning. Resource allocation refers to a predetermined lower-bound system performance, to perform a branch-and-bound resource allocation search for an area-efficient multiprocessor configuration where each processor has local instruction and data cache. In order to bridge the gap between the profiling, modeling, and synthesis tools of the two traditionally independent synthesis domains (architecture and CAD), we develop a new synthesis and evaluation platform which integrates the existing modeling, profiling, and simulation tools with the new developed system-level synthesis tools. The effectiveness of the approach is demonstrated on the industrial strength MediaBench benchmark suite.

Rapid prototyping and development of in-circuit and FPGA-based emulators as key accelerators for fast time-to-market has resulted in a need for fast error correction mechanisms. The fabricated or emulated prototypes upon error diagnosis require quick and as much as possible flexible engineering change (EC). However, this problem has initiated research activity mainly in the logic synthesis domain. We introduce the first set of EC protocols for behavioral synthesis. The protocols support both the pre- and post-processing EC paradigms. In addition, instead of developing special algorithms for EC which is the adopted research model, as a key contribution, we show that using protocols which facilitate constraint manipulation of the initial design specification there is no need for development of specialized EC algorithms. The EC process is performed using the standard optimization algorithms on the modified design. Nevertheless, as shown on a number of behavioral synthesis tasks including: resource assignment, design partitioning, and operation scheduling, the approach provides variable and guaranteed flexibility for incremental synthesis with minimal hardware overhead.

This paper addresses an optimal technique for throughput optimization of general non-linear data flow computations using a set of transformations. Throughput is widely recognized as the most important design metric of the modern DSP and communication applications. Numerous approaches have been proposed for throughput optimization, but most were restricted to limited classes of computations. They have limited effectiveness when applied to large complex non-linear DSP and communication computations. The new technique is used as an optimization engine in a divide-and-conquer global approach for throughput optimization. We demonstrate the effectiveness of the new technique on numerous real-life non-linear designs.

We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to previous watermarking-based IP protection methods in finding and proving improper use of design IP. After reviewing related literature (notably in the text processing domain), we propose a generic methodology for copy detection based on determining basic elements within structural representations of solutions (IPs), calculating (context-independent) signatures for such elements, and performing fast comparisons to identify potential violators of IP rights. We give example implementations of this methodology in the domains of scheduling, graph coloring and gate-level layout; experimental results show the effectiveness of our copy detection schemes as well as the low overhead of implementation. We remark on open research areas, notably the potentially deep and complementary interaction between watermarking and copy detection.

Recently, a number of techniques for IP protection have been introduced that rely on a selection of a global solution to an optimization problem according to a unique user-specific digital signature. Although such techniques may provide convincing proof of authorship with low hardware overhead, they fail to protect parts of design, do not provide an easy procedure for watermark detection, and are not capable of detecting the watermark when the design or its part is augmented in another larger design. Since these demands are of the highest interest for the IP business, we introduce localized watermarking as an IP protection technique that enables these features while satisfying the demand for low-cost and transparency. We propose a set of protocols that implement the new watermarking methodology at the operation scheduling design level. We have demonstrated that the difficulty of erasing or finding another signature in the synthesized design can be made arbitrarily computationally difficult. The watermarking method has been tested on a set of real-life benchmarks where high likelihood of authorship has been achieved with negligible overhead in solution quality.

Design systems to provide various quality of service (QoS) guarantees have received a lot of attention due to the increasing popularity of real-time multimedia and wireless communication applications. Meanwhile, low power consumption is always one of the goals for system design, especially for battery-operated systems. With the design trend of integrating multiple processor cores and memory on a single chip, we address the problem of how to partition a set of applications among processors, such that all the individual QoS requirements are met and the total energy consumption is minimized. We exploit the advantages provided by the variable voltage design methodology to choose the voltage for each application on the same processor optimally for this purpose. We also discuss how to partition applications among the processors to achieve the same goal. We formulate the problem on an abstract QoS model and present how to allocate resources (e.g., CPU time) and determine the voltage profile for every single processor. Experiments on media benchmarks have also been studied.

Distributed hypermedia system that supports collaboration is an emerging platform for creation, discovery, management and delivery of information.We present an approach to low power system design space exploration for distributed hypermedia applications.Traditionally, low power design and synthesis of application specific programmable processors has been done in the context of a given number of operations required to complete a task.Our approach utilizes the modem advances in compiler technology and architectural enhancements that are well matched to the compiler technology.This work is, to the best of our knowledge, the first attempt to address the need for synthesis of low power hypermedia processors.Also, this is the first work to address the power efficiency through exploiting instruction level parallelism (ILP) found in hypermedia tasks by an production quality ILP compiler.Using the developed framework we conduct an extensive exploration of low power system design space for a hypermedia application under area and throughput constraints.The framework introduced in this paper is very valuable in making early low power design decisions such as architectural configuration trade-offs including the cache and issue width trade-off under area and throughput constraint, and the number of branch units and issue width.

The growing class of portable systems, such as personal computing and communication devices, has resulted in a new set of system design requirements, mainly characterized by dominant importance of power minimization and design reuse. The energy efficiency of systems-on-a-chip (SOC) could be much improved if one were to vary the supply voltage dynamically at run time. We developed the design methodology for the low-power core-based real-time SOC based on dynamically variable voltage hardware. The key challenge is to develop effective scheduling techniques that treat voltage as a variable to be determined, in addition to the conventional task scheduling and allocation. Our synthesis technique also addresses the selection of the processor core and the determination of the instruction and data cache size and configuration so as to fully exploit dynamically variable voltage hardware, which results in significantly lower power consumption for a set of target applications than existing techniques. The highlight of the proposed approach is the nonpreemptive scheduling heuristic, which results in solutions very close to optimal ones for many test cases. The effectiveness of the approach is demonstrated on a variety of modern industrial strength multimedia and communication applications.

Due to the increasing popularity of multimedia and communications applications, requirements for application-specific systems typically include design flexibility and data management ability. Since the development of such systems is a market-driven task, reducing the time to market and manufacturing cost, while still satisfying application performance requirements, is an important system synthesis requirement. We have developed a new approach for area optimization of core-based systems. The approach uses basic block relocation in order to reduce the number of cache misses and, thus, enable hardware savings during system synthesis. Given a processor model, a cache model, and a set of nonpreemptive tasks with timing constraints, the goal of the synthesis framework is to select a system configuration (processor, I-cache, and D-cache) of minimal area that satisfies the performance constraints. The system synthesis framework has two key components. The first component is a code optimization engine that relocates basic blocks within a given assembly program in order to reduce the number of cache misses. The second component is a search mechanism that leverages the improvements in code performance obtained by the first component to select the most area-efficient system configuration. In order to bridge the gap between the profiling and modeling tools, we have constructed a new performance evaluation platform. It integrates the existing modeling, profiling, and simulation tools with the developed system-level synthesis tools. The effectiveness of the synthesis approach is demonstrated on a variety of modern real-life multimedia and communication applications.

Growing design complexity has made functional debugging of application-specific integrated circuits crucial to their development. Two widely used debugging techniques are simulation and emulation. Design simulation provides good controllability and observability of the variables in a design, but is two to ten orders of magnitude slower than the fabricated design. Design emulation and fabrication provide high execution speed, but significantly restrict design observability and controllability. To facilitate debugging, and in particular error diagnosis, we introduce a novel cut-based functional debugging paradigm that leverages the advantages of both emulation and simulation. The approach enables the user to run long test sequences in emulation, and upon error detection, roll-back to an arbitrary instance in execution time, and transparently switch over to simulation-based debugging for full design visibility and controllability. The new debugging approach introduces several optimization problems. We formulate the optimization tasks, establish their complexity, and develop most-constrained least-constraining heuristics to solve them. The effectiveness of the new approach and accompanying algorithms is demonstrated on a set of benchmark designs where combined emulation and simulation is enabled with low hardware overhead.

Implementation platform selection is an important component of hardware-software codesign process which selects, for a given computation, the most suitable implementation platform. In this paper, we study the complementary component of hardware-software codesign, algorithm selection. Given a set of specifications for the targeted application, algorithm selection refers to choosing the most suitable completely specified computational structure for a given set of design goals and constraints, among several functionally equivalent alternatives. While implementation platform selection has been recently widely and vigorously studied, the algorithm selection problem has not been studied in computer-aided design domain until now. We first introduce the algorithm selection problem, and then analyze and classify its degrees of freedom. Next, we demonstrate an extraordinary impact of algorithm selection for achieving high throughput, and low-cost implementations. We define the algorithm selection problem formally and prove that throughput and area optimization using algorithm selection are computationally intractable problems. We also propose a relaxation-based heuristic for throughput optimization. Finally, we present an algorithm for cost optimization using algorithm selection. The effectiveness of methodology and proposed algorithms is illustrated using real-life examples.

We introduce an approach for power optimization using a set of compilation and architectural techniques. The key technical innovation is a novel divide-and-conquer compilation technique to minimize the number of operations for general computations. Our technique optimizes not only a significantly wider set of computations than the previously published techniques, but also outperforms (or performs at least as well as other techniques) on all examples. Along the architectural dimension, we investigate coordinated impact of compilation techniques on the number of processors which provide optimal trade-off between cost and power. We demonstrate that proper compilation techniques can significantly reduce power with bounded hardware cost. The effectiveness of all techniques and algorithms is documented on numerous real-life designs.

Traditional high-level synthesis concentrates on the implementation of a single task (e.g. filter, linear controller, A/D converter). However, many applications—multifunctional embedded controllers intelligent wireless end-points, and DSP and multimedia servers—are defined as sets of several computational tasks. This paper describes new techniques for the synthesis of ASIC implementations that realize multiple computational processes under hard real-time constraints. Our synthesis methodology establishes connections between two important comengineering domains: operating systems and behavioral synthesis. Our hierarchical approach starts from an incompletely-specified preliminary solution and uses, interchangeably, operating system and behavioral synthesis techniques to derive increasingly more detailed and accurate design solutions. We have experimented with both optimal and heuristic algorithms to implement this methodology. The optimal algorithm uses several heuristics to speed up the average run time of an exhaustive branch-and-bound search. Force-directed optimization is the core of the heuristic synthesis method. Analysis of the proposed algorithms and the experiments shows that matching the number of bits and type of operational in taskes assigned to the same application-specific processor was the most important factor in obtaining area-efficient designs.

Functional debugging of application specific integrated circuits (ASICs) has been recognized as a very labor-intensive and expensive process. We propose a new approach based on the divide and conquer optimization paradigm for the functional test pattern execution. The goal is to maximize the simultaneous controllability of an arbitrary set of the user selected variables in the design at the debugging time for facilitating the functional test pattern execution while minimizing the hardware overhead. The approach imposes minimal restriction on register sharing so that the synthesized designs will have the desired characteristic while minimizing the additional hardware overhead and minimizing the disruption of the optimization potential when scheduling, allocation and binding tasks in high-level synthesis are performed. The effectiveness of the proposed approach is demonstrated on a number of designs.

We propose a novel methodology for designing fault-tolerant real-time system to achieve optimal productivity on a single-chip multiprocessor platform using the heterogeneous built-in-self-repair (BISR) based graceful degradation and yield enhancement technique as an embedded optimization engine which exploits task-level scheduling and algorithm selection flexibility. We also developed a hardware fault model for modern superscalar processors and multi-processors which enables an efficient treatment of the synthesis and compilation goals.

We developed a new modular synthesis approach for design of low-power core-based data-intensive application-specific systems on silicon. The power optimization is conducted in three steps: minimization of instruction cache misses, placement of frequently executed sequential basic blocks of code in consecutive Gray code addressed memory locations, and processor and cache application-driven selection for low power. In order to bridge the gap between the profiling and modeling tools from the two traditionally disjoint synthesis domains (architecture and CAD), we developed a new synthesis and evaluation platform. The platform integrates the existing modeling, profiling, and simulation tools with the developed system-level synthesis tools. The effectiveness of the approach is demonstrated on a variety of modern industrial-strength multimedia and communication applications.

Abstract — Optimization at the early stages of design are crucial. However, due to an overwhelming number of design and optimization options, design exploration is often conducted in a qualitative, ad-hoc manner. This paper presents a methodology and interactive environment for guiding the exploration process. A prototype targeting behavioral-level optimization for datapath-intensive ASIC implementations has been developed. The key to the approach is encapsulated knowledge about the various optimizations and a set of techniques to automatically extract the “essence ” of a design description. At each stage in the exploration process, the system suggests and ranks potential optimizations, both in terms of immediate and longer-term impact. It also provides evaluations of the design and of the likely affects each optimization will have on metrics like power and performance. In the new approach, the designer is responsible for making the actual optimization selections. However,

The growing class of portable systems, such as personal computing and communication devices, has resulted in a new set of system design requirements, mainly characterized by dominant importance of power minimization and design reuse. We develop the design methodology for the low power core-based real-time system-on-chip based on dynamically variable voltage hardware. The key challenge is to develop effective scheduling techniques that treat voltage as a variable to be determined, in addition to the conventional task scheduling and allocation. Our synthesis technique also addresses the selection of the processor core and the determination of the instruction and data cache size and configuration so as to fully exploit dynamically variable voltage hardware, which result in significantly lower power consumption for a set of target applications than existing techniques. The highlight of the proposed approach is the non-preemptive scheduling heuristic which results in solutions very close to optimal ones for many test cases. The effectiveness of the approach is demonstrated on a variety of modern industrial-strength multimedia and communication applications.

Digital system designs are the product of valuable effort and knowhow. Their embodiments, from software and HDL program down to device-level netlist and mask data, represent carefully guarded intellectual property (IP). Hence, design methodologies based on IP reuse require new mechanisms to protect the rights of IP producers and owners. This paper establishes principles of watermarkingbased IP protection, where a watermark is a mechanism for identification that is (i) nearly invisible to human and machine inspection, (ii) difficult to remove, and (iii) permanently embedded as an integral part of the design. We survey related work in cryptography and design methodology, then develop desiderata, metrics and example approaches -- centering on constraint-based techniques -- for watermarking at various stages of the VLSI design process. 1 Introduction The advance of processing technology has led to a rapid increase in IC design complexity. The economic drivers are compelling: only by put...

Increasingly popular reuse-based design paradigms create a pressing need for authorship enforcement techniques that protect the intellectual property rights of designers. We develop the first intellectual property protection protocols for embedding design watermarks at the physical design level. We demonstrate that these protocols are tarnsparent with respect to existing industrial tools and design flows, and that they can embed watermarks into real-world industrial designs with very low implementation overhead (as measured by such standard metrics as wirelength, layout area, number of vias, routing congestion and CPU time). On several industrial test cases, we obtain extremely strong, tamper-resistant proofs of authorship for placement and routing solutions.

We have developed a new algorithm and software for graph coloring by systematically combining several algorithm and software development ideas that had crucial impact on the algorithm's performance. The algorithm explores the divide-and-conquer paradigm, global search for constrained independent sets using a computationally inexpensive objective function, assignment of most-constrained vertices to least-constraining colors, reuse and locality exploration of intermediate solutions, search time management, post-processing lottery-scheduling iterative improvement, and statistical parameter determination and validation. The algorithm was tested on a set of real-life examples. We found that hard-to-color real-life examples are common especially in domains where problem modeling results in denser graphs. Systematic experimentations demonstrated that for numerous instances the algorithm outperformed all other implementations reported in literature in solution quality and run-time.

In this paper we report a framework that makes it possible for a designer to rapidly explore the application-specific programmable processor design space under area constraints. The framework uses a production-quality compiler and simulation tools to synthesize a high performance machine for an application. Using the framework we evaluate the validity of the fundamental assumption behind the development of application-specific programmable processors. Application-specific processors are based on the idea that applications differ from each other in key architectural parameters, such as the available instruction-level parallelism, demand on various hardware components (e.g. cache memory units, register files) and the need for different number of functional units. We found that the framework introduced in this paper can be valuable in making early design decisions such as area and architectural trade-off, cache and instruction issue width trade-off under area constraint, and the number of branch units and issue width.

While system reliability is conventionally achieved through component replication, we have developed a fault-tolerance approach for FPGA-based systems that comes at a reduced cost in terms of design time, volume, and weight. We partition the physical design into a set of tiles. In response to a component failure, we capitalize on the unique reconfiguration capabilities of FPGAs and replace the affected tile with a functionally equivalent tile that does not rely on the faulty component. Unlike fixed structure fault-tolerance techniques for ASICs and microprocessors, this approach allows a single physical component to provide redundant backup for several types of components. Experimental results conducted on a subset of the MCNC benchmarks demonstrate a high level of realiability with low timing and hardware overhead.

Modern image and video processing applications are characterized by a unique combination of arithmetic and computational features: fixed point arithmetic, a variety of short data types, high degree of instruction-level parallelism, strict timing constraints, high computational requirements, and high cost sensitivity. The current generation of behavioral synthesis tools does not address well this type of application. In this paper we explore the potential of using multiple precision arithmetic units to effectively support implementation of image and video processing applications as application specific integrated circuits. A new architectural scheme for collaborate addition of sets of variable precision data is proposed as well as an allocation and assignment methodology for multiple precision arithmetic units. Experimental results indicate the strong advantages of the proposed approach.

Numerous watermarking-based techniques for intellectual property protection of DSP artifacts, such as images, compressed and uncompressed audio and video data, and text documents have been proposed. However, the applicability of all techniques proposed until now are limited to digital data and they either implicitly or explicitly exploit the imperfection of human perception to audio and video. We propose the first watermarking technique for protecting the intellectual property of DSP designs. The essence of the technique is the use of additional synthesis constraints to encode the authorship signature. The constraints are selected in such a way that they result in minimal hardware overhead while embedding the signature which is unique and difficult to detect and remove. The technique is applicable to all levels of design process, from the algorithm, system and behavioral synthesis to logic synthesis and physical design levels. The technique is illustrated on a set of DSP design examples on all levels of the design process.

We consider the problem of schtifing the mixed worMoad of both sporadic (on-fine) and periodic (off-fine) tasks on variable voltage processor to optimize power consumption while ensuring that ~ periodic tasks meet their destines and to accept as many sporadic tasks, which can be guaranteed to meet their destines, as possible.The proposed efficient dgonthms restit in the scheduling solutions, which are very close to the minimum bound achievable with the dynamictiy variable voltage approach.The effectiventis of the proposed dgonthrns is shown on extensive experiments with rd-fife design examples.

No abstract available.

Recently, design reuse has emerged as a dominant integrated system design and integration paradigm. However, the intellectual property (IP) business model is vulnerable to a number of potentially devastating obstructions, such as misappropriation and intellectual property fraud. We propose a new method for IP protection (IPP) which facilitates design watermarking at the combinational logic synthesis level. We developed protocols for embedding designer- and/or tool-specific information into a logic network while performing multi-level logic minimization and technology mapping. We demonstrate that the difficulty of erasing author's signature or finding another signature in the synthesized design can be made arbitrarily computationally difficult. We also developed a statistical method which enables us to establish the strength of the proof of authorship. The watermarking method has been tested on a standard set of real-life benchmarks where exceptionally high probability of authorship has been achieved with negligible overhead in solution quality.

MS~CTDue totheexponentird growth of both design complexity and the number of gates per pin, functional debugging has emerged as a critical step in the development of a system-on-chip.We introduce a novel debugging approach for programmable systems-on-chip.The new method leverages the advantagw of the two complementary functional execution approaches, emdation and simdation.We have developed a set of tools, transparent to both the design and debug~ng process, which enabl= the user to run long test sequences in emdation, and upon error detection, roll-back to an arbitrary instance in execution time, and switch over to simtiationbased debugging for fu~design visibility md contro~abifity.The efficacy of the approach is dependent on the method for transferring the computation from one execution domain to another.To enable effective transfer of the computation state, we have identifid a set of optimization tasks, established their computation complexity, and developed an efficient suite of optimization dgoritbms.

Abstract – This work presents the first known attempt to leverage the unique characteristics of FPGAs to protect commercial investments in intellectual property. A watermark is applied to the physical layout of a digital circuit when it is mapped into an FPGA. This watermark uniquely identifies the circuit origin and yet is difficult to detect. While this approach imposes additional constraints, experiments involving a number of large complex designs indicate that the performance impact is small. 1

We present a quantitative approach to development and v~ldation of synthetic benchmarks for behavioral synth=is systems.me approach is built on the idea of qwntitative benchrk selection.We briefly explain the idea and pr~ent experimental results on the quantitative selection and vfidation of benchmarks.We develop a synthetic design example generator which composes the behavioral level specification of a d~ign having the propertiw given by a set of numencd parameters.Experimental generation and application of synthetic design examples demonstrate the effwtiveness of the proposal approach and the develo@ algorithms.

We lay out a theoretical framework to evaluate watermarking techniques for intellectual property protection (IPP). Based on this framework, we analyze two watermarking techniques for the graph coloring (GC) problem . Since credibility and overhead are the most important criteria for any efficient watermarking technique, we derive formulae that illustrate the trade-off between credibility and overhead. Asymptotically we prove that arbitrarily high credibility can be achieved with at most 1-color-overhead for both proposed watermarking techniques. 1 Introduction Protecting software from piracy is one of the most crucial issues in computer science. The time-to-market pressure drives intellectual property (IP) into the center of several trends sweeping through today 's electronic design automation (EDA) and application specific integrated circuits (ASIC) industries. The requirement for the exchange of IP in the design of system-on-chip is well documented. As the price of hardware drops a...

me performance of many modem computer and communication systems is dictated by latency of communication pipelinm.At the same time, power consumption is often another fimiting factor in many portable systems.We addrws the problem of how to minimize the power consumption in system-level pipetines under latency constraints.h partictiar, we exploit advantages provided by variable voltage design methodology to optimtiy select SPA and therefore voltage of each pipefine stage.We define the problem and solve it optimtiy under rdstic and widely accepted assumptions.We apply the obtained theoretical r~sdts to develop rdgorithms for power minimization of computer and communication systems and show that significmt power reduction is possible without additiomd latency.

We present a framework for area optimal system design space exploration for hypermedia applications. We focus on a category of processors that are programmable yet optimized to a hypermedia application. The key components of the framework presented in this paper are a retargetable instruction-level parallelism compiler, instruction level simulators, a set of complete media applications written in a high level language and a media processor synthesis algorithm. The framework addresses the need for area optimal system design by exploiting the instruction-level parallelism found in media applications by compilers that target multiple-instruction-issue processors. Using the framework we conduct an extensive exploration of area optimal system design space for a hypermedia application. We found that there is enough ILP in the typical media and communication applications to achieve highly concurrent execution when throughput requirements are high. On the other hand, when throughput requirements are low, there is no need to use multiple-instruction-issue processors.

The energy efficiency of systems-on-a-chip can be much improved if one were to vary the supply voltage dynamically at run time. We describe the synthesis of systems-on-a-chip based on core processors, while treating voltage (and correspondingly the clock frequency) as a variable to be scheduled along with the computation tasks during the static scheduling step. In addition to describing the complete synthesis design flow for these variable voltage systems, we focus on the problem of doing the voltage scheduling while taking into account the inherent limitation on the rates at which the voltage and clock frequency can be changed by the power supply controllers and clock generators. Taking these limits on rate of change into account is crucial, since changing the voltage by even a volt may take time equivalent to 100 s to 10000 s of instructions on modern processors. We present both an exact but impractical formulation of this scheduling problem as a set of nonlinear equations, as well as a heuristic approach based on reduction to an optimally solvable restricted ordered scheduling problem. Using various task mixes drawn from a set of nine real life applications, our results show that we are able to reduce power consumption to within 7% of the lower bound obtained by imposing no limit at the rate of change of voltage and clock frequencies.

We study the effect of the controller on the testability of sequential circuits composed of controllers and data paths. We show that even when all the loops of the circuit have been broken by using scan flip-flops (FF's) and the control and data path parts are individually 100% testable, the composite circuit may not be easily testable by gate-level sequential automatic test pattern generation (ATPG). Analysis shows that a primary problem in test pattern generation of combined controller-data path circuits is the correlation of control signals due to implications imposed by the controller specification. A design-for-testability (DFT) technique is developed to redesign the controller such that the implications which may produce conflicts during test pattern generation are eliminated. The DFT technique involves adding extra control vectors to the controller. Experimental results show the ability of the controller DFT technique to produce highly testable controller-data path circuits, with nominal hardware overhead.

We introduce a transformation, named rephasing, that manipulates the timing parameters in control-data-flow graphs (CDFG's) during the high-level synthesis of data-path-intensive applications. Timing parameters in such CDFG's include the sample period, the latencies between input-output pairs, the relative times at which corresponding samples become available on different inputs, and the relative times at which the corresponding samples become available at the delay nodes. While some of the timing parameters may be constrained by performance requirements, or by the interface to the external world, others remain free to be chosen during the process of high-level synthesis. Traditionally high-level synthesis systems for data-path-intensive applications either have assumed that all the relative times, called phases, when corresponding samples are available at input and delay nodes are zero (i.e., all input and delay node samples enter at the initial cycle of the schedule) or have automatically assigned values to these phases as part of the data-path allocation/scheduling step in the case of newer schedulers that use techniques like overlapped scheduling to generate complex time shapes. Rephasing, however, manipulates the values of these phases as an algorithm transformation before the scheduling/allocation stage. The advantage of this approach is that phase values can be chosen to transform and optimize the algorithm for explicit metrics such as area, throughput, latency, and power. Moreover, the rephasing transformation can be combined with other transformations such as algebraic transformations. We have developed techniques for using rephasing to optimize a variety of design metrics, and our results show significant improvements in several design metrics. We have also investigated the relationship and interaction of rephasing with other high-level synthesis tasks.

In this paper, behavioral-level synthesis techniques are presented for the design of reconfigurable hardware. The techniques are applicable for synthesis of several classes of designs, including: (1) design for fault tolerance against permanent faults, (2) design for Improved manufacturability, and (3) design of application specific programmable processors (ASPPs)-processors designed to perform any computation from a specified set on a single implementation platform. This paper focuses on design techniques for efficient built-in self-repair (BISR), and thus directly addresses the former two applications. Previous BISR techniques have been based on replacing a failed module with a backup of the same type. We present new heterogeneous BISR methodologies which remove this constraint and enable replacement of a module with a spare of a different type. The approach is based on the flexibility of behavioral-level synthesis to explore the design space. Two behavioral synthesis techniques are developed; the first method is through assignment and scheduling, and the second utilizes transformations. Experimental results verify the effectiveness of the approaches.

Fault-tolerance is an important system metric for many operating environments, from automotive to space exploration. The conventional technique for improving system reliability is through component replication, which usually comes at significant cost: increased design time, testing, power consumption, volume, and weight. We have developed a new fault-tolerance approach that capitalizes on the unique reconfiguration capabilities of field programmable gate arrays (FPGA's). The physical design is partitioned into a set of tiles. In response to a component failure, a functionally equivalent tile that does not rely on the faulty component replaces the affected tile. Unlike application specific integrated circuit (ASIC) and microprocessor design methods, which result in fixed structures, this technique allows a single physical component to provide redundant backup for several types of components. Experimental results conducted on a subset of the MCNC benchmarks demonstrate a high level of reliability with low timing and hardware overhead.

We introduce a technique for on-line built-in self-testing (BIST) of bus-based field programmable gate arrays (FPGAs). This system detects deviations from the intended functionality of an FPGA without using special-purpose hardware, hardware external to the device, and without interrupting system operation. Such a system would be useful for mission-critical applications with resource constraints. The system solves these problems through an on-line fault scanning methodology. A device's internal resources are configured to test for faults. Testing scans across an FPGA, checking a section at a time. Simulation on a model FPGA supports the viability and effectiveness of such a system.

Successive, well organized application of transformations has beenwidely recognized as an exceptionally effective, but complex anddifficult CAD task. We introduce a new potential-driven statisticalapproach for ordering transformations. Two new synthesis ideasare the backbone of the approach. The first idea is to quantifythe characteristics of all transformations and the relationship betweenthem based on their potential to reorganize a computationsuch that the complexity of the corresponding implementation isreduced. The second one is based on the observation that transformationsmay disable each other not only because they prevent theapplication of the other transformation, but also because both transformationstarget the same potential of the computation. These twoobservations drastically reduce the search space to find efficient andeffective scripts for ordering transformations. A key algorithmicnovelty is that both conceptual and optimization insights as well asall optimization algorithms are automatically derived by organizedexperimentation and statistical methods. On a large set of diversereal-life examples improvements in throughput, area, and power bylarge factors have been obtained. Both qualitative and quantitativestatistical analysis indicate effectiveness, high robustness, and consistencyof the new approach for ordering transformations.

Synthesis of Application Specific ProgrammableProcessors poses numerous new tasks onbehavioral synthesis tools.We address some ofthem including application bundling.ApplicationBundling is a synthesis task where n control-data flowgraphs are bundled into at most m groups, so that eachapplication belongs to at least one group and throughputconstraints for all applications are satisfied.We have shown how a variety of application specificconstraints such as manufacturing cost reduction andproduction risk reduction can be targeted during thesynthesis process.The effectiveness of our approach isdemonstrated on a number of real examples.

We present a system-level approach for power optimization undera set of user specified costs and timing constraints of hard real-timedesigns. The approach optimizes all three degrees of freedom forpower minimization, namely switching activity, effective capacityand voltage supply.We first define two key associated optimization problems, processorallocation and task assignment, and establish their computationalcomplexity. Efficient algorithms are developed for bothsystem design problems. The statistical analysis of comprehensiveexperimental results and their comparison with the developed conservativeand optimistic sharp lower bounds, clearly indicates thequality of the proposed optimization techniques.

Numerous fast algorithms for the DiscreteCosine Transform (DCT) have been proposed. Until recently, it has been difficult to compare different DCT algorithms and select one which is best suitedfor implementation under a given set of design goals.We propose an approach for design space explorationat the algorithm and behavioral levels using behavioral synthesis tools and demonstrate its effectiveness for designing DCT ASIC. In particular, we study andcompare the following nine DCT algorithms: Lee's,Wang's, DIT, DFT, Arai's, DIF, Vetterli's, planar rotation, and direct algorithm. The main conclusions of this study are (i) the best choice among fast DCT algorithms depends on a particular set of design goals and constraints and (ii) almost always more than anorder of magnitude improvement can be achieved using algorithm and behavioral design space exploration.

Reduction of the number of operations optimizes the important design metrics such as area, cost, throughput, and power consumption for both custom ASIC and programmable processor implementations. We propose a novel technique to minimize the number of operations in DSP computations. The first step of the approach logically partitions a computation into strongly connected components. The second step optimizes each component separately. In the third step the components are merged to further optimize. Finally, the components are scheduled to minimize memory consumption. The effectiveness of our approach is demonstrated on real-life examples.

Although the undeniable importance of high quality, efficient and effective DSP synthesis benchmark has been firmly and widely established, until now the emphasis of benchmarking has been restricted on assembling individual examples. In this paper we introduce the "ideal candidate benchmark methodology" which poses the development of the benchmark as well as defines a statistical and optimization problem. We first outline the goals and requirements relevant for the benchmark development. After discussing the computational complexity of the benchmark selection problem, we present a simulated annealing-based algorithm for solving this computationally intractable optimization task. Using this approach from 150 examples we select 12 examples for the new DSP Quant benchmark for DSP hard Real-Time applications. The DSP benchmark is statistically validated, and its application to the analysis and development of system-level synthesis algorithms is demonstrated,.

We develop an approach to minimizing power consumption of portable wireless DSP applications using a set of compilation and architectural techniques. The key technical innovation is a novel divide-and-conquer compilation technique to minimize the number of operations for general DSP computations. Our technique optimizes not only a significantly wider set of computations than the previously published techniques, but also outperforms (or performs at least as well as other techniques) on all examples. Along the architectural dimension, we investigate coordinated impact of compilation techniques on the number of processors which provide optimal trade-off between cost and power. We demonstrate that proper compilation techniques can significantly reduce power with bounded hardware cost. The effectiveness of all techniques and algorithms is documented on numerous real-life designs.

Task preemption is a critical enabling mechanism in multi-task VLSI systems. On preemption, data in the register files must be preserved in order for the task to be resumed. This entails extra memory to save the context and additional clock cycles to restore the context. We present techniques and algorithms to incorporate micro-preemption constraints during multi-task VLSI system synthesis. Specifically, we have developed: algorithms to insert and refine preemption points in scheduled task graphs subject to preemption latency constraints; techniques to minimize the context switch overhead by considering the dedicated registers required to save the state of a task on preemption and the shared registers required to save the remaining values in the tasks; and a controller based scheme to preclude preemption related performance degradation.

We developed a new hierarchical modular approach for synthesis of area-minimal core-based data-intensive systems. The optimization approach employs a novel global least-constraining most-constrained heuristic to minimize the instruction cache misses for a given application, instruction cache size and organization. Based on this performance optimization technique, we constructed a strategy to search for a minimal area processor core, and an instruction and data cache which satisfy the performance characteristics of a set of target applications. The synthesis platform integrates the existing modeling, profiling, and simulation tools with the developed system-level synthesis tools. The effectiveness of the approach is demonstrated on a variety of modern real-life multimedia and communication applications.

We introduce a novel cut-based debugging paradigm. It coordinates design emulation and simulation and enables fast transition from one to another. Emulation or functional implementation is used for fast application execution; simulation provides complete design observability and controllability. The implementation of the new debugging approach poses several CAD tasks. We formulate the optimization tasks and develop constraint-based heuristics to solve them. Effectiveness of the approach is demonstrated on a set of designs.

The authors survey the state-of-the-art in real-time operating systems (RTOSs) from the system synthesis point of view. RTOSs have a very long research history which provides important theoretical results and useful industrial implementations. Convergence of applications, technology, and market trends of embedded systems implies a strong need for new generation of RTOS. Therefore, new system synthesis problem areas, notably hardware/software co-design and synthesis for systems-on-silicon (SOS), are opening up new avenues for RTOS research and development. The paper starts with a survey of classical academic and industrial RTOS work and continues with a survey of recent results related to co-design and design systems-on-silicon. They conclude by outlining future directions for the SOS RTOS.

Significant advances have been made in compilation technology for capitalizing on instruction-level parallelism (ILP). The vast majority of ILP compilation research has been conducted in the context of general-purpose computing, and more specifically the SPEC benchmark suite. At the same time, a number of microprocessor architectures have emerged which have VLIW and SIMD structures that are well matched to the needs of the ILP compilers. Most of these processors are targeted at embedded applications such as multimedia and communications, rather than general-purpose systems. Conventional wisdom, and a history of hand optimization of inner-loops, suggests that ILP compilation techniques are well suited to these applications. Unfortunately, there currently exists a gap between the compiler community and embedded applications developers. This paper presents MediaBench, a benchmark suite that has been designed to fill this gap. This suite has been constructed through a three-step process: intuition and market driven initial selection, experimental measurement to establish uniqueness, and integration with system synthesis algorithms to establish usefulness.

This paper presents nonscan design-for-testability (DFT) techniques applicable to register-transfer (RT)-level data path circuits. Knowledge of high-level design information, in the form of the RT-level structure, as well as the functions of the RT-level components is utilized to develop effective nonscan DFT techniques. Instead of conventional techniques of selecting flip-flops (FF's) to make systems controllable/observable, execution units (EXU's) are selected using the EXU S-graph introduced in this paper. Controllability/observability points can be implemented using register files and constants. We introduce the notion of k-level controllable and observable loops and demonstrate that it suffices to make all the loops k-level controllable/observable, k>0, to achieve very high test efficiency. The new testability measure eliminates the need by traditional DFT techniques to make all loops directly (zero-level) controllable/observable, reducing significantly the hardware overhead required and making the nonscan DFT approach feasible and effective. We discuss ways of avoiding the formation of reconvergent regions while adding test points to make loops k-level controllable/observable. We introduce dual points, which utilize the different controllability/observability levels of loops, to make one loop controllable while making another loop observable. We present efficient algorithms to add the minimal hardware possible to make all loops in the data path k-level controllable/observable, without the use of scan FF's. The nonscan DFT techniques were applied to several data path circuits. The experimental results demonstrate the effectiveness of the k-level testability measure, and the use of distributed and dual points, to generate easily testable data paths with reduced hardware overhead. The hardware overhead and the test application time required for the nonscan designs are significantly lower than for the partial scan designs. Most significantly, the experimental results demonstrate the ability of the RT-level DFT techniques to produce nonscan testable data paths, which can be tested at-speed.

Abstract|Block-processing is a powerful and popular technique for increasing computation speed by simultaneously processing several samples of data.The eectiveness of block-processing is often reduced, however, due to suboptimal placement of delays in the data ow graph of a computation.In this paper we i n v estigate an application of the retiming transformation for improving the effectiveness of block-processing in computation structures.Speci cally, w e consider the k-delay problem in which w e wish to retime any given computation so that given an integer k the resulting computation can process k data samples simultaneously in a fully regular manner.Our main contribution is an O(V 3 E+V 4 log V )-time algorithm for the k-delay problem, where V is the number of computation blocks and E is the number of interconnections in the computation.

Article Power optimization in programmable processors and ASIC implementations of linear systems: transformation-based approach Share on Authors: Mani Srivastava AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Miodrag Potkonjak Computer Science Department, University of California, Los Angeles, CA Computer Science Department, University of California, Los Angeles, CAView Profile Authors Info & Claims DAC '96: Proceedings of the 33rd annual Design Automation ConferenceJune 1996 Pages 343–348https://doi.org/10.1145/240518.240583Online:01 June 1996Publication History 18citation318DownloadsMetricsTotal Citations18Total Downloads318Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We introduce an approach for the design and optimization of ASIC implementations which realize multiple computational tasks under hard real-time constraints. The approach designs a multitask ASIC by combining techniques from hard real-time scheduling and behavioral synthesis. The key component of the methodology is the successive multiresolution synthesis technique. The technique starts from an incompletely specified preliminary solution and uses interchangeably operating systems and behavioral synthesis tools to derive increasingly more detailed and complete design solutions. The effectiveness of the optimization algorithms is demonstrated on several multiple task designs.

Transformations have been widely used in VLSI design, high level synthesis and DSP. We propose a two-step approach for transformation ordering which combines the use of optimization-intensive CAD techniques with knowledge-based user-driven search strategy. The first step is the development of basic building blocks which target small sets of transformations which are well suited for optimization intensive CAD treatment. Next, transformation orderings are developed using knowledge about mathematical laws, an application domain, and the relationship among transformations. Transformation ordering scripts combine several building blocks to form effective approaches for optimization of several design metrics in many common computational structures. As the highlight of the approach, we developed a method which efficiently simultaneously optimizes the throughput, latency, power, and area of linear computations.

While numerous power optimization techniques have been proposed at all levels of design process abstractions for electronic components, until now, power minimization in mixed mechanical-electronic subsystems, such as disks, has not been addressed. We propose a conceptually simple, but realistic power consumption model for disk drives. We present heuristics for optimization of power consumption in several common hard real-time disk-based design systems. We show how to coordinate task scheduling and disk data assignment, in order to minimize power consumption in both electronic and mechanical components of used disks. Extensive experimental results indicate significant power reduction.

Using the flexibility provided by multiple functionalities we have developed a new approach for permanent fault-tolerance: Heterogeneous Built-In-Resiliency (HBIR). HBIR processor synthesis imposes several unique tasks on the synthesis process: (i) latency determination targeting k-unit fault-tolerance, (ii) application-to-faulty-unit matching and (iii) HBIR scheduling and assignment algorithms. We address each of them and demonstrate the effectiveness of the overall approach, the synthesis algorithms, and software implementations on a number of designs.

This paper introduces a new approach to performance-driven template mapping for high-level synthesis. Template mapping, the process of mapping high-level algorithmic descriptions to specialized hardware libraries or instruction sets, involves template matching, template selection, and clock selection. Efficient algorithms for each are presented, and novel issues such as partial matching are addressed. The paper focuses on datapath-intensive ASIC design, though the concepts are also highly applicable to compiler development. Experimental results on examples from real applications show significant improvements in throughput with limited area overhead.

Many applications in DSP, telecommunications, graphics, and control have computations that either involve a large number of multiplications of one variable with several constants, or can easily be transformed to that form. A proper optimization of this part of the computation, which we call the multiple constant multiplication (MCM) problem, often results in a significant improvement in several key design metrics, such as throughput, area, and power. However, until now little attention has been paid to the MCM problem. After defining the MCM problem, we introduce an effective problem formulation for solving it where first the minimum number of shifts that are needed is computed, and then the number of additions is minimized using common subexpression elimination. The algorithm for common subexpression elimination is based on an iterative pairwise matching heuristic. The power of the MCM approach is augmented by preprocessing the computation structure with a new scaling transformation that reduces the number of shifts and additions. An efficient branch and bound algorithm for applying the scaling transformation has also been developed. The flexibility of the MCM problem formulation enables the application of the iterative pairwise matching algorithm to several other important and common high level synthesis tasks, such as the minimization of the number of operations in constant matrix-vector multiplications, linear transforms, and single and multiple polynomial evaluations. All applications are illustrated by a number of benchmarks.

We address the problem of transforming a behavioral specification so that synthesis of a testable implementation from the new specification requires significantly less area and partial scan cost than synthesis from the original specification. A two-stage objective function, that estimates the area and testability of the final implementation, and also captures enabling effects of the transformations, is developed. Optimization is done using a new randomized branch and bound steepest descent algorithm. Application of the transformation algorithm on several examples demonstrates significant simultaneous improvement in both area and testability of the final implementations.

System level design and behavior transformations have been rapidly establishing themselves as design steps with the most in uential impact onnal performance metrics, throughput and latency, o f a design.In this paper we develop a formal ILPbased approach for throughput and latency optimization when algorithm-architecture matching, retiming, and pipelining are considered simultaneously.The effectiveness of the approach is demonstrated on several real-life examples.

We introduce a transformation, named rephasing, that manipulates the timing parameters in control-dataflow graphs.Traditionally high-level synthesis systems for DSP have either assumed that all the relative times, called phases, when corresponding samples are available at input and delay nodes are zero or have automatically assigned values to as part of the scheduling step when software pipelining is simultaneously applied.Rephasing, however, manipulates the values of these phases as a transformation before the scheduling.The advantage of this approach is that phases can be chosen to optimize the algorithm for metrics such as area and power.Moreover, rephasing can be combined with other transformations.We have developed techniques for using rephasing to optimize several design metrics.The experimental results show significant improvements.

We introduce the algorithm selection problem for power minimization. After demonstrating the high impact of this synthesis task on the power consumption of the final implementation using a case study, we studied its computational complexity. We present an efficient optimization intensive algorithm for power minimization using algorithm selection. We applied the marginal utility-based algorithm for algorithm selection on three DSP examples. A table illustrates the effectiveness of the power optimization using algorithm selection on one audio (LMS DCT transform domain filter) and two video (NTSC formatter and DPCM coder) applications. On several DSP examples more than an order of magnitude reduction in power is demonstrated.

Presents a generalized Horner's scheme-based approach which enables that a large and important subclass of nonlinear computations, named feedback linear computations, is efficiently, maximally, and arbitrarily sped-up. The new class includes popular nonlinear polynomial Volterra filters and widely used LMS and RLS adaptive filters. The effectiveness and low overhead of the proposed techniques is illustrated on several designs.

This paper investigates the effect of the controller on the testability of sequential circuits composed of controllers and data paths. It is shown that even when both the controller and the data path parts are individually 100% testable, the composite circuit may not be easily testable by gate-level sequential ATPG. Analysis shows that a primary problem in test pattern generation of combined controller-data path circuits is the correlation of control signals due to implications imposed by the controller specification. A design-for-testability technique is developed to re-design the controller such that the implications which may produce conflicts during test pattern generation are eliminated. The DFT technique involves adding extra control vectors to the controller. Experimental results show the ability of the controller DFT technique to produce highly testable controller-data path circuits, with nominal hardware overhead.

We address the problem of considering debugging requirements during high level synthesis by providing low-cost hardware support and scheduling and assignment methods for ensuring controllability and observability of the user specified variables. Two key conceptually new design ideas that enable efficient debugging are developed: pipelining of debugging variables for improving their scheduling and assignment freedom and use of I/O buffers for improving resource utilization of I/O pins. The provably optimal bounds for the maximum cardinality of the set of controllable and observable variables for a given design specification are derived. A polynomial time complexity synthesis algorithm for achieving the bounds is developed. The minimization of hardware overhead gives rise to a combinatorial optimization problem which is solved using a non-greedy heuristic algorithm. The effectiveness of the proposed Design-for-Debugging approach is demonstrated on several examples.

Modern applications are often defined as sets of several computational tasks. This paper presents a synthesis algorithm for ASIC implementations which realize multiple computational tasks under hard real-time deadlines. The algorithm analyzes constraints imposed by task sharing as well as the traditional datapath synthesis criteria. In particular we demonstrated an efficient technique to combine rate-monotonic scheduling, a widely used hard real-time systems scheduling discipline, with estimations and scheduling and allocation algorithms. Matching the number of bits in tasks assigned to the same processor was the most important factor in obtaining good designs. We have demonstrated the effectiveness of our algorithms on several multiple-task examples.

System level design and computational transformations have been rapidly establishing themselves as important high impact design steps which often have the most influential impact on the most important final performance parameter, throughput, of a design. In this paper, we introduce an iterative heuristic approach for throughput optimization when algorithm-architecture matching, and any of three behavioral transformations, retiming, rephasing, and pipelining, are considered simultaneously. The effectiveness of the approach and optimization algorithms is demonstrated on several video and image processing examples.

Numerous fast algorithms for the discrete cosine transform (DCT) have been proposed in image and video processing literature. Until recently, it has been difficult to compare different DCT algorithms and select one which is best suited for implementation under a given set of design goals and constraints. In this paper, we propose an approach for design space exploration at the algorithm and behavioral levels using high level synthesis tools. In particular, we study and compare the following nine DCT algorithms: Lee's, Wang's, DIT, DFT, QR, Givens, Arai, MCM, and direct algorithm. The main conclusion of this study is that the best choice among fast DCT algorithms depends on a particular set of design goals and constraints. Another important conclusion is that for almost all sets of implementation goals and constraints more than an order of magnitude improvement can be achieved using algorithm and behavioral design space exploration.

The increasing demand for portable computing has elevated power consumption to be one of the most critical design parameters. A high-level synthesis system, HYPER-LP, is presented for minimizing power consumption in application specific datapath intensive CMOS circuits using a variety of architectural and computational transformations. The synthesis environment consists of high-level estimation of power consumption, a library of transformation primitives, and heuristic/probabilistic optimization search mechanisms for fast and efficient scanning of the design space. Examples with varying degree of computational complexity and structures are optimized and synthesized using the HYPER-LP system. The results indicate that more than an order of magnitude reduction in power can be achieved over current-day design methodologies while maintaining the system throughput; in some cases this can be accomplished while preserving or reducing the implementation area.>

We address the problem of transforming a behavioral specification so that synthesis of a testable implementation from the new specification requires significantly less area and partial scan cost than synthesis from the original specification. The proposed approach has three components: a library of relevant transformation mechanisms, an objective function, and an optimization algorithm. The most effective transformations for testability optimization are identified by analyzing the fundamental relationship between transformational mechanisms and topological and functional properties of the computations that affect testability. A dynamic, two-stage objective function that estimates the area and testability of the final implementation, and also captures enabling and disabling effects of the transformations, is developed. Optimization is done using a new randomized branch and bound steepest descent algorithm. Application of the transformation algorithm on several benchmark examples demonstrates significant simultaneous improvement in both area and testability of the final implementations.>

We introduce BETS, a behavioral test synthesis system, for the synthesis of high-throughput, area-efficient testable designs. While hardware sharing is a powerful technique to achieve area efficiency, it may adversely affect the testability of the synthesized design by introducing new loops. Besides CDFG loops, hardware sharing introduces three other types of loops: assignment loops, sequential false loops, and register files cliques. We provide a comprehensive analysis and a formal grammar characterization of the sources of loops in the data path during behavioral synthesis. Partial scan is a cost-effective technique for sequential circuit testing. Hardware sharing of scan registers can be used to minimize the number of scan registers required to synthesize data paths with minimal number of loops. The scan registers can be shared amongst several variables of the CDFG, to break not only the loops in the CDFG, but also the very loops introduced in the data path by hardware sharing. A new random walk based algorithm is proposed to break all CDFG loops using a minimal number of scan registers. The subsequent scheduling and assignment phase avoids formation of loops in the data path by reusing the scan registers, while ensuring high resource utilization. The experimental results demonstrate the effectiveness of the new technique to synthesize easily testable data paths, with nominal hardware overhead, while maintaining the performance of the designs. The partial scan overhead incurred by the technique is significantly less than that of a gate-level partial scan approach.>

Although throughput alone can be arbitrarily improved for several classes of systems using previously published techniques, none of those approaches are effective when latency constraints, which are increasingly important in embedded DSP systems, are considered. After formally establishing the relationship between latency and throughput in general computation, we explore the effect of pipelining on latency, and establish necessary and sufficient conditions under which pipelining does not alter latency. Many systems are either linear, or have subsystems that are linear. For such cases we have used a state-space based approach that treats various transformations in an integrated fashion, and answers analytically whether it is possible to simultaneously meet any given combination of constraints on latency and throughput, The analytic approach is constructive in nature, and produces a complete implementation when feasibility conditions are fulfilled. We also present a suboptimal but hardware efficient heuristic approach for the special case of initially-relaxed single-input single-output linear time-invariant computations. A novel software platform consisting of a high-level synthesis system coupled to a symbolic algebra system was used to implement the proposed algorithm transformations. Instead of optimizing to improve throughput and latency, our transformations can also be used to increase the implementation efficiency while achieving the same latency and throughput as the original design.>

Throughput has been widely traditionally recognized as the most popular performance metric for implementation of application specific computations. However, increasingly applications such as embedded controllers impose constraints on both throughput and latency as important metrics of speed. Although throughput alone can be arbitrarily improved for several classes of systems using previously published techniques, none of those approaches are effective when latency constraints are considered. DSP, communications, and control systems are often either linear, or have subsystems that are linear. Recently an optimal technique for simultaneous optimization of throughput and latency of linear computations was introduced by M.B. Srivastava and M. Potkonjak (1994). However, in many cases this technique introduces significant area overhead. We apply certain key aspects of that technique (on-arrival-processing and maximally fast implementation of linear computations) with exploration of state-space based transformations to develop four synthesis techniques which generate high throughput, low latency, low area, and low power application specific processors for the special case of single input linear computations. The new transformation techniques can also be used to increase the implementation efficiency while achieving the same latency and throughput as the original design-we obtained large improvements in area and power on many benchmarks when using the proposed transformations in this alternate role.>

This paper introduces hot potato high level synthesis transformation techniques. These techniques add deflection operations in a computation in such a way that a specific goal is optimized. We demonstrate how the requirements for two important components of the final implementation cost, registers and interconnects, are significantly reduced using new technique. It is also demonstrated how hot potato techniques can be effectively used during high level synthesis to minimize the partial scan overhead to make the synthesized design testable.

Many numerically intensive applications have computations that involve a large number of multiplications of one variable with several constants.A proper optimization of this part of the computation, which we call the multiple constant multiplication (MCM) problem, often results in a significant improvement in several key design metrics.After defining the MCM problem, we formulate it as a special case of common subexpression elimination.The algorithm for common subexpression elimination is based on an iterative pairwise matching heuristic.The flexibility of the MCM problem formulation enables the application of the iterative pairwise matching algorithm to several other important high level synthesis tasks.All applications are illustrated by a number of benchmarks.

Partial scan is a popular design for testability technique for cost-effective sequential automatic test pattern generation (ATPG). An efficient partial scan approach selects flip-flops (FFs) in the minimum feedback vertex set (MFVS) of the FF dependency graph, so that loops are broken. Through an analysis of the sources of loops in the data path, this paper proposes a new high-level synthesis methodology to synthesize DSP designs which have low-cardinality MFVS, thereby reducing the cost of partial scan significantly. A test efficiency of 100% could be achieved for all designs synthesized by the proposed approach, requiring a significantly less number of FFs to be scanned compared to the original implementations.>

The exploration of concurrency has emerged as a dominant research problem in the VLSI DSP literature. A great variety of forms of concurrency exploration have been proposed, analyzed and used on a number of hardware platforms. The belief that the DSP domain is amenable to concurrency exploration has been gaining popularity; however, no systematic study has been conducted to confirm or dispel this claim. This paper presents a global view of the concurrency problem, presenting comprehensive statistics on concurrency properties in commonly used DSP programs. Particular emphasis is placed on the potential cost effectiveness of concurrency exploitation.>

This paper introduces heuristic transformation techniques to simultaneously optimize throughput and latency of linear time-invariant systems. The technique is based on a properly coordinated manipulation of an arbitrary initial specification by both high level synthesis and symbolic algebraic manipulation tools. The technique produces implementations that not only have high throughput and low latency, but also have lower area and power requirements compared to the initial specifications. The effectiveness of the technique is demonstrated on a number of high level synthesis DSP benchmarks.>

Recently, several high level synthesis approaches have been proposed to synthesize testable data paths from behavioral specifications. This paper introduces a novel technique to transform behavioral specifications, such that an existing behavioral test synthesis system can generate area-efficient, testable designs with significantly lower partial scan overhead. Experimental results demonstrate the significant savings in partial scan overhead when the transformation is applied before using the behavioral test synthesis system to synthesize 100% test-efficient designs.

An efficient partial scan approach for cost-effective sequential ATPG is to select flip-flops (FFs) in the minimum feedback vertex set (MFVS) of the FF dependency graph, so that loops are broken. Through a comprehensive analysis of the sources of loops in the data path, this paper proposes a new high-level synthesis methodology to synthesize data paths which have low-cardinality MFVS, thereby reducing the cost of partial scan significantly. A test efficiency of 100% could be achieved for all designs synthesized by the proposed approach, requiring a significantly less number of FFs to be scanned compared to the original implementations.>

The goal of the high level synthesis process for real time applications is to minimize the implementation cost, while still satisfying all timing constraints. In this paper, the authors present a combination of four conceptually simple, yet powerful, transformations: namely retiming, associativity, commutativity and inverse element law, which can help to further this goal. Since the minimization problem associated with these transformations is NP complete, a new fast iterative improvement probabilistic algorithm has been developed. The effectiveness of the proposed algorithm and the associated transformations is demonstrated in multiple ways: using standard benchmark examples, with the aid of statistical analysis and through a comparison with estimated minimal bounds.>

This paper discusses techniques for estimating implementation bounds on computational resources and their role in the high-level synthesis process. Accurate estimations can be extremely useful in a multitude of synthesis operations, such as algorithm and architecture selection, design space search, module selection, transformations, allocation, assignment, and scheduling. Several techniques to efficiently estimate sharp minimum and maximum bounds on the resource requirements of a hardware implementation are discussed. The performance of the algorithms as well as their applications is analyzed using an extensive benchmark set. The proposed techniques have been implemented in the HYPER synthesis system.>

Built-In-Self-Repair (BISR) is a fault tolerance technique against permanent faults, where in addition to core operational modules, a set of spare modules is provided. If a faulty core module is detected, it is replaced with a spare module. The BISR methodology has been used only in situations where a failed module of one type can only be replaced by a backup module of the same type. The authors propose a new BISR approach for ASIC design which removes this constraint and enables replacement of modules of different types with the same spare units by exploiting the design space exploration abilities provided by the use of transformations in high level synthesis. Fast and efficient high level synthesis algorithms which take into account peculiarities of transformation-based design for BISR are presented. The potential of the approach is demonstrated on a set of benchmark examples by showing significant yield and relative productivity improvements which are calculated using state-of-the-art yield modeling techniques.>

ABSTRACT: We propose a novel sequential delay op-timization technique based on network flow methods that simultaneously exploits delays on all paths in the circuit. We view the sequential circuit as an intercon-nection of path segments with pre-specified delays. Path segments are bounded by flip-flops, primary inputs or primary outputs. Recognizing that a delay optimizer can satisfy certain delay constraints more easily than others, we first propose a measure of difficulty for the delay optimizer. Our measure is based on explicit path delays to be satisfied by the delay optimizer. Also, our measure induces a partial order on the set of possible delay constraints. We then compute a set of delay con-straints that is optimal with respect to our measure. The delay constraint set is optimal in the sense that it is the easiest constraint that can be specified to the delay optimizer. We formulate the delay constraint cal-culation problem as a minimum cost network flow prob-lem. If the delay optimizer satisfies the optimal delay constraint set, then the resynthesized circuit may have several pat hs exceeding the desired clock period. How-ever, we show that the resynthesized circuit can always be retimed to achieve the desired clock period. Exper-imental results on MCNC synthesis benchmarks show that our method improves the performance of circuits beyond what is achievable using optimal retiming and conventional combinational logic synthesis. 1.

The power of retiming is often limited by the underlying topology of a computational structure.We combine the power of retiming with a complete set of algebraic transformations in an iterative improvement framework, where retiming and algebraic speed-up algorithms are successively applied, so that the latter enables the former.The key part of the approach is a new algebraic speed-up algorithm being used for the first time in high-level synthesis for transformations of algebraic expressions so that an arbitrary set of input arrival times and output required times are satisfied.Since the new method moves delays forward only and retiming is done locally and very infrequently, it also always calculates the new initial state efficiently.The proposed approach has yielded results better or equal to the best previously published on all benchmark examples and on several novel real-life examples.

Performance optimization is the primary design goal in most digital signal processing (DSP) and numerically intensive applications. The problem of mapping high-level algorithmic descriptions for these applications to specialized instruction sets has only recently begun to receive attention. In fact, the problem of optimizing performance has yet to be addressed directly. This paper introduces a new approach to instruction set mapping (and template matching in general) targeted toward performance optimization. Several novel issues are addressed including partial matching and automatic clock selection.

A new approach to high level synthesis, which simultaneously addresses testability and resource utilization, is presented. We explore the relationship between hardware sharing, loops in the synthesized data-path, and partial scan overhead. Since loops make a circuit hard to test, a comprehensive analysis of the sources of loops in the data path, created during high level synthesis, is provided. The paper introduces the problem of breaking CDFG loops with a minimal number of scan registers. Subsequent scheduling and assignment avoid formation of loops in the data path by sharing the scan registers, while ensuring high resource utilization. Experimental results demonstrate the effectiveness of the technique to synthesize easily testable data paths, with significantly less partial scan cost than a gate-level partial scan approach.

High level synthesis techniques for the synthesis of restructurable datapaths are introduced. The techniques can be used in applications such as design for fault tolerance against permanent faults, design for yield improvement, and design of application specific programmable processors. The paper focuses on design techniques for built in self repair (BISR), which addresses the first two of these applications. The new BISR methodology consists of two approaches which exploit the design space exploration abilities of high level synthesis. The first method uses resource allocation, assignment, and scheduling, and the second uses transformations. The effectiveness of the approaches are verified on a set of benchmark examples.

Retiming, algebraic and redundancy manipulation transformations are widely used in both the high level synthesis and the compilers fields. We present a new approach on how these powerful transformations can be applied to improve the performance of embedded systems, by optimizing their latency and throughput. A simple modification is sufficient to adapt both the Leiserson-Saxe retiming algorithm and the recently introduced ERB algorithm for the new task. We introduce a new negative retiming technique and the algorithm which coordinates this technique with both algebraic and redundancy manipulation techniques for latency optimization. The effectiveness of all discussed techniques is demonstrated on a set of "real-life" examples. Latency and throughput are improved by factors of 7.06 and 2.83 respectively, often with minimal or no additional hardware overhead.>

A system has been developed which targets the rapid prototyping of high performance data computation units which are typical to real-time digital signal processing applications. The hardware platform of the system is a family of multiprocessor integrated circuits. The prototype chip of this family contains 8 processors connected via a dynamically controlled crossbar switch. With a maximum clock rate of 25 MHz, it can support a computation rate of 200 MIPs and can sustain a data I/O bandwidth of 400 MByte/sec. An assembler and simulator provide low-level programmability of the hardware. A compiler which takes input described in the high-level data flow language Silage, and performs estimation, transformations, partitioning, assignment, and scheduling before generating assembly code, provides an automated software compilation path.>

A simple formulation of pipelining: 'Pipelining with N stages is equivalent to retiming where the number of delays on all inputs or all outputs, but not both, is increased by N' is used as the basis for a convenient and efficient treatment of pipelining in design of application specific computers. Classification of pipelining according to the optimization goal (throughput and resource utilization) and the latency is introduced. For polynomial complexity pipelining classes, optimal algorithms are presented. For other classes both proof of NP-completeness and efficient probabilistic algorithms are presented. Both theoretical and experimental properties of pipelining are discussed. In particular, a relationship with other transformations is explored. Due to close relationship between software pipelining and pipelining presented, all results can be easily modified for use in compilers for general purpose computers. Also, as a side result, the exact bound (solution) for iteration bound is derived.>

An automatic transformational approach used to reduce the iteration bound of recursive DSP algorithms is presented. The proposed approach combines delay retiming, algebraic transformations and loop unrolling in a well defined order. The effectiveness of the approach is demonstrated using examples.>

An automated high-level synthesis system, HYPER-LP, for minimizing power consumption in application-specific datapath-intensive CMOS circuits using a variety of architectural and computational transformations is presented. The sources of power consumption are reviewed, and the effects of architectural transformations on the various power components are presented. The synthesis environment consists of high-level estimation of power consumption, a library of transformation primitives (local and global), and heuristic/probabilistic optimization search mechanisms for fast and efficient scanning of the design space. Examples with varying degree of computational complexity and structures are optimized and synthesized. The results indicate that an order of magnitude reduction in power can be achieved over current-day design methodologies while maintaining the system throughput; in some cases, this can be accomplished while preserving or reducing the implementation area.>

A method to improve the effectiveness of retiming by transforming the sequential circuit is proposed. Bottlenecks which prevent retiming to achieve a desired clock period are identified. Conditions to eliminate the retiming bottlenecks are derived. These conditions are satisfied by a process of identifying subcircuits and satisfying a set of timing constraints on the subcircuits. The transformed circuit, which satisfies the timing constraints, can be retimed to achieve the desired clock period. If the original circuit has its initial state specified, the method always generates the final circuit with an equivalent initial state. Experimental results on a variety of sequential benchmark circuits demonstrate significant performance improvement.>

It is pointed out that by establishing a relationship between the basic properties of linear computations and several optimizing transformations, it is possible to optimally speed up linear computations with respect to those transformations while keeping the latency fixed. Furthermore, arbitrarily fast, asymptotically optimal implementations can be obtained by adding retiming and loop unrolling to the transformations set and trading latency for throughput. The proposed techniques have yielded results superior to the best published previously on all benchmark examples. The presented approach is also applicable to general (nonlinear) computations.>

A transformational approach aimed at improving the resource utilization in high level synthesis is introduced. The current implementation combines retiming and associativity in a single framework. This combination of transformations results in considerable area improvements, as is amply demonstrated by benchmark examples. A novel learning while searching iterative improvement probabilistic algorithm has been developed and is used to resolve the associated NP-complete combinatorial optimization problem. The effectiveness of the proposed algorithms and the transformations is demonstrated using standard benchmark examples, with the aid of statistical analysis, and through a comparison with estimated minimal bounds. The proposed algorithm has proven to be very effective in reaching the optimal solution as well as in runtime.>

The paper describes a new algorithm for the scheduling and resource allocation problem in high-level synthesis. The algorithm can not only efficiently treat flattened signal flow graphs, but also handles graphs with embedded control constructs such as conditional branches and loops. Based on simple and clear, but powerful principles, the algorithm simultaneously minimizes the number of execution units, the number of registers and the amount of interconnections. The algorithm has been implemented and we present the first results, which are very promising.

A synthesis system called HYPER is proposed for real-time applications. HYPER takes a flow graph description of an algorithm as the input and performs scheduling, resource allocation, optimizations, and transformations. A dedicated bit-sliced data path cluster is generated by the system and the layouts can be further generated through the LAGER IV system.>