Field-programmable gate arrays (FPGAs) have the potential to revolutionize rapid hardware prototyping both in industry and in university research and instruction. To realize this potential, FPGA placement and routing tools must be orders of magnitude faster than those currently available. This project is investigating the use of incremental placement and routing to speed up FPGA design. Design is an iterative process characterized by small changes. By processing design changes as minimally as possible, incremental placement and routing has the potential to be dramatically faster than conventional tools which must reprocess an entire design from scratch. For placement, a generalized incremental form of the force-directed algorithm with time-varying cost functions is being investigated. Routing is being investigated using incremental penalty-driven iterative improvement and a generalized graph representation of routing resources. The algorithms produced will be implemented to demonstrate their efficacy and at the same time provide high-quality FPGA design tools. As a side benefit, the algorithms will also be applicable to conventional IC and PC board placement and routing tasks.
