Abstract Practical Experiences with Standard-Cell Based Datapath Design Tools Do We Really
- 格式：pdf
- 大小：105.01 KB
- 文档页数：6
Practical Experiences withStandard-Cell Based Datapath Design ToolsDo We Really Need Regular Layouts?Paolo Ienne and Alexander GrießingSiemens AG,HL LIB GCPostfach801709,D–81617M¨u nchenPaolo.Ienne,Alexander.Griessing@hl.siemens.de AbstractCommercial tools for standard-cell based datapath design are hereclassed according to designflows,and the advantages of each classare discussed with the results of two test circuits.Algorithmic gen-eration of netlists and of relative cell placement can help reducingarea but,contrary to common belief,appears often detrimental tospeed.Extraction of regularity from synthesized netlists is difficultand requires counterproductive simplifications to the synthesis pro-cess.Most promising are synthesis tools which can generate place-ment data;yet,no tool of this class appears ready today.1IntroductionInformally,datapaths are circuits where the same or similar logicis applied to several bits of a bus.These signals get processed inparallel by complex operators such as adders,multipliers,or simplyby multiplexers,bitwise logic gates,etc.Typically the same pieceof logic is repeated—almost unchanged—for all bits,or an operandgets implemented as a regular array structure(e.g.,multipliers)[6].Traditional place&route(P&R)tools are incapable to use thisregularity to produce more compact and higher performance results.Datapath design tools are programs which in different ways helpto exploit regularity:they may replace standard P&R tools—andto a certain extend preceding tools in the designflow—altogetherand use some special library of datapath-cells,or they can simplyproduce placement constraints for traditional P&R tools.Generally,datapath tools are supposed to help designers inachieving smaller and faster circuits.The obtained implementa-tions are smaller because of the regular placement;they are alsosupposed to be faster because of several reasons.Thefirst argu-ment for the speed improvement is that with a regular arrangementof the basic cells,wiring will be reduced to a minimum.A secondargument is the common belief that by carefully generating a netlistone can easily improve on synthesis results.A third and differentargument says that by integrating in a datapath tool everything fromsynthesis down to layout generation,the more accurate timing in-formation available at synthesis can be used to further improve thedesign.Finally,datapath tools could also improve controllabilityover the design process(e.g.,clock skew,matching bus parasitics).Generation ExtractionSynthesisFigure1.Basic designflow for the three main types of commercial datapath tools.Similarly,the output of the various tools is also pretty different: some tools have a dedicated placement engine integrated(or are themselves part of P&R tools)and produce afinal layout.Others just produce a placement suggestion for all or some of the cells,and this can be used in the P&R tool of user’s choice(when supported) to complete the placement and route the design.Another distinctive feature of the tools is the ability to handle mixed datapath and control logic.Some tools can separate among control logic and datapath components automatically,while others require as an input the datapath part completely independent from any control logic,leaving the partitioning of the design to the user.2.1Types of commercial datapath toolsThe available datapath tools can be fundamentally classed in the three categories represented in Figure1:“Generation”tools.The simplest tools are those more closely imitating a manual datapath design:from a list of dat-apath operators belonging to a library,the individual cell-level netlists are generated algorithmically.This algorithmic gen-eration process is different from synthesis in that one wants to produce the mentioned netlist and a database with the de-sired relative placement information of the cells at the same time.In the simplest example,generation of an-bit register requires instantiation of registers(with trivial connections) and assignment of each register to the corresponding bit-slice of the datapath.A second part of the tool usuallyfixes the cell placement obeying the specified relative placement.“Extraction”tools.An approach which preserves as much as possible of the standardflow consists in extracting relative placement information from the results of normal synthesis.The ways this extraction from thefinal netlist is performed are usually not documented and essentially consist in a combina-tion of techniques such as:(1)exploit levels of hierarchy in the netlist,(2)look for bus names,(3)look for telling instance name patterns,(4)look for identical cells sharing control sig-nals,(5)obtain from the user hints on the“average”number of bits,and perhaps others.Clearly the possibility of using a normally synthesized netlist depends very much on the actual regularity of the design after synthesis;this implies that the synthesis process may have to be performed following some guidelines to maximize the amount of regularity available at the end.“Synthesis”tools.The most complex tools are special syn-thesizers dedicated to datapath designs,which produce from an HDL description the placement information together with the netlist.The tools of this category are potentially the most versatile since their scope spans over most of the designflow.These are the only ones which can easily profit from a more accurate modeling of the datapath components:during syn-thesis,an accurate wiring model can be chosen for each sub-design or even for each wire thanks to the available placement data.The potential weakness of these tools may be the in-ability to leverage the state-of-the-art synthesis capabilities or placement algorithms from other traditional tools.The tools evaluated in the present research explore all the three dif-ferent categories.3Evaluation resultsIn this section,the main test circuit is described and the relevant results reported.The results of the test case are supplemented by a discussion of the implementation of16-bit multipliers with different techniques which throw additional insight into the difficulties of competing with synthesis techniques.Total Cell AreaC only Synth.STA@66MHz(mm)(mm)(%)83 %84%2.1290 %91%1.86(C)DP component generatorsTraditional synthesis toolTraditional P&R0.808%0.573%71(D)Traditional synthesis toolDP extraction toolTraditional P&R0.956%0.639%67(E)DP synthesis tool(No routing)(0.686)%(0.640)%(93)100 MHz 9080706050403020Figure 2.Evolution of speed after each design step of imple-mentations (A),(B),and (C).by two experiences.The first concerns the generation of complex and timing critical blocks,such as multipliers.It appears that it is extremely hard to compete with the synthesis results simply by generating—however carefully—a netlist of standard cells:all the generated multipliers which were planned to replace the synthe-sized one in implementation (B)turned out to be slower and there-fore not worth substituting.The important fact is that when these generated netlists have been re-synthesized in the synthesis tool,the timing has improved tangibly over the standard implementation of the synthesizer.This fact indicates that the intrinsic quality of the generated netlist is good,but generation alone cannot compete with synthesis.Since the regularity and the placement information get completely disrupted during re-synthesis,implementation (B)con-tains a synthesized multiplier traditionally placed by the P&R tool.Full details on the multiplier speed will be reported in Section 3.3.The second experience indicating the importance for timing op-timization of a synthesizer even in a generation-based flow is rep-resented by implementation (C).This result has been produced by re-synthesizing the netlist used for implementation (B):the speed of the design improves further—about 15–20%better than the sim-ple synthesis of implementation (A).However,as in the case of the mentioned multipliers,the regularity is lost and the placement is therefore performed by a traditional P&R tool (with the same area penalty as the reference implementation).Synthesis,generation,or generation plus synthesis?The results of Table 1and the results on the multipliers discussed in the next section seem to indicate that synthesis is today an almost essential step in a cell-based design flow to get the best performance from a given cell library.Figure 2highlights the contributions on speed of the different de-sign steps for implementations (A),(B),and (C).It visually shows that the generation of simple components (multiplexers,registers,etc.)followed by a driver strength re-optimization leads to better timing results than direct synthesis (+8%).However,it also shows that a complete re-synthesis step after generation has a tangible im-pact,bringing the advantage over direct synthesis to +15%.It is also interesting to notice that apparently the techniques used for implementation (B)do not have a visible impact on wiring de-lay.Implementations (A)and (C)are after placement only slightly slower or faster than the pre-placement calculation of the synthesis tool:implementation (B)has a behavior which is clearlysimilar.0.80 mm 0.750.700.650.600.550.500.450.402Figure 3.Evolution of area after each design step of implemen-tations (A),(B),and (C).(One possible reason not to observe any intrinsic advantage of the regular layout is perhaps the fact that a large part of the design is still conventionally placed.)Figure 3presents a similar picture about the area contributions of the different implementation steps.Generation and synthesis look quite equivalent at the netlist stage,but the whole advantage of the regular placement of implementation (B)is now apparent:the rout-ing overhead of this implementation is about one third of the one of implementations (A)and (C).It is also evident how the fastest implementation (C)is achieved at the expenses of a very large area (both because of large cell area and of irregular placement).Extraction of the regularity from the synthesized netlist.With the good results achieved by synthesis,it is particularly in-teresting to see what extraction tools can do to leverage synthesis capabilities.Implementation (D)is the best result of a series of it-erations with the only tested “extraction”tool.Clearly,extracting regularity from the final synthesized netlist is not an easy task.It is not easy because the best possible optimizations in the synthe-sis tool apparently destroy so much of the circuit regularity that the netlist gets useless for the tool.If,on the other hand,one tries to retain the regularity by stopping the optimization process slightly earlier,one can get better placement results (about 10–15%more density)but with a much larger cell area (up to 40%more)which basically offsets the advantage.In many cases the design is also slower.Implementation (D)represents the fastest design achieved.A tangible penalty on power consumption can be observed.Datapath synthesis.With synthesis achieving very good re-sults and post-synthesis extraction being limited in its possibilities,datapath synthesis appears as promising.Indeed,implementation (E)seems to indicate that direct synthesis in a datapath-aware tool can lead to good results.Unfortunately this implementation was never routed because the tool was in a preliminary version,and therefore results should be considered only indicative.Yet,some preliminary placements produced by the tool appeared qualitatively interesting;in a way,these indicative results support the view that merging the regularity extraction process with synthesis leads to the best solution.In the next section,the optimistic (E)timing results will be given some credibility.Min Max Min118 %8.51%128%7.80%(B)Custom Generators(Booth encoding,optimized adder)Synthesis tool(re-optimization)—0.107%(Bbis)Custom Generators(Booth encoding,optimized adder)Synthesis tool(full re-synthesis)0.164%0.156%——106%9.42%136%7.33%143%6.97%(D)Custom Generators(no Booth enc.,standard adder)Synthesis tool(re-optimization)—0.127%(Dbis)Custom Generators(no Booth enc.,standard adder)Synthesis tool(full re-synthesis)—0.192%parison of different multipliers obtained by synthesis,by generation,and by a combination of both techniques.3.3Sixteen-bit multipliersIn the previous section,it has been mentioned that the best gener-ated implementation(B)contains a synthesized multiplier.Indeed, several multiplier architectures have been explored with the purpose of including a generated multiplier made of regularly tiled standard cells.Table2shows the results of the most interesting multipli-ers achieved,all using the same standard cell library in the same technology.Thefirst two pairs of columns report the maximum frequency and the critical path delay for each implementation.The two pairs contain the post-layout measurements after parasitic re-sistance and capacitance extraction and the pre-layout estimation in the synthesis tool,respectively.The remaining columns indicate the total area of the implementation and the area of the cells alone. Power consumption has been measured for all the multipliers whose layout has been completed—multipliers(A),(Bbis),and (Cbis).The measured power consumption is—predictably—almost the same for all designs(the highest measured value is only about 3%more than the lowest value).This seems to reflect the fact that thefinal optimization technique for all the described multipliers is equivalent.Satisfactory P&R results for the multiplier alone.Due to the globally poor generation results,no regular placement has been attempted,although for some of the multipliers tiling informa-tions had been produced during generation.(The techniques origi-nally developed to prepare relative placement information had been abandoned in the current of the experiments,when it has been clear that a regular placement could not lead to a tangible advantage.) The core area utilization after standard P&R is in all cases95%.Several generation techniques explored.Multiplier(A) is the standard implementation of the synthesis tool:it is the refer-ence implementation and the one used in most designs of the pre-vious section.The other multipliers(some not shown on the table) have been generated combining the following elements:(1)Partial product generation is built in the customary using either a Booth-2 encoding scheme or no encoding[5].(2)Column compressors are generated with an algorithm similar to the one published in[4],and use the available timing information on the signals to add and on the standard cells to be used(several combinations have been tried).(3) Two types offinal adders have been used,either with afixed8-bit group carry-select/carry-lookahead structure or with a generalized structure optimized with a timing-driven algorithm which should represent an improvement over[1].Synthesis is very sensitive to a better architectural start-ing point.Two are the important results that can be evinced from Table2and emphasized in Figure4:(1)Even the best at-tempts to generate a fast multiplier do not achieve the speed of the synthesizer’s standard implementation(only multiplier(B)comes close to it with a tangible area advantage,but it should be remem-bered that all the generation techniques developed were aiming at delay reduction at any area cost).(2)Re-synthesizing the gener-ated netlists systematically reduces the critical path delay of ap-proximately20–30%.Rather consistently,the better the starting re-optimized netlist,the better is the re-synthesized result.How-ever,the speed improvement with re-synthesis usually reduces for the best starting netlists—for instance,%from(D)to(Dbis), but only%from(B)to(Bbis).0.19mm 0.180.170.160.150.140.130.120.1129.5ns98.587.576.5(B)(Bbis)(C)(Cbis)(D)(Dbis)Generation and Re-optimization(Re-) Synthesis for minimum delayStandard ImplementationRe-synthesisNo Encoding & StdAddRe-synthesis Booth-2 & StdAddFigure 4.Cell area and maximum delay (as predicted by the sythesis tool)for the studied multipliers.These results appear in agreement with those for the fastest im-plementations of the execution unit test case discussed in the pre-vious section.The experiments performed suggest that the logic synthesis and optimization capabilities of state-of-the-art synthe-sizers are essentially unbeatable:no manually or algorithmically generated example described in the experiments performed for the present research could not get a significative improvement by re-synthesis.(One may notice that all generated netlists seem interest-ing area-wise compared to (A);yet,it should be noted again that (1)all the generated netlists have been produced disregarding area and trying to minimize delay,and (2)multiplier (A)has also been syn-thesized for highest speed and is therefore not in direct competition with the generated netlists.)On the other hand,although manual or algorithmic generation alone hardly competes with synthesis—unless the design complex-ity is very low as in implementation (B)of Table 1—the starting logic mapping given to the synthesis tool appears to be highly de-terminant for the result.In fact,it seems that the initial mapping can be improved both for simple components (with no real “archi-tectural”issues)and for complex ones (such as multipliers,where a first timing-driven mapping proves its superiority).Impact of faster multipliers on the execution unit test case.It is useful to speculate on the impact of the present mul-tipliers on the maximum speed of the execution unit test case.The fastest implementation (B)of Table 1uses a 7.80ns multi-plier in a 10.36ns design (97MHz).Multiplier (Bbis)of Table 2has a maximum delay of 6.60ns.Simple calculations suggest that the maximum achievable speed for the execution unit test case is about 110MHz.Interestingly,this frequency is higher than the pre-dicted frequency for the implementation with a datapath synthesizer (104MHz)and adds to the predicted value some credibility.Con-sidering that the fast multiplier has essentially the same area as the slower one,the area of the design at 110MHz would be about 15–20%larger than the value predicted by the datapath synthesizer,thus emphasizing the potential interest of handling generation,syn-thesis,and directed placement in the same tool.4ConclusionsThe present evaluation has shown that there is no panacea for the design of standard-cell based datapath structures.State-of-the-art synthesis tools and standard area-based P&R tools in technologies with more than 2layers of metal now perform a job which strongly challenges manual and semi-manual techniques to preserve and make use of design regularity.“Extraction”tools have big problems in performing a good job,at least without putting heavy constraints on the synthesis process.These constraints may compromise the final result by producing a negative effect which offsets the benefits of regular placement.“Generation”tools are the only ones which really produced use-ful results in our experience.However,their beneficial effect can be seen exclusively in terms of reduced die area,and the indiscriminate use of algorithmic generation techniques for the netlist may have a very negative impact on the speed of the design.In fact,the present experiences show that when timing is the only metric of interest,pure synthesis of accurately generated netlist (without any place-ment data)achieves the best results.If,on the other hand,area is important,generation of netlist and relative placement data for very simple components may lead to a tangible advantage.The gener-ated components must be simple enough so that they do not have a too negative impact on timing (or,equivalently,simple enough so that the timing improvement possible by re-synthesizing them is not too large).From the above,it clearly appears that on timing-critical cell-based designs it is nowadays a severe penalty not to use a synthe-sizer.On the other side,regular placement is still beneficial (at least with 3layers of metal)in situations of very high connectivity.It follows that adding the placement generation inside a datapath “synthesis”tool (or just having the synthesis tool preserve a given relative placement)might prove to be the best solution.Although some interesting preliminary results have been observed with a tool of this class,the technique is still immature and it represents an area where the best improvements are still to be expected.References[1]J.Fadavi-Ardekani.Booth encoded multiplier gen-erator using optimized Wallace trees.IEEE Transactions onVery Large Scale Integration Systems ,VLSI-1(2):120–25,June 1993.[2]M.Gansen,F.Richter,O.Weiss,and T.Noll.A datapathgenerator for full-custom macros of iterative logic arrays.In L.Tiehle et al.,editors,Proceedings of the International Con-ference on Application Specific Systems,Architectures and Pro-cessors ,Zurich,July 1997.[3]rmore,D.D.Gajski,and yout place-ment for sliced architecture.IEEE Transactions on Computer-Aided Design ,11(1):102–14,Jan.1992.[4]V .G.Oklobdzija,D.Villeger,and S.S.Liu.A method forspeed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach.IEEE Transactions on Computers ,C-45(3):294–306,Mar.1996.[5]S.Vassiliadis,E.M.Schwarz,and B.M.Sung.Hard-wiredmultipliers with encoded partial products.IEEE Transactions on Computers ,C-40(11):1181–97,Nov.1991.[6]N.H.E.Weste and K.Eshraghian.Principles of CMOSVLSI Design .VLSI System Series.Addison-Wesley,Reading,Mass.,second edition,1993.[7]Q.Wu,C.Y .R.Chen,and B.S.Carlson.LILA:Layout genera-tion for iterative logic arrays.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ,14(11):1359–69,Nov.1995.。
