Method of segmenting an FPGA channel architecture for maximum routability and performance

• US 5,598,343 A
• Filed: 10/01/1993
• Issued: 01/28/1997
• Est. Priority Date: 10/01/1993
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Nag, Sudip K., Roy, Kaushik
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US08/130,605
• Time in Patent Office: 1,215 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/716, 340/825.83, 326/39, 326/41
• US Class Current: 716/128
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

The current invention considers automatic synthesis of segmented channel architecture of row-based FPGAs so as to achieve maximum routability and performance. The routability of a channel and the performance of the routed nets may have conflicting requirements. For a given number of tracks, very short segments usually enhance routability at the expense of performance. For such a granular segmented channel architecture routing of long nets may require that several short segments be joined together by programming horizontal antifuses. Depending on the antifuse technology, the programmed antifuses can add considerably to the path delays. A simulated annealing based channel architecture synthesis algorithm has been developed which enhances routability and performance. The synthesis algorithm is based on the fact that a strong correlation between the spatial distribution of nets and segments in a channel improves both routability and performance.

Claims

1. A method of segmenting a field programmable gate array (FPGA) channel architecture comprising:

(a) designing an initial channel architecture for a row-based FPGA having a preselected number of horizontal tracks in each channel and a preselected number of logic elements in each row, including assigning an arbitrary channel segmentation for the channel, wherein any single segment is no less than the width of one logic module, and wherein the same segmentation is used for each channel in the FPGA;

(b) modifying the assigned arbitrary channel segmentation by either merging two adjacent segments in a track or breaking a segment within a track into two segments, wherein the segments are randomly selected for either merging or breaking;

(c) determining the routing cost associated with different preselected net distributions with the assigned channel segmentation as follows;

##EQU10## where the first term V_r ·

|N_iu | represents the number of 1-segment unroutable nets, the second term V_w·

α

_i represents the segment wastage factor, and the last term ##EQU11## represents the percentage segment overlap for the unroutable nets;

(d) repeat step (c) for each of the channels in the FPGA and add the cost of routing each channel to calculate a total cost C;

(e) repeating step (b) by again modifying the channel architecture;

(f) again repeating the step of determining the routing cost according to the formula in step (c) and (d) associated with different pre-selected net distributions with the modified channel segmentation;

(g) if the total routing cost is lower after modifying the channel architecture then this modification is accepted and if the total routing cost after modifying the channel architecture is higher then this modification is accepted only with a probability e -|8(c)|/Temp where |8(c)| is the absolute value of the change in cost C and Temp is the annealing temperature, otherwise the modification is rejected and a further modification is made; and

(f) repeating the steps of modifying the channel architecture and calculating the cost of routing until a certain minimal cost is achieved.