Place and Route Algorithms

Austin,

> So, if I would recap this ramble:  HDLs are not good at telling the
> tools the best way to actually do what the designer wanted.

The purpose of high level languages (for logic generation or
writing software) is to allow cheaper programming, the loss
factor I have witnessed has varied between 10 and >1000.
If one has the resources to do things at a lower level,
this is always the better choice. It does not take longer,
it does not cost more text (except for very low complexity
works where this is a non-issue anyway), it "only" takes
more skills. No translating tool can replace direct access
to the programmed hardware.
 I wish silicon vendors were less unwilling to allow
third parties to be able to program their silicon,
thus removing a major progress roadblock. But this
is unlikely to come true, it has some political
background which eludes me (economically the
chip makers would benefit from such openness).


Dimiter

------------------------------------------------------
Dimiter Popoff               Transgalactic Instruments

http://www.tgi-sci.com
------------------------------------------------------

"Austin Lesea" <austin@xilinx.com> wrote in message 
news:dochlk$85d5@xco-news.xilinx.com...
> jg,
>
> I'll probably regret putting in my 2 cents, but here goes:
>
>
> It is true that "significant gains" are still (often, not always) realized 
> by some careful hand placement, and some careful partitioning.
>
> That suggests that the design languages lack something important, as the 
> intent of the designer is not being communicated to the tools.

<snip>

I appreciate the quality of the tools over where they were years ago.  I 
regularly curse the software, however, because the design intent that "I 
want to achive 200 MHz performance" can make it through the synthesis tools 
after some coaxing but ends up coming through the place & route software 
with brain-dead 2.5 ns nets on both sides of a single LUT.  This is the 
extreme example of when good routes go bad.

I've tried to push the idea that a "critical path routing" approach can make 
the designs run as fast as n-levels of logic with appropriate 
primitive-specific delays can go.  The tool shows no signs that it looks at 
what is possible before deciding how to throw everything together.

My opinion is that the process of mapping separate from place & route is 
archaic (to use kind words) and that spreading the logic out so each slice 
has just one LUT is *not* the way to alleviate the problem.  The tools 
should have the intelligence to unbundle and rebundle unrelated logic as 
necessary to keep the logic "tight" (delays low) even in a low-utilization 
design.

The tools *can* do so much more; the evolutionary development of the tools 
has hampered true progress.  The silicon is *amazing* in what can be 
accomplished.  "Pushing the rope" to improve results with synthesis is bad 
enough.  Having place & route software that can't understand what it takes 
to produce good results every time is sad.  I can pass with total timing 
compliance then lose by 1.5 nanoseconds after changing non-critical logic. 
I prefer not to curse my tools.

Respectfully,
- John_H 

On Wed, 21 Dec 2005 22:44:22 GMT, "John_H" <johnhandwork@mail.com>
wrote:

>My opinion is that the process of mapping separate from place & route is 
>archaic (to use kind words) and that spreading the logic out so each slice 
>has just one LUT is *not* the way to alleviate the problem.

Yes.  Xilinx has added "map -timing" to do just that.  Mappping logic
is now with placement, and the result works rather better.


-- 
Phil Hays 

Austin Lesea wrote:
> 
> It is true that "significant gains" are still (often, not always) 
> realized by some careful hand placement, and some careful partitioning.
> 
> That suggests that the design languages lack something important, as the 
> intent of the designer is not being communicated to the tools.
> 
...

> The software folks here at Xilinx are amazing:  they have managed to 
> improve every generation the performance while reducing the time to 
> compile the designs; all the while we in IC design follow Moore's law 
> and double the density.  Not to mention we add more custom IP, and 
> customers are getting more demanding.
> 


Austin,

What is missing is geographic relationships between parts of the 
circuit.  Perhaps the biggest piece missing in the current tools is 
utilization of the hierarchy in a design.  The current xilinx tools 
flatten the design before they even start on the place and route 
problem, and that greatly increases the workload and time to complete 
while also degrading performance.  The tools have an opportunity to use 
the hierarchy in the design to treat each hierarchical layer as a 
mini-design, essentially breaking the problem into smaller problems in a 
way that is consistent with the way the designer broke up the design. 
Going to a true hierarchical place and route would improve both the 
quality of results as well as the run times.

