FORM -2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
Specification
(See Section 10 and rule 13)


CLUSTER COMPUTING
COMPUTATIONAL RESEARCH LABORATORIES LTD.
an Indian Company of Survey No. 103/A, Ground Floor, Pride Portal, Bahirat Wadi, Senapati Bapat Road, Pune 411 016, Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION


Field of the invention:
This invention relates to field of cluster computing.
Particularly this invention relates to connecting computers forming a cluster for increased computational capability.
Background of the Invention:
Connecting computers in a cluster is an important way of increasing computational power available to solve large problems. An important part of a cluster is the underlying connectivity network. Ideally an all connect network which allows any combination of computers to talk to each other is required. That is if N computers labeled {0. 1, ... N-l}, the connectivity network should support any permutation. The other step is to partition the communication pattern in the program so that it can be broken into a sequence of non-conflicting permutation patterns. Having an all connect network is prohibitively expensive for large N as it will require N*(N-l)/2 connections. Hence the quest for alternative network connections.
In order to have k < N - 1 connections per node (N node cluster) it may take several hops to communicate data between nodes that are not directly connected.
Objects of the Invention:
It is an object of this invention to provide a clustered computer network.
Another object of this invention is to provide a cluster of computers which has increased computational power.
Still one more object of the invention is to provide a non conflict data access to a plurality of nodes in a network.
2

Further another object is to reduce the number of connections required for the network.
Detailed Description of the Invention:
In accordance with this invention there is envisaged a network of diameter 2, meaning any two nodes are at most 2 edges away from each other which uses an optimum number of connections. In this method a Singer difference set is used differently resulting in networks with a smaller number of connections per node for clusters of same size described in the earlier approaches. Further, a method of allowing multiple computers to be placed at each node is envisaged with the computers sharing the network in a non-conflicting manner. These methods together result in creation of powerful clusters at a reduced cost.
Two Hop Networks:
Two Hop Cycle Networks: If we have a cycle of N nodes, then the maximum distance between two nodes is N/2. Consider a cluster of N=13 nodes. Add another cycle with a stride of 4. Since N=13 is relatively prime to 4 a full cycle of N nodes is obtained. In accordance with this invention 4 was selected because it makes possible to reach node 1 and 2 in at most 2-hops from 0. If a connection is added to 4; then 4 and 3 and 5 can be reached in at most two hops. The table below lists the nodes that we can reach from 0 in 1 and 2 hops. The connectivity pattern for all nodes is identical, therefore the various properties that are observed for node 0 are true for all other nodes.

CYCLE 0 0 1 2 3 4 5 6 7 8 9 10 11 12
CYCLE1 0 4 8 12 3 7 11 2 6 10 1 5 9
Table 1: Cluster connections with 2 cycles

In the above table 4 1-hop neighbors corresponding to the 4 edges of the 2 cycles is indicated. There are 2 2 hop neighbors from stride 1 cycle (CycieO) and 4 2 hop neighbors from stride 4 cycles. Table 2 above lists the 1 and 2 hop neighbors. The nodes 5 and 8 have multiple paths whereas node 6 and 7 are not reachable in two hops. To perform this another cycle of stride 6 is added.

This method describes a way of arriving at 2-HOP networks, using cycles.
Singer Difference Set and Standard PG cycles:
Singer described in a paper that there exists a 1-1 isomorphism between difference Sets and Projective Geometry points. In 1992 Narendra Karmarkar described in a paper that projective Geometry points and lines (also planes/hyper planes etc) can be used to create a connectivity pattern.

Table 4: Difference set D of size 3,5,7,11 for Fields 13,31,57 and 133.
4
Definition 1: A Difference Set D for a Field F is a set of numbers disuch that for any number n in the field F there exists X distinct pairs di and dj such that n = dj - dj. For the discussion X=\. Thus the difference of any pair of numbers in D will gives a number in F. Also all numbers can be expressed as a difference of a unique pair of numbers in D.

The method to create a cluster based on Singer difference set is as follows. Let N be the size of F and prime+1 is size of D. Then create a cycle of stride dj where dj € D and di≠£ 0 over nodes in the field F. Thus for 13 nodes we will have 3 cycles of stride 1, 3, and 9. For 31 nodes we will create 5 cycles of stride 1, 3, 8, 12 and 18. The table below shows Singer Cycles over 13 nodes.

