Study of Connectivity Using AND and XOR Logical Operation on JOSEPHUS CUBE for Parallel and Distributed Systems Operation on JOSEPHUS CUBE for Parallel and Distributed Systems

Abstract:

Graph is a conceptual mathematical data structure. In this paper, Josephus cube (JC) architecture is studied as a graph. We consider Josephus architecture as a self-loop free graph. We study Josephus cube interconnection connectivity properties where vertices present the processor (nodes) and communication arcs / links as edges of the graph. Josephus cube architecture connectivity is presented through mathematical tool: Matrices to perform logical operations. Incidence Matrix, Circuit Matrix and Path Matrix were considered to map the graph properties to the matrix properties of Josephus Cube interconnection network.  Here we take matrix and in each matrix all columns are arranged using the same order of edges. Binary AND (.) logical operation is performed in MATLAB on the incidence matrix & transpose of circuit matrix and vice-versa for Josephus graph in this The result shows that, for any pth processor lies in the nth circuit, then the nonzero values in a matrix at corresponding position exist, if the particular communication link is incident on the pth processor (vertex) and is also in the nth circuit of the Josephus cube graph structure. Path matrix of Josephus cube was also presented to define all the connectivity’s between two processor nodes P(Px,Py). Here we observed that AND (.) logical operation was executed on the incidence matrix and transposed of path matrix, the resultant matrix has 1’s in exactly two rows Px and Py , the processor nodes for which we had considered all the possible paths and the rest of the (Rn-2) rows are filed with 0 bits, that confirms Px and Py nodes does not lies in any other connectivity paths. The XOR of any two rows of path matrix of Josephus cube corresponds to the circuit that contains the traversed paths.

Keywords: – Josephus Cube, Interconnection Network, Incidence Matrix, Circuit Matrix, Path Matrix, Transposed.

1Manisha Singh, 2Neha Singh, 3Prof. Rakesh Katare, 4Charvi Katare

IJIRG-09-12-101