Place and Route Algorithms for FPGAs: How Do They Do That?

In January, I taught a Continuing Education Center online class called "Programmable Logic: How Do They Do That?" One of the topics I covered is how place and route software works. This is one of the many sources of head scratching when you look at the results of an FPGA design that just doesn't seem right. A little understanding of how place and route algorithms work, and a bit of historical background, can help avoid some of these head-scratching moments.

In the early days of designing with FPGAs, getting the design to close (successfully route all the signals and meet some simple timing requirements) was a very big challenge -- both for the FPGA manufacturer and the customer. FPGA manufacturers had to trade off device capacity, place and route time and the effort ("tweaking") required of the customer to optimize the design for the target architecture. Customers needed to minimize their design time, keep device utilization high (or be forced to buy a bigger, sometimes much more expensive device to fit their design), and meet their timing constraints.

This problem was difficult enough that academic researchers saw it as a challenge. Many different proposals for improving place and route algorithms were proposed and one of them, first published in the mid-90s, "Pathfinder: A Negotiation-Based Performance Driven Router for FPGAs", L. E. McMurchie, and Carl Ebeling, (reprinted in the ACM International Symposium on Filed Programmable Gate Arrays, 1995, page 111; and also available here) outlined a new approach for the place and route algorithms used in FPGAs.

MORE FROM DESIGN NEWS: How Do You Get Started Designing with FPGAs? Here's How

The key approach used by Pathfinder is to over assign signals to routing nets (route multiple signals on a single net). The algorithm then negotiates the extra signals off the congested net to eventually place them on other nets (ones with perhaps longer delays). The negotiation is done systematically, with the cost of using a congested signal gradually increasing until other signal paths are found (that usually have longer delays) and the congestion is eventually eliminated. Because Pathfinder starts with a fully routed network (even if many signals are using a single resource) it was a much more manageable and predictable approach for resource constrained FPGA architectures.

Can you route S1 to D1, S2 to D2, and S3 to D3 with a minimal cost? Pathfinder can. (Hint: Start with all signals using node B and gradually increase the cost of using B on the congested signals to see what happens)

FPGA manufacturers found that this algorithm works much better than the algorithms used previously -- ones that tried to route incomplete signal networks by ripping up a signal and replacing it with another. These trial-and-error approaches were notorious for working for a long time without finding a solution. Pathfinder provided a much more systematic approach, and by 2000 the Pathfinder approach of negotiated congestion was being used by virtually all FPGA place and route algorithms.

MORE FROM DESIGN NEWS: Here's Your Chance to Learn About the Secrets of FPGAs

With a good algorithm in hand the FPGA architecture people could now tune the FPGA fabric more easily for timing driven place and route. Previously, delay time could swing wildly based on the routing resources used. Some signals required multiple pass gates and if signal delay was too long a buffer could be inserted to try and improve delay. This type of architecture was silicon efficient, but the large delay variation would dramatically reduce utilization. A new, more silicon intensive approach that used fully buffered signals started being explored. In this fabric architecture every wire has only one signal source. This is less flexible and costs more in silicon real estate, but it made timing driven place and route much more predictable and dramatically increased utilization. Thus it turned out that the resulting architecture was more silicon efficient and met timing much more predictably.

So, the next time you run an FPGA compile chain from a high level language through synthesis and the back-end FPGA manufacturer tools, give a nod to the Place and Route algorithm doing all the heavy lifting. Now if we could just find a way to use negotiated congestion to solve our evening highway commute problems, (perhaps via mass transit), life would be even better.

Warren Miller has more than 30 years of experience in electronics and has held a variety of positions in engineering, applications, strategic marketing, and product planning with large electronics companies like Advanced Micro Devices, Actel, and Avnet, as well as with a variety of smaller startups. He has in-depth experience of programmable devices (PLDs, FPGAs, MCUs, and ASICs) in industrial, networking, and consumer applications and holds several device patents.