ComputationalComplexityOfSysGen < Main

Tags: view all tags
<span style="text-decoration: underline;">SYSGEN Computational complexity analysis.</span>

Let there be <em>n </em>TR processes in the system and let <em>PS={P<sub>0</sub>...P<sub>n-1</sub>}</em> be the set of processes. Let each process have at most _m_ input/output operations.

Let _cmap_ specify the port to port connection mapping between the processes, where

 <em>cmap(i, </em> _a_ <em>)=(j, </em> _b_ <em>)</em>

means that input port _a_ on process _i_ is connected to output port _b_ on process _j_. The processes are scanned in order from <em>P<sub>0</sub></em> to <em>P<sub>n-1</sub></em> (left to right) and for each process <em>i </em>from the first ocurring port intput/out operation <em>IO<sub>i,0</sub></em> to the last ocurrring one <em>IO<sub>i,m-1</sub></em><sub> </sub>(i.e. top to bottom).

Let _U_ be the set of all ports in the system of processes,

where _U_ = _IN_ union <em>OU</em>,

and   <em>IN</em> intersect <em>OU</em> = 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 <em>IO<sub>i,0</sub></em> to <em>IO<sub>i,m-1</sub></em><sub> </sub>for process _i_.

Let _ports(i) = iports(i)_ union <em>oports(i) </em>and <em>iports(i) </em> _intersect_ <em> oports(i) = </em> _null_, where <em>iports(i) </em>is the set of input ports on process _i_ and <em>oports(i) </em>is the set of output ports on process _i_.

_cmap_ : <em>N<sub>n</sub> x</em><em> IN x</em><em> N<sub>n</sub> x OU</em>

_cmap_ is a _valid mapping_ iff for every <em>cmap(i, </em> _a_ <em>)=(j, </em> _b_ <em>)</em>,

 - _i_ <em>!=</em> _j_ and <em>0</em><em>&lt;=</em><em> i </em> _&lt;=_ <em> n, 0 </em> _&lt;=_ <em> j </em> _&lt;=_ _n_

 - _a_ in iports(i)

 - _b_ in oports(j)

_cmap_ is <span style="text-decoration: underline;">irreflexive</span>: there exists no elements of the form <em>cmap(i, </em> _a_ <em>)=(i, </em> _a_ <em>)</em>

_cmap_ <span style="text-decoration: underline;">respects processes</span>: there exist no elements of the form <em>cmap(i, </em> _a_ <em>)=(i, </em> _b_ <em>)</em>

_cmap_ connects PS: 

_"_ _a_ _in_ <em> IN </em> and for some _j_ and _b_ _in_ <em> OU</em>, there exists an element of _cmap_: <em>cmap(i, </em> _a_ <em>)=(j, </em> _b_ <em>)</em>; and,

_"_ _b_ _in_ <em> OU</em> and for some _i_ and _a_ _in_ <em> IN</em>, there exists an element of _cmap_: <em>cmap(i, </em> _a_ <em>)=(j, </em> _b_ <em>).</em>

_cmap_ is <span style="text-decoration: underline;">invertable</span> if there is a unique image <em>(j, </em> _b_ <em>)</em> for each <em>cmap(i, </em> _a_ <em>)</em>

_cmap_ is <span style="text-decoration: underline;">bijective</span> if it is invertible and there is a single <em>(j, </em> _b_ <em>)</em> for each <em>cmap(i, </em> _a_ <em>)</em>

_Principle of finite progress_: Let each process <em>P<sub>i</sub></em> be just about to execute its port communication operation <em>IO<sub>i,top(i)</sub></em> where _top(i)_ in<em>{0..m-1}</em> and where <em>IO<sub>i,top(i)</sub></em><sub> </sub>is an operation on port <em>a</em> _in_ <em> iports(i).</em> For <em>P<sub>i</sub></em> to be able to execute, <em>IO<sub>i,top(i)</sub></em><sub> </sub>there has to be another process _j_ such that <em>cmap(i, </em> _a_ <em>)=(j, </em> _b_ <em>)</em>, and <em>IO<sub>j,top(j)</sub></em><sub> </sub>is an operation on port _b_ _in_ _oports(j)._ If that is the case, both processes can now take a finite step forward in their computation, and both <em>top(i) </em>and<em> top(j)</em> can increment by one.

