Chathura Herath 's Blog

Non-tail call to tail call coversion - Scheme Fibonacci example with recursion tree

2011-02-18T18:50:00.000-08:00

After thought from a discussion i had with Felix Terkhorn, made write this blog to show the awesome display of tail-call optimization of scheme using scheme trace. I implemented this optimization when i did my scheme compiler for Prof Dybvig's class.

Here on display is also the conversion of non-tail call to a tail call. Most common example for this is Factorial which can be seen here, but i took Fibonacci as an example because it requires little more thinking. Take a look at the following Fibonacci implementation. We know if lambda is placed in tail context the lambda body will also be in tail context. Also if cond/if is placed in tail context the then and else branches will also be in tail context. But the recursion to fib is placed as args to +. Although + is in the tail context the args to + are not. This is displayed when we calculate (fib 13) and we can see the stack growing and shrinking in the recursion tree.

Now take a look at the re-written tailfib function and its trace. you would notice the tail call optimization as the stack does not grow in the recursion tree. In other words its an iteration. Here the idea is to use an accumulator similar to that of the Factorial example, but in Fibonacci you need two such accumulators because it is a second order recurrence with reference to two previous states. Which updating the accumulators in the reverse order as if you started with the initial condition you would decrement the counter. This placement of accumulators allow us to position tailfib function in tail context of the cond special form, thus making it a tail recursion.

>(define fib (lambda (n)
                 (cond
                  ( (= n 0) 0)
                  ( (= n 1) 1)
                  ( else (+ (fib (- n 1)) (fib (- n 2)))))))
>(fib 7)
13
> (trace fib)
(fib)
> (fib 7)
|(fib 7)
| (fib 5)
| |(fib 3)
| | (fib 1)
| | 1
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| |2
| |(fib 4)
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| |3
| 5
| (fib 6)
| |(fib 4)
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| |3
| |(fib 5)
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| | (fib 4)
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | |(fib 3)
| | | (fib 1)
| | | 1
| | | (fib 2)
| | | |(fib 0)
| | | |0
| | | |(fib 1)
| | | |1
| | | 1
| | |2
| | 3
| |5
| 8
|13
13




>(define tailfib (lambda (n F-1 F-2)
  (cond 
  ( (= n 0) 0)
  ( (= n 1) F-1)
  ( else (tailfib (- n 1) (+ F-1 F-2) F-1)))))

>(define fib(lambda (n)
                    (tailfib n 1 0)))
>(trace tailfib)

>(fib 7)
|(tailfib 7 1 0)
|(tailfib 6 1 1)
|(tailfib 5 2 1)
|(tailfib 4 3 2)
|(tailfib 3 5 3)
|(tailfib 2 8 5)
|(tailfib 1 13 8)
|13
13



Trace lambda in Scheme to display recursion tree
2011-01-29T10:10:00.000-08:00
When doing recursions in Scheme programming sometime its useful to see the growth of the recursion tree for debugging or even to get an intuition about approaches to improve the algorithm like dynamic programming. Following is a pure recursive insertion sort, obviously not the efficient implementation, yet it illustrate the use of trace procedure.

 (define insert (lambda (val sorted)
(if (null? sorted)
(list val)
(if (< val (car sorted))
(cons val sorted)
(cons (car sorted) (insert val (cdr sorted)))))))

(define sort (lambda (vals)
(if (null? vals)
vals
(insert (car vals) (sort (cdr vals))))))

(trace insert)
(trace sort)





