On the Crossing Number of ToriProceeding: The Fourth International Conference on Electronics and Software Science (ICESS2018)
Publication Date: 2018-11-05
Authors : Antoine Bossard; Keiichi Kaneko; Frederick Harris;
Page : 55-64
Keywords : VLSI; Interconnect; Network; Intersection; Circuit;
Reducing the number of link crossings in a network to a minimum is a difficult problem which has nonetheless important applications. Circuit design with very-large-scale integration (VLSI) is an example of such an application. This problem is known as the crossing number problem. Finding a general solution to this problem has been shown to be NP-hard. Hence, solutions for particular classes of graphs have been proposed. In this paper, we focus on tori as they have proven very popular as interconnection network of massively parallel systems; see for instance the Fujitsu K and Cray Titan supercomputers. We start by devising an optimal upper bound on the crossing number of a twodimensional k-ary torus. This first result is extended to obtain an upper bound on the crossing number of a three-dimensional k-ary torus. Finally, we derive from these discussions an upper bound on the crossing number of a k-ary n-dimensional torus. The proposed bounds and drawing methods are empirically evaluated with experiments involving system-generated torus drawings and the automatic calculation of their crossing numbers.
Other Latest Articles
Last modified: 2019-01-20 20:49:14