Time-Optimal Domain-Specific Querying on Enhanced Meshes.
AbstractQuery processing is a crucial component of various application domains including information retrieval, database design and management, pattern recognition, robotics, and VLSI. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the Batched Searching and Ranking problem, (BSR, for short) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries. Q is an arbitrary mix of the following query types: For a search query qj, one is interested in an item of A that is closest to qj; for a rank query qj one is interested in the number of items of A that are strictly smaller than qj. The BSR problem asks for solving all queries in Q. In this work, we consider the BSR problem in the following context: The matrix A is pretiled, one item per processor, onto an enhanced mesh of size $\sqrt n\times \sqrt n$; the m queries are stored, one per processor, in the first ${{m \over {\sqrt n}}}$ columns of the platform. Our main contribution is twofold. First, we show that any algorithm that solves the BSR problem must take at least $\Omega ({\rm max\{log}n,\sqrt m\})$ time in the worst case. Second, we show that this time lower bound is tight on meshes of size $\sqrt n\times \sqrt n$ enhanced with multiple broadcasting, by exhibiting an algorithm solving the BSR problem in $\Theta ({\rm max\{log}\!\!n,\sqrt m\})$ time on such a platform.
Introduction
Due to its simple and intuitive topology, the mesh has established
itself as one of the massively parallel architectures
suitable for solving problems in image processing, robot vi-
sion, computer graphics, path planning, and VLSI design,
among many others. At the same time, the mesh is notoriously
inefficient when it comes to handling non-spatially
organized data. To address this problem, mesh-connected
computers have been enhanced with various types of bus
systems [1], [22], [25], [28].
Recently, a powerful and elegant architecture, referred
to as mesh with multiple broadcasting, has been obtained
by endowing each row and column of the mesh with its
own dedicated high speed bus [22], [35]. The mesh with
multiple broadcasting has proven to be feasible for implementation
in VLSI and was adopted, among others, by the
DAP family of computers [35].
Being of theoretical interest as well as commercially
available, the mesh with multiple broadcasting has attracted
a great deal of well deserved attention. Applications
ranging from image processing [23], [35], to computer
graphics and robotics [6], [34], to computational geometry
and pattern recognition [5], [6], [9], [10], [12], [22], [27], [33],
to sorting and searching [8], [11], [22], to other fundamental
problems [3], [7], [13], [14] have found efficient solutions
Work supported by NASA grant NAS1-19858, by NSF grants CCR-
9407180 and CCR-9522093, and by ONR grant N00014-95-1-0779.
A preliminary version of this work has appeared in Proc. International
Conference on Application-Specific Array Processors, Stras-
bourg, France, July 1995. Correspondence to Prof. S. Olariu email
on this architecture and some of its variants [27].
Query processing is a crucial transaction in various application
domains including information retrieval, database
design and management, and VLSI. Many of these applications
involve data stored in a matrix satisfying a number
of properties. One property that occurs time and again in
applications specifies that the rows and the columns of the
matrix are independently sorted [16], [21], [30]. It is customary
to refer to such a matrix as sorted. A matrix is said
to be fully sorted if its entries are sorted in row-major (resp.
column-major) order. Figure 1a displays a sorted matrix;
Figure 1b features a fully sorted version of the matrix in

Figure