SINGER CYCLE 0 0 1 2 3 4 5 6 7 8 9 10 11 12
SINGER CYCLE 1 0 3 6 9 12 2 5 8 11 1 4 7 10
SINGER
CYCLE 2 0 9 5 1 10 6 2 11 7 3 12 8 4
Table 5: Cluster of 13 nodes connected using 3 Singer Cycles
In one scheme each node can represent a computer with a switch. The 13 nodes are connected with 3 cycles as shown in table 5. This results in each node having 6 connections (2 per cycle). Another scheme is provided which separates the connections from node i to di from the connections from node di to i into 2 sets. Each node is connected to 2 switches, one for each set. This allows to build a cluster with smaller switches or build larger clusters with existing switches, the fanout degree at each node is still 2*p (p=prime=number of cycles) for clusters of size p +p+l.
A different scheme is proposed by Narendra Karmarkar in which there are N processors and N memories. Processor i connects to memory i+dj where dj is an element in the difference set. This means processor i connects to memories in column i + 1. Referring to Table 5 there is processor 0 which connects to memories 1, 3, 9. In addition processor 12, 10, 4 connect to memory 0. If there is an architecture where processors and memories are different units then we can build a cluster such that we need p connections from the memory or processor units. However in practice processor and memories are present in the same unit. Thus if processor 0
5

and memory 0 represent the same node, then the node 0 is connected to 1, 3, 9 and 12, 10, 4. Thus this scheme will also results in 2 * 3 = 6 connections per node.
In accordance with this invention it is envisaged to implement a 183 (prime=13) node 2D PG cluster. This requires 13*2 = 26 connections per node. The switch according to prior art supports 24 connections. Thus if only 1 blade per node was placed there could be only 23 connections. This implies that either build a smaller cluster or discover a method which will require smaller number of connections and still give us a 2-Hop cluster. This requirement and the research that followed resulted in a discovery which we call the reflected PG scheme [4]. In this method each node is connected at most to p+1 (p=prime) nodes and we get 2 hop connectivity cluster network of p2+p+l nodes. A further modification allows us to construct (p+l)/2 cycles which give 2 hop connectivity. With these two modifications it is possible to have p+1 (or its multiples) computers at a node such that each of the computers access one of the p+1 edges at any time. A pattern is proposed which allows non-conflicting access when we have p+1 computers at each node.
A method is proposed which allows to connect p2+p+l nodes with at most p+1 connections
where p is a prime number such that the maximum (distance) number of edges between any
two nodes is 2.
A method is proposed which allows to connect p2+p+l nodes with p+1 edges where p is a
prime number such that we have (p+l)/2 cycles and the maximum number of edges between
any two nodes is 2.
A method known as perfect access pattern is described which allows non-conflict data access
between cluster computers.
A method is proposed which allows to populate (p+1) computers at a node connected by the
above methods,
A method is proposed where each of the p+1 computers at a node can simultaneously
communicate using the p+1 edges with p+1 computers at p+1 other nodes.
CRL reflected (permuted) 2 color Cycle Scheme:
6

The present invention uses the concept of Singer's difference set quiet differently to arrive at a
cluster of qt=p2+p+l node with at most p+1 connections.
As an example considering the difference set for p=3 and qt=13. The difference set is {0, 1,
3,9}.
Instead of connecting node i to i-{0,l,3,9} for i=0,l,2,...qt-l, first connect node i to qt -
1 -i + dj where di are elements of the corresponding difference set.
For p=3 and qt-13 the connections are' described by the equation node i is connected to node j
= 12-i + {0, 1,3,9} fori = 0,.. 12.
This is called the reflected PG scheme.
Table 6 below gives the connectivity pattern based on this scheme.

DIFFERENCE
SET ELEMENT
NODE# CONNECTIONS 12-1 +{0, 1,3,9}

0 1 3 9
0 12 0 2 8
1 11 12 I 7
2 10 11 0 6
3 9 10 12 5
4 8 9 11 4
5 7 8 10 3
6 6 7 9 2
7 5 6 8 1
8 4 5 7 0
9 3 4 6 12
10 2 3 5 n
11 1 2 4 10
12 0 1 3 9
Table 6: Reflected PG connectivity for prime=3, 13 nodes.
7

