+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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 { 78static final String DESCRIPTION 79 ="A map/reduce program that estimates Pi using a quasi-Monte Carlo method." ; 80/** tmp directory for input/output */ 81static 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*/ 87private static class HaltonSequence { 88/** Bases */ 89static final int []P = {2 ,3 }; 90/** Maximum number of digits allowed */ 91static final int []K = {63 ,40 }; 92 93private long index ; 94private double []x ; 95private double [][]q ; 96private int [][]d ; 97 98/** Initialize to H(startindex), 99* so the sequence begins with H(startindex+1). 100*/ 101HaltonSequence (long startindex ) { 102index =startindex ; 103x =new double [K .length ]; 104q =new double [K .length ][]; 105d =new int [K .length ][]; 106for (int i =0 ;i <K .length ;i ++) { 107q [i ] =new double [K [i ]]; 108d [i ] =new int [K [i ]]; 109 } 110 111for (int i =0 ;i <K .length ;i ++) { 112long k =index ; 113x [i ] =0 ; 114 115for (int j =0 ;j <K [i ];j ++) { 116q [i ][j ] = (j ==0 ?1.0 :q [i ][j -1 ])/P [i ]; 117d [i ][j ] = (int )(k %P [i ]); 118k = (k -d [i ][j ])/P [i ]; 119x [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*/ 130double []nextPoint () { 131index ++; 132for (int i =0 ;i <K .length ;i ++) { 133for (int j =0 ;j <K [i ];j ++) { 134d [i ][j ]++; 135x [i ] +=q [i ][j ]; 136if (d [i ][j ] <P [i ]) { 137break ; 138 } 139d [i ][j ] =0 ; 140x [i ] -= (j ==0 ?1.0 :q [i ][j -1 ]); 141 } 142 } 143return 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*/ 152public static class QmcMapper extends 153Mapper <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->numInside, false->numOutside} 159*/ 160public void map (LongWritable offset , 161LongWritable size , 162Context context ) 163throws IOException ,InterruptedException { 164 165final HaltonSequence haltonsequence =new HaltonSequence (offset .get ()); 166long numInside =0L ; 167long numOutside =0L ; 168 169for (long i =0 ;i <size .get (); ) { 170//generate points in a unit square 171final double []point =haltonsequence .nextPoint (); 172 173//count points inside/outside of the inscribed circle of the square 174final double x =point [0 ] -0.5 ; 175final double y =point [1 ] -0.5 ; 176if (x *x +y *y >0.25 ) { 177numOutside ++; 178 }else { 179numInside ++; 180 } 181 182//report status 183i ++; 184if (i %1000 ==0 ) { 185context .setStatus ("Generated " +i +" samples." ); 186 } 187 } 188 189//output map results 190context .write (new BooleanWritable (true ),new LongWritable (numInside )); 191context .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*/ 199public static class QmcReducer extends 200Reducer <BooleanWritable ,LongWritable ,WritableComparable <?>,Writable > { 201 202private long numInside =0 ; 203private 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*/ 211public void reduce (BooleanWritable isInside , 212Iterable <LongWritable >values ,Context context ) 213throws IOException ,InterruptedException { 214if (isInside .get ()) { 215for (LongWritable val :values ) { 216numInside +=val .get (); 217 } 218 }else { 219for (LongWritable val :values ) { 220numOutside +=val .get (); 221 } 222 } 223 } 224 225/** 226* Reduce task done, write output to a file. 227*/ 228@ Override 229public void cleanup (Context context )throws IOException { 230//write output to a file 231Configuration conf =context .getConfiguration (); 232Path outDir =new Path (conf .get (FileOutputFormat .OUTDIR )); 233Path outFile =new Path (outDir ,"reduce-out" ); 234FileSystem fileSys =FileSystem .get (conf ); 235SequenceFile .Writer writer =SequenceFile .createWriter (fileSys ,conf , 236outFile ,LongWritable .class ,LongWritable .class , 237CompressionType .NONE ); 238writer .append (new LongWritable (numInside ),new LongWritable (numOutside )); 239writer .close (); 240 } 241 } 242 243/** 244* Run a map/reduce job for estimating Pi. 245* 246* @return the estimated value of Pi 247*/ 248public static BigDecimal estimatePi (int numMaps ,long numPoints , 249Path tmpDir ,Configuration conf 250 )throws IOException ,ClassNotFoundException ,InterruptedException { 251Job job =Job .getInstance (conf ); 252//setup job conf 253job .setJobName (QuasiMonteCarlo .class .getSimpleName ()); 254job .setJarByClass (QuasiMonteCarlo .class ); 255 256job .setInputFormatClass (SequenceFileInputFormat .class ); 257 258job .setOutputKeyClass (BooleanWritable .class ); 259job .setOutputValueClass (LongWritable .class ); 260job .setOutputFormatClass (SequenceFileOutputFormat .class ); 261 262job .setMapperClass (QmcMapper .class ); 263 264job .setReducerClass (QmcReducer .class ); 265job .setNumReduceTasks (1 ); 266 267// turn off speculative execution, because DFS doesn't handle 268// multiple writers to the same file. 269job .setSpeculativeExecution (false ); 270 271//setup input/output directories 272final Path inDir =new Path (tmpDir ,"in" ); 273final Path outDir =new Path (tmpDir ,"out" ); 274FileInputFormat .setInputPaths (job ,inDir ); 275FileOutputFormat .setOutputPath (job ,outDir ); 276 277final FileSystem fs =FileSystem .get (conf ); 278if (fs .exists (tmpDir )) { 279throw new IOException ("Tmp directory " +fs .makeQualified (tmpDir ) 280 +" already exists. Please remove it first." ); 281 } 282if (!fs .mkdirs (inDir )) { 283throw new IOException ("Cannot create input directory " +inDir ); 284 } 285 286try { 287//generate an input file for each map task 288for (int i =0 ;i <numMaps ; ++i ) { 289final Path file =new Path (inDir ,"part" +i ); 290final LongWritable offset =new LongWritable (i *numPoints ); 291final LongWritable size =new LongWritable (numPoints ); 292final SequenceFile .Writer writer =SequenceFile .createWriter ( 293fs ,conf ,file , 294LongWritable .class ,LongWritable .class ,CompressionType .NONE ); 295try { 296writer .append (offset ,size ); 297 }finally { 298writer .close (); 299 } 300System .out .println ("Wrote input for Map #" +i ); 301 } 302 303//start a map/reduce job 304System .out .println ("Starting Job" ); 305final long startTime =System .currentTimeMillis (); 306job .waitForCompletion (true ); 307final double duration = (System .currentTimeMillis () -startTime )/1000.0 ; 308System .out .println ("Job Finished in " +duration +" seconds" ); 309 310//read outputs 311Path inFile =new Path (outDir ,"reduce-out" ); 312LongWritable numInside =new LongWritable (); 313LongWritable numOutside =new LongWritable (); 314SequenceFile .Reader reader =new SequenceFile .Reader (fs ,inFile ,conf ); 315try { 316reader .next (numInside ,numOutside ); 317 }finally { 318reader .close (); 319 } 320 321//compute estimated value 322final BigDecimal numTotal 323 =BigDecimal .valueOf (numMaps ).multiply (BigDecimal .valueOf (numPoints )); 324return BigDecimal .valueOf (4 ).setScale (20 ) 325 .multiply (BigDecimal .valueOf (numInside .get ())) 326 .divide (numTotal ,RoundingMode .HALF_UP ); 327 }finally { 328fs .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*/ 338public int run (String []args )throws Exception { 339if (args .length !=2 ) { 340System .err .println ("Usage: " +getClass ().getName ()+" <nMaps> <nSamples>" ); 341ToolRunner .printGenericCommandUsage (System .err ); 342return 2 ; 343 } 344 345final int nMaps =Integer .parseInt (args [0 ]); 346final long nSamples =Long .parseLong (args [1 ]); 347long now =System .currentTimeMillis (); 348int rand =new Random ().nextInt (Integer .MAX_VALUE ); 349final Path tmpDir =new Path (TMP_DIR_PREFIX +"_" +now +"_" +rand ); 350 351System .out .println ("Number of Maps = " +nMaps ); 352System .out .println ("Samples per Map = " +nSamples ); 353 354System .out .println ("Estimated value of Pi is " 355 +estimatePi (nMaps ,nSamples ,tmpDir ,getConf ())); 356return 0 ; 357 } 358 359/** 360* main method for running it as a stand alone command. 361*/ 362public static void main (String []argv )throws Exception { 363System .exit (ToolRunner .run (null ,new QuasiMonteCarlo (),argv )); 364 } 365}