Browse Prior Art Database

Active Detouring Algorithm

IP.com Disclosure Number: IPCOM000244132D
Publication Date: 2015-Nov-12
Document File: 6 page(s) / 8M

Publishing Venue

The IP.com Prior Art Database

Abstract

An algorithm for active detouring of nets is discussed for congestion resolution The algorithm is divided into three parts where first a congestion map for a complete design is generated Based on identified congested regions from the map candidate nets for detouring are determined that satisfy certain criteria Finally the detouring algorithm based on weights is applied to forcefully detour nets out of congested regions

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

Active Detouring Algorithm

Abstract

An algorithm for active detouring of nets is discussed for congestion resolution. The algorithm is divided into three parts, where first a congestion map for a complete design is generated. Based on identified congested regions from the map, candidate nets for detouring are determined that satisfy certain criteria. Finally, the detouring algorithm based on weights is applied to forcefully detour nets out of congested regions.

Background

With increasing demand for packing density on chip, routing congestion has become a major bottleneck in today’s SoC. The problem is further aggravated by the fact that nets are also bottlenecks for chip performance. In most cases the congestion problem is seen in later stages of the design cycle, where it is more difficult to resolve congestion. Detouring is an important method used in later stages of design to ease congestion. In this paper we propose an algorithm to automatically force specific nets to be detoured, while controlling the amount of detouring that occurs.

Congestion Resolution

Algorithm for congestion resolution is divided into 3 parts is shown in Fig. 1.

Fig. 1   Algorithm for congestion resolution

1.      Congestion Prediction

The first step of the algorithm is to generate a congestion map of the design by diving design into unique boxes of predefined size and then finding routing density and track requirement for each box.

Fig. 2 shows a congestion map generated for a design. One important observation is that congestion distribution is Gaussian in the sense that only a small portion of the design is highly congested (shown in orange) and most of the design is not congested (shown in green and blue). This is the primary motivation for the detouring algorithm since taking some nets out of congested regions and routing them through non-congested regions can help reduce congestion.

Fig. 2 Congestion map for the design. Orange shows high congestion and green and blue show less congestion

2.      Nets Selection           

Candidate nets for detouring in congestion regions are identified based on the following criteria:

a.      Slack on net is greater than slack_threshold

b.      Net length is greater than length_threshold

c.       Nets do not have source and sink pins in region, i.e., net is completely passing through region

d.      Net direction is same as that of congestion, i.e., either horizontal or vertical

e.      Most of net is contained in that region only.

Point c. is necessary because if net has either source or sink pin in region then even after detouring some portion of net will always go through region and detouring may not ease out congestion in that case.

Point d. is necessary because if net direction is opposite to congestion direction then detouring will not help at all.

Point e. is considered so that detouring has maximum impact on congestion score of the region.

3.      Active Detouring Algorithm

Fig. 3 is a flow chart of our proposed detouring algorithm. First we gene...