(sort '(7 6 5 9 3 4 2 8))
|(sort (7 6 5 9 3 4 2 8))
| (sort (6 5 9 3 4 2 8))
| |(sort (5 9 3 4 2 8))
| | (sort (9 3 4 2 8))
| | |(sort (3 4 2 8))
| | | (sort (4 2 8))
| | | |(sort (2 8))
| | | | (sort (8))
| | | | |(sort ())
| | | | |()
| | | | (insert 8 ())
| | | | (8)
| | | |(insert 2 (8))
| | | |(2 8)
| | | (insert 4 (2 8))
| | | |(insert 4 (8))
| | | |(4 8)
| | | (2 4 8)
| | |(insert 3 (2 4 8))
| | | (insert 3 (4 8))
| | | (3 4 8)
| | |(2 3 4 8)
| | (insert 9 (2 3 4 8))
| | |(insert 9 (3 4 8))
| | | (insert 9 (4 8))
| | | |(insert 9 (8))
| | | | (insert 9 ())
| | | | (9)
| | | |(8 9)
| | | (4 8 9)
| | |(3 4 8 9)
| | (2 3 4 8 9)
| |(insert 5 (2 3 4 8 9))
| | (insert 5 (3 4 8 9))
| | |(insert 5 (4 8 9))
| | | (insert 5 (8 9))
| | | (5 8 9)
| | |(4 5 8 9)
| | (3 4 5 8 9)
| |(2 3 4 5 8 9)
| (insert 6 (2 3 4 5 8 9))
| |(insert 6 (3 4 5 8 9))
| | (insert 6 (4 5 8 9))
| | |(insert 6 (5 8 9))
| | | (insert 6 (8 9))
| | | (6 8 9)
| | |(5 6 8 9)
| | (4 5 6 8 9)
| |(3 4 5 6 8 9)
| (2 3 4 5 6 8 9)
|(insert 7 (2 3 4 5 6 8 9))
| (insert 7 (3 4 5 6 8 9))
| |(insert 7 (4 5 6 8 9))
| | (insert 7 (5 6 8 9))
| | |(insert 7 (6 8 9))
| | | (insert 7 (8 9))
| | | (7 8 9)
| | |(6 7 8 9)
| | (5 6 7 8 9)
| |(4 5 6 7 8 9)
| (3 4 5 6 7 8 9)
|(2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9)


Latex Equation Editor
2010-12-02T20:54:00.000-08:00
Here is a great site that allows you to edit and render mathematical equation.


How to setup Eclipse project and development envionment for changing Hadoop framework
2010-09-06T21:17:00.000-07:00
Here are the three easy steps that i followed when i want to hack the hadoop code to for my research and i have seen this question asked and answered few times and i personally think the approach i took is worth blogging.

First of all you need to decide on the version that you are selecting to hack on. I usually use the .20.2 tag and i download and install the binary version of that and follow the instructions posted  that. Now the idea is you would check out the same tag from svn and and setup an eclipse project  and you would build that project and replace the jar in binary installation with the newly build jar.

Step 1: Install: Download and install a stable version of Hadoop that you are chosen to develop on.

Step2 :  Setup Hadoop Eclipse Project - To setup the Hadoop eclipse project you would have to have Eclipse with the svn plug-in and add a svn repository using  https://svn.apache.org/repos/asf/hadoop/common/  URL. Once the repository is added go into the tags in the repository tree and find the tag version you installed in step 1 and check out that using the eclipse. Now you will have a eclipse project with lot of errors. First step in getting the project to compile is to run the ant jar target in the build script. This will find all the dependency jars and they will be stored in the lib and other folders. You can try to add the jars one by one but i would rather suggest using a explorer like Konqueror and searching for all the jar files in the project root folder and copying all of them into a folder named libn. You might have to manually download the ant.jar and add that to the libn as well. Then you can add all these jar files to the eclipse classpath. Once this is done you will be almost all set except for selecting the src folders that you want to be compiled. Most of the exciting stuff in hadoop happen in src/mapreduce, src/core, src/hdfs source trees. So for a starter i would only add these as the source directories. By now the Eclipse project should compile successfully without errors.

Step 3: Deployment - Once the eclipse project is setup and you done with your hacking and changed say  the Hadoop core, you could  run the jar target of the build.xml and build the project. This would generate a jar file inside the build directory named hadoop-0.xx.x-dev-core.jar. Now you should go to the installation directory of Hadoop in step1 and delete the core jar there and replace it with the new jar you just build. Once you have done that you can restart Hadoop and you will have your own version of Hadoop installation.

Happy Hadoop hacking !!!


Nice overview of Hadoop Pig
2010-06-22T21:05:00.000-07:00

Came across this nice presentation of Hadoop Pig!. It can be found here.


Great Hadoop installation guide
2010-06-15T11:39:00.000-07:00
Following is the link to the  most straight forward installation guide i ve seen so far

Link!!


Amazon Elastic Map Reduce: API call to find and terminate job flows without Amazon Console
2010-05-04T17:30:00.000-07:00
Recently one of the interns in the lab asked me how can he kill the running job flows in Amazon Elastic Map Reduce so he will not run up a big bill. This is straight forward to do in Amazon Management Console, but in this case the student didn't have the username/password to the amazon account because he was using a community account (although he had access to the accesskeys). Another application would be to write a cron job that checks the left over Job Flows and their EC2 instances every night so being able to do this programmatically helps.

Terminating a Job flow is straight forward using the client API that Amazon has provided and a sample can be found here. Now the issue is how to find the running Job Flows using API calls. The DescribeJobFlow API may give the impression that one need to give the Job Flow id to begin with to query the Job Flow Status, but my testing shows that if we don't specify any Job Flow ids in the request as shown in the sample here, it would return the Job Flows with the most recent activities. If there are Job Flows that are running those would have most recent activities. So once you have these two its easy to write a piece of code that would glue these two together to kill all the existing Job Flows.

Thats it!!!


Google Scholar, I want BibTex all the time !!!
2010-04-19T11:25:00.000-07:00
Don't get me wrong, i am extremely grateful for Google scholar especially their import to BibTex feature and yes, i do want to stand on the shoulders of giants.

The BibTex feature is very useful when including related work for a paper but its not there by default and i say they should put it there by default. You do have the option though, to go to preferences and switch it on, but apparently its not associated with my Gmail account and if i login from a different machine i have to switch it on again.


Graham and Brent theorem for speedup when using multiprocessors or multicores
2010-04-09T17:49:00.000-07:00
Since we are big into multicores these days and it would be useful to predict or make a conservative estimate the behavior of an application speedup as we throw more and more processors at it. Let us consider the two obvious extreme cases, one favorable the other unfavorable. The are embarrassingly parallel applications and strictly sequential applications respectively and we will have a look at an example in the reverse order.

Strictly Sequential.

Lets consider calculating the famous nth Fibonacci number and lets assume we do NOT know how to solve a second order recurrence using the clever mathematical way so we will just use the formula as it is. So starting from F0 and F1 we can calculate F2 and so fourth upto the nth number. So if we write a program to calculate Fi we can observe that it has a strict data dependency on Fi-1 and Fi-2. So in such data dependent cases there is no room for making things parallel. Such application obviously won't speed up as you throw more processors at the problem.


Fn+2 = Fn+1 + Fn


Embarrassingly parallel

Consider an application that requires adding two large matrices. Addition of two elements from the matrices are totally independent of any other element. So there is no data dependency in such a case and the matrices can be easily split into sub-problems and given to the number of processors that are available and can be made to run in parallel easily. In such applications programs could achieve linear speed up and in some cases with some clever caching techniques even super linear speedups can be achieved.

In the two cases discussed above we can calculate how an application may speedup in the boundary cases, but most applications that we encounter are in between strictly sequential and embarrassingly parallel. Most applications have certain degree of parallelism and some amount of data dependency which forces sequential behavior and analyzing speed up of such application is much harder. In this post we have a look at  a clever theorem invented by Graham[1] and Brent[2] independently and one of the MIT talks i listened to consolidated their ideas to a very insightful theorem.

First Some naming conventions.

T_n  - Time taken for the application to run when n processors are at its disposal. T_1 represent the sequential case and T_infinity represent that case where application may have as many processors as needed 

based on above conventions we could define:

Parallelism = T_1/T_infinity
Speedup for p processors  = T_1/T_p

An observation assuming no cache tricks to achieve super-linear speedup:

T_p > T_1/p

This simply mean that by having two processors you cannot cut the time exactly by half, it will always be a little more due to possible data dependencies and of course the extra overhead associated with making the application parallel.


Model

This theorem models a given application using a graph where nodes would represent computational units and edges would represent the data dependencies similar to the workflow idea. Graham and Brent argue that if you have infinite processors available for the application, the time will depend upon the critical path of the graph or longest path of the graph from start to finish. So T_infinity may also looked upon as the critical path time. They argue that the speedup that can be achieved depend on this critical path as well as the number of processors that is available to the scheduler at the execution of the application. Based on these two parameters they propose a upper bound to the time taken by an application when its presented with p processors. Upper bound of time is useful because it may allow you to provision your resources for worst case scenario.

Theorem:

T_p <=  T_1/p   + T_infinity

Theorem means an application with p processors at most would take time that is addition of sequential time / p and critical path time. Many techniques have since developed to reduce that upper bound but in my view this is the most insightful theorem of its nature and its simplicity makes it quite appealing when making an conservative estimate or during formal analysis.




[1]R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied
Mathematics, 17(2):416{429, March 1969
[2]Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of
the ACM, 21(2):201{206, April 1974


2010-04-06T19:09:00.000-07:00
Reducing debug cycle during Amazon elastic map reduce development

The cost model that Amazon has published for Amazon Elastic Map Reduce is totally unfair during the development process. The minimum billing unit is an hour and these hours add up quickly to run up your  bill if you are not careful enough. If you are doing anything serious using Amazon Elastic Map Reduce, that is to say you are running something other than the word count example and you choose not to install Hadoop yourself but rather to develop off the Hadoop in Amazon Elastic Map Reduce, you will end up making lot of debug runs to get the configurations right. In each of these runs if the Hadoop gets launched  even for a minute it will charge you for an entire hour times the number of instances you launched. Especially if you are using the Amazon Management Console you will end up having to start a new Job Flow every time you change your application and want to test it. These costs quickly add up if you are not careful, or rather careless.

Tips to reduce the costs

Avoid using the extra large machines 

During development avoid using extra large instances because the cost of these are much much higher and because they have 8 cores you will be billed 8 normalized CPU hours when the instance gets launched.

Programatically Launch Job Flow with keep alive

I wrote a blog earlier showing how to launch a Job Flow programatically and in that i showed how to keep the Job Flow and the instances alive after your map reduce application finish. Then you can simply add a job flow step to the already running application. This will not only reduce the debug cycle because the instance boot up time is no longer relevant to the subsequent Job Flow Steps and you can launch multiple map reduce runs as Job Flow Step with in an hour and yet it will cost you only one hour of CPU because you are not shutting down the instances after one run.

Not develop on Amazon Elastic Map Reduce

One option is to install Hadoop locally and test it there before coming the Amazon so you will not end up paying an hours price for every few minutes of debug run you did.

Amazon should provide development instances billed per minute.

Best scenario is amazon either provide cheaper instances for development or bill per minute during development.


2010-03-31T07:14:00.000-07:00
Optimal Map tasks for Map Reduce Applications based on Time Complexity ???

Some Analysis

One of the strong points in Hadoop is its ability to efficiently partition the input files using API hooks in the HDFS and calling the Map tasks with each of these partitions. Its useful to understand how to find these task distribution to get the best possible performance achievable. There are few factors to consider when trying to pick the right number of map tasks but the obvious would be to strike a balance between the speedup from the distribution and the overhead of distribution.

Consider the case where time Complexity of the application is O(n) meaning the running time depend entirely on the size of the input, like in the case of WordCount. We can argue that the efficient sizes of the partition that the system could handle would be the deciding factor because the running time is only growing linearly with the input and you have to read the input anyway. So in such cases letting the Hadoop decide on the partition sizes will be the right approach because it will base the partition size based on the optimal block sizes. Why? Following may convince you why.

Lets assume Hadoop distribution overhead is linear with the Map tasks, then Total time would look like the following equation. This may be oversimplified equation because it leaves out the reduction complexity and without any argument assumed the overhead of Hadoop is linear with Map Tasks. But this simplicity would let you have more insight.

Total time = O (Input Size/Map Tasks) + Overhead * Map Tasks

So if the application has linear time complexity O(n) then ;

Total time = (Input Size/Map Tasks)+ Overhead * Map Tasks

Taking the derivative would tell you that Total time is minimum when

Map Tasks = sqrt(Input Size/Overhead)

Since this number is very dependent on the Overhead it make sense to let Hadoop do the partitioning and distribution.



Structured input for Map Reduce

Consider the case where the time complexity of the application is not linear but higher, then the dominant term in the Total time is O (Input Size/Map Tasks). In case the time complexity is O(n^2)  =>


Total time = (Input Size/Map Tasks) ^ 2 + Overhead * Map Tasks


Here the first term grows much faster.  So minimizing that by increasing the Map tasks is essential.  So in such cases you cannot let the Hadoop come up with the number of Map tasks based on the optimal block sizes that it can handle but rather you need to force the number of map tasks upon it.

For example a java ray tracing application which has O(n^2)  complexity according to Michael. In this you try to render a scene using ray tracing and this can be easily parallelized because each pixel calculation is independent of the other. When you parallelize it, you will have different segments you want to compute in the input file and you need to force the Map Reduce to calculate those segments in different map tasks.  So you need much structured input than that in the word count example because your number of map tasks and your running time depend on it. Letting the partitioning be done to optimize the file sizes in such a compute intensive application would be unwise and in many cases counterproductive. Although it should be noted Hadoop was designed for data intensive parallelism rather than compute intensive parallelism .


Forcing Hadoop to run a map task for each line in input file

Hadoop provides a input formater called NLineInputFormat where each line in the input file would get mapped to a separate map task which allows you to have control over the number of map tasks that you want to force upon the Hadoop framework. Following is the incomplete code to setup the JobConfiguration and the Bold line shows what you need to do to set the NLineInputFormat. So if you know how to optimally map tasks you need to run you can allow those inputs to lines in the input file so Hadoop will create a new map task for each input.


JobConf conf = new JobConf(HadoopRayTracer.class);
        conf.setJobName("raytrace");
        conf.setOutputKeyClass(Text.class);
        conf.setOutputValueClass(Text.class);
        conf.setMapperClass(Map.class);
        conf.setReducerClass(Reduce.class);

        conf.setInputFormat(NLineInputFormat.class);

        conf.setOutputFormat(TextOutputFormat.class)
.......


2010-03-28T23:19:00.000-07:00
Programmatically Launch Elastic Map Reduce applications

I am writing this mainly to help the student that I am teaching this semester in Prof Beth Plale’s B534 class.


Short Background

Amazon Elastic MapReduce has provides an API to Hadoop MapReduce jobs using Amazon EC2. If you have a Hadoop application you can use the Amazon Console to deploy and run it in the EC2. A great great tutorial on how to use the Amazon Console to run your Hadoop application can be found here.
If you do not have a Hadoop application you need to have a look at the famous word count example which can be found here.


Amazon abstraction of Map reduce.

Amazon has introduce two abstraction for its Elastic MapReduce framework and they are

1) Job Flow
2) Job Flow Step

It is important to understand these abstractions before using the API to launch MapReduce application. Following are the definitions provided by Amazon for Job Flow and Job Flow Step, but it would be much more intuitive to understand them in the context of an application.

Q: What is an Amazon Elastic MapReduce Job Flow?

A Job Flow is a collection of processing steps that Amazon Elastic MapReduce runs on a specified dataset using a set of Amazon EC2 instances. A Job Flow consists of one or more steps, each of which must complete in sequence successfully, for the Job Flow to finish.

Q: What is a Job Flow Step?

A Job Flow Step is a user-defined unit of processing, mapping roughly to one algorithm that manipulates the data. A step is a Hadoop MapReduce application implemented as a Java jar or a streaming program written in Java, Ruby, Perl, Python, PHP, R, or C++. For example, to count the frequency with which words appear in a document, and output them sorted by the count, the first step would be a MapReduce application which counts the occurrences of each word, and the second step would be a MapReduce application which sorts the output from the first step based on the counts.


Terminology: Single MapReduce Run

When you run a MapReduce application, data files will be read by the Hadoop framework and it will be divided in to say N segments and your map function will be called N times in parallel and at the completion of the map tasks your reduce function will be called. Once the reduce function is finished executing your outputs will be written to the output folder. We shall call this a Single MapReduce Run for the purpose of identification. So if you want to word count a particular log file and lets assume you ran it within a Single MapReduce Run and at the end of it or during the run you received another log message that you want to word count, so you may want to launch another Single MapReduce Run.

For the purpose of the class, a rendering of a given scene using the modified ray tracing library will be a Single MapReduce Run. In this Single MapReduce Run you will split the scene into sections and ray trace these sections/subviews in different Map tasks and you will combine the sections/subviews in the Reduce task and write it to the output. So if you have a second scene to render, it will be another Single MapReduce Run.


Single MapReduce Run –Job Flow Step

The Amazon Job Flow corresponds to a running application in Amazon Elastic MapReduce and could contain one or more Single MapReduce Runs. So the Single MapReduce Run described above correspond to a Job Flow Step in Amazon Elastic Map Reduce. Job Flow and Job Flow Step has somewhat like parent child relationship and its one-to-many.

The Job Flow corresponds to the setup of infrastructure, EC2 reservation and I am guessing for accounting. Within that Job Flow one may run Hadoop MapReduce applications. Each Single MapReduce Run will be a Job Flow Step inside that Job Flow.

Ec2 machine reservations are done at the Job Flow level and once reserved it is fixed for all the Job Flow Steps in that particular Job Flow. This would become much clearer when you get to the API calls.


Launching Elastic MapReduce jobs with programmatically using Java

Amazon provides an API client that enable Amazon Elastic MapReduce users to launch Hadoop MapReduce jobs programmatically. Again I assume by this time you have already launched and tested your application manually using Amazon MapReduce Console. You can download the client from here

Once you download it set it us with your IDE and find the com.amazonaws.elasticmapreduce.samples package. Inside this package you will find the few java files which will allow you to create Job Flows, add Job Flow Steps, Terminate Job Flows and Query Job Flow Status. In this discussion we will focus on first two (RunJobFlowSample.java and AddJobFlowStepsSample.java).

If you open RunJobFlowSample class from the Amazon you may notice its main method is pretty empty but the API that they provide is very easy and you would have to fill in your configurations to the bean objects they have provided and set it to the request. Following is the code to setup Job Flow with a single Job Flow Step. In other words it will setup the Hadoop framework using 11 machines and will launch Single MapReduce Run. You can download the implementation class here. You will obviously have to change the Amazon credential to your own.

Once you launch the Job Flow, you may go to the Amazon console and monitor the status of your Job Flow.



public static void main(String[] args) {


String accessKeyId = "FHJKDFIHKJDF";
String secretAccessKey = "DFJLDFODF/AND/NO/THIS/IS/NOT/MY/ACCESS/KEY";

AmazonElasticMapReduceConfig config = new AmazonElasticMapReduceConfig();
config.setSignatureVersion("0");
// config.set
AmazonElasticMapReduce service = new AmazonElasticMapReduceClient(
accessKeyId, secretAccessKey, config);


RunJobFlowRequest request = new RunJobFlowRequest();
JobFlowInstancesConfig conf = new JobFlowInstancesConfig();
conf.setEc2KeyName("class");
conf.setInstanceCount(11);
conf.setKeepJobFlowAliveWhenNoSteps(true);
conf.setMasterInstanceType("m1.small");
conf.setPlacement(new PlacementType("us-east-1a"));
conf.setSlaveInstanceType("m1.small");

request.setInstances(conf);
request.setLogUri("s3n://b534/logs");

String jobFlowName = "Class-job-flow" + new Date().toString();
jobFlowName = Utils.formatString(jobFlowName);
System.err.println(jobFlowName);

request.setName(jobFlowName);
String stepname = "Step" + System.currentTimeMillis();
List steps = new LinkedList();
StepConfig stepConfig = new StepConfig();
stepConfig.setActionOnFailure("CANCEL_AND_WAIT");
HadoopJarStepConfig jarsetup = new HadoopJarStepConfig();
List arguments = new LinkedList();
arguments.add("s3n://b534/inputs/");
arguments.add("s3n://b534/outputs/"+jobFlowName+"/"+stepname+"/");
jarsetup.setArgs(arguments);
jarsetup.setJar("s3n://b534/Hadoopv400.jar");
jarsetup.setMainClass("edu.indiana.extreme.HadoopRayTracer");
stepConfig.setHadoopJarStep(jarsetup);

stepConfig.setName(stepname);
steps.add(stepConfig);

request.setSteps(steps);

invokeRunJobFlow(service, request);

}




Adding a Job Flow Step to existing Job Flow

Above Job Flow will not shutdown once it finished the execution of its Job Flow Step, you may find the following line which is responsible for that.


conf.setKeepJobFlowAliveWhenNoSteps(true);

Now we will attempt to add another Job Flow Step to the Job Flow we started earlier. This will be another Single MapReduce Run because Job Flow Steps correspond to Single MapReduce Runs. Have a look at the AddJobFlowStepsSample.java class and this class will be used to add a job step to an already running Job Flow. Following is the implemented main method in that class that could be used to add a Job Flow Step to a Job Flow that is already running. In this you will have to set the jobflowID and the jobFlowName apart from the credentials and they would identify the already running Job Flow. Once you run it you can again go to Amazon management Console and monitor the progress. The implemented class could be found here.

This would be useful to reuse already allocated and booted up EC3 resources and launch multiple Single MapReduce Runs one after the another without having to incur setup cost each time. So if you want to word count a second data file or if you are a student in my class if you want to render a second scene, you can use this client to add a new Job Flow Step without having to setup all the machines again and incur the setup cost.



public static void main(String... args) {


//Set these values
String accessKeyId = "FHJKDFIHKJDF";
String secretAccessKey = "DFJLDFODF/YES!/YOU/GUESSED/IT/NO/THIS/IS/NOT/MY/ACCESS/KEY/NEITHER";
String jobflowID = "j-6XL4RL7E5A2";
String jobFlowName = "Class_job_flowSat_Mar_27_23_12_16_EDT_2010";



AmazonElasticMapReduce service = new AmazonElasticMapReduceClient(
accessKeyId, secretAccessKey);
AddJobFlowStepsRequest request = new AddJobFlowStepsRequest();
String stepName = "Step" + System.currentTimeMillis();
System.err.println(stepName);


request.setJobFlowId(jobflowID);


List steps = new LinkedList();
StepConfig stepConfig = new StepConfig();
stepConfig.setActionOnFailure("CANCEL_AND_WAIT");
HadoopJarStepConfig jarsetup = new HadoopJarStepConfig();
List arguments = new LinkedList();
arguments.add("s3n://b534/inputs/");
arguments.add("s3n://b534/outputs/"+jobFlowName +"/"+stepName+"/");
jarsetup.setArgs(arguments);
jarsetup.setJar("s3n://b534/Hadoopv400.jar");
jarsetup.setMainClass("edu.indiana.extreme.HadoopRayTracer");
stepConfig.setHadoopJarStep(jarsetup);

stepConfig.setName(stepName);
steps.add(stepConfig);

request.setSteps(steps);

invokeAddJobFlowSteps(service, request);

}








2009-02-28T16:41:00.000-08:00
Java method level generics - Getting First Element from an Iterator.

There are ample examples where you are given an iterator but you are only interested in the first element of the collection. Following through some code i had to read, which was doing WSDL parsing, I ran into some code which most probably annoyed the programmer because of the repeating code of the same form that had to be written for different Iterator types, to loop through the iterator and extract the first element. One solution, besides writing helper for each case is to not do typing at all and do non generic helper method.


public static Object getFirst(Iterable itr){
    for (Object object : itr) {
         return object;
    }
    throw new RuntimeException("Iterator empty");
}


Obviously this is not why i wrote this blog. I wrote down the following code which is type safe and gives exactly what i want. This makes use of java method level templates. This is type safe because when some one calls this method the templates will be instantiated and the return values are obviously typed based on the instantiation happened at the caller and no type casting necessary.


public static <T extends Object> T getfirst(Iterable<T> vals) {
    for (T val: vals) {
         return val;
    }
    throw new RuntimeException("Iterator empty");
}




2009-02-03T14:54:00.001-08:00
Generic Online web service client

As i ve mentioned many times before Eclipse WTP is cool for many reasons, one of them being the ability to generate a web service client to test a service in an instant.

Lately i came across this online tool to make web service call, and its pretty useful for testing purposes and does save you time. It would get the WSDL (as a http url or otherwise) and would generate a web client which would have the text boxes for the different simple types that would build the complex type.

One client can be found in service-repository  and another at soap-client.


2008-06-17T20:50:00.000-07:00
Whats Up Vegas!!

Last week I attended the TeraGrid conference in Las Vegas, I was presenting a paper there.
Besides the conference proceedings the gambling and the other Vegas activities were pretty interesting. Best attraction for me was the Bellagio Fountains a video of that could be found here, it was amazing.


2008-06-05T08:51:00.000-07:00
Deepal's Axis2 Book

Deepal Jayasinghe has published a book on Axis2 and i believe its the first book published by one of my peers from University of Moratuwa. Job well done!


2008-06-03T22:25:00.000-07:00
Proud of my school

Department of computer science University of Moratuwa, the school i did my undergrads and a place i revere, recently became the highest ranking school in Google Summer of Code acceptance. Well done.


2008-05-06T16:31:00.000-07:00
Browser market share.

I was interested about knowing how the Firefox was doing in their quest "take back the web" and i came across this interesting article. It seems Firefox is eating away IE and numbers seem to add up. I think it would continue to grow, from my personnel experience, i  have introduces Firefox to many, none seem to have gone back to IE. The original work can be found here.





Browser 2007 2008 diff  
IE          74.8%      79.1%          -4%
Firefox     14.6%    17.8%    +3%
Safari      4.5%     5.8%     +1%



2007-01-17T04:56:00.000-08:00
How to accommodate an Out-Only MEP service in Axis2

I have been queried quite a few times by Axis2 users about writing Out-Only MEPed services with Axis2 wsdl2java compiler, so thought of writing this down for future use.

First of all Axis2 does not have first class support for Out-Only MEP, as at now. Main reason being that this MEP is not widely used. Further there is a technique that is stated below that could change Out-Only MEP paradigm in to some kind of isomorphism to IN-Only MEP by switching client and the server.
In technical point of view there are other concerns such as, if a Out-Only is sitting inside Tomcat what would trigger it to send out its message? This trigger cannot be an incoming SOAP message to that service, because if it is then the MEP of the service would change to IN-OUT. So we need some trigger interface to the service implementation to tell it 'ok service now its time to send out your message'. Say we do all that what would be the gain, I would say nothing much. Even though the service reside inside Tomcat it will not gain much from Tomcat scalability because when it is sending out its message it will use commons http to initiate its communication, i.e. it would not use Tomcat's(actually jetty's) features. So might as well keep it outside Tomcat and following is the way to do it.


