Mappings for conflict-free access of paths in bidimensional arrays, circular lists, and complete trees.
Since the divergence between the processor speed and the memory access rate is progressively increasing, an efficient partition of the main memory into multibanks is useful to improve the overall system performance. The effectiveness of the multibank partition can be degraded by memory conflicts, that occur when there are many references to the same memory bank while accessing the same memory pattern. Therefore, mapping schemes are needed to distribute data in such a way that data can be retrieved via regular patterns without conflicts. In this paper, the problem of conflict-free access of arbitrary paths in bidimensional arrays, circular lists and complete trees is considered for the first time and reduced to variants of graph-coloring problems. Balanced and fast mappings are proposed which require an optimal number of colors (i.e., memory banks). The solution for bidimensional arrays is based on a particular Latin Square. The functions that map an array node or a circular list node to a memory bank can be calculated in constant time. As for complete trees, the mapping of a tree node to a memory bank takes time that grows logarithmically with the number of nodes of the tree. The problem solved here has further application in minimizing the number of frequencies assigned to the stations of a wireless network so as to avoid interference.
Introduction
In recent years, the traditional divergence between the processor speed and the memory access rate is
progressively increasing. Thus, an efficient organization of the main memory is important to achieve
high-speed computations. For this purpose, the main memory can be equipped with cache memories
which have about the same cycle time as the processors - or can be partitioned into multibanks.
Since the cost of the cache memory is high and its size is limited, the multibank partition has mostly
been adopted, especially in shared-memory multiprocessors [3]. However, the effectiveness of such a
memory partition can be limited by memory conflicts, that occur when there are many references to
the same memory bank while accessing the same memory pattern. To exploit to the fullest extent the
performance of the multibank partition, mapping schemes can be employed that avoid or minimize the
memory conflicts [15]. Since it is hard to find universal mappings - mappings that minimize conflicts
for arbitrary memory access patterns - several specialized mappings, designed for accessing regular
patterns in specific data structures, have been proposed in the literature (see [12, 2] for a complete list
of references).
In particular, for bidimensional arrays, Budnik and Kuck [7], Balakrishnan et al. [4], Kim and
Prasanna [12], and Das and Sarkar [8] studied mappings that provide conflict-free access to rows,
columns, positive and negative diagonals, subarrays, and distributed subarrays. The techniques used
range from Latin squares to Perfect Latin squares, from linear mappings to quasi-groups [11]. Subse-
quently, mappings for other data structures like complete trees and binomial trees have been devised.
In particular, mappings that provide conflict-free access to complete subtrees, root-to-leaves paths, sub-
levels, and composite patterns obtained by their combination, have been investigated in [8, 9, 1, 10, 14].
The mapping schemes proposed in those papers are optimal, i.e., they use as few memory modules as
possible; balanced, i.e., the nodes of data structures are distributed as evenly as possible among the
banks; fast, i.e., the bank address to which a node is assigned is computed quickly with no knowledge
of the entire structure mapping; and flexible, i.e., they can be used for templates of different size.
In the present paper, optimal, balanced and fast mappings are designed for conflict-free access of
paths in bidimensional arrays, circular lists, and complete trees. With respect to the above mentioned
papers, paths in bidimensional arrays and circular lists are dealt with for the first time. Moreover, access
to any (not only to root-to-leaves) paths in complete trees is provided. The remainder of this paper
is organized as follows. In Section 2, the conflict-free access problem is formally stated. In Section 3,
the problem of accessing paths in bidimensional arrays is solved. The proposed solution is a variant
of a graph-coloring, which requires an optimal number of colors and is achieved using a combinatorial
object similar to a Latin Square. As a byproduct, the memory bank to which an array node is assigned
is computed in constant time. In Section 4, the problem of accessing paths in circular lists is optimally
solved and the function that maps a circular list node to a memory bank can be calculated in constant
time. In Section 5, the same problem on complete trees is also optimally solved via a variant of a graph-coloring
problem. The time needed to assign a tree node to a memory bank grows logarithmically with
the number of nodes of the tree. Conclusions are offered in Section 6.
Conflict-Free Access
When storing a data structure D, represented in general by a graph, on a memory system consisting
of N memory banks, a desirable issue is to map any subset of N arbitrary nodes of D to all the N
different banks. This problem can be viewed as a coloring problem where the distribution of nodes of
D among the banks is done by coloring the nodes with a color from the set f0;
it is hard to solve the problem in general, access of regular patterns, called templates, in special data
structures - like bidimensional arrays, circular lists, and complete trees - are considered hereafter.
A template T is a connected subgraph of D. The occurrences fT of T in D are the
template instances. For example, if D is a complete binary tree, then a path of length k can be a
template, and all the paths of length k in D are the template instances.
After coloring D, a conflict occurs if two nodes of a template instance are assigned to the same
memory bank, i.e., they get the same color. An access to a template instance T i results in c conflicts if
belong to the same memory bank.
Given a memory system with N banks and a template T , the goal is to find a memory mapping
that colors the nodes of D in such a way that the number of conflicts for accessing any
instance of T is minimal. In fact, the cost for T i colored according to U , CostU (D; defined as
the number of conflicts for accessing T i . The template instance of T with the highest cost determines
the overall cost of the mapping U . That is,
A mapping U is conflict-free for T if
Among desirable properties for a conflict-free mapping, a mapping should be balanced, fast, and
optimal. A mapping U is termed balanced if it evenly distributes the nodes of the data structure among
the N memory banks. For a balanced mapping, the memory load is almost the same in all the banks.
A mapping U will be called fast if the color of each node can be computed quickly (possibly in constant
time) without knowledge of the coloring of the entire data structure. Among all possible conflict-free
mappings for a given template of a data structure, the more interesting ones are those that use the
minimum possible number of memory banks. These mappings are called optimal. It is worth to note
that not only the template size but also the overlapping of template instances in the data structure
determine a lower bound on the number of memory banks necessary to guarantee a conflict-free access
scheme. This fact will be more convincing by the argument below for accessing paths in D.
E) be the graph representing the data structure D. The template P k is a path of
length k in D. The template instance P k [x; y] is the path of length k between two vertices x and y in
V , that is, the sequence of vertices such that (v h ; v h+1
The conflicts can be eliminated on P k [x; y] if are assigned to all different memory
banks. The conflict-free access to P k can be reduced to a classical coloring problem on the associated
graph GDP k
obtained as follows. The vertex set of GDP k
is the same as the vertex set of GD , while
the edge (r; s) belongs to the edge set of GDP k
iff the distance d rs between the vertices r and s in GD
satisfies d rs - k, where the distance is the length of the shortest path between r and s. Now, colors
must be assigned to the vertices of GDP k
so that every pair of vertices connected by an edge is assigned
a couple of different colors and the minimum number of colors is used. Hence, the role of maximum
clique in GDP k
is apparent for deriving lower bounds on the conflict-free access on paths. A clique K
for GDP k
is a subset of the vertices of GDP k
such that for each pair of vertices in K there is an edge.
By well-known graph theoretical results, a clique of size n in the associated graph GDP k
implies that at
least n different colors are needed to color GDP k
. In other words, the size of the largest clique in GDP k
is a lower bound for the number of memory banks required to access paths of length k in D without
conflicts.
On the other hand, the conflict-free access to P k on GD is equivalent to color the nodes of GD in
such a way that any two nodes which are at distance k or less apart have assigned different colors.
Unfortunately, this latter coloring problem is NP-complete [13] for general graphs. This justifies the
investigation either for good heuristics for general graphs or optimal algorithms for special classes of
graphs. In the next three sections, optimal mappings for bidimensional arrays, circular lists and complete
binary trees will be derived for conflict-free accessing P k .
Accessing Paths in Bidimensional Arrays
Let a bidimensional array A be the data structure D to be mapped into the multibank memory system.
An array r \Theta c has r rows and c columns, indexed respectively from 0 to r \Gamma 1 (from top to bottom)
and from 0 to c \Gamma 1 (from left to right), with r and c both greater than 1.
The graph E) representing A is a mesh, whose vertices correspond to the elements of
A and whose arcs correspond to any pair of adjacent elements of A on the same row or on the same
column. For the sake of simplicity, A will be used instead of GA since there is no ambiguity. Thus, a
generic node x of A will be denoted by its row index and j is its column index.
least
l (k+1) 2m
memory banks are required for conflict-free accessing P k in A.
Proof Consider a generic node of A, and its opposite node at distance k on the same
column, i.e., All the nodes of A at distance k or less from both x and y are mutually at
distance k or less, as shown in Figure 1. Therefore, in the associated graph GAP k , they form a clique,
and they must be assigned to different colors. In details, such a clique, denoted as KA (x; k), is defined
as follows:
KA
ni
l km
l km
l km
l km
l kmo
Summing up over t, the size of the clique results to be
''- k-
Hence, at least
l (k+1) 2m
colors are required. 2
(b)
x
x
y
y

