ALLOCATION AND MAPPING BASED RELIABILITY-ANALYSIS OF MULTISTAGE INTERCONNECTION NETWORKS

Task allocation using cubic partitioning of multistage interconnection networks (MINs) offers several advantages over random allocation of r esources. The objective of this paper is to analyze MIN reliability co nsidering the cubic allocation algorithm. A comprehensive analytical m odel is derived for predicting reliability of MIN-based systems where tasks are allocated using the buddy strategy. System reliability with the free list allocation policy is computed via simulation, it is show n that the system reliability is dependent on the allocation algorithm and the free list policy is superior to the buddy scheme in this resp ect. Two types of mapping algorithms known as conventional and bit rev ersal are used on a baseline MIN to show that the same allocation algo rithm can result in different reliability and performance. A performan ce-related reliability measure is analyzed using probability of accept ance as the performance measure to demonstrate the trade-offs between performance and reliability.