Computational Complexity

We estimate the speedup factor that can be achieved using query pack execution in two steps: first we consider one-level packs, then we extend the results towards deeper packs.

Lower and upper bounds on the speedup factor that can be achieved by executing a one-level pack instead of separate queries can be obtained as follows. For a pack containing $n$ queries $q_i = (a,b_i)$, let $T_i$ be the time needed to compute the first answer substitution of $q_i$ if there are any, or to obtain failure otherwise. Let $t_i$ be the part of $T_i$ spent within $a$ and $t'_i$ the part of $T_i$ spent in $b_i$. Then $T_s = \sum_i (t_i + t'_i)$ and $T_p = \max(t_i)+ \sum_i t'_i$ with $T_s$ representing the total time needed for executing all queries separately and $T_p$ the total time needed for executing the pack. Introducing $c = \sum_i t_i / \sum_i t'_i$, which roughly represents the ratio of the computational complexity in the shared part over that in the non-shared part, we have

$${T_s \over T_p} = {\sum_i t_i + \sum_i t'_i \over \max_i t_i... ...sum_i t'_i } = {c+1 \over { \max_i t_i \over \sum_i t'_i} + 1}$$ (1)

Now defining $K$ as the ratio of the maximal $t_i$ over the average $t_i$, i.e.

$$K = {\max_i t_i \over \sum_i t_i / n}$$

we can rewrite Equation (1) as

$${T_s \over T_p} = {c + 1 \over {K \over n}c + 1}$$ (2)

Since ${\sum_i t_i \over n} \leq \max t_i \leq \sum_i t_i$ we know $1 \leq K \leq n$, which leads to the following bounds:

$$1 \leq {T_s \over T_p} \leq {c+1 \over {c \over n}+1} < \min(c+1,n)$$ (3)

Thus the speedup factor is bounded from above by the branching factor $n$ and by the ratio $c$ of computational complexity in the shared part over the computational complexity of the non-shared part; and a maximal speedup can be attained when $\max t_i \simeq \sum t_i/n$ (or, $K \simeq 1$), in other words when the $t_i$ for all queries are approximately equal.

For multi-level packs, we can estimate the efficiency gain as follows. Given a query $q_i$, let $T_i$ be defined as above (the total time for finding 1 answer to $q_i$ or obtaining failure). Instead of $t_i$ and $t'_i$, we now define $t_{i,l}$ as the time spent on level $l$ of the pack when solving $q_i$; counting the root as level 0 and denoting the depth of the pack with $d$ we have $T_i = \sum_{l=0}^d t_{i,l}$. Further define $T_{i,l}$ as the time spent on level $l$ or deeper: $T_{i,l} = \sum_{j=l}^d t_{i,j}$ with $d$ the depth of the pack. (Thus $T_i = T_{i,0}$.). We will assume a constant branching factor $b$ in the pack. Finally, we define $\bar{t}_l = \sum_i t_{i,l}/n$ with $n = b^d$. For simplicity, in the formulae we implicitly assume that $i$ always ranges from 1 to $n$ with $n$ the number of queries, unless explicitly specified otherwise. We then have

$$T_p = \max_i t_{i,0} + \sum_i T_{i,1} = \max_i t_{i,0} + \sum_{j=1}^b (\max_{i \in G_j} t_{i,1} + \sum_{i \in G_j} T_{i,2})$$ (4)

where $j=1 \ldots b$ is the index of a child of the root and $G_j$ is the set of indexes of the queries belonging to that child. Now define $K_0 = \max_i t_{i,0} / \bar{t}_0$ and define $K_1$ as the smallest number such that $\max_{i \in G_j} t_{i,1} \leq K_1 \bar{t}_{j,1}$ with $\bar{t}_{j,1} = \sum_{i \in G_j} t_{i,1} / b$. Note $1 \leq K_0, K_1 \leq b$. It then follows that

$$\sum_{j=1}^b \max_{i \in G_j} t_{i,1} \leq K_1 \sum_{j=1}^b \bar{t}_{j,1} = K_1 b \bar{t}_1$$ (5)

which allows us to rewrite Equation (4) into

$$T_p \leq K_0 \bar{t}_0 + K_1 b \bar{t}_1 + \sum_i T_{i,2}$$ (6)

where the equality holds if $\max_{i \in G_j} t_{i,1}$ is equal in all $G_j$. The reasoning can be continued up till the lowest level of the pack, yielding

$$T_p \leq K_0 \bar{t}_0 + b K_1 \bar{t}_1 + b^2 K_2 \bar{t}_2 + \cdots + b^{d-1} K_{d-1} \bar{t}_{d-1} + \sum_i t_{i,d}$$ (7)

and finally

$$T_p \leq K_0 \bar{t}_0 + b K_1 \bar{t}_1 + b^2 K_2 \bar{t}_2 + \cdots + b^{d-1} K_{d-1} \bar{t}_{d-1} + b^d \bar{t}_d$$ (8)

with all $K_l$ between 1 and $b$. We will further simplify the comparison with $T_s$ by assuming $\forall l: K_l = 1$; the $K_l$ can then be dropped and the inequality becomes an equality (because all maxima must be equal):

$$T_p = \bar{t}_0 + b \bar{t}_1 + b^2 \bar{t}_2 + \cdots + b^{d-1} \bar{t}_{d-1} + b^d \bar{t}_d$$ (9)

Note that for $T_s$ we have

$$T_s = b^d \bar{t}_0 + b^d \bar{t}_1 + b^d \bar{t}_2 + \cdots + b^d \bar{t}_{d-1} + b^d \bar{t}_d$$ (10)

It is clear, then, that the speedup will be governed by how the $b^d \bar{t}_k$ terms compare to the $b^k \bar{t}_k$ terms. (In the worst case, where $K_k = b$, the latter become $b^{k+1} \bar{t}_k$.) We therefore introduce $R_{l,m}$ as follows:

$$R_{l,m} = {\sum_{k=l}^m b^m \bar{t}_k \over \sum_{k=l}^m b^k \bar{t}_k}$$ (11)

The $R$ coefficients are always between 1 (if $\bar{t}_m$ dominates) and $b^{m-l}$ (if $\bar{t}_l$ strongly dominates); for all $\bar{t}_l$ equal, $R_{l,m}$ is approximately $m-l$.

Further, similar to $c$ in our previous analysis, define

$$c_l = {\sum_{k=0}^l b^k \bar{t}_k \over \sum_{k=l+1}^d b^k \bar{t}_k}$$ (12)

Some algebra then gives

$${T_s \over T_p} = {b^{d-l} c_l R_{0,l} + R_{l+1,d} \over c_l + 1}$$ (13)

which needs to hold for all $l$. We can interpret this as follows: for a certain level $l$, $c_l$ roughly reflects the speedup gained by the fact that the part up till level $l$ needs to be executed only once; the $R$ factors reflect the speedup obtained within these parts because of the pack mechanism.

This inequality holds for all $l$, hence we will find the best lower bound for the speedup factor by maximizing the right hand side. Note that $c_l$ increases and $b^{d-l}$ decreases monotonically with $l$. It is clear that if at some point $c_l$ becomes much larger than 1, a speedup factor of roughly $b^{d-l}$ is obtained. On the other hand, if $c_l$ is smaller than 1, then the behaviour of $b^{d-l} c_l$ is crucial. Now,

$$b^{d-l} c_l = {\bar{t}_l + {1 \over b} \bar{t}_{l-1} + \cdots... ...b} \bar{t}_{d-1} + \cdots + {1 \over b^{d-l-1}} \bar{t}_{l+1}}.$$

Our conclusion is similar to that for the one-level pack. If for some $l$, $c_l»1$, i.e., if in the upper part of the pack (up till level $l$) computations take place that are so expensive that they dominate all computations below level $l$ (even taking into account that the latter are performed $b^{d-l}$ times more often), then a speedup of $b^{d-l}$ can be expected. If $c_l « 1$, which will usually be the case for all $l$ except those near $d$, the speedup can roughly be estimated as $\bar{t}_l / \bar{t}_d$. The maximum of all these factors will determine the actual speedup.