+/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*/ 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 .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 { 73public static final String DESCRIPTION 74 ="A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact digits of Pi." ; 75 76private static final String NAME ="mapreduce." + 77BaileyBorweinPlouffe .class .getSimpleName (); 78 79//custom job properties 80private static final String WORKING_DIR_PROPERTY =NAME +".dir" ; 81private static final String HEX_FILE_PROPERTY =NAME +".hex.file" ; 82private static final String DIGIT_START_PROPERTY =NAME +".digit.start" ; 83private static final String DIGIT_SIZE_PROPERTY =NAME +".digit.size" ; 84private static final String DIGIT_PARTS_PROPERTY =NAME +".digit.parts" ; 85 86private static final Log LOG =LogFactory .getLog (BaileyBorweinPlouffe .class ); 87 88/** Mapper class computing digits of Pi. */ 89public static class BbpMapper extends 90Mapper <LongWritable ,IntWritable ,LongWritable ,BytesWritable > { 91 92/** Compute the (offset+1)th to (offset+length)th digits. */ 93protected void map (LongWritable offset ,IntWritable length , 94final Context context )throws IOException ,InterruptedException { 95LOG .info ("offset=" +offset +", length=" +length ); 96 97// compute digits 98final byte []bytes =new byte [length .get () >>1 ]; 99long d =offset .get (); 100for (int i =0 ;i <bytes .length ;d +=4 ) { 101final long digits =hexDigits (d ); 102bytes [i ++] = (byte ) (digits >>8 ); 103bytes [i ++] = (byte )digits ; 104 } 105 106// output map results 107context .write (offset ,new BytesWritable (bytes )); 108 } 109 } 110 111/** Reducer for concatenating map outputs. */ 112public static class BbpReducer extends 113Reducer <LongWritable ,BytesWritable ,LongWritable ,BytesWritable > { 114 115/** Storing hex digits */ 116private final List <Byte >hex =new ArrayList <Byte >(); 117 118/** Concatenate map outputs. */ 119@ Override 120protected void reduce (LongWritable offset ,Iterable <BytesWritable >values , 121Context context )throws IOException ,InterruptedException { 122// read map outputs 123for (BytesWritable bytes :values ) { 124for (int i =0 ;i <bytes .getLength ();i ++) 125hex .add (bytes .getBytes ()[i ]); 126 } 127 128LOG .info ("hex.size() = " +hex .size ()); 129 } 130 131/** Write output to files. */ 132@ Override 133protected void cleanup (Context context 134 )throws IOException ,InterruptedException { 135final Configuration conf =context .getConfiguration (); 136final Path dir =new Path (conf .get (WORKING_DIR_PROPERTY )); 137final FileSystem fs =dir .getFileSystem (conf ); 138 139// write hex output 140 { 141final Path hexfile =new Path (conf .get (HEX_FILE_PROPERTY )); 142final OutputStream out =new BufferedOutputStream (fs .create (hexfile )); 143try { 144for (byte b :hex ) 145out .write (b ); 146 }finally { 147out .close (); 148 } 149 } 150 151// If the starting digit is 1, 152// the hex value can be converted to decimal value. 153if (conf .getInt (DIGIT_START_PROPERTY ,1 ) ==1 ) { 154final Path outfile =new Path (dir ,"pi.txt" ); 155LOG .info ("Writing text output to " +outfile ); 156final OutputStream outputstream =fs .create (outfile ); 157try { 158final PrintWriter out =new PrintWriter ( 159new OutputStreamWriter (outputstream ,Charsets .UTF_8 ),true ); 160// write hex text 161out ,hex .iterator (),"Pi = 0x3." ,"%02X" ,5 ,5 ); 162out .println ("Total number of hexadecimal digits is " 163 +2 *hex .size () +"." ); 164 165// write decimal text 166final Fraction dec =new Fraction (hex ); 167final int decDigits =2 *hex .size ();// TODO: this is conservative. 168out ,new Iterator <Integer >() { 169private int i =0 ; 170 171public boolean hasNext () { 172return i <decDigits ; 173 } 174 175public Integer next () { 176i ++; 177return dec .times10 (); 178 } 179 180public void remove () { 181 } 182 },"Pi = 3." ,"%d" ,10 ,5 ); 183out .println ("Total number of decimal digits is " +decDigits +"." ); 184 }finally { 185outputstream .close (); 186 } 187 } 188 } 189 } 190 191/** Print out elements in a nice format. */ 192private static <T >void PrintWriter out ,Iterator <T >iterator , 193String prefix ,String format ,int elementsPerGroup ,int groupsPerLine ) { 194final StringBuilder sb =new StringBuilder ("\n" ); 195for (int i =0 ;i <prefix .length ();i ++) 196sb .append (" " ); 197final String spaces =sb .toString (); 198 199out ."\n" +prefix ); 200for (int i =0 ;iterator .hasNext ();i ++) { 201if (i >0 &&i %elementsPerGroup ==0 ) 202out .i /elementsPerGroup ) %groupsPerLine ==0 ?spaces :" " ); 203out .String .format (format ,iterator .next ())); 204 } 205out .println (); 206 } 207 208/** Input split for the {@link BbpInputFormat}. */ 209public static class BbpSplit extends InputSplit implements Writable { 210private final static String []EMPTY = {}; 211 212private long offset ; 213private int size ; 214 215/** Public default constructor for the Writable interface. */ 216public BbpSplit () { 217 } 218 219private BbpSplit (int i ,long offset ,int size ) { 220LOG .info ("Map #" +i +": workload=" +workload (offset ,size ) 221 +", offset=" +offset +", size=" +size ); 222this .offset =offset ; 223this .size =size ; 224 } 225 226private long getOffset () { 227return offset ; 228 } 229 230/** {@inheritDoc} */ 231public long getLength () { 232return size ; 233 } 234 235/** No location is needed. */ 236public String []getLocations () { 237return EMPTY ; 238 } 239 240/** {@inheritDoc} */ 241public void readFields (DataInput in )throws IOException { 242offset =in .readLong (); 243size =in .readInt (); 244 } 245 246/** {@inheritDoc} */ 247public void write (DataOutput out )throws IOException { 248out .writeLong (offset ); 249out .writeInt (size ); 250 } 251 } 252 253/** 254* Input format for the {@link BbpMapper}. 255* Keys and values represent offsets and sizes, respectively. 256*/ 257public static class BbpInputFormat 258extends InputFormat <LongWritable ,IntWritable > { 259 260/** {@inheritDoc} */ 261public List <InputSplit >getSplits (JobContext context ) { 262//get the property values 263final int startDigit =context .getConfiguration ().getInt ( 264DIGIT_START_PROPERTY ,1 ); 265final int nDigits =context .getConfiguration ().getInt ( 266DIGIT_SIZE_PROPERTY ,100 ); 267final int nMaps =context .getConfiguration ().getInt ( 268DIGIT_PARTS_PROPERTY ,1 ); 269 270//create splits 271final List <InputSplit >splits =new ArrayList <InputSplit >(nMaps ); 272final int []parts =partition (startDigit -1 ,nDigits ,nMaps ); 273for (int i =0 ;i <parts .length ; ++i ) { 274final int k =i <parts .length -1 ?parts [i +1 ]:nDigits +startDigit -1 ; 275splits .add (new BbpSplit (i ,parts [i ],k -parts [i ])); 276 } 277return splits ; 278 } 279 280/** {@inheritDoc} */ 281public RecordReader <LongWritable ,IntWritable >createRecordReader ( 282InputSplit generic ,TaskAttemptContext context ) { 283final BbpSplit split = (BbpSplit )generic ; 284 285//return a record reader 286return new RecordReader <LongWritable ,IntWritable >() { 287boolean done =false ; 288 289public void initialize (InputSplit split ,TaskAttemptContext context ) { 290 } 291 292public boolean nextKeyValue () { 293//Each record only contains one key. 294return !done ?done =true :false ; 295 } 296 297public LongWritable getCurrentKey () { 298return new LongWritable (split .getOffset ()); 299 } 300 301public IntWritable getCurrentValue () { 302return new IntWritable ((int )split .getLength ()); 303 } 304 305public float getProgress () { 306return done ?1f :0f ; 307 } 308 309public void close () { 310 } 311 }; 312 } 313 } 314 315/** Create and setup a job */ 316private static Job createJob (String name ,Configuration conf 317 )throws IOException { 318final Job job =Job .getInstance (conf ,NAME +"_" +name ); 319final Configuration jobconf =job .getConfiguration (); 320job .setJarByClass (BaileyBorweinPlouffe .class ); 321 322// setup mapper 323job .setMapperClass (BbpMapper .class ); 324job .setMapOutputKeyClass (LongWritable .class ); 325job .setMapOutputValueClass (BytesWritable .class ); 326 327// setup reducer 328job .setReducerClass (BbpReducer .class ); 329job .setOutputKeyClass (LongWritable .class ); 330job .setOutputValueClass (BytesWritable .class ); 331job .setNumReduceTasks (1 ); 332 333// setup input 334job .setInputFormatClass (BbpInputFormat .class ); 335 336// disable task timeout 337jobconf .setLong (MRJobConfig .TASK_TIMEOUT ,0 ); 338 339// do not use speculative execution 340jobconf .setBoolean (MRJobConfig .MAP_SPECULATIVE ,false ); 341jobconf .setBoolean (MRJobConfig .REDUCE_SPECULATIVE ,false ); 342return job ; 343 } 344 345/** Run a map/reduce job to compute Pi. */ 346private static void compute (int startDigit ,int nDigits ,int nMaps , 347String workingDir ,Configuration conf ,PrintStream out 348 )throws IOException { 349final String name =startDigit +"_" +nDigits ; 350 351//setup wroking directory 352out .println ("Working Directory = " +workingDir ); 353out .println (); 354final FileSystem fs =FileSystem .get (conf ); 355final Path dir =fs .makeQualified (new Path (workingDir )); 356if (fs .exists (dir )) { 357throw new IOException ("Working directory " +dir 358 +" already exists. Please remove it first." ); 359 }else if (!fs .mkdirs (dir )) { 360throw new IOException ("Cannot create working directory " +dir ); 361 } 362 363out .println ("Start Digit = " +startDigit ); 364out .println ("Number of Digits = " +nDigits ); 365out .println ("Number of Maps = " +nMaps ); 366 367// setup a job 368final Job job =createJob (name ,conf ); 369final Path hexfile =new Path (dir ,"pi_" +name +".hex" ); 370FileOutputFormat .setOutputPath (job ,new Path (dir ,"out" )); 371 372// setup custom properties 373job .getConfiguration ().set (WORKING_DIR_PROPERTY ,dir .toString ()); 374job .getConfiguration ().set (HEX_FILE_PROPERTY ,hexfile .toString ()); 375 376job .getConfiguration ().setInt (DIGIT_START_PROPERTY ,startDigit ); 377job .getConfiguration ().setInt (DIGIT_SIZE_PROPERTY ,nDigits ); 378job .getConfiguration ().setInt (DIGIT_PARTS_PROPERTY ,nMaps ); 379 380// start a map/reduce job 381out .println ("\nStarting Job ..." ); 382final long startTime =System .currentTimeMillis (); 383try { 384if (!job .waitForCompletion (true )) { 385out .println ("Job failed." ); 386System .exit (1 ); 387 } 388 }catch (Exception e ) { 389throw new RuntimeException (e ); 390 }finally { 391final double duration = (System .currentTimeMillis () -startTime )/1000.0 ; 392out .println ("Duration is " +duration +" seconds." ); 393 } 394out .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*/ 401public int run (String []args )throws IOException { 402if (args .length !=4 ) { 403System .err .println ("Usage: java " +getClass ().getName () 404 +" <startDigit> <nDigits> <nMaps> <workingDir>" ); 405ToolRunner .printGenericCommandUsage (System .err ); 406return -1 ; 407 } 408 409final int startDigit =Integer .parseInt (args [0 ]); 410final int nDigits =Integer .parseInt (args [1 ]); 411final int nMaps =Integer .parseInt (args [2 ]); 412final String workingDir =args [3 ]; 413 414if (startDigit <=0 ) { 415throw new IllegalArgumentException ("startDigit = " +startDigit +" <= 0" ); 416 }else if (nDigits <=0 ) { 417throw new IllegalArgumentException ("nDigits = " +nDigits +" <= 0" ); 418 }else if (nDigits %BBP_HEX_DIGITS !=0 ) { 419throw new IllegalArgumentException ("nDigits = " +nDigits 420 +" is not a multiple of " +BBP_HEX_DIGITS ); 421 }else if (nDigits -1L +startDigit >IMPLEMENTATION_LIMIT +BBP_HEX_DIGITS ) { 422throw 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 ) { 428throw new IllegalArgumentException ("nMaps = " +nMaps +" <= 0" ); 429 } 430 431compute (startDigit ,nDigits ,nMaps ,workingDir ,getConf (),System .out ); 432return 0 ; 433 } 434 435/** The main method for running it as a stand alone command. */ 436public static void main (String []argv )throws Exception { 437System .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*/ 449private static final long IMPLEMENTATION_LIMIT =100000000 ; 450 451private static final long ACCURACY_BIT =32 ; 452private static final long BBP_HEX_DIGITS =4 ; 453private 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*/ 459static long hexDigits (final long d ) { 460if (d <0 ) { 461throw new IllegalArgumentException ("d = " +d +" < 0" ); 462 }else if (d >IMPLEMENTATION_LIMIT ) { 463throw new IllegalArgumentException ("d = " +d 464 +" > IMPLEMENTATION_LIMIT = " +IMPLEMENTATION_LIMIT ); 465 } 466 467final double s1 =sum (1 ,d ); 468final double s4 =sum (4 ,d ); 469final double s5 =sum (5 ,d ); 470final double s6 =sum (6 ,d ); 471 472double pi =s1 +s1 ; 473if (pi >=1 ) 474pi --; 475pi *=2 ; 476if (pi >=1 ) 477pi --; 478 479pi -=s4 ; 480if (pi <0 ) 481pi ++; 482pi -=s4 ; 483if (pi <0 ) 484pi ++; 485pi -=s5 ; 486if (pi <0 ) 487pi ++; 488pi -=s6 ; 489if (pi <0 ) 490pi ++; 491 492return (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*/ 500private static double sum (final long j ,final long d ) { 501long k =j ==1 ?1 :0 ; 502double s =0 ; 503if (k <=d ) { 504s =1.0 / ((d <<3 ) |j ); 505for (;k <d ;k ++) { 506final long n = (k <<3 ) |j ; 507s +=mod ((d -k ) <<2 ,n ) *1.0 /n ; 508if (s >=1 ) 509s --; 510 } 511k ++; 512 } 513 514if (k >=1L << (ACCURACY_BIT -7 )) 515return s ; 516 517for (;;k ++) { 518final long n = (k <<3 ) |j ; 519final long shift = (k -d ) <<2 ; 520if (ACCURACY_BIT <=shift ||1L << (ACCURACY_BIT -shift ) <n ) { 521return s ; 522 } 523 524s +=1.0 / (n <<shift ); 525if (s >=1 ) 526s --; 527 } 528 } 529 530/** Compute $2^e \mod n$ for e > 0, n > 2 */ 531static long mod (final long e ,final long n ) { 532long mask = (e &0xFFFFFFFF00000000L ) ==0 ?0x00000000FFFFFFFFL 533 :0xFFFFFFFF00000000L ; 534mask &= (e &0xFFFF0000FFFF0000L &mask ) ==0 ?0x0000FFFF0000FFFFL 535 :0xFFFF0000FFFF0000L ; 536mask &= (e &0xFF00FF00FF00FF00L &mask ) ==0 ?0x00FF00FF00FF00FFL 537 :0xFF00FF00FF00FF00L ; 538mask &= (e &0xF0F0F0F0F0F0F0F0L &mask ) ==0 ?0x0F0F0F0F0F0F0F0FL 539 :0xF0F0F0F0F0F0F0F0L ; 540mask &= (e &0xCCCCCCCCCCCCCCCCL &mask ) ==0 ?0x3333333333333333L 541 :0xCCCCCCCCCCCCCCCCL ; 542mask &= (e &0xAAAAAAAAAAAAAAAAL &mask ) ==0 ?0x5555555555555555L 543 :0xAAAAAAAAAAAAAAAAL ; 544 545long r =2 ; 546for (mask >>=1 ;mask >0 ;mask >>=1 ) { 547r *=r ; 548r %=n ; 549 550if ((e &mask ) !=0 ) { 551r +=r ; 552if (r >=n ) 553r -=n ; 554 } 555 } 556return r ; 557 } 558 559/** Represent a number x in hex for 1 > x >= 0 */ 560private static class Fraction { 561private final int []integers ;// only use 24-bit 562 563private int first =0 ;// index to the first non-zero integer 564 565/** Construct a fraction represented by the bytes. */ 566Fraction (List <Byte >bytes ) { 567integers =new int [(bytes .size () +2 ) /3 ]; 568for (int i =0 ;i <bytes .size ();i ++) { 569final int b =0xFF &bytes .get (i ); 570integers [integers .length -1 -i /3 ] |=b << ((2 -i %3 ) <<3 ); 571 } 572skipZeros (); 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*/ 580int times10 () { 581int carry =0 ; 582for (int i =first ;i <integers .length ;i ++) { 583integers [i ] <<=1 ; 584integers [i ] +=carry + (integers [i ] <<2 ); 585carry =integers [i ] >>24 ; 586integers [i ] &=0xFFFFFF ; 587 } 588skipZeros (); 589return carry ; 590 } 591 592private void skipZeros () { 593for (;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*/ 602static int []partition (final int offset ,final int size ,final int nParts ) { 603final int []parts =new int [nParts ]; 604final long total =workload (offset ,size ); 605final int remainder =offset %4 ; 606 607parts [0 ] =offset ; 608for (int i =1 ;i <nParts ;i ++) { 609final long target =offset +i *(total /nParts ) +i *(total %nParts )/nParts ; 610 611//search the closest value 612int low =parts [i -1 ]; 613int high =offset +size ; 614for (;high >low +4 ;) { 615final int mid = (high +low -2 *remainder ) /8 *4 +remainder ; 616final long midvalue =workload (mid ); 617if (midvalue ==target ) 618high =low =mid ; 619else if (midvalue >target ) 620high =mid ; 621else 622low =mid ; 623 } 624parts [i ] =high ==low ?high : 625workload (high )-target >target -workload (low )? 626low :high ; 627 } 628return parts ; 629 } 630 631private static final long MAX_N =4294967295L ;// prevent overflow 632 633/** Estimate the workload for input size n (in some unit). */ 634private static long workload (final long n ) { 635if (n <0 ) { 636throw new IllegalArgumentException ("n = " +n +" < 0" ); 637 }else if (n >MAX_N ) { 638throw new IllegalArgumentException ("n = " +n +" > MAX_N = " +MAX_N ); 639 } 640return (n &1L ) ==0L ? (n >>1 ) * (n +1 ) :n * ((n +1 ) >>1 ); 641 } 642 643private static long workload (long offset ,long size ) { 644return workload (offset +size ) -workload (offset ); 645 } 646}