Theory

  

Figure 18: Application Graph showing processing nodes and data flow relationships for Quadtree Compression.

The application graph describing processing and data flow for the two level tree used in this quadtree compression implementation is shown in Figure 18. Since the tree only has one level, all communication is with the same amount of data. For the 256x256 integer arrays used for testing communication will consist of 131,072 Bytes. Processing time for leaf nodes is estimated to be 0.15s, and processing time at the end for task 2 is estimated to be 0.05s. As with the merge-sort algorithm, task allocation begins with arbitrarily picking a processor for the root.
Task 0
No other tasks are allocated, so

$$resp\_time(m_0)_i = 0 \cdot 0 + 0.$$

All choices are equal, so arbitrarily pick processor 0.
Tasks 1
Task 1a is allocated when task 0 is exiting, so don't consider task 0 to compete for processor time.

D₀ = D₁ = D₂ = D₃ = 0

$$resp\_time(m_{1a})_0 = resp\_time(m_{1a})_1 = 0 \cdot 0.15 + 0$$

No times will be less than 0, so allocate 1a to processor 0.
Task 1b

D₀ = 1

D₁ = D₂ = D₃ = 0

$$resp\_time(m_{1a})_1 = 0 \cdot 0.15 + 0$$

No times will be less than 0, so allocate 1b to processor 1.
Now for task 1c.

D₀ = D₁ = 1

D₂ = D₃ = 0

$$comm\_time(m_1c)_0 = comm\_time(m_1c)_1 = 0$$

$$comm\_time(m_1c)_2 = comm\_time(m_1c)_3 = 0.0089s (ServerNet) or 0.23s (TCP)$$

$$resp\_time(m_{1c})_0 = resp\_time(m_{1c})_1 = 1 \cdot 0.15s + 0 = 0.15s$$

$$resp\_time(m_{1c})_2 = resp\_time(m_{1c})_3 = 0 \cdot 0.15s$$

+ 0.0089s (ServerNet) or 0.23s (TCP) = 0.0089s (ServerNet) or 0.23s (TCP)

The results are much like those for merge-sort. We expect that for ServerNet task 1c should be allocated to processor 2, and for TCP/IP it should be allocated to processor 0. However, the numbers for TCP/IP in quadtree compression are much closer than they were for merge-sort. Quadtree compression requires more processing time per Byte passed than sorting did.
Task 1d will be examined in two parts, one for the ServerNet allocation, one for the TCP/IP allocation. First ServerNet:

D₀ = D₁ = D₂ = 1

D₃ = 0

$$comm\_time(m_1d)_0 = comm\_time(m_1d)_1 = 0$$

$$comm\_time(m_1d)_2 = comm\_time(m_1d)_3 = 0.0089s$$

$$resp\_time(m_{1d})_0 = resp\_time(m_{1d})_1 = 1 \cdot 0.15s + 0 = 0.15s$$

$$resp\_time(m_{1d})_2 = 1 \cdot 0.15s + 0.0089s = 0.1589s$$

$$resp\_time(m_{1d})_3 = 0 \cdot 0.15s + 0.0089s = 0.0089s$$

So allocate m_1d to 3. Now TCP/IP:

D₀ = 2

D₁ = 1

D₂ = D₃ = 0

$$comm\_time(m_1d)_0 = comm\_time(m_1d)_1 = 0$$

$$comm\_time(m_1d)_2 = comm\_time(m_1d)_3 = 0.23s$$

$$resp\_time(m_{1d})_0 = 2 \cdot 0.15s + 0 = 0.30s$$

$$resp\_time(m_{1d})_1 = 1 \cdot 0.15s + 0 = 0.15s$$

$$resp\_time(m_{1d})_2 = resp\_time(m_{1d})_3 = 0 \cdot 0.15s + 0.23s = 0.23s$$

So m_1d is allocated to processor 1.
Predicted processing times are: For ServerNet, 0.0089s + 0.15s + 0.0089s + 0.05s = 0.22sFor one node (TCP/IP allocation), 0.15s + 0.15s + 0.05s = 0.35sFor TCP/IP with ServerNet allocation, 0.23s + 0.15s + 0.23s + 0.05s = 0.66sSince the data involved in this algorithm gets compressed, possibly down to two integers, the factors in the above calculations which account for data passed from the 1 tasks to task 2 can in some cases disappear. Having fully compressible data would change the expected ServerNet time to 0.21s, and TCP/IP allocated to both workstations to 0.43s.