English
资源说明：My attempt to cs239 hw2
CS239 Homework 2
May Happen in Parallel Information Analysis
Wenchuan Weng
wenchuan@cs.ucla.edu
---------------------------------------------------------------
0. Guide to code
--------------------
.
├── Main.java
├── Makefile
├── MapReduce.x10
├── mhp
│ ├── MhpAsyncNode.java
│ ├── MhpFinishNode.java
│ ├── MhpFunctionNode.java
│ ├── MhpIfelseNode.java
│ ├── MhpInfoGenerator.java
│ ├── MhpInfo.java
│ ├── MhpLabelNode.java
│ ├── MhpLoopNode.java
│ ├── MhpNode.java
│ ├── MhpSequenceNode.java
│ └── MhpVisitor.java
├── miniX10.jj
├── README
├── Series.x10
├── testall.sh
└── Test.x10
The submitted source files consists of the above files.
0. Main.java
Take in a miniX10 program from standard input.
Calls TreeDumper to print the syntax tree, then calls MhpVisitor to
analysis the program.
1. Makefile
provides several easy to use target
"make run" recompile the program and runs it with Test.x10
"make build" rebuild the entire project
"make clean/realclean" clean the class files / all auto-generated files
2. MapReduce.x10, Series.x10, Test.x10
Three example miniX10 program. I wrote Test.x10 myself, resembles the
example from class.
3. mhp/MhpVisitor.java
A Visitor, all the hard works are in this file.
4. mhp/Mhp*Node.java
These class is my internal representation for miniX10 program, the syntax
resemble that of FeatherWeight X10 (FX10).
5. mhp/MhpInfo*.java
Hierarchical data structure used to represent and calculate M,O,L infos.
1. Tools required
--------------------
0. JTB 1.4.4
Java Tree Builder.
1. Javacc 5.0
Java Compiler Compiler
2. Algorithm description
--------------------
0. General description
I solve the MHP problem in 3 stages.
First, walk the miniX10 syntax tree, generate a dictionary that translate
Integer (statement label) to String (the actual source code); At the same
time, generate another MhpNode tree, only consists of the following
structure: Async, Finish, Loop, Sequence, Label, If-else, Function-call;
Second, Unfold the MhpNode tree. This step is designed to solve the
problem of function calls. With enough unfolding, recursive calls and
very complex calls can be unfold and analyzed correctly.
Third, walk the unfolded MhpNode tree, generate MhpInfo tree. At the same
time reduce the tree into a single node, using the rules discussed on the
class.
1. Stage one: miniX10 ----------> MhpNode forest
The design of MhpNode Tree is based on our discussion in the class, and
FX10. Visitor pattern is used to generate the MhpNode tree. At this step,
each function in every class generate a tree. And this info is tracked by
a dictionary of type Map;
2. Stage two: MhpNode forest ----unfolding---> MhpNode Tree
This is really the tricky part.
After realizing that a function that calls itself behave essentially like
a loop, and loop is essentially like a sequence with the same statements
chained together. A -> B -> C -> A is three functions calls each other
forming a loop, which is a quite nasty situation. And this can be unfolded
4 times in to a long sequence, but the result is the same.
3. Stage Three: MhpNode Tree ----------> MhpInfo
Now with a single tree, reduction using rules become easy. This is done,
again, using Visitor Pattern.
3. How to run this code
--------------------
0. if you have all the tools (JTB, JavaCC, Java)
"make build"
"make"
1. if you are not sure and you are using Debian based distros
"sudo apt-get install sun-java6-jdk jtb javacc"
"make build"
"make"
2. otherwise
I don't know yet. Mail me for further info.
4. What the output means
--------------------
"make"
|--------------MHP---------------
|****T.f
|Async - (L0)
|****T.run
|Seq - (Finish - (Seq - (Async - (L1); FunctionCall - (T.f))); Finish - (Seq - (FunctionCall - (T.f); Async - (L5))))
|****Test.main
|FunctionCall - (T.run)
|------------------
|Expression list:
|L0: a5
|L1: a3
|L2: a4
|L3: a4
|L4: a4
|L5: a4
|------------------
|After Unfold:
|Seq - (Finish - (Seq - (Async - (L1); Async - (L0))); Finish - (Seq - (Async - (L0); Async - (L5))))
|
|-------------MHP Info------------
|{"a3" ,"a5"}
|{"a5" ,"a4"}
Above is a sample output of a run.
After print the original source file;
0. The first part print the MhpNode trees for each functions;
1. The second part print out label and expression correspondence;
2. That's the unfolded the MhpNode tree;
3. The final MHP info.
5. Other words
--------------------
I finished this homework alone, which is quite an experience.
Learned a lot of stuff during the process.
How to handle the function calls really kept me uneasy for several days.
This is a good piece of homework assignment.
Thank you.
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
