Load Balancing on the Biswapped Network

BSN is related to well-known swapped or OTIS networks, and is promising because of their attractive performance attributes including structural symmetry and algorithmic efficiency. It is a recently proposed network model of parallel computing, which is built of 2n copies of an n-node basic network, and its basic network may be hypercube, mesh and other networks, hence we can construct BSN-Hypercube and BSN-Mesh by using hypercube and mesh as basic network. BSN uses a simple rule for connectivity to ensure its regularity. Lots of algorithms such as basic communication operations algorithms, matrix multiplication algorithm and parallel sorting algorithm on the BSN have been developed, and some topological properties of BSN have been investigated. In this paper, we present load balancing algorithm on the BSN, and analyze this algorithm´s time complexity.