A dynamic programming approach for layout optimization of interconnection networks

The reliability and cost are two important performance measures of an interconnection network. Both these aspects need to be attended at the layout design stage for an appropriate trade-off between them. This paper introduces a new approach for layout optimization of interconnection networks using dynamic programming. Our principal objective here is to optimize the network layout so as to maximize the network reliability of a given network within some predefined cost constraint. Since the above problem is NP-hard, a new technique based on dynamic programming is proposed to locate the optimal positions of the nodes and links in the network. The proposed method is illustrated through an example. We also present experimental results for a wide range of interconnection networks. The proposed method is found to be efficient and is applicable for large sized interconnection networks.