Electrical & Computer Engineering Research Works

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

Browse

Author: search.filters.author.Potkonjak, MiodragStart date: 2000

Search Results

Now showing 1 - 10 of 10
  • 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
    An On-line Approach for Power Minimization in QoS Sensitive Systems
    (IEEE, 2003-01) Wong, Jennifer L.; Qu, Gang; Potkonjak, Miodrag
    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.
  • Thumbnail Image
    Item
    Fingerprinting Intellectual Property Using Constraint-Addition
    (IEEE, 2000-06) Qu, Gang; Potkonjak, Miodrag
    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. In order to make our discussion concrete we focus on a single NP-complete problem - graph coloring. We test the new fingerprinting on a number of standard benchmarks. Interestingly, while on random graphs it is relatively difficult to produce a large number of solutions without nontrivial quality degradation, on all real-life compilation graphs we are able to generate millions of solution which are all optimal.
  • Thumbnail Image
    Item
    Fair Watermarking Techniques
    (IEEE, 2000-01) Qu, Gang; Wong, Jennifer L.; Potkonjak, Miodrag
    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.
  • Thumbnail Image
    Item
    Achieving Utility Arbitrarily Close to the Optimal with Limited Energy
    (IEEE, 2000-07) Qu, Gang; Potkonjak, Miodrag
    Energy is one of the limited resources for modern systems, especially the battery-operated devices and personal digi- tal 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 applica- tions' 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 re- sources to get the maximal system utility. We formulate this utility maximization problem, which is NP-hard in gen- eral, 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 alloca- tion of resources to actually achieve such solutions. Simu- lation 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.
  • Thumbnail Image
    Item
    Function-Level Power Estimation Methodology for Microprocessors
    (IEEE, 2000-06) Qu, Gang; Kawabe, Naoyuki; Usami, Kimiyoshi; Potkonjak, Miodrag
    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.
  • Thumbnail Image
    Item
    Power Minimization in QoS Sensitive Systems
    (IEEE, 2004-06) Wong, Jennifer L; Qu, Gang; Potkonjak, Miodrag
    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 provablyoptimal techniques that minimize energy consumption of streamoriented 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.
  • Thumbnail Image
    Item
    Effective Iterative Techniques for Fingerprinting Design IP
    (IEEE, 2004-01) Caldwell, Andrew E.; Choi, Hyun-Jin; Kahng, Andrew B.; Mantik, Stefanus; Potkonjak, Miodrag; Qu, Gang; Wong, Jennifer L.
    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.
  • Thumbnail Image
    Item
    Optimization-Intensive Watermarking Techniques for Decision Problems
    (IEEE, 2004-01) Wong, Jennifer L.; Qu, Gang; Potkonjak, Miodrag
    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 the 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.
  • Thumbnail Image
    Item
    Techniques for Energy-Efficient Communication Pipeline Design
    (IEEE, 2002-10) Qu, Gang; Potkonjak, Miodrag
    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 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. We apply the obtained theoretical results to develop algorithms for power/energy minimization of computer and communication systems. The experimental result suggests that significant power/energy reduction, is possible without additional latency. In fact, we achieve almost 40% total energy saving over the combined minimal supply voltage selection and system shut-down technique and 85% if none of these two energy minimization methods is used.