Week 2

The plot thickens...

So here we are at the end of the second week of the program. To recap a bit, we are looking at ways to model disease spread over large geographical areas. We'll be using a cluster to parallelize the algorithm in order to run our simulation in a more efficient manner. So with that knowledge, let's discuss this a bit further.

Cluster Computing

Let me discuss this topic a bit more in detail to explain what I mean when I say things like "cluster" and "cluster computing". A cluster is generally several computers networked together working towards a single goal. This can involve 2 computers or thousands. In the latter case, these tend to be defined as supercomputers. In my last post, I detailed the specs of our cluster we use in the lab. This becomes extremely useful when working with large sets of data. We can spit up the work across all of our machines (nodes) in order to exponentially speed up our work. Think of it this way: If a single construction worker tried to build a house, it would take a very long time. However, if we add several workers to the job, they can split the duties and complete the house much faster than a single worker. In computer science, we take algorithms that can take a long time, and try to find ways to split the work into multiple tasks that can be worked on simultaneously.

Large Graphs

For the problem we are trying to solve, we end up having to use graphs to store a lot of our data. We aren't talking about bar graphs or line charts. These are a data structure in computer science which involve a set of vertices connected by a set of edges. For example:

This is a graph with 3 vertices (nodes)

Now the example presented above is a relatively small graph. The graphs we will be using in our simulation will consist of thousands (possibly millions) of nodes. This is because we will be using a graph to represent various locations in our geographical area. Each node can contain a number of agents in which we must process and determine any health changes as well as determine the agent's next possible location.

For a given node, we will need to examine the adjacent nodes to determine if a given agent should travel to that particular node. Even further than that, a given agent may need to travel to a node which is several nodes away from its current location. This could be due to parameters such as age (agent is traveling to school) or financial classification (expensive housing is located further away). In this situation, we will need to find a path (more specifically the best path) to the agent's desired location. Many algorithms exist for this situation. We will be utilizing Breadth First Search (BFS) as it will provide an adequate solution for our case. With such a large graph this can take a long time. This is because the algorithm examines each adjacent node, then it looks at each adjacent node to those, and each adjacent to those, and so on and so on. This adds up not only as our graph grows large, but also with the number of agents this must be performed for.

Enter cluster computing

So obviously we have a problem that will hinder our simulation's performance immensely. Thankfully, there are a few ways we can parallelize this problem to take advantage of our cluster's computing power. First, we can split up our graph into sub areas. Think of this like different areas of your city, taking Fort Worth as an example, we could section it into the Hulen area, Ridgmar, Downtown, and so on. We can then assign the areas to an individual processor. So on our cluster, we could section our geographical area into 16 sub areas (8 machines, 2 processors each). Any more than this and we risk hurting our performance more than we can boost it. Now we have 16 smaller graphs that are more manageable and a bit easier to traverse. Now we still have a problem where path finding could take a while especially at one node at a time. One thing we could do is modify our BFS algorithm to be a bit similar to the A* search algorithm. Since we will have a known distance between each node, which is called a weight, we can use this to help determine if the nodes we are searching are getting us closer to our destination or further away. Additionally, we can utilize the multiple cores on our processor to examine several nodes simultaneously to speed up the process of finding a path.

This simulation will grow very complicated, very quickly. Therefore, we will need to be careful writing the algorithm to keep from breaking things or causing our code to become ugly and messy. Smaller sub-experiments should be utilized to ensure parts of the algorithm will behave the way we expect.

Software Testing

Dr. Mikler has returned this week, so we've had some time to discuss plans for the summer. Rather than focus on the software testing of the cluster, he has asked me to develop a testing solution for the ACM Abstract Repository website, where students may submit abstracts for papers they are writing for peer review. I was just recently given access to this code so I am in the process of examining the code to find points of potential failure. Once I have a complete idea of the functionality of the site, I can begin developing tools to test parts of the site to ensure the code will not fail when presented with various types of input. I plan to research and utilize PHP unit testing tools to aid in this task.

We have discovered much this week. Stay tuned, and we just might see some mini experiments next week.

Week 1

First week of the REU has gone fairly smoothly I believe. Getting settled in and figuring out what I want to do has been fun. We started the week by getting to know everyone and showing the out of town students around downtown Denton. This was a good time and I think everyone had fun checking out some of the cool places around the square.

Dr. Mikler (my faculty sponsor) had been out of town this week so Dr. O'Neil has been helping me find some topics to research and finding a place to get started. Which leads us to our next topic.

Computational Epidemiology

Let's start by talking about this lab and what we do. We are the Computational Epidemiology Research Laboratory (CERL). The lab applies Computer Science techniques to epidemiology in order to provide better ways of modeling data and studying the spread of diseases. One particularly useful part of this subject is simulating the way a disease can spread through a given population. For example, a simulation can be created where a given number of people in a population have the flu. Using a mathematical data model known as the SEIR model (Susceptible, Exposed, Infected, Recovered), we can simulate the way this disease is transmitted through the public. We can control different parameters such as the starting number of infected, how likely a person is to be infected, how long the person is in the exposed state before transforming into infected and being able to infect others, and how likely a person is to recover from the infection. So we'll input these parameters, run the simulation for some amount of time and examine the results. The results will show us how many people were infected, how fast the infection spread, and how many people were able to recover. This data is very useful to health officials as they can use it to prepare for a possible pandemic. It will give them an insight to how this disease will spread and help them to plan prevention measures.

My Research

Before I talk about what I plan to research regarding this topic, let me take a step back. Part of my duties in the lab are restoring our cluster back to full functionality. Our cluster consists of 8 nodes, each with 2 quad core processors and 32GB of RAM a piece. This allows us to do some serious processing. This week I spent some time writing user management scripts so that we could add people on to the cluster easily for other members of the lab to use it. Now that these are in place, the cluster is in a usable state.

So with this in mind, what I would like to do is expand upon the simulation I discussed in the previous section. Current implementations of this type of simulation tend to focus on smaller population areas, like a concert or a festival. I believe this could be expanded into a larger population area such as a large city like Fort Worth or Dallas. When you scale things up to this magnitude, single processors would take an extremely long time to simulate something like this. This is where our cluster comes in. We can utilize the greater number of processors and large amount of RAM to scale the simulation up to potentially millions of individuals. This would speed up simulation time and allow us to analyze larger geographical areas more efficiently. We could also add more parameters to get more comprehensive data. If we add variables like income ranges and age ranges, we can see the way the disease affects different parts of the population.

Software Testing

With an application like this, we will need an effective way to test it. Currently there aren't readily available solutions for testing parallel applications such as this. So as I develop this simulation, I will be researching an developing a solution for Unit Testing or a similar testing method for cluster computing applications. This is a difficult subject because you have any number of processes running across the cluster and you need a way to examine them all to be sure they are providing correct results.

This is all pending approval by Dr. Mikler on his return.