Electrical & Computer Engineering Research Works

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

Browse

Start date: 1995End date: 1999

Search Results

Now showing 1 - 10 of 32
  • 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
    The Associative-Skew Clock Routing Problem
    (IEEE, 1999-11) Chen, Yu; Kahng, Andrew B.; Qu, Gang; Zelikovsky, Alexander
    We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is easier to address within current EDA frameworks than useful-skew (skew-scheduling) approaches, and defines an interesting tradeoff between the traditional zero-skew clock routing problem (one sink group) and the Steiner minimum tree problem (n sink groups). We present a set of heuristic building blocks, including an efficient and optimal method of merging two zero-skew trees such that zero skew is preserved within the sink sets of each tree. Finally, we list a number of open issues for research and practical application.
  • 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.
  • Thumbnail Image
    Item
    Effective Iterative Techniques for Fingerprinting Design IP
    (IEEE, 1999-06) Caldwell, Andrew E.; Choi, Hyun-Jin; Kahng, Andrew B.; Mantik, Stefanus; Potkonjak, Miodrag; Qu, Gang; Wong, Jennifer L.
    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.
  • Thumbnail Image
    Item
    Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors
    (IEEE, 1998-12) Hong, Inki; Qu, Gang; Potkonjak, Miodrag; Srivastava, Mani B.
    The energy efficiency of systems-on-a-chip can be much improved if one were to vary the supply voltage dynamically at run time. In this paper 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 100s to 10,000s of instructions on modern processors. We present both an exact but impractical formulation of this scheduling problem as a set of non-linear 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.
  • Thumbnail Image
    Item
    Analysis of Watermarking Techniques for Graph Coloring Problem
    (IEEE, 1998-11) Qu, Gang; Pokonjak, Miodrag;
  • Thumbnail Image
    Item
    Techniques for Energy Minimization of Communication Pipelines
    (IEEE, 1998-11) Qu, Gang; Potkonjak, Miodrag;
    The performance of many modern computer and communication systems is dictated by latency of communication pipelines. At the same time, power 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 exploit advantages provided by variable voltage design methodology to optimally select speed and therefore voltage of each pipeline stage. We define the problem and solve it optimally under realistic and widely accepted assumptions. We apply the obtained theoretical results to develop algorithms for power minimization of computer and communication systems and show that significant power reduction is possible without additional latency.