Pin Assignment Optimization for Multi-2.5D FPGA-based Systems with Time-Multiplexed I/Os

As 2.5-D field-programmable gate arrays (FPGAs) have larger logic capacity and higher pin counts compared to conventional FPGAs, they are already deployed in some multi-FPGA systems. 2.5-D FPGA consists of multiple dies connected through an interposer. Since the interposer provides only a fraction of the amount of interconnect resources with an increased delay compared to that within individual dies, it is important to reduce the number of signal crossings between dies both for routability and timing consideration when a circuit is mapped to a 2.5-D FPGA. In a multi-2.5D FPGA system with time-multiplexed hardwired inter-FPGA connections, there can be tens of thousands of inter-FPGA signals incident with each FPGA and their pin assignment can greatly affect the amount of die-crossing signals within the FPGAs. In this article, we formulate the pin assignment problem for such systems with the objective of minimizing signal crossings between dies within the individual FPGAs. Taking into consideration of the multi-die structure of 2.5-D FPGA, we propose two different iterative refinement approaches to the problem, one based on integer linear programming (ILP) and the other algorithm C-2MCF based on clustering optimization and minimum cost flow optimization. Compared to a greedy pin assignment heuristic for minimization of signal crossings between dies, C-2MCF produced 27.1% less crossings on average. While the ILP-based algorithm has up to 1% quality advantage over C-2MCF for moderate-sized instances, C-2MCF is orders of magnitude faster and can comfortably handle very large problem instances. In addition, the proposed minimum cost flow techniques within C-2MCF can also be used in conjunction with any other possible pin assignment method to enhance the final result.