The use of petri nets in the performance evaluation of shuffle-exchange network under uniform traffic distribution

Abstract EN

Many multistage interconnection networks (MINs) and single stage interconnection networks (SSINs) have been proposed for parallel computer systems and for fast packet switching in high speed networks.

There have been extensive studies on MINs but relatively little work on SSINs has appeared in the literature.

A SSIN consists of only one stage of switches.

Recirculation through processors is used to provide the desired source-destination permutations.

In this paper we evaluate the unbuffered shuffle-exchange network (SEN) topology of SSIN.

The behavior of the SEN is modeled probabilistically as a stochastic Petri net (SPN) graph.

An efficient model has been proposed to evaluate the performance of the network.

We have minimized the number of places and transitions to find an efficient and reasonable combination state.

We analyze the random delay experienced by a message traversing a SEN for a uniform traffic.

Messages can have different sizes.

The time between the generation of two consecutive requests is exponentially distributed.

Each sender can accept one packet per clock cycle and route it to the appropriate receiver.

It is shown that the unbuffered strategy is suited to long data transfer times.

The power of this approach is its simplicity to model the network and to compute the passing or blocking probabilities between states.