MODELS OF CONCURRENT ARCHITECTURES - Modelling with Generalised Stochastic Petri Nets - page 255

Mesh size and interaction policy No. of states

2 × 2, preemptive 57

2 × 3, preemptive

833

3 × 3, preemptive 58681

2 × 2, not preemptive 117

2 × 3, not preemptive 2176

3 × 3, not preemptive

215712

Table 11.1: Number of tangible states for different mesh sizes and interaction
policies (simplified models)

Mesh size and interaction policy No. of states
2 × 2, preemptive 57
2 × 3, preemptive 939
3 × 3, preemptive 81893
2 × 2, not preemptive 189
2 × 3, not preemptive 4692
3 × 3, not preemptive 300000

Table 11.2: Number of tangible states for different mesh sizes and interaction
policies (models in Figs. 5 and 6 with k = 1)

models, all places are covered by P-invariants so that the net is bounded.
Furthermore, the number of T-invariants is given by the sum over all pro-
cessors of the number of neighbours and all transitions are covered by T-
invariants. This last result is a necessary condition for liveness and re-
versibility of bounded nets.
Table 11.1 reports the number of tangible states for the simplified models in
Figs. 11.3 and 11.4, whereas Table 11.2 reports the number of states for the
models in Figs. 11.5 and 11.6 with k = 1. With the simpler model, reacha-
bility graph construction for the 3 × 3 mesh with non-preemptive interaction
among processors takes about 1 hour of CPU time on a SUN4 SPARCsta-
tion 1+ equipped with 16 Mbyte RAM, thus approaching the computational
limits of GreatSPN on this workstation. With the more elaborate model,
the analysis of the 3 × 3 mesh exceeds these limits.
Tables 11.3 and 11.4 show some performance figures obtained from the quan-
titative analysis assuming λ = 1 and µ = 10. For all these models we can
distinguish the processor performance figures according to the number of
neighbours. Given the uniform workload, within each model, all processors
with the same number of neighbours exhibit the same performance figures.
Specifically, the idle time (time spent by the processors waiting for service) is
reported in Tables 11.3 and 11.4, along with the overall effective processing
power. In all models each processor can be in one of the following states: