 |
 |
 |
| Tyler Hunt | Will, Tyler, and Nicks "Circle Of Death" |
Nick Sun and Will Cathcart with Hrothgar IE participant Fin Cotton |
|---|---|---|
|
|
|
| Tyler Hunt | Will, Tyler, and Nicks "Circle Of Death" |
Nick Sun and Will Cathcart with Hrothgar IE participant Fin Cotton |
|---|---|---|
During the summer of 1999, three students participated in an admittedly unstructured exploration of the utility of a Beowulf machine as an educational opportunity for high end students. The efforts of the three students culminated in the creation of a distributed simulation of a world of carnivores, herbivores, and plants, as is described in more detail in the Hrothgar IE White Paper (see the "Unplanned Exercise in Inquiry" part of the Outlook section.)
As part of the summer program, each student was requested to write a report describing his activities and impressions (and, in the obvious manner, the request was enforced by witholding final paychecks until text was delivered). The unedited comments of the students are presented below.
Contents
- Comments From Will Cathcart
Will began his junior year at San Marino High School in September 1999.
- Comments From Tyler Hunt
Tyler began his senior year at Pasadena Polytechnic School.
- Comments From Nick Sun
Nick began his freshman year at UCLA, after graduating from San Marino High School
- Hrothgar IE Home
Playing God: How our virtual world was created.
This summer, I was fortunate enough to be able to work as an assistant to Dr. Gottschalk. Through my work on the K-12 project, I learned more than I ever thought possible in such a short time.
To start, I'll briefly explain the K-12 Beowulf project. The K-12 Beowulf project is, at its essence, an attempt to use Beowulf parallel computing power to further the education of students in the elementary through high school levels. This summer we discussed many different ways that we could use a computer with such vast capabilities in an educational environment; ideas ranging from a program in which you design your own race car and then race it against classmates in a realistically modeled world to a SimCity-like simulation in which each student takes on a role in city management.
The goal for Tyler, Nick, and I (the three assistants) this summer was to create a simulation that consisted of interacting entities and adjustable global factors using a parallel computing system. When we started out, the project was to create a group of flocking birds. These birds would flock towards friendly birds, flee from predators and, occasionally, eat. Flocking turned out to have many more problems than we could imagine. How does the flock decide where to go? The flock could have a leader who would guide the flock, but then is it really a flock? And how do you choose the leader?
We managed to get as far as a rudimentary flocking program96 Birds that tended to fly towards each other. However, these birds were just as likely to stubbornly refuse to flock, for if they weren't going the right speed they would pass each other by. Eventually, we decided that we were spending too much time on problems that weren't the same problems we would have when we (or someone else) created the real simulation. So we decided to scrap the whole flocking project, and go with something closer to the type of simulation that might eventually be created.
Tyler, Nick, and I decided to create a virtual ecosystem: A simple world within the computer that would include plants, herbivores and carnivores in a balanced system. The plants would use energy from the sunlight; the herbivores would eat the plants and flee from the predators, who would hunt them down. We managed to get a simple version of this world up and running fairly quickly, however we, yet again, ran into a few problems. The herbivores and the carnivores had to know where the nearest creatures were. However, we couldn't just give each herbivore/carnivore a list of all the creatures, as that take too much time too compute, especially in a simulation with thousands of entities. We ended up using a grid system, with each creature only searching in his own grid. This allowed the simulation to run at real time.
We still had a few other bugs to overcome. The carnivores had somehow gained the ability to pull the herbivores towards them. This turned out to be a problem in (gasp!) my coding. One typo replacing a subtraction sign with an equal sign was the culprit. There were many such bugs, and it took a while to exterminate them.
After we had the basic, nonparallel simulation running, we started to work on the parallel version. We decided to divide the simulation into zones, one for each processor. Although this meant that the simulation could become unbalanced, we decided that it would run far faster. There were still more problems, such as interaction between creatures on separate nodes, but they were eventually worked out.
I never expected to be able to work on a computer program this large, as all the programs I had worked with before had been no greater than a couple of thousand lines. I must admit I was surprised that we got the program working in the end, and I'm not sure that I know exactly how the program is running. In the end, I had a lot of fun this summer, and, more importantly, I learned a lot about computers, parallel computing, and writing working code.
|
- Will Cathcart |
Consider a brick falling from a building, and an ant meandering in its asinine little way directly beneath it. This is a rather appropriate illustration of my encounter with socket communications this summer.
At some point, it was realized that in order to actually have a user view or effect changes in whatever the Hrothgar happened to be running, sockets would inevitably have to be used to communicate between the java client and the Beowulf. After a short time it was decided that forking off the simulation would be "A Bad Thing." (tm) Thus the sockets would have to be nonblocking, to my dismay. I did get them working, eventually, though, so it was all for the best.
Thus began the quest for writing a simple socket class to communicate with the mysterious java client. The goal was to fit it into the main cycle of node 0, and then while all the other nodes were performing something time consuming (density checks, we decided, after creating some logs) do a Select and handle the individual requests. The computer(s) on the other ends would send something trivial like a 64 byte packet of instructions, consisting of a byte describing what follows, the actual data/instructions, so on and so forth. This has not been implemented yet due to there being only one implemented instruction so far: a map update request. It would then continue through every event until it either hit some predefined time limit, maximum number of requests, or was left with no new events.
In the case of the simulation brought up this summer: Things that will probably be implemented later include logins, the ability to fetch specified regions of the map, a request for detailed information of a grid, a logout signal (thus freeing up a socket instead of letting the simulation close said dead socket much later) the ability to change variables remotely at run time, etc.
The request for the maps has been implemented, though it doesn't do much good, as last time I checked the Java client wasn't being cooperative.
Part of the idea behind the project is the ability to administer/see it remotely, as opposed to being forced to remain at the screen or exporting a display, thus allowing a level of freedom for sort of "hands-on" approach that people seem to cherish so much.
Sure, pretty much any reasonably up-to-date machine can handle 50 somewhat busy socket connections, provided it has a decent connection, but the ammount of time spent dealing with each and every request that comes in can become fiarly significant. Try to run a real time simulation on a machine doing that, and you run into some problems, which is a good reason to have the model consist of machines running the simulation and a smaller number of nodes exclusively handling routing and/or socket communciations. One might even say that any nontrivial nonparalellized piece of code and user control on a massive scale are mutually exclusive.
Naturally, one would assume that as the purpose of Java is cross-platform executability, Java would be very sensible in having function calls to facilitate the proper translation of data sent from other machines over sockets. So, sending data to a Java client from anything should be nice and simple, right?
As far as my comrades and I could discern, this is not the case, nor is there a simple magical method of making sense of the gibberish that we were initially able to send through after establishing that connecting the two was not a real problem. Sure, strings of text didn't seem to be much of a problem, but sending some sensible number like 4 would come out to something in the area of 17179879184, if I remember correctly, as long integers would come out 65536^2 times their intended value. This was not too difficult to learn, but the ability to send integers without too much hassle is little consolation for the fact that sending floating point numbers was a task beyond us.
Eventually, there was success in connecting the Java client to a C/C++ server, and I decided to make a simple socket class for implementation in the little simulation we had put together. This part was fairly easy, suprisingly, and after I mucked up the code a bit, even managed to get simple updates assembled and ready for sending to a requesting Java client.
Unfortunately, by the time I had that implemented, I had somehow broken the ability of the simple little java client to communicate properly.
|
- Tyler Hunt |
The summer of 1999, I worked for Dr. Thomas Gottschalk in his project to introduce Beowulf class computers into K-12 schools. Working in a research-type environment which specializes in programming has been a great experience for me.
Coming into the CACR building, my first reaction was that I was over my head and would probably not be able to produce anything productive. The one goal on my mind was not to get fired. But as I grew accustomed to the "set your own hours" and "work as you like" attitude, I was less concerned about being fired as I was about setting out and creating something useful to the project. So, thats became my main concern for the duration of the summer.
The first thing I learned, was that I had a lot to learn. The goal of the project was to create some type of program which would run on a Beowulf class machine (ours was dubbed Hrothgar) and would have educational value. The first problem was that I had no idea how to program in MPI, the standard interface for Beowulf Machines. Still, the teachers provided us with the idea of a high-fidelity simulation which would run very much like SimCity and with this, I began creating the framework for such a simulation to run on a regular machine. My first world consisted of birds flying around each other using grid-type proximity detection for collisions and interaction, and real-world physics for movement. Once I had the birds skittishly flying around in a plane, we decided to up the ante and create a world of plants, herbivores, and carnivores. I personally like to think of them as dinos.
Our first real-world would include the ability to both give birth and die. In doing this, I had to learn a lot about dynamic memory allocation and storage. Although all this was still being done on one computer, I had to learn how MPI would be finally implemented before I began writing so that the program could eventually be ported over. With all these things to do at once, the coding went rather slowly. It took 3 weeks of coding and debugging before we had a proper run. Even then, crashes were the norm until from constant debugging, the stability of the program rose from 1 cycle to 1000 cycles and the population handling increased from 2,000 to 20,000.
Our successes in creating the world of three species was probably the climax of my productive time. After doing that, I moved to begin coding the same type of framework into MPI for the Beowulf class machine. The first problem was packaging the objects into sendable packets. Once again, Dr. Gottschalk helped by pointing out different methods to address the problem and in the end, the communications worked fine. We discussed whether an interest map, or quad-tree was more effective. For the interest of time and complexity, we choose to do a faux quad-tree which would allow for simplier load handling but hardcode a requirement of 5 processors. As all the communications were finished and all the code running reliably on 5 processors, I then moved on to the Java client.
As all the work was being done on the communications by both Tyler Hunt and Will Cathcart, I moved onto the end-user client. Since it was not expected to run under any specific OS, we decided to use Java to write our client program. This meant I had to learn enough Java to create some type of window into what the server was doing. The next two weeks was spent learning about and then creating a Java client. I used a small canvas to represent the world and painted polygons of different shades to represent the density of creatures within a certain area.
Finally, as things began to wind down, I read quite a bit about artificial intelligence and more specifically neural networks for my own personal knowledge. This summer has probably been the most productive I've spent and am glad to have had the experience. Overall, I've learned as much as I have in the past two years of programming classes, as I did this summer. I am happy to have spent this time and am very thankful to Dr. Gottschalk for allowing me to help with this project.
|
- Nick Sun |