Electrical & Computer Engineering Research Works

Permanent URI for this collectionhttp://hdl.handle.net/1903/1658

Browse

Author: search.filters.author.Qu, Gang

Search Results

Now showing 1 - 10 of 48
  • Thumbnail Image
    Item
    Obtaining Statistically Random Information from Silicon Physical Unclonable Functions
    (2013) Yin, Chi-En; Qu, Gang
    Silicon physical unclonable functions (PUF) uti- lize the variation during silicon fabrication process to extract information that will be unique for each chip. There have been many recent approaches to how PUF can be used to improve security related applications. However, it is well-known that the fabrication variation has very strong spatial correlation1 and this has been pointed out as a security threat to silicon PUF. In fact, when we apply NIST’s statistical test suite for randomness [1] against the random sequences generated from a population of 125 ring oscillator (RO) PUFs [2] using classic 1-out-of-8 Coding [3], [4] and Neighbor Coding [5], none of them can pass all the tests. In this paper, we propose to decouple the unwanted systematic variation from the desired random variation through a regression-based distiller, where the basic idea is to build a model for the systematic variation so we can generate the random sequences only from the true random variation. Applying Neighbor Coding to the same benchmark data [2], our experiment shows that 2nd and 3rd order polynomials distill random sequences that pass all the NIST randomness tests. So does 4th order polynomial in the case of 1-out-of-8 Coding. Finally, we introduce two generic random sequence generation methods. The sequences they generate fail all the randomness tests, but with the help of our proposed polynomial distiller, all but one tests are passed. These results demonstrate that our method can provide statistically random PUF information and thus bolster the security characteristics of existing PUF schemes.
  • Thumbnail Image
    Item
    Power Minimization under QoS Constraints
    (IEEE, 2002-04) Wong, Jennifer L.; Qu, Gang; Potkonjak, Miodrag
    QoS has been often addressed in multimedia, video, and networking research communities, but rarely in the design community. Our goal is to introduce the first system design technique for comprehensive quality-of-service (QoS) low power synthesis. Specifically, we study how to efficiently exploit the trade-o between the system cost and energy consumption in real-time systems that address packet-based multimedia transmission and processing. We first introduce a system of techniques that minimizes energy consumption of stream-oriented applications under two main QoS metrics: latency and synchronization. Speci cally, 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 this case satisfying latency and synchronization requirements. We have developed a provably optimal polynomial time o -line algorithm for multiple volt- age scheduling of single and multiple processes. The o -line algorithm provides lower bounds on achievable power minimization and can be used as a starting point for the development and evaluation of an on-line approach. The effectiveness of the algorithm is demonstrated on a number of multimedia benchmarks.
  • Thumbnail Image
    Item
    Dual-Processor Design of Energy Efficient Fault-Tolerant System
    (IEEE, 2006-09) Hua, Shaoxiong; Pari, Pushkin R.; Qu, Gang
    A popular approach to guarantee fault tolerance in safety-critical applications is to run the application on two processors. A checkpoint is inserted at the comple- tion of the primary copy. If there is no fault, the sec- ondary processor terminates its execution. Otherwise, should the fault occur, the second processor continues and completes the application before its deadline. In this paper, we study the energy efficiency of such dual- processor system. Specifically, we first derive an opti- mal static voltage scaling policy for single periodic task. We then extend it to multiple periodic tasks based on worst case execution time (WCET) analysis. Finally, we discuss how to further reduce system’s energy con- sumption at run time by taking advantage of the actual execution time which is less than the WCET. Simula- tion on real-life benchmark applications shows that our technique can save up to 80% energy while still provid- ing fault tolerance.
  • Thumbnail Image
    Item
    VLSI CAD Tool Protection by Birthmarking Design Solutions
    (IEEE, 2005-04) Yuan, Lin; Qu, Gang; Srivastava, Ankur
    Many techniques have been proposed in the past for the protection of VLSI design IPs (intellectual property). CAD tools and algorithms are intensively used in all phases of modern VLSI designs; however, little has been done to protect them. Basically, given a problem P and a solution S, we want to be able to determine whether S is obtained by a particular tool or algorithm. We propose two techniques that intentionally leave some trace or birthmark, which refers to certain easy detectable properties, in the design solutions to facilitate CAD tool tracing and protection. The pre-processing technique provides the ideal protection at the cost of losing control of solution’s quality. The post-processing technique balances the level of protection and design quality. We conduct a case study on how to protect a timing-driven gate duplication algorithm. Experimental results on a large set of MCNC benchmarks confirm that the pre-processing technique results in a significant reduction (about 48%) of the optimization power of the tool, while the post-processing technique has almost no penalty (less than 2%) on the tool’s performance.
  • Thumbnail Image
    Item
  • Thumbnail Image
    Item
    How Many Solutions Does a SAT Instance Have?
    (IEEE, 2004-05) Pari, Pushkin R.; Yuan, Lin; Qu, Gang
    Our goal is to investigate the solution space of a given Boolean Satisfiability (SAT) instance. In particular, we are interested in determining the size of the solution space – the number of truth assignments that make the SAT instance true – and finding all such truth assignments, if possible. This apparently hard problem has both theoretical and practical values. We propose an exact algorithm based on exhaustive search that Solves the instance Once and Finds All Solutions (SOFAS) and several sampling techniques that estimate the size of the solution space. SOFAS works better for SAT instances of small size with a 5X-100X speed-up over the brute force search algorithm. The sampling techniques estimate the solution space reasonably well for standard SAT benchmarks.
  • Thumbnail Image
    Item
    ARBITRATE-AND-MOVE PRIMITIVES FOR HIGH THROUGHPUT ON-CHIP INTERCONNECTION NETWORKS
    (IEEE, 2004-05) Balkan, Aydin O.; Vishkin, U.; Qu, Gang
    An n-leaf pipelined balanced binary tree is used for arbitration of order and movement of data from n input ports to one output port. A novel arbitrate-and-move primitive circuit for every node of the tree, which is based on a concept of reduced synchrony that benefits from attractive features of both asynchronous and synchronous designs, is presented. The design objective of the pipelined binary tree is to provide a key building block in a high-throughput mesh-of-trees interconnection network for Explicit Multi Threading (XMT) architecture, a recently introduced parallel computation framework. The proposed reduced synchrony circuit was compared with asynchronous and synchronous designs of arbitrate-and-move primitives. Simulations with 0.18m technology show that compared to an asynchronous design, the proposed reduced synchrony implementation achieves a higher throughput, up to 2 Giga- Requests per second on an 8-leaf binary tree. Our circuit also consumes less power than the synchronous design, and requires less silicon area than both the synchronous and asynchronous designs.
  • Thumbnail Image
    Item
    VLSI Design IP Protection: Solutions, New Challenges, and Opportunities
    (IEEE, 2006-06) Yuan, Lin; Qu, Gang
    It has been a decade since the need of VLSI design intellectual property (IP) protection was identified [1,2]. The goals of IP protection are 1) to enable IP providers to protect their IPs against unauthorized use, 2) to protect all types of design data used to produce and deliver IPs, 3) to detect the use of IPs, and 4) to trace the use of IPs [3]. There are significant advances from both industry and academic towards these goals. However, do we have solutions to achieve all these goals? What are the current state-of-the-art IP protection techniques? Do they meet the protection requirement designers sought for? What are the (new) challenges and is there any feasible answer to them in the foreseeable future? This paper addresses these questions and provides possible solutions mainly from academia point of view. Several successful industry practice and ongoing efforts are also discussed briefly.
  • Thumbnail Image
    Item
    CASPER: An Integrated Energy-Driven Approach for Task Graph Scheduling on Distributed Embedded Systems
    (IEEE, 2005-07) Kianzad, Vida; Bhattacharyya, Shuvra S.; Qu, Gang
    For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (Combined Assignment, Scheduling, and PowER-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) [3]: applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3% energy saving, a 7.8% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm [13], CASPER improves its energy efficiency by 8.2%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3% more energy over GMA+EE-GLSA [12], the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop.
  • Thumbnail Image
    Item
    TRANSFERRING PERFORMANCE GAIN FROM SOFTWARE PREFETCHING TO ENERGY REDUCTION
    (IEEE, 2004-05) Agarwal, Deepak N.; Pamnani, Sumitkumar N.; Qu, Gang; Yeung, Donald
    Performance-enhancement techniques improve CPU speed, but at higher cost to other valuable system resources such as power and energy. We study this trade-off using software prefetching as the system performance-enhancement technique. We first demonstrate software prefetching provides an average 36% performance boost with 8% more energy consumption and 69% higher power on six memory-intensive benchmarks. However, when we combine prefetching with a (unrealistic) static voltage scaling technique, the performance gain afforded by prefetching can be traded off for savings in power/energy consumption. In particular, we observe a 48% energy saving when we slow down the system with prefetching so as to match the performance of the system without prefetching. This suggests a promising approach to build low power systems by transforming traditional performance-enhancement techniques into low power methods. We thus propose a real time dynamic voltage scaling (DVS) algorithm that monitors a system’s performance and adapts the voltage level accordingly while maintaining the observed system performance. Our dynamic DVS algorithm achieves a 38% energy saving without any performance loss on our benchmark suite.