Proceedings of the 18th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2023F592

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 1119–1123 (2023)

Full text

Abstract. Circuit prototyping on multi-FPGA (Field Programmable Gate Arrays) platforms is a widely used technique in the VLSI (Very-Large-Scale Integration) context. Due to the ever-increasing size of circuits, it is necessary to use partitioning algorithms to place them on multi-FPGA platforms. Existing partitioning algorithms focus on minimizing the cut size but do not consider the critical path length, which can be degraded when mapping long paths to multiple FPGAs. However, recent studies try to consider the degradation of the critical path and the target topology. However, these works still use cutting minimization algorithms. In this work, we propose a mathematical model as an integer program (IP) based on the Red-Black Hypergraph model that considers the minimization of the critical path degradation and the target topology. We compare our partitioning results with khMeTiS, a min-cut algorithm, and show a better critical path for many circuit instances.

References

1. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hypergraph partitioning: applications in VLSI domain,” IEEE Transactions on VLSI Systems, vol. 7, no. 1, pp. 69–79, 1999.
2. J. Rodriguez, F. Galea, F. Pellegrini, and L. Zaourar, “A hypergraph model and associated optimization strategies for path length-driven netlist partitioning,” in International Conference on Computational Science. Springer, 2023, pp. 652–660.
3. C. Ababei, S. Navaratnasothie, K. Bazargan, and G. Karypis, “Multi-objective circuit partitioning for cutsize and path-based delay minimization,” in IEEE/ACM ICCAD 2002., 2002, pp. 181–185.
4. M.-H. Chen, Y.-W. Chang, and J.-J. Wang, “Performance-driven simultaneous partitioning and routing for multi-fpga systems,” in 2021 58th ACM/IEEE DAC, 2021.
5. S.-H. Liou, S. Liu, R. Sun, and H.-M. Chen, Timing Driven Partition for Multi-FPGA Systems with TDM Awareness. New York, NY, USA: Ass. Comp. Mach., 2020, p. 111–118. [Online]. Available: https://doi.org/10.1145/3372780.3375558
6. U. Çatalyürek, K. Devine, M. Faraj, L. Gottesbüren, T. Heuer, H. Meyerhenke, P. Sanders, S. Schlag, C. Schulz, D. Seemaier, and D. Wagner, “More recent advances in (hyper)graph partitioning,” ACM Computing Surveys, vol. 55, no. 12, mar 2023. [Online]. Available: https://doi.org/10.1145/3571808
7. D. Kucar, S. Areibi, and A. Vannelli, “Hypergraph partitioning techniques,” DYNAMICS OF CONTINUOUS DISCRETE AND IMPULSIVE SYSTEMS SERIES A, vol. 11, pp. 339–368, 2004.
8. G. Karypis and V. Kumar, “Analysis of multilevel graph partitioning,” in Proceedings of the 1995 ACM/IEEE Conference on Supercomputing, ser. Supercomputing ’95. New York, NY, USA: Association for Computing Machinery, 1995, p. 29–es. [Online]. Available: https://doi.org/10.1145/224170.224229
9. K. George and K. Vipin, “Hmetis: a hypergraph partitioning package,” ACM Transactions on Architecture and Code Optimization, 1998.
10. F. Pellegrini, “Scotch and PT-Scotch Graph Partitioning Software: An Overview,” in Combinatorial Scientific Computing, O. S. Uwe Naumann, Ed. Chapman and Hall/CRC, 2012, pp. 373–406. [Online]. Available: https://hal.inria.fr/hal-00770422
11. P. Bonami, V. H. Nguyen, M. Klein, and M. Minoux, “On the solution of a graph partitioning problem under capacity constraints,” in Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers 2. Springer, 2012, pp. 285–296.
12. F. Corno, M. Reorda, and G. Squillero, “RT-level ITC’99 benchmarks and first ATPG results,” IEEE Design & Test of Computers, vol. 17, no. 3, pp. 44–53, 2000.
13. C. Fiduccia and R. Mattheyses, “A linear-time heuristic for improving network partitions,” in 19th DAC, 1982.