Method
Say you have the out-only operation named op1( which does not have a input message reference)
WSDL operation would look something like the following:






We  always refer to the MEP with respect to the server's message exchange.

Consider a In-Only MEP, its operation would look like the following.





Now compare the service of Out-Only MEP against the client of the In-Only MEP. They are semantically the same, both send out only one message.

So if you have a WSDL with Out-Only MEP like the following.






Change it to (i.e. change the output message reference to an input message reference)






Now above is a very familiar MEP for Axis2, In-Only MEP. Now using this changed wsdl, instead of code generating for server we code generate for client using wsdl2java compiler.

Now you will get a client that would send out messages when you call/trigger it to the endpoint you define. Functionality sound familiar?? Its same as what Out-Only service would do.

The only flaw that I can think of is that there will be no endpoint where you could run a ?wsdl query and get the WSDL. That would something that you would achieve had this service been deployed inside Tomcat. Its a compromise.




2006-08-08T18:24:00.000-07:00

Eclipse again- UML!!
I was asked of my opinion on a modeling tool by one of the research groups before they jump and purchase rational rose.  I already knew the Eclipse SOA guys have done significant work in this direction. EMF and eclipse UML2 had quite a bit of development in this direction but the I found this product which had everything nicely packaged and of course its free. Its a product called Omondo and worth downloading. The class diagram posted here is done using the tool and it impressed me. It threw exceptions once in a while, oh well I should fix at least one bug before start complaining.


