Abstract:
In the design of a structured ASIC device that is intended to be functionally equivalent to a programmed FPGA, an initial design for the structured ASIC may be modified in any of several ways to improve various aspects of its performance. For example, for critical or near-critical parts of the structured ASIC design, attempts may be made to permute inputs to improve performance. Alternatively or in addition, Shannon&#39;s decomposition or other decomposition may be attempted to move a critical input closer to the output of a cell. Another possible modification is replacement of high-speed adders with slower-speed adders in non-critical parts of the structured ASIC design.

Description:
BACKGROUND OF THE INVENTION 
   This invention relates to the design of application-specific integrated circuits (“ASICs”). More particularly, the invention relates to the design of ASICs of the type known as structured ASICs that are intended to be functionally equivalent to a field-programmable gate array (“FPGA”) that has been programmed in a particular way. 
   FPGAs are relatively general-purpose integrated circuit devices that can be programmed to perform any of many different functions such as logic. After a design has been implemented and proven in an FPGA, it may be desirable to migrate that design to a structured ASIC. A structured ASIC is an integrated circuit that always has the same basic structure, but that has several layers that can be customized to cause the structured ASIC to implement particular functions. For example, many of the masks used to make a particular type of structured ASIC are the same or substantially the same for all ASIC products of that type. A few of the masks can be customized to give any one of those products a particular set of functions. These functions can be those that have been proven to work in a programmed FPGA. Using a structured ASIC to replicate an FPGA in this way (as opposed to attempting to design an unstructured ASIC, completely “from scratch”, for this purpose) has a number of advantages. These include faster design turn-around, lower design cost, less risk that the ASIC design will not be a good functional equivalent of the FPGA design, etc. 
   References such as the following show examples of structured ASICs and methods for converting FPGA designs to structured ASIC implementations of those designs: Foo U.S. patent application Ser. No. 10/861,585, filed Jun. 4, 2004; Chua et al. U.S. patent application Ser. No. 10/884,460, filed Jul. 2, 2004; Yuan et al. U.S. patent application Ser. No. 10/916,305, filed Aug. 11, 2004; Schleicher et al. U.S. patent application Ser. No. 11/050,607, filed Feb. 3, 2005; Pedersen et al. U.S. patent application Ser. No. 11/072,560, filed Mar. 3, 2005; Schleicher et al. U.S. patent application Ser. No. 11/097,633, filed Apr. 1, 2005; Yuan et al. U.S. patent application Ser. No. 11/101,949, filed Apr. 8, 2005; Park et al. U.S. patent application Ser. No. 11/108,370, filed Apr. 18, 2005; Park et al. U.S. patent application Ser. No. 11/115,641, filed Apr. 27, 2005; Lim et al. U.S. patent application Ser. No. 11/141,867, filed May 31, 2005; and Tan et al. U.S. patent application Ser. No. 11/141,941, filed May 31, 2005. (All of these references are assigned to the same assignee as this disclosure, and references identified as patent applications are co-pending with this disclosure.) As at least some of these references show, programmed-FPGA-to-structured-ASIC conversion methods frequently include use of libraries of structured ASIC cells that are known to be equivalent to particular programmed FPGA functions or cells. 
   There are several respects in which the known methods of converting an FPGA design to a functionally equivalent structured ASIC design could be improved. For example, the known methods do not attempt to permute the inputs to structured ASIC library cells to try to achieve better timing performance. Nor do the known methods attempt to decompose a structured ASIC library cell for similar purposes. Still another possible deficiency of known programmed-FPGA-to-structured-ASIC conversion methods is that the known methods tend to implement all adders in the structured ASIC using two-bit adder cells. These may be more costly (e.g., in terms of area occupied and power consumed) than is warranted in all cases. 
   SUMMARY OF THE INVENTION 
   In the design of a structured ASIC that is intended to be functionally equivalent to a programmed FPGA, after an initial design for the structured ASIC has been produced from a conversion of the programmed FPGA design, any one or more of several modifications of the initial structured ASIC design are attempted to improve various aspects of the structured ASIC design. One such possible modification is permutation of inputs to a cell in a critical portion of the structured ASIC design for the purpose of moving a critical logical input to that cell to a faster physical input of the cell. Another possible modification employs Shannon&#39;s decomposition to move a critical input to a cell to the selection control input terminal of a multiplexer that selects from among outputs of other cells that effect the remaining logical operations of the original structured ASIC cell. Still another possible modification is decomposition of the original structured ASIC cell in an effort to move a critical input closer to the output of a new cell structure that implements the decomposed version of the original. A final possible modification is replacement of high-speed, two-bit adders in non-critical portions of the structured ASIC design with slower-speed, one-bit adders. 
   Further features of the invention, its nature and various advantages, will be more apparent from the accompanying drawings and the following detailed description. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a simplified block diagram of an illustrative logic cell. 
       FIG. 2   a  is a simplified block diagram of illustrative circuitry in a structured ASIC device. 
       FIG. 2   b  is a simplified block diagram of other illustrative circuitry in a structured ASIC device. 
       FIG. 3  is a simplified flow chart of part of an illustrative structured ASIC design process. 
       FIGS. 4   a  and  4   b  are collectively a simplified flow chart of further parts of an illustrative structured ASIC design process. 
       FIGS. 5   a  and  5   b  are collectively a simplified flow chart of other aspects of an illustrative structured ASIC design process in accordance with the invention. 
       FIGS. 6   a  and  6   b  are collectively a simplified flow chart of an illustrative elaboration of one of the steps in  FIG. 5   b  in accordance with the invention. 
       FIGS. 7   a  and  7   b  are collectively a simplified flow chart of an alternative or additional illustrative elaboration of one of the steps in  FIG. 5   b  in accordance with the invention. 
       FIG. 8  is a simplified block diagram of illustrative structured ASIC circuitry in accordance with certain aspects of what is shown in  FIGS. 7   a  and  7   b.    
       FIG. 9  is a simplified flow chart of another alternative or additional illustrative elaboration of one of the steps in  FIG. 5   b  in accordance with the invention. 
       FIG. 10  is a simplified block diagram of illustrative structured ASIC circuitry in accordance with certain aspects of what is shown in  FIG. 9 . 
       FIG. 11  is a simplified flow chart illustrating another possible aspect of the invention. 
       FIG. 12  is a simplified block diagram of illustrative machine-readable media in accordance with a possible aspect of the invention. 
   

   DETAILED DESCRIPTION 
   This description assumes a basic knowledge of programmed-FPGA-to-structured-ASIC conversion of the general type shown in the references mentioned earlier in this specification. 
   Unlike look-up-table-based (“LUT-based”) architectures, the cells used in structured ASICs in accordance with this invention at least originate from a fixed library of functionally equivalent structured ASIC cells that have been worked out in advance. Not all k-input functions are legal library cells when k becomes larger than a certain number such as 4. The router step in known structured ASIC design methods does not permute the inputs of a cell retrieved from the library to attempt to speed up a critical path in the structured ASIC design. This can mean that significant structured ASIC performance improvements are not attained due to not taking advantage of faster structured ASIC cell inputs. Different structured ASIC cell inputs can have very different delays to output. For example, in the library of structured ASIC cells for the so-called Fusion product of Altera Corporation, a six-input EXCLUSIVE OR (“XOR”) function (shown in block diagram form in  FIG. 1 ) has a typical delay of 667 ps (picoseconds) from its F input to the output, but only a 154 ps delay from its A input to the output. This is a difference of over 500 ps. 
   Another characteristic of known programmed-FPGA-to-structured-ASIC conversion methods is the following. In the interest of achieving balanced and speed-based flows, high-speed adders are always used to implement carry chains. However, high-speed adders cost much more than normal single-bit adder cells (see  FIGS. 2   a  and  2   b  which show the relative sizes in a structured ASIC of a high-speed two-bit adder  20  and a normal one-bit adder  30 .) 
   A typical algorithm for synthesizing a structured ASIC that is functionally equivalent to a programmed FPGA is shown in  FIG. 3 . The desired design (sometimes referred to herein as the user&#39;s logic design) goes through a normal FPGA synthesis flow  110 . Just before the atom netlist  120  is formed, ASIC conversion step  130  is performed. This approach has the advantage of minimal disturbance to the structure of the FPGA netlist, since conversion from FPGA cells to structured ASIC cells is a local change. More detail regarding relevant aspects of ASIC conversion step  130  is shown in  FIGS. 4   a  and  4   b , which will now be described. 
   In step  210  each look-up table (“LUT”) from step  110  is considered in turn. For a LUT being considered, the canonical form of the LUT is computed to get a library cell key value. This includes combining the minimum LUTMASK value and the number of inputs that the LUT has. The LUTMASK value of a LUT is the value stored in the memory of the LUT. The inputs to the LUT control selection of one of these memory storage locations as the source of the output of the LUT. The inputs to the LUT can be permuted until the LUTMASK value has been minimized, which is the so-called canonical LUTMASK value. That value is combined with the number of LUT inputs being used to produce the library cell key value that is referred to as X. 
   In step  220  X is used to find structured ASIC library cells that have key value X. 
   Step  230  tests whether any structured ASIC library cells having key value X have been found. If not, step  240  is performed to split the starting LUT into smaller LUTs, for each of which the above-described  FIG. 4   a/b  steps are repeated. Eventually at least one structured ASIC library cell can be found for each starting or sub-divided LUT (e.g., because there is at least one structured ASIC library cell for every four-input LUT). 
   An affirmative result from step  230  leads to step  250 . In step  250  the structured ASIC library cell having key value X and the smallest size is the one finally selected for use in the structured ASIC implementation of the user&#39;s logic design. (Step  250  refers to the smallest hybrid logic element (“HLE”) count. An HLE is the basic unit of structured ASIC logic in this illustrative embodiment. An HLE is a via-programmable 2:1 multiplexer, two two-input NAND gates, and two inverters.) 
   In accordance with an illustrative embodiment of the present invention, at the end of the structured ASIC synthesis step (e.g., after performance of step  250  for all LUTs), the flow shown in  FIGS. 5   a  and  5   b  may be performed. In step  310  delays are computed for all of the combinational nodes in the structured ASIC design. This may be done in both the input direction and the output direction. In step  320  so-called critical nodes are identified. A node is said to appear on a critical path if the total delay is equal to the maximum delay of the design. A threshold is used to identify nodes that are not critical but that are close to critical. The delay model itself can be a combination of the node fanout and the number of HLE levels a given input has to go through. It will be appreciated that different inputs of a cell go through different numbers of HLE stages to reach the cell output, so they are assigned different delay values. 
   In step  330  a modification of the structured ASIC design may be attempted for each critical or near critical node. Examples of possible modifications are discussed later in this specification. (To simplify the further discussion, critical and near critical nodes will generally be referred to simply as critical nodes.) 
   In step  340  the effectiveness of each modification is tested to determine whether the modification should be accepted (step  360 ) or rejected (step  350 ). For example, in order to be accepted, the modification may be required to satisfy a “goodness” metric, which can be the amount by which the modification reduces the maximum delay of the design or a combination of the maximum delay and the average delay. 
   It will be appreciated that other strategies can be used to compute the delay and critical nodes. For example, a timing analysis algorithm can be called. 
     FIGS. 6   a  and  6   b  illustrate a type of modification that can be performed in relation to step  330  in accordance with the invention. This type of modification is a permutation of inputs to a structured ASIC cell. 
   In step  410  each structured ASIC cell from the critical node set (step  320 ) is considered. 
   In step  420 , for the critical input of a cell from step  410  (e.g., input F), the structured ASIC cell library is queried to identify all of the physical inputs to that cell that are faster than physical input F. 
   In step  430 , the faster physical inputs (assuming there are any) are sorted from fastest to slowest. 
   In step  440 , for each physical input that is faster than F (preferably starting with the fastest (e.g., physical input A)), the steps described below are performed. 
   In step  450  the LUTMASK stored for the structured ASIC library cell being used is retrieved (e.g., from the structured ASIC cell library) and defined as MASK_ORIG. 
   In step  460  logical inputs A and F are swapped and the resulting new LUTMASK value for the cell is determined. This new value is defined as MASK_NEW. 
   In step  470 , MASK_NEW and MASK_ORIG are compared. If they are equal, then the cell is symmetric with respect to logical inputs A and F. This means that these logical inputs can be swapped with no need to change the underlying structured ASIC cell. Accordingly, this swap is performed (i.e., original, critical, logical input F is routed to faster physical input A, and original logical input A is routed to slower physical input F. Steps  340  et seq. are then performed to determine whether or not the swap is sufficiently effective to warrant keeping it. If so, the swap is accepted and processing moves on to consider another possible modification (e.g., for another critical node). If the swap is not sufficiently effective to warrant accepting, another possible input swap may be tried for the structured ASIC cell being considered (if other, possibly effective swaps have been identified in step  420 ). These other possible swaps may be tried in order from fastest to slowest, as identified in step  430 . 
     FIGS. 7   a  and  7   b  illustrate another type of modification that can be performed in relation to step  330  in accordance with the invention. This type of modification uses Shannon&#39;s decomposition. In this approach, step  510  is performed to move the critical input F to the select line of a two-input multiplexer (“mux”) cell  610  ( FIG. 8 ) in the structured ASIC design being developed. In step  520  the two data inputs  620  and  630  are constructed as g0=f( . . . , 0) and g1=f( . . . , 1), respectively. (In a typical Altera Fusion-type product, the delay of the select line of a mux cell like  610  is 120 ps.) Step  530  then initiates trying both of the possibilities specified in steps  540  and  550 . 
   In step  540  an attempt is made to find, in the structured ASIC cell library, cells for implementing g0 and g1. If that can be done, then those library cells can be used as components  620  and  630  in the modified implementation, shown in  FIG. 8 , of the starting structured ASIC cell. 
   In step  550  an attempt is made to absorb 0 into g0or 1 into g1. This can be done if the resulting cell is still in the structured ASIC library. It will be appreciated that in an embodiment in which all four-input functions are library cells, if the original function f has five or fewer inputs, it is always possible to look at this alternative. 
   In step  560  the delays resulting from the step  540  and step  550  modifications are computed (assuming that there are usable results from steps  540  and/or  550 ). In step  570  the solution that gives the smaller value is picked (e.g., for further consideration in step  340 ). 
   It will be appreciated that modifications of the type illustrated by  FIGS. 7   a  and  7   b  essentially turn one starting structured ASIC cell into three structured ASIC cells ( 610 ,  620 , and  630 ) if the modification is ultimately accepted. 
     FIG. 9  illustrates another type of modification that can be attempted in relation to step  330  in accordance with the invention. This is decomposition of a starting structured ASIC cell having a critical input in order to move that critical input closer to the output. For example, a cell whose LUTMASK is 6AFFFF6AFF6AFF6A has a typical A input delay (in an Altera Fusion-type product) of 477 ps. Its functionality is as follows:
   f=A &amp;( D $( E &amp; F )+ C′+B ′)+ A ′&amp;( B &amp; C+D $( E &amp; F )) 
(&amp; denotes AND, + denotes OR, and $ denotes XOR). If we define X=D $ (E &amp; F) and Y=B &amp; C, then f can be decomposed as
   f=A &amp;( X+Y ′)+ A ′&amp;( X+Y )= X+A $ Y      FIG. 10  shows a structured ASIC implementation in these terms. Three structured ASIC library cells (“subcells”)  810 ,  820 , and  830  replace the original structured ASIC cell. The delay from input A to the cell output is now reduced to 220 ps in an Altera Fusion-type product.
 
   Returning to  FIG. 9 , in step  710  a critical input (e.g., A in the above example) to a structured ASIC cell is identified. 
   In step  720  the cell is decomposed to move the initial input closer to the output, if possible. 
   In step  730  an attempt is made to find each subcell in the decomposition in the library of structured ASIC cells. If that can be done, those library cells are used to produce (as in  FIG. 10 ) a modified structured ASIC implementation of the starting ASIC library cell. Step  340  can then be performed as part of a determination as to whether or not to retain this modification in the final structured ASIC design. 
     FIG. 11  illustrates another type of modification that can be employed in accordance with the invention. In step  910  all adders in the structured ASIC design are identified. 
   In step  920  each adder is tested to determine whether it is in a critical or near-critical part of the structured ASIC design. The threshold value mentioned in step  920  is used to establish what is near critical. If an adder is critical or near-critical, step  930  is performed to leave the default, high-speed, two-bit adder implementation (e.g., as in  FIG. 2   a ) in place in the structured ASIC design. On the other hand, if an adder is not critical or near-critical, step  940  is performed. 
   In step  940 , the default, high-speed, two-bit adder is replaced by a normal single-bit adder (e.g., as in  FIG. 2   b ). 
   Modifications of the type covered by  FIG. 11  help save HLE usage and power consumption by the final structured ASIC design. 
     FIG. 12  illustrates another possible aspect of the invention. This is machine-readable media  1000  (e.g., magnetic disc(s), optical disc(s), magnetic tape(s), or the like) encoded with machine-readable instructions  1010  (e.g., a computer program) for at least partly performing one or more methods in accordance with the invention. 
   It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the order in which certain steps are performed can, in some cases, be different from the order shown and described herein.