In the above scheme there is a symmetry in connectivity. Considering column 1 it is observed that node 0 is connected to 12 and node 12 is connected to 0. Lemma: In this scheme if node i is connected to j then j is connected to i. Proof; Node i is connected to j = 12-i+{0,1,3,9}. j is connected to k=12-j+{0,l ,3,9}. Substituting the first equation in the second equation we get k=12-(12-i+{0,l,3,9})+{0,l,3,9}
= i-{0,1,3,9}+ {0,1,3,9}
= i. Here the total number of connections per node is at most prime+1 = 4 which is the size of the difference set. Thus a reduced the number of connections from 2 * prime to prime + 1 is obtained. Thus for 13 nodes only 24 connections are required. Next step is to check whether the above connection pattern has 2-hop connectivity. Examining the node 0, the first row shows that node 0 is connected by 1 hop connectivity to node {2, 8, 12}. Also node 0 appears in rows 2 (column 3) , 8 (column 4), and 12 (columnl). This means it is connected to the remaining 3 nodes in rows 2, 8 and 12. The connections for node 0 are elaborated below

1-HOP 0->{2,8, 12}
2-HOP 0->2->{10, 11,6}
2-HOP 0->8->{4,5,7}
2-HOP ' 0->12->{l,3,9}
Table 7: 1 and 2-HOP connectivity pattern for node 0. It can be verified that all nodes are either 1-HOP or 2-HOP connected. The 0th column lists all the nodes and remaining 4 columns lists the connections that are 1-HOP away. Thus every node has either 3 or 4 1-HOP connections. The remaining connections are 2-HOP and are between pairs of nodes in columns 1 to 4. The connections for difference sets constructed for p=5, 7, 11, 13 are given in the table 7 below.
8

p (prime) qt (Number of Nodes in the cluster) Connectivity formula
3 13 .12-i+{0,l,3,9}
5 31 30-i+{0, 1,3,8, 12,18}
7 57 56-i+{0,l,3,13,32,36,43,52}
11 133 132-i+{0,l,3,I7,21,58,65,73,100!105,l 11,124}
13 183 182-i+{l, 13, 20, 21, 23, 44, 61, 72, 77, 86, 90, 116, 122, 169}
Table 7: Reflected PG connectivity for p=3,5,7,11 and 13.
2 Column reflected PG cycle connections:
The reflected PG connectivity retains 2-HOP connectivity and at the same time requires atmost only p+1 connections per node for p +p+l node cluster. However it does not have clearly visible cyclic connectivity pattern and it does not have uniform connectivity as the nodes have either p or p+1 connections. This invention proposes a modification which will result in
* All nodes having p+1 connections.
• Having (p+l)/2 cycles distinct cycles
Consider the reflected PG connectivity described in Table 6. Each column represents 6 edges between pairs of nodes (12 nodes) and 1 self loop (1 node). For a cycle of 13 nodes we will need 13 edges. Consider 2 columns (1 and 2), there are 12 edges and 2 self loops. Adding a connection to the 2 nodes that have a self loop results in 13 edges and 13 nodes. If the 2 columns are considered representing 2 colors then 6 edges of color 1 and 6 edges of color 2 and one edge of mixed color. The procedure to construct the cycle is as follows. Start from Node 0 and chose an edge from column 1 (color 1). Selecting the next edge from the column 2 (color 2). This takes to Node 1. Proceed like this alternately choosing edges from column 1 and 2 till 13 edges are obtained and all 13 nodes are covered. Similarly we can create another
9

cycle from columns 3 and 4. The table below gives 2 2-color cycles for the 13 node reflected PG cluster.

NODE# COLOR 0 D1-0 COLOR 1 (D1=l) COLOR 2 (D1=3) COLOR 3
(D1=9)
0 12 6* 2 8
1 11 12 4+ 7
2 10 11 0 6
3 9 10 12 5
4 8 9 11 1+
5 7 8 10 3
6 0* 7 9 2
7 5 6 8 1
8 4 5 7 0
9 3 4 6 12
10 2 3 5 11
11 1 2 4 10
12 0 1 3 9
Table 8a: Connections represented in 4 columns (colors). * and represent connections
replacing self-loops.

CYCLE 0 0 12 1 11 2 10 3 9 4 8 5 7 6
(COLOR 0&1)
CYCLE 1 0 2 6 9 12 3 5 10 11 4 1 7 8
(COLOR 2 & 3)
Table 8b: 2 2-color cycles connecting 13 nodes. Cycle 0 uses colors 0 and 1, Cycle 1 uses colors 2 and 3. These circles are drawn in Fig 2
10

After renumbering circle 0 as 0, 1, 2,.. we get the circles shown in Table 8c:

