MVAMIN: Mean value analysis algorithms for multistage interconnection networks (Q1177279)

This paper deals with the queuing model for a class of multiprocessor interconnection networks operating in an asynchronous packet-switched buffered mode. The multiprocessor consists of \(N\) processors and \(N\) memory modules connected together through a multistage interconnection network. The interconnection networks consists of \(\log_ 2 N\) stages of \(2\times 2\) crossbar switches with \(N/2\) such switches per stage. A processor requests access to memory modulles with a fixed probability. The requests are fixed size packets which include the address of the memory. The multistage interconnection model consists of delay centers representing the processors and single-server First Input First Served centers representing the switches and the memories. Each switch has an infinite buffer in it. The mean value analysis algorithm is used. To characterize the performance of the network the response time, i.e. the amount of time, the processor has to wait from the time it issues a memory request to the time it receives the reply from the memory is used. The model contains \(N\) customer classes for an \(N\times N\) network. Both tighlty coupled (processors connected to memory modules only through multistage interconnection network) and loosely coupled (processors have local memories) are considered. The obtained results show that loosely coupled systems perform better than thighly coupled systems in terms of cost effectiveness. Analytical results have been checked against simulation results and the agreement in the range of 1\% is achieved. The interesting modification of the method is ``service center aggregation'' which reduces by a factor of \(O(\log_ 2 N)\) the computational complexity.