1 //******************************************************************************
2 //
3 // File: CommPattern.java
4 // Package: edu.rit.pj.cluster
5 // Unit: Class edu.rit.pj.cluster.CommPattern
6 //
7 // This Java source file is copyright (C) 2008 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.pj.cluster;
41
42 import java.util.ArrayList;
43
44 /**
45 * Class CommPattern provides static methods for calculating communication
46 * patterns for collective communication operations.
47 *
48 * @author Alan Kaminsky
49 * @version 15-Mar-2008
50 */
51 public class CommPattern {
52
53 // Prevent construction.
54 private CommPattern() {
55 }
56
57 // Exported operations.
58 /**
59 * Calculate the communication pattern for a parallel broadcast tree. This
60 * is also used in reverse for a parallel reduction tree.
61 *
62 * @param size Size of the communicator. Must be >= 1.
63 * @param rank Rank of this process in the communicator. Must be in the
64 * range 0 .. <code>size</code>-1.
65 * @param root Rank of the root process for the broadcast. Must be in the
66 * range 0 .. <code>size</code>-1.
67 * @return Array of process ranks for the parallel broadcast pattern. The
68 * element at index 0 is the parent process rank, or -1 if there is no
69 * parent process. The elements at indexes 1 and above, if any, are the
70 * child process ranks.
71 * @exception IllegalArgumentException (unchecked exception) Thrown if any
72 * argument is illegal.
73 */
74 public static int[] broadcastPattern(int size,
75 int rank,
76 int root) {
77 // Verify preconditions.
78 if (size < 1) {
79 throw new IllegalArgumentException("broadcastPattern(): size must be >= 1");
80 }
81 if (0 > rank || rank >= size) {
82 throw new IllegalArgumentException("broadcastPattern(): rank must be in the range 0 .. "
83 + (size - 1));
84 }
85 if (0 > root || root >= size) {
86 throw new IllegalArgumentException("broadcastPattern(): root must be in the range 0 .. "
87 + (size - 1));
88 }
89
90 // Imagine for the moment that the processes are numbered 1 through K,
91 // where K = size. The broadcast communication pattern takes place in a
92 // number of rounds. The rounds are numbered 1, 2, 4, 8, and so on. In
93 // round 1, process 1 sends to process 2. In round 2, processes 1 and 2
94 // send to processes 3 and 4 in parallel. In round 4, processes 1, 2, 3,
95 // and 4 send to processes 5, 6, 7, and 8 in parallel:
96 //
97 // Process
98 // 1 2 3 4 5 6 7 8
99 // | | | | | | | |
100 // | | | | | | | |
101 // |--->| | | | | | | Round 1
102 // | | | | | | | |
103 // | | | | | | | |
104 // |-------->| | | | | | Round 2
105 // | |-------->| | | | |
106 // | | | | | | | |
107 // | | | | | | | |
108 // |------------------>| | | | Round 4
109 // | |------------------>| | |
110 // | | |------------------>| |
111 // | | | |------------------>|
112 // | | | | | | | |
113 // | | | | | | | |
114 //
115 // In general, in round i, processes 1 through i send to processes 1+i
116 // through i+i in parallel. This continues until there are no more
117 // processes to send to.
118 //
119 // After calculating the above pattern, the process numbers are shifted
120 // such that process 1 becomes process root, process 2 becomes process
121 // root+1, and so on. In general, process i becomes process (i+root-1)
122 // (mod size).
123 // This process's rank relative to the root, in the range 1 .. size.
124 int thisrank
125 = rank >= root
126 ? rank - root + 1
127 : rank + size - root + 1;
128
129 // Parent process.
130 int parent = -1;
131
132 // List of child processes.
133 ArrayList<Integer> childlist = new ArrayList<Integer>();
134
135 // Do all rounds.
136 int round = 1;
137 while (round < size) {
138 // Do all messages within this round.
139 for (int src = 1; src <= round; ++src) {
140 int dst = src + round;
141
142 // If this process is the destination, record source as parent.
143 if (thisrank == dst) {
144 parent = src;
145 } // If this process is the source, record destination as child.
146 else if (thisrank == src && dst <= size) {
147 childlist.add(dst);
148 }
149 }
150
151 // Next round.
152 round <<= 1;
153 }
154
155 // Make an array to hold parent and child processes.
156 int n = childlist.size();
157 int[] result = new int[n + 1];
158
159 // Record parent, offsetting rank.
160 result[0] = parent == -1 ? -1 : (parent + root - 1) % size;
161
162 // Record children, offsetting ranks.
163 for (int i = 0; i < n; ++i) {
164 result[i + 1] = (childlist.get(i) + root - 1) % size;
165 }
166
167 // All done!
168 return result;
169 }
170
171 // Unit test main program.
172 // /**
173 // * Unit test main program.
174 // * <P>
175 // * Usage: java edu.rit.pj.cluster.CommPattern <I>size</I> <I>rank</I>
176 // * <I>root</I>
177 // */
178 // public static void main
179 // (String[] args)
180 // {
181 // if (args.length != 3) usage();
182 // int size = Integer.parseInt (args[0]);
183 // int rank = Integer.parseInt (args[1]);
184 // int root = Integer.parseInt (args[2]);
185 // int[] pattern = CommPattern.broadcastPattern (size, rank, root);
186 // System.out.print ("broadcastPattern (size=");
187 // System.out.print (size);
188 // System.out.print (", rank=");
189 // System.out.print (rank);
190 // System.out.print (", root=");
191 // System.out.print (root);
192 // System.out.print (") returns {");
193 // System.out.print (pattern[0]);
194 // for (int i = 1; i < pattern.length; ++ i)
195 // {
196 // System.out.print (", ");
197 // System.out.print (pattern[i]);
198 // }
199 // System.out.println ("}");
200 // }
201 //
202 // /**
203 // * Print a usage message and exit.
204 // */
205 // private static void usage()
206 // {
207 // System.err.println ("Usage: java edu.rit.pj.cluster.CommPattern <size> <rank> <root>");
208 // System.exit (1);
209 // }
210 }