Multi-Comparand Associative Machine and its Application to Relational Algebra Operations
In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations. We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm that performs a paral...
Saved in:
| Date: | 2010 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут програмних систем НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/14647 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Multi-Comparand Associative Machine and its Application to Relational Algebra Operations / Nepomniaschaya, A.S.// Пробл. програмув. — 2010. — № 2-3. — С. 185-192. — Бібліогр.: 20 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-14647 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-146472025-02-10T01:32:40Z Multi-Comparand Associative Machine and its Application to Relational Algebra Operations Nepomniaschaya, A.S. Паралельне програмування. Розподілені системи і мережі In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations. We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm that performs a parallel search in a matrix based on the exact match with a given pattern. Then we apply the new associative algorithm to implement a group of the relational algebra operations on the MCA-machine. The proposed algorithms are represented as corresponding procedures for the MCA-machine. We prove their correctness and evaluate their time complexity. 2010 Article Multi-Comparand Associative Machine and its Application to Relational Algebra Operations / Nepomniaschaya, A.S.// Пробл. програмув. — 2010. — № 2-3. — С. 185-192. — Бібліогр.: 20 назв. — англ. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/14647 519.682.5 en application/pdf Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Паралельне програмування. Розподілені системи і мережі Паралельне програмування. Розподілені системи і мережі |
| spellingShingle |
Паралельне програмування. Розподілені системи і мережі Паралельне програмування. Розподілені системи і мережі Nepomniaschaya, A.S. Multi-Comparand Associative Machine and its Application to Relational Algebra Operations |
| description |
In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations. We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm that performs a parallel search in a matrix based on the exact match with a given pattern. Then we apply the new associative algorithm to implement a group of the relational algebra operations on the MCA-machine. The proposed algorithms are represented as corresponding procedures for the MCA-machine. We prove their correctness and evaluate their time complexity. |
| format |
Article |
| author |
Nepomniaschaya, A.S. |
| author_facet |
Nepomniaschaya, A.S. |
| author_sort |
Nepomniaschaya, A.S. |
| title |
Multi-Comparand Associative Machine and its Application to Relational Algebra Operations |
| title_short |
Multi-Comparand Associative Machine and its Application to Relational Algebra Operations |
| title_full |
Multi-Comparand Associative Machine and its Application to Relational Algebra Operations |
| title_fullStr |
Multi-Comparand Associative Machine and its Application to Relational Algebra Operations |
| title_full_unstemmed |
Multi-Comparand Associative Machine and its Application to Relational Algebra Operations |
| title_sort |
multi-comparand associative machine and its application to relational algebra operations |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2010 |
| topic_facet |
Паралельне програмування. Розподілені системи і мережі |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/14647 |
| citation_txt |
Multi-Comparand Associative Machine and its Application to Relational Algebra Operations / Nepomniaschaya, A.S.// Пробл. програмув. — 2010. — № 2-3. — С. 185-192. — Бібліогр.: 20 назв. — англ. |
| work_keys_str_mv |
AT nepomniaschayaas multicomparandassociativemachineanditsapplicationtorelationalalgebraoperations |
| first_indexed |
2025-12-02T11:58:42Z |
| last_indexed |
2025-12-02T11:58:42Z |
| _version_ |
1850397658791804928 |
| fulltext |
Паралельне програмування. Розподілені системи і мережі
© A.S. Nepomniaschaya, 2010
ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск 185
UDC 519.682.5
MULTI-COMPARAND ASSOCIATIVE MACHINE AND ITS APPLICATION
TO RELATIONAL ALGEBRA OPERATIONS
A.S. Nepomniaschaya
Institute of Computational Mathematics and Mathematical Geophysics,
Siberian Division of the Russian Academy of Sciences,
pr. Lavrentieva, 6, Novosibirsk, 630090, Russia
Fax: (+7 383) 330-8783, Phone: (+7 383) 330 8994
E-mail: anep@ssd.sscc.ru
In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations.
We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm
that performs a parallel search in a matrix based on the exact match with a given pattern. Then we apply the new associative algorithm to
implement a group of the relational algebra operations on the MCA-machine. The proposed algorithms are represented as corresponding
procedures for the MCA-machine. We prove their correctness and evaluate their time complexity.
Introduction
Associative (content addressable) parallel processors of the SIMD type with simple processing elements are
ideally suited for performing fast parallel search operations being used in different applications such as graph theory,
computational geometry, relational database processing, image processing, and genome matching. In [19], the search
and data selection algorithms for both bit-serial and fully parallel associative processors were described. In [5], the
depth search machines and their applications to computational geometry, relational databases, and expert systems were
investigated. In [6, 7], an experimental implementation of a multi-comparand multi-search associative processor and
some parallel algorithms for search problems in computational geometry were considered. In [11], a formal model of
associative parallel processors called the associative graph machine (AG-machine) and its possible hardware
implementation were proposed. It performs bit-serial and fully parallel associative processing of matrices representing
graphs as well as some basic set operations on matrices (sets of columns). The AG-machine differs from that in [7] due
to the presence of built-in operations designed for associative graph algorithms.
In [2, 9, 12, 18], the relational database processing on conventional associative processors and specialized
parallel processors were discussed. In [8], an experimental architecture, called the optical content addressable parallel
processor for the relational database processing, was devised. It supports the parallel relational database processing by
fully exploiting the parallelism of optics. In [4], different optical and optoelectronic architectures for image processing
and relational database processing were reviewed.
In this paper, we propose a new multi-comparand associative machine (MCA-machine) and show how this
model can efficiently support classical operations in relational databases. We first propose a new associative algorithm
for the multi-comparand search and its implementation on the MCA-machine. It generalizes the Falkoff associative
algorithm [1] that simultaneously selects those rows in a given matrix that coincide with a given pattern. Then we
consider applications of this algorithm to representing one group of the relational algebra operations whose resulting
relation is a subset of the corresponding argument relations. We also provide the operation Product that belongs to
another group of the relational algebra operations. Every operation of this group assembles a new relation. The
proposed algorithms are given as the corresponding procedures for the MCA-machine. We prove their correctness and
evaluate the time complexity.
1. A model of a multi-comparand associative machine
In this section, we first explain, why the new model is introduced.
By means of the STAR-machine [10], we have represented both the associative versions of some classical graph
algorithms (for example, [14]-[16]) and classical operations in relational databases [13]. The proposed associative
algorithms utilize the following properties of associative systems with vertical processing: data parallelism, bit-serial
processing, and access data by contents. To improve the time complexity of associative graph algorithms, the AG-
machine was proposed in [11]. It allows one to use both the bit-serial and the bit-parallel processing. Due to the bit-
parallel processing, some parts of a given associative graph algorithm can be performed in parallel [17]. To improve the
time complexity of performing the relational algebra operations, we have considered in [12] a modified version of the
STAR-machine joined with two hardware supports: the set intersection processor and the λ-processor. The MCA-
machine allows one to implement the classical relational algebra operations with the same time complexity as in the
case of a modified version of the STAR-machine [12].
Паралельне програмування. Розподілені системи і мережі
186
We define the model as an abstract MCA-machine of the SIMD type with simple single-bit processing elements
(PEs). To simulate the access data by contents, the MCA-machine uses both the typical operations for associative
systems first presented in Staran [3] and a group of new operations to perform the bit-parallel processing.
The model consists of the following components:
a sequential common control unit (CU), where the programs and scalar constants are stored;
an associative processing unit forming a two-dimensional array of single-bit PEs;
a matrix memory for the associative processing unit.
The CU broadcasts each instruction to all PEs in one unit of time. All active PEs execute it simultaneously, while
inactive PEs do not perform it. Activation of a PE depends on the data employed.
Input binary data are given in the form of two-dimensional tables, where each datum occupies an individual row
to be updated by a dedicated row of PEs. In any table, rows are numbered from top to bottom and columns - from left to
right.
The associative processing unit is represented as a matrix of single-bit PEs that corresponds to the matrix of
input binary data. Each column in the matrix of PEs can be regarded as vertical register that maintains the entire column
of a table.
To simulate data processing in the associative processing unit, we use the data types slice and word for the bit
column access and the bit row access, respectively, and the type table for defining and updating matrices. We assume
any variable of the type slice to consist of n components. For simplicity, let us call slice any variable of the type slice.
To perform bit-serial (vertical) processing, the MCA-machine employs the same operations for slices as the
STAR-machine [10] along with new operations FRST(Y) and CONVERT(Y).
For the sake of completeness, we recall some elementary operations for slices being used in this paper.
SET(Y) simultaneously sets all components of the slice Y to '1';
CLR(Y) simultaneously sets all components of Y to '0’;
FND(Y) returns the ordinal number of the first component '1' of Y;
STEP(Y) returns the same result as FND(Y), then resets the first found '1' to '0'. For example, let Y='0100101'
and the statement k:=STEP(Y) be performed. Then we obtain k=2 and Y='0000101';
FRST(Y) saves the first (the uppermost) component '1' in the slice Y and sets to '0' its other components. For
example, let Y='0100101' and the operation FRST(Y) be performed. Then we obtain Y='0100000';
NUMB(Y) returns the number of components '1' in the slice Y;
MASK(Y,i,j) sets components '1' from the i-th through the j-th positions, inclusively, and components '0' in
other positions of the slice Y (1≤i<j≤n);
SHIFT(Y,down,k) moves the contents of Y by k positions down, placing each component from the position i to
the position i+k (n-ki1) and setting components '0' from the first through the k-th positions, inclusive;
CONVERT(Y) returns a row whose every i-th component (bit) coincides with Y(i). It is applied when a column
of one matrix is used as a comparand for another matrix.
In the usual way, we introduce the predicate SOME(Y) and the bitwise Boolean operations X and Y, X or Y, not
Y, X xor Y.
The above-mentioned predicates and operations for slices, except SHIFT, are also used for variables of the type
word.
For a variable T of the type table, we use the following two operations:
ROW(i,T) returns the i-th row of the matrix T;
COL(i,T) returns the i-th column of T.
To perform the bit-parallel processing, the MCA-machine uses two groups of new elementary operations for
variables of the type table. One group of such operations is applied to a single binary matrix, while the other one is used
for two binary matrices of the same size. In any binary matrix, its rows can be masked by means of a variable of the
type slice, while its columns can be masked by means of a variable of the type word.
Now we present the first group of elementary operations for matrices.
The operation SCOPY(T,X,v) simultaneously writes the given slice X into those columns of the matrix T, which
are marked with bits '1' in the comparand v.
The operation RCOPY(T,v,X) simultaneously writes the given word v into those rows of the matrix T, which are
marked with bits '1' in the slice X.
The operation FRST(row,T) simultaneously performs FRST(v) for every row v of the matrix T and writes the
result into T.
The operation FRST(col,T) simultaneously performs FRST(Y) for every column Y of the matrix T and writes
the result into T.
The operation SHIFT(T,down,k) simultaneously performs SHIFT(Y,down,k) for all columns of the given matrix T.
Let us present a group of logical operations for binary matrices. Every logical operation will be used as the right
part of the assignment statement.
The operation not (T,v) simultaneously replaces the columns of the given matrix T, marked with bits '1' in the
comparand v, with their negation.
Паралельне програмування. Розподілені системи і мережі
187
The operation or (row,T) simultaneously performs the disjunction in every row of the matrix T. It returns a slice
whose every i-th component is equal to '0' if and only if ROW(i,T) consists of zeros.
The operation and (row,T) simultaneously performs the conjunction in every row of the matrix T. It returns a
slice whose every i-th component is equal to '1' if and only if ROW(i,T) consists of ones.
The operation or (col,T) simultaneously performs the disjunction in every column of the matrix T. It returns a
row whose every i-th bit is equal to '0’ if and only if COL(i,T) consists of zeros.
Now, we present the second group of elementary operations for matrices.
The operation SMERGE(T,F,v) simultaneously writes the columns of the given matrix F that are marked with
bits '1' in the comparand v in the corresponding columns of the resulting matrix T. If the comparand v consists of ones,
the operation SMERGE copies the matrix F into the matrix T.
The operation op (T,F,v), where op { or, and, xor }, is simultaneously performed between those columns of
the given matrices T and F that are marked with bits '1' in the given comparand v. This operation is used as the right
part of the assignment statement. For example, let a binary matrix R be a result of the operation or (T,F,v). Then we
write this as R:= or (T,F,v).
Remark 1. Statements of the MCA-machine are defined in the same manner as for Pascal. We will use them later
for presenting our procedures.
Following Foster [3], the time complexity of an algorithm is measured by counting all elementary operations of
the MCA-machine (its microsteps) performed in the worst case. It is assumed that each elementary operation for
variables of the types slice, word, and table takes one unit of time.
2. Performing multi-comparand searching in parallel
In [1], Falkoff proposed an associative algorithm for selecting rows in a given matrix T that coincide with a
given pattern w. This algorithm runs as follows: at every i-th step of computation, it saves the matrix T rows whose first
i bits are the initial part of the pattern w.
In [15], we presented an implementation of this algorithm on the STAR-machine as procedure
MATCH(T,X,w,Z). It determines positions of the matrix T rows that coincide with the given pattern w. By means of the
slice X, we mark with '1' the matrix T rows that are used for comparison with w. The procedure returns the slice Z,
where Z(i)='1' if and only if ROW(i,T)=w and X(i)='1'. On the STAR-machine, the procedure MATCH requires O(k)
time [15], where k is the number of columns in the matrix T.
Let us explain its implementation on the STAR-machine that performs the bit-serial processing. The procedure
MATCH uses an auxiliary slice, say Y. Initially, the resulting slice Z coincides with the given slice X, that is, the rows
of T marked with '1' in the slice X, are candidates for analysis. At every i-th step of computation (i 1), we first write
the i-th column of the matrix T into the slice Y. Then we examine the i-th bit of the pattern w. If w(i)='1', we perform
the statement Z:=Z and Y. Otherwise, for saving positions of rows whose i-th bit is '0', we fulfil the statement Z:=Z and
( not Y).
Now we consider implementation of the procedure MATCH(T,X,w,Z) on the MCA-machine. It makes use of the
following idea. For every 1 ≤ i ≤ |w|, the i-th bit of every row of the matrix T is simultaneously compared to the i-th bit
of the given pattern w.
procedure MATCH(T: table; X: slice(T); w: word; var Z: slice(T));
var A,B: table; u,v: word(T);
1. Begin SET(u); v:= not w;
/* Positions of the bit '0' in the pattern w are marked with '1' in the row v. */
2. SCOPY(A,X,u);
/* Every column of the matrix A saves with '1' positions of the matrix T rows being used for comparison with w.
*/
3. B:= not(T,v);
/* We write the negation of every column of the matrix T that corresponds to '0' into the given string w. */
4. A:=and (A,B,u);
/* Here, u is a mask for columns of matrices A and B.*/
5. Z:= and (row,A);
/* We obtain that Z(i)='1' if ROW(i,A) consists of bits ‘1’. */
6. End;
Proposition 1. Let T be a matrix, X be a slice, where positions of the matrix T rows being analyzed, are marked
with '1', and w be a pattern. Then the procedure MATCH(T,X,w,Z) returns the slice Z, where Z(i)='1' if and only if
ROW(i,T)=w and X(i)='1'.
Proof. We will prove this by contradiction. Assume that ROW(j,T)= w, X(j)='1' but Z(j)='0'. Let us analyze the
execution of the procedure MATCH. After performing lines 1-2, ROW(j,A) consists of ones because X(j)='1'. After
performing line 3, ROW(j,B) also consists of ones because we write the negation of every bit of ROW(j,T) that
corresponds to '0' in the given string w. Therefore after performing lines 4-5, ROW(j,A) consists of ones and Z(j)='1'.
This contradicts to our assumption.
Паралельне програмування. Розподілені системи і мережі
188
Obviously, on the MCA-machine, the procedure MATCH takes O(1) time.
Here we generalize the Falkoff algorithm. Let T be a given matrix consisting of n rows and k columns and F be a
given matrix of patterns or comparands consisting of m rows and k columns, where m≤n. We will select in parallel the
matrix T rows that coincide with a given set of m patterns. Our algorithm uses the following idea: at every i-th step of
computation, by means of bits '1', we store in parallel m groups of the matrix T rows such that each group stores
positions of those rows whose first i bits match the initial part of a concrete pattern.
Now we propose the procedure MultiMatch. It uses the number of bit columns k in the given matrix T and two
auxiliary matrices A and B. Note that the number of columns in A and B is equal to the number of patterns m in F.
procedure MultiMatch(T: table; X: slice(T); F: table; k: integer; var A: table);
/* Every i-th column of the matrix A saves with '1' positions of those rows of T that coincide with
the i-th pattern of the matrix F. */
var B: table; u,w1,w2: word(A); Y: slice(T); Z: slice(F);
1. Begin SET(w1); SCOPY(A,X,w1);
2. for i:=1 to k do
3. begin Y:=COL(i,T);
4. SCOPY(B,Y,w1);
5. Z:=COL(i,F);
6. w2:=CONVERT(Z);
7. u:= not w2; B:= not (B,u);
/* The columns of the matrix B marked with bits '1' in the row u are replaced with their negation. */
8. A:= and (A,B,w1);
9. end;
10. End;
Proposition 2. Let T be a matrix consisting of n rows and k columns and F be a matrix of patterns consisting of
m rows and k columns, where m≤ n. Let the selected rows of the matrix T be marked with '1' in the given slice X. Then
the procedure MultiMatch(T,X,F,k,A) returns a matrix A consisting of n rows and m columns whose every i-th column
stores positions of those matrix T rows that coincide with the pattern written in the i-th row of the matrix F.
Proof. (Sketch.) We prove this by induction in terms of the number of columns k in the matrix T.
Basis is checked for k=1. Then maximum two patterns '0' and '1' belong to F and m=2. After performing line 2,
the given slice X is written into both columns of the matrix A. After fulfilling lines 3-7, we first write the single column
of the matrix T into the slice Y. Then we store this slice in both columns of the matrix B. Further, the column of B, that
corresponds to the pattern '0', is replaced by not Y. Therefore after performing line 8, one column of the matrix A stores
positions of the matrix T rows that coincide with the pattern '1' and its another column saves positions of rows that
coincide with the pattern '0'.
Step of induction. Let the assertion be true for k1. We will prove it for k+1. To this end, we represent the
matrices T and F as T=T1T2, F=F1F2, where T1 consists of the first k columns of T and T2 is its (k+1)-th column. In the
same manner, we determine F1 and F2. After performing line 2, the given slice X will be written into k+1 columns of the
matrix A. By the inductive assumption, the assertion is true for T1 and F1, that is, after updating the first k columns of T,
every i-th column of the matrix A (1≤i≤m) saves with '1' the positions of the matrix T rows whose first k bits match the
initial part of the i-th pattern. Now, we perform the (k+1)-th iteration. Here, we reason by analogy with the basis.
Hence, after performing this iteration, every i-th column of the resulting matrix A saves with '1' the positions of the
matrix T rows which coincide with the i-th pattern of F.
This completes the proof.
On the MCA-machine, the procedure MultiMatch takes O(k) time, where k is the number of columns in the
matrix T. On the STAR-machine, such an algorithm can be implemented by fulfilling the procedure MATCH for every
pattern. Since on the STAR-machine the procedure MATCH takes O(k) time, the procedure MultiMatch requires O(km)
time.
Now, we enumerate two properties of the matrix A to be used below.
Property 1. The i-th row of the matrix A (1≤i≤n) consists of zeros if and only if the i-th row of T does not
belong to F.
Property 2. The j-th column of the matrix A (1≤j≤m) consists of zeros if and only if the j-th pattern from F does
not belong to T.
3. Implementing the first group of relational algebra operations on the MCA-machine
A relational database is defined as in [20]. Let Di be a domain, i=1,2,…,k. Let R denote a relation. It is
determined as a subset of the Cartesian product D1 D2 … Dk. An element of the relation R is called tuple and has
the form v=(v1,v2, …, vk), where viDi. Let Ai be the name of the domain Di, which is called attribute. Let
R(A1,A2,…,Ak) denote a scheme of the relation R.
Паралельне програмування. Розподілені системи і мережі
189
On the MCA-machine, any relation is represented as a matrix and each its tuple is allocated to one memory row.
Obviously, any relation consists of different tuples. We will assume the entire relation to fit in the hardware matrix of
the associative processing unit.
The relational algebra operations are divided into two groups. The first group consists of the following
operations: Intersection, Difference, Semi-join, Projection, and Division. The resulting relation for these operations is a
subset of the argument relations T and F. The second group consists of operations Product, Join, and Union. These
operations assemble a new relation.
We will consider applications of the multi-comparand search to the first group of relational algebra operations.
The corresponding procedures will use a global slice X to select with bits '1' positions of tuples in the relation T.
The operation Intersection has two argument relations T and F that are drawn from the same domain. The
resulting relation of this operation consists of those tuples that belong to T and F.
On the MCA-machine, this operation is implemented as follows.
procedure Intersection(T: table; X: slice(T); F: table; k: integer; var Y: slice(T));
var A: table;
1. Begin MultiMatch(T,X,F,k,A);
2. Y:= or (row,A);
3. Y:= Y and X;
4. End;
The correctness of this procedure is checked as follows. Since T and F are relations, there is at most a single bit
'1' both in every column and in every row of the matrix A (line 1). Therefore, after performing lines 2-3, Y(i)='1' if and
only if the i-th row of T is a tuple of the relation F.
Consider the operation Difference of relations T and F. The resulting relation consists of those tuples of T that do
not belong to F.
procedure Difference(T: table; X: slice(T); F: table; k: integer; var Y: slice(T));
var Z: slice(T);
Begin Intersection(T,X,F,k,Z);
Y:= X and ( not Z);
End;
Consider the operation Semi-join of relations T(T1,T2) and F. We assume that the attribute T2 of the relation T
and the relation F are drawn from the same domain. The resulting relation of the operation Semi-join consists of those
tuples ROW(i,T), for which there exists such j that ROW(i,T2)= ROW(j,F). Positions of the resulting tuples are marked
with '1' in the slice Y.
procedure Semi-join(T(T1,T2): table; X: slice(T); F: table; k: integer; var Y: slice(T));
/* Here, k is the number of columns in the relation F. */
Begin Intersection(T2,X,F,k,Y);
End;
It should be noted that the attribute T2 is not a relation. Therefore a tuple of F may coincide with a few rows of
T2. However, the resulting tuples form a relation as a subset of T.
The correctness of the procedures Difference and Semi-join is evident.
Let the relation T have two attributes T1 and T2. Consider the operation Projection2. The resulting relation of
this operation consists of the tuples from the relation T that have only different values of the second attribute. The
operation Projection1 is determined in the same manner.
procedure Projection2(T(T1,T2): table; X: slice(T); k: integer; var Y: slice(T));
/* Here, k is the number of columns in the attribute T2. */
var A: table;
1. Begin MultiMatch(T2,X,T2,k,A);
2. FRST(col,A);
3. Y:= or (row,A);
4. End;
Let us justify the correctness of this procedure. After performing line 1, every i-th column of the matrix A
(1≤i≤k) stores with '1' positions of rows of T2 that coincide with the pattern ROW(i,T2). Note that T2 is not a relation
in the general case. However, after performing line 2, in every i-th column of A, a single representative is saved. Notice
that after performing line 2 the matrix A may include some identical columns. Nevertheless, after performing line 3, the
slice Y saves the positions of tuples from the relation T having different values of the attribute T2.
Паралельне програмування. Розподілені системи і мережі
190
Now, we consider the operation Division. Let the relation T=(T1,T2) and the relation F be given. Let the relation
T be a divident and the relation F be a divisor. Let the values of T2 and F be drawn from the same domain. Then
T÷F={uT1 / vF, uvT}.
The implementation of the operation Division is complicated [18]. However, for the considered model, we can
propose a clear implementation of this operation.
On the MCA-machine, the procedure Division returns a slice Z, where the positions of rows from the attribute
T1 belonging to the result are marked with '1'.
procedure Division(T(T1,T2): table; X: slice(T); F: table; Y: slice(F); k: integer; var Z: slice(T));
/* Here, k is the number of columns in the attribute T1. */
var M,Q: slice(T); P: slice(F);
w: word(F); v1,v2: word(T1);
C: table; i: integer;
1. Begin P:= Y; M:= X;
2. SET(v1); CLR(v2);
3. SMERGE(T1,C,v1);
/* The matrix C is a copy of the attribute T1. */
4. RCOPY(C,v2,not X);
/* We write v2 into the rows of C marked with '0' in the slice X. */
5. while SOME(P) do
6. begin i:= STEP(P); w:= ROW(i,F);
7. MATCH(T2,M,w,Q);
8. Intersection(T1,Q,C,k,M);
9. RCOPY(C,v2,not M);
/* We write v2 into the rows of C marked with '0' in the slice M. */
10. end;
11. Z:=M;
12. End;
Remark 2. The procedure Intersection does not use a slice for the second relation. To obtain a sequence of the
embedded sets, we perform line 9 after every application of the procedure Intersection.
The correctness of the procedure Division is checked by induction in terms of the number of tuples in the
relation F.
Let us evaluate the time complexity of the considered procedures. On the MCA-machine, procedures
Intersection, Difference, Semi-join, and Projection2 take O(k) time each, where k is the number of columns in the
corresponding relation. On the STAR-machine, these procedures take O(kn) time each [13], where n is the number of
tuples in the relation T and k is the number of columns in T or in F.
On the MCA-machine, the procedure Division takes O(km) time, where m is the number of tuples in the relation
F and k is the number of columns in the attribute T1. On the STAR-machine, this procedure takes O(kmn) time [13],
where n is the number of tuples in the relation T and the parameters m and k were determined above.
It should be noted that the implementation of every operation from the first group on the MCA-machine and on a
modified version of the STAR-machine joined with the hardware support called the set intersection processor [12] takes
the same time.
4. Implementing the operation Product
The operation Product is defined as follows. Let T and F be argument relations for the operation Product. The
resulting relation R(R1,R2) is obtained as concatenation of all combinations of the relations T and F.
Let us explain the main idea of implementing the operation Product on the MCA-machine. Let the relation T
consist of p tuples and the relation F consist of s tuples. We first build the attribute R1, where s copies of every tuple
from T are written. We do this with the use of the operations MASK, RCOPY, and SHIFT. To build the attribute R2,
we first mark with '1' in a slice, say Z2, the positions of rows in R2, where p copies of the first tuple from F are written.
Then by means of the operations RCOPY and SHIFT, we write the tuples from the relation F into the corresponding
rows of R2.
procedure Product(T: table; F: table; var X: slice(T); var Y: slice(F); var R(R1,R2): table);
/* The rows of T are marked with '1' in the slice X, and the rows of F are marked with '1' in the slice Y. */
var i,j,p,s: integer; Z1,Z2,Z: slice(R); v: word(T); v1: word(F);
1. Begin p:=NUMB(X); s:=NUMB(Y);
2. MASK(Z,1,s);
/* We set '1' in the first s bits of the slice Z. */
3. while SOME(X) do
4. begin i:=STEP(X); v:=ROW(i,T);
5. RCOPY(R1,v,Z);
/* We copy the string v in the rows of R1 marked with '1' in the slice Z. */
Паралельне програмування. Розподілені системи і мережі
191
6. SHIFT(Z,down,s);
7. end;
8. CLR(Z1); Z1(1):='1';
9. CLR(Z2); Z2(1):='1';
10. for j:=1 to p-1 do
11. begin SHIFT(Z1,down,s);
12. Z2:=Z2 or Z1;
13. end;
/* We mark with '1' in Z2 positions of the matrix R2 rows where p copies of its first string are written. */
14. while SOME(Y) do
15. begin i:=STEP(Y);
16. v1:=ROW(i,F);
17. RCOPY(R2,v1,Z2);
/* We write the string v1 in the rows of R2 marked with '1' in Z2. */
18. SHIFT(Z2,down,1);
19. end;
20. End;
Proposition 3. Let a relation T have p tuples whose positions are marked with '1' in the slice X. Let a relation F
have s tuples whose positions are marked with '1' in the slice Y. Then the procedure Product returns the relation
R(R1,R2), where s copies of any tuple of T are created in the attribute R1, and p copies of the relation F tuples are
created in the attribute R2.
Proof. (Sketch.) We prove this by contradiction. Let there be such a tuple v1 in the relation T and a tuple v2 in
the relation F that v1v2 does not belong to the resulting relation R. We will prove this to contradict to execution of the
procedure Product.
Really, after performing lines 1-2, the variables p and s save the number of tuples in the relations T and F,
respectively, and the first s bits of the slice Z are equal to '1'. After fulfilling lines 3-6, we select the first tuple in the
relation T and simultaneously write it into the rows of the attribute R1 marked with '1' in the slice Z. After that we shift
the contents of the slice Z down by s bits. Hence, the slice Z will save the positions of rows in R1, where s copies of the
next tuple of T will be written. After execution of the cycle while SOME(X) do (lines 3-7), s copies of every tuple from
T will be written in R1. Hence, s copies of v1 are also written in the attribute R1. It is easy to check that after
performing lines 8-13, the slice Z2 saves the positions of rows in the attribute R2, where p copies of the first tuple from
F must be written. After execution of the cycle while SOME(Y) do (lines 14-19), p copies of a group of s tuples from F
are written in the attribute R2. Since the tuple v2 belongs to the relation F, it belongs to every copy of the group of s
tuples in the attribute R2. Let v1 be the k-th tuple in T and v2 be the i-th tuple in F. Then the tuple v1v2 has been written
in the (i+(k-1)s)-th row of the resulting relation R. This cotradicts to our assumption.
This completes the proof.
Let us evaluate the time complexity of the procedure Product. Obviously, on the MCA-machine, it takes O(p+s)
time.
In [12], we proposed an implementation of the operation Product on the STAR-machine. This implementation
uses an auxiliary matrix G obtained by compaction of the relation F. We have also shown how to implement this
operation using a modified version of the STAR-machine joined with a special hardware support called λ-processor.
This processor allows one to execute the matrix compaction by means of the vertical processing. As shown above, the
efficient implementation of the operation Product on the MCA-machine does not use the compaction of the relation F.
We avoid the compaction of a matrix due to the use of the operations SHIFT and RCOPY.
5. Conclusions
In this paper, we have proposed a multi-comparand associative machine and its application to parallel implementation
of classical relational algebra operations. We first consider an efficient associative algorithm for performing the multi-
comparand search in parallel. On the MCA-machine, this algorithm is implemented as procedure MultiMatch whose
correctness is proved. We have shown that this procedure takes O(k) time, where k is the number of columns in the
given matrix. On the STAR-machine, such an algorithm takes O(km) time, where m is the number of patterns. We have
also proposed applications of the multi-comparand search to carry out the first group of relational algebra operations:
Intersection, Difference, Semi-join, Projection, and Division. On the MCA-machine, these operations are represented
as corresponding procedures and their correctness is justified. We have shown that the procedure Division takes O(km)
time, where m is the number of tuples in the divisor and k is the number of columns in the attribute T1 of the divident
T(T1,T2). Other procedures take O(k) time each, where k is the number of columns in the corresponding relation.
Паралельне програмування. Розподілені системи і мережі
192
We have also proposed the efficient implementation of the operation Product on the MCA-machine and evaluated its
time complexity. We have shown that all these estimations are optimal. We have obtained clear and simple
implementations of the proposed associative algorithms due to the access data by contents and the use of data
parallelism. We achieve the fastest processing because the structure of input data and applied algorithms correspond in
the best way to the structure of the model. It might be well to use the MCA-machine for simulating and specifying
different properties of new associative systems. The efficient non-trivial procedure Multi-Match may be of advantage
when different associative algorithms use the fast parallel search.
We are planning to study some applications of the MCA-machine to the image processing.
1. Falkoff A.D. Algorithms for parallel-search memories // J. of the ACM. – 1962. – 9. Р. 448–510.
2. Fernstrom C., Kruzela J., Svensson B. LUCAS Associative Array Processor. Design, Programming and Application Studies, Lecture Notes in
Computer Science. – Berlin; Springer-Verlag, 1986. – 216 р.
3. Foster C.C. Content Addressable Parallel Processors, Van Nostrand Reinhold Company, New York, 1976.
4. Irakliotis L.J., Betzos G.A., Mitkas P.A. Optical associative processing, in: A. Krikelis, C.C. Weems (Eds.) // Associative Processing and
Processors, IEEE Computer Society – 1997. – Р. 155–178.
5. Kapralski A. Sequential and Parallel Processing in Depth Search Machines – Singapore; World Scientific, 1994.
6. Kokosinski Z. An associative processor for multi-comparand parallel searching and its selected applications // Proc. Int. Conf. on Parallel and
Distributed Processing Techniques and Applications, PDPTA'97, Las Vegas, USA. – 1997. – Р. 1434–1442.
7. Kokosinski Z., Sikora W. An FPGA implementation of multi-comparand multi-search associative processor // Proc. 12th Int. Conf. FPL'2002,
Lect. Notes in Comp. Sci. – Berlin; Springer-Verlag, v. 2438, 2002. – Р. 826–835.
8. Louri A., Hatch J.A. Jr. An optical associative parallel processor for high–speed database processing, Computer. // 1994. – v. 27. – Р. 65–72.
9. Muraszkiewicz M.R. Cellular array architecture for relational database implementation // Future Generations Computer Systems 1988, v. 4.
– Р. 31–38.
10. Nepomniaschaya A.S. Language STAR for associative and parallel computation with vertical data processing // Proc. of the Intern. Conf. on
Parallel Computing Technologies, World Scientific. – Singapore. – 1991. – Р. 258–265.
11. Nepomniaschaya A.S., Kokosinski Z. Associative graph processor and its properties // Proc. of the Intern. Conf. PARELEC'2004, IEEE
Computer Society. – Dresden, Germany, 2004 – Р. 297–302.
12. Nepomniaschaya A.S., Fet Y.I. Investigation of some hardware accelerators for relational algebra operations // Proc. of the First Aizu Intern.
Symp. on Parallel Algorithms / Architecture Synthesis, IEEE Computer Society. – Aizu-Wakamatsu, Fukushima, Japan, 1995. – Р. 308–314.
13. Nepomniaschaya A.Sh. A language STAR for associative and bit-serial processors and its application to relational algebra // Bulletin of the
Novosibirsk Computing Center, Ser. Computer Science, Issue 1, NCC Publisher. – 1993. – Р. 23–36.
14. Nepomniaschaya A.S. An associative version of the Bellman-Ford algorithm for finding the shortest paths in directed graphs // Proceedings of
the 6-th Intern. Conf. PaCT–2001, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2001. – v. 2127. Р 285–292.
15. Nepomniaschaya, Dvoskina M.A. A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors, Fundamenta
Informaticae // IOS Press, Amsterdam. – v. 43. – 2000. – Р. 227–243.
16. Nepomniaschaya A.S. Efficient implementation of Edmonds' algorithm for finding optimum branchings on associative parallel processors //
Proc. of the Eighth Intern. Conf. on Parallel and Distributed Systems (ICPADS'01), IEEE Computer Society. – KyongJu City, Korea. – 2001.
– Р . 3–8.
17. Nepomniaschaya A.S. Efficient update of tree paths on associative systems with bit-parallel processing // Bulletin of the Novosibirsk
Computing Center. Ser. Computer Science, Issue: 23, NCC Publisher. – 2005. – Р. 71–83.
18. Ozkarahan E. Database Machines and Database Management. – Prentice-Hall, Inc. 1986.
19. Parhami B. Search and data selection algorithms for associative processors / A. Krikelis, C.C. Weems (еds.) // Associative Processing and
Processors, IEEE Computer Society. – 1997. – Р. 10–25.
20. Ullman J.D Principles of Database Systems, Computer Science Press. – 1980.
|