1a.
3 9 14 26
a b
Fig. 1. Illustrating sorted and fully sorted matrices
Sorted matrices provide a natural generalization of a
number of real-life situations. Consider vectors
and y j. The Cartesian sum of X
and Y , denoted Y is the
n \Theta
matrix A with
entries a It is clear that X +Y is a sorted ma-
can be stored succinctly in O(
n)
space [16], [19], since the entries a ij can be computed, as
needed, in constant time. The tasks of searching, ranking,
and selection in sorted matrices have received considerable
attention [16], [17], [19], [20], [21], [30].
The main goal of this paper is to look at the problem of
Batched Searching and Ranking (BSR, for short) in sorted
matrices. Throughout this work, a generic instance of the
BSR problem involves a sorted matrix A of size
n \Theta
stored one item per processor in a mesh with multiple
broadcasting of size
n and a collection Q of m,
queries stored in the first
columns of
the platform. The queries are of two types: for a query
q j of the first type one is interested in an item of A that
is closest to q j ; for a query q j of the second type one is
interested in the number of items in A that are strictly
smaller than q j . The two query types are referred to as
search queries and rank queries, respectively. The set Q of
queries is an arbitrary mix of the two query types. The
goal is to determine the solution of every query in Q.
It is important to note that search queries occur frequently
in image processing, pattern recognition, computational
learning, and artificial intelligence, where one is
interested in finding an item in the database that best
matches, in some sense, the query at hand [2], [18], [36].
On the other hand, rank queries are central to relational
database design, histogramming, and pattern analysis.
Here, given a collection of items in a database along with a
query, one is interested in computing the number of items
in the database that have a lesser value than the query. In
addition, rank queries finds applications to image process-
ing, robotics, and pattern recognition [2], [6], [18]. We note
here that a variant of rank queries have also received attention
in the literature. Specifically, a range query involves
determining the number of items in a given database that
fall in a certain range. It is easy to see that range queries
can be answered by stating them as rank queries [18].
At this point the reader may wonder why the m queries
lie in the leftmost
l
columns of the mesh. As we shall
discuss in Section II, we assume that the mesh with multiple
broadcasting communicates with the outside world via
I/O ports placed along the leftmost column of the platform.
This is consistent with the view [29] that enhanced meshes
can serve as fast coprocessors for present-day computers:
in such a scenario, the host computer passes the queries on
to the mesh in batches of
n and so, in the presence of m
input queries, the leftmost
l
columns will be used.
Our main contribution is twofold. First, we show that
any algorithm that solves the BSR problem must take at
least \Omega\Gammaast flog n;
time in the worst case. This lower
bound holds for both the CREW-PRAM and for the mesh
with multiple broadcasting. Second, we show that the BSR
problem can be solved time-optimally on a mesh with multiple
broadcasting of size
n \Theta
n by exhibiting an algorithm
whose running time matches the lower bound.
To put our contribution in perspective, we note that recently
Bhagavathi et al. [9] showed that the task of solving
m search or rank queries in a fully sorted matrix can be
performed in \Theta( p m) time on a mesh with multiple broadcasting
of size p n \Theta p n. Actually, in the context of fully
sorted matrices the difference between the two query types
vanishes, both of them being solved, essentially, in the same
way. In the context of sorted matrices, search queries and
rank queries are very much different, requiring a different
resolution strategy. It is not surprising, therefore, that our
algorithm for the BSR problem is much more complicated
and sophisticated that the algorithm in [9]. In order to
obtain a time-optimal algorithm for the BSR problem we
develop a novel and interesting cloning strategy for the
queries. The scenario is the following. We partition the
platform into a number of submeshes and clone the given
queries in each of them. Having done that, we obtain the
local solution of each query in each of the submeshes. Fi-
nally, since the number of clones of each query is large -
larger than the available bandwidth allows to handle - we
devise a strategy whereby we retrieve information gathered
by some of the clones only. The interesting feature of this
strategy is that there always exists a relatively small subset
of the clones that, when retrieved, allows the resolution of
all the queries. As a consequence, the algorithm devised in
this paper is completely different from that of [9], showing
the whole potential of meshes with multiple broadcasting.
The paper is organized as follows: Section II introduces
the model of computation; Section III presents the lower
bound arguments; Section IV discusses the time-optimal
algorithm for the BSR problem. Finally, Section V offers
concluding remarks and poses open problems.
II. The Computational Model
A mesh with multiple broadcasting of size M \Theta N , referred
to as a mesh when no confusion is possible, consists
of MN identical SIMD processors positioned on a rectangular
array overlaid with a high-speed bus system. In
every row of the mesh the processors are connected to a
horizontal bus; similarly, in every column the processors
are connected to a vertical bus as illustrated in Figure 2.
We assume that the processors in the first column serve as
I/O ports, as illustrated, and that this is the only way the
platform communicates with the outside world.
Fig. 2. A mesh with multiple broadcasting of size 4 \Theta 4
Processor P (i; j) is located in row i and column j, (1 -
in the northwest corner
of the mesh. Each processor P (i; j) has local links to its
neighbors
1), provided they exist. The processors are assumed to
know their own coordinates within the mesh and to have
a constant number of registers of size O(log MN ); in unit
time, the processors perform some arithmetic or boolean
operation, communicate with one of their neighbors using
a local link, broadcast a value on a bus, or read a value from
a specified bus. Each of these operations involves handling
at most O(log MN ) bits of information.
Due to physical constraints, only one processor is allowed
to broadcast on a given bus at any one time. By contrast,
all the processors on the bus can simultaneously read the
value being broadcast. In accord with other researchers [3],
[13], [22], [23], [25], [28], [35], we assume constant broadcast
delay. Although inexact, recent experiments with the
DAP the PPA and the YUPPIE multiprocessor array systems
seem to indicate that this is a reasonable working
hypothesis [25], [28], [35].
III. The Lower Bound
The purpose of this section is to establish a non-trivial
lower bound for the BSR problem on meshes with multiple
broadcasting. For this purpose, consider such a platform
of size
n \Theta
storing a sorted matrix of the same size.
As discussed, the m, (1 - m - n), queries are stored in
the first m
columns 1 of the mesh. Clearly, each processor
stores one item and at most one query.
Our lower bound arguments rely, in part, on the following
fundamental result of Cook et al. [15].
Proposition 3.1. [15] The time lower bound for computing
the logical OR of n bits on the CREW-PRAM is
\Omega\Gammas/2 n) no matter how many processors and memory cells
are available.
We also rely on the following result of Lin et al. [26].
Proposition 3.2. Any computation that takes O(t(n))
computational steps on an n-processor mesh with multiple
broadcasting can be performed in O(t(n)) computational
steps on an n-processor CREW-PRAM.
It is important to note that Proposition 3.2 guarantees
that if TM (n) is the execution time of an algorithm for solving
a given problem on an n-processor mesh with multiple
broadcasting, then there exists a CREW-PRAM algorithm
to solve the same problem in TP using n
processors and O(n) extra memory. In other words, "too
fast" an algorithm on the mesh with multiple broadcasting
implies "too fast" an algorithm for the CREW-PRAM.
This observation is exploited in [26] to transfer known computational
lower bounds for the CREW-PRAM to the mesh
with multiple broadcasting.
Fig. 3. Illustrating the lower bound for solving a single query
We shall prove that even solving a single query of the
search or rank type takes
n) time. This result will
be proved for the CREW-PRAM and then ported to the
mesh with multiple broadcasting by Proposition 3.2.
We begin by reducing the OR problem to the problem
of solving a search query q. For this purpose, let
be an arbitrary input to OR. Construct a
sorted matrix A, as illustrated in Figure 3, by placing
n; 1), and
by setting for all
ae
We assume for simplicity that m
n is an integer.
Our construction guarantees that the matrix A is sorted,
regardless of the values of b We assign query
q the value 0.9. It is easy to confirm that the answer to the
problem is 0 if and only if the solution of the query is
To see this, note that if the sequence b 1 contains
a 1, then 1 will be returned as a solution of the query.
Failing this, 0 will be returned. By virtue of Proposition
3.1, any algorithm that correctly answers a search query
on a sorted matrix must
n)=\Omega\Gamma615 n) time on
the CREW-PRAM, regardless of the number of processors
and memory cells available.
We continue by reducing the OR problem to the problem
of solving a rank query q. For this purpose, let
be an arbitrary input to OR. Construct a
sorted matrix A, as illustrated in Figure 3, and let the
query q have the value 0.9. It should be clear that the
answer to the OR problem is 0 if and only if the number
of elements of A that are smaller than q is exactly n+ p
nTo see this, observe that by construction, every element of
the matrix in the upper left triangle is strictly smaller than
the query and the only other elements that may be strictly
smaller than the query lie on the diagonal, as seen from

