Project Log
7/22/06
Started googeling how to get software for a cluster. Came up with beowulf.org right away and decided to try clusterknoppix. Accidentally downloaded regular knoppix, so I played around with that for a while before I went back to trying to find the link to clusterknoppix. Couldn’t find it, so I decided to try parallelknoppix, downloaded that, burned it, ran it, downloaded it to the hard drive. Got another computer together by 10 at night only to find that the network cards weren’t compatible unless they were hooked up to a router. There actually is a router, but it doesn’t have a power supply. Wonder how I managed that? Switched both cards with other computers. Now they’re on the same network but won’t talk to each other. The master node setup is coming up on the slave node. That computer doesn’t recognize it’s hard drive, and the master node needs one, so that’s not working so well.
7/23/06
Figured out that the slave node had to be off when booting the master node. Actually, knoppix just needs the master node to have a hard drive, not be downloaded. So I booted it off the CD (which makes it run like molasses) without the slave node on and it started the setup right. Found this guide that said something about how the key to easy setup was to boot over the network. The slave node is so old that the BIOS doesn’t have that setting. I found out that you need a ROM with some files on it or a floppy and that’ll direct it to boot from the network. So I did that and it’s waiting for a signal form the master node, which is now getting the proper setup but the network card isn’t listed. Not sure if that’s the problem. Anyways, used Windows 95 to re-partition the disc because it was getting confused with the knoppix I had downloaded on the hard drive. Didn’t help much. Maybe if I got the slave node to find its hard drive I could use it to boot the other one over the network, because the current master node has a newer BIOS with that feature built in. I’m still not entirely sure they even know they’re on the same network. I should get two different network cards and a router. That would help for starters, and I’m going to try to get a different software thing too. Parallelknopix isn’t working, even with every help file. I’m thinking about Debian because it seems really popular and has a huge help section. Unfortunately I’m not sure if it’s stand-alone and there’s sooooo many things to download I’m not sure where to start. Tried to find some books, but they were like $120 or $30 used. Crazy. And they might not be all that helpful. So I’m just gonna read some more stuff. Here are some links I accumulated:
http://www-unix.mcs.anl.gov/dbpp/text/node1.html
http://www.beowulf.org/overview/howto.html
http://en.wikipedia.org/wiki/Parallel_computing
http://www.clusterbuilder.org/
http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/beowulf_book/node8.html
http://clusterknoppix.sw.be/download.htm
ftp://mirror.cs.wisc.edu/pub/mirrors/linux/knoppix/
http://www.rocksclusters.org/wordpress/?page_id=3
http://www.clusterresources.com/pages/products/torque-resource-manager.php
http://clusterknoppix.sw.be/knx-install.htm
http://www.knoppix.net/wiki/Knoppix_FAQ
http://instant-grid.de/?q=en/downloadfiles
http://www.pcquest.com/content/pcshootout/2005/105060204.asp
http://157.181.66.70/wmlc/english.html
http://www.irb.hr/en/cir/projects/internal/dcc/00001/
http://sourceforge.net/project/showfiles.php?group_id=33944/
http://www.mosix.org/txt_pub.html
8/15/06
Finally figured out how to download cluster knoppix. Burned it and it ran great- even came with Blender built in! Not sure where the set-up script is, I’ll have to look for that.
8/19/06
Found a manual for clusterknoppix setup:
http://midnightcode.org/papers/How%20To%20-%20Heterogeneous%20Clusters.pdf
8/21/06
I printed out that manual, it suggests using another distribution called Chaos, downloading the –v0.7.iso file while messing with the master node that is still on clusterknoppix. Here’s the link to chaos
http://www.midnightcode.org/projects/chaos/
The cheats it gave me for booting the clusterknoppix node seemed to work, it said ‘default gateway set to [the correct ip address]’ at one point. Now the question is: since it’s a boot-from-cd operating system will it remember the settings? Probably not, but it didn’t take that long so that’s not really a problem.
8/26/06
I wrote this summary of what I’m doing for my science teacher. My title is about 15 words long. I’ve got to fix that.
8/27/06
Burned the copy of what I hope is Chaos, but it doesn’t seem to be a very common version so I’m not sure if it’ll be ok. It’s also a really tiny file for a whole operating system, about 1/6th the size of knoppix, so that’s also really weird.
Ok, I tested it and it didn’t go so well. I noticed that it had all sorts of stuff about how it was meant for security (weird how that would be paired with cluster knoppix because that’s the most unsecure thing ever, but whatever) and it lived up to it. It starts like fedora core and then asks for a username and password. Maybe there’s something that I don’t know about fedora passwords but that seems odd to me.
8/28/06
There’s a wikipedia article on CHAOS. It’s not a stub either- it’s really long. Apparently it’s not as forsaken a version as I thought.
9/3/06
The passwords for CHAOS haven’t shown up, and I tried the obvious things like root. So apparently I’d have to download another version or something, but it’s just not working for me.
I’m ditching the whole idea of getting a Linux distribution to experiment with. I’m just writing my program from scratch. I’m thinking about factoring lots of large numbers because the communication between computers would be minimal and therefore easy to debug.
I noticed something sorta funny about all the web sites for Linux clusters. The latest update dates seem to range from 2002 to 2004- there’s noting recent and nothing before 2000. I asked around and one hypothesis is that sometimes everything on a topic will be written efficiently over just a few years of development and after that there’s not much more to do because all the bugs have been caught.
9/9/06
I had to do 11 hours of choir today and yesterday, so I sent dad to go bid on some computers for my cluster. I was told that he got me 7, but he came home with $150 dollars worth: 24 computers, a box of cables, a box of keyboards, a router, two printers, and some speakers.
9/10/06
I went through most of the computers today. There’s a couple that have so few parts or such a different setup I can’t turn them on, a couple of them have broken power supplies. Most of them came from the national lab so the hard drives are missing. I think there’s three hard drives total. All the other ones I’m considering using for a knoppix based cluster so I don’t have to have hard drives.
There may be a source of hard
dives, like you can get them at goodwill for a couple of dollars. I think about
half of them work right now (for knoppix) and another quarter I can swap parts
for. Yay!!!! I’ll probably have over 16 computers when I’m done!!!! And I got a
Xeon, even tough it doesn’t have memory and it takes a different kind then we
have right now I looked up the product code on the internet and it’s supposed
to be a 2 ghz! And Xeons are really cool for other reasons- like how much stuff
it has in it. Still don’t know if it works, but it was only $5 and they usually
go for hundreds. Fishy but cool. Dad thinks that someone just forgot to bid on
it. Basically I opened the computers up all the computers 
and
tried to turn them on. Them I gave them a quick clean job with the air pump. A
lot of them needed it, there was one that looked like it had been out in the
rain and this A Open had cobwebs in it and 32 mb of memory. There were a couple
that were really from the dark ages, the other ones that don’t work just don’t
have enough parts. Overall I think I have more computers than I’ll ever want to
fix and definitely enough for a cluster.
Chart of computers and their parts 24compsInspection.xls
9/12/06
I’ve continued re-fitting the computers. There are four computers that I should be able to get to run with little trouble:
4156, dell, 1.1 Ghz, 384 mb, no hard drive. It’s loading windows off a dell re-install disk now, I gave it a hard drive.
4231, Gateway, 1000 mhz, 384 mb, network card, rage 128 graphics board, hard drive. That ran right away.
4973, dell, 1 ghz, 256 mb, no hard drive. This one will require a hard drive, but it’s the fastest (other than the first two and one with a broken power supply).
5143, dell, 933 mhz, no hard drive. Same situation as 4973.
These are the computers that are fastest and only have the hard drive missing. There are several other dells that also have memory missing, and they really don’t need much of that and we have a few sticks laying around the house so it shouldn’t be a problem. I definitely think I can get these computers to work.
9/16/06
I got two hard drives at Goodwill for $10 each, which is more than they used to be. It’s also more than the computers were, which is really bugging me because I was trying to be cheap. Oh well. I got 5143 to work on Windows 2000. 4973 had a faulty cd drive, which is easy to replace, but since there was only one windows re-load disc there wasn’t a point to getting it fixed until 5143 had loaded.
I’ve been thinking about just using knoppix for everything because then I wouldn’t have to have harddrives. However, knoppix will eventually run slower for that very reason. I’m also leaning toward writing my code from scratch, which would be easier to do on windows because I’m more familiar with the networking.
9/17/06
All four of the new (ok, so old) computers I fixed up are running one version of Windows or another. I swapped the CD drive with another computer and it works. With the two I originally have there’s 6 for my cluster.
9/18/06
Found something called MPICH. It’s a C++ library that allows you to network nicely. Apparently it just lets you call computers on a network by number and bypass IP addresses etc. Looks perfect for starting my program. Just like all the other things dealing with cluster computing, the latest update date is in 2003.
Starting work on 4153 and 4155. Slightly slower dells, no hard drive, pretty much the same as the other four.
9/19/06
I got to be on KOB TV today to promote science fair this year. There was this really nice guy who gave me four hard drives!!!! There was one that was 4.2 and three that were 4.3 gb. Here’s his name:
Michael Vaughn, IS Administrator
505-243-4411 email: mvaughn@kobtv.com
9/20/06
I got mail from a teacher wondering how many more hard drives I might need. My email back:
“Right now I have:
* 6 computers with hard drives installed
* 6 hard drives with computers selected to put them in
* and from 3-6 more computers that are currently hard drive-less. There are actually 12 more hard drive-less computers but I won't be using all of them because they're missing parts or they're too slow. I'll be combining the last computers.
I don't know if I'll actually need any more hard drives. With just the ones I have right now there will be 12 computers. I don't know if I'll need any more for the experiments I'm planning on at the moment. More computers could change the purpose of the project to dealing with lots of nodes, which isn't as interesting as what I'm planning. So maybe more would be nice, maybe not. I don't know yet.
Thanks Again,
-Erika”
9/23/06
The new hard drives seem readable. I have installed one of them; it even has a copy of Windows 98 on it! Of course, being Microsoft, it spent an hour looking for drivers before I finally put it out if it’s misery. I’ll be re-partitioning the disc and re-installing the operating system.
9/24/06
I
set up a power strip with four computer, two monitors, three keyboards/mice,
and a router. I’m using one of the routers with 24 slots that I got at the
auction. I’ve been able to get the computer’s IP addresses set, I’m starting at
192.168.0.205. From now on when I’ll refer to computers by the last three
digits of their IP address, or if they don’t have one yet then just their
number form the auction like I’ve been doing. 206 had Windows NT on it, so I
had to re-load that just for consistency and convenience. One of the computers
I tried didn’t have a network card in it, so I had to get that taken care of.
Then I had to install a driver for both the video card and the network card,
and now it works fine. I have all the computers on one power strip right now,
so when I want to reboot I can just switch it on and off all at once! It’s
really cool to hear seven fans stop all at once! Currently there’s three on the network that
are set up to share files and one that needs some drivers.
9/26/06
MPICH comes in a million different pieces, all of which needed to be unzipped, unpacked in various ways, put into the right folders and installed over each other. I think I got about half of the pieces and half of them unzipped before I became completely confused.
So I just wrote my own program. It actually wasn’t so bad. I loaded winsock.h, it’s a library for network commands. It does the same kinds of stuff MPICH does just not as directly. I got it to access site bob through several steps:
Oh, and Bob is just my name for the website I enter at startup so it’s not hard-coded. I just used bob because I really wanted to name the project bob for some strange reason, but I resisted and named it boring old cluster. Blah. But boring cluster can access cool bob, so it’s ok.
Gethostbyname- takes the name of the site and asks all the other computers it knows if they know it’s IP address. This changes the name into IP.
Socket- assigns a socket for the connection. This is not just for the internet, like USB ports have socket values too. Apparently you just have to know what takes a socket.
sockaddr_in- establishes a link through the IP address given and the socket.
And my favorite part is:
si.sin_addr.S_un.S_un_b.s_b1=a0;
si.sin_addr.S_un.S_un_b.s_b2=a1;
si.sin_addr.S_un.S_un_b.s_b3=a2;
si.sin_addr.S_un.S_un_b.s_b4=a3;
which just uses the awesome network command to retrieve the four parts of an IP address. Like in 192.168.0.1 a0= 192 a1=168 a2=0 and a3=1
and you can print them out like this:
printf ("%d.%d.%d.%d", a0, a1, a2, a3);
and it’s a totally obvious part of the code, but I really like it because I’ve never seen these system commands before and it’s cool to see how it works. I even learned that the people in Gulliver’s travels that had a war over weather to crack their hard-boiled eggs on the big side or the little side wormed their way into programming lingo. Some computers transmit the larger bits first and the smaller bits second and other computers do it vice versa. I had to call a function that checks weather it needs to swap it at some point. It’s called big-endian or little-endian. Here’s the page that Dany Cohen wrote about it: http://www.rdrop.com/~cary/html/endian_faq.html#danny_cohen called ON HOLY WARS AND A PLEA FOR PEACE
This is
an attempt to stop a war. I hope it is not too late and that
somehow, magically perhaps,
peace will prevail again.
The latecomers into the arena
believe that the issue is: "What
is the
proper byte order in messages?".
And people say nerds don’t have a sense of humor.
9/30/06
I spent a few hours moving the four computers I has setup to the attic, which I
hope will be the permanent home of the cluster. Now only two of the computers
work. I also hooked up my laptop to the network, which is vastly more powerful
than any of the computers and also has the program on it. Currently there are
five computers plugged in, two working, and another two that should work but
probably don’t. grrrr….
10/1/06
Ok, here’s a quick report on my cluster:
205- working
206- no networking driver, I’ve tried everything, including installing windows again
207- says ‘network cable disconnected!?’ Maybe I should re-install…?
208- working
209- working
210- working (especially after I turned the router back on in the morning- duh)
10/04/06
Here’s a brief bibliography so far:
· Xavier, C. and Iyengar S, Introduction to Parallel Algorithms, Wiley & Sons Inc, 1998
· Almasi George and Gottlieb, Allan. Highly parallel computing, Redwood City, Calif., Ben-jamin/Cummings Publ. Comp.,., 1989.
· Wikipedia, (no date given), Parallel Computing, 10/4/06, from: http://en.wikipedia.org/wiki/Parallel_computing
· openMosix, 05/21/06, opeanMoisx, and Open Source Linux Cluster Project, 10/4/06, from: http://openmosix.sourceforge.net/
· Tannenbaum T., A Computation Management Agent for Multi-Institutional Grids, Netherlands, Kluwer Academic Publishers, 2002.
10/5/06
Ok, I got another computer to work, another one that seemed to have a faulty CD drive. I replaced it and loaded 2000, works great first time- even could network without any wait! I brought up two more and started working on the Dell, it’s loaded and recognizes the network. The other one was a Gateway, which normally I would go at with a screwdriver to see what needed to be done but it wouldn’t do any good. Weird as it may sound I couldn’t even boot it because there are so many computers lined up right now that the monitor cable wouldn’t reach! That may be a cue for me to stop adding nodes.
205,
208, 209, 210, 211, 212- working +my laptop (so 6 nodes and a master.)
206- no networking driver
207- says ‘network cable disconnected!?’
10/7/06
Beaucoup Program Progress! I ditched the gethostbyname function and now it communicates with a computer in the attic! First I copied the code I had twice, once for ‘node0’- the sending node, and once for ‘node1’- the receiving node. There were some extra commands I set for the receiver like these ‘bind’ and ‘listen’ functions. I now have the sending node send every five seconds and say ‘blew it’ if it doesn’t get a connection. I can initialize the nodes in either order and they’ll communicate. It’s really cool! I get the sending node to send “Hello node1, this is node 0” Originally clusterlaptop was the sender, but I’ve switched it around and it still works even with the code remotely accessed from over the shared network! This is totally awesome!!!!!
Here’s a picture of command prompt (reversed the colors or I’d get fined for
excessive ink use). Note: node0 just stops saying ‘blew it’ when it establishes
a signal- it doesn’t get a message from node1.
10/14/06
I looked through the computers that were less than 800 mhz and pulled the parts. Took the rest upstairs. Got batteries, any memory that was still there, graphics cards, and windows license numbers. There are 12 computers that are now ready for the trash and the Xeon that still needs memory. I have 7 from the auction on my cluster, two don’t work. There is a gateway upstairs that I haven’t added yet and another gateway that my dad took. Overall, I got 9 high-end computers out of 24 (3/8!), plus lots of extra cards, memory, and batteries. Aboot $16 for each >=800mhz computer, plus all the other stuff (like printers)!
10/23/06
Ok, more mucho program magic (ha ha- a pun you’ll get in a minute.) I had the master node not only ‘greet’ node 1, but also send it commands. In turn, node1 listens for the commands and executes that particular command. Also made some subroutines (SendMessage and ReadMessage) because they get repeated so many times and entered the last three digits of the receiving node’s IP address in one place. Here’s the command prompt on the master node for commands ABRACADABRA! (this is the magic part. har har.)
11/4/06
Modifications so that the master can send commands to multiple nodes. It even works! (harder than it sounded.)
11/12/06
I’m trying to come up with how to proceed from here. I think I’ve got it.
I need what’s called a parser- a piece of code that breaks down another piece of code into basic grammar. Hopefully, I’ll finish this step with something that takes the code and puts it into a directional flow chart: variables modify each other within structures like loops, if statements, and subroutines. Each time a variable is changed the program will show what variables went into changing it and when it happens in the overall program structure.
So far I’ve come up with one two a few languages that will probably be good for this: yacc (yet another compiler compiler), bison (who stole their name from yacc), and Lex (lexical analyzer- rather boring name.) Each of these are languages specifically designed to parse programs, and yacc seems to be the most suited for my purpose. In yacc, you define the grammar of the language and then give it ‘snippets’ of the program you want it to parse, it then recognizes where the grammar is used in the snippets and tells you.
Some helpful links:
http://en.wikipedia.org/wiki/Yacc the ever essential wikipedia article
http://en.wikipedia.org/wiki/Flex_lexical_analyser
http://dinosaur.compilertools.net/#books original web sight for yacc (I think)
http://dinosaur.compilertools.net/yacc/index.html detailed explanation of how yacc works
http://dinosaur.compilertools.net/bison/index.html same for bison
http://cs.uic.edu/~spopuri/cparser.html helpful-looking bison page
Apparently yacc “Find[s] the hierarchical structure of the program.” That would be what I want.
There are several books that look helpful, but they’re all hundreds of dollars and they’re textbooks, so I think I’ll be sticking with the internet sources.
11/18/06
I downloaded some code examples off the internet and ran a bison program.
http://cs.wwc.edu/~aabyan/464/Book/YaccBison.html
It’s a program that takes a math equation (like when you enter “2 3 +” it means “2+3”), parses it, and performs the action specified.
The problem is that it doesn’t display the parse tree, and there isn’t a very convenient way of getting it to. The current grammar rules are for simple math, not another program. However, I made considerable progress in understanding how it works. Here’s the rundown:
The main program, bison.exe, takes a file you write about the grammar (calc.y) and another file bison.simple (makes state transitions) and converts them into another program. This program (calc_tab.c) describes all the conditions the parser can encounter, how to parse the input, and if there are other functions needed to be performed when it sees something. It’s kind of like a ‘choose your own adventure’ book- you read a page, decide if you want to open the trapdoor or climb up the ladder, and flip to the next appropriate page. Some steps cause you to die, similar to a action associated with parse functions or error messages. When you get to the next page, you read it (like the lookahead function that takes new imput) and decide again.
This all makes it very inconvenient to run on windows because the copy of visual c++ I have doesn’t automatically update the actual file that gets run. First you have to save calc.y (the file with the grammar rules.) Then you run bison.exe to create the new file. Finally you go to calc_tab.c and run that. It would all be a lot easier on linux because all this was originally developed on it, but I can tell that if I switch now I’ll have a parser on linux and a cluster on windows.
I’ve been slowly making progress typing up my research and assembling my report. It’s hard to decide how much detail is necessary.
11/22/06
I took the sample code I got off of http://cs.wwc.edu/~aabyan/464/Book/YaccBison.html and modified it so that instead of taking the input from command prompt it gets each character from a file. Now I have “2 3 +” in a file, it will read it, and execute the statement. This is the first step toward making it into a general program parser. Now I have to write the grammar rules (C syntax) and modify the output structure into a parse tree format, or whatever else will be most convenient for the program separator.
Here’s the bookmarks I acquired after a ton of googeling:
http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elsa/index.html
http://directory.google.com/Top/Computers/Programming/Compilers/Lexer_and_Parser_Generators/
http://3d2f.com/programs/11-349-parser-generator-download.shtml
http://yaccman.com/papers/YPP.html
http://www.antlr.org/article/parse.trees/index.tml
http://www.cplusplus.com/ref/cstdio/fopen.html
I was trying to see if anyone had a general code parser for C. Apparently not, although I did find one person who categorized it as one of his ‘unfinished long-term projects.’
I got out my first C book and I’m using it for all the syntax rules. It has a really nice index that should be super helpful.
I had momentary issues with the fact that windows uses \r for newlines, instead of the obvious \n. It works now.
Yay! I got it to ‘parse main function.’ Coolness! So basically it just read the word ‘m’ ‘a’ ‘i’ ‘n’ and then printed ‘parsed main function.’ Fun.
I put in the first parts of c grammar: expressions and primaries.
11/23/06
Bison is one of the most insulting compilers! It will tell you your code is ‘useless.’ “1 useless nonterminal and 1 useless rule” it actually said that! How very rude.
Here’s a list of stuff I can get it to parse, I’m putting it here so I know exactly what it gives me parse errors on: (p is an identifier)
1; 2.3; p; *p; (p); p[p]; p[(*p)];
While I was looking for some papers on how to fix left and right associtivity, I found a general c parser. It’s from http://isthe.com/chongo/tech/comp/c/index.html and runs on yacc and lex.
I downloaded it (lex, yacc, and copied the files into it) and got rid of some errors. They were mostly form differences between windows and unix.
It kinda stinks that I don’t get to write my own parser. Darn. But there’s no point not using this one and there’s plenty more to do.
http://www.lysator.liu.se/c/ANSI-C-grammar-y.html#external-declaration specifically, the c rules
http://www.lysator.liu.se/c/ANSI-C-grammar-l.html the Lex token part
When you run it, it will repeat back at you whatever you type in except when there’s an error. Currently a c program that compiles with no errors will be accepted by the parser, but it hasn’t been programmed to do anything with it yet.
11/24/06
It’s so freaking hard to write this report! Never before have I had so many programs! Here’s an example of a footnote:
The ‘program’ will from now on refer to the process developed for this
project of automatically separating and running code in parallel on a cluster.
The ‘code’ will refer to the algorithm that this project is attempting to
separate and run in parallel. The ‘program’ will run the ‘code.’
I had “Confused? You better be!” at the end for a while before I figured out what I was talking about and took it out.
The problem is that at the end of the project I should have three programs, which I have decided to call the C.C., the P.P., and the F.S. (It seems like the time for a hilarious sentence to go with that… nothing comes to mind…) Plus I’ll have the the program that all this will be operating on, oops, er rather, the code. The F.S. will probably turn into a lot of separate programs, so that will make things reeeeeeally hard to write. I’m already confuzzeled.
I decided to move the research section between the introduction to my experiment and the explanation of my experiment. I’m sure my old English teacher is rolling over in her grave, even though it was actually my science teacher who taught me how to write technical reports and she’s still alive, but whatever. She likes the research after the experiment. I’m sure she also likes the experiment all in one place too, but there’s no way that’s gonna happen. It actually makes life a ton easier for me because now I can define terms in the research section so I don’t have to try to summarize complex concepts into little sentences that just confuse everyone and make the paragraphs long and off-topic. The experiment section can now be about how I did stuff without interruptions. It’s a ton better already!
Oh, I also have a ‘appendix!’ Very exciting. All except that it’ll probably end up in another binder entirely- a big binder- because it’ll have copies of all the code in it and also a copy of the project log (this). Cool name, huh?
12/25/06
I started figuring out how to get the parse tree to track variables. Each chunk of the program has its own variables that will be tagged with number/name/place and associated with the eventual parse tree. There are interesting situations involving read/right rights to a variable, and these can be used to arrange the parse tree in terms of flow- the variables needed for one calculations will be formed before they are used. Variables that are defined or constant and are only read by all functions are ignored, while the variables that are passed between different parts of the program, especially in the read right read right pattern, are focused on for parallelization because they will be the ones crucial to a optimal parallelization.
For some reason the program I had running now crashes my computer, something about how it’s formatted I think. I’m trying to fix it, I also put it in version control.
12/26/06
After a morning of intense re-formatting I finally switched over my hard drive and re-installed everything. I can now debug! YAY!
More thought about how to attack my problem: The parser starts from bottom up- first recognizing and parsing integers and declarations before moving onto higher structure that these make up. That’s not what I need for a full-blown parse tree- one that starts with the largest structures and displays what makes them up. I also need to track the variables as the move through the program modifying eachother, but the parser recognizes each variable by kind, not name, meaning that the integer 3 is the same as the integer 3984. Fortunately, I googled how to find the semantic value, or original character string, of each token: you do a combination of several commands, the main one being yylval(). My next step is figuring out how to explain to the parser which variables are the same, especially inside a structure. Well, first I’m going to read 60 pages worth of manual I got off the internet. Here’s some sites:
http://www.monmouth.com/~wstreett/lex-yacc/bison.html
http://www.tldp.org/HOWTO/Lex-YACC-HOWTO-6.html
http://www.gnu.org/software/flex/manual/html_mono/flex.html
12/27/06
Stupid yacc/bison/flex/lex is sooo annoying! It’s impossible to define anything because everything is imported into a different program where it’s re-written and dumped into another file just to be mushed around by yet another program and finally run. Everything is defined like a MILLION times and just to figure out what yylval was I had to go chase a ton of other declarations around which got me NOWHERE! It’s very irritating.
However, after a lot of annoyance and a ton of online manuals, I got something working. I have the beginning of a node structure for the parse tree, it’s where each block of code is separated into nodes, which is made up of nodes, and so on. Currently, I have a system that prints out the structure of basic statements in terms of a node structure, incorporated with both the semantic value of the variables that went into it and also the operator that was performed. When given the grammatically correct statement “int i= 5+4-3*2%9;” it prints:
Showing
the structure with tabs based on the left and right nodes of the input.
The big difference between this and what it was doing before is that it says what originally made up the statement: the number (5). This is significant because normally a parser wants to forget what the original semantic value was in favor or a general token.
I’m a little worried about some odd error messages I’ve been getting when I compile bisony.y. It spews out about 80 complaints about how everything I use had no ‘declared type.’ I don’t think it’s fatal though, especially because it doesn’t seem to effect how my program works, it’s probably one of those weird things about yacc.
12/28/06
My mom is the one who generally rehearses what I’ll say to the judges and helps me figure out how to display my project so everyone knows what I’m talking about. I ran my project by her and she said I don’t have enough pictures and I’ll never get it done anyway. So, I’ve re-defined my project so it’s graphic, manageable, and explainable.
I’m going to manually parallelize a fractal program and run it on my cluster. If I have time later I’ll do a general parallilization but with a subset of the C language.
It’s really disappointing that I’m not doing automatic paralilization right now, but it’s what has to be done.
I’ve looked into programs that will allow me to do fractals. I think I’ll right my own because I’ll be in charge of the grammar and it’ll make everything easier. I got a couple programs off the internet and ran them, but they don’t have a graphical interface, just numbers or symbols. I figured out the basic way of doing the complex number equation while avoiding I entirely (no kidding!) and I can write something pretty short for it. It’ll give slave nodes a region to calculate and report the speed of divergence or in set to the master node who will write a bitmap out of the information.
I
have a fractal program I wrote after looking at several other c programs and
reading the wikipedia article. Took a ton of time to realize I deleted the y*y
statement and had an if instead of a while, but it does print out little hashes
for points outside the set. The printout is a little distorted by the font, but
I’ll modify it, hopefully by the end of today. The entire thing’s so small the
program and the picture all fit in one screenfull!
Here
were some helpful sites:
http://en.wikipedia.org/wiki/Mandelbrot_set
http://pheno.physik.uni-freiburg.de/~andrea/Fractals.html
http://www.cygnus-software.com/theory/theory.htm
Now for adjusting it for bitmaps…
12/29/06
I modified my fractal program so it’s all one function that takes fractal (double LEFT, double RIGHT, double TOP, double BOTTOM, int numcols, int numrows, int maxsteps). Not it’ll be much easier once I want to dump it into my compiler program because it’ll recognize the ‘fractal’ part and then take the arguments. It writes the points to a file in terms of their position in the array and the number of iterations they took. I think when I put it into the cluster program it’ll just save the file and then I’ll make another thinggy to print it.
Here’s basically what it looks like, the colors got a little messed up.
I
started putting the fractal code into the cluster program. I think it’ll work
if I make it a command that the nodes can access. I’m not sure yet exactly how
I’ll get the master node to sort out which slave node is which, but it’ll work
out eventually.
Aaaand now… for the better program!
I got the two to merge! The master node sends the slave node an entire structure, comprising the command, the parameters for the fractal calculation, the fractal array (empty at this point), and some data space. The node calls the fractal calculation function and sends back the completed array and displays the fractal in command prompt with stars and spaces. The master node then checks which data is form which part of the image and reassembles the pictures.
This
process is separated into different parts because the left half is calculated
by one node and the other does the right half.
I’d like to try to make the algorithm zoom in on a smaller section and add more than two slave nodes to the process.
12/30/06
I got the original cluster networking program to work for three nodes by modifying some loops and using the variable numberofnodes. Now I need to do the same thing for the fractal program, which should be slightly harder because I’ll have to cut the picture into more pieces.
I spent a really long time connecting this Switch gizmo. It runs extension cables from the computers to the switch which then lets you connect one monitor, keyboard, and mouse for all the computers that are connected. The only problem is that there are only four cables, but there’s only three computers that work to my satisfaction anyway, so it’s ok. I’d still like more cables because it’s extremely convenient. Took forever to setup because I had to re-wire everything, but it’s soo much cleaner now.
The fractal program works with three nodes, although it’s rather difficult to separate the picture into three parts. The image display code I’m using wasn’t designed for large images, so the ones that I’m currently using are about 20x20. I got them up to 300 last night, but that was just with two nodes, and I’ll have to figure something out for that. The point is that it’s calculating it, so I’m happy. I’d still like a better color scheme, the pink was kinda accidental, I was trying for purple and it didn’t work out. It also doesn’t have the cool color for the edges, I’m going to try to fix that now.
OK! WOWOWOW! IT’S WORKING!!!
It even took a loooong time to calculate! Exciting!
1/2/07
Stupid little sockets are doing everything possible to stop me from modifying my program to zoom in. There’s this function called ISMAP that allows you to click on an image and return the coordinates you clicked on. My problem is that there are three images and the parameters for each are kinda hard-coded, and the stupid thing will either completely exit or hang when I want it to display the fractal image but not sever the node connection. It’s calling itself all wrong. So annoying.
Ok, so I now have a master2 function and a master2run function, one of which initializes stuff and is outside the loop that calls the webpage, so it only does it once. I have all the new parameters set and it should work but when I look at the picture it’s flipped upside-down and kinda distorted. I’ve checked my calculations and they’re right! Even when I track the variables while debugging the top is positive and the bottom is negative, so I can’t see why it’s flipped.
Oh, and I wrote some of my report today. It was sad, I had to write a kinda obituary section for automatic parallelization. It’s not totally dead, just for science fair and only for right now. Later I’ll bring it back. It will be RESERRECTED!
1/3/07
The problem is officially FOUND!
It was a problem with how you counted, as in where the origin was. The browser counts from the upper-left corner, while the fractal function was counting from the lower right, and the equation was in real coordinates (somewhere in-between). So I can now zoom and it won’t flip upside down, so off in a random direction, or distort itself! Yay!
Wow, there is a serious coolness factor going on with it zooming in on the right place… I changed it so it was passing a smaller array around, which sped it up considerably, and now I’m modifying it to not pass an empty array from the master to the slave but just… ok here:
The master sends the slave m1 (talk about descriptive variable names) which contains LEFT RIGHT TOP BOTTOM maxsteps and this weird little data thing that doesn’t do anything anymore (kinda like the appendix). Actually I’m not sure if it doesn’t do anything, I know it used to, and it may complain at me and give me errors if I take it out right now, so it’s being left in for the moment. So only then does the slave construct the fractaldata structure (m2) it needs to call the function fractal. Fractal uses this and fills it with an array of numbers between 0 and 254 that describe the color it should be. Then the slave sends only this small array back to the master who then displays it.
At least that’s what it’s supposed to do, right now it hangs when you refresh the browser.
1/4/07
I got it to pass a different array, after some problems about not passing back the information it needed to decide which picture it is. It’s all fixed now, I also added a timer and it takes from 0.5 to 3.7 seconds to calculate, depending on how much black there is.
1/5/07
I started assembling my binder today, which has a ton of stuff in it- report, results, and references… code. That kind of thing.
1/15/07
It was a long weekend and I was wondering why I was all relaxed yesterday and I realized it’s because I totally forgot to do my board and school fair is in, uh, not very long! So I edited my report more and went to go get a board and stuff. Then I came home and decided to go modify the code (yes again!) to weight the stupid calculation between processors. Unfortunately they’re a MILLION problemos!
· the computers don’t process directly proportional to their speed. I have a 933, 1000, and 1000 mhz and it’s more like 6:11:16 than 9:10:10 must do with network speeds, but those are harder to just find out. There isn’t a prettyful mycomputer/preferences to click on! Waaa! So I just guessed… not that I could run it anyway… getting into the next 999,999 issues…
· The entire setup is designed for a data structure that contains an image array. Unfortunately, the image array is determined by NUMCOLS and NUMROWS, and since I’m going with the idea about weighting according to how much of the image they calculate all the dimensions have to be different. Although it just occurred to me that numcols will be the same no matter what, but still. I make three copies of each structure.
· Then I have to change everything that takes the structure as a parameter. So now the fractal command (which has three now: fractaldata2A, B, or C now) to change the number of pixels it calculates with NUMCOLS1, 2, or 3. Same with numrows.
· …..and modify every read and send function (all now taking A, B, or C.) It’s gross and painful!
Amazingly, the first time I ran it after getting 130 or so bugs out it kinda worked! Well, the entire right third of the picture doesn’t work at all, I don’t think it’s sending properly or something, because it’s just black with random colors in it and takes 0.010 or 0.000 seconds to calculate. But aside from that it successfully communicated all the commands and stuff, so that’s good! The other two pictures aren’t garbled either (mostly, I think, anyways)! Amazing.
Still need to get the bugs out, but still.
AHHH! The code that deals with C are exactly the same as the other ones!!!
1/17/07
Yay! I figured out the problem!
First, I was counting nodes 0,1,2 in one place and 1,2,3 when I called it so the third one was getting confused. Then I was setting the arrays to their default values wrong: since the images had different sizes it was writing into some other (and apparently important) memory. It works!
And it works well too! I weighted the nodes about 23:11:9, and it works really well! I doubled the size- from 600x600 to 1200x1200, and it only took about 1.5 more seconds! The pictures are really high-res too!
1/22/07
I’ve been working for like a week on the board, and I finally have it the way I like it. Now I just have a TON of printing to do!
3/2/07
I’m BACK!
Yeah, I’ve been working on supercomputing in great leaps and bounds for the last couple months and I’m going to run all the stuff I wrote on my cluster! MUAHAHAHA! I have a program that can simulate a rocket whipping around the moon and hitting mars, and I went to a lot of trouble to get it into a nice little function. In a separate file even! So now I’m trying to get the stupid cluster to calculate it but the silly thing is overflowing the stack because I’m writing an 800x800 array of integers just for the heck of it. Ok, so actually I need it, but it should be static or something. Trying to work out bug #1.
3/4/07
I debugged a lot over the last couple days. It now gets all the way through the calculation but doesn’t send back the data correctly. Probably because there’s too much of it. At least it’s talking to itself now!
3/7/07
Ok- I’ve been working the last few days and I chased down all the little bugs in adapting the orbits program to the cluster. If I had it to do over again it would be a lot faster- there’s definitely a method to adding a function.
So, when I started out I had the function in a separate file along with some function declarations, important definitions, etc. In the process I cleaned up all my send a read functions: instead of 18 total I’m now back to 2! Here’s a list of bugs I ran into:
· Running the old version of the cluster program on the nodes and the new version (in a totally different directory) on the master node. And NO I’m not that dumb- it was just confusing!
· Having the browser call the orbits function alone without going through the master because the remnants of that program were still in there.
· Making the fractal structure the right size so it didn’t have a cow over memory violations. This was a problem because the fractaldstruct had an array that only needed to have a number between 0 and 265 but the orbits has to have one that can carry RG and B.
· Making the picture the right size. At first I was dumping it into fractaldata1, but then that wasn’t the whole picture because I’d broken it up for the nodes, so I finally (after much futzing around) just went and added an additional 7 full-sized pictures.
To make a long story short, if I ever run into the need to add another program (which I hopefully will!) I’ll have a procedure that will hopefully make it easier. The program is dynamic now, as in it’s not particular about what it’s transmitting, and that will help a lot. I’ll also know to not try to modify existing structures but instead just make similar structure. Not copies. And more pictures! ;)
Now I’m trying to do something I never in my wildest dreams would have attempted: get the silly little probe to PLUTO- not just mars. Pluto is… far… away. Very far. So it takes a heck of a long time to get there. But with my amazing and wonderful cluster it won’t! Hopefully by next Friday! ;)
3/8/07
I’m this close to hitting Jupiter! Something scary happened too, but it all turned out ok! I noticed that when I started having it calculate for four years one node would finish and it would display. I would compile and it wouldn’t let me because the other nodes were still running! What happened was that I copied and pasted one of the fractal functions that was dependent on which node it was coming from. I fixed it so that they all report back before it displays, but I’m glad I noticed. Whew!
3/11/07
It’s pretty much at Pluto, the problem being that Pluto’s just so small. Grrr. I also have to run it for about 17 years generally to get them that far out in the solar system. It’s pretty cool though. Pluto’s orbit is about where Mars’ was when I was trying to get there. Pretty exciting!
3/12/07
I found out what was wrong with the picture!!!!! In the .h file it took two copies of orbitdataO6 rather than one of those and one with O7! This is why I had earth orbiting pluto… really worried me there for a minute… I’m timing it now- it started at 6:06 and ended at 6:51. Started 7:10 ended 8:00.
So it takes 50 minutes. Great. 8:04 to 8:57. 8:59- yeah, haven’t even been keeping track. I made flow charts for all the programs and I made comparison chart for the communication/ calculation requirements of the programs.
3/14/07 (pi day!!! Whoo!)
Now that I got the circle bug out I have absolutely amazing results! I’m charting the time the cluster takes (also each node) against the laptop alone. It almost seems linear! AHH! COOOOL! I almost fell out of my chair. When I graphed the total time in comparison to the nodes it was sooo cool! As you have more calculations the nodes’ times start to diverge!!! THAT’S SOO COOL! Exactly what you’d expect, of course, but it’s really interesting to have data to prove that it actually happens. The time speedup is amazing too- it’s sooo exciting!
3/17/07
Amazing what happens in three days! I got to internationals!!! W00t! Now I think I’m going to do a program that has more complex networking requirements.
5/4/07
So obviously I actually have been working, it just hasn’t gotten written up. I’ve done all the presentation work for regionals and state, as well as finishing my other project, and so now all I have to worry about is internationals and finals. all. haha.
I got some really good comments from the judges at both fairs. There were three main areas they commented on. They were confused about my research because it’s when I wrote my own program it didn’t get incorporated into the talk much and they don’t have the opportunity to read the report. I’m going to fix this by branching out and putting papers in stacks on my board. So they can see the miles of references, raw data, etc. I’m going to separate all the research, code, report, etc. into different folders, I think one binder was too clunky. There were also two other questions: “how many nodes could you add?” and “what do you do about inter-calculation node-to-node communication?” I’m going to address both of these.
Last week I programmed up a ‘game of life’ sim to run on the master node. I’m going to use this to figure out how to separate a cellular automata program over several nodes. I’ll possibly transmit a few extra columns between nodes so they don’t have to transmit every time but are still separated and then find out when how many are most efficient.
I’m also making performance models of both (hopefully three) of the models. I’ve just finished the math for solar sim and fractals will be underway shortly. It’s really interesting! I figured out all the equations for how fast it goes and the startup time and they verified each other! Very exciting! And confusing! Did you know that if you put a $ in the beginning of a cell in exel it makes it stay? Yeah… I didn’t for a while there. Heh. Figured that out pretty fast ;)
5/5/07
I figured out two different situations for the Solar Sim one and now I have the one for fractals, but I need to check the delay and send data. I’m restarting the cluster now to get some figures on that. The data I did before was more testing calculation time, rather than send time. I used it for the calculation part of the equation though. It’s looking really interesting- it’s doing exactly what I thought it would! When there are too many processors, 24 with the figures right now, the delay time adds up so much it makes the time improvement negative! COOL!
Here are some pictures I took of my whiteboard after I wrote the equations down.
One Spacecraft per processor:
Fixed spacecraft shared between nodes:
For fractal, shared:
I’ll be writing these up in equation editor if I ever find it...
I got Conway’s to run on the worker nodes, and it’s presumably working, but I can’t see it. The master and the nodes confirm the number of pixels that should be colored and they definitely say they’re coloring pixels, but it’s not printing out! Really weird. I have the calculation separated over the nodes but I’m not worrying about shuffling columns back and forth as of yet. I finished the performance model for fractal, and it’s totally awesome! I wrote it up… without the equations nice, but it’s still pretty cool. ;)
I figured out how tog et equation editor onto this computer, only to find out that word 97 can’t handle it. L So then I went to the other computer and got the equations in and they look really nice. It’s annoying the lines get so far apart, but at least you can read it now. I started on the results section and I have all the graphs in there, but the raw data from some of them is horizontal and I can’t figure out how to convert it of shrink it.
5/6/07
I got all the graphs’ raw data translated and put into the results section. I’m separating everything out so that it’s easier for the judges to read. It’s also size 12 font now. GASP. I’m having the main report, a results binder, a parser (and code) binder, and the code code binder. I have all the performance model stuff written up and graphed for fractals and solar sim, but I’ll definitely want to be as or more rigorous with game of life. Busy busy busy! ;)
I’m trying to debug sending the stuff between the nodes, the program’s working, but the boundaries are so error-prone it’s really hard to debug. Yuck.
Ok, got it working- I even got the glider guns to kill each other! And I found out you can simulate a Turing machine with the GOL! HOW COOL IS THAT!? I definitely want to do that!
5/9/07
I got stuff to work really coooool!
Well. Whatever. The performance model finally works and it’s totally awesome!
It’s really cool that I can figure out how it’ll run with a different setup.
Probably said that before, but I’m really liking it. I finished the results
report- its’ 50 pages! I even got to do calculus! J
YAYAYAYAYA. Very fun. And it works and everything! J
5/11/07
I’m finishing up the last bits and pieces of my report, results, and board. I’m also applying the performance models to figure out what the best kind of computer is to make the cluster out of. So say you have $150- what processor speed do you want when the speed is dependent on how much each computer costs. You can also figure out what price you want to buy something at to make it worth your money.
And I’m finishing up my log! awwww! L