Quantitative analysis of permutation capability with colored petri nets

Abstract

Given a multistage interconnection network (MIN) the calculation of the number of permutations of its input terminals into its output terminals is a classical difficult problem. In this paper, we introduce a novel technique to analyze the permutation capability of a MIN based on Colored Petri Nets (CP-nets or CPNs). We show how to verify whether a MIN is rearrangeable through the state space analysis of the associated CP-net. Also the permutation capability of non-rearrangeable MINS is measured in terms of the permutations that can be generated. The proposed approach takes advantage of powerful,existing software tools for the analysis of CP-nets. CPNTools software is, in particular used to explore the occurrence graphs of CP-nets in order to determine the set of permutations performed by the modeled MINs and so to measure their permutation capability.