A mathematical programming method for constructing the shortest interconnection VLSI arrays

J. Antusiak, A. Trouv, K. Murakami, A comparison of DAG and mesh topologies for coarse-grain reconfigurable array, in: Proc. IEEE 26th Int’l Parallel and Distributed Processing Symp. Workshops & PhD Forum (IPDPSW ’12), May 2012, pp. 227-233. D. Ajwani, S. Ali, J.P. Morrison, Graph Partitioning for reconfigurable topology, in: Proc. IEEE 26th Int. Parallel Distrib. Process. Symp., May 2012, pp. 836-847. M. Modarressi, H. Sarbazi-Azad, A. Tavakkol, An efficient dynamically reconfigurable on-chip network architecture, in: Proc. 47th Des. Autom. Conf., 2010, pp. 310-313. Modarressi, 2011, Applicationaware topology reconfiguration for on-chip networks, IEEE Trans. Very Large Scale Integr. Syst., 19, 2010, 10.1109/TVLSI.2010.2066586 S. Murali, G. De Micheli, SUNMAP: A tool for automatic topology selection and generation for NoCs, in: Proc. 41st Des. Autom. Conf., 2004, pp. 914-919. M. Modarressi, H. Sarbazi-Azad, Power-aware mapping for reconfigurable NoC architectures, in: Proc. 25th Int. Conf. Comput. Des., 2007, pp. 417-422. Collet, 2011, Chip self- organization and fault tolerance in massively defective multicore arrays, IEEE Trans. Dependable Secure Comput., 8, 207, 10.1109/TDSC.2009.53 Akbar, 2016, An efficient fault-tolerant routing algorithm in NoCs to tolerate permanent faults, J. Supercomput., 72, 4629, 10.1007/s11227-016-1749-0 Chen, 2017, Path-diversityaware fault-tolerant routing algorithm for network-on-chip systems, IEEE Trans. Parallel Distrib. Syst., 28, 838, 10.1109/TPDS.2016.2588482 Xiang, 2009, Practical deadlock-free fault-tolerant routing in meshes based on the planar network fault model, ACM Trans. Des. Autom. Electr. Syst., 58, 620 Xiang, 2018, Fault-tolerant unicast-based multicast for reliable network-on-chip testing, ACM Trans. Des. Autom. Electr. Syst., 23, 1 Wu, 2019, Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays, J. Circuits Syst. Comput., 28, 10.1142/S0218126619501111 Zhang, 2002, Fault-tolerant meshes with small degree, IEEE Trans. Comput., 51, 553, 10.1109/TC.2002.1004594 Fukushi, 2004, A self-reconfigurable hardware architecture for mesh arrays using single/double vertical track switches, IEEE Trans. Instrum. Meas., 53, 10.1109/TIM.2003.822717 I. Takanami, T. Horita, A built-in circuit for self-repairing mesh-connected processor arrays by direct spare replacement, in: IEEE Pacific Rim Int. Symp. on Dependable Computing (PRDC). Niigata, Nov. 2012, pp. 96-104. Lin, 2009, Fault-tolerant router with built-in self-test/self-diagnosis and fault-isolation circuits for 2D-mesh based chip multiprocessor systems, J. Electr. Eng., 16, 213 Horita, 2000, Fault-tolerant processor arrays based on the 1.5-track switches with flexible spare distributions, IEEE Trans. Comput., 49, 542, 10.1109/12.862214 Chuang, 2005, An efficient reconfiguration scheme for fault-tolerant meshes, Inform. Sci., 172, 309, 10.1016/j.ins.2004.05.003 Kuo, 1992, Efficient reconfiguration algorithms for degradable VLSI/WSI arrays, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 11, 1289, 10.1109/43.170991 Low, 1997, On the reconfiguration of degradable VLSI/WSI arrays, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 16, 1213, 10.1109/43.662684 Low, 2000, An efficient reconfiguration algorithm for degradable VLSI/WSI arrays, IEEE Trans. Comput., 49, 553, 10.1109/12.862215 M. Fukushi, Y. Fukushima, S. Horiguchi, A genetic approach for the reconfiguration of degradable processor arrays, in: Proc. IEEE 20th Int’l Symp. Defect and Fault Tolerance in VLSI Systems, 2005, pp. 63-71. Y. Fukushima, M. Fukushi, S. Horiguchi, An improved reconfiguration method for degradable processor arrays using genetic algorithm, in: Proc. IEEE 21st Int’l Symp. Defect and Fault Tolerance in VLSI Systems, 2006, pp. 353-361. Wu, 2007, Integrated row and column re-routing for reconfiguration of VLSI arrays with 4-port switches, IEEE Trans. Comput., 56, 1387, 10.1109/TC.2007.1085 Ding, 2021, Flexible scheme for reconfiguring 2D mesh-connected VLSI subarrays under row and column rerouting, J. Parallel Distrib. Comput., 151, 1, 10.1016/j.jpdc.2021.01.003 Wu, 2009, Preprocessing and partial rerouting techniques for accelerating reconfiguration of degradable VLSI arrays, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 18, 315 Y.B. Zhu, J.G. Wu, S.K. Lam, Preprocessing technique for accelerating reconfiguration of degradable VLSI arrays, in: IEEE International Symposium on Circuits and Systems (ISCAS), 2013, pp. 2424-2427. Qian, 2020, An efficient multiple shortest augmenting paths algorithm for constructing high performance VLSI subarray, Integr. VLSI J., 75, 63, 10.1016/j.vlsi.2020.06.005 Qian, 2016, Optimal reconfiguration of high-performance VLSI subarrays with network flow, IEEE Trans. Parallel Distrib. Syst., 27, 3575, 10.1109/TPDS.2016.2539958 Qian, 2021, An improved algorithm for accelerating reconfiguration of VLSI array, Integr. VLSI J., 79, 124, 10.1016/j.vlsi.2021.04.005 Jiang, 2013, Efficient reconfiguration algorithms for communication-aware three-dimensional processor arrays, Parallel Comput., 39, 490, 10.1016/j.parco.2013.04.005 Jiang, 2015, Reconfiguring three-dimensional processor arrays for fault-tolerance: Hardness and heuristic algorithms, IEEE Trans. Comput., 64, 2926, 10.1109/TC.2015.2389846 Qian, 2019, Efficient reconfiguration algorithm with flexible rerouting schemes for constructing 3D VLSI sub-arrays, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 39, 267, 10.1109/TCAD.2019.2891984 Wu, 2006, Reconfiguration algorithms for power efficient VLSI subarrays with four-port switches, IEEE Trans. Comput., 55, 243, 10.1109/TC.2006.43 Wu, 2014, Constructing sub-arrays with short interconnects from degradable VLSI arrays, IEEE Trans. Parallel Distrib. Syst., 25, 929, 10.1109/TPDS.2013.114 Jiang, 2014, Flexible rerouting schemes for reconfiguration of multiprocessor arrays, J. Paraller Distrib. Comput., 74, 3026, 10.1016/j.jpdc.2014.06.009