Now, I do disagree with your assertion that each generation of the tools 
improves both run time and quality of results.  I have indeed seen 
improvements in run time, but more often than not the quality of results 
has taken a step backwards with each major release of ISE.  Yes, I 
suppose for flat RTL only designs, the results have gotten somewhat 
better, but that is mostly due to large improvements in synthesis, and 
small incremental improvements in the automatic placement (which BTW, 
still does a dismal job with placing non-LUT resources, with placing 
data paths, and with placing logic that has multiple levels of LUTs 
between FFs).  In the mean time, the routing algorithms have gotten 
lazy, apparently in the interest of speeding up run times.  For designs 
with poor placement, the effects of poor routing are not as apparent as 
they are for well placed (eg carefully floorplanned) designs.  For my 
floorplanned designs, I have seen a steady erosion in the max speeds 
attainable by the tools on each new release since 4.1.

One of the biggest steps backward came from eliminating delay based 
clean-up (IIRC that happened in 5.2).  The result there is that the 
tools just stop as soon as all routes meet timing.  Every route in the 
design is potentially a critical route.  The routes to nearby 
destinations often take circuitous routes that congest the routing 
resources and unnecessarily drive the power dissipation up considerably. 
  With the current emphasis on power dissipation, I would think that the 
Xilinx team would be looking at reinstituting the delay based clean-up. 
  Based on my empirical observations, that could pick up a 15-20% 
improvement in power dissipation for designs that are clocked in the 
upper half of the performance envelope.

Phil Hays wrote:
> On Wed, 21 Dec 2005 22:44:22 GMT, "John_H" <johnhandwork@mail.com>
> wrote:
> 
> 
>>My opinion is that the process of mapping separate from place & route is 
>>archaic (to use kind words) and that spreading the logic out so each slice 
>>has just one LUT is *not* the way to alleviate the problem.
> 
> 
> Yes.  Xilinx has added "map -timing" to do just that.  Mappping logic
> is now with placement, and the result works rather better.

The map -timing is still done ONLY in the map phase WITHOUT iterative 
back & forth with place & route.  The attempt is made to group related 
logic together to get "tighter" logic but this little user-selectable 
switch doesn't make up for the rest of the problems with disjunct mapper 
and P&R.

Ray Andraka wrote:
> Austin Lesea wrote:
> 
>>
>> It is true that "significant gains" are still (often, not always) 
>> realized by some careful hand placement, and some careful partitioning.
>>
>> That suggests that the design languages lack something important, as 
>> the intent of the designer is not being communicated to the tools.
>>
> ...
> 
>> The software folks here at Xilinx are amazing:  they have managed to 
>> improve every generation the performance while reducing the time to 
>> compile the designs; all the while we in IC design follow Moore's law 
>> and double the density.  Not to mention we add more custom IP, and 
>> customers are getting more demanding.
>>
> 
> 
> Austin,
> 
> What is missing is geographic relationships between parts of the 
> circuit.  Perhaps the biggest piece missing in the current tools is 
> utilization of the hierarchy in a design.  The current xilinx tools 
> flatten the design before they even start on the place and route 
> problem, and that greatly increases the workload and time to complete 
> while also degrading performance.  The tools have an opportunity to use 
> the hierarchy in the design to treat each hierarchical layer as a 
> mini-design, essentially breaking the problem into smaller problems in a 
> way that is consistent with the way the designer broke up the design. 
> Going to a true hierarchical place and route would improve both the 
> quality of results as well as the run times.
> 
> Now, I do disagree with your assertion that each generation of the tools 
> improves both run time and quality of results.  I have indeed seen 
> improvements in run time, but more often than not the quality of results 
> has taken a step backwards with each major release of ISE.  Yes, I 
> suppose for flat RTL only designs, the results have gotten somewhat 
> better, but that is mostly due to large improvements in synthesis, and 
> small incremental improvements in the automatic placement (which BTW, 
> still does a dismal job with placing non-LUT resources, with placing 
> data paths, and with placing logic that has multiple levels of LUTs 
> between FFs).  In the mean time, the routing algorithms have gotten 
> lazy, apparently in the interest of speeding up run times.  

  Hmm.. seems the real world is rather removed from that of Xilinx 
