Perbaikan Internal Blocking pada Jaringan Benes 8x8 Menggunakan Algoritma Complete Residue Partition Tree (CRPT)

Abstract

Generally multi-level interconnection networks (Multistage interconnection Network/MIN) is blocking in nature there is always there are input-output connections that cannot be realized by this network.One type of MIN network is the Benes network. Because unique interconnection pattern between levels, many non-blocking algorithms have been proposed by experts for this network. for this network. In this paper, research is conducted on the Complete Residue Partition Tree (CRPT) algorithm. which aims to overcome the blocking nature of the Benes network. This algorithm utilizes a binary tree called Complete Residue Partition Tree, to divide the bits of the destination address so that an input-output path is formed based on the tree division. However, after some testing with a number of permutations, it turns out that some of the input-output connections of the tested permutationsexperience blocking. This means that the CRPT algorithm is not fully able to overcome blocking in every permutation. Next came a routing algorithm called the novel routing algorithm. This algorithm works based on routing matrix. Connect the input switches and the inputs of each input switch form a matrix. matrix. At each level a matrix is formed. Except for the last 3 (three) levels, routing is based on the bits of the destination address assigned to the permutation. In this study, 5 different permutations (input-output connections) were tested and implemented on a Benes 8x8 network. Initially, the test was conducted Of the 5 tests conducted with CRPT, 3 permutations were successfully non-blocking and two permutations experienced blocking on some of their input-output connections. Furthermore, the two permutations that experienced blocking to him implemented a novel routing algorithm that eventually all the inputoutput connections of the permutation became non-blocking. input-output connections of the permutation become non-blocking. From the tests that have been carried out, it is obtained that the novel routing algorithm can improve the blocking results in the CRPT permutation.