Open AccessCNF-SAT modelling for banyan-type networks and its application for assessing the rearrangeability
Author(s) -
Satoru Ohta
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/2090/1/012133
Subject(s) - banyan , satisfiability , scheme (mathematics) , boolean satisfiability problem , computer science , type (biology) , multistage interconnection networks , solver , conjecture , routing (electronic design automation) , mathematics , combinatorics , algorithm , computer network , programming language , mathematical analysis , ecology , biology
A banyan-type network is a switching network, which is constructed by placing unit switches with two inputs and two outputs in s ( s > 1) stages. In each stage, 2 n – 1 (n > 1) unit switches are aligned. Past studies conjecture that this network becomes rearrangeable when s ≥ 2 n-1 . Although a considerable number of theoretical analyses have been done, the rearrangeability of the banyan-type network with 2n – 1 or more stages is not completely proved. As a tool to assess the rearrangeability, this study presents a CNF-SAT (conjunctive normal form - satisfiability) modelling scheme for banyan-type networks. In the proposed scheme, the routing is formulated to a SAT problem represented in CNF. By feeding the problem to a SAT solver, it is found whether the problem is satisfiable or unsatisfiable. If the problem is unsatisfiable for a certain request, the network is not rearrangeable. By contrast, if the problem is satisfiable for any requests, the network is rearrangeable. This study applies the CNF-SAT modelling scheme to various configurations of 2 n – 1 stage banyan-type networks. These networks are assessed for rearrangeability by solving the SAT problems. The proposed method will be helpful to conduct future theoretical studies on banyan-type networks.