Abstract:
Based upon a circuit design, a system generates a plurality of seed circuits. An initial circuit constraint is used to generate a plurality of constraints sets, one for each seed circuit. The plurality of seed circuits and the corresponding constraint sets are distributed to a plurality of processors. In parallel, the processors execute a design software application to generate a plurality of candidate circuits based on the constraints and the seed circuits. The best candidate of the plurality of candidate circuits may be used for additional iterations in the design process.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    A. Field of the Invention  
           [0002]    This invention relates generally to circuit design and, more particularly, to improved methods and apparatus for robust distributed circuit synthesis.  
           [0003]    B. Description of the Related Art  
           [0004]    Design synthesis is a process of creating an integrated circuit implementation from a functional specification and a set of constraints. In recent years, integrated circuits have become increasingly complex and typically incorporate one to five million logic gates. Integrated circuits are implemented using technologies less than 0.25 micron in size mounted on a flat physical surface. The physical implementation of an integrated circuit is often referred to as a “chip.” 
           [0005]    Today, integrated circuits are often designed using logic synthesis software such as Synopsis Design Compiler offered by Synopsys, Inc. Before using logic synthesis software programs, like Design Compiler, chip designers decide what functions the chip should perform and compile a functionality specification. Most conventional synthesis software programs use the functionality specification to test candidate circuit architectures. The functionality specification and various parameters, or “constraints,” are input to the synthesis software. Examples of constraints are the desired size of the circuit (in physical area) or the circuit speed in performing the functions specified in the functionality specification. Synthesis software programs use the functionality specification and constraints to produce a circuit design. The runtime required for synthesis software programs to produce a circuit design varies greatly depending on such factors as the speed of the processor on which the software program is operating, the complexity of the circuit design, and the difficulty of building a circuit that satisfies the specified functions and constraints. It is not uncommon, however, for a synthesis software program to take days, even weeks, to run to completion.  
           [0006]    One difficulty encountered in circuit design is that often the constraints are not precisely known at the start of the design period or may change during the design period. Sometimes, determining constraints is a part of the design process and requires a process of trial and error. During a trial and error process, the circuit designer begins with constraints that may be chosen randomly. The synthesis software is run using these constraints and the circuit designer manually evaluates the output. The circuit designer then refines the constraints and runs the synthesis software again.  
           [0007]    Some conventional systems have attempted to accelerate the trial and error process by partitioning the circuit into blocks and assigning block timing constraints to each block. Block timing constraints are often determined by dividing the timing constraint for the circuit by the number of blocks or based on gate level design data. This system, however, may not lead to the most optimized circuit because the restraints are imposed per block.  
           [0008]    Results from synthesis software can be very sensitive and a small change in the constraints may cause drastically different synthesis outcomes. It is necessary, therefore, to repeat this process numerous times to achieve the final circuit design. Sometimes the design process requires going back to a previous result and trying a different refinement or using a previous set of constraints with some modifications. If each iteration of a large, complex circuit design takes a few days to complete, the total time for circuit design becomes quite lengthy. Therefore, a need exists for improving the design of circuits in parallel.  
         SUMMARY OF THE INVENTION  
         [0009]    In accordance with the invention, methods, systems, and apparatus for generating a circuit receive functional specifications, including initial circuit constraints and generate a plurality of seed circuits, each seed circuit a copy of the functional specifications. The invention generates a plurality of variant constraints based on the initial circuit constraints. Each seed circuit and corresponding variant constraint is distributed to one of a plurality of processors, and, in parallel, a plurality of candidate circuits is generated. The output is a best candidate circuit design that represents gate-level design data and the corresponding best candidate circuit constraints that most closely matches the initial circuit constraints. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]    The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, serve to explain the advantages and principles of the invention. In the drawings,  
         [0011]    [0011]FIG. 1 is a block diagram of a computer system in which systems consistent with the present invention may be implemented;  
         [0012]    [0012]FIG. 2 is a block diagram of a system consistent with the present invention;  
         [0013]    [0013]FIGS. 3 a  and  3   b  are a flow diagram representing steps of a method for designing a circuit consistent with the present invention;  
         [0014]    [0014]FIG. 4 is a flow diagram showing a basic circuit; and  
         [0015]    [0015]FIG. 5 shows a basic circuit with multiple paths through point x. 
     
    
     DETAILED DESCRIPTION  
       [0016]    Reference will now be made in detail to an implementation of the present invention as illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings and the following description to refer to the same or like parts.  
         [0017]    A. Overview  
         [0018]    Systems and methods consistent with the present invention may allow the circuit designer to synthesize a circuit design in parallel. Multiple copies of the circuit design, or “seed circuits,” are created and distributed to a network of computers. From an initial constraint set, a family of constraint sets corresponding to the seed circuits is generated. Synthesis jobs comprising a seed circuit and a constraint set are dispatched to a network of computers and synthesized simultaneously. The plurality of synthesis results are used for the next iteration of circuit design.  
         [0019]    B. Architecture  
         [0020]    Methods and systems consistent with the present invention operate in distributed systems comprised of, for example, multiple homogenous or heterogenous machines operationally connected to form a network. An exemplary LAW OFFICES network for use with the present invention is shown in FIG. 1 and is designated by reference number  122 . Network  122  comprises one or more clients  102 ,  104 ,  106 ,  108  operatively connected to network link  120  by communication interfaces  112 ,  114 ,  116 , and  118 . In addition, network  122  includes a host  124  linked to network link  120 .  
         [0021]    Network link  120  typically provides data communication between one or more of clients  102 ,  104 ,  106 , and  108  and host  124  to data devices outside of network  122 . For example, network link  120  may provide a connection through network  122  to data equipment operated by an Internet Service Provider (ISP)  126 . ISP  126  in turn provides data communication services through the Internet  128  to server  130 . Network  122  and Internet  128  may use any one of electric, electromagnetic, or optical signals to carry digital data streams. The signals through the various networks and the signals on network link  120  are exemplary forms of carrier waves transporting the information.  
         [0022]    Clients  102 ,  104 ,  106 , and  108  can send and receive data, including program code, through network link  120  and communication interfaces  112 ,  114 ,  116 , and  118  to host  124  and server  130 . For example, server  130  transmits a request for an application program through Internet  128 , ISP  126 , and network  122  to client  102 ,  104 ,  106 , or  108  or host  124 . In accordance with one implementation, an application consistent with the present invention may be downloaded to client  102 ,  104 ,  106 , or  108 . The received code may be executed by a processor as it is received, and/or stored in storage device  210 , or other non-volatile storage for later execution. Application code in this form is one example of a carrier wave.  
         [0023]    Although clients  102 ,  104 ,  106 , and  108  are shown in FIG. 1 as being connectable to one server  130 , clients  102 ,  104 ,  106 , and  108  may establish connections to multiple hosts and server on Internet  128 . In addition, fewer or more clients may be used.  
         [0024]    [0024]FIG. 2 illustrates systems suitable for use with the present invention. Clients  102 ,  104 ,  106 ,  108 , and host  124  are conventional computers as shown in FIG. 2. For ease of explanation, however, the system in FIG. 2 is referred to only as client  102 . Client  102  comprises a bus  202  and a processor  204  coupled to bus  202  for processing information and executing application programs. Client  102  also comprises a main memory, such as a random access memory (RAM)  206  or other dynamic storage device, coupled to bus  202  for storing information and instructions to be executed by processor  204 . RAM  206  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  204 . Client  102  further comprises a read only memory (ROM)  208  or other static storage device coupled to bus  202  for storing static information and instructions for processor  204 . A storage device  210 , such as a magnetic disk or optical disk, is provided and coupled to bus  202  for storing information and instructions.  
         [0025]    Client  102  maybe coupled via bus  202  to a display  212 , such as a cathode ray tube (CRT), for displaying information to a computer user. An input device  214 , including alphanumeric and other keys, is coupled to bus  202  for communicating information and command selections to processor  204 . Another type of user input device is cursor control  216 , such as a mouse, a trackball or cursor direction keys for communicating direction information and command selections to processor  204  and for controlling cursor movement on display  212 . This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.  
         [0026]    Methods and systems consistent with the present invention may operate in a distributed environment as shown in FIG. 1. Consistent with one implementation, processor  204  of client  102 ,  104 ,  106 , or  108  executes one or more sequences of one or more instructions contained in main memory  206 . These instructions may include, for example, the steps of the program code associated with a circuit synthesis software program consistent with the present invention. Such instructions may be read into main memory  206  from another computer-readable medium, such as storage device  210 . Execution of the sequences of instructions contained in main memory  206  causes processor  204  to perform the process steps described herein. In an alternative implementation, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus implementations of the invention are not limited to any specific combination of hardware circuitry and software.  
         [0027]    The term “computer-readable medium” as used herein refers to any media that participates in providing instructions to processor  204  for execution. Such a medium may take many forms, including but not limited to non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device  210 . Volatile media includes dynamic memory, such as main memory  206 . Transmission media includes coaxial cables, copper wire, and fiber optics, including the wires that comprise bus  202 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.  
         [0028]    Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punch cards, papertape, any other physical medium with patterns of holes, a RAM, PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read.  
         [0029]    Various forms of computer-readable media may be involved in carrying one or more sequences of one or more instructions to processor  204  for execution. For example, the instructions may initially be carried on magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to client  102  can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector coupled to bus  202  can receive the data carried in the infra-red signal and place the data on bus  202 . Bus  202  carries the data to main memory  206 , from which processor  204  retrieves and executes the instructions. The instructions received by main memory  206  may optionally be stored on storage device  210  either before or after execution by processor  204 .  
         [0030]    Client  102  also comprises a communication interface  218  coupled to bus  202 . Communication interface  218  provides a two-way data communication coupling to a network link connects client  102  to a network, such as network  122  shown in FIG. 1. For example, communication interface  218  may be an integrated services digital network (ISDN) card, cable modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface  218  may be a local area network (LAN) card that provides a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface  218  sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.  
         [0031]    C. Method  
         [0032]    [0032]FIGS. 3 a  and  3   b  are flowcharts showing steps of a method consistent with the present invention. To begin, a design D is copied to produce a set of N seed circuits comprising the set {D i } (step  305 ). A seed circuit is a copy of the entire circuit represented by design D.  
         [0033]    The total circuit design, D, may be submitted to the synthesis software and run without using constraints (step  308 ). The process of running synthesis software without restraints is often referred to as “quick-synthesis.” Synthesis software programs run without constraints typically produce a result in a very short period of time. The synthesis job on the total circuit design produces an initial representation of a circuit showing a connection of gates, Path lengths calculated for an initial representation may be used to calculate initial constraints.  
         [0034]    Initial constraints for each seed circuit are obtained using system specification C (step  310 ). System specification C contains various constraints for the total circuit that will be designed according to design D. Constraints are typically defined in terms of ranges or minimum and maximum values for such variables as physical area or maximum delay of the circuit. Although many different types of constraints may be computed, most common is the maximum delay through a circuit path. FIG. 4 shows a basic circuit diagram. A “path” from input a to output b is defined to be a sequence of gates such that one of the inputs of the first gate in the sequence is connected to a and one of the outputs of the last gate in the sequence is connected to b. Path length is the sum of the gate delays along the path. For example, in the circuit shown in FIG. 4, the path length of a path from input a to output b as indicated by a heavier line may be 5 nanoseconds. When referring to the specification, the maximum delay desired by the circuit designer for a specific path is referred as the required time. Once the circuit is implemented, the actual delay time over a specific path is called the “arrival time.” The difference between the required time desired by the designer and the actual arrival time achieved in the final implementation of the circuit is referred to as the “slack.” 
         [0035]    The following example is described using required times as the constraints for the circuit design. To obtain initial constraint sets for the required times for each seed circuit, the required time for the total circuit specified by system specification C is uniformly distributed into a set of N different constraint sets, one for each seed circuit (step  320 ). For example, if maximum desired delay is 1 nanosecond and N equals 10, the constraint sets may be uniformly distributed over the range {0.5, 1.5}, such as, for example, [0.5, 0.6], [0.6, 0.7], . . . [1.4, 1.5].  
         [0036]    In some embodiments of the invention, the N constraint sets may be calculated as a function of maximum delay, for example, the amount of perturbation applied to the constraints to obtain constraint ranges may be described using the following formula. Let U x  be a percentage range over which constraints at output x can vary. Then, the range of the required time for output X with initial required time R x  is given by [R1 x , R2 x ], where:  
           R 1 x   =R   x −( L   1 /( L   1   +L 2))* U   x   *R   x ,  
         and  
           R 2 x   =R   x +( L   2 /( L   1   +L   2 ))* U   x   *R   x.    
         [0037]    L 1  is the maximum delay of all paths in a seed circuit whose output is X. L 2  is the maximum delay of all paths in a seed circuit whose input is X. R 1   x  forms the lower limit of the constraint range, I, and R2x forms the upper limit of the constraint range, I.  
         [0038]    The perturbation set for a seed circuit with constraint set C i =R x1 , R x2 , R xn  , . . . is formed by selecting values from the set formed by the Cartesian product I 1 ×I 2 × . . . ×I n , where I i  is the perturbation interval (R1 xi , R2 xi ) for the ith seed circuit. The Cartesian product of sets A and B is defined as A×B={(a,b)|a εA         bεB}. The synthesis software may choose values throughout the constraint set C i  according to any number of methods well understood in the art, such as using uniform or Gaussian distribution methods. In the uniform distribution method, for example, points are chosen that are uniformly distributed throughout the interval. In a Gaussian distribution method, the points are chosen according to a Gaussian distribution.  
         [0039]    A synthesis job is created for each seed circuit by associating each seed circuit with a corresponding constraint range to form a synthesis job (step  330 ). Each synthesis job is dispatched to a processor (step  340 ). If there are more seed circuit/constraint pairs to be dispatched (step  350 ), the process moves to the next seed circuit (step  355 ) and continues from step  330 . Once all of the constraints are distributed, the synthesis jobs are processed in parallel (step  360 ) to obtain a set of results R(C) (step  370 ). The set of results is stored in a data base (step  375 ) and a “best” result from the set is selected (step  380 ). In the timing constraint example, the “best” result would be the design that produces the shortest delay.  
         [0040]    If the best result is determined to produce a circuit design that is within acceptable limitations (step  390 ), the process terminates. If the circuit design needs to be further refined, the best result may be used as a seed for another iteration of synthesis jobs (step  395 ). The best result may be, for example, the result that produced the fastest runtime or the circuit that most closely approximates the functional specification. The best result is then used as the constraint seed (step  310 ) and the process continued from step  320 .  
         [0041]    D. Conclusion  
         [0042]    As described in detail above, methods and apparatus consistent with the present invention allow a user to design a circuit in parallel by distributing seed circuits of the overall design and constraints sets from a family of constraints sets over a network of computers. The foregoing description of an implementation of the invention has been presented for purposes of illustration and description. For example, the described implementation includes software but the present invention may be implemented as a combination of hardware and software or in hardware alone. The scope of the invention is therefore defined by the claims and their equivalents.