employees - Engineers should know better than to believe their own
marketing fluff ?

  Peter, What Ray suggests sounds very sensible and not what I'd call
"a very unconventioanl way"

  Austin, perhaps if you used engineering measurements for SW results,
rather than the words like "wizards" and "magic", then the SW might have 
a chance to really improve with each release ?

For designs
> with poor placement, the effects of poor routing are not as apparent as 
> they are for well placed (eg carefully floorplanned) designs.  For my 
> floorplanned designs, I have seen a steady erosion in the max speeds 
> attainable by the tools on each new release since 4.1.

  Yikes!
One wonders how _CAN_ SW make a carefully floorplanned design go 
backwards ?  By how much ?

  Is that the lazy routing, being so bad, it actually finds a longer 
path, than earlier SW ?

> 
> One of the biggest steps backward came from eliminating delay based 
> clean-up (IIRC that happened in 5.2).  The result there is that the 
> tools just stop as soon as all routes meet timing.  Every route in the 
> design is potentially a critical route.  The routes to nearby 
> destinations often take circuitous routes that congest the routing 
> resources and unnecessarily drive the power dissipation up considerably. 
>  With the current emphasis on power dissipation, I would think that the 
> Xilinx team would be looking at reinstituting the delay based clean-up. 
>  Based on my empirical observations, that could pick up a 15-20% 
> improvement in power dissipation for designs that are clocked in the 
> upper half of the performance envelope.

  I did wonder how Altera suddenly found power savings in SOFTWARE -
perhaps they now do exactly this, clean up messy, but timing legal,
routes ? Anyone in Altera comment ?

  PCB routing software has for years used cleanup and optimise passes,
and only rarely (these days) goes outside a bounding rectangle on paths.

  PCB routers also routinely route the 'most obvious' traces first,
and so are very unlikely to go backwards on carefully floorplanned 
designs. They also allow net priority, where important nets can
get first bite at resources.

  Q: Does Xilinx SW scan floorplanned areas, and tag those nets as
(probably) being important, and thus should have first-bite-privilages 
in Routing ?

  Given the enomous investment the companies claim, these field results
seem rather abysmal - seems the HW is carrying the SW ?.

  Still, it does seem there is indeed a lot of 'fat' in Place & Route SW,
so we can expect further 'double digit improvement' claims.... :)

-jg

Ray,

Some comments,

Austin

-snip-

> What is missing is geographic relationships between parts of the 
> circuit.  Perhaps the biggest piece missing in the current tools is 
> utilization of the hierarchy in a design.

As I said, there is a lot of room for improvement here.  You are 
assuming that the hierarchy is well done, and that the results from 
working on each piece alone will do better.  Just don't know if that is 
true.  Good area for work, I would agree.

> Now, I do disagree with your assertion that each generation of the tools 
> improves both run time and quality of results.

I have to differ here.  I understand your issues, but if we deal with 
the ever expanding "standard suite" of test designs with better 
performance, and better run time, I have to assert that it is better. 
Is everything better?  Of course not.

> One of the biggest steps backward came from eliminating delay based 
> clean-up (IIRC that happened in 5.2).

I happen to agree with you here, my personal opinion is that the tools 
should allow you to choose to go to the extra effort to find the best 
paths, and not stop as soon as the aggregate requirements are met (or 
stop and give up if it can't meet the requirements).  I think you will 
appreciate that what was done did provide for a much faster time to get 
the design.

We do make the parts bigger every generation, and you may have noticed, 
processor power is not keeping up anymore.

Jim,

Some comments,

Austin

-snip-

>  Austin, perhaps if you used engineering measurements for SW results,
> rather than the words like "wizards" and "magic", then the SW might have 
> a chance to really improve with each release ?

The software group has a very rigorous quality of results metrics 
(measurement) system for evaluating their work.  I get to use the 
superlatives, they do not.

>  I did wonder how Altera suddenly found power savings in SOFTWARE -

We still beat them on power, ask your FAE for the presentation.  They 
took a really lousy situation and made it just plain lousy.  We still 
have a 1 to 5 watt advantage, AFTER they run their power cleanup.

>  Given the enomous investment the companies claim, these field results
> seem rather abysmal - seems the HW is carrying the SW ?.

Rather, the software is now (often) carrying the hardware.  Very hard to 
get the latest technology to be any faster than the previous one, 
without architecture and software.  If the software buys a speed grade, 
that is all the customer cares about.  The silicon get less expensive 
with the shrink to the next generation.  Who cares if the performance 
came from software, hardware, or both?

>  Still, it does seem there is indeed a lot of 'fat' in Place & Route SW,
> so we can expect further 'double digit improvement' claims.... :)

I agree.  Until the tools do a better job than a room full of experts, 
the tools are just not 'there'.  Reminds me of compilers for high level 
languages many years ago:  there was a time I could write assembly code 
that was faster, better, smaller, than any compiled high level language 
(anyone recall PLM86?).  Then after a while, the compilers got better 
and better.  Until finally, I had to agree that all that work was not 
worth it:  often the compiler yielded a better solution that my hand 
written assembly code.

Jim Granville wrote:


> 
>  Yikes!
> One wonders how _CAN_ SW make a carefully floorplanned design go 
> backwards ?  By how much ?
> 
 >  Is that the lazy routing, being so bad, it actually finds a longer
 > path, than earlier SW ?

Enough to make so a design that passed timing with the earlier tools 
will not pass timing no matter what you do with the newer tools short of 
   hand routing it.  about 10% loss in performance average in each major 
revision.  There was a huge hit going to 5.2.  7.1 seems to have a much 
smaller degradation from 6.3.

Yes, the routing got lazy so that it actually finds a longer path than 
it did with earlier software.  Quite often, it will not find the direct 
connection to a neighboring cell, and instead routes it all over the 
place, which adds delay, increases power consumption, and congests the 
routing resources so that other nets also get a circuitous route so that 
the overall timing is even further degraded.

>  I did wonder how Altera suddenly found power savings in SOFTWARE -
> perhaps they now do exactly this, clean up messy, but timing legal,
> routes ? Anyone in Altera comment ?

 From what I understand, Altera is moving toward more delay based 
clean-up.  Xilinx has moved away from it, and is instead pursuing 
capacitance based clean-up to reduce the power...which not only may miss 
the mark, but also requires toggle rate information for each net.

Austin,

 From what I have seen, folks who use hierarchy generally do a decent 
job of it. You really have to work hard at making a hierarchical design 
worse than a flat design. Hierarchy puts organization in the design, and 
because crossing levels of hierarchy is a little bit painful, it forces 
the designer to think in terms of components and to group related stuff 
together.  Even in a poor example of hierarchy, there is at least a 
little bit of grouping done, and therefore information the tools can 
use.  I and others have been asking for hierarchical tools from Xilinx 
for close to 15 years.  I honestly don't think Xilinx understands why 
using hierarchy is a good thing.



Austin Lesea wrote:



> I have to differ here.  I understand your issues, but if we deal with 
> the ever expanding "standard suite" of test designs with better 
> performance, and better run time, I have to assert that it is better. Is 
> everything better?  Of course not.

Fine, but improvements shouldn't break existing designs.  Nearly every 
single one of my designs over the past 5 years gets better results with 
the tool that was current at the start of the project than it does with 
later versions of the tools.  I could accept a low rate of recitivism, 
but close to 100% is criminal.  I know I am not the only "power user" 
running into this, in fact it regularly comes up as a subject here at 
each major release of the tools.

> stop and give up if it can't meet the requirements).  I think you will 
> appreciate that what was done did provide for a much faster time to get 
> the design.

Ummm, well no.  The tools give you faster time to completion for a run 
through the tools, but that doesn't help if the design does not meet the 
timing requirements.  It actually takes longer to complete a design 
because you need to iterate on the place and route much more than when 
there was a predictable routing solution for a good placement.  Faster 
completion in the tools does not equal faster time to get the design done.

> 
> We do make the parts bigger every generation, and you may have noticed, 
> processor power is not keeping up anymore.
> 
Yup, and Hierarchy can help you tremendously here.  Routing complexity 
(and therefore effort needed) goes up with roughly the square of the 
device size measured in LUTs, primitives, cells etc.  By breaking it 
down into hierarchical sub-assemblies, you end up with N smaller k/N 
problems, so the effort is smaller than k^2.