CYCLE 0 0 1 2 3 4 5 6 7 8 9 10 11 12
(COLOR 0&1)
CYCLE 1 0 4 12 7 1 6 10 5 3 8 2 11 9
(COLOR 2 & 3)
Table 8c: The two circles after renumbering. These circles are drawn in Fig 3
The number of columns (colors) is prime+1 and the number of pairs of columns and cycles is (prime+l)/2. Pairs are selected to get a complete cycle of length N=(prime2+prime+l). Let di and dj be the two elements of the difference set. The connectivity pattern of the column dj is the same as di shifted by dj-di = dstride. If dstride is not relative prime with N that is if lcf(N, dstride) = f ≠ 1. Then a cycle of N/f nodes is obtained. For example for prime=7 and N=57 the difference set from table 4 is
0,1,3,13.32,36,43,52. Table 9a and 9b shows the difference set elements with combinations that will not give a full cycle being marked by X.

DIFFSET ELEMENTS 0 1 3 13 32 36 43 52
0 0 1 3(3) 13 32 36(3) 43 52
1 0 2 12(3) 31 35 42(3) 51(3)
3 0 10 29 33(3) 40 49
13 0 19(19) 23 30(3) 39(3)
32 0 4 11 20
36 0 7 16
43 0 9(3)
52 0
Table 9a: Difference stride when combining 2 columns, LCF is in parenthesis when non-zero.
11

DIFFSET
ELEMENTS 0 1 3 13 32 36 43 52
0 X X X
1 X X X
3 X
13 X X X
32
36
43 X
52
Table 9b: Column pairs that will not give a full cycle for a 57 node cluster is indicated by X The procedure to create (p+l)/2 cycles is given below. Procedure to create (p+l)/2 cycles:
1. Let {do,d1],...dp} be the difference set on a field of size qt = p2+p+l.
2. Create Reflected PG connections by constructing a matrix of qt rows and p+1 columns.
3. Node i is connected to qt-1 -i+dj for i =0, 1, 2, ... qt-1 and j =0, 1, ..p.
4. Mark column pairs that cannot be combined to give full cycles (perimeter qt). A column pair k and 1 cannot be combined for k =0, l....,p and l=k+l,...,p
If lcf(d,-dk, qt) >1 or lcf(dk-d|+qt, qt)>l.
5. Create (p+l)/2 column pairs such that each pair gives a full cycle. These pairs are selected by a straightforward depth first search through all column pair combinations.
6. Construct a cycle for each of the p+1 column pairs using the following procedure. Connect node nk to nk+i for k=0, 1. 2...qt-1, by using edges from column I and 2 of the column pair alternatively. Table 8b shows cycle 0 created by using column 0 and 1.
12

Optimum Communication:
If two computers access data from the same node then the bandwidth is reduced due to memory contention. Therefore one of the steps in reducing communication costs is to decompose data communication sequences into non-conflicting sequence. A non-conflicting communication sequence is a sequence of non-conflicting data access patterns, also known as perfect access pattern, A perfect access pattern for n nodes is any permutation pattern of n nodes.
2 Color Cycle Perfect Access Sequences:
In the 2 color reflected PG cycle scheme the number of cycles is nc = (p+l)/2 (p being prime) and the number of nodes is qt=p2+p+l.
A clockwise rotation along a circle and anti-clockwise rotation along a circle is a 1-HOP perfect access pattern. For nc cycles we have 2*nc 1-HOP perfect access patterns. Since only 2*nc nodes are reached in 1 HOP we need to construct 2-HOP patterns to enable data transfer between node ni and all other nodes for i=0,l,2...qt-l. The number of 2-HOP perfect access patterns is 2nc *2nc -2nc = (2nc)2-2nc.
2-HOP patterns are obtained by picking any 2 cycles (same cycle is ok) and applying either clockwise or anti-clockwise rotation (2nc*2nc). If the same cycle is picked twice the identity operation
• clockwise and anti-clockwise operation (nc), or
• anti-clockwise and clockwise operation (nc).
Subtracting these (2*nc) we get the total number of 2-HOP perfect access patterns as (2ric) -2nc. The total number of patterns (1-HOP and 2-HOP) is (2nc)2. The table below lists all 1-HOP and 2-HOP perfect access patterns for 13 node cluster (nc= 2).
13