2006-08-02T19:59:00.000-07:00

Niagara!!!

Few days ago I visited my Woden and WSDL Working group collegues at IBM Toronto and Arthur Ryman was so nice to arrage a visit to Niagara on the second day. It was once in a lifetime experiance to withness such a massive mass of water (over half a million gallons per second) falling down over 150 feet. Next time i am gonna go i am sure to be ready to get wet. You don't need to go in the boat ride to get wet, I got wet badly at the top of the fall from the rain like dripping from the moisture generated by the fall. It is an experiance of a lifetime.


2006-07-06T12:31:00.000-07:00
Eclipse Web Tool Platform

I met some of the IBM  guys from Toronto and they wanted me to look at this "other" Eclipse thisng that they are developping. Of course! its opensourse, otherwise no point talking about it. I downloaded and set it up and some of the guys there showed me some of the useful functionalities, and i was quite convinced. It has the some cool xml tools that makes the life of xml speakers like me, bit easier than before.
Here is the location to download it.


2006-03-12T21:50:00.000-08:00
Numbers we use !!!!!!!!

After a mobile communications talk at IU which claimed that Google would index numbers, I wanted to check it myself. Google indeed does index numbers and it lead me to the observation that as the numbers become larger the usage decreases super linearly. Do a google search for some random number like 43538. For this you will get around 200,000 hits. If you do a search for a random 10 digit number, most probably you will not get any hits. The interesting part is for any random number that is smaller than 10 digits you will probably get hits. As the number becomes smaller (in terms of digits)  there will be multiple hits for a given random number and the hit rate will increase super linearly as the number becomes smaller.
Bottom line the internet may represent a sample representation of the number usage of people and most of the time the numbers we use are within the first 10 billion range as I observed. Further the we use big number less often as they get bigger even within the above 10 billion range.
Interesting study to be done in a web mining course.




