Abstract:
The present invention provides a new method to handle a signal that crosses one or more areas in modular design of programmable logic devices. Even when the signal have an attribute disallowing the use of programmable interconnect points on an associated wire, the programmable interconnect points may still be used if the wire has no input programmable interconnect points outside of the attribute&#39;s associated area. This approach makes use of the programmable interconnect point directionalities and allows for more programmable interconnect points to be used while guaranteeing that the detailed routing solution is conflict free and absent of signal shorts.

Description:
FIELD OF THE INVENTION 
     The present invention relates to programmable logic devices (PLDs), and more particularly to a method for routing signals in programmable logic devices. 
     BACKGROUND OF THE INVENTION 
     A programmable logic device, such as a field programmable gate array (FPGA), is designed to be user-programmable so that users can implement logic designs of their choices. In a typical architecture, an FPGA includes an array of configurable logic blocks (CLBs) surrounded by programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a hierarchy of programmable routing resources. The routing resources comprise many interconnect wires and associated programmable interconnect points (PIPs). In one embodiment, a PIP contains a pass transistor that can be turned on and off, thereby allowing an associated interconnect wire to be either connected or disconnected (depending on the state of the transistor) to other circuit elements. These CLBS, IOBs, and programmable routing resources are customized by loading a configuration bitstream into the FPGA. 
     When an FPGA comprises thousands of CLBs in large arrays of tiles, the task of establishing the required multitude of interconnections between primitive cells inside a CLB and between the CLBs becomes so onerous that it requires software tool implementation. Accordingly, the manufacturers of FPGAS, including the assignee hereof, Xilinx, Inc., have developed place and route software tools which may be used by their customers to implement their respective designs into the FPGAs of these manufacturers. 
     The execution of routing software (called herein “router engines”) can be very time consuming. A typical design implementation can take many hours of computer time using conventional routing software tools. Many routing methods do not connect resources optimally. This could lead to unnecessary timing delays and power consumption in the final design. Thus, there is a need to improve conventional routing methods. 
     SUMMARY OF THE INVENTION 
     The present invention involves a novel application of area constraint for signal routing in a programmable logic device. The method of the present invention can be applied to designs that can be separated into global logic and a number of modules. The signals of the design include at least one global signal and a plurality of local signals. Each local signal is associated with at least one of the modules. The local signals are area constrained. During the module implementation phase of the present invention, an area constraint property is attached to each local signal, while the global signal is not attached to an area constraint property. In one embodiment, power and ground signals are also associated with area constraint properties during this module implementation phase. The global signal is not pre-routed and locked. A router engine routes all the signals in each module under the restrictions of their respective area constraint properties. Thus, the router engine does not commit to a sub-optimal solution. It avoids pre-routing and locking of results early in the routing process. 
     During the assembly phase, the global logic and the modules are merged into a single design. During this phase, area constraint is removed from the power and ground signals. The modules implemented under the module implementation phase are retrieved. As each module is retrieved, its routing is not considered locked. Instead, the router engine has the freedom to rip-up and re-route the signals. However, the routing performed under module implementation is normally kept unless it leads to conflicts or it contains signals running across other modules. This process allows the router engine to explore alternative allowable routing solutions to better achieve overall optimal solution for the entire design. 
     The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1A is a flow chart showing a modular design process of the present invention. 
     FIG. 1B is a flow chart showing detailed steps of module implementation of the present invention. 
     FIG. 1C is a flow chart showing detailed steps of the assembly phase of the present invention. 
     FIG. 2A is a flow chart showing the detailed steps of area constraint property assignment in accordance with the present invention. 
     FIG. 2B is a flow chart showing the detailed steps of signal routing in the module implementation phase of the present invention. 
     FIG. 2C is a flow chart showing the steps in handling routing where a signal crosses one or more areas. 
     FIG. 3 is a flow chart showing the detailed steps of routing in the assembly phase of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     As the number of gates in a PLD becomes larger and larger, it is possible to implement increasingly complex designs into a PLD. It is the experience of many designers that partitioning a single large design into several smaller designs has many benefits. For example, large designs are generally difficult to manage if kept as a single, monolithic entity. By dividing a design into smaller pieces, each piece can be separately understood and implemented. Other advantages are discussed in a Xilinx application note, XAPP 404, entitled “Xilinx Alliance 3.1i Modular Design” and published in June 2000. This publication also contains detailed technical information on conventional modular design methods, and its content is incorporated herein by reference. 
     A new routing paradigm that can improve the performance of router engines used in modular design is disclosed herein. This is illustrated in FIGS. 1A-1C. FIG. 1A is a flow chart showing a modular design process  100  of the present invention. In step  102 , a design is divided into a plurality of modules. Some logic elements (called “global logic”) are not included in any of the modules. Global logic is defined as logic not evenly distributed on a target chip. Members in this group are top level logic elements that connect different modules. Examples of global logic are I/O pins leading onto or off of the chip, DLLs, or other global clock modification resources. In step  104 , each module is floor planned into separate areas. The methods described in the above mentioned publication may be used in steps  102  and  104 . In step  106 , signals are categorized as either global or area constrained. In the present invention, the treatment of these two types of signals is substantially different from that in conventional methods. Details of the categorization and treatment are described below. In step  108 , a module is implemented into its planned area (“module implementation”). In step  110 , process  100  determines whether all the modules have been implemented. If not all have been implemented, step  108  is performed again for another module. If all have been implemented, all the modules (implemented under step  108 ) and global logic are merged into a single design (step  112 ). This is called the “assembly” phase. 
     Details of step  108  (module implementation) as applied to each module is further described in FIG.  1 B. In step  122 , the logic elements of the design associated with a module is assigned to specific physical PLD elements that implement the logic elements (generally referred to as “mapping”). In step  124 , a place tool is used to determine the placement of the physical elements inside the module. In step  126 , each signal in the module is analyzed using the method of the present invention, and then assigned, if appropriate, an area constraint property (described in more detail below). In the present invention, the signal area constraint property of each signal is used to guide the routing. In step  128 , the signals are routed in accordance with the method of the present invention so that the physical elements in the module are connected using routing resources. Additional details of this step will be disclosed below. In step  132 , the area constraint property of each signal belonging to the current module is deposited in a predetermined location. Other information, such as those described in the above-described publication, may also be deposited. 
     Details of step  112  (assembly) are further described in FIG.  1 C. In step  142 , the deposited area constraint properties of all the signals are retrieved. In step  144 , mapping is performed on the full design (including all the modules and global logic). In step  146 , the elements in the full design are placed. In step  148 , all the signals in the full design are routed using the method of the present invention. Additional details of this step will be disclosed below. 
     Turning now to the method of categorizing signals (step  106  of FIG.  1 A), a signal is considered a global signal if its associated resources and loads span throughout the PLD (i.e., more than two modules). In the present invention, global signals are not associated with area constraint. All other signals are local signals. In the present invention, the local signals are highly area constrained. The sources and loads of the local signals are defined within the physical boundaries of their respective modules. Furthermore, the routing of the local signals must reside within pre-defined routing areas of their respective modules. In order to convey such information, each local signal has an associated area constraint property. One exception to this categorization is that both power and ground signals are area constrained during module implementation, and each is associated with an area constraint property. 
     Some examples of global signals are: 
     (a) a signal that has a global clock buffer source; 
     (b) a signal that has a block ram source; 
     (c) a signal that has a boundary scan source; 
     (d) a signal that has a phased lock loop source; 
     (e) a signal that has a global clock I/O source; 
     (f) a signal that has a PCI I/O source; 
     (g) a signal that has a PCI logic source; 
     (h) a signal that has a startup source; 
     (i) a signal that has a I/O source; and 
     (j) a signal that has 2 or more tri-stateable sources (tri-state bus). 
     In conventional methods, module implementation is done in two phases. First, all global signals are routed, and the resulting detailed routing are locked. This is done to prevent subsequent signal routing to alter its prior results. Then all local signals are routed within their pre-defined route region of the module. These conventional methods often commit the router engine unnecessarily to a sub-optimal solution early in the routing phase. By routing the global signals early and independent of the local signals, these conventional methods do not take into consideration the effects of the local signals. This could lead to a sub-optimal result. Making matter worse, the router engine in conventional methods cannot reverse its previous decisions and remedy the problem because the routing of the global signals is locked. 
     During the assembly phase of conventional methods, the previously implemented modules are retrieved and all the module routings are locked. At this point, the router engine is severely handicapped and has little or no flexibility in achieving reasonable levels of routability and delay optimizations. Thus, this further compound the problems introduced at the module implementation phase. Consequently, the final design using conventional methods typically results in excessive run-time and/or poor design routability. 
     In the approach of the present invention, area constraints are assigned on a per signal basis. During module implementation phase, each signal is analyzed. The local signals are each assigned an area constraint while each global signal is assigned no restraint. The area constraint serves as a resource map and will guide the signals in its routing. In this approach, no pre-routing of global signals or locking of routing is required. The router engine can consider all signals. Routing both local and global signals in module implementation leads to more flexibility in performing resource and delay optimizations. 
     To extend this concept to the assembly phase, the area constraint (or lack thereof) of each signal is carried forward from module implementation to final assembly. As each module is retrieved, its routing is no longer considered locked. Instead, the router engine has the freedom to rip-up and re-route as needed (while under the restrictions placed by area constraint). As a result, the router engine can explore alternative allowable routing solutions to better achieve an overall optimal solution for the entire design. 
     The detailed process  170  of assigning area constraint property (i.e., step  126  of FIG. 1B) is shown in FIG.  2 A. One aspect of the present invention is that each local signal in a module may have a different routing area. This is different from conventional modular implementation in which all local signals in a module have the same routing area. One advantage is that this method provides more flexibility in routing. The routing area of a local signal is determined by external sources (such as input from users of the present method). 
     Two pieces of information are found to be very important for routing local signals in accordance with the present invention. The first piece of information is a pair of coordinates defining a “bounding box”, which is the routing area of the signal. The second piece of information is whether the local signal is allowed to use routing resources that cross the bounding box. 
     In step  172  of FIG. 2A, information of each local signal is encoded into its associated area constraint property. In one embodiment, data encoded into an area constraint property includes (a) version number of data encoded, which is used to verify data and control revisions, (b) name of the area constraint, (c) two (x,y) coordinates, and (d) an attribute describing if the signal is allowed to use routing resources that cross a routing area defined by the (x,y) coordinates. In one embodiment, only one area will be assigned an attribute of “allow” for a signal to use PIPs on wires that cross one or more areas. The (x,y) coordinates are the bounding box coordinates (e.g., lower left and upper right) of the routing area of the signal. These pieces of data may be encoded in any convenient format because the format is not important for implementing the present invention. 
     The signals in a module are considered one by one. Note that the order of considering the two factors listed below (i.e., global and old property) is not important to the present invention. In step  174 , process  170  determines whether a signal under consideration is a global signal. If it is, the signal is not assigned an area constraint property (step  184 ), and another signal is considered. If it is not, process  170  determines whether the signal is associated with an old area constraint property, e.g., based on a previous routing operation (step  176 ). If the signal is associated with an old area constraint property, the old area constraint property is removed (step  178 ). A new area constraint property (generated by step  172 ) is attached to the signal (step  180 ). If it is determined (under step  176 ) that the signal is not associated with an old area constraint property, then there is no need to perform step  178 , and a new area constraint property is attached to the signal. Process  170  then determines whether all the signals associated with a module have been considered (step  182 ). If all the signals have been considered, process  170  terminates. Otherwise, the loop will be repeated. 
     In process  170 , power and grounds signals are not considered global signals, and are assigned area constraints under the present invention. 
     Note that the present invention can be applied to many types of PLDs. In one embodiment, this method is most effectively applied when there are multiple non-overlapping routing areas defined over the same routing fabric in an integrated circuit device. This allows an application to control and manage detailed routing results within pre-defined routing areas. Dense routing results can be achieved while guarantying no signal shorts. 
     The detailed process  200  of route signals in the module implementation phase (i.e., step  128  of FIG. 1B) is shown in FIG.  2 B. In step  202 , the area constraint property attached with a signal is read. Some signals (e.g., global signals) may not have any area constraint. In step  204 , this area constraint property is supplied to a router engine. In step  206 , the router engine routes the signal in accordance with the restrictions in the area constraint property. In step  208 , process  200  determines whether all the signals in the module have been routed. If all the signals have been routed, process  200  terminates. Otherwise, the loop will be repeated. 
     One aspect of the present invention is a procedure to handle routing where a signal crosses one or more areas. This is shown in a flow chart  210  of FIG. 2C, which is a part of step  204  of FIG.  2 B. In step  212 , the attribute of a signal is read. If the attribute is “not allow,” process  170  determines whether there is at least one input PIP located on a wire that is outside of the routing area under consideration (step  213 ). If the attribute is “allow,” flow chart  210  returns to other parts of step  204  of FIG.  2 B. If step  213  determines that there is no input PIP outside of the routing area under consideration, a notation is added to the area constraint property indicating that the PIPs on the wire can be used for routing inside the routing area under consideration (step  214 ). Flow chart  210  then returns to other parts of step  204 . If step  213  determines that there is at least one input PIP outside of the routing area under consideration, then every PIP on the wire will be marked as excluded or unavailable during the routing process (step  215 ). Flow chart  210  returns to other parts of step  204 . This approach makes use of the PIP directionalities and allows for more PIPs to be used while guaranteeing that the detailed routing solution is conflict free and absent of signal shorts. 
     A process  220  of routing the full design (i.e., step  148  of FIG. 1C) is shown in FIG.  3 . The first phase of operations is to properly handle the area constraint property of the signals. In step  222 , process  220  determines whether the signal under consideration belongs to global logic. If it belongs to global logic, it is not associates with an area constraint property. Thus, process  220  can proceed with other signals (step  228 ). If it does not belong to global logic, process  220  determines whether the signal spans two or more modules (step  224 ). If it does, the existing area constraint property is also removed (step  230 ). If it does not, process  220  determines whether the signal is a power or a ground signal (step  226 ). If it is either a power or ground signal, the existing area constraint property is removed (step  230 ). If it is not, the area constraint property assigned using the method of the present invention remains with the signal. This phase of the operation for one signal is completed. Process  220  determines whether all the signals have been considered (step  228 ). If not all the signals in the full design have been considered, the next signal will be considered by looping back to step  222 . When all the signals have been considered, the second phase begins. 
     In step  234 , the area constraint property of the first phase is supplied to a router engine (which can be the same engine as the one used in process  200  of FIG.  2 B). In carrying out this step, the procedure described above in connection with flow chart  210  of FIG. 2C (for handling signals that cross one or more areas) can be used. In step  236 , the modules routed using module implementation is retrieved. The routing information developed under module implementation is used in the assembly phase. If the signals in a module are not in conflict with the global signals or signals in other modules, the routing under module implementation does not need to be changed. In step  238 , the router engine routes all the signals using information under module implementation and taking into account of the restrictions based on the area constraint properties. Process  220  determines whether all the signals have been routed (step  240 ). If not all have been routed, process  220  loops back to step  234 . If all have been routed, process  220  stops. 
     It can be seen from the above description that a novel routing method has been disclosed. Those having skill in the relevant arts of the invention will now perceive various modifications and additions which may be made as a result of the disclosure herein. Accordingly, all such modifications and additions are deemed to be within the scope of the invention, which is to be limited only by the appended claims and their equivalents.