AN FPGA LAYOUT RECONFIGURATION ALGORITHM-BASED ON GLOBAL ROUTES FOR ENGINEERING CHANGES IN SYSTEM-DESIGN SPECIFICATIONS

Rapid system prototyping is one of the main applications for field-pro grammable gate arrays (FPGAs). At the stage of rapid system prototypin g, design specifications can often be changed since they cannot be det ermined completely. In this paper, layout design change is focused on and a layout reconfiguration algorithm is proposed for FPGAs. The targ et FPGA architecture is developed for transport processing. In order t o implement more various circuits flexibly it has three-input lookup t ables (LUTs) as minimum logic cells. Since its logic granularity is fi ner than that of conventional FPGAs, it requires more routing resource s to connect them and minimization of routing congestion is indispensa ble. In layout reconfiguration, the main problem is to add LUTs to ini tial layouts. Our algorithm consists of two steps: For given placement and global routing of LUTs, in Step 1 an added LUT is placed with all owing that the position of the added LUT may overlap that of a preplac ed LUT; Then in Step 2 preplaced LUTs are moved to their, adjacent pos itions so that the overlap of the LUT positions can be resolved. Globa l routes are updated corresponding to reconfiguration of placement. Th e algorithm keeps routing congestion small by evaluating global routes directly both in Steps 1 and 2. Especially in Step 2, if the minimum number of preplaced LUTs are moved to their adjacent positions, our al gorithm minimizes routing congestion. Experimental results demonstrate that, if the number of added LUTs is at most 20% of the number of ini tial LUTs, our algorithm generates the reconfigured layouts whose rout ing congestion is as small as that obtained by executing a conventiona l placement and global routing algorithm. Run time of our algorithm is within approximately one second.