Designing an Interconnection Network Using Genetic Algorithm

Abstract

This thesis describes the technique of evolutionary design which is aimed at designing an interconnection network. An Interconnection network is the communication path used in any digital subsystem and it is through them that the data is transferred between any two nodes. There is always willingness for obtaining shortest path between any source-destination pair. There are various performance parameters that need to be looked upon while constructing such paths in the network. Taking well care of these parameters leads to enhancement in the performance of the network. The parameters range from bisection width to cost to throughput. Therefore for obtaining optimal results, we need to take the performance analysis into consideration. For this purpose, here we construct the desired interconnection network by maximizing its bisection bandwidth and minimizing the cost of the network. However we know cost requires degree of the node, degree is given by number of links and bisection width is also dependent on the number of links. In this chaining, maximizing one and minimizing another leads to a tradeoff between the bisection bandwidth and the cost of the interconnection network. Now as we have to solve this difficult optimization problem, we do so by using Genetic Algorithm (GA). It indeed helps a lot in solving this tradeoff and constructs the network constrained to the parameters mentioned. As we turn to use Genetic Algorithm for optimization, we consider it much capable to solve such optimization problems which are humanly not possible to solve. The various GA operators like selection, crossover and mutation are applied which leads to the formation of new population on each iteration. The selection is carried out on each one of the chromosomes of the population based on the fitness function and thereby the best amongst them is considered. The offspring’s are obtained first through the crossover and then corresponding mutation operator is performed to rectify them. This is carried out for specified number of generations after which the fittest chromosome obtained is simulated on OMNeT++.This all leads to interpretation of that fittest chromosome as the interconnection network which is designed constrained to the performance parameters, optimized by the genetic algorithm and thus providing us with the optimized design results.