Figure

1: A subset KA (x; of nodes of A that forms a clique in GAP k
Below, a conflict-free mapping is given to color all the nodes of an array A using as few colors as in
Lemma 1. Therefore, the mapping is optimal. From now on, the color assigned to node x is denoted
by fl(x).
Algorithm Array-Coloring (A; k);
l (k+1) 2m
and
even
if k is odd
ffl Assign to each node x = (i; A the color
Intuitively, the above algorithm first covers A with a tessellation of basic sub-arrays of size M \Theta M .
Each basic sub-array S is colored in a Latin Square fashion as follows:
ffl the colors in the first row of S appear from left-to-right in the sequence 0;
ffl the color sequence for a generic row is obtained from the sequence at the previous row by a \Delta
left-cyclic shift.
For the coloring of A, decomposed into 6 basic sub-arrays of size M \Theta M , is illustrated in

Figure

2.
Theorem 1 The Array-Coloring mapping is optimal, fast, and balanced.
Proof To prove optimality, it must be shown that the mapping is conflict-free and that the
minimum number of colors is used.
Figure

2: An array A of size 16 \Theta 24 with a tessellation of 6 sub-arrays of size 8 \Theta 8 colored by the
Array-Coloring algorithm to conflict-free access P 3 .
Consider a generic node x = (g; f) of A and the associated clique KA (x; k), defined in Lemma 1. In
order to prove that the mapping is conflict-free, one only needs to show that all the nodes of KA (x; k),
which are mutually at distance no more than k, are assigned by the Array-Coloring algorithm to different
colors. Formally, consider an arbitrary pair of nodes belonging to KA (x; k),
such that 0, the roles of w and z could be swapped). Then the mapping is
conflict-free if the Array-Coloring algorithm guarantees that the colors fl(w) and fl(z) are different.
Moreover, let oe(w; z) be the difference between
the two colors assigned to w and z. Then, the mapping is conflict-free if the following two conditions
simultaneously hold:
(1)
In order to show that the conditions in (1) hold for any pair of nodes of KA (x; k), the two cases k
even and k odd must be distinguished.
When k is even, one has that
l (k+1) 2m
that oe(w; z)
the congruence oe(w; z) 6j 0 mod M is equivalent to oe(w; z) 6= 0 and oe(w; z) 6= M .
Clearly, oe(w; which is verified only if either z = w or j' \Gamma jj is a
multiple of k + 1. But, since j' \Gamma jj - k implies oe(w; z) 6= 0, no two distinct nodes of KA (x; can have
the same color.
Thus, it remains to prove that oe(w; z) 6= M . Assume by contradiction that oe(w;
Therefore, three cases may occur:
l M
In case (i), oe(w;
which contradicts the fact that jj \Gamma 'j - k.
In case (ii), oe(w; z) can be equal to M if and only if
is,
. Thus, in case (ii), for any pair of nodes z and w of
KA (x; which do not satisfy the first condition in (1), it results that is equal to a positive integer
and precisely,
But this violates the second condition in (1) because (i
Finally, in case (iii), oe(w; if and only if jj \Gamma
1). That is, for any pair
of nodes z and w of KA (x; not satisfying the first condition in (1), it yields precisely,
But again this violates the second condition in (1) because the distance between w and z is (i
In conclusion, for k even, any two nodes whose colors differ exactly by M are k
relative positions are depicted in Figure 3(a).
When k is odd, it follows that
l (k+1) 2m
that oe(w; z)
equivalent to oe(w; z) 6= 0 and oe(w; z) 6= M .
Clearly, oe(w; which is verified only if either
or is a multiple of k. Hence, two distinct nodes of KA (x; which have the same
color are at distance (i
It remains to prove that oe(w; z) 6= M . As before, three cases may occur:
l M
Note that
2 and
l M
Repeating the same reasoning done for k even, one can show again that any two nodes whose colors
differ by M are k apart. Their relative positions are illustrated in Figure 3(b).
So, the Array-Coloring Algorithm is conflict-free. Moreover, since it uses the minimum number of
colors, the proposed mapping is optimal.
(b)
(a)

Figure

3: Relative positions in A of two nodes which are assigned to the same color: (a) k even, (b) k
odd.
It is easy to see that the time required to color all the nodes of an array is O(n). Moreover,
to color only a single node x = (i; j) of the tree requires only O(1) time, since
and hence the mapping is fast.
In order to prove that the mapping is balanced, observe that each color appears once in each sub-row
of size M . Hence, the number m of nodes with the same color verifies rb c
e: 2
Observe that the Array-Coloring Algorithm guarantees conflict-free access to some paths longer than
k. Specifically, it is possible to access without conflicts any horizontal path of length M and any vertical
path of length
g.c.d.(M;\Delta) because L is the minimum integer such that Finally,
since the distance between two consecutive nodes on the same diagonal of A is 2, any b k
consecutive
elements on a diagonal can be accessed with no conflicts.
Accessing Paths in Circular Lists
Let a circular list C be the data structure D to be mapped into the multibank memory system. A
circular list of n nodes, indexed consecutively from 0 to n \Gamma 1, is a sequence of n nodes such that node
i is connected to both nodes (i \Gamma 1) mod n and (i
The graph E) representing C is a ring, whose vertices correspond to the elements of C
and whose arcs correspond to any pair of adjacent elements of C. For the sake of simplicity, C will be
used instead of GC since there is no ambiguity.
At least M memory banks are required for conflict-free accessing P k in C.
Proof For conflict-free accessing P k in C two nodes with the same color must be at distance at
least k + 1. When all the nodes are mutually at distance less than k and must all be colored
with different colors. When each color may appear at most
times. Therefore,
Figure

4: Conflict-free access to P 4 in a circular list C of 13 nodes colored by the Circular-List-Coloring
algorithm with 7.
at least
\Upsilon colors are needed. Observed that
follows that at
least
memory banks are required. 2
Below, an optimal conflict-free mapping is provided to color all the nodes of a circular list C using
as few colors as in Lemma 2. As before, the color assigned to node x is denoted by fl(x).
Algorithm Circular-List-Coloring (C; k);
ffl Assign to node x 2 C, the color
Note that a linear (that is, non circular) list L can be optimally colored to conflict-free access P k with
which matches the trivial lower bound given by the number of nodes in P k . In fact,
L can be optimally colored by a naive algorithm which assigns to node x the color
Such a naive algorithm does not work for circular lists. For example, consider the circular list C of
nodes, shown in Figure 4, to be colored to access P 4 . Applying the naive algorithm with M
only the first 10 nodes can be feasibly colored with 5 colors, but 3 additional colors are then required
for feasibly coloring the last 3 nodes, for a total of 8 colors. In contrast, the optimal Circular-List-
(b)
(a)

Figure

5: A circular list C of 17 nodes colored to conflict-free access P 3 according to: (a) the Circular-
Coloring algorithm requires 7 colors only. Moreover, it is worth to point out that the naive algorithm
does not always work for circular lists even when applied with M
. For
instance, for 5. Applying the naive algorithm with M
to this instance, 15 nodes can be colored using 5 colors, but 2 additional colors are needed for feasibly
coloring the last 2 nodes for a total of 7 colors (as shown in Figure 5(b)). Instead, the optimal coloring
provided by the Circular-List-Coloring algorithm uses only 5 colors, as shown in Figure 5(a). Indeed,
the naive algorithm always produces a feasible (although not necessarily optimal) coloring if applied
using
Theorem 2 The Circular-List-Coloring mapping is optimal, fast, and balanced.
Proof To prove optimality, two cases may be distinguished. If
and the Circular-List-Coloring algorithm reuses the same color at distance M . Hence, no
conflict arises. If n 6j 2. Two nodes get the same color only if they
are at distances M or M \Gamma 1, which are both greater than or equal to k+ 1. Hence, as before, no conflict
arises. Since the algorithm uses as few colors as possible, the mapping is optimal. It is also fast since
each node is colored in constant time. Finally, each color is assigned to exactly n
nodes when n is a
multiple of M , and no more than
l min(n;')
l max(n\Gamma';0)
nodes are colored with the same color in
all the other cases. 2
It is interesting to note at this point that, given a circular list of n nodes, the minimum number
of colors required to conflict-free access P k satisfies the following properties (see Figure 6):
ffl Up to results, i.e. all the nodes must have different colors. Indeed,
all of them are mutually at distance no more than k and, therefore, they form a clique on the
graph
depends on both n and k, and, for a fixed k, is not a monotone
M(n,

Figure

The number of colors M(n; 6) required to conflict-free access P 6 when n ranges between 1
and 58.
function of n. In contrast, for arrays and trees (as will be proved in the next section), M depends
only on k and is monotone.
Accessing Paths in Complete Trees
Let a rooted complete binary tree B be the data structure to be mapped into the multibank memory
system. The level of node x 2 B is defined as the number of edges on the path from x to the root,
which is at level 0. The maximum level of the nodes of B is the height of B. Let LevB (i) be the set of
all nodes of B at level i - 0.
A complete binary tree of height H is a rooted tree B in which all the leaves are at the same level
and each internal node has exactly 2 children. Thus, LevB (i) contains 2 i nodes. The h-th ancestor of
the node (i; j) is the node (i
its children are the nodes (i
in the left-to-right order.
From now on, the generic node x, which is the j-th node of LevB (i), with counting from left
to right, will be denoted by Therefore, the generic path instance P k [x; y] will be denoted by
Lemma 3 At least
memory banks are required to conflict-free access P k in B.
Proof Consider a generic node x = (i; j). All the 2 b k
nodes in the subtree S of height b k
rooted at the b k
c-th ancestor of x are mutually at distance not greater than k.
In addition, consider the d k
, ancestors of x, on the path I of length d k
2 e from
the b k
c-th ancestor of x up to the k-th ancestor of x. All these nodes are at distance not greater than
k from node x, and together with the nodes of S they are at mutual distance not greater than k.
x
(a)
(b)

Figure

7: A subset KB (k) of nodes of B that forms a clique in
Moreover, for
nodes in the complete subtree of height
rooted at the - j 's child which does not belong to I. Such nodes are at distance
not greater than k from x. Furthermore, these nodes, along with the nodes of S and I, are all together
at mutual distance not greater than k.
Hence, in the associated graph GDP k
there is at least a clique of size
From that, the claim easily follows. Figure 7 shows a subset KB (k) of nodes of B which are at pairwise
distance not greater than k, for 4, and hence forms a clique in the associated graph GBP kAn optimal conflict-free mapping to color a complete binary tree B acts as follows.
A basic subtree KB (k) defined as in the proof of Lemma 3 is identified and colored. Such a tree is
then overlaid to B in such a way that the uppermost
levels of B coincide with the lowermost
levels of KB (k). Then, the complete coloring of B is produced level by level by assigning to each node
the same color as an already colored node.
Formally, for a given k, define the binary tree KB (k) as follows:
ffl KB (k) has a leftmost path of k nodes.
ffl the root of KB (k) has only the left child;
ffl a complete subtree of height is rooted at the right child of the node at level i on the leftmost
path of KB (k).
(a) (b)6 7 8 934

Figure

8: Coloring of B for conflict-free accessing: (a) P 3 , (b) P 4 . (Both KB (3) and KB (4) are depicted
by dash splines.)
The
nodes of KB (k) must be colored with 2 b k
different colors. Thus,
the uppermost
levels of B are already colored.
For the sake of simplicity, to color the remaining part of B, the levels are counted starting from
the root of KB (k). That is, the level of the root of B will be renumbered as level
1. Now, fixed
the algorithm to color B acts as follows.
Algorithm Binary-Tree-Coloring (B; k);
ffl Color KB (k) with M colors;
ffl Visit the tree B in breadth first search, and for each node x of B, with
mod 2;
- Assign to x the same color as that of the node y
and
Examples of colorings to conflict-free access P 3 and P 4 are illustrated in Figure 8.
x
y
Figure

9: For inherits the same color as node y
Theorem 3 The Binary-Tree-Coloring mapping is optimal, fast and balanced.
Proof. To prove that the mapping is optimal, it must be shown that it is conflict-free and it uses
as few colors as those given by Lemma 3. First, observe that the 2 b k
c leaves of a subtree of height
are at mutual distance not greater than k, and therefore they must be colored with all different
colors. Thus, let each level of B be partitioned (starting from the leftmost node) into consecutive
blocks of size 2 b kc . The block b(i; w), with w - 0, at level i of B consists of the 2 b kc consecutive
nodes (i; w2 b k
which must all be assigned to a different color.
Consider the node x = (i; j) to be colored. The node x = (i; belongs to the block b
and it appears in the (- position inside the block. Consider the leftmost node z of b x , where
. Then, a generalization KB (z; of KB (k) can be defined depending on z.
KB (z; includes the following nodes of B:
ffl the nodes on the path \Gamma of length k from the father of z up to the (k 1)-th ancestor of z;
ffl for
the nodes of the complete binary tree S q of height k \Gamma q rooted at the child,
which does not belong to \Gamma, of the q-th ancestor of z;
ffl the nodes of the complete binary tree S of height
rooted at the
-th ancestor of z.
It is crucial to note that all the following nodes are at distance k + 1 from all the nodes in b x :
(i) the root of KB (z; k),
(ii) the leaves of S q , with
(iii) the leaves of S, which are not parents of any node in b x .
The nodes of b
are colored from left to right copying the same colors used in the
nodes of KB (z; specified in (i), (ii), and (iii) above, and considered by increasing level and from left
to right, as illustrated in Figures 10 and 11 for k even and odd, respectively. In particular,
is assigned to the same color as the root of KB (z; k), which is the
ancestor of x;
2, the 2 k\Gammaq nodes of b x , (i; b j
are assigned to the same colors as the leaves of the tree S q .
Observe that the number of nodes colored with the two steps above is 1
When k is odd, this is enough to color the entire block since 2 d k
c . In fact, the
set of nodes of KB (z; specified in (iii) above is empty for k odd. In contrast, when k is even, only
the first half of the block has been colored since 2 d k
to color the second half of
the block, one further step is required, which uses the colors of the nodes of KB (z; specified in (iii)
above:
ffl The rightmost 2 b k
nodes of b x are assigned to the same colors as the rightmost (resp., leftmost)
leaves of the complete binary tree rooted at (
1)-th ancestor of z, depending on the
fact that the
-th ancestor of z is a left (resp., right) child of its father.
In order to prove that the mapping is conflict-free, an inductive reasoning on the level i of the tree
is followed. The basis for the induction is when the tree coincides with KB (k) and it is colored,
by definition, with all different colors. For i ? k, consider a generic node x = (i; j), its block b x and
its leftmost node z. By inductive hypothesis, all the nodes in the tree up to level are colored in a
conflict-free manner, but with color repetitions. In particular, the subtree KB (z; k) is conflict-free and
since its nodes are mutually at distance at most k they must have been assigned to all different colors.
The algorithm colors b x copying the colors of some nodes in KB (z; k), specified in (i), (ii), and (iii),
which are exactly at distance k + 1 from the nodes of b x . Therefore, there are no color repetitions in b x
and no conflict can arise. Note that nodes in different blocks at level i may inherit the same color, but
since any two nodes in different blocks are at distance at least k conflict can arise. Therefore, all
the nodes in the tree up to level i are colored in a conflict-free manner.
Finally, since the tree is colored with the colors of KB (k), whose number equals the lower bound of
Lemma 3, the tree-coloring mapping is optimal.
It is easy to see that the time required to color all the n nodes of a tree is O(n). However, to color
only a single node x of the tree requires only O(log n) time since, in the worst case, all the nodes along
a path from x up to the root must have been colored.
One can readily see that, if the height H of the tree B is a multiple of k, then the nodes of B can be
partitioned into
subsets, each of which induces a copy of KB (k). Therefore, each color
is used m times, and the mapping is balanced. 2
z
G

Figure

10: The generalization KB (z; 6) of KB (6) for the node z. The root of KB (z; 6), the leaves of the
and the rightmost leaves of S are used to color the nodes in the block b z .
G
z

Figure

11: The generalization KB (z; 5) of KB (5) for the node z. The root of KB (z; 5) and the leaves of
the subtrees S 4 and S 5 are used to color the nodes in the block b z .
The results shown for binary trees can be extended to a q-ary tree Q, with q - 2.
Corollary 1 At least
memory modules are required to conflict-free access P k in a q-ary tree Q. 2
Similarly to the binary case, for a given k, define a q-ary tree K q
ffl K q
Q (k) has a leftmost path of k
ffl the root of K q
Q has only the leftmost child;
ffl a complete subtree of height is rooted at the q \Gamma 1 rightmost children of the node at level i
on the leftmost path of K q
Such a K q
Q (k) is then overlaid to Q in such a way that the uppermost
levels of Q coincide with
the lowermost
levels of K q
Then, the complete coloring of Q is produced level by level by
assigning to each node the same color as an already colored node.
For the sake of simplicity, to color the remaining part of Q, the levels are again counted starting
from the root of K q
That is, the level of the root of Q will be renumbered as level
1. Now,
the algorithm to color Q is the following:
Algorithm q-ary-Tree-Coloring (Q; k);
ffl Color K q
ffl Visit the tree Q in breadth first search, and for each node x of Q, with
do:
mod q;
- Assign to x the same color as that of the node y
and
By a reasoning similar to that employed for complete binary trees, the optimality of the q-ary-Tree-
Coloring Algorithm easily follows.
6 Conclusions
In this paper, the problem of conflict-free accessing arbitrary paths P k in particular data structures,
such as bidimensional arrays, circular lists and complete trees, has been considered for the first time
and reduced to variants of graph-coloring problems. Optimal, fast and balanced mappings have been
proposed. Indeed, the memory bank to which a node is assigned is computed in constant time for arrays
and circular lists, while it is computed in logarithmic time for complete trees. However, it remains as
an open question whether a tree node can be assigned to a memory bank in constant time.
On the other hand, the conflict-free access to P k on an arbitrary data structure D is NP-complete
[13], and this justifies the investigation of good heuristics. This problem is equivalent to the classical
node coloring problem in the associated graph GDP k
. Therefore, it can be solved by the most effective
coloring heuristic known so far, that is, the saturation-degree heuristic [6], which works as follows. Let
N(x) be the neighborhood of node x in the associated graph GDP k
. At each iteration, the saturation-
degree heuristic selects the node x to be colored as one with the largest number of different colors
already assigned in N(x). Ties between nodes are broken by preferring the node x with the largest
number of colored nodes in N(x). Once selected, node x is assigned the lowest color not yet assigned
in N(x).
As experimentally proved in [5], the saturation-degree heuristic is especially effective when the
minimum number of colors is given by the size of the largest clique K of GDP k
. Therefore, it should
work efficiently also for the conflict-free access problem, and, in particular, for d-dimensional arrays
as well as for generic, i.e. not necessarily complete, trees. Indeed, it is expected in such cases that
the minimum number of required memory banks be equal to the lower bound given by the size of the
largest clique K of GDP k
, as happened for bidimensional arrays and complete trees. Unfortunately,
the resulting coloring is not guaranteed to be optimal, fast or balanced. Moreover, it is still an open
question to determine whether the problem of conflict-free accessing paths on d-dimensional arrays and
generic trees is NP-complete.
Finally, in a more practical perspective, the number of memory banks available could be fixed to a
constant -, depending on the memory configuration. Then, if the number of memory modules M(k)
required for a given P k is larger than -, no conflict-free access is possible. However, assume that P k 0 is
the longest path that can be accessed without conflicts using - memory banks, i.e. M(k 0 ) -. Then,
accessing P k , no more than d k
conflicts may arise. Hence, the proposed mappings are scalable.

Acknowledgement

The authors are grateful to Richard Tan for his helpful comments, and to Thomas McCormick for having provided the
reference [13].



--R

"Toward a Universal Mapping Algorithm for Accessing Trees in Parallel Memory Systems"
"Multiple Template Access of Trees in Parallel Memory Systems"
"Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors"
"On Array Storage for Conflict-Free Memory Access for Parallel Processors"
"Assigning Codes in Wireless Networks: Bounds and Scaling Properties"

"The Organization and Use of Parallel Memories"
"Conflict-Free Data Access of Arrays and Trees in Parallel Memory Systems"
"Parallel Priority Queues in Distributed Memory Hypercubes"
"Load Balanced Mapping of Data Structures in Parallel Memory Modules for Fast and Conflict-Free Templates Access"
New York

"Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem"
"Conflict-Free Template Access in k-ary and Binomial Trees"
"Theoretical Limitations on the Efficient Use of Parallel Memories"
--TR
Conflict-free template access in <italic>k</italic>-ary and binomial trees
Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors
Multiple templates access of trees in parallel memory systems
Assigning codes in wireless networks
New methods to color the vertices of a graph
Latin Squares for Parallel Array Access
Optimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes
Load Balanced Mapping of Data Structures in Parallel Memory Modules for Fast and Conflict-Free Templates Access
Toward a Universal Mapping Algorithm for Accessing Trees in Parallel Memory Systems

--CTR
Alan A. Bertossi , Cristina M. Pinotti , Richard B. Tan, Channel Assignment with Separation for Interference Avoidance in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.222-235, March
Sajal K. Das , Irene Finocchi , Rossella Petreschi, Conflict-free star-access in parallel memory systems, Journal of Parallel and Distributed Computing, v.66 n.11, p.1431-1441, November 2006
bidimensional array;conflict-free access;complete tree;path template;multibank memory system;mapping scheme;frequency assignment;circular list