Browse Prior Art Database

Method and apparatus for improving wirelength and frequency in circuit design

IP.com Disclosure Number: IPCOM000244046D
Publication Date: 2015-Nov-09

Publishing Venue

The IP.com Prior Art Database

Abstract

This disclosure describes Method and apparatus for improving wirelength and frequency in circuit design

This text was extracted from a Microsoft PowerPoint presentation.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 22% of the total text.

Slide 1 of 42

Method and apparatus for improving wirelength and frequency in circuit design


Slide 2 of 42

Background: FPGA Fitter Flow

Device

Information

Synthesis/Mapping

Design Source

& Constraints

Atom Netlist

Pre-Fitter

APL: Analytic Placement

APL BLE placement

Physical clustering

Placement

APL CBE Placement

Fitter

Detailed Placement Refinement

Using Annealing Framework

Atom Locations

Routing

Timing

Report

Timing Analysis

Programming

Files

Assembler

2


Slide 3 of 42

This invention focuses is on the placement stage

Improvements after analytic placement and legalization

Before detailed placement

APL BLE placement

Physical clustering

APL CBE Placement

Invention

focus

APL Legalizer

APL CBE Improver

Detailed Placement Refinement

Using Annealing Framework

3


Slide 4 of 42

Problem statement

Algorithm to optimize physical locations of cells in the design process of fitting a user design

Objectives:

  Improve timing (maximum frequency of operation of the design)

  Minimize routed wire of all electrical nets

Constraints:

  Chip legality

  Runtime scalability

4


Slide 5 of 42

Summary of invention

We present a novel dynamic programming (DP) based algorithm for optimizing cell placement of a design to optimize routed wirelength, max frequency of operation

The DP algorithm is scalable in runtime

The DP algorithm’s worstcase runtime complexity can be tuned to be within a spectrum of O(n2) to O(2n+logn) to provide an easy Quality of Results (QoR) vs runtime trade-off

The DP algorithm can optimize cell placement in 1 dimension (X or Y) and in 2 dimensions (simultaneous X/Y)

The DP algorithm can be used as a minimum wirelength legalizer

The DP algorithm can be used for constructive placement in a window

The DP algorithm lends itself to parallel implementation

5


Slide 6 of 42

Prior Art

[1] Mixed integer programming models for detailed placement, Shuai Li and Cheng Kok-Koh, ISPD 2012

[2] Optimal Partitioners and End-case Placers for Standard-cell Layout, Andrew Caldwell, Andrew Kahng and Igor Markov, TCAD 2000

[3] On interaction between routing and detailed placement, Jariwala and Lillis, ICCAD 2004

6


Slide 7 of 42

Prior Art: Mixed integer programming models for detailed placement [1]

Rows and columns of sitesin each rectangular sliding window

Uniform-height cellsoccupying integral number of contiguous sites

7

[This slide contains 1 picture or other non-text object]


Slide 8 of 42

Prior Art: Mixed integer programming models for detailed placement [1]

Model based on site-occupation variables:pcrq whether cell c occupies the site at row r and column q

Linear Program:

8

[This slide contains 2 pictures or other non-text objects]


Slide 9 of 42

Prior Art: Mixed integer programming models for detailed placement [1]

Advantages:

  Optimal solution for the region under consideration – captures the relative positions of cells for net length

Disadvantages:

  Not runtime scalable

  MILP explodes in runtime with increasing numbers of cells

  Runtime complexity is exponential

9


Slide 10...