2006-03-10T12:58:00.000-08:00
WS-Messenger paper 
I was working with my collegue Yi Haung to improve his WS-Notification and WS-Eventing brocker, WS-Messenger, for the past few weeks. This is a publish subscribe framework developped at extreme lab @ IU. A research paperabout this work was published in the ccgrid conference. Yi did most of the work, so great job Yi. Paper can be looked up here.


2006-01-02T18:41:00.000-08:00


 GT4 - WS - Notification behavior under multiple subscriptions.

I tried out the Globus Toolkit lates version (4.0, aka gt4) recently and my interest was with its WSRF and WS-Notification capability. With respect to WS-Notification GT4 container was quite capable of getting a heavy pounding with multiple clients and could in fact deliver notifications without loosing messages up to 90 subscriptions to a particular topic. Such a load was possible when the no two publishings were interleaved or in other word the container was given enough time to deliver to all the subscribers before publishing the next message.
Above graph shows the notification delivery time as the number of subscribers to a given topic increases and the delivery time is linearly proportional to the number of subscribers.
Bottom line from these results is, GT4 Notification can be used for applications that would use less than 100 subscribers for a given topic. This is not a bad outcome, after all many practical applications would fall below this limit.
The SOAP message in concern is a very light weight soap message which has only a simple xsd:string as a input parameter.
SOAP style used is Document and the Use is Literal.
Ran the test on a linux box and the web service calls did not involve network overhead. (ran in localhost)
Notification was done in the form of a value changed event of a WS-Resource.

Browser	2007	2008	diff
IE	74.8%	79.1%	-4%
Firefox	14.6%	17.8%	+3%
Safari	4.5%	5.8%	+1%