Let there be n TR processes in the system and let PS={P₀...P_n-1} 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

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₀ to P_n-1 (left to right) and for each process i from the first ocurring port intput/out operation IO_i,0 to the last ocurrring one IO_i,m-1 (i.e. top to bottom).

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 IO_i,m-1 for process i.

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 IN x N_n x OU

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 IO_i,top(i) where top(i) in{0..m-1} and where IO_i,top(i) is an operation on port a in iports(i). For P_i to be able to execute, IO_i,top(i) there has to be another process j such that cmap(i, a )=(j, b ), and IO_j,top(j) 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 top(i) and top(j) can increment by one.

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) ) = b, if not principle of finite progress is violated

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 j, and IO_j,top(j) such that cmap(i,port(top(i)))=(j,port(top(j))).

Let fi(IO_i,k) be the degree, number of different (j,b) for which cmap(i,port(i,k))= (j,b)

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 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.

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²*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