Abstract
Field-programmable gate arrays (FPGAs) are commonly used in board designs. The authors consider the constrained FPGA pin-mapping problem in the FPGA-printed circuit board (PCB) codesign process. Unlike all previous works, which only saw constrained FPGA pin mapping as an independent chip-level problem, they take into account the connectivity of the FPGA with other components on the PCB to minimize the occurrence of net crossover and the PCB wirelength when computing a pin mapping. They propose an efficient tool, the versatile input/output (VIO) mapper, to automatically generate a proper pin-mapping upfront during the FPGA-PCB codesign process. Their input/output (I/O) mapper has a high level of flexibility. It can handle the different kinds of complex restrictions found in different FPGA devices. And it allows the PCB designers to lock down, say, the pin assignments for some critical signals before generating the assignments for the rest of the signals. Their mapper is based on an elegant 0-1 integer linear program (ILP) formulation. They show that due to the effective control of the number of integer variables and the use of a strong formulation (instead of an alternative weak formulation), their ILP-based approach is highly efficient in practice. It runs much faster than the mapping tool in Altera's Quartus II tool suite. In addition, they experimentally showed that the industrial tool's mapping algorithm is very far from optimal. For many instances on which Quartus II failed, feasible I/O mappings were found using the VIO mapper. © 2006 IEEE.