Abstract
In reconfigurable computing, circuits implemented on multiFPGA systems have to be incrementally modified. Since reconfiguring an FPGA is timeconsuming, the time for reconfiguration depends on the number of FPGAs to be reconfigured. Our objective is to reduce the number of such FPGAs. In this paper, we consider the specific problem of incrementally reconfiguring a multiFPGA system that utilizes the direct interconnection architecture, where routing connections between FPGAs are to neighbors that are near. This problem can be divided into a net addition problem and a net deletion problem. We show that the net addition problem is a generalization of the NPcomplete Steiner tree problem. Our algorithm for this problem is based on an adaptation of the KleinRavi approximation algorithm for the nodeweighted Steiner tree problem. As for the net deletion problem, we prove that it is NPcomplete but the problem is solvable in polynomial time for tree topologies. Based on the algorithm for trees, we design an effective heuristic algorithm for the general net deletion problem. Finally, we present an algorithm for solving the incremental reconfiguration problem which handles both placement of new gates and interFPGA routing.
Original language  English 

Title of host publication  FPGA '02 
Subtitle of host publication  Proceedings of the 2002 ACM/SIGDA tenth international symposium on Fieldprogrammable gate arrays 
Place of Publication  United States 
Publisher  Association for Computing Machinery (ACM) 
Pages  206213 
Number of pages  8 
ISBN (Print)  9781581134520 
DOIs  
Publication status  Published  Feb 2002 
Event  10th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2002  Monterey Beach Hotel, Monterey, United States Duration: 24 Feb 2002 → 26 Feb 2002 https://www.isfpga.org/past/fpga2002/ (Conference website) https://www.isfpga.org/past/fpga2002/AdvProg.html (Conference program) https://dl.acm.org/doi/proceedings/10.1145/503048 (Conference proceedings) 
Publication series
Name  Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 

Symposium
Symposium  10th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2002 

Country/Territory  United States 
City  Monterey 
Period  24/02/02 → 26/02/02 
Internet address 

Scopus Subject Areas
 Computer Science(all)