+/EE360P

distributed systems

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

vijaygarg1init07ca65d

master
8.5 KiB228 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.dancing;
20
21import java.io.*;
22import java.util.List;
23import java.util.StringTokenizer;
24
25import org.apache.hadoop.conf.Configuration;
26import org.apache.hadoop.conf.Configured;
27import org.apache.hadoop.fs.FileSystem;
28import org.apache.hadoop.fs.Path;
29import org.apache.hadoop.io.Text;
30import org.apache.hadoop.io.WritableComparable;
31import org.apache.hadoop.mapreduce.*;
32import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
33import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
34import org.apache.hadoop.util.*;
35
36import com.google.common.base.Charsets;
37
38/**
39 * Launch a distributed pentomino solver.
40 * It generates a complete list of prefixes of length N with each unique prefix
41 * as a separate line. A prefix is a sequence of N integers that denote the 
42 * index of the row that is choosen for each column in order. Note that the
43 * next column is heuristically choosen by the solver, so it is dependant on
44 * the previous choice. That file is given as the input to
45 * map/reduce. The output key/value are the move prefix/solution as Text/Text.
46 */
47public class DistributedPentomino extends Configured implements Tool {
48
49  private static final int PENT_DEPTH = 5;
50  private static final int PENT_WIDTH = 9;
51  private static final int PENT_HEIGHT = 10;
52  private static final int DEFAULT_MAPS = 2000;
53  
54  /**
55   * Each map takes a line, which represents a prefix move and finds all of 
56   * the solutions that start with that prefix. The output is the prefix as
57   * the key and the solution as the value.
58   */
59  public static class PentMap extends 
60      Mapper<WritableComparable<?>, Text, Text, Text> {
61    
62    private int width;
63    private int height;
64    private int depth;
65    private Pentomino pent;
66    private Text prefixString;
67    private Context context;
68    
69    /**
70     * For each solution, generate the prefix and a string representation
71     * of the solution. The solution starts with a newline, so that the output
72     * looks like:
73     * <prefix>,
74     * <solution>
75     * 
76     */
77    class SolutionCatcher 
78    implements DancingLinks.SolutionAcceptor<Pentomino.ColumnName> {
79      public void solution(List<List<Pentomino.ColumnName>> answer) {
80        String board = Pentomino.stringifySolution(width, height, answer);
81        try {
82          context.write(prefixString, new Text("\n" + board));
83          context.getCounter(pent.getCategory(answer)).increment(1);
84        } catch (IOException e) {
85          System.err.println(StringUtils.stringifyException(e));
86        } catch (InterruptedException ie) {
87          System.err.println(StringUtils.stringifyException(ie));
88        }
89      }
90    }
91    
92    /**
93     * Break the prefix string into moves (a sequence of integer row ids that 
94     * will be selected for each column in order). Find all solutions with
95     * that prefix.
96     */
97    public void map(WritableComparable<?> key, Text value,Context context) 
98        throws IOException {
99      prefixString = value;
100      StringTokenizer itr = new StringTokenizer(prefixString.toString(), ",");
101      int[] prefix = new int[depth];
102      int idx = 0;
103      while (itr.hasMoreTokens()) {
104        String num = itr.nextToken();
105        prefix[idx++] = Integer.parseInt(num);
106      }
107      pent.solve(prefix);
108    }
109    
110    @Override
111    public void setup(Context context) {
112      this.context = context;
113      Configuration conf = context.getConfiguration();
114      depth = conf.getInt(Pentomino.DEPTH, PENT_DEPTH);
115      width = conf.getInt(Pentomino.WIDTH, PENT_WIDTH);
116      height = conf.getInt(Pentomino.HEIGHT, PENT_HEIGHT);
117      pent = (Pentomino) 
118        ReflectionUtils.newInstance(conf.getClass(Pentomino.CLASS, 
119                                                  OneSidedPentomino.class), 
120                                    conf);
121      pent.initialize(width, height);
122      pent.setPrinter(new SolutionCatcher());
123    }
124  }
125  
126  /**
127   * Create the input file with all of the possible combinations of the 
128   * given depth.
129   * @param fs the filesystem to write into
130   * @param dir the directory to write the input file into
131   * @param pent the puzzle 
132   * @param depth the depth to explore when generating prefixes
133   */
134  private static long createInputDirectory(FileSystem fs, 
135                                           Path dir,
136                                           Pentomino pent,
137                                           int depth
138                                           ) throws IOException {
139    fs.mkdirs(dir);
140    List<int[]> splits = pent.getSplits(depth);
141    Path input = new Path(dir, "part1");
142    PrintWriter file = 
143      new PrintWriter(new OutputStreamWriter(new BufferedOutputStream
144                      (fs.create(input), 64*1024), Charsets.UTF_8));
145    for(int[] prefix: splits) {
146      for(int i=0; i < prefix.length; ++i) {
147        if (i != 0) {
148          file.print(',');          
149        }
150        file.print(prefix[i]);
151      }
152      file.print('\n');
153    }
154    file.close();
155    return fs.getFileStatus(input).getLen();
156  }
157  
158  /**
159   * Launch the solver on 9x10 board and the one sided pentominos.
160   * This takes about 2.5 hours on 20 nodes with 2 cpus/node.
161   * Splits the job into 2000 maps and 1 reduce.
162   */
163  public static void main(String[] args) throws Exception {
164    int res = ToolRunner.run(new Configuration(), 
165                new DistributedPentomino(), args);
166    System.exit(res);
167  }
168
169  public int run(String[] args) throws Exception {
170    Configuration conf = getConf();
171    if (args.length == 0) {
172      System.out.println("Usage: pentomino <output> [-depth #] [-height #] [-width #]");
173      ToolRunner.printGenericCommandUsage(System.out);
174      return 2;
175    }
176    // check for passed parameters, otherwise use defaults
177    int width = conf.getInt(Pentomino.WIDTH, PENT_WIDTH);
178    int height = conf.getInt(Pentomino.HEIGHT, PENT_HEIGHT);
179    int depth = conf.getInt(Pentomino.DEPTH, PENT_DEPTH);
180    for (int i = 0; i < args.length; i++) {
181      if (args[i].equalsIgnoreCase("-depth")) {
182        depth = Integer.parseInt(args[++i].trim());
183      } else if (args[i].equalsIgnoreCase("-height")) {
184        height = Integer.parseInt(args[++i].trim());
185      } else if (args[i].equalsIgnoreCase("-width") ) {
186        width = Integer.parseInt(args[++i].trim());
187      }
188    }
189    // now set the values within conf for M/R tasks to read, this
190    // will ensure values are set preventing MAPREDUCE-4678
191    conf.setInt(Pentomino.WIDTH, width);
192    conf.setInt(Pentomino.HEIGHT, height);
193    conf.setInt(Pentomino.DEPTH, depth);
194    Class<? extends Pentomino> pentClass = conf.getClass(Pentomino.CLASS, 
195      OneSidedPentomino.class, Pentomino.class);
196    int numMaps = conf.getInt(MRJobConfig.NUM_MAPS, DEFAULT_MAPS);
197    Path output = new Path(args[0]);
198    Path input = new Path(output + "_input");
199    FileSystem fileSys = FileSystem.get(conf);
200    try {
201      Job job = Job.getInstance(conf);
202      FileInputFormat.setInputPaths(job, input);
203      FileOutputFormat.setOutputPath(job, output);
204      job.setJarByClass(PentMap.class);
205      
206      job.setJobName("dancingElephant");
207      Pentomino pent = ReflectionUtils.newInstance(pentClass, conf);
208      pent.initialize(width, height);
209      long inputSize = createInputDirectory(fileSys, input, pent, depth);
210      // for forcing the number of maps
211      FileInputFormat.setMaxInputSplitSize(job, (inputSize/numMaps));
212   
213      // the keys are the prefix strings
214      job.setOutputKeyClass(Text.class);
215      // the values are puzzle solutions
216      job.setOutputValueClass(Text.class);
217      
218      job.setMapperClass(PentMap.class);        
219      job.setReducerClass(Reducer.class);
220      
221      job.setNumReduceTasks(1);
222      
223      return (job.waitForCompletion(true) ? 0 : 1);
224      } finally {
225      fileSys.delete(input, true);
226    }
227  }
228}