View Javadoc
1   //******************************************************************************
2   //
3   // File:    LongSchedule.java
4   // Package: edu.rit.pj
5   // Unit:    Class edu.rit.pj.LongSchedule
6   //
7   // This Java source file is copyright (C) 2009 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;
41  
42  import java.lang.reflect.Constructor;
43  import java.lang.reflect.InvocationTargetException;
44  import java.util.concurrent.atomic.AtomicLong;
45  
46  import edu.rit.util.LongRange;
47  
48  /**
49   * Class LongSchedule provides an object that determines how to schedule the
50   * iterations of a {@linkplain ParallelForLoop} among the threads in a
51   * {@linkplain ParallelTeam}. The loop index is type <code>long</code>.
52   * <p>
53   * To create a schedule object, call one of the following static methods:
54   * <UL>
55   * <LI><code>LongSchedule.fixed()</code>
56   * <LI><code>LongSchedule.dynamic()</code>
57   * <LI><code>LongSchedule.guided()</code>
58   * <LI><code>LongSchedule.runtime()</code>
59   * <LI><code>LongSchedule.parse()</code>
60   * </UL>
61   * <p>
62   * The Parallel Java Library includes three built-in schedule implementations:
63   * fixed, dynamic, and guided. You can create instances of these by calling the
64   * <code>fixed()</code>, <code>dynamic()</code>, and <code>guided()</code> methods. You can
65   * also create your own schedule implementation by writing a subclass of class
66   * LongSchedule. The subclass must have a no-argument constructor and a
67   * constructor whose argument is an array of Strings; see the <code>parse()</code>
68   * method for further information about how these constructors are used.
69   *
70   * @author Alan Kaminsky
71   * @version 18-Nov-2009
72   */
73  public abstract class LongSchedule
74          extends Schedule {
75  
76      // Hidden data members.
77      // Loop index for ordered() construct.
78      AtomicLong myOrderedIndex = new AtomicLong();
79  
80  // Hidden constructors.
81  
82      /**
83       * Construct a new schedule object.
84       */
85      protected LongSchedule() {
86          super();
87      }
88  
89  // Exported operations.
90  
91      /**
92       * Returns a fixed schedule object. The loop iterations are apportioned
93       * among the parallel team threads once at the beginning of the parallel for
94       * loop, with each thread getting a fixed number of iterations, the same
95       * number of iterations for each thread (plus or minus one).
96       *
97       * @return Fixed schedule object.
98       */
99      public static LongSchedule fixed() {
100         return new FixedLongSchedule();
101     }
102 
103     /**
104      * Returns a dynamic schedule object with a chunk size of 1. The loop
105      * iterations are apportioned into chunks of size 1 (one iteration per
106      * chunk). Each parallel team thread repeatedly performs the next available
107      * iteration until there are no more iterations.
108      *
109      * @return Dynamic schedule object.
110      */
111     public static LongSchedule dynamic() {
112         return new DynamicLongSchedule(1);
113     }
114 
115     /**
116      * Returns a dynamic schedule object with the given chunk size. The loop
117      * iterations are apportioned into chunks of size <code>theChunkSize</code>
118      * (<code>theChunkSize</code> iterations per chunk). Each parallel team thread
119      * repeatedly performs the next available chunk of iterations until there
120      * are no more chunks. The final chunk may be smaller than
121      * <code>theChunkSize</code>.
122      *
123      * @param theChunkSize Chunk size, &gt;= 1.
124      * @return Dynamic schedule object.
125      * @throws java.lang.IllegalArgumentException (unchecked exception) Thrown if
126      *                                  <code>theChunkSize</code> &lt; 1.
127      */
128     public static LongSchedule dynamic(long theChunkSize) {
129         return new DynamicLongSchedule(theChunkSize);
130     }
131 
132     /**
133      * Returns a self-guided schedule object with a minimum chunk size of 1. The
134      * loop iterations are apportioned into chunks of exponentially diminishing
135      * sizes. Each successive chunk's size is half the remaining number of
136      * iterations divided by the number of threads in the parallel team.
137      * However, each chunk's size is at least 1 (a minimum of one iteration per
138      * chunk). Each parallel team thread repeatedly performs the next available
139      * chunk of iterations until there are no more chunks.
140      *
141      * @return Self-guided schedule object.
142      */
143     public static LongSchedule guided() {
144         return new GuidedLongSchedule(1);
145     }
146 
147     /**
148      * Returns a self-guided schedule object with the given minimum chunk size.
149      * The loop iterations are apportioned into chunks of exponentially
150      * diminishing sizes. Each successive chunk's size is half the remaining
151      * number of iterations divided by the number of threads in the parallel
152      * team. However, each chunk is at least <code>theChunkSize</code> (a minimum of
153      * <code>theChunkSize</code> iterations per chunk). Each parallel team thread
154      * repeatedly performs the next available chunk of iterations until there
155      * are no more chunks. The final chunk may be smaller than
156      * <code>theChunkSize</code>.
157      *
158      * @param theChunkSize Minimum chunk size, &gt;= 1.
159      * @return Self-guided schedule object.
160      * @throws java.lang.IllegalArgumentException (unchecked exception) Thrown if
161      *                                  <code>theChunkSize</code> &lt; 1.
162      */
163     public static LongSchedule guided(long theChunkSize) {
164         return new GuidedLongSchedule(theChunkSize);
165     }
166 
167     /**
168      * Returns a schedule object of a type determined at run time. If the
169      * <code>"pj.schedule"</code> Java property is specified, the property's value
170      * is parsed by the <code>parse()</code> method, and that gives the type of
171      * schedule. If the <code>"pj.schedule"</code> Java property is not specified,
172      * the default is a fixed schedule. You can specify the schedule on the Java
173      * command line like this (note that quotation marks may be needed):
174      * <PRE>
175      * java -Dpj.schedule="dynamic(5)" . . .
176      * </PRE>
177      *
178      * @return Schedule object.
179      * @throws java.lang.IllegalArgumentException (unchecked exception) Thrown if the
180      *                                  <code>"pj.schedule"</code> property value cannot be parsed.
181      */
182     public static LongSchedule runtime() {
183         return runtime(LongSchedule.fixed());
184     }
185 
186     /**
187      * Returns a schedule object of a type determined at run time, using the
188      * given default schedule. If the <code>"pj.schedule"</code> Java property is
189      * specified, the property's value is parsed by the <code>parse()</code> method,
190      * and that gives the type of schedule. If the <code>"pj.schedule"</code> Java
191      * property is not specified, the given <code>defaultSchedule</code> is
192      * returned. You can specify the schedule on the Java command line like this
193      * (note that quotation marks may be needed):
194      * <PRE>
195      * java -Dpj.schedule="dynamic(5)" . . .
196      * </PRE>
197      *
198      * @param defaultSchedule Schedule to use if the <code>"pj.schedule"</code>
199      *                        Java property is not specified.
200      * @return Schedule object.
201      * @throws java.lang.IllegalArgumentException (unchecked exception) Thrown if the
202      *                                  <code>"pj.schedule"</code> property value cannot be parsed.
203      */
204     public static LongSchedule runtime(LongSchedule defaultSchedule) {
205         String s = PJProperties.getPjSchedule();
206         return s == null ? defaultSchedule : parse(s);
207     }
208 
209     /**
210      * Returns a schedule object of a type determined by parsing the given
211      * string. The string must be one of the following:
212      * <UL>
213      * <LI><code>"fixed"</code> -- Fixed schedule.
214      * <LI><code>"dynamic"</code> -- Dynamic schedule with a chunk size of 1.
215      * <LI><code>"dynamic(<I>n</I>)"</code> -- Dynamic schedule with a chunk size of
216      * <code><I>n</I></code>, an integer &gt;= 1.
217      * <LI><code>"guided"</code> -- Self-guided schedule with a minimum chunk size
218      * of 1.
219      * <LI><code>"guided(<I>n</I>)"</code> -- Self-guided schedule with a minimum
220      * chunk size of <code><I>n</I></code>, an integer &gt;= 1.
221      * <LI><code>"<I>classname</I>"</code> -- Schedule that is an instance of the
222      * given class. <I>classname</I> is the fully-qualified class name of the
223      * schedule class, which must be a subclass of class LongSchedule. The
224      * instance is constructed using the subclass's no-argument constructor.
225      * <LI><code>"<I>classname</I>(<I>arg</I>,<I>arg</I>,...)"</code> -- Schedule
226      * that is an instance of the given class. <I>classname</I> is the
227      * fully-qualified class name of the schedule class, which must be a
228      * subclass of class LongSchedule. The arguments between the parentheses are
229      * split into separate strings separated by commas. There cannot be
230      * parentheses or commas within the arguments themselves. The instance is
231      * constructed using the subclass's constructor whose argument is an array
232      * of Strings, namely the individual arguments between the parentheses.
233      * </UL>
234      *
235      * @param s String to parse.
236      * @return Schedule object.
237      * @throws java.lang.NullPointerException     (unchecked exception) Thrown if
238      *                                  <code>s</code> is null.
239      * @throws java.lang.IllegalArgumentException (unchecked exception) Thrown if
240      *                                  <code>s</code> is not one of the above.
241      */
242     public static LongSchedule parse(String s) {
243         try {
244             int p1 = s.indexOf('(');
245 
246             if (p1 == -1) {
247                 // No arguments. s is the subclass name. Get subclass.
248                 Class<?> subclass
249                         = Class.forName(getSubclassName(s),
250                         true,
251                         Thread.currentThread().getContextClassLoader());
252 
253                 // Instantiate subclass using no-argument constructor.
254                 return (LongSchedule) subclass.getConstructor().newInstance();
255             } else {
256                 // Arguments. Verify syntax.
257                 int p2 = s.indexOf(')');
258                 if (p2 != s.length() - 1) {
259                     throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s
260                             + "\" illegal");
261                 }
262 
263                 // Split arguments around commas.
264                 String[] args = s.substring(p1 + 1, p2).split(",");
265 
266                 // s up to '(' is the subclass name. Get subclass.
267                 Class<?> subclass
268                         = Class.forName(getSubclassName(s.substring(0, p1)),
269                         true,
270                         Thread.currentThread().getContextClassLoader());
271 
272                 // Get constructor with one String[] argument.
273                 Constructor<?> constructor
274                         = subclass.getConstructor(String[].class);
275 
276                 // Instantiate subclass using String[]-argument constructor.
277                 return (LongSchedule) constructor.newInstance((Object) args);
278             }
279         } catch (ClassCastException exc) {
280             throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s + "\" illegal",
281                     exc);
282         } catch (ClassNotFoundException exc) {
283             throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s + "\" illegal",
284                     exc);
285         } catch (IllegalAccessException exc) {
286             throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s + "\" illegal",
287                     exc);
288         } catch (InstantiationException exc) {
289             throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s + "\" illegal",
290                     exc);
291         } catch (InvocationTargetException exc) {
292             throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s + "\" illegal",
293                     exc);
294         } catch (NoSuchMethodException exc) {
295             throw new IllegalArgumentException("LongSchedule.parse(): Schedule \"" + s + "\" illegal",
296                     exc);
297         }
298     }
299 
300     /**
301      * Determine if this schedule is a fixed schedule. For a parallel team with
302      * <I>K</I> threads, a fixed schedule partitions the loop index range into
303      * exactly <I>K</I> chunks, one chunk for each thread, each chunk with
304      * predetermined upper and lower bounds.
305      *
306      * @return True if this is a fixed schedule, false otherwise.
307      */
308     public abstract boolean isFixedSchedule();
309 
310 // Hidden operations.
311 
312     /**
313      * Get the name of the subclass to instantiate. The names <code>"fixed"</code>,
314      * <code>"dynamic"</code>, and <code>"guided"</code> are recognized as special
315      * cases.
316      *
317      * @param name Subclass name, or special case string.
318      * @return Subclass name.
319      */
320     private static String getSubclassName(String name) {
321         if (name.equals("fixed")) {
322             return "edu.rit.pj.FixedLongSchedule";
323         } else if (name.equals("dynamic")) {
324             return "edu.rit.pj.DynamicLongSchedule";
325         } else if (name.equals("guided")) {
326             return "edu.rit.pj.GuidedLongSchedule";
327         } else {
328             return name;
329         }
330     }
331 
332     /**
333      * Start a parallel for loop using this schedule. This method performs
334      * common processing, then calls the subclass-specific <code>start()</code>
335      * method.
336      *
337      * @param K            Number of threads in the parallel team.
338      * @param theLoopRange Range of iterations for the entire parallel for loop.
339      *                     The stride may be 1 or greater.
340      */
341     void commonStart(int K,
342                      LongRange theLoopRange) {
343         myBreak = false;
344         myOrderedIndex.set(theLoopRange.lb());
345         start(K, theLoopRange);
346     }
347 
348     /**
349      * Start generating chunks of iterations for a parallel for loop using this
350      * schedule.
351      * <p>
352      * The <code>start()</code> method is only called by a single thread in the
353      * Parallel Java middleware.
354      *
355      * @param K            Number of threads in the parallel team.
356      * @param theLoopRange Range of iterations for the entire parallel for loop.
357      *                     The stride may be 1 or greater.
358      */
359     public abstract void start(int K,
360                                LongRange theLoopRange);
361 
362     /**
363      * Obtain the next chunk of iterations for the given thread index. This
364      * method performs common processing, then calls the subclass-specific
365      * <code>next()</code> method.
366      *
367      * @param theThreadIndex Thread index in the range 0 .. <I>K</I>-1.
368      * @return Chunk of iterations, or null if no more iterations.
369      */
370     LongRange commonNext(int theThreadIndex) {
371         if (myBreak) {
372             return null;
373         } else {
374             return next(theThreadIndex);
375         }
376     }
377 
378     /**
379      * Obtain the next chunk of iterations for the given thread index. If there
380      * are more iterations, a range object is returned whose lower bound, upper
381      * bound, and stride specify the chunk of iterations to perform. The
382      * returned range object's stride is the same as that given to the
383      * <code>start()</code> method. The returned range object's lower bound and
384      * upper bound are contained within the range given to the <code>start()</code>
385      * method. If there are no more iterations, null is returned.
386      * <p>
387      * The <code>next()</code> method is called by multiple parallel team threads in
388      * the Parallel Java middleware. The <code>next()</code> method must be multiple
389      * thread safe.
390      *
391      * @param theThreadIndex Thread index in the range 0 .. <I>K</I>-1.
392      * @return Chunk of iterations, or null if no more iterations.
393      */
394     public abstract LongRange next(int theThreadIndex);
395 
396 // Unit test main program.
397 //	/**
398 //	 * Unit test main program.
399 //	 */
400 //	public static void main
401 //		(String[] args)
402 //		{
403 //		if (args.length != 4)
404 //			{
405 //			System.err.println ("Usage: java [-Dpj.schedule=<SCHEDULE>] edu.rit.pj.LongSchedule <K> <lb> <ub> <stride>");
406 //			System.exit (1);
407 //			}
408 //		int K = Integer.parseInt (args[0]);
409 //		long lb = Long.parseLong (args[1]);
410 //		long ub = Long.parseLong (args[2]);
411 //		long stride = Long.parseLong (args[3]);
412 //		LongSchedule schedule = LongSchedule.runtime();
413 //		schedule.start (K, new LongRange (lb, ub, stride));
414 //		LongRange chunk;
415 //		for (int k = 0; k < K; ++ k)
416 //			{
417 //			while ((chunk = schedule.next (k)) != null)
418 //				{
419 //				System.out.println ("Thread " + k + " chunk = " + chunk);
420 //				}
421 //			}
422 //		}
423 }