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.

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

marco wrote:

> 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

Peter Alfke wrote:
> 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.


> 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 ;-)


> Peter Alfke
> 

Peter Alfke schrieb:
> 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

Thank you very much for the information Kolja.
I greatly appreciate the information that you included in your reply.
Best Regards,
Marco.

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

Peter Alfke schrieb:
> 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

Peter Alfke wrote:
> 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

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