SYSGEN Computational complexity analysis.

Let there be *n *TR processes in the system and let *PS={P _{0}...P_{n-1}}* be the set of processes. Let each process have at most

Let *cmap* specify the port to port connection mapping between the processes, where

*cmap(i, * *a* *)=(j, * *b* *)*

means that input port *a* on process *i* is connected to output port *b* on process *j*. The processes are scanned in order from *P _{0}* to

Let *U* be the set of all ports in the system of processes,

where *U* = *IN* union *OU*,

and *IN* intersect *OU* = null

and *IN* is the set of input processes and *OU* is the set of output processes.

Let *ports(i)* be the set of ports on process *i*, that is, the ports used in the port communications *IO _{i,0}* to

Let *ports(i) = iports(i)* union *oports(i) *and *iports(i) * *intersect* * oports(i) = * *null*, where *iports(i) *is the set of input ports on process *i* and *oports(i) *is the set of output ports on process *i*.

*cmap* : *N _{n} x*

*cmap* is a *valid mapping* iff for every *cmap(i, * *a* *)=(j, * *b* *)*,

- *i* *!=* *j* and *0**<=** i * *<=* * n, 0 * *<=* * j * *<=* *n*

- *a* in iports(i)

- *b* in oports(j)

*cmap* is irreflexive: there exists no elements of the form *cmap(i, * *a* *)=(i, * *a* *)*

*cmap* respects processes: there exist no elements of the form *cmap(i, * *a* *)=(i, * *b* *)*

*cmap* connects PS:

*"* *a* *in* * IN * and for some *j* and *b* *in* * OU*, there exists an element of *cmap*: *cmap(i, * *a* *)=(j, * *b* *)*; and,

*"* *b* *in* * OU* and for some *i* and *a* *in* * IN*, there exists an element of *cmap*: *cmap(i, * *a* *)=(j, * *b* *).*

*cmap* is invertable if there is a unique image *(j, * *b* *)* for each *cmap(i, * *a* *)*

*cmap* is bijective if it is invertible and there is a single *(j, * *b* *)* for each *cmap(i, * *a* *)*

*Principle of finite progress*: Let each process *P _{i}* be just about to execute its port communication operation

Case 1: *cmap* is irreflexive, respects processes, connects PS and is bijective.

1. for all *i, top(i)=0*,*done(i)=false*

2. while there is one *i* such that *!done(i)*

3. let *a* * = port(IO _{i,top(i)})*

4. *cmap(i, * *a* *)=(j, * *b* *)* must exist since *cmap* connects P and

there is only one since *cmap* is bijective

5. check if *port(IO _{j,top(j) })* =

6. *top(j) +=1*, if *top(j)>m* then *done(j)=true*

7. *top(i) +=1*, if *top(i)>m* then *done(i)=true*

Termination: on every loop, *top(i) *and *top(j*) each increase by one or else violation; top() starts from 0 and is bounded from above by *m*.

The total number of *IO* operations is *n*m*, and since 2 IO operations are completed with each loop iteration complexity is *n*m/2*.

ÿ

If we relax the assumption that cmap is bijective, then an input operation may have its port connected to *several* output ports.

Dynamic fan-in and fan-out on ports is restricted to degree 1: this means that if an input port is connected to *q* output ports, this is just the same as *q* separate communication operations in sequence; if an output port is connected to *q* input ports, this is the same as *q *separate communication operations in sequence.

Let (fan-out) *FO(j,k) = { (i, * *a* *) : cmap(i,**a**) =(j,** port(j,k)**) }* and

Let (fan-in) *FI((i,k) = { (j,* *b* *): cmap(i,** port(i,k)**) =(j,**b**) }* where *port(i,k)* is the port used in operation *IO _{i,k}*

Case 2: *cmap* is irreflexive, respects processes, connections PS and is invertable with dynamic fan-in/out restricted to 1.

For all processes *i*, *IO _{i,top(i)}* there is at most one other process

Let *fi(IO _{i,k})* be the degree, number of different

Where *port(i,k)* is the port used in operation *IO _{i,k}*

_{ }

Step 4 is modified since more than one *(j, * *b* *)* could exist, however, with the assumption of dynamic fan-in/our restricted to degree one, there is at most one that is *top(j)* for some process *j*.

The total number of IO operations is still *n*m*; however, on each operation we may need to search a fan-on *FO(j,k)* or fan-out *FI(i,k)* set. Since the largest that each such set could be is the maximum number of input or number of output ports, *P = max(|IN|,|OU|), *the worst case complexity would be *P_*( _n*m/2).*

ÿ

If we relax the restriction on dynamic fan-in/out, then each time we encounter an operation in process *i*, with *IO _{i,top(i)}* there will be in the worst case

Case 3: *cmap* is irreflexive, respects processes, connections PS and is invertable with no dynamic fan-in/out restriction, and all orderings of communications must be examined to determine if a) any order exists in which all IO operations are matched or b) amy order exists in which all IO operations are not matched.

The maximum size of an *FI* or *FO* set is *P *and in the worst case all *m * IO operations will have this number of choices, resulting in an exponential complexity *P ^{(n*m)/2}.*

IO operations composed with Parallel-min and Parallel-max compositions impose additional constraints on the IO matching process:

Parallel-max: all the operations in composition must be matched, but they can be matched in any order.

Parallel-min: any one operation in the composition can be matched, but not more than one.

Case 4: *cmap* is irreflexive, respects processes, connections PS and is invertable with dynamic fan-in/out restriction of 1, and including parallel-min compositions.

Parallel-min presents a choice at step 4 in the same manner that *FI* or *FO* would. However, in this case, as long as there is any match for step 5, it is sufficient. Since the number of choices available in the Parallel-min composition is still at most *P*, the complexity is not changed beyond *P_*( _n*m/2).* In fact, because the parallel-min includes *P* of the *m* IO operations, and because only one of these needs to be considered, it reduces the complexity to *P*(n*(m-P))/2= P*(n*m/2) – P ^{2}*n/2.*

Case 5: *cmap* is irreflexive, respects processes, connections PS and is invertable with dynamic fan-in/out restriction of 1, and including parallel-max compositions.

Parallel-max also presents a choice at step 4 in the same manner that *FI* or *FO* would. However, all the m operations still need to be carried out, so there is no reduction in complexity as seen above.

<meta name="robots" content="noindex" />

-- (c) Fordham University Robotics and Computer Vision

This topic: Main > WebHome > FordhamRoboticsAndComputerVisionLaboratory > FRCVProjects > DTRA > PARS-verification > ComputationalComplexityOfSysGen

Topic revision: r1 - 2013-06-13 - DamianLyons

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback