+/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 .pi ; 19 20import java .util .ArrayList ; 21import java .util .Collections ; 22import java .util .List ; 23import java .util .Map ; 24 25import org .apache .hadoop .conf .Configured ; 26import org .apache .hadoop .examples .pi .DistSum .Computation ; 27import org .apache .hadoop .examples .pi .DistSum .Parameters ; 28import org .apache .hadoop .examples .pi .math .Bellard ; 29import org .apache .hadoop .examples .pi .math .Summation ; 30import org .apache .hadoop .examples .pi .math .Bellard .Parameter ; 31import org .apache .hadoop .util .Tool ; 32import org .apache .hadoop .util .ToolRunner ; 33 34/** 35* A map/reduce program that uses a BBP-type method to compute exact 36* binary digits of Pi. 37* This program is designed for computing the n th bit of Pi, 38* for large n, say n >= 10^8. 39* For computing lower bits of Pi, consider using bbp. 40* 41* The actually computation is done by DistSum jobs. 42* The steps for launching the jobs are: 43* 44* (1) Initialize parameters. 45* (2) Create a list of sums. 46* (3) Read computed values from the given local directory. 47* (4) Remove the computed values from the sums. 48* (5) Partition the remaining sums into computation jobs. 49* (6) Submit the computation jobs to a cluster and then wait for the results. 50* (7) Write job outputs to the given local directory. 51* (8) Combine the job outputs and print the Pi bits. 52*/ 53/* 54* The command line format is: 55* > hadoop org.apache.hadoop.examples.pi.DistBbp \ 56* <b> <nThreads> <nJobs> <type> <nPart> <remoteDir> <localDir> 57* 58* And the parameters are: 59* <b> The number of bits to skip, i.e. compute the (b+1)th position. 60* <nThreads> The number of working threads. 61* <nJobs> The number of jobs per sum. 62* <type> 'm' for map side job, 'r' for reduce side job, 'x' for mix type. 63* <nPart> The number of parts per job. 64* <remoteDir> Remote directory for submitting jobs. 65* <localDir> Local directory for storing output files. 66* 67* Note that it may take a long time to finish all the jobs when <b> is large. 68* If the program is killed in the middle of the execution, the same command with 69* a different <remoteDir> can be used to resume the execution. For example, suppose 70* we use the following command to compute the (10^15+57)th bit of Pi. 71* 72* > hadoop org.apache.hadoop.examples.pi.DistBbp \ 73* 1,000,000,000,000,056 20 1000 x 500 remote/a local/output 74* 75* It uses 20 threads to summit jobs so that there are at most 20 concurrent jobs. 76* Each sum (there are totally 14 sums) is partitioned into 1000 jobs. 77* The jobs will be executed in map-side or reduce-side. Each job has 500 parts. 78* The remote directory for the jobs is remote/a and the local directory 79* for storing output is local/output. Depends on the cluster configuration, 80* it may take many days to finish the entire execution. If the execution is killed, 81* we may resume it by 82* 83* > hadoop org.apache.hadoop.examples.pi.DistBbp \ 84* 1,000,000,000,000,056 20 1000 x 500 remote/b local/output 85*/ 86public final class DistBbp extends Configured implements Tool { 87public static final String DESCRIPTION 88 ="A map/reduce program that uses a BBP-type formula to compute exact bits of Pi." ; 89 90private final Util .Timer timer =new Util .Timer (true ); 91 92/** {@inheritDoc} */ 93public int run (String []args )throws Exception { 94//parse arguments 95if (args .length !=DistSum .Parameters .COUNT +1 ) 96return Util .printUsage (args , 97getClass ().getName () +" <b> " +Parameters .LIST 98 +"\n <b> The number of bits to skip, i.e. compute the (b+1)th position." 99 +Parameters .DESCRIPTION ); 100 101int i =0 ; 102final long b =Util .string2long (args [i ++]); 103final DistSum .Parameters parameters =DistSum .Parameters .parse (args ,i ); 104 105if (b <0 ) 106throw new IllegalArgumentException ("b = " +b +" < 0" ); 107Util .printBitSkipped (b ); 108Util .out .println (parameters ); 109Util .out .println (); 110 111//initialize sums 112final DistSum distsum =new DistSum (); 113distsum .setConf (getConf ()); 114distsum .setParameters (parameters ); 115final boolean isVerbose =getConf ().getBoolean (Parser .VERBOSE_PROPERTY ,false ); 116final Map <Parameter ,List <TaskResult >>existings =new Parser (isVerbose ).parse (parameters .localDir .getPath (),null ); 117Parser .combine (existings ); 118for (List <TaskResult >tr :existings .values ()) 119Collections .sort (tr ); 120Util .out .println (); 121final Map <Bellard .Parameter ,Bellard .Sum >sums =Bellard .getSums (b ,parameters .nJobs ,existings ); 122Util .out .println (); 123 124//execute the computations 125execute (distsum ,sums ); 126 127//compute Pi from the sums 128final double pi =Bellard .computePi (b ,sums ); 129Util .printBitSkipped (b ); 130Util .out .println (Util .pi2string (pi ,Bellard .bit2terms (b ))); 131return 0 ; 132 } 133 134/** Execute DistSum computations */ 135private void execute (DistSum distsum , 136final Map <Bellard .Parameter ,Bellard .Sum >sums )throws Exception { 137final List <Computation >computations =new ArrayList <Computation >(); 138int i =0 ; 139for (Bellard .Parameter p :Bellard .Parameter .values ()) 140for (Summation s :sums .get (p )) 141if (s .getValue () ==null ) 142computations .add (distsum .new Computation (i ++,p .toString (),s )); 143 144if (computations .isEmpty ()) 145Util .out .println ("No computation" ); 146else { 147timer .tick ("execute " +computations .size () +" computation(s)" ); 148Util .execute (distsum .getParameters ().nThreads ,computations ); 149timer .tick ("done" ); 150 } 151 } 152 153/** main */ 154public static void main (String []args )throws Exception { 155System .exit (ToolRunner .run (null ,new DistBbp (),args )); 156 } 157}