Figure

3. The reader should have no difficulty verifying
that the total number of elements strictly smaller than q is
only if all the elements on the diagonal are 0.
Now Proposition 3.1 guarantees that any algorithm that
correctly answers a rank query on a sorted matrix must
take\Omega\Gamma324 n) time on the CREW-PRAM.
By virtue of Proposition 3.2 we have the following result.
Lemma 3.3. Any algorithm that correctly solves one
search or rank query on a sorted matrix with n elements
must take at least \Omega\Gammaast n) time on a mesh with multiple
broadcasting of size
We now demonstrate that every algorithm that solves the
BSR problem on a fully sorted matrix must take \Omega\Gamma
m)
time in the worst case. This, of course, will imply the
same lower bound for sorted matrices. For this purpose,
we assume that we have a fully sorted matrix A, stored
in row-major order in a mesh with multiple broadcasting
of size
n \Theta
n. We refer to the elements of A, in row
major order, as a 1 ; a an . We note that, in the context
of fully sorted matrices, both search and rank queries are
solved, essentially, the same way. Specifically, let q be an
arbitrary query and let i be the subscript for which a i !
q - a i+1 . Clearly, if q is of rank type than its solution is
which denotes the number of items in A strictly smaller
than q. On the other hand, if q is of search type, then
the item in A that is closest to q is either a i or a i+1 . This
observation allows us to handle, for the purpose of the lower
bound, both type of queries as if they were rank queries.
In turn, this implies that we can use the following result
proved in Bhavagathi et al. [9].
Proposition 3.4. Any algorithm that correctly solves m,
queries on a fully sorted matrix with n elements
must take at
m) time on a mesh with
multiple broadcasting of size
n \Theta
n.
Lemmas 3.3 and 3.4, combined, provide the main result
of this section that we state next.
Theorem 3.5. Any algorithm that correctly solves an
instance of the BSR problem involving a sorted matrix of
items, stored one per processor, and a collection of m,
stored one per processor, in the first
columns of a mesh with multiple broadcasting of size
n \Theta
must take at least \Omega\Gammaast flog n;
mg) time.
IV. A Time-Optimal BSR Algorithm
A generic instance of the BSR problem involves a
sorted matrix A of size
n \Theta
n and a collection
of queries; a query q j can be
of the following types:
1. search type: determine the item of A that is closest to
2. rank type: determine the rank of q j in A, i.e., the
number of items in A that are strictly smaller than q j .
To avoid handling double subscripts, the items of A will
be enumerated, in row-major order, as a 1 ; a an . The
sorted matrix A is stored, one item per processor, in a
mesh R with multiple broadcasting of size
n \Theta
n. The
set Q is stored in the first m
columns of R, one query per
processor, as illustrated in Figure 4.
We shall view the mesh R as consisting of submeshes
m ), of size
m \Theta
m, with R i;j involving
processors P (r; c) with 1
m, as illustrated in Figure
5. Occasionally, we shall find it convenient to view
the mesh R as consisting of submeshes
of
size
m \Theta
n,
consisting of the
submeshes R i;1
. Each submesh S i will be
referred to as a slice of R as depicted in Figure 5.
Fig. 4. Illustrating the input to the BSR problem
In outline, our algorithm for the BSR problem proceeds
in the following three stages:
Stage 1. The set Q of queries is replicated in each sub-mesh
R i;j , creating local instances of the BSR problem

