12.4 Case III: Petri net example

---

12.4 Case III: Petri net example

We could look at the same problem from a Petri net perspective. In this case we make some of the same assumptions: There are n_p processors, n_m shared memory modules, and n_b data buses. In the previous theoretical analysis we ignored the data buses. Each of the processors has local memory, which gets used until a page miss. At this point an access to an external memory module is required, resulting in a new page being loaded into the local processor memory. The miss rate is exponentially distributed and set at 1/λ. The access time to the shared memory is also assumed to be exponentially distributed with mean 1/μ. If we originally set n_p = 5, n_m = 3, and n_b = 2, we have the initial configuration seen in Figure 12.9. The model depicted contains two places per memory module (one place for processor tokens and one place for bus tokens) and one timed transition (for memory allocation and use). There are also two immediate transitions associated with synchronizing and controlling the memory access. For the size model we postulated we would have nine total places, four timed transitions, and six immediate transitions. Tokens in place P₂ represent data buses available for use. Tokens in place P₁ represent processors executing on their local memory. An important assumption in this model is that every processor and memory module act in an identical manner.

Figure 12.9: Petri net model for multiprocessor system.

When a processor completes its local memory access (has a page miss resulting in firing transition t₁) and requires more shared memory resources, a token is moved from place P₁ to place P₃. A processor determines which memory it needs by firing the immediate transition, t₂, on the memory module it has chosen using a probabilistic branch. Once t₂ fires, a token is moved from place 3 to place 4. Once a token is in place 4, the processor is requesting access to a data bus. The bus is used to connect the processor to the memory module. The processor acquires the memory desired, and then acquires a data bus to retrieve the needed information. Once a processor has the bus, signaled by the firing of transition t₃, and has acquired the memory (indicated by the token in place, p₅), it begins to model using the memory module by initiating the timer on transition t₄. Upon completion of using the bus, the token representing the processor and the bus are routed back to their initial places, P₂ and P₁.

If we run this model with inputs similar to what were applied to the queuing model discussed previously, we would find results that very closely match the queuing model case. That is, we would find out that the effective processor power would be proportional to about 2.05 with the configuration as specified. We could improve on this if we made the access balanced, implying that no single processor could hold more than one memory at a time. This would increase our effective processor capacity to approximately 3.2.

---