An Efficient Algorithm for Row Minima Computations on Basic Reconfigurable Meshes.
AbstractA matrix A of size mn containing items from a totally ordered universe is termed monotone if, for every i, j, 1 i < jm, the minimum value in row j lies below or to the right of the minimum in row i. Monotone matrices, and variations thereof, are known to have many important applications. In particular, the problem of computing the row minima of a monotone matrix is of import in image processing, pattern recognition, text editing, facility location, optimization, and VLSI. Our first main contribution is to exhibit a number of nontrivial lower bounds for matrix search problems. These lower bound results hold for arbitrary, infinite, two-dimensional reconfigurable meshes as long as the input is pretiled onto a contiguous nn submesh thereof. Specifically, in this context, we show that every algorithm that solves the problem of computing the minimum of an nn matrix must take (log log n) time. The same lower bound is shown to hold for the problem of computing the minimum in each row of an arbitrary nn matrix. As a byproduct, we obtain an (log log n) time lower bound for the problem of selecting the kth smallest item in a monotone matrix, thus extending the best previously known lower bound for selection on the reconfigurable mesh. Finally, we show an $\Omega \left( {\sqrt {\log\log n}} \right)$ time lower bound for the task of computing the row minima of a monotone nn matrix. Our second main contribution is to provide a nearly optimal algorithm for the row-minima problem: With a monotone matrix of size mn with mn pretiled, one item per processor, onto a basic reconfigurable mesh of the same size, our row-minima algorithm runs in O(log n) time if 1 m 2 and in $O\!\left( {{{{\log n} \over {\log m}}}\log\log m} \right)$ time if m > 2. In case $m = n^\epsilon$ for some constant $\epsilon,$$(0 < \epsilon \le 1),$ our algorithm runs in O(log log n) time.
Introduction
Recently, in an attempt to reduce its large computational diameter, the mesh-connected architecture
has been enhanced with various broadcasting capabilities. Some of these involve endowing the
mesh with static buses, that is buses whose configuration is fixed and cannot change; more recently,
researches have proposed augmenting the mesh architecture with reconfigurable broadcasting buses:
these are high-speed buses whose configuration can be dynamically changed in response to specific
processing needs. Examples include the bus automaton [25, 26], the reconfigurable mesh [21], the
mesh with bypass capability [12], the content addressable array processor [31], the reconfigurable
network [7], the polymorphic processor array [16,20], the reconfigurable bus with shift switching [15],
the gated-connection network [27, 28], the PARBS [30], and the polymorphic torus network [13, 17]
- see the comprehensive survey paper of Nakano [22].
Among these, the reconfigurable mesh and its variants have turned out to be valuable theoretical
models that allowed researchers to fathom the power of reconfiguration and its relationship with
the PRAM. From a practical standpoint, however, the reconfigurable mesh and its variants [21,30]
omit important properties of physical architectures and, consequently, do not provide a complete
and precise characterization of real systems. Moreover, these models are so flexible and powerful
that it has turned out to be impossible to derive from them high-level programming models that
reflect their flexibility and intrinsic power [16, 20]. Worse yet, it has been recently shown that
the reconfigurable mesh and the PARBS do not scale and, as a consequence, do not immediately
support virtual parallelism [18, 19].
Motivated by the goal of developing algorithms in a scalable model of computation, we adopt
a restricted version of the reconfigurable mesh, that we call the basic reconfigurable mesh, (BRM,
for short). Our model is derived from the Polymorphic Processor Array (PPA) proposed in [16,20]:
the BRM shares with the PPA all the restrictions on the reconfigurability and the directionality
of the bus system. The BRM differs from the PPA in that we do not allow torus connections.
As a result, the BRM is potentially weaker than the PPA. It is very important to stress that the
programming model developed in [16, 20] for the PPA also applies to the BRM. In particular, all
the broadcast primitives developed in [16, 20], with the exception of those using torus connections,
can be inherited by the BRM. In fact, all the algorithms developed in this paper could have been,
just as easily, written using the extended C language primitives of [16,20]. We opted for specifying
our algorithm in a more conventional fashion only to make the presentation easier to follow.
Consider a two-dimensional array (i.e. a matrix) A of size m \Theta n with items from a totally
ordered universe. Matrix A is termed monotone if for every m, the smallest
value in row j lies below or to the right of the smallest value in row i, as illustrated in the example
above, where the row minima are highlighted. A matrix A is said to be totally monotone if every
submatrix of A is monotone. The concepts of monotone and totally monotone matrices may seem
artificial and contrived at first. Rather surprisingly, however, these concepts have found dozens of
applications to problems in optimization, VLSI design, facility location problems, string editing,
pattern recognition, and computational morphology, among many others. The reader is referred
to [1-6] where many of these applications are discussed in detail.
One of the recurring problem involving matrix searching is referred to as row-minima computation
[6]. In particular, Aggarwal et al. [2] have shown that the task of computing the row-minima
of an m \Theta n monotone matrix has a sequential lower bound of \Omega\Gamma n log m). They also showed that
this lower bound is tight by exhibiting a sequential algorithm for the row-minima problem running
in O(n log m) time. In the case matrix is totally monotone, the sequential complexity is reduced to
To the best of our knowledge, no time lower bound for the row-minima problem has been
obtained in parallel models of computation, in spite of the importance of this problem. The first
main contribution of this paper is to propose a number of non-trivial time lower bounds for matrix
search problems. These lower bounds hold for general two-dimensional reconfigurable meshes of
infinite size, as long as the input is pretiled onto a contiguous submesh of size n \Theta n. Specifically,
in this context we show that every algorithm that solves the problem of computing the smallest
item of an n \Theta n matrix must
take\Omega\Gamma238 log n) time. The same lower bound is shown to hold for
the problem of computing the minima in each row of an arbitrary n \Theta n matrix. As a byproduct,
we obtain an
\Omega\Gamma/13 log n) time lower bound for the problem of selecting the k-th smallest item
in a monotone matrix. Previously, Hao et al. [10] have obtained
log n) lower bound for
selection in arbitrary matrices on finite reconfigurable meshes. Thus, our lower bound extends
the result of [10] in two directions: we show that the same lower bound applies to selection on
monotone matrices and on a reconfigurable mesh of an infinite size. Finally, we show an almost
tight \Omega\Gamma
log log n) time lower bound for the task of computing the row minima of a monotone
n \Theta n matrix. Our second main contribution is to provide an efficient algorithm for the row-minima
problem: with a monotone matrix of size m \Theta n with m - n pretiled, one item per processor, onto
a BRM of the same size, our row-minima algorithm runs in O( log n
log m log log m) time. In case
for some constant ffl, (0 our algorithm runs in O(log log n) time.
The remainder of this work is organized as follows: Section 2 introduces the model of computations
adopted in this paper; Section 3 discusses a number of relevant lower-bound results; Section 4
presents basic algorithms that will be key in our subsequent row-minima algorithm; Section 5 gives
the details of our row-minima algorithm; finally, Section 6 offers concluding remarks and poses
open problems.
2 The Basic Reconfigurable Mesh
A Basic Reconfigurable Mesh (BRM, for short) of size m \Theta n consists of mn identical SIMD
processors positioned on a rectangular array with m rows and n columns. As usual, it is assumed
that every processor knows its own coordinates within the mesh: we let P (i; j) denote the processor
placed in row i and column j, with P (1; 1) in the north-west corner of the mesh.

Figure

1: A basic reconfigurable mesh of size 4 \Theta 4
Each processor P (i; j) is connected to its four neighbors P (i \Gamma
exist, and has four ports N, S, E, and W, as illustrated in Figure 1. Local
connections between these ports can be established, subject to the following restrictions:
1. In each time unit at most one of the pairs of ports (N, S) or (E,W) can be set; moreover,
2. All the processors that connect a pair of ports must connect the same
3. broadcasting on the resulting subbuses is unidirectional. For example, if the processors set
the (E,W) connection, then on the resulting horizontal buses all broadcasting is done either
"eastbound" or else "westbound", but not both.

Figure

2: Examples of unidirectional horizontal subbuses
We refer the reader to Figure 2(a)-(b) for an illustration of several possible unidirectional sub-
buses. The BRM is very much like the recently proposed PPA multiprocessor array, except that
the BRM does not have the torus connections present in the PPA. In a series of papers [16, 18-20]
Maresca and his co-workers demonstrated that the PPA architecture and the corresponding programming
environment is not only feasible and cost-effective to implement, it also enjoys additional
features that set it apart from the standard reconfigurable mesh and the PARBS. Specifically, these
researchers have argued convincingly that the reconfigurable mesh is too powerful and unrestricted
to support virtual parallelism under present-day technology. By contrast, the PPA architecture has
been shown to scale and, thus, to support virtual parallelism [16, 18].
The BRM is easily shown to inherit all these attractive characteristics of the PPA, including
the support of virtual parallelism and the C-based programming environment, making it eminently
practical. As in [16], we assume ideal communications along buses (no delay). Although inexact, a
series of recent experiments with the PPA [16] and the GCN [27, 28] seem to indicate that this is
a reasonable working hypothesis.
3 Lower Bounds
The main goal of this section is to demonstrate non-trivial lower bounds for several matrix search
problems. Our lower bound arguments do not use the restrictions of the BRM, holding for more
powerful reconfigurable meshes that allow any local connections. In fact, our arguments hold for
arbitrary two-dimensional reconfigurable meshes of an infinite size, provided that the input is placed
into a contiguous n \Theta n submesh thereof.
Formally, this section deals with the following problems:
Problem 1. Given an n \Theta n matrix pretiled one item per processor onto an n \Theta n submesh of an
reconfigurable mesh, find the minimum item in the matrix.
Problem 2. Given an n \Theta n matrix pretiled one item per processor onto an n \Theta n submesh of an
reconfigurable mesh, find the minimum item of each row.
Problem 3. Given an n \Theta n monotone matrix pretiled one item per processor onto an n \Theta n
submesh of an 1 \Theta 1 reconfigurable mesh, find the minimum item of each row.
Problem 4. Given an n \Theta n totally monotone matrix pretiled one item per processor onto an n \Theta n
submesh of an 1 \Theta 1 reconfigurable mesh, find the minimum item of each row.
We will show that Problems 1 and 2 have
an\Omega\Gamma/29 log n)-time lower bound, and that Problem 3
has an \Omega\Gamma
log log n)-time lower bound. The lower bound for Problem 4 is still open.
The proofs are based on a technique detailed in [11, 29] that uses the following graph-theoretic
result of Tur'an [8]. (Recall that an independent set in a graph is a set of pairwise non-adjacent
vertices.)
Lemma 3.1 E) be an arbitrary graph. G has an independent set U such that
This lemma is used, in an implicit adversary argument, to bound from below the number of items
in the matrix that are possible choices for the minimum. Let V be the set of candidates for the
minimum at the beginning of the current iteration and let E stand for the set of pairs of candidates
that are compared within the current iteration. The situation benefits from being represented by
a graph E) with, V and E representing, respectively, the vertices and the edges of the
graph. It is intuitively obvious that an adversary can choose the outcome of the comparisons in
such a way that the next set of candidates is no larger than the size of an independent set U in G.
In other words, for a set V of candidates and for a set E of pairs that are compared by a minimum
finding algorithm, items in the independent set U have the potential of becoming the minimum.
Consequently, all items in U are still candidates for the minimum after comparing all pairs in E.
To make the presentation easier to follow, we assume that each time unit is partitioned into the
following three stages:
Phase 1 bus reconfiguration: i.e. the processors set local connections;
Phase 2 broadcasting: i.e. the processors send at most a data item to each port, and receive a
piece of data from each port;
Phase 3 local computation: i.e. every processor selects two elements stored in its local memory,
compares them and changes its internal status.
We begin by proving the following lemma.
Lemma 3.2 Every algorithm that solves Problem 1
log n) time.
Proof. We will evaluate the number of pairs that can be compared by an algorithm in Phase 3 of
time unit t. Notice that in Phase 2 of a time unit, at most 4n items can be sent to the outside of
the submesh. Hence, altogether, at most 4nt items can be sent before the execution of Phase 3 of
time unit t. Therefore, the outside of the submesh can compare at mostB @ 4nt1
of items. The inside of the submesh can compare at most n 2 pairs in each Phase 3. Consequently,
in Phase 3 of time unit t, at most 16n 2 can be compared by the 1 \Theta 1
reconfigurable mesh. Let c t be the number of candidates that can be the minimum after Phase 3
of time unit t. Then, by virtue of Lemma 3.1 we have,
By applying the logarithm, we obtain
log c t - 2 log c
To complete the algorithm at the end of T time units, c T must be less than or equal to 1. Therefore,
must hold. In turn, this implies that T
2\Omega\Gamma400 log n), as claimed. 2
It is worth mentioning that Lemma 3.2 implies a similar lower bound for the task of selection
in monotone matrices. To see this, note that given an arbitrary matrix A of size n \Theta n we can
construct a monotone matrix A 0 of size n \Theta (n + 1) by simply adjoining to A a column vector of all
of whose entries are \Gamma1. It is now clear that the minimum item in A is precisely the (n
smallest item in A 0 . Thus, we have the following result.
Lemma 3.3 Every algorithm that selects the k-th smallest item in a monotone matrix of size n \Theta n
requires
\Omega\Gamma108 log n) time.
Previously, Hao et al. [10] have obtained
log n) lower bound for selection in arbitrary matrices
on finite reconfigurable meshes. Thus, Lemma 3.3 extends the result of [10] in two directions:
first it shows that \Omega\Gammaat/ log n) remains the lower bound for selection on monotone matrices and
second, it shows that the lower bound must hold even for infinite reconfigurable meshes.
Lemma 3.4 Every algorithm that solves Problem 2
log n) time.
Proof. Suppose to the contrary that Problem 2 requires o(log log n) time However, by using the
algorithm of Proposition 4.1 in Section 4, the minimum in the matrix can be computed in O(1)
further time. This contradicts Lemma 3.2. 2
Lemma 3.5 Every algorithm that solves Problem 3 requires \Omega\Gamma
log log n) time.
Proof. Since there is an algorithm that solves Problem 3 in O(log log n) time (see Section 5), we
can assume that the upper bound for the Problem 3 is O(log log n). Assume that a row-minima
algorithm spent time and has found no row-minima so far, and now it is about to execute
Phase 3 of time unit t, where t ! ffl log log n for some small fixed ffl ? 0.
Proceeding as in the proof of Lemma 3.2, we see that at most 17n 2 t 2 pairs can be compared in
Phase 3 of time unit t. Now a simple counting argument guarantees that at most n 1\Gamma1=4 t
rows have
been assigned at least 17n
comparisons each in time unit i,
Hence, at time i, at least n \Gamma in 1\Gamma1=4 t
rows have been assigned at most 17n 1+1=4 t
Assume that the topmost row was assigned at most 17n 1+1=4 t
comparisons in each time unit i,
be the number of candidates in the top row at the end of Phase 3 of time
unit t.
By applying the logarithm, we have log c i - 2 log c
Hence, for some small fixed ffl ? 0, c ffl log log n ? 1 for large n. Therefore, at least n \Gamma tn 1\Gamma1=4 t rows
including the topmost row cannot find the row-minima in Phase 3 of time unit t. Consequently, at
most tn 1\Gamma1=4 t
rows can find the row-minima in Phase 3 of time unit t. In turn, this implies that
there exist n=(tn 1\Gamma1=4 t
=t consecutive rows that cannot find the row-minima in Phase 3
of time t. Therefore, we can find a submatrix of size n 1=4 t
=t \Theta n 1=4 t
=t such that all of the n 1=4 t
row-minima are in it but no row-minima is found. Let d t \Theta d t be the size of sub-matrix such that all
d t row-minima are in it but no row-minima is found at time t. Then, d t - d
=t. In addition,
for large t, d
holds. Thus, for large t we have: d t - d
. By applying the
logarithm twice, we can write
log log d t - log log d
log log
log log
Hence, in order to have d T - 1 it must be the case that T 2 \Omega\Gamma
log log n), and the proof is
4 Preliminaries
Data movement operations are central to many efficient algorithms for parallel machines constructed
as interconnection networks of processors. The purpose of this section is to review a number of
basic data movement techniques for basic reconfigurable meshes.
Consider a sequence of n items a 1 , a . We are interested in computing the prefix maxima
defined for every j, (1 - j - n), by setting z g. Recently Olariu
et al. [23] showed that the task of computing the prefix maxima of a sequence of n numbers stored
in the first row of a reconfigurable mesh of size m \Theta n can be solved in O(log n) time if
in O( log n
log m algorithm is crucial for understanding our algorithm for
computing the row minima of a monotone matrix, we now present an adaptation of the algorithm
in [23] for the BRM.
To begin, we exhibit an O(1) time algorithm for computing the prefix maxima of n items on
a BRM of size n \Theta n. The idea of this first algorithm involves checking, for all j, (1 - j - n),
whether a j is the maximum of a 1 ; a . The details are spelled out by the following sequence
of steps. The reader is referred to Figure 3(a)-(f) where the algorithm is illustrated on the input
sequence 7, 3, 8, 6.
Algorithm
Step 1. Establish a vertical bus in every column j, (1
every processor P (1; j), (1 broadcasts the item a j southbound along the vertical
bus in column j;
Step 2. Establish a horizontal bus in every row i, (1
every processor P broadcasts the item a n+1\Gammai westbound along
the horizontal bus in row
Step 3. At the end of Step 2, every processor P (i; j), (i stores the items a n+1\Gammai and
sets a local variable b i;j as follows:
Step 4. Every processor P (i; j), (i connects its ports E and W; every
processor P (i; j), (i broadcasts a 0 eastbound; every processor
that receives a 0 from its W port sets b i;n+1\Gammai to 0;
Step 5. Every processor P (i; j), (i connects its ports N and S; every processor P
northbound on the bus in column i; every processor
copies the value received into b 1;i ;
to a i ; every processor P (1; i),
connects its ports E and W; every processor P (1; i), (1 - i -
to the value received from its port W.
The correctness of the algorithm above is easily seen. Thus, we have the following result.
Proposition 4.1 The prefix maxima of n items from a totally ordered universe stored one item
per processor in the first row of a basic reconfigurable mesh of size n \Theta n can be computed in O(1)
time.
Next, following [23], we briefly sketch the idea involved in computing the prefix maxima of n
items a 1 , a a n on a BRM of size m \Theta n with by partitioning the original
mesh into submeshes of size m \Theta m, and apply Prefix-Maxima-1 to each such submesh of size m \Theta m.
We further combine groups of m consecutive submeshes of size m \Theta m into a submesh of size
combine groups of m consecutive submeshes of size m \Theta m 2 into a submesh of size
m\Thetam 3 , and so on. Note that if the prefix maxima of a group of m consecutive submeshes are known,
then the prefix maxima of their combination can be computed essentially as in Prefix-Maxima-1.
For details, we refer the reader to [23].
To summarize the above discussion we state the following result.
Proposition 4.2 The prefix maxima of n items from a totally ordered universe stored in one row
of a basic reconfigurable mesh of size m \Theta n with can be computed in O( log n
log m ) time.
Proposition 4.2 has the following important consequence.
Proposition 4.3 Let ffl be an arbitrary constant in the range 1. The prefix maxima of
n items from a totally ordered universe stored one item per processor in the first row of a basic
reconfigurable mesh of size n ffl \Theta n can be computed in O(1) time.
For later reference we now solve a particular instance of the row-minima problem, that we call
the selective row minima problem. Consider an arbitrary matrix A of size K \Theta N stored, one item
per processor, in K consecutive rows of a BRM of size M \Theta N . For simplicity of exposition we
assume that A is stored in the first K rows of the platform, but this is not essential. The goal is to
compute the minima in rows 1;
A. We proceed as follows.
Algorithm Selective-Row-Minima;
7,6
(a) (b)
(c) (d)

Figure

3: Illustrating algorithm Prefix-Maxima-1
r
r
r
r
R
R i;2
R i;1

Figure

4: Illustrating algorithm Selective-Row-Minima
Step 1. Partition the BMR into N=K submeshes R 1 N=K each of size K \Theta K as illustrated
in Figure 4; further partition each submesh R i , (1 - i - N=K), into submeshes
k each of size
K \Theta K;
Step 2. Compute the minimum in the first row of each submesh R i;j in O(1) time using Proposition
4.3; let a i;1 ; a
K be the minima in the first row of R i;1
by using appropriately established horizontal buses we arrange for every a i;j ,
to be moved to the processor in the first row and j
K-th column of R i;j ;
Step 3. We now perceive the original BRM of size M \Theta N as consisting of
K submeshes
K each of size M
\Theta N ; the goal now becomes to compute for every i, (1 -
the minimum of row (i \Gamma 1)
of A in T i ; it is easy to see that after having established
vertical buses in all columns of the BRM, all the partial minima in row (i \Gamma 1)
K+1,
of A can be broadcast southbound to the first row of T
Step 4. Using the algorithm of Proposition 4.2 compute the minimum in the first row of each T i ,
in O
log N \Gammalog K
log M \Gammalog
O
log N
log M
time.
Thus, we have proved the following result.
Lemma 4.4 The task of computing the minima in rows 1;
of an arbitrary matrix of size K \Theta N stored one item per processor in K rows of a BRM of size
M \Theta N can be performed in O
log N
log M
time.
5 The algorithm
The goal of this section is to present the details of an efficient algorithm for computing the row-
minima of an m \Theta n monotone matrix A. The matrix is assumed pretiled one item per processor
onto a BRM R of the same size, such that for every
stores A(i; j).
We begin by stating a few technical results that will come in handy later on. To begin, consider
a subset of the rows of A and let j(i 1 be such that for all k, (1 - k - p),
is the minimum in row r k . Since the matrix A is monotone, we must have
be the submatrices of A defined as follows:
consists of the intersection of the first rows with the first j(i 1 ) columns of A;
ffl for every k, consists of the intersection of rows
with the columns j(i
ffl A p consists of the intersection of rows with the columns j(i p ) through n.
The following result will be used again and again in the remainder of this section.
Lemma 5.1 Every matrix A k , (1 - k - p) is monotone.
Proof. First, let k be an arbitrary subscript with 2 - k - p. and refer to Figure 5. Let B k consist
of the submatrix of A consisting of the intersection of rows columns
Similarly, let C k be the submatrix of A consisting of the intersection of rows

Figure

5: Illustrating the proof of Lemma 5.1
Since the matrix A is monotone and since A(i is the minimum in row i
that none of the minima in rows i occur in the submatrix B k . Similarly,
since A(i k ; j(i k )) is the minimum in row i k , no minima in rows i
in the submatrix C k . It follows that the minima in rows i must occur in the
submatrix A k . Consequently, if A k is not monotone, then we violate the monotonicity of A.
A perfectly similar argument shows that A 1 and A p are also monotone, completing the proof of
the lemma. 2
The matrices A k , (1 - k - p), defined above pairwise share a column. The following technical
result shows that one can always transform these matrices such that they involve distinct columns.
For this purpose, consider the matrix A 0
k obtained from A k by replacing for every i, (i
by dropping
column j(i k ). In other words, A 0
k is obtained from A k by retaining the minimum values in its first
and next column and then removing the last column. The last matrix A 0
p is taken to be A p . The
following result, whose proof is omitted will be used implicitly in our algorithm.
Lemma 5.2 Every matrix A 0
In outline, our algorithm for computing the row-minima of a monotone matrix proceeds as
follows. First, we solve an instance of the selective row minima, whose result is used to partition
the original matrix into a number of monotone matrices as described in Lemmas 5.1 and 5.2. This
process is continued until the row minima in each of the resulting matrices can be solved directly.
then the problem has a trivial solution running in \Theta(log n) time, which is also best
possible even on the more powerful reconfigurable mesh [23].
We shall, therefore, assume that m - 2. exposition we shall assume that
c i#1
R
c i#1

Figure

Illustrating the partition into submeshes T i and R i
Algorithm Row-Minima(A);
Step 1. Partition R into
each of size
m \Theta n such that for every
m),
m of R as illustrated in Figure 6;
Step 2. Using the algorithm of Lemma 4.4 compute the minima of the items in the first row of
every submesh T i ,
m), in O( log n
log
Step 3. Let c
m be the columns of R containing the minima in T
tively, computed in Step 2. The monotonicity of A guarantees that c 1 - c 2 - c p m .
m), be the submesh of consisting of all the processors P (r; c) such that
In other words, R i consists of the intersection
of rows
m with columns c
illustrated in Figure 6;
c i#1

Figure

7: Illustrating the submeshes S i
Step 4. Partition the mesh R into submeshes S 1
illustrated in Figure 7; for log log m iterations, repeat Steps 1-3 above in each submesh S i .
The correctness of algorithm being easy to see, we now turn to the complexity. Steps 1-3 have
a combined complexity of O
log m
. In Step 4, c and so, by Lemma 4.4 each iteration
of Step 4 also runs in O
log m
time. Since there are, essentially, log log m such iterations, the
overall complexity of the algorithm is O
log m log log m
. To summarize our findings we state the
following result.
Theorem 5.3 The task of computing the row-minima of a monotone matrix of size m \Theta n with
pretiled one item per processor in a BRM of the same size can be solved in O(log n)
and in O
log m log log m
2.
Theorem 5.3 has the following consequence.
Corollary 5.4 The task of computing the row-minima of a monotone matrix of size m \Theta n with
pretiled one item per processor in a BRM of the same size can be solved in
O(log log n) time.
6 Conclusions and open problems
We have shown that the problem of computing the row-minima of a monotone matrix can be solved
efficiently on the basic reconfigurable mesh (BRM) - a weaker variant of the recently proposed
Polymorphic Processor Array [16].
Specifically, we have exhibited an algorithm that, with a monotone matrix A of size m \Theta n,
stored in a BRM of the same size, as input solves the row-minima problem in
O(log n) time in case m 2 O(1), and in O
log m log log m
time otherwise. In particular, if
for some fixed ffl, (0 our algorithm runs in O(log log n) time.
Our second main contribution was to propose a number of non-trivial time lower bounds for matrix
search problems. These lower bounds hold for general two-dimensional reconfigurable meshes
of infinite size, as long as the input is pretiled onto an n \Theta n submesh thereof. Specifically, in this
context we show that every algorithm that solves the problem of computing the smallest item of
an n \Theta n matrix, or the smallest item in each row of an n \Theta n matrix must
take\Omega\Gamma453 log n) time.
This result implies an
\Omega\Gamma/17 log n) time lower bound for the problem of selecting the k-th smallest
item in a monotone matrix, extending the result of [10] in two directions: we show that the same
lower bound applies to selection on monotone matrices and on a reconfigurable mesh of an infinite
size. Finally, we showed an almost tight \Omega\Gamma
log log n) time lower bound for the task of computing
the row minima of a monotone n \Theta n matrix. These are the first non-trivial lower bounds of this
kind known to the authors.
A number of problems remain open. First, as noted, there is a discrepancy between the time
lower bound we obtained for the task of computing the row-minima of a monotone matrix and
the upper bound provided by our algorithm. Narrowing this gap will be a hard problem that we
leave for future research. Second, no non-trivial lower bounds for the problem of computing the
row-minima of a totally monotone matrix are known to us. This promises to be an exciting area
for future research. Yet another problem of interest would be to solve the row-minima problem
for the special case of totally monotone matrices. trivially, our algorithm for monotone matrices
also works for totally monotone ones. Unfortunately, to this date we have not been able to find a
non-trivial lower bound for this problem.

Acknowledgement

: The authors wish to thank Mike Atallah for many useful comments
and for pointing out a number of relevant references.



--R

Applications of generalized matrix searching to geometric problems
Geometric applications of a matrix-searching algorithm
Notes on searching in multidimensional monotone arrays
Efficient parallel algorithms for string editing and related problems
A faster parallel algorithm for a matrix searching problem
An efficient parallel algorithm for the row minima of a totally monotone matrix
The power of reconfiguration
Graphs and Hypergraphs
Pattern Classification and Scene Analysis
Selection on the reconfigurable mesh
An Introduction to Parallel Algorithms

IEEE Transactions on Computers

Reconfigurable buses with shift switching - concepts and applications
IEEE Transactions on Parallel and Distributed Systems
Connection autonomy in SIMD computers: a VLSI implementation
Virtual parallelism support in reconfigurable processor arrays
Hierarchical node clustering in polymorphic processor arrays
Hardware support for fast reconfigurability in processor arrays
Parallel computations on reconfigurable meshes
A bibliography of published papers on dynamically reconfigurable architectures
Fundamental data movement on reconfigurable meshes
Fundamental algorithms on reconfigurable meshes
On the ultimate limitations of parallel processing
Bus automata
bit serial associate processor
The gated interconnection network for dynamic programming
Parallelism in comparison problems
Constant time algorithms for the transitive closure problem and its applications IEEE Transactions on Parallel and Distributed Systems
The image understanding architecture
--TR

--CTR
Schwing , Larry Wilson, Optimal Algorithms for the Multiple Query Problem on Reconfigurable Meshes, with Applications, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.875-887, September 2001
Tatsuya Hayashi , Koji Nakano , Stephen Olariu, An O((log log n)2) Time Algorithm to Compute the Convex Hull of Sorted Points on Reconfigurable Meshes, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1167-1179, December 1998
R. Lin , K. Nakano , S. Olariu , M. C. Pinotti , J. L. Schwing , A. Y. Zomaya, Scalable Hardware-Algorithms for Binary Prefix Sums, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.838-850, August 2000
Alan A. Bertossi , Alessandro Mei, Time and work optimal simulation of basic reconfigurable meshes on hypercubes, Journal of Parallel and Distributed Computing, v.64 n.1, p.173-180, January 2004
basic reconfigurable meshes;monotone matrices;cellular system design;row minima;search problems;facility location problems;VLSI design;reconfigurable meshes;totally monotone matrices