| Author |
Message |
marco
Guest
|
 Posted:
Tue Dec 20, 2005 11:44 pm Post subject:
Place and Route Algorithms |
|
|
Hello everyone.
Does anyone know where I can find information about the place and route
algorithms used for FPGAs, and what kind of work has been done or is
being done to accelerate these algorithms.
Books and/or links to web-sites will be greatly appreciated.
Regards,
Marco. |
|
| Back to top |
|
 |
Peter Alfke
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Place and Route Algorithms |
|
|
Marco, I am sure that you will not find anything beyond very basic
tutorial information.
These are the "crown jewels" of any FPGA company, and these jewels are
well guarded, but also polished daily. The quality of these tools
determines the success of our companies, and each of us wants to be at
leats a step ahead of the other company.
BTW, the continuous investment by companies like Xilinx and Altera (to
name just the two biggest) is enormous, and it is unlikely that an
individual engineer can provide significant improvements. Unless you
are a genius and addressthe problem in a very unconventioanl way.
Peter Alfke |
|
| Back to top |
|
|
Mike Treseler
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Place and Route Algorithms |
|
|
marco wrote:
| Quote: | Does anyone know where I can find information about the place and route
algorithms used for FPGAs, and what kind of work has been done or is
being done to accelerate these algorithms.
|
http://groups.google.com/groups?q=place+route+algorithm+fpga |
|
| Back to top |
|
|
Stephane
Guest
|
| Posted:
Wed Dec 21, 2005 3:20 pm Post subject:
Re: Place and Route Algorithms |
|
|
Peter Alfke wrote:
| Quote: | Marco, I am sure that you will not find anything beyond very basic
tutorial information.
|
Maybe it's just better not to know: [remark for all users:] did you
never realize that sometimes setting some options has the opposite
action that their name suggest?
I always told myself: the proof that the tool vendors are not
comfortable with the complexity of their software is named Xplorer...
I don't blame, I'm no troll! I acknowledge the great job your teams do.
But intrisic knowledge of the tools should allow confirmed users to set
correctly the right options with predictable behavior.
| Quote: | Unless you
are a genius and addressthe problem in a very unconventioanl way.
|
In that case, create your company and get acquired by one of those
"biggest" or submit a CV ;-)
|
|
| Back to top |
|
|
Kolja Sulimma
Guest
|
| Posted:
Wed Dec 21, 2005 5:16 pm Post subject:
Re: Place and Route Algorithms |
|
|
Peter Alfke schrieb:
| Quote: | Marco, I am sure that you will not find anything beyond very basic
tutorial information.
These are the "crown jewels" of any FPGA company, and these jewels are
well guarded, but also polished daily. The quality of these tools
determines the success of our companies, and each of us wants to be at
leats a step ahead of the other company.
BTW, the continuous investment by companies like Xilinx and Altera (to
name just the two biggest) is enormous, and it is unlikely that an
individual engineer can provide significant improvements. Unless you
are a genius and addressthe problem in a very unconventioanl way.
|
I totally disagree.
There is a difference between an algorithm and an implementation with
tweaked parameters for a given architecture.
Im am doing EDA-algortihm research for quite some time, and most
substantial progress has been made by individuals or very small teams.
These people do not provide industrial grade implementations that can do
a better job on any given FPGA than the vendor tools, but provide enough
evidence that a certain approach might be better suited.
I hear pathfinder variants are used a lot for fpga routing. Two authors
only.
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/proceedings/&toc=comp/proceedings/fpga/1995/2550/00/2550toc.xml&DOI=10.1109/FPGA.1995.15
And without flowmap Xilinx probably would build MUX-based FPGAs now.
You and can be greatful that Leiserson and Saxe did not patent retiming
and sell it to altera.
http://www.springerlink.com/(equ2gbjfwu2v44ebrbkulu55)/app/home/contribution.asp?referrer=parent&backto=issue,2,47;journal,56,61;linkingpublicationresults,1:400117,1
Otherwise ISE would have to be an web based application with servers
running in europe.
Xilinx used placement based on simulated annealing in the past.
(UC Berkeley, Carl Sechen, Sangiovanni-Vincentelly, et. al.)
What is it now? Quadratic placement imported from Munich?
The OP should turn to University of Toronto were a lot of FPGA placement
and routing research has been done. Also, scholar.google.com tells me
that André DeHon at CalTech has published in the area of hardware
accelerated placement and routing recently (2003)
Kolja Sulimma |
|
| Back to top |
|
|
marco
Guest
|
| Posted:
Wed Dec 21, 2005 11:35 pm Post subject:
Re: Place and Route Algorithms |
|
|
Thank you very much for the information Kolja.
I greatly appreciate the information that you included in your reply.
Best Regards,
Marco. |
|
| Back to top |
|
|
Peter Alfke
Guest
|
| Posted:
Thu Dec 22, 2005 12:36 am Post subject:
Re: Place and Route Algorithms |
|
|
I stand corrected.
My response was directed at the suggestion: "I can come up with a
better P&R implementation for Xilinx or Altera chips". As Kolja also
might agree, an industrial-strength complete solution involves massive
efforts that only the major companies can afford.
But a novel algorithm, a completely different way of attacking the
problem, can more easily come from a few individuals who are not
burdened with maintaining legacy designs, or with the expectation of
completing their project to industrial strength. Without such burdens,
they can explore more freely, and such exploration has been fruitful in
the past, and might well be in the future.
I stand corrected.
Peter Alfke |
|
| Back to top |
|
|
John_H
Guest
|
| Posted:
Thu Dec 22, 2005 1:15 am Post subject:
Re: Place and Route Algorithms: where's the fat? |
|
|
"Austin Lesea" <austin@xilinx.com> wrote in message
news:dochlk$85d5@xco-news.xilinx.com...
| Quote: | 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 |
|
| Back to top |
|
|
dp
Guest
|
| Posted:
Thu Dec 22, 2005 1:15 am Post subject:
Re: Place and Route Algorithms: where's the fat? |
|
|
Austin,
| Quote: | 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
------------------------------------------------------ |
|
| Back to top |
|
|
Austin Lesea
Guest
|
| Posted:
Thu Dec 22, 2005 1:16 am Post subject:
Re: Place and Route Algorithms: where's the fat? |
|
|
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.
Teasing that intent from the HDL, through clever constrains, additional
tools (like PlanAhead), or inferring (or evwen guessing) by use of
clever code, can provide improvement.
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.
It matters little if IC Design or software cleverness led to low power,
and high speed/performance. It is the sum total that is magic: the
next version of the part (and the tools) provides that cost/benefit that
is required for a new generation of applications.
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. Lots of
room for improvements here. Tools still have cleverness left to
discover, as we seem to still be getting more clever even after 7
products (that I was personally involved in). Adjuct tools (like
PlanAhead) are very valuable for the users who just must get the
absolute best from the tools (without hiring a consultant who hand
places, and tries to tease the performance out which is not always
successful, and certainly can't be predicted), and because they are so
useful, they provide direct benefit that is worth something (so they
justify their price). Finally, it is the combination of tools and
silicon that solves the problem, neither stands alone.
Austin |
|
| Back to top |
|
|
Jim Granville
Guest
|
| Posted:
Thu Dec 22, 2005 1:16 am Post subject:
Re: Place and Route Algorithms |
|
|
Peter Alfke wrote:
| Quote: | Marco, I am sure that you will not find anything beyond very basic
tutorial information.
These are the "crown jewels" of any FPGA company, and these jewels are
well guarded, but also polished daily. The quality of these tools
determines the success of our companies, and each of us wants to be at
leats a step ahead of the other company.
BTW, the continuous investment by companies like Xilinx and Altera (to
name just the two biggest) is enormous, and it is unlikely that an
individual engineer can provide significant improvements. Unless you
are a genius and addressthe problem in a very unconventioanl way.
Peter Alfke
|
If these are so polished, then why do manual tools like PlanAhead,
still give significant gains ?
Until the automated tools get within a few % of good manual design,
to me that demonstrates ample scope for improved SW.
There also seem to be steady annual claims of Tool Improvements well
into the double digits, which also suggest these are far from mastered
( or are these claims more inflated by marketing fluff... ?)
A cynic might also point out, that the PlanAhead tools are $$$,
and so Xilinx have something of a conflict of interest - if the
free tools, get too close to the fullsuite, their revenue stream
will drop....
-jg |
|
| Back to top |
|
|
Kolja Sulimma
Guest
|
| Posted:
Thu Dec 22, 2005 1:16 am Post subject:
Re: Place and Route Algorithms |
|
|
Peter Alfke schrieb:
| Quote: | As Kolja also
might agree, an industrial-strength complete solution involves massive
efforts that only the major companies can afford.
Full ACK. |
For my contributions to that area it usually is required to check the
benchmarks beforehand for special cases the tools can not handle. E.g.
it is just not worthwile for research to handle wires that go directly
from inputs to outputs if your data model for some reason requires a
cell connected to each net. An industrial tool would hack in some
workaround. I just delete the wire.
Even large companies sometimes take a while to handle such cases. I
regularly succeed to kill industrial grade synthesis tools with 0 input
designs for example. There are VLSI placers that can not handle single
cell designs, because the loop condition is checked after the loop.
One element arrays in high level synthesis sometimes are fun, too.
Another issue is, that many algorithms have a lot of tunable parameters
that need to be adjusted for a whole range of devices for optimum
results. The developer of the tool can do that on a case to case basis
manually. But if you want to sell a push button solution to thousands of
customers....
Still, there are many small companies that develop special case EDA
algorithm implementations and sell them to tool chain vendors that
incorporate them into their flows. A lot of what xilinx uses was not
developed inhouse.
Kolja Sulimma |
|
| Back to top |
|
|
Phil Hays
Guest
|
| Posted:
Thu Dec 22, 2005 8:12 am Post subject:
Re: Place and Route Algorithms: where's the fat? |
|
|
On Wed, 21 Dec 2005 22:44:22 GMT, "John_H" <johnhandwork@mail.com>
wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Jim Granville
Guest
|
| Posted:
Thu Dec 22, 2005 9:15 am Post subject:
Re: Place and Route Algorithms: where's the fat? |
|
|
Ray Andraka wrote:
| Quote: | 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
| Quote: | 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 ?
| Quote: |
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 |
|
| Back to top |
|
|
John_H
Guest
|
| Posted:
Thu Dec 22, 2005 9:15 am Post subject:
Re: Place and Route Algorithms: where's the fat? |
|
|
Phil Hays wrote:
| Quote: | 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. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in