<span style="text-decoration: underline;">Case 1:</span> _cmap_ is irreflexive, respects processes, connects PS and is bijective.

1. for all _i, top(i)=0_,<em>done(i)=false</em>

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

          3. let _a_ <em> = port(IO<sub>i,top(i)</sub>)</em>

          4. <em>cmap(i, </em> _a_ <em>)=(j, </em> _b_ <em>)</em> must exist since _cmap_ connects P and

there is only one since _cmap_ is bijective

          5. check if _port(IO<sub>j,top(j) </sub>)_ = _b_, if not principle of finite progress is violated

          6. _top(j) +=1_, if _top(j)&gt;m_ then _done(j)=true_

          7. _top(i) +=1_, if _top(i)&gt;m_ then _done(i)=true_

Termination: on every loop, <em>top(i) </em>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_.
<p align="right">ÿ</p>

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 <span style="text-decoration: underline;">is restricted to degree 1</span>: 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 <em>q </em>separate communication operations in sequence.

Let (fan-out) <em>FO(j,k) = { (i, </em> _a_ <em>) : cmap(i,</em><em>a</em><em>) =(j,</em><em> port(j,k)</em><em>) }</em> and

Let (fan-in)  _FI((i,k) = { (j,_ _b_ <em>): cmap(i,</em><em> port(i,k)</em><em>) =(j,</em><em>b</em><em>) }</em> where _port(i,k)_ is the port used in operation <em>IO<sub>i,k</sub></em>

<span style="text-decoration: underline;">Case 2:</span> _cmap_ is irreflexive, respects processes, connections PS and is invertable with dynamic fan-in/out restricted to 1.

For all processes _i_, <em>IO<sub>i,top(i)</sub></em> there is at most one other process <em>j, </em>and <em>IO<sub>j,top(j)</sub></em><sub> </sub>such that _cmap(i,port(top(i)))=(j,port(top(j)))._

Let _fi(IO<sub>i,k</sub>)_ be the degree, number of different <em>(j,</em><em>b</em><em>) </em>for which <em>cmap(i,port(i,k))= (j,</em><em>b</em><em>)</em>

Where _port(i,k)_ is the port used in operation <em>IO<sub>i,k</sub></em>

<sub> </sub>

Step 4 is modified since more than one <em>(j, </em> _b_ <em>)</em> 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, <em>P = max(|IN|,|OU|), </em>the worst case complexity would be _P_*( _n*m/2)._
<p align="right">ÿ</p>

If we relax the restriction on dynamic fan-in/out, then each time we encounter an operation in process _i_, with <em>IO<sub>i,top(i)</sub></em> there will be in the worst case _FI(i,top(i))_ (and equivalently for fan-out) cases to consider. The problem is that selecting one of these cases may result in later being unable to match step 5 in the algorithm; therefore, all the different choices need to be explored to see if at least one allows all IO operations to be matched.

<span style="text-decoration: underline;">Case 3:</span> _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 <em>P </em>and in the worst case all <em>m </em> IO operations will have this number of choices, resulting in an exponential complexity _P<sup>(n*m)/2</sup>._
<p align="right"> </p>

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

<span style="text-decoration: underline;">Parallel-max:</span> all the operations in composition must be matched, but they can be matched in any order.

<span style="text-decoration: underline;">Parallel-min:</span> any one operation in the composition can be matched, but not more than one.

<span style="text-decoration: underline;">Case 4: </span> _cmap_ is irreflexive, respects processes, connections PS and is invertable with dynamic fan-in/out restriction of 1, and including parallel-min compositions.

<span style="text-decoration: underline;"> </span>

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) &ndash; P<sup>2</sup>*n/2._
<p align="right"> </p>

<span style="text-decoration: underline;">Case 5: </span> _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.

<span style="color: #7a4707; font-family: 'Courier New', courier, monaco, monospace; white-space: pre;">&lt;meta name="robots" content="noindex" /&gt;</span>

-- (c) Fordham University Robotics and Computer Vision
Topic revision: r1 - 2013-06-13 - DamianLyons