+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
20.8 KiB646 linesraw
1/**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements.  See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership.  The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License.  You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18package org.apache.hadoop.examples;
19
20import java.io.BufferedOutputStream;
21import java.io.DataInput;
22import java.io.DataOutput;
23import java.io.IOException;
24import java.io.OutputStream;
25import java.io.OutputStreamWriter;
26import java.io.PrintStream;
27import java.io.PrintWriter;
28import java.util.ArrayList;
29import java.util.Iterator;
30import java.util.List;
31
32import org.apache.commons.logging.Log;
33import org.apache.commons.logging.LogFactory;
34import org.apache.hadoop.conf.Configuration;
35import org.apache.hadoop.conf.Configured;
36import org.apache.hadoop.fs.FileSystem;
37import org.apache.hadoop.fs.Path;
38import org.apache.hadoop.io.BytesWritable;
39import org.apache.hadoop.io.IntWritable;
40import org.apache.hadoop.io.LongWritable;
41import org.apache.hadoop.io.Writable;
42import org.apache.hadoop.mapreduce.InputFormat;
43import org.apache.hadoop.mapreduce.InputSplit;
44import org.apache.hadoop.mapreduce.Job;
45import org.apache.hadoop.mapreduce.JobContext;
46import org.apache.hadoop.mapreduce.MRJobConfig;
47import org.apache.hadoop.mapreduce.Mapper;
48import org.apache.hadoop.mapreduce.RecordReader;
49import org.apache.hadoop.mapreduce.Reducer;
50import org.apache.hadoop.mapreduce.TaskAttemptContext;
51import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
52import org.apache.hadoop.util.Tool;
53import org.apache.hadoop.util.ToolRunner;
54
55import com.google.common.base.Charsets;
56
57/**
58 * A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact 
59 * digits of Pi.
60 * This program is able to calculate digit positions
61 * lower than a certain limit, which is roughly 10^8.
62 * If the limit is exceeded,
63 * the corresponding results may be incorrect due to overflow errors.
64 * For computing higher bits of Pi, consider using distbbp. 
65 * 
66 * Reference:
67 *
68 * [1] David H. Bailey, Peter B. Borwein and Simon Plouffe.  On the Rapid
69 *     Computation of Various Polylogarithmic Constants.
70 *     Math. Comp., 66:903-913, 1996.
71 */
72public class BaileyBorweinPlouffe extends Configured implements Tool {
73  public static final String DESCRIPTION
74      = "A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact digits of Pi.";
75
76  private static final String NAME = "mapreduce." + 
77    BaileyBorweinPlouffe.class.getSimpleName();
78
79  //custom job properties
80  private static final String WORKING_DIR_PROPERTY = NAME + ".dir";
81  private static final String HEX_FILE_PROPERTY = NAME + ".hex.file";
82  private static final String DIGIT_START_PROPERTY = NAME + ".digit.start";
83  private static final String DIGIT_SIZE_PROPERTY = NAME + ".digit.size";
84  private static final String DIGIT_PARTS_PROPERTY = NAME + ".digit.parts";
85
86  private static final Log LOG = LogFactory.getLog(BaileyBorweinPlouffe.class);
87
88  /** Mapper class computing digits of Pi. */
89  public static class BbpMapper extends
90      Mapper<LongWritable, IntWritable, LongWritable, BytesWritable> {
91
92    /** Compute the (offset+1)th to (offset+length)th digits. */
93    protected void map(LongWritable offset, IntWritable length,
94        final Context context) throws IOException, InterruptedException {
95      LOG.info("offset=" + offset + ", length=" + length);
96
97      // compute digits
98      final byte[] bytes = new byte[length.get() >> 1];
99      long d = offset.get();
100      for (int i = 0; i < bytes.length; d += 4) {
101        final long digits = hexDigits(d);
102        bytes[i++] = (byte) (digits >> 8);
103        bytes[i++] = (byte) digits;
104      }
105
106      // output map results
107      context.write(offset, new BytesWritable(bytes));
108    }
109  }
110
111  /** Reducer for concatenating map outputs. */
112  public static class BbpReducer extends
113      Reducer<LongWritable, BytesWritable, LongWritable, BytesWritable> {
114
115    /** Storing hex digits */
116    private final List<Byte> hex = new ArrayList<Byte>();
117
118    /** Concatenate map outputs. */
119    @Override
120    protected void reduce(LongWritable offset, Iterable<BytesWritable> values,
121        Context context) throws IOException, InterruptedException {
122      // read map outputs
123      for (BytesWritable bytes : values) {
124        for (int i = 0; i < bytes.getLength(); i++)
125          hex.add(bytes.getBytes()[i]);
126      }
127
128      LOG.info("hex.size() = " + hex.size());
129    }
130
131    /** Write output to files. */
132    @Override
133    protected void cleanup(Context context
134        ) throws IOException, InterruptedException {
135      final Configuration conf = context.getConfiguration();
136      final Path dir = new Path(conf.get(WORKING_DIR_PROPERTY));
137      final FileSystem fs = dir.getFileSystem(conf);
138
139      // write hex output
140      {
141        final Path hexfile = new Path(conf.get(HEX_FILE_PROPERTY));
142        final OutputStream out = new BufferedOutputStream(fs.create(hexfile));
143        try {
144          for (byte b : hex)
145            out.write(b);
146        } finally {
147          out.close();
148        }
149      }
150
151      // If the starting digit is 1,
152      // the hex value can be converted to decimal value.
153      if (conf.getInt(DIGIT_START_PROPERTY, 1) == 1) {
154        final Path outfile = new Path(dir, "pi.txt");
155        LOG.info("Writing text output to " + outfile);
156        final OutputStream outputstream = fs.create(outfile);
157        try {
158          final PrintWriter out = new PrintWriter(
159              new OutputStreamWriter(outputstream, Charsets.UTF_8), true);
160          // write hex text
161          print(out, hex.iterator(), "Pi = 0x3.", "%02X", 5, 5);
162          out.println("Total number of hexadecimal digits is "
163              + 2 * hex.size() + ".");
164
165          // write decimal text
166          final Fraction dec = new Fraction(hex);
167          final int decDigits = 2 * hex.size(); // TODO: this is conservative.
168          print(out, new Iterator<Integer>() {
169            private int i = 0;
170
171            public boolean hasNext() {
172              return i < decDigits;
173            }
174
175            public Integer next() {
176              i++;
177              return dec.times10();
178            }
179
180            public void remove() {
181            }
182          }, "Pi = 3.", "%d", 10, 5);
183          out.println("Total number of decimal digits is " + decDigits + ".");
184        } finally {
185          outputstream.close();
186        }
187      }
188    }
189  }
190
191  /** Print out elements in a nice format. */
192  private static <T> void print(PrintWriter out, Iterator<T> iterator,
193      String prefix, String format, int elementsPerGroup, int groupsPerLine) {
194    final StringBuilder sb = new StringBuilder("\n");
195    for (int i = 0; i < prefix.length(); i++)
196      sb.append(" ");
197    final String spaces = sb.toString();
198
199    out.print("\n" + prefix);
200    for (int i = 0; iterator.hasNext(); i++) {
201      if (i > 0 && i % elementsPerGroup == 0)
202        out.print((i / elementsPerGroup) % groupsPerLine == 0 ? spaces : " ");
203      out.print(String.format(format, iterator.next()));
204    }
205    out.println();
206  }
207
208  /** Input split for the {@link BbpInputFormat}. */
209  public static class BbpSplit extends InputSplit implements Writable {
210    private final static String[] EMPTY = {};
211
212    private long offset;
213    private int size;
214
215    /** Public default constructor for the Writable interface. */
216    public BbpSplit() {
217    }
218
219    private BbpSplit(int i, long offset, int size) {
220      LOG.info("Map #" + i + ": workload=" + workload(offset, size)
221          + ", offset=" + offset + ", size=" + size);
222      this.offset = offset;
223      this.size = size;
224    }
225
226    private long getOffset() {
227      return offset;
228    }
229
230    /** {@inheritDoc} */
231    public long getLength() {
232      return size;
233    }
234
235    /** No location is needed. */
236    public String[] getLocations() {
237      return EMPTY;
238    }
239
240    /** {@inheritDoc} */
241    public void readFields(DataInput in) throws IOException {
242      offset = in.readLong();
243      size = in.readInt();
244    }
245
246    /** {@inheritDoc} */
247    public void write(DataOutput out) throws IOException {
248      out.writeLong(offset);
249      out.writeInt(size);
250    }
251  }
252
253  /**
254   * Input format for the {@link BbpMapper}.
255   * Keys and values represent offsets and sizes, respectively.
256   */
257  public static class BbpInputFormat
258      extends InputFormat<LongWritable, IntWritable> {
259
260    /** {@inheritDoc} */
261    public List<InputSplit> getSplits(JobContext context) {
262      //get the property values
263      final int startDigit = context.getConfiguration().getInt(
264          DIGIT_START_PROPERTY, 1);
265      final int nDigits = context.getConfiguration().getInt(
266          DIGIT_SIZE_PROPERTY, 100);
267      final int nMaps = context.getConfiguration().getInt(
268          DIGIT_PARTS_PROPERTY, 1);
269
270      //create splits
271      final List<InputSplit> splits = new ArrayList<InputSplit>(nMaps);
272      final int[] parts = partition(startDigit - 1, nDigits, nMaps);
273      for (int i = 0; i < parts.length; ++i) {
274        final int k = i < parts.length - 1 ? parts[i+1]: nDigits+startDigit-1;
275        splits.add(new BbpSplit(i, parts[i], k - parts[i]));
276      }
277      return splits;
278    }
279
280    /** {@inheritDoc} */
281    public RecordReader<LongWritable, IntWritable> createRecordReader(
282        InputSplit generic, TaskAttemptContext context) {
283      final BbpSplit split = (BbpSplit)generic;
284
285      //return a record reader
286      return new RecordReader<LongWritable, IntWritable>() {
287        boolean done = false;
288
289        public void initialize(InputSplit split, TaskAttemptContext context) {
290        }
291
292        public boolean nextKeyValue() {
293          //Each record only contains one key.
294          return !done ? done = true : false;
295        }
296
297        public LongWritable getCurrentKey() {
298          return new LongWritable(split.getOffset());
299        }
300
301        public IntWritable getCurrentValue() {
302          return new IntWritable((int)split.getLength());
303        }
304
305        public float getProgress() {
306          return done? 1f: 0f;
307        }
308
309        public void close() {
310        }
311      };
312    }
313  }
314
315  /** Create and setup a job */
316  private static Job createJob(String name, Configuration conf
317      ) throws IOException {
318    final Job job = Job.getInstance(conf, NAME + "_" + name);
319    final Configuration jobconf = job.getConfiguration();
320    job.setJarByClass(BaileyBorweinPlouffe.class);
321
322    // setup mapper
323    job.setMapperClass(BbpMapper.class);
324    job.setMapOutputKeyClass(LongWritable.class);
325    job.setMapOutputValueClass(BytesWritable.class);
326
327    // setup reducer
328    job.setReducerClass(BbpReducer.class);
329    job.setOutputKeyClass(LongWritable.class);
330    job.setOutputValueClass(BytesWritable.class);
331    job.setNumReduceTasks(1);
332
333    // setup input
334    job.setInputFormatClass(BbpInputFormat.class);
335
336    // disable task timeout
337    jobconf.setLong(MRJobConfig.TASK_TIMEOUT, 0);
338
339    // do not use speculative execution
340    jobconf.setBoolean(MRJobConfig.MAP_SPECULATIVE, false);
341    jobconf.setBoolean(MRJobConfig.REDUCE_SPECULATIVE, false);
342    return job;
343  }
344
345  /** Run a map/reduce job to compute Pi. */
346  private static void compute(int startDigit, int nDigits, int nMaps,
347      String workingDir, Configuration conf, PrintStream out
348      ) throws IOException {
349    final String name = startDigit + "_" + nDigits;
350
351    //setup wroking directory
352    out.println("Working Directory = " + workingDir);
353    out.println();
354    final FileSystem fs = FileSystem.get(conf);
355    final Path dir = fs.makeQualified(new Path(workingDir));
356    if (fs.exists(dir)) {
357      throw new IOException("Working directory " + dir
358          + " already exists.  Please remove it first.");
359    } else if (!fs.mkdirs(dir)) {
360      throw new IOException("Cannot create working directory " + dir);
361    }
362
363    out.println("Start Digit      = " + startDigit);
364    out.println("Number of Digits = " + nDigits);
365    out.println("Number of Maps   = " + nMaps);
366
367    // setup a job
368    final Job job = createJob(name, conf);
369    final Path hexfile = new Path(dir, "pi_" + name + ".hex");
370    FileOutputFormat.setOutputPath(job, new Path(dir, "out"));
371
372    // setup custom properties
373    job.getConfiguration().set(WORKING_DIR_PROPERTY, dir.toString());
374    job.getConfiguration().set(HEX_FILE_PROPERTY, hexfile.toString());
375
376    job.getConfiguration().setInt(DIGIT_START_PROPERTY, startDigit);
377    job.getConfiguration().setInt(DIGIT_SIZE_PROPERTY, nDigits);
378    job.getConfiguration().setInt(DIGIT_PARTS_PROPERTY, nMaps);
379
380    // start a map/reduce job
381    out.println("\nStarting Job ...");
382    final long startTime = System.currentTimeMillis();
383    try {
384      if (!job.waitForCompletion(true)) {
385        out.println("Job failed.");
386        System.exit(1);
387      }
388    } catch (Exception e) {
389      throw new RuntimeException(e);
390    } finally {
391      final double duration = (System.currentTimeMillis() - startTime)/1000.0;
392      out.println("Duration is " + duration + " seconds.");
393    }
394    out.println("Output file: " + hexfile);
395  }
396
397  /**
398   * Parse arguments and then runs a map/reduce job.
399   * @return a non-zero value if there is an error. Otherwise, return 0.
400   */
401  public int run(String[] args) throws IOException {
402    if (args.length != 4) {
403      System.err.println("Usage: java " + getClass().getName()
404          + " <startDigit> <nDigits> <nMaps> <workingDir>");
405      ToolRunner.printGenericCommandUsage(System.err);
406      return -1;
407    }
408
409    final int startDigit = Integer.parseInt(args[0]);
410    final int nDigits = Integer.parseInt(args[1]);
411    final int nMaps = Integer.parseInt(args[2]);
412    final String workingDir = args[3];
413
414    if (startDigit <= 0) {
415      throw new IllegalArgumentException("startDigit = " + startDigit+" <= 0");
416    } else if (nDigits <= 0) {
417      throw new IllegalArgumentException("nDigits = " + nDigits + " <= 0");
418    } else if (nDigits % BBP_HEX_DIGITS != 0) {
419      throw new IllegalArgumentException("nDigits = " + nDigits
420          + " is not a multiple of " + BBP_HEX_DIGITS);
421    } else if (nDigits - 1L + startDigit > IMPLEMENTATION_LIMIT + BBP_HEX_DIGITS) {
422      throw new UnsupportedOperationException("nDigits - 1 + startDigit = "
423          + (nDigits - 1L + startDigit)
424          + " > IMPLEMENTATION_LIMIT + BBP_HEX_DIGITS,"
425          + ", where IMPLEMENTATION_LIMIT=" + IMPLEMENTATION_LIMIT
426          + "and BBP_HEX_DIGITS=" + BBP_HEX_DIGITS);
427    } else if (nMaps <= 0) {
428      throw new IllegalArgumentException("nMaps = " + nMaps + " <= 0");
429    }
430
431    compute(startDigit, nDigits, nMaps, workingDir, getConf(), System.out);
432    return 0;
433  }
434
435  /** The main method for running it as a stand alone command. */
436  public static void main(String[] argv) throws Exception {
437    System.exit(ToolRunner.run(null, new BaileyBorweinPlouffe(), argv));
438  }
439
440    /////////////////////////////////////////////////////////////////////
441   // static fields and methods for Bailey-Borwein-Plouffe algorithm. //
442  /////////////////////////////////////////////////////////////////////
443
444  /** Limitation of the program.
445   * The program may return incorrect results if the limit is exceeded.
446   * The default value is 10^8.
447   * The program probably can handle some higher values such as 2^28.
448   */
449  private static final long IMPLEMENTATION_LIMIT = 100000000;
450
451  private static final long ACCURACY_BIT = 32;
452  private static final long BBP_HEX_DIGITS = 4;
453  private static final long BBP_MULTIPLIER = 1 << (4 * BBP_HEX_DIGITS);
454
455  /**
456   * Compute the exact (d+1)th to (d+{@link #BBP_HEX_DIGITS})th
457   * hex digits of pi.
458   */
459  static long hexDigits(final long d) {
460    if (d < 0) {
461      throw new IllegalArgumentException("d = " + d + " < 0");
462    } else if (d > IMPLEMENTATION_LIMIT) {
463      throw new IllegalArgumentException("d = " + d
464          + " > IMPLEMENTATION_LIMIT = " + IMPLEMENTATION_LIMIT);
465    }
466
467    final double s1 = sum(1, d);
468    final double s4 = sum(4, d);
469    final double s5 = sum(5, d);
470    final double s6 = sum(6, d);
471
472    double pi = s1 + s1;
473    if (pi >= 1)
474      pi--;
475    pi *= 2;
476    if (pi >= 1)
477      pi--;
478
479    pi -= s4;
480    if (pi < 0)
481      pi++;
482    pi -= s4;
483    if (pi < 0)
484      pi++;
485    pi -= s5;
486    if (pi < 0)
487      pi++;
488    pi -= s6;
489    if (pi < 0)
490      pi++;
491
492    return (long) (pi * BBP_MULTIPLIER);
493  }
494
495  /**
496   * Approximate the fraction part of
497   * $16^d \sum_{k=0}^\infty \frac{16^{d-k}}{8k+j}$
498   * for d > 0 and j = 1, 4, 5, 6.
499   */
500  private static double sum(final long j, final long d) {
501    long k = j == 1 ? 1 : 0;
502    double s = 0;
503    if (k <= d) {
504      s = 1.0 / ((d << 3) | j);
505      for (; k < d; k++) {
506        final long n = (k << 3) | j;
507        s += mod((d - k) << 2, n) * 1.0 / n;
508        if (s >= 1)
509          s--;
510      }
511      k++;
512    }
513
514    if (k >= 1L << (ACCURACY_BIT - 7))
515      return s;
516
517    for (;; k++) {
518      final long n = (k << 3) | j;
519      final long shift = (k - d) << 2;
520      if (ACCURACY_BIT <= shift || 1L << (ACCURACY_BIT - shift) < n) {
521        return s;
522      }
523
524      s += 1.0 / (n << shift);
525      if (s >= 1)
526        s--;
527    }
528  }
529
530  /** Compute $2^e \mod n$ for e > 0, n > 2 */
531  static long mod(final long e, final long n) {
532    long mask = (e & 0xFFFFFFFF00000000L) == 0 ? 0x00000000FFFFFFFFL
533        : 0xFFFFFFFF00000000L;
534    mask &= (e & 0xFFFF0000FFFF0000L & mask) == 0 ? 0x0000FFFF0000FFFFL
535        : 0xFFFF0000FFFF0000L;
536    mask &= (e & 0xFF00FF00FF00FF00L & mask) == 0 ? 0x00FF00FF00FF00FFL
537        : 0xFF00FF00FF00FF00L;
538    mask &= (e & 0xF0F0F0F0F0F0F0F0L & mask) == 0 ? 0x0F0F0F0F0F0F0F0FL
539        : 0xF0F0F0F0F0F0F0F0L;
540    mask &= (e & 0xCCCCCCCCCCCCCCCCL & mask) == 0 ? 0x3333333333333333L
541        : 0xCCCCCCCCCCCCCCCCL;
542    mask &= (e & 0xAAAAAAAAAAAAAAAAL & mask) == 0 ? 0x5555555555555555L
543        : 0xAAAAAAAAAAAAAAAAL;
544
545    long r = 2;
546    for (mask >>= 1; mask > 0; mask >>= 1) {
547      r *= r;
548      r %= n;
549
550      if ((e & mask) != 0) {
551        r += r;
552        if (r >= n)
553          r -= n;
554      }
555    }
556    return r;
557  }
558
559  /** Represent a number x in hex for 1 > x >= 0 */
560  private static class Fraction {
561    private final int[] integers; // only use 24-bit
562
563    private int first = 0; // index to the first non-zero integer
564
565    /** Construct a fraction represented by the bytes. */
566    Fraction(List<Byte> bytes) {
567      integers = new int[(bytes.size() + 2) / 3];
568      for (int i = 0; i < bytes.size(); i++) {
569        final int b = 0xFF & bytes.get(i);
570        integers[integers.length - 1 - i / 3] |= b << ((2 - i % 3) << 3);
571      }
572      skipZeros();
573    }
574
575    /**
576     * Compute y = 10*x and then set x to the fraction part of y, where x is the
577     * fraction represented by this object.
578     * @return integer part of y
579     */
580    int times10() {
581      int carry = 0;
582      for (int i = first; i < integers.length; i++) {
583        integers[i] <<= 1;
584        integers[i] += carry + (integers[i] << 2);
585        carry = integers[i] >> 24;
586        integers[i] &= 0xFFFFFF;
587      }
588      skipZeros();
589      return carry;
590    }
591
592    private void skipZeros() {
593      for(; first < integers.length && integers[first] == 0; first++)
594        ;
595    }
596  }
597
598  /**
599   * Partition input so that the workload of each part is
600   * approximately the same.
601   */
602  static int[] partition(final int offset, final int size, final int nParts) {
603    final int[] parts = new int[nParts];
604    final long total = workload(offset, size);
605    final int remainder = offset % 4;
606
607    parts[0] = offset;
608    for (int i = 1; i < nParts; i++) {
609      final long target = offset + i*(total/nParts) + i*(total%nParts)/nParts;
610
611      //search the closest value
612      int low = parts[i - 1];
613      int high = offset + size;
614      for (; high > low + 4;) {
615        final int mid = (high + low - 2 * remainder) / 8 * 4 + remainder;
616        final long midvalue = workload(mid);
617        if (midvalue == target)
618          high = low = mid;
619        else if (midvalue > target)
620          high = mid;
621        else
622          low = mid;
623      }
624      parts[i] = high == low? high:
625          workload(high)-target > target-workload(low)?
626              low: high;
627    }
628    return parts;
629  }
630
631  private static final long MAX_N = 4294967295L; // prevent overflow
632
633  /** Estimate the workload for input size n (in some unit). */
634  private static long workload(final long n) {
635    if (n < 0) {
636      throw new IllegalArgumentException("n = " + n + " < 0");
637    } else if (n > MAX_N) {
638      throw new IllegalArgumentException("n = " + n + " > MAX_N = " + MAX_N);
639    }
640    return (n & 1L) == 0L ? (n >> 1) * (n + 1) : n * ((n + 1) >> 1);
641  }
642
643  private static long workload(long offset, long size) {
644    return workload(offset + size) - workload(offset);
645  }
646}