Skip to main content
SpringerLink
Log in

On Optimal Interconnections for VLSI

  • Book
  • © 1995

Overview

Authors:
  1. Andrew B. Kahng

    1. University of California, Los Angeles, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Gabriel Robins

    1. University of Virginia, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: The Springer International Series in Engineering and Computer Science (SECS, volume 301)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (5 chapters)

  1. Front Matter

    Pages i-xvii
    Download chapter PDF

  2. Preliminaries

    • Andrew B. Kahng, Gabriel Robins
    Pages 1-15

  3. Area

    • Andrew B. Kahng, Gabriel Robins
    Pages 16-63

  4. Delay

    • Andrew B. Kahng, Gabriel Robins
    Pages 64-139

  5. Skew

    • Andrew B. Kahng, Gabriel Robins
    Pages 140-196

  6. Multiple Objectives

    • Andrew B. Kahng, Gabriel Robins
    Pages 197-238

  7. Back Matter

    Pages 239-286
    Download chapter PDF
Back to top

Keywords

About this book

On Optimal Interconnections for VLSI describes, from a geometric perspective, algorithms for high-performance, high-density interconnections during the global and detailed routing phases of circuit layout. First, the book addresses area minimization, with a focus on near-optimal approximation algorithms for minimum-cost Steiner routing. In addition to practical implementations of recent methods, the implications of recent results on spanning tree degree bounds and the method of Zelikovsky are discussed. Second, the book addresses delay minimization, starting with a discussion of accurate, yet algorithmically tractable, delay models. Recent minimum-delay constructions are highlighted, including provably good cost-radius tradeoffs, critical-sink routing algorithms, Elmore delay-optimal routing, graph Steiner arborescences, non-tree routing, and wiresizing. Third, the book addresses skew minimization for clock routing and prescribed-delay routing formulations. The discussion starts with early matching-based constructions and goes on to treat zero-skew routing with provably minimum wirelength, as well as planar clock routing. Finally, the book concludes with a discussion of multiple (competing) objectives, i.e., how to optimize area, delay, skew, and other objectives simultaneously. These techniques are useful when the routing instance has heterogeneous resources or is highly congested, as in FPGA routing, multi-chip packaging, and very dense layouts.
Throughout the book, the emphasis is on practical algorithms and a complete self-contained development. On Optimal Interconnections for VLSI will be of use to both circuit designers (CAD tool users) as well as researchers and developers in the area of performance-driven physical design.

Authors and Affiliations

  • University of California, Los Angeles, USA

    Andrew B. Kahng

  • University of Virginia, USA

    Gabriel Robins

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation