Abstract:
The optimal configuration of a number of optional pipeline stages within the data paths of systems-on-chip is determined by application of a solver. The solver includes variables such as: the placement of modules physically within the floorplan of the chip; the signal propagation time; the logic gate switching time; the arrival time, after a clock edge, of a signal at each module port; the arrival time at each pipeline stage; and the Boolean value of the state of activation of each optional pipeline stage. The optimal configuration ensures that a timing constraint is met, if possible, with the lowest possible cost of pipeline stages.

Description:
TECHNICAL FIELD 
       [0001]    This invention is in the field of semiconductor chip design. More specifically, this invention relates to the design of logic to achieve timing closure. 
       BACKGROUND 
       [0002]    By dividing a process into steps, and performing the steps simultaneously on different data, the frequency at which the processing system can operate depends on the length of time to complete its slowest step. The same process performed with a shorter “slowest step” can be performed faster. Designing shorter steps in order to achieve higher speed generally requires creating more steps. More steps, given imperfect balancing of the length of steps, require more time to generate the resulting output from any particular input. 
         [0003]    Processes are often referred to as pipelines. Storage devices between steps are referred to as pipeline stages. The number of steps in a processing system is referred to as the pipeline depth. Within a system-on-chip (SoC) data moves through a pipeline no faster than one stage per clock cycle. Therefore, the number of stages determines the number of clock cycles for each input datum to be fully processed. Such time is often referred to as latency. Longer latency due to pipeline stages is undesirable, but the faster clock frequency due to pipeline stages is desirable. Designing an optimal number of pipeline stages requires a trade-off between clock frequency and cycles of latency. 
         [0004]    Within the design of a data processing chip it is not immediately clear how to optimally apply pipelining. The conventional method of designing a pipeline that works is an iterative process of experimentation. It is time consuming. Furthermore, it rarely results in an optimal design. 
         [0005]    The problem is further complicated when the physical layout of the chip is considered. The length of time for data to propagate from a point of production to a point of consumption depends on the distance and the average propagation rate through the wires between those points. Conventionally, the physical layout is considered at a later stage in the chip design process than the decisions about pipelining. To avoid unexpected problems achieving the desired clock frequency during physical design, pipeline stages are placed at smaller increments within the processing logic, thereby leaving extra time for data to propagate between points if they happen to be distant in the physical design. This over-design of pipeline stages costs area, power consumption, and especially latency. Therefore, what is needed is a system and method to automatically determine optional pipeline stages in order to meet clock frequency constraints. 
       SUMMARY 
       [0006]    The disclosed invention is a method and electronic design system to automatically activate optional pipeline stages in order to meet clock frequency constraints. In alternative embodiments of the invention, the location of data processing modules within chips is determined in conjunction with the configuration of pipeline stages. 
     
    
     
       DESCRIPTION OF DRAWINGS 
         [0007]      FIG. 1  illustrates a module, as in SoCs, with pipeline stages. 
           [0008]      FIG. 2  illustrates a path between pipeline stages, the path occurring in three modules. 
           [0009]      FIG. 3  illustrates a sequence of optional pipeline stages in a path, a subset of which is enabled. 
           [0010]      FIG. 4  illustrates signal propagation times through a path. 
           [0011]      FIG. 5  illustrates two sequences of optional pipeline stages on correlated paths, a subset of which is enabled. 
           [0012]      FIG. 6  illustrates signal propagation times through a correlated path. 
       
    
    
     DETAILED DESCRIPTION 
       [0013]    This invention relies on an ability to determine a number of data path connections within the logic of a system on a chip or system-on-chip (SoC) where a pipeline stage can be inserted. A pipeline stage is an array of flip-flops (flops) that stores at least a word of data. It generally has the benefit of dividing the signal propagation delay through the path into two shorter paths such that a shorter clock period (a higher clock frequency) can be used to synchronize the SoC. Such data path connections are known as optional pipeline stages. The chip can function correctly with or without each pipeline stage. When present, the optional pipeline stage is said to be activated. A set of activated optional pipeline stages is known as a configuration. 
         [0014]      FIG. 1  illustrates module  100 , comprising a first pipeline stage  102  and second pipeline stage  104 . Pipeline stages, each comprising parallel flip-flops, are depicted with the conventional symbol of a flip-flop. Lines represent paths through logic elements, the logic elements are not shown. Path  120  connects input  106  to pipeline stage  102 . Path  130  connects pipeline stage  102  to pipeline stage  104 . Path  140  connects pipeline stage  104  to output  108 . Path  150  connects input  110  to output  112 . Path  160  connects input  110  to pipeline stage  104  through logic shared with path  130  and  150 . Path  170  connects pipeline stage  102  to output  112  through logic shared with path  130  and  150 . 
         [0015]    This illustrates the four types of path segments on which signals, the time of which can be calculated, can propagate within a module: 
         [0016]    input to pipeline stage (paths  120  and  160 ); 
         [0017]    pipeline stage to pipeline stage (path  130 ); 
         [0018]    pipeline stage to output (paths  140  and  170 ); 
         [0019]    input to output (path  150 ); 
         [0020]      FIG. 2  illustrates a full path between a first pipeline stage  200  and a second pipeline stage  202 . The path occurs in three interconnected modules  210 ,  220 , and  230 . The full path comprises a pipeline stage to output path segment from pipeline stage  200  to connection  240 , an input to output path segment from connection  240  to connection  250 , and an input to pipeline stage path segment from connection  250  to pipeline stage  202 . 
         [0021]    Every flop, and therefore every pipe stage, has a unit cost in terms of silicon area. It also has a cost in terms of power consumption as a result of the power used to drive flops switching current and power used to toggle the clock tree. The cost is approximately proportional to the number of flops, which is generally approximately proportional to the width of the data in the data path. 
         [0022]    In practice, chips are designed with the underlying constraints of target clock frequencies in different parts of the chip and a target cell library for a particular CMOS process node. 
         [0023]    Most SoCs are designed as an interconnection of modules. Each module has a number of optional pipeline stages, a number of inputs, a number of outputs, and a number of required registers. Timing within the module from flop to flop, input to flop, flop to output, and input to output can be determined for the module alone. The flop to output and input to flop delay can be added together where there is connectivity between modules in the SoC. Registers comprise flops as do optional pipeline stages when activated. 
         [0024]    Some SoC designs contain non-sythesizable logic blocks, such as memory arrays or register files. With regard to delay analysis, those blocks may be described with the same formalism as synthesized gates. Their interface ports are usually comparable to register ports. 
         [0025]      FIG. 3  illustrates a sequence of pipeline stages. Pipeline stages are depicted as triangles for simplicity. Each optional pipeline stage is shown in white and can be activated or not. Fixed pipeline stages are shown in grey. The full path occurs in modules  320 ,  340 , and  360 . The path begins at pipeline stage  302 , traverses optional pipeline stages  304 ,  306 , and  308 , and ends at pipeline stage  310 . Path segment X is from pipeline stage  302  to pipeline stage  304 . Path segment Y is from pipeline stage  304  to pipeline stage  306 . Path segment Z is from pipeline stage  306  to pipeline stage  308 . Path segment Q is from pipeline stage  308  to pipeline stage  310 . 
         [0026]    Timelines of signal propagation delays are shown in  FIG. 4 . Clock cycle  400  has duration T CLK .  FIG. 3  path segments X, Y, Z, and Q take  FIG. 4  time T X , T Y , T Z , and T Q  time, respectively. Signal propagation time from  FIG. 3  register  302  to optional pipeline stage  308 , consisting of path segments X, Y, and Z, takes T X  plus T Y  plus T Z  propagation time, which is shown in  FIG. 4 . The cumulative time exceeds the duration of T CLK . Activating optional pipeline stage  304  would break the long timing path. The timing path from pipeline stage  304  through T Y , T Z , and T Q  also violates the T CLK  timing constraint. Activating pipeline stage  308  would resolve that violation. However, activating pipeline stage  306  would resolve both timing violations with less cost. 
         [0027]    The best configuration of pipeline stages is less clear when multiple paths pass through optional pipeline stages. In accordance with various aspects of the present invention,  FIG. 5  illustrates the sequence of  FIG. 3  with an additional sequence of optional pipeline stages that share a path. The second path begins at register  514 , traverses optional pipeline stages  516 ,  304 ,  306 , and  308 , and ends at register  310 . Path segment A is from pipeline stage  514  to pipeline stage  516 . Path segment B is from pipeline stage  516  to pipeline stage  304 . 
         [0028]    Timelines of signal propagation delays are shown in  FIG. 6 , in accordance with the various aspects of the present invention. As in  FIG. 4 , clock cycle  400  has duration T CLK .  FIG. 5  path segment A signal propagation takes  FIG. 6  T A  time.  FIG. 5  path segment B signal propagation takes  FIG. 6  T B  time. Signal propagation time from  FIG. 5  pipeline stage  514  to optional pipeline stage  306 , consisting of path segments A, B, and Y takes  FIG. 6  T A , T B , T Y  propagation time. The cumulative time of which exceeds the duration of T CLK . The cumulative time of T X  and T Y  is less than the duration of T CLK . Therefore, activating pipeline stage  304  resolves the timing violation, but activating pipeline stage  306  does not. 
         [0029]    The activation or deactivation of each pipeline stage affects all paths through it, and therefore all other pipeline stages traversed by all of those paths and so forth. Typical SoC designs have thousands of paths sharing each of hundreds of optional pipeline stages. 
         [0030]    One approach that designers use is an iterative process of experimentation to determine a best configuration of optional pipeline stages. A method is to begin with no pipeline stages then repeatedly synthesize the design, analyze timing, and add a pipeline stage at the point in the logic of the slowest critical path. 
         [0031]    An experienced designer considers all factors and creates an initial configuration that is more likely to meet the constraints. This approach will require fewer iterations and thereby tend to add fewer unnecessary pipeline stages. However, if the initial configuration is too pessimistic then this approach will still have unnecessary pipeline stages. 
         [0032]    Another method, in accordance with other aspects of the present invention, would iterate automatically, considering where there is extra slack and accordingly moving pipeline stages farther apart in the logic paths. That will cause paths between other pipeline stages to be shortened, which will cause other pipeline stages to be moved. In this case, even small changes potentially cause changes in many other optional pipeline stages of the chip and so a large number of iterations would still be required to approach an optimal configuration. 
       Logic Synthesizers 
       [0033]    System-on-chip designers commonly use logic synthesizers. Those tools take a logic behavior as input, and produce as an output an arrangement of logical gates that realizes the behavior and meets maximum long path requirements, on a given process node and a target clock frequency. Different configurations of a module with regard to pipeline stages have different behaviors; a logic synthesizer is not able to select a configuration: it tries and optimizes the one it has been given as an input. 
         [0034]    The implementation of a logic synthesizer consists of two phases. In a first phase, called mapping, the behavior is translated into an arrangement of gates. In a second iterative phase, called timing optimization, parts of the arrangement are modified to shorten the longest path, while keeping the same behavior. Many timing optimization techniques have been described and all imply using more silicon area and more power. The stronger the timing constraints are, the higher the impact on area and power are expected to be, until the logic synthesizers fails to find a solution to the problem. The optimization is always limited by the longest path: one path longer than required is enough to make the logic synthesizer fail. 
         [0035]    Finding the optimal configuration would basically require all configurations to be separately synthesized. The present invention determines, for given constraints of target clock frequency and CMOS process node, without iteration, an optional pipeline stage configuration that, when passed the logic synthesizer mapping phase, presents an even timing optimization problem. The timing optimization is then more likely to converge, in a shorter time frame, and with less area and/or power impact. 
       Linear Equations 
       [0036]    In accordance with the various aspects of the present invention, embodiments of the invention use a mixed integer programming linear equation solver to compute an optimized configuration of optional pipeline stages. 
         [0037]    Full system timing can be broken down into smaller tasks by analyzing individual module timings. This makes the full system analysis simpler, as only the number of optional pipeline stages within a module need be considered at a time when calculating timing. Determining the optimal configuration of a module depends on calculating timing with every combination of optional pipelines stages activated. This would require 2 N  calculations, where N is the number of optional pipeline stages within the module. In practice, timing calculated with each optional pipeline stage activated alone gives a nearly optimal guess of the best configuration. This method requires only N+1 calculations. In accordance with the disclosure of the present invention as related to the various embodiments, this method is used to improve run time. 
         [0038]    Timing is calculated within each module by running a synthesis process on a configuration of a model of each instantiated module. The synthesis does not generate a netlist of standard cells, but does generate a delay estimate of timing arcs between flip-flops, inputs and outputs. 
         [0039]    In accordance with various aspects of the present invention, the following steps are performed:
       1. Perform a synthesizer mapping phase on each module, once with each optional pipeline stage activated alone and once with no pipeline stage, to generate a timing and area estimate for the module.   2. Build timing arrays of the synthesized timing values for each pipeline stage; with an array for each of input to flop, flop to flop, flop to output, and input to output timing. Sort each array of pipe stages in order of timings.   3. Use a linear programming solver such as the open source Ipsolve mixed-integer linear programming solver.       
 
         [0043]    A resulting optimal configuration of optional pipeline stages is represented as a vector of Boolean values that is the lowest cost solution to a system of linear equations. A linear problem is a set of inequalities of a set of variables. Lpsolve is used to find an optimal solution vector that meets all timing constraints, if possible. 
         [0044]    The variables include: 
         [0045]    1. the arrival time of signals per module port and 
         [0046]    2. Boolean state of activation per optional pipeline stage. 
         [0047]    Inequalities for the solver include: 
         [0048]    1. For each module output port: 
         [0049]    arrival time≧clock-to-output delay of the module; and 
         [0050]    arrival time≧input port arrival time+input to output delay. 
         [0051]    2. For each input port connected to each activated pipeline stage: 
         [0052]    input port arrival time+input port to flip-flop delay clock period. 
         [0053]    Within modules, input port to output port, input port to pipe stage, and pipe stage to output port connectivity and a timing estimate for each connection is known from the models of the configuration of each module instance. The timing, as well as an area estimation, is derived from a synthesis algorithm on the instances of configured modules. The synthesis algorithm is generic across process technologies. 
         [0054]    The cost function to be minimized is the sum of the cost of each activated pipeline stage. The cost of each activated pipeline stage is determined by the area estimation. In another embodiment cost is a function of area estimation and power consumption. 
         [0055]      FIG. 7  shows a process flow diagram in accordance with one aspect of the present invention with an embodiment of automatic pipeline stage insertion. The considerations of pipeline stage cost, connectivity, module location, module timing as determined by a synthesis process, and timing constraints are input to the solver. The solver outputs an optimal configuration if one can be found that meets the criteria of all inequalities. 
         [0056]    In accordance with another aspect of the present invention, another embodiment considers the data processing latency introduced by pipeline stages. Forward pipeline stages are ones that store datapath signals in flops such that no forward-going combinatorial paths traverse the pipeline stage. That includes the data path as well as sideband signals and forward-going flow control signals. Backward pipeline stages store datapath signals in flops, thereby having a similar cost as forward-going pipeline stage, but have datapath multiplexing and other forward-going combinatorial logic paths. Backward pipeline stages ensure that no combinatorial paths are present on backward-going flow control signals. A key difference is that forward pipeline stages add a cycle of latency to transactions and backward pipeline stages do not. If a combinatorial logic path may be broken on both forward-going and backward-going signals, it is generally preferable to break the path with a backward pipe stage. 
         [0057]    Desired maximum data processing latency between any point of data production and point of data consumption is a constraint on the solver. The embodiment includes the additional variable of a target latency per initiator-target connectivity. An additional inequality is, that for each connection between initiator and target, the number of activated optional pipeline stages in path latency constraint. 
         [0058]    In accordance with another aspect of the present invention, another embodiment of the invention considers not just synthesized timing within modules, but the time required for the propagation of signals between modules. The locations of modules within the chip floorplan are used, a simple table of their relative distances is used, or both are used with a function between delay and distance. Module locations are represented in a simplified format, with a single x and y coordinate. In accordance with one aspect of the present invention, in one embodiment the function is a simple delay proportional to the Manhattan distance between modules. In accordance with another aspect of the present invention, in another embodiment the delay is a super-linear function of distance in order to account for vias, obstructions, and varying propagation times on different metal layers. Output port to input port connectivity between modules is known from the SoC architecture level netlist. Output port to input port delay is estimated by a signal propagation speed multiplied by the distance. 
         [0059]    The application of a linear equation solver to the configuration of optional pipeline stages is extended from that previously described. Additional variables include: 
         [0060]    3. x axis location per module; 
         [0061]    4. y axis location per module; 
         [0062]    5. distance per connected pair of modules; 
         [0063]    Additional inequalities include: 
         [0064]    3. For each pair of connected module  1  and module  2 : 
         [0065]    distance≧x 1 −x 2 +y 1 −y 2 ; 
         [0066]    distance≧x 1 −x 2 +y 2 −y 1 ; 
         [0067]    distance≧x 2 −x 1 +y 1 −y2; and 
         [0068]    distance≧x 2 −x 1 +y 2 −y 1 . 
         [0069]    4. For each module input port: 
         [0070]    arrival time≧arrival time at a connected output port+distance*signal propagation rate. 
         [0071]    A resulting optimal configuration of optional pipeline stages is represented as a vector of Boolean values along with arrays of x and y coordinates for each module. 
         [0072]    A network-on-chip is a component within the design of an SoC. A network-on-chip, designed modularly, lends itself to presenting data path connections where a pipeline stage can be simply inserted without changing the correctness of chip functionality. The logic and wires of a network-ok-chip span relatively long distance. As a result, some embodiments of this invention are applied particularly to a network-on-chip. 
         [0073]    The various aspects of the present invention may be implemented in software, hardware, application logic, or a combination of software, hardware, and application logic. The software, application logic and/or hardware may reside on a server, an electronic device, or a service. If desired, part of the software, application logic and/or hardware may reside on an electronic device, part of the software, application logic and/or hardware may reside on a server. 
         [0074]    While the present invention has been described with reference to the specific applications thereof, it should be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the true spirit and scope of the invention. In addition, many modifications may be made to adapt a particular situation, material, composition of matter, process, process step or steps, to the objective, spirit and scope of the present invention. All such modifications are intended to be within the scope of the claims appended hereto. 
         [0075]    The foregoing disclosures and statements are illustrative only of the present invention, and are not intended to limit or define the scope of the present invention. The above description is intended to be illustrative, and not restrictive. Although the examples given include many specificities, they are intended as illustrative of only certain possible applications of the present invention. The examples given should only be interpreted as illustrations of some of the applications of the present invention, and the full scope of the present invention should be determined by the appended claims and their legal equivalents. Those skilled in the art will appreciate that various adaptations and modifications of the just-described applications can be configured without departing from the scope and spirit of the present invention. Therefore, it is to be understood that the present invention may be practiced other than as specifically described herein. The scope of the present invention as disclosed and claimed should, therefore, be determined with reference to the knowledge of one skilled in the art and in light of the disclosures presented above. 
         [0076]    Although various aspects of the present invention are set out in the independent claims, other aspects of the invention comprise any combination of the features from the described embodiments and/or the dependent claims with the features of the independent claims, and not the solely the combination explicitly set out in the claims. 
         [0077]    Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Any methods and materials similar or equivalent to those described herein can also be used in the practice or testing of the present invention. 
         [0078]    All publications and patents cited in this specification are herein incorporated by reference as if each individual publication or patent were specifically and individually indicated to be incorporated by reference and are incorporated herein by reference to disclose and describe the methods and/or materials in connection with which the publications are cited. The citation of any publication is for its disclosure prior to the filing date and should not be construed as an admission that the present invention is not entitled to antedate such publication by virtue of prior invention. Further, the dates of publication provided may be different from the actual publication dates which may need to be independently confirmed. 
         [0079]    It is noted that, as used herein and in the appended claims, the singular forms “a”, “an”, and “the” include plural referents unless the context clearly dictates otherwise. It is further noted that the claims may be drafted to exclude any optional element. As such, this statement is intended to serve as antecedent basis for use of such exclusive terminology as “solely,” “only” and the like in connection with the recitation of claim elements, or use of a “negative” limitation.