Browse Prior Art Database

Embedding Interleaved With Constraints

IP.com Disclosure Number: IPCOM000052104D
Original Publication Date: 1981-Apr-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Frisiani, AL: AUTHOR [+3]

Abstract

A method is outlined for the embedding - interleaving placement and routing - of a logic design on a chip or a set of chips on a board. These embeddings are subject to constraints, such as timing, power dissipation, distances to I/O pins, delta-I effects, etc., and such checking operation is interleaved with the embedding.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Embedding Interleaved With Constraints

A method is outlined for the embedding - interleaving placement and routing - of a logic design on a chip or a set of chips on a board. These embeddings are subject to constraints, such as timing, power dissipation, distances to I/O pins, delta-I effects, etc., and such checking operation is interleaved with the embedding.

Given a logic design (See Original.) and a "physical technology", (See Origi embed-place and wire (See Original.) into (See Original.) subject to a number of constraints, such as a bound on the total delay, delta-I effects, wiring constraints, closeness of circuits to I/O pins if they are off-chip drivers, bounds on power dissipation, etc. A similar problem exists in embedding chips onto boards - whatever the higher-level package is called. This article proposes a heuristic method for making such an embedding, utilizing an interleaving technique. For any given (##), the size of (See Original.) can be adjusted so that it is always possible to make some embedding, but then (See Ori may be relegated to more than one chip. The subsets of logic are initially defined by the natural grouping of elements given by the results of the (; See Original.) routines [1]. This method applies both to circuit-onto and chip-onto-board embeddings. The method is not exact but heuristic. Because of the computational complexity of the problem, such an attack is necessary.

First, we compute by a simple delay algorithm [1] for each circuit (chip) the longest interchip (board) delay through the circuit chip called the (See Original.). Let (See Original.)(1) be the subset of (See Origin each member having a maximum logic length. Let (See Original.)(2) be the subset with the ne longest logical delay etc., (See Original.)(1), (See Original.)(2), (See Origina (See Original.)(k), define a (See Original.) via logic length in descending order of delay.

Within each equivalence class (See Original.)(i), i=l,...,k, order the chips according to power (dissipation) on the chip, the highest powered element first. Place the highest powered chip c(l) in a slot of maximum possible power dissipation.

Order likewise the chip slots, (m,n) positions on (; See Original.) for chip m, n integers, according to their current power (dissipation), according to the formula See Origina...