Graphics Programs Reference
In-Depth Information
task per processor. Fig.
11.3
shows the GSPN model of the behaviour of a
processor in the case in which the requests are preemptive, whereas Fig.
11.4
depicts the case in which requests are not preemptive. In both cases the local
computation is modelled by a place p
loc rdy
and a transition T
loc ex
with rate
λ, the completion of the local computation is modelled by place p
ext acc
, and
the request for service towards the neighbours is modelled by the transitions
t
ext acc 1
and t
ext acc 2
.
Under the preemptive policy (Fig.
11.3)
, the external requests are immedi-
ately served (firing of transition t
start req 1
or t
start req 2
), preempting any
local computation. The local computation may resume only when no further
external requests are pending.
In the non-preemptive case (Fig.
11.4)
, service is given to neighbours only
at the end of the local computation. In this case, at the end of the local
operation priority is given to accepting and serving requests from the neigh-
bours rather than to issuing the local request. The priority of immediate
transitions t
start req 1
and t
start req 2
is higher than that of immediate tran-
sitions t
ext acc 1
and t
ext acc 2
. If the two groups of transitions have the same
priority a deadlock may occur. Consider the case with two processors and
assume both executing local activities (place p
loc rdy
of both processors have
a token). When T
loc ex
of processor 1 fires a token is moved to p
ext acc
and
transition t
ext acc 2
of the same processor is enabled and its firing submits
a request to processor 2. If the next transition to fire is T
loc ex
of processor
2 transition t
ext acc 1
of processor 2 will be enabled together with transition
t
start req 1
when T
loc ex
of processor 2 fires. If now transition t
ext acc 1
is
chosen to fire the net reaches a condition on which no transition is enabled.
11.3
Single Processor Model with Multitasking
distinguish between processor state and task state. As a consequence, when
a task has completed its local execution phase and has been dispatched to
one of the neighbours by the owner processor, the processor is not able to
provide service to incoming requests. In actual concurrent architectures,
e
ciency in use of the processing power dictates the following constraints
for any reasonable scheduling policy:
1. if no external request is pending and the ready-task pool is not empty,
a local task is immediately scheduled for execution;
2. if the ready-task pool is empty but there are external requests pending,
service of an external request is immediately scheduled for execution;
3. if the ready-task pool is not empty and there are external requests
pending, either a local task or service of an external request is imme-
diately scheduled for execution.
Search WWH ::
Custom Search