+/EE360P

distributed systems

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

vijaygarg1init07ca65d

master
12.3 KiB365 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 */
18
19package org.apache.hadoop.examples;
20
21import java.io.IOException;
22import java.math.BigDecimal;
23import java.math.RoundingMode;
24import java.util.Random;
25
26import org.apache.hadoop.conf.Configuration;
27import org.apache.hadoop.conf.Configured;
28import org.apache.hadoop.fs.FileSystem;
29import org.apache.hadoop.fs.Path;
30import org.apache.hadoop.io.BooleanWritable;
31import org.apache.hadoop.io.LongWritable;
32import org.apache.hadoop.io.SequenceFile;
33import org.apache.hadoop.io.Writable;
34import org.apache.hadoop.io.WritableComparable;
35import org.apache.hadoop.io.SequenceFile.CompressionType;
36import org.apache.hadoop.mapreduce.*;
37import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
38import org.apache.hadoop.mapreduce.lib.input.SequenceFileInputFormat;
39import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
40import org.apache.hadoop.mapreduce.lib.output.SequenceFileOutputFormat;
41import org.apache.hadoop.util.Tool;
42import org.apache.hadoop.util.ToolRunner;
43
44/**
45 * A map/reduce program that estimates the value of Pi
46 * using a quasi-Monte Carlo (qMC) method.
47 * Arbitrary integrals can be approximated numerically by qMC methods.
48 * In this example,
49 * we use a qMC method to approximate the integral $I = \int_S f(x) dx$,
50 * where $S=[0,1)^2$ is a unit square,
51 * $x=(x_1,x_2)$ is a 2-dimensional point,
52 * and $f$ is a function describing the inscribed circle of the square $S$,
53 * $f(x)=1$ if $(2x_1-1)^2+(2x_2-1)^2 <= 1$ and $f(x)=0$, otherwise.
54 * It is easy to see that Pi is equal to $4I$.
55 * So an approximation of Pi is obtained once $I$ is evaluated numerically.
56 * 
57 * There are better methods for computing Pi.
58 * We emphasize numerical approximation of arbitrary integrals in this example.
59 * For computing many digits of Pi, consider using bbp.
60 *
61 * The implementation is discussed below.
62 *
63 * Mapper:
64 *   Generate points in a unit square
65 *   and then count points inside/outside of the inscribed circle of the square.
66 *
67 * Reducer:
68 *   Accumulate points inside/outside results from the mappers.
69 *
70 * Let numTotal = numInside + numOutside.
71 * The fraction numInside/numTotal is a rational approximation of
72 * the value (Area of the circle)/(Area of the square) = $I$,
73 * where the area of the inscribed circle is Pi/4
74 * and the area of unit square is 1.
75 * Finally, the estimated value of Pi is 4(numInside/numTotal).  
76 */
77public class QuasiMonteCarlo extends Configured implements Tool {
78  static final String DESCRIPTION
79      = "A map/reduce program that estimates Pi using a quasi-Monte Carlo method.";
80  /** tmp directory for input/output */
81  static private final String TMP_DIR_PREFIX = QuasiMonteCarlo.class.getSimpleName();
82  
83  /** 2-dimensional Halton sequence {H(i)},
84   * where H(i) is a 2-dimensional point and i >= 1 is the index.
85   * Halton sequence is used to generate sample points for Pi estimation. 
86   */
87  private static class HaltonSequence {
88    /** Bases */
89    static final int[] P = {2, 3}; 
90    /** Maximum number of digits allowed */
91    static final int[] K = {63, 40}; 
92
93    private long index;
94    private double[] x;
95    private double[][] q;
96    private int[][] d;
97
98    /** Initialize to H(startindex),
99     * so the sequence begins with H(startindex+1).
100     */
101    HaltonSequence(long startindex) {
102      index = startindex;
103      x = new double[K.length];
104      q = new double[K.length][];
105      d = new int[K.length][];
106      for(int i = 0; i < K.length; i++) {
107        q[i] = new double[K[i]];
108        d[i] = new int[K[i]];
109      }
110
111      for(int i = 0; i < K.length; i++) {
112        long k = index;
113        x[i] = 0;
114        
115        for(int j = 0; j < K[i]; j++) {
116          q[i][j] = (j == 0? 1.0: q[i][j-1])/P[i];
117          d[i][j] = (int)(k % P[i]);
118          k = (k - d[i][j])/P[i];
119          x[i] += d[i][j] * q[i][j];
120        }
121      }
122    }
123
124    /** Compute next point.
125     * Assume the current point is H(index).
126     * Compute H(index+1).
127     * 
128     * @return a 2-dimensional point with coordinates in [0,1)^2
129     */
130    double[] nextPoint() {
131      index++;
132      for(int i = 0; i < K.length; i++) {
133        for(int j = 0; j < K[i]; j++) {
134          d[i][j]++;
135          x[i] += q[i][j];
136          if (d[i][j] < P[i]) {
137            break;
138          }
139          d[i][j] = 0;
140          x[i] -= (j == 0? 1.0: q[i][j-1]);
141        }
142      }
143      return x;
144    }
145  }
146
147  /**
148   * Mapper class for Pi estimation.
149   * Generate points in a unit square
150   * and then count points inside/outside of the inscribed circle of the square.
151   */
152  public static class QmcMapper extends 
153      Mapper<LongWritable, LongWritable, BooleanWritable, LongWritable> {
154
155    /** Map method.
156     * @param offset samples starting from the (offset+1)th sample.
157     * @param size the number of samples for this map
158     * @param context output {ture-&gt;numInside, false-&gt;numOutside}
159     */
160    public void map(LongWritable offset,
161                    LongWritable size,
162                    Context context) 
163        throws IOException, InterruptedException {
164
165      final HaltonSequence haltonsequence = new HaltonSequence(offset.get());
166      long numInside = 0L;
167      long numOutside = 0L;
168
169      for(long i = 0; i < size.get(); ) {
170        //generate points in a unit square
171        final double[] point = haltonsequence.nextPoint();
172
173        //count points inside/outside of the inscribed circle of the square
174        final double x = point[0] - 0.5;
175        final double y = point[1] - 0.5;
176        if (x*x + y*y > 0.25) {
177          numOutside++;
178        } else {
179          numInside++;
180        }
181
182        //report status
183        i++;
184        if (i % 1000 == 0) {
185          context.setStatus("Generated " + i + " samples.");
186        }
187      }
188
189      //output map results
190      context.write(new BooleanWritable(true), new LongWritable(numInside));
191      context.write(new BooleanWritable(false), new LongWritable(numOutside));
192    }
193  }
194
195  /**
196   * Reducer class for Pi estimation.
197   * Accumulate points inside/outside results from the mappers.
198   */
199  public static class QmcReducer extends 
200      Reducer<BooleanWritable, LongWritable, WritableComparable<?>, Writable> {
201    
202    private long numInside = 0;
203    private long numOutside = 0;
204      
205    /**
206     * Accumulate number of points inside/outside results from the mappers.
207     * @param isInside Is the points inside? 
208     * @param values An iterator to a list of point counts
209     * @param context dummy, not used here.
210     */
211    public void reduce(BooleanWritable isInside,
212        Iterable<LongWritable> values, Context context)
213        throws IOException, InterruptedException {
214      if (isInside.get()) {
215        for (LongWritable val : values) {
216          numInside += val.get();
217        }
218      } else {
219        for (LongWritable val : values) {
220          numOutside += val.get();
221        }
222      }
223    }
224
225    /**
226     * Reduce task done, write output to a file.
227     */
228    @Override
229    public void cleanup(Context context) throws IOException {
230      //write output to a file
231      Configuration conf = context.getConfiguration();
232      Path outDir = new Path(conf.get(FileOutputFormat.OUTDIR));
233      Path outFile = new Path(outDir, "reduce-out");
234      FileSystem fileSys = FileSystem.get(conf);
235      SequenceFile.Writer writer = SequenceFile.createWriter(fileSys, conf,
236          outFile, LongWritable.class, LongWritable.class, 
237          CompressionType.NONE);
238      writer.append(new LongWritable(numInside), new LongWritable(numOutside));
239      writer.close();
240    }
241  }
242
243  /**
244   * Run a map/reduce job for estimating Pi.
245   *
246   * @return the estimated value of Pi
247   */
248  public static BigDecimal estimatePi(int numMaps, long numPoints,
249      Path tmpDir, Configuration conf
250      ) throws IOException, ClassNotFoundException, InterruptedException {
251    Job job = Job.getInstance(conf);
252    //setup job conf
253    job.setJobName(QuasiMonteCarlo.class.getSimpleName());
254    job.setJarByClass(QuasiMonteCarlo.class);
255
256    job.setInputFormatClass(SequenceFileInputFormat.class);
257
258    job.setOutputKeyClass(BooleanWritable.class);
259    job.setOutputValueClass(LongWritable.class);
260    job.setOutputFormatClass(SequenceFileOutputFormat.class);
261
262    job.setMapperClass(QmcMapper.class);
263
264    job.setReducerClass(QmcReducer.class);
265    job.setNumReduceTasks(1);
266
267    // turn off speculative execution, because DFS doesn't handle
268    // multiple writers to the same file.
269    job.setSpeculativeExecution(false);
270
271    //setup input/output directories
272    final Path inDir = new Path(tmpDir, "in");
273    final Path outDir = new Path(tmpDir, "out");
274    FileInputFormat.setInputPaths(job, inDir);
275    FileOutputFormat.setOutputPath(job, outDir);
276
277    final FileSystem fs = FileSystem.get(conf);
278    if (fs.exists(tmpDir)) {
279      throw new IOException("Tmp directory " + fs.makeQualified(tmpDir)
280          + " already exists.  Please remove it first.");
281    }
282    if (!fs.mkdirs(inDir)) {
283      throw new IOException("Cannot create input directory " + inDir);
284    }
285
286    try {
287      //generate an input file for each map task
288      for(int i=0; i < numMaps; ++i) {
289        final Path file = new Path(inDir, "part"+i);
290        final LongWritable offset = new LongWritable(i * numPoints);
291        final LongWritable size = new LongWritable(numPoints);
292        final SequenceFile.Writer writer = SequenceFile.createWriter(
293            fs, conf, file,
294            LongWritable.class, LongWritable.class, CompressionType.NONE);
295        try {
296          writer.append(offset, size);
297        } finally {
298          writer.close();
299        }
300        System.out.println("Wrote input for Map #"+i);
301      }
302  
303      //start a map/reduce job
304      System.out.println("Starting Job");
305      final long startTime = System.currentTimeMillis();
306      job.waitForCompletion(true);
307      final double duration = (System.currentTimeMillis() - startTime)/1000.0;
308      System.out.println("Job Finished in " + duration + " seconds");
309
310      //read outputs
311      Path inFile = new Path(outDir, "reduce-out");
312      LongWritable numInside = new LongWritable();
313      LongWritable numOutside = new LongWritable();
314      SequenceFile.Reader reader = new SequenceFile.Reader(fs, inFile, conf);
315      try {
316        reader.next(numInside, numOutside);
317      } finally {
318        reader.close();
319      }
320
321      //compute estimated value
322      final BigDecimal numTotal
323          = BigDecimal.valueOf(numMaps).multiply(BigDecimal.valueOf(numPoints));
324      return BigDecimal.valueOf(4).setScale(20)
325          .multiply(BigDecimal.valueOf(numInside.get()))
326          .divide(numTotal, RoundingMode.HALF_UP);
327    } finally {
328      fs.delete(tmpDir, true);
329    }
330  }
331
332  /**
333   * Parse arguments and then runs a map/reduce job.
334   * Print output in standard out.
335   * 
336   * @return a non-zero if there is an error.  Otherwise, return 0.  
337   */
338  public int run(String[] args) throws Exception {
339    if (args.length != 2) {
340      System.err.println("Usage: "+getClass().getName()+" <nMaps> <nSamples>");
341      ToolRunner.printGenericCommandUsage(System.err);
342      return 2;
343    }
344    
345    final int nMaps = Integer.parseInt(args[0]);
346    final long nSamples = Long.parseLong(args[1]);
347    long now = System.currentTimeMillis();
348    int rand = new Random().nextInt(Integer.MAX_VALUE);
349    final Path tmpDir = new Path(TMP_DIR_PREFIX + "_" + now + "_" + rand);
350        
351    System.out.println("Number of Maps  = " + nMaps);
352    System.out.println("Samples per Map = " + nSamples);
353        
354    System.out.println("Estimated value of Pi is "
355        + estimatePi(nMaps, nSamples, tmpDir, getConf()));
356    return 0;
357  }
358
359  /**
360   * main method for running it as a stand alone command. 
361   */
362  public static void main(String[] argv) throws Exception {
363    System.exit(ToolRunner.run(null, new QuasiMonteCarlo(), argv));
364  }
365}