Field-programmable gate arrays (FPGAs) are integrated circuits that one can program repeatedly after manufacturing to perform any logical function. The programmable parts of FPGAs are called modules. “Programming” refers to interconnecting these modules, and changing their interconnections over time. Several methodologies already exist to perform this task; we can find some of them by browsing the references at the end of this paper.

The methodology that the authors propose, however, especially improves costs related to changing the interconnections. It works by first modeling communications among modules in terms of a data flow graph; then modeling module interconnections in terms of temporal graph partitions; and finally finding partitions with both the lowest data routing costs between any two modules, and the lowest switching costs between partitions.

After an introduction, the paper presents the mathematical quantities used to model the algorithm. Then, it describes the algorithm in mathematical terms as a collection of theorems and their proofs. Finally, it reports results from several experiments.

The aim of the paper is to provide mathematical proof of the correctness and robustness of the methodology. Although others have tested the results on real circuits, the environment of this paper is purely academic; it leaves the development of real-life products to the integrated circuit (IC) industry.