SEQ# o, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
seq 0+, 0-, I+, 1-, 0+0
+, 0-0-, 0+1 0+1- 0- 0-1-, 1+0 1+0- 1-
o+, 1-0-, 1+1
+, I-
1-,
0: 1, 12, 4, 9, 2, 11, 6, 7, 7, 4, 5, 10, 8, 12, 11,
1: 2, o, 6, 7, 3, 12, 11, 8, 4, 9, 7, 5, 8, 6, 10, 12,:'
2: 3, 1, 11, 8, 4, 0, 8, 5, 6, 7, 12, 10, 9, 7, 9, 3,
3: 4, 2, 8, 5, 5, 1, 12, o, 11, 8, 9, 7, 6, 4, 2, 10,
4: 5, 3, 12, o, 6, 2, 3, 10, 8, 5, 0, 11, 1, 12, 7, 9,
5: 6, 4, 3, 10, 7, 3, 10, 1, 12. 0, 4, 2, 11, 9, 8, 6,
6: 7, 5, 10, 1, 8, 4, 1, 12, 3, 10, 11, 9, 2, o, 5, 7, .
7: 8, 6, 1, 12, 9, 5, 2, 3, 10, 1, 2, o, o, 11, 6, 4,
8: 9, 7, 2, 10, 6, o, 11, 1, 12, 3, 1, 4, 2, 11, 5,
9: 10, 8, 0, 11, 11, 7, 5, 6, 2, 3, 1, 12, 12, 10, 4, 2,
10: 11, 9, 5, 6, 12, 8, 9, 2, o, 11, 6, 4, 7, 5, 3, 1, '
11: 12, 10, 9, 2, o, 9, 7, 4, 5, 6, 10, 8, 3, 1, o, 8, j
12: o, 11, 7, 4, 1, 10, 4, 9, 9, 2, 8, 6, 5, 3, 1, o,
Table 10: List of Reflected 2 Color 2D PG sequences and the corresponding permutations
Parallel Perfect access patterns in reflected PG cluster:
It takes about 10X time to communicate between non-loca! computer memories. In the previous section the concept of perfect access patterns was introduced. These patterns allow all the computers to access data simultaneously from non-local memories without conflict. This ensures the fastest access of data. Every node has p+i connections. With the perfect access patterns at any given time only 1 out of the p+1 connections is used. This invention propose to populate each node with p+1 computers and connect it in one of the following ways
• Each node is connected to a p+1 by p+1 bipartite switch. This enables each of the p+1
computers to simultaneously communicate with one of the p+1 computers through the
bipartite switch.
14

• In addition to the above bipartite switch each computer at a node is connected to the
remaining p computers at the node in a variety of ways
o All connect,
o Tree network
o Ring network. These connections will allow the super node (of p+1 computers at a node) to communicate data between its computers.
• Each node with p+1 computers is connected to a 2*p+2 all connect switch. This
enables p+1 computers to
o communicate amongst themselves as well as to
o communicate with 2nc- p+1 external computers (using 1-HOP connections).
o communicate with the remaining external computers using 2-HOP connections
Table 10 below groups parallel sequences together. With this complete data transfer from all nodes to all nodes in 2nc cycles is achieved.

0 1 2 3
0+ 1 0+0+ 2 0+1+ 6 0+1- 7
0- 12 0-0- 11 0-1- 4 0-] + 7
1+ 4 1+1 + 12 1+0+ 5 1+0- 3
1- 9 1-1- 11 1-0- 8 1-0+ 10
Table 10: Transferring data from node 0 in 4 (2*nc) time cycles using edges of nc cycles. Since the number of cycles nc is (p+l)/2 and the number of nodes is p2+p+l, then the maximum number of time cycles to achieve complete transfer of data from all nodes to all nodes as 2*nc = p+1. This indicates complete utilization of the network connectivity and scalability of computation as the number of nodes is increased.
Application to Matrix Algebra Problem:
15

Dense Matrix X Vector Multiply: In this problem the matrix is partitioned such that Ay is stored on node i and Vj is stored on node i. To complete the solution each node i needs to get the vector Vj from all other nodes. Thus for a 13 node 2D reflected PG cluster we need to transfer data from all 12 nodes to ail other 12 nodes. Table 10 lists the sequences and permutations that it supports. The reader can verify that all 16 sequences are required to transfer data from 13 nodes to all the 12 remaining nodes. This is because the minimum number of columns that we need to select to cover the complete pattern is 16. If it is implemented in parallel it will require 4 time sequences.
Sparse Matrix X Vector Multiply:
This problem can be solved similar to dense matrix problem. However since the matrices are sparse, it may be able to solve the problem in lesser number of sequences. For instance if Aij ≠0 when i=j+l or j=i+l, then we can use sequence 0 and 1 to transfer the data. The reader can create sample sparse matrix patterns and try to come up with a sequence that will cover all the necessary data transfer patterns. TO DO: Description of Sequencer in another document. TO DO: Multi-Blade in another document
While considerable emphasis has been placed herein on the specific steps and elements of the preferred embodiment it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.