×

MVAMIN: Mean value analysis algorithms for multistage interconnection networks. (English) Zbl 0755.68026

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.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60K25 Queueing theory (aspects of probability theory)
68M10 Network design and communication in computer systems
Full Text: DOI