Electrical & Computer Engineering Research Works

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

Browse

Author: search.filters.author.Potkonjak, Miodrag

Search Results

Now showing 1 - 10 of 20
  • 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
    System Synthesis of Synchronous Multimedia Applications
    (IEEE, 1999-11) Qu, Gang; Mesarina, Malena; Potkonjak, Miodrag
    Modern system design is being increasingly driven by applications such as multimedia and wireless sensing and communications, which all 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 constraints among the interacting media (synchronization) and within each media (latency). We have developed the first framework for systems design with timing QoS guarantees, latency and synchronization. In particular, we address how to design system-on-chip with minimal silicon area to meet timing constraints. We propose the two-phase design methodology. In the first phase, we select an architecture which facilitates the needs of synchronous low latency applications well. In the second phase, for a given processor configuration, we use our new scheduler in such a way that storage requirements are minimized. We have develop scheduling algorithms that solve the problem optimally for a-priori specified applications. The algorithms have been implemented and their effectiveness demonstrated on a set of simulated MPEG streams from popular movies.
  • 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
    Power Minimization using System-Level Partitioning of Applications with Quality of Service Requirements
    (1999-11) Qu, Gang; Potkonjak, Miodrag
    Design systems to provide various quality of service (QoS) guarantees has received a lot of attentions 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.
  • Thumbnail Image
    Item
    Energy Minimization of System Pipelines Using Multiple Voltages
    (IEEE, 1999-05) Qu, Gang; Kirovski, Darko; Potkonjak, Miodrag; Srivastava, Mani B.
    Modem computer and communication system design has to consider the timing constraints imposed by communication and system pipelines, and minimize the energy consumption. We adopt the recent proposed model for communication pipeline latency[23] and address the problem of how to minimize the power consumption in system-level pipelines under the latency constraints by selecting supply voltage for each pipeline stage using the variable voltage core-based system design methodology[l 11. We define the problem, solve it optimally under realistic assumptions and develop algorithms for power minimization of system pipeline designs based on our theoretical results. We apply this new approach on the 4- stage Myrinet GAM pipeline, with the appropriate voltage profiles, we achieve 93.4%, 91.3% and 26.9% power reduction on three pipeline stages over the traditional design.
  • Thumbnail Image
    Item
    Optimization-Intensive Watermarking Techniques for Decision Problems
    (IEEE, 1999-06) Wong, Jennifer L.; Qu, Gang; Potkonjak, Miodrag
    Abstract—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
    Quality of Service and System Design
    (IEEE, 1999-04) Kornegay, Kevin T.; Qu, Gang; Potkonjak, Miodrag
    Quality of Service (QoS) of the implementation of an application can be defined as a function of the properties of the application and its implementation as observed by the user and/or the environment. Typical application and implementation properties include latency, throughput, jitter, and the level of resolution. Many of the current and pending most popular applications, such as multimedia, wireless sensing and communications, security and PEBBs, have intrinsic relevant QoS components. Recently, quality of service attracted a great of deal of attention in a number of research and development communities, and in particular, in the network and multimedia literature. However, until now synthesis and CAD research did not addressed how to design systems with quantitative QoS requirements. Our goal in this paper is to outline foundations and framework in which QoS system design trade-offs and optimization can be addressed. We first identify and state in synthesis-usable way two currently most popular approaches to Quality of Service treatment: Q-RAM and DScurve (demand/service). We discuss advantages and limitations of the two approaches. Next, we show how these two approaches can be combined in a new more comprehensive QoS framework. We also explain and illustrate using examples interaction between QoS and synthesis and compilation tasks. We conclude by identifying and discussing the future directions related to synthesis of QoS-sensitive systems.