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.amazon.com/gp/product/0471251828/sr=1-4/qid=1153680132/ref=sr_1_4/102-3914225-0287315?ie=UTF8&s=books

http://www.amazon.com/gp/product/0471251828/sr=1-4/qid=1153680132/ref=sr_1_4/102-3914225-0287315?ie=UTF8&s=books

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://www.instant-grid.de/

http://instant-grid.de/?q=en/downloadfiles

http://www.pcquest.com/content/pcshootout/2005/105060204.asp

http://www.linuxquestions.org/linux/answers/Jeremys_Magazine_Articles/Live_CD_Clustering_Using_ParallelKnoppix

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

Thisisanattempt 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:"Whatisthe

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 constructthe 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