Stage 2. We determine in each submesh R i;j , in paral-
lel, the solution of the local instance of the BSR problem

Stage 3. The solutions of the local instances of the BSR
problem obtained is Stage 2 are combined into the
R
R 1,1
slice
slice
Fig. 5. Illustrating the partition into submeshes R i;j
solution of the original BSR problem.
The remainder of this section is devoted to a detailed description
of each of these stages.
Stage 1.
The purpose of this stage is to replicate the set Q of
queries, in each submesh R i;j , one query per processor.
Our plan is to move the queries in each column of R into
m columns of every R i;j . Specifically, the queries in a
will be moved to
columns
m of R i;j .
We now give the details of this data movement. For an
illustration the reader is referred to Figures 6(a)-(d). To
begin, every processor P
n), broadcasts
the query it holds horizontally to the diagonal processor
as shown in Figure 6(a,b). In turn, processor P (r; r)
broadcasts the query received vertically to every processor
as shown in Figure 6(b,c).
Fig. 6. Illustrating the data movement of Stage 1
As noted before, as a result of this data movement, the
queries originally stored in column k of R have been replicated
in the diagonal processors of the submeshes in every
slice. From now on, all slices are processed in parallel.
Specifically, the queries stored by the diagonal processors
of R i;1 are replicated, using the row buses in slice S i , into
the
-th column of each R i;j in slice S i .
Next, the queries stored by the diagonal processors in R i;2
are replicated, using the row buses in slice S i , into the
-th column of each R i;j , and so on (for
an illustration refer to Figure 6(d)).
It is easy to see that the task of replicating the
queries originally stored in one column of R takes O(
time. Therefore, as long as m -
n, the queries initially
stored in the leftmost m
columns of R can be replicated
in time O(
m). In case m !
the queries are replicated in a way similar to the one de-
scribed. The complexity of the data movement is, again,
O(
m). With this, the goal of Stage 1 has been achieved:
the queries have been replicated into each of the submeshes
R i;j . Thus, we have proved the following result.
Lemma 4.1. The set Q of queries initially stored in the
first m
columns of R can be replicated, one query per
processor, in each submesh R i;j in O(
m) time.
Stage 2.
It is important to note that, at the end of the Stage 1,
having replicated the set Q of queries in each submesh R i;j
we have, in fact, partitioned the original instance of the
BSR problem into several instances, each local to a R i;j .
Each local instance involves the subset of A stored by the
processors in R i;j and the entire set Q of queries.
The main goal of this stage is to solve the local instance of
BSR in each submesh R i;j . To avoid broadcasting conflicts,
in Stage 2 the bus system is ignored, and every submesh
R i;j will act as an unenhanced mesh. We begin by sorting
the items and queries in each R i;j in row-major order using
an optimal sorting algorithm for meshes [31]. We note that
in the sorting process ties are broken in favor of queries. In
other words, if a query and an item are equal, then in the
sorted version the query precedes the item.
Let C 2m be the resulting sorted
sequence stored, two items per processor in the submesh
R i;j . The following two results will justify our approach to
solving the local instances of the BSR problem.
Lemma 4.2. Let q k be a query on rank type and assume
that c in other words, q k occurs in position t in the
sorted sequence C i;j . The number of items in R i;j strictly
smaller than q k equals the number of items preceding q k in
C i;j .
Proof. Follows directly from the sortedness of C i;j along
with the assumed tie-breaking discipline.
Lemma 4.2 motivates the following strategy for solving
all rank type queries in R i;j . Assign to every c t a weight
defined as follows:
ae
is an item
is a query. (1)
Next, compute the prefix sums of the sequence
using the weights assigned in (1) and
2m be the result. By virtue of Lemma
4.2, the value e t corresponding to c is exactly the
number of items in R i;j strictly smaller than q k . Therefore,
all the rank queries can be solved in the time of sorting and
of prefix sums computation which is O( p m) [31], [32].
The task of handling search queries requires a different
approach. To motivate our strategy, consider again the
sorted sequence C and refer to

Figure

7.
item
query
l 1 l 3 l 4
Fig. 7. Illustrating the sorted sequence C i;j
The m queries occur in C i;j in the form of contiguous
subsequences for every such sequence s p let
l p and r p stand, respectively, for the leftmost and rightmost
query in s p , as illustrated in Figure 7. Of course, if the
sequence s p consists of one query only then l
2m. The motivation for this terminology becomes
clear once we observe that
Lemma 4.3. For all the search queries in some sequence
s p the solution is either c ff\Gamma1 or c fi+1 .
Proof. Let q k be an arbitrary search query in the sequence
s p . The sortedness of C i;j along with the tie-breaking discipline
guarantees that the no item in R i;j is closer to q k
than one of the items c ff\Gamma1 or c fi+1 .
In turn, Lemma 4.3 suggests the following approach to
solving all the search queries in R i;j . First, assign to every
c t a weight w t defined as follows:
ae
c t if c t is an item
is a query. (2)
Next, compute the prefix maxima of the sequence
using the weights assigned in (2) and
2m be the result. It is easy to confirm
that for every search query c , the corresponding value
e t is exactly the identity of the item c ff\Gamma1 in our previous
terminology, or \Gamma1 if no such item exists.
Next, assign to every c t a weight w t
ae
c t if c t is an item
is a query, (3)
and compute the prefix minima of the sequence
using the weights assigned in (3). Let
2m be the result. It is easy to confirm
that for every search query c , the corresponding value
e t is exactly the identity of the item c fi+1 in our previous
terminology, or +1 if no such item exists. Therefore, at
the end of these two computations, every search query q k
becomes aware of c ff\Gamma1 or c fi+1 . By virtue of Lemma 4.3
this is sufficient for the purpose of determining the solution
of every search query q k in R i;j . To summarize our finding
we state the following result.
Lemma 4.4. The task of solving the local instance of the
BSR problem in each submesh R i;j can be performed, in
parallel, in O(
m) time.
Stage 3.
At the end of Stage 2, each processor of a generic sub-mesh
R i;j stores, along with query q k , its local solution
In case q k is a search query oe(i; j; denotes the
item in A closest to q k ; in case q k is a rank query oe(i; j;
denotes the number of items in A that are strictly smaller
than q k . The goal of Stage 3 is to combine these local solutions
into the solution of q k in the original instance of the
BSR problem.
Fig. 8. Illustrating the proof of Lemma 4.5.
In preparation for this, the first task of this stage
is to arrange, in every submesh R i;j , the ordered pairs
in row-major order, sorted by subscript k.
Recall that using an optimal sorting algorithm for meshes
[31], this task can be performed in O(
m) time. Note that,
after sorting, the tuple (q occupies the same relative
position in each of the submeshes R i;j .
From now on, the processing relies heavily on a technical
property of sorted matrices that we discuss next. Referring
to

Figure

8, a submesh R i;j is said to be critical with respect
to a query q k if q k is larger than the entry a v in the
northwest corner of R i;j but not greater than the entry b v
in the southeast corner of R i;j , in other words:
a
The following result is key in deriving a time-optimal algorithm
for the BSR problem.
Lemma 4.5. If a submesh R i;j is critical with respect to
a query q k , then at most one of the submeshes R i\Gamma1;j and
R i;j+1 may be critical with respect to q k .
Proof. Referring, again, to Figure 8, let a u ; a v , and
aw stand for the items stored in the northwest corner of
respectively. Similarly, let b
and b w stand for the items stored in the southeast corner
of R i\Gamma1;j ; R i;j , and R i;j+1 , respectively.
Assume, further, that R i;j is critical with respect to
query q k . Now, if R i\Gamma1;j is critical with respect to q k , then
we have
a
and, since the matrix A is sorted
Now (5) and (6) combined guarantee that
and so, by (4), R i;j+1 cannot be critical with respect to q k .
Similarly, if R i;j+1 is critical with respect to q k , then we
have
and, since the matrix A is sorted
Now (7) and (8) combined guarantee that
confirming, by virtue of (4), that R i\Gamma1;j cannot be critical
with respect to q k . This completes the proof of Lemma 4.5.
R
Fig. 9. Illustrating the concept of active copy of query q k
Consider a generic slice S i . For further reference, we
shall call a copy of query q k in some submesh R i;j active if
one of the conditions (a1)-(a4) below is satisfied. We refer
the reader to Figure 9 for an illustration.
R i;j is critical with respect to query q k ;
(a2) slice S i contains no critical submesh with respect
to query q k and, for some
larger than
all items in R i;j but smaller than or equal to all items
in R i;j+1 ;
larger than all the items in slice S i ; in this
case the copy of q k in R i;
is active;
smaller than or equal to all the items in slice
this case the copy of q k in R i;1 is active.
The leftmost submesh of a slice containing an active copy
of a query q k will be referred to as leading with respect to
. At this point the reader may wonder how all this information
is computed. It is clear that for determining what
submeshes R i;j are critical with respect to a given query,
the only information needed are the values in the north-west
and southeast corners of the submesh. In O(
m)
time these values can be circulated within the submesh
and every processor becomes aware of them. Next, every
processor in R i;j needs to be informed about the values
of the items in the northwest and southeast corners of the
neighboring submeshes in its own slice. Again, this information
can be obtained in O(
m) time in the obvious way.
With this information available, critical submeshes and active
copies of all queries can be found in constant time.
Fig. 10. Illustrating the assignment of buses
Our strategy for combining the solutions of queries in
every R i;j into the global solution involves a considerable
amount of data movement. To restrict the running time
to \Theta(
m) we plan to use buses in support of this data
movement. Lemma 4.5 motivates us to assign buses to
active copies of queries according to the following rules,
illustrated in Figure 10:
(r1) the copy of q k that belongs to the leading submesh
in slice S i is assigned the horizontal bus in its own row;
(r2) all the remaining active copies of q k in S i are assigned
the vertical bus in their own column.
The following result shows that rules (r1) and (r2) lead to
conflict-free broadcasting.
Lemma 4.6. If every active copy of q k broadcasts simultaneously
on the assigned bus, no broadcast conflict will
arise.
Proof. First, we claim that no broadcast conflicts can
occur on horizontal buses. To see this, note that if the
horizontal bus was assigned to a copy of q k , then either
there exists only one active copy of q k in slice S i (in case
the copy of q k in the leading submesh is active by rules
(a2)-(a4)) and so no other copy of q k attempts to use the
same bus, or else, the copy comes from a critical submesh.
By rule (r2) all the other active copies in the same slice
will use vertical buses and, again, no conflict can arise.
Next, we show that no conflicts can arise on vertical
buses. Supposing the contrary, let i be the largest subscript
for which a broadcast conflict occurs when the copy of q k in
slice S i broadcasts vertically on its assigned bus. Without
loss of generality, assume that q k belongs to R i;j+1 . The
conclusion of Lemma 4.5, along with the maximality of i
imply that the copy of q k in submesh R i\Gamma1;j+1 is also using
the same vertical bus. This implies that neither R i\Gamma1;j+1
nor R i;j+1 are leading submeshes (with respect to q k ) in
slice S i\Gamma1 , and S i , respectively. However, now R i\Gamma1;j , R i;j ,
and R i;j+1 must be critical with respect to q k , contradicting
Lemma 4.5.
It is important to note that the total number of active
copies of any query q k is at most 2
m . This follows immediately
from Lemma 4.6, since the assignment of buses
to active copies of q k leads to no two copies using the same
bus. Since at most
m copies of q k are assigned horizontal
buses and at most
m copies of q k are assigned vertical
buses, the conclusion follows.
Next, one may wonder if the active copies of query q k
carry enough information to yield the correct overall solution
of q k . The answer to this natural question is provided
by the following results.
Lemma 4.7. Let q k be a search query and let a be an
item in A closest to q k . There exists an active copy of
q k in some submesh R i;j such that either a = oe(i; j;
Proof. By assumption, a must be the solution oe(p; q;
of q k in some submesh R p;q . In fact, since the items in the
matrix are not necessarily distinct, it is possible that a is
the solution of q k in a number of such submeshes. Assume,
without loss of generality, that such is the case for some
submeshes in slice S i . Specifically, let R i;j be the leftmost
submesh in S i for which a = oe(i; j; k). If the copy of q k in
R i;j is active, there is nothing to prove. We shall, therefore,
assume that the copy of q k in R i;j is inactive.
We propose to show that at least one of the copies of
q k in R i;j \Gamma1 or R i;j+1 is active. Since the copy of q k in
R i;j is inactive, (4) guarantees that R i;j cannot be critical
with respect to q k . Therefore, with a v and b v denoting,
respectively, the item in the northwest and southeast corner
of R i;j ,
Notice that a = oe(i; j; along with (9) implies that a must
be either a v or b v . Symmetry allows us to assume, without
loss of generality, that a = a v . In turn, this implies that
Notice that (10) along with the fact that the copy of q k in
R i;j is inactive guarantees, by virtue of (a4) that j 6= 1 and,
thus, R i;j must exist. Let, a u and b u be, respectively,
the items in the northwest and southeast corner of R i;j \Gamma1 .
R i;j is the leftmost submesh in S i for which a =
and since the matrix A is sorted, we must have
a
Moreover, we cannot have q k ? b u for otherwise, (a2) and
combined would guarantee that the copy of q k in R i;j
must be active. Therefore, it must be the case that
However, equations (4), (11), and (12), combined imply
that the copy of q k in R i;j \Gamma1 must be active, as desired.
This completes the proof of Lemma 4.7.
Lemma 4.7 suggests an obvious way of updating the solutions
of active copies of a search query q k . We spell out
the details as follows:
ffl If the active copy of q k belongs to a critical submesh
R i;j and R i;j \Gamma1 is not critical, then the copy of q k in
R i;j updates its solution oe(i; j; by combining it with
ffl If the active copy of q k belongs to a critical submesh
R i;j and R i;j+1 is not critical, then the copy of q k in
R i;j updates its solution oe(i; j; by combining it with
ffl If the copy of q k is active because of rule (a2), then
it updates its solution oe(i; j; by combining it with
Lemma 4.8. Let q k be a rank query. The active copies of
q k in a generic slice S i carry enough information to compute
the number of items in S i strictly smaller than q k .
Proof. First, if all copies of q k in slice S i are active then the
sum of their local solutions oe(i; j; is exactly the number
of items in S i strictly smaller than q k .
Assume, therefore, that not all copies of q k in slice S i
are active. Consider the active copy of q k in the leading
submesh of S i with respect to q k .
ffl If this copy is active by rule (a4) then its solution
must be 0, which is the correct number of
items in S i strictly smaller than q k .
ffl If this copy is active by rule (a3) then its solution
is updated to read
mn, which is the correct
number of items in S i strictly smaller than q k .
ffl If this copy is active by rule (a1) or (a2) then its solution
is updated to read oe(i;
which is the correct number of items in S i strictly
smaller than q k in all submeshes R i;1
It is important to note that the solutions of the other active
copies of q k are not changed by the updates. Thus, after
the required updates, the collection of active copies of q k
in slice S i carry enough information to correctly compute
the number of items in S i smaller that q k . The conclusion
follows.
R
R 1,1
Fig. 11. Illustrating the target of the data movement in Stage 3
The next task of Stage 3 is to move all the active copies
of queries to diagonal submeshes R i;i , (1 - i -
illustrated in Figure 11. This task can be performed in two
broadcast rounds as follows. In the first round, we proceed
row by row in each submesh R i;j . Specifically, all active
copies of the queries in the first row of the R i;j 's that have
been assigned vertical buses broadcast their local solution
on this bus to the corresponding processor in the diagonal
submesh R j;j . Following this, all the queries in the second
row will broadcast vertically, and so on. By Lemma 4.6
no broadcast conflicts will arise. Since every R i;j has
rows, this first round takes O( p m) time.
The second broadcast round involves broadcasting along
horizontal buses. This time, the columns of every R i;j are
handled one by one. Since there are
columns in each
submesh, the second round takes O(
m) time. Note, how-
ever, that as illustrated in Figure 12, it is possible for two
active copies of the same query q k to be sent to the same
location of a diagonal submesh R j;j , one copy via a horizontal
bus and one via a vertical bus. By Lemma 4.6, the
number of such copies is restricted to at most two. Fur-
thermore, one of them will arrive in one broadcast round
(on vertical buses) while the second will arrive on horizontal
buses. The processor receiving them will proceed to
combine the respective solutions. To summarize, we state
the following result.
Fig. 12. Illustrating combining solutions
Lemma 4.9. The solutions of all active copies of queries
in Q can been broadcast to the diagonal submeshes R i;i
one per processor in O(
m) time.
To complete the algorithm, the various copies of queries
in Q moved to the diagonal submeshes will be collected
and combined. The idea is to move all the active copies of
the same query from the diagonal submeshes R i;i to one or
several adjacent rows of the original mesh. Specifically, in
case p
all the copies of the first m
will be
moved to the first row of the mesh, the copies of the second
group of m
will
be moved to the second row of the mesh, and so on.
On the other hand, in case
the copies of q 1 will be moved to the first
m rows of the
mesh,
per row. The data movement for both cases is
similar and will be discussed next. In preparation for this
data movement we need to introduce some terminology.
Consider a generic copy of query q k . We associate with
q k the quantities r(q k ) and c(q k ) referred to as the r-value
and c-value of q k . Here, r(q k ) is the identity of the row of
the mesh to which this copy will have to navigate; c(q k ) is
the relative position of this query among the copies moved
to row r(q k ). Further, note that the processor storing q k
can compute r(q k ) and c(q k ) in O(1) time.
Recall that at the beginning of Stage 3, in every submesh
R i;j the queries were sorted in row-major order. Thus, their
solutions will be stored in the diagonal submeshes R i;i in
the same relative order.
Further, using vertical buses, the copies of the queries in
the first row of every submesh R i;i are moved to the row
of the mesh corresponding to their r-value. Specifically, a
generic copy of query q k stored by a processor P (i; will be
broadcast vertically to processor P (r(q k ); j). It is crucial
to note that the queries are also sorted in row-major order
by their r-values and so no broadcasting conflicts can arise.
Proceeding sequentially, all the p m rows of the R i;i 's are
processed as described. Thus, in O( p m) time all the copies
will be broadcast to the row of the mesh corresponding to
their r-value. It is important to observe that no processor
will receive more than one copy of any query in the above
data movement.
From now on, the processing that takes place in each row
of the mesh depends on whether (13) or (14) holds. First,
assume that (13) is true. We shall detail the processing that
takes place in the first row of the mesh, the same action
being performed, in parallel in all other rows. The copies
of q 1 will be broadcast to processor P (1; 1) in the order of
their c-values. Upon receiving the next copy of q 1 , P (1; 1)
combines the corresponding solutions in the obvious way.
Since there are (at most)
m copies of q 1 , the solution
of query q 1 will be obtained in O(
time. The copies
of the remaining queries q
moved to row 1 will
be processed similarly. Therefore, the overall time needed
to solve all the queries in case (13) holds is bounded by
O(
m).
In case (14) holds, recall that the copies of a given query
have been spread over
m rows of the mesh. Again, we
discuss the processing of query q 1 , all the others being han-
dled, in parallel, in a perfectly similar way. The
copies
of q 1 have been moved to rows
copies to
each row. Now proceeding sequentially, in order of their c-
values, the
m copies of q 1 in each of the first
rows will
be broadcast to the leftmost processor in these rows. These
processors will be responsible for combining the solutions
as described above.
By Lemmas 4.7 and 4.8, at the end of
all the information needed to solve the queries is stored by
the processors in the first column of the mesh. Specifically,
processors
solutions
corresponding to query q 1 , the next group of
processors contain partial solutions corresponding to query
on. Refer to Figure 13 for an illustration.
Finally, consider diagonal submeshes
size
m \Theta
m as illustrated in Figure 14. For the final step
of Stage 3 we dedicate the diagonal submesh D i to solving
the query q i .
In one broadcast, the partial results stored by processors
in the first column of the mesh are moved, along horizontal
buses to the first column of each D i , as depicted in Figure
13. Now combining the partial solutions of query q i , (1 -
Fig. 13. Partial solutions contained by processors in first column
Fig. 14. Illustrating the submeshes
amounts to a semigroup computation, local to D i .
Using the result of Olariu et al. [33] this computation can
be performed in O(log
Once the final solution
of each query has been computed, it is a routine matter to
move it back to the first column of the mesh.
Consequently, in case (14) holds the overall running time
of the algorithm is bounded by O(
log
that since for m ? 16 we have
the running time of the algorithm, in case (14) holds, satisfies
O(
log
To summarize, we state
the following result.
Theorem 4.10. An arbitrary instance of the BSR problem
involving a sorted matrix of size
n \Theta
n and a set
of m queries, can be solved in O(maxflog n;
mg) time on
a mesh with multiple broadcasting of size
thermore, this is time-optimal on this architecture.
V. Concluding Remarks and Open problems
A matrix is said to be sorted if its rows and columns
are independently sorted. An instance of the Batched
Searching and Ranking problem, (BSR, for short) involves
a sorted matrix A of items from a totally ordered universe,
along with a collection Q of queries. Q is an arbitrary mix
of the following query types: for a search query q j one is
interested in the item of A that is closest to q j ; for a rank
query q j one is interested in the number of items of A that
are strictly smaller than q j . The BSR problem asks for
solving all queries in Q.
In this work, we considered the BSR problem with the
matrix A pretiled, one item per processor, onto a mesh
with multiple broadcasting of size
n \Theta
n; the m queries
are stored, one per processor, in the first m
columns of
the platform. Our main contribution is twofold:
ffl First, we proved that any algorithm that correctly
solves the BSR problem must take at least
\Omega\Gammaeas flog n;
time in the worst case.
ffl Second, we showed that this time lower bound is tight
on a mesh with multiple broadcasting of size
n \Theta
n.
We developed a novel and interesting cloning strategy
for the queries. partitioned the platform into a number of
The interesting feature of this cloning strategy, supported
by the sortedness of the matrix, is that there is always a
small set of clones that, when retrieved, allow to obtained
the overall solution for each query.
Visibly, the cloning strategy is perfectly general. An
interesting direction for further research is to see for what
other datasets this strategy works. Yet another direction
is to see what other practical applications benefit from our
strategy.

Acknowledgement

: The authors wish to express their
appreciation to three anonymous referees for an exceptionally
thorough reviewing job.



--R

Optimal bounds for finding maximum on array of processors with k global buses
Computer Vision
Square meshes are not always optimal
Design of massively parallel processor
Square meshes are not optimal for convex hull computa- tion

A unifying look at semigroup computations on meshes with multiple broad- casting
A fast selection algorithm on meshes with multiple broadcasting



Square meshes are not optimal for convex hull compu- tation
Designing efficient parallel algorithms on mesh connected computers with multiple broadcasting
Efficient median finding and its application to two-variable linear programming on mesh-connected computers with multiple broadcasting
Upper and lower time bounds for parallel random access machines without simultaneous writes
The complexity of searching in X
Parallel algorithms for searching in X
Pattern Classification and Scene Analysis
Parallel search in sorted multisets
Generalized selection and ranking: sorted matrices
Communications of the ACM
Array processor with multiple broadcasting
Image computations on meshes with multiple broadcast
Sorting X.
IEEE Transactions on Computers
Parallel Processing Letters
An efficient VLSI architecture for digital geometry
IEEE Transactions on Parallel and Distributed Systems

Channel routing in VLSI
Bitonic sort on a mesh-connected parallel computer
Data broadcasting in SIMD computers
Optimal convex hull algorithms on enhanced meshes

The AMT DAP 500
Image database systems: a survey
--TR

--CTR
Susumu Matsumae , Nobuki Tokura, An efficient self-simulation algorithm for reconfigurable meshes, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.216-223, July 09-13, 2000, Bar Harbor, Maine, United States
Dharmavani Bhagavathi , Himabindu Gurla , Stephan Olariu , Larry Wilson , James L. Schwing , Jingyuan Zhang, Time- and VLSI-Optimal Sorting on Enhanced Meshes, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.929-937, October 1998
R. Lin , S. Olariu , J. L. Schwing , B.-F. Wang, The Mesh with Hybrid Buses: An Efficient Parallel Architecture for Digital Geometry, IEEE Transactions on Parallel and Distributed Systems, v.10 n.3, p.266-280, March 1999
parallel algorithms;time-optimal algorithms;searching;VLSI;ranking;enhanced meshes;pattern recognition;robotics;database design