Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

6.7    PLACE-AND-ROUTE ACCELERATION

The place-and-route subsystem of the Algotronix CAD software uses a simulated annealing algorithm to repeatedly generate and evaluate potential placements for a user’s design. In the later stages of this process, the computer attempts to completely route the current placement. This step of the procedure is very computation intensive and results in long run times for the software. In this section we present a hardware acceleration tool for this application, which runs on the CHS2×4 board.

6.7.1    The Global Routing Algorithm

The global routing problem for CAL is to route a set of nets successfully, each of which has a single source and one or more destinations using the multiplexer routing resources of the CAL chip. The nets contend for multiplexer resources and the algorithm will fail if more than one net requires a particular multiplexer to route. In this case, the current placement will be rejected.

Each net is routed individually using a wavefront expansion algorithm, so the order in which nets are routed is of critical importance and it is usually necessary to rip up previously routed nets and retry nets in a different order to route a design successfully. The hardware accelerator described here allows the algorithm to very rapidly determine whether implementing the current net using a particular multiplexer will cause any of the currently unrouted nets to fail to route. That is, it answers the question: Given the present allocation of multiplexers, ...