A dynamic programming approach for layout optimization of interconnection networks

Engineering Science and Technology, an International Journal

Ranjan Kumar Dash¹  Pradyumna Kumar Tripathy²  Chitta Ranjan Tripathy³ 

[1] Department of Computer Science and Application, College of Engineering and Technology, Bhubaneswar, Odisha, India;Department of Computer Science and Engineering, Silicon Institute of Technology, Bhubaneswar, Odisha, India;Sambalpur University, Odisha, India;

关键词: Layout optimization;    Dynamic programming;    Network reliability;    Interconnection networks;   

DOI  :  10.1016/j.jestch.2015.01.003

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown