Computational Conversations

(based on actual conversations I have had with domain scientists...)

Solving a scientific problem?  I can help!

Is it a partial differential equation?  I know something about that.  I've solved Schrödinger's equation in many forms.  Advection and diffusion I know well.  Choose your finiteness: finite elements, finite differences, or finite volumes?  Each one has its own advantages and pitfalls.

Linear algebra?  Use an optimized BLAS library, not the reference library!  Our vendor has a group of applied mathematicians who developed these math libraries just for you.  Don't let all their effort go to waste!  Eigenvalues -- you don't need to orthogonalize at every step, just every so often.  Maybe it will require a few more iterations, but the iterations will be so much cheaper...

Optimization?  Yes!  Finally something I am an expert in!  Okay, so what type of problem are you solving?  Is it convex?  Is the objective function cheap to evaluate?  How many parameters?  Is it a mixed-integer program?  Actually, I think your problem could be reformulated as a combinatorial optimization problem and we could try an evolutionary algorithm...

Oh, you meant code optimization.  Yes, I can do that too.  See these loops?  Since it's Fortran, we need to reorder the loops so that the array is accessed by its first index in the innermost loop, not its second.  See, we just got a 4x performance boost just by swapping these indices.  Okay, let's change this array to a function, because it is easily calculated and the function can be inlined whereas that memory lookup can't.  And let's eliminate these "if" statements by dividing this loop into two parts.

Your job fails at 120,000 MPI processes, but not below that?  What happens when it fails?  How long does it take to get to the point of failure?  What is the code doing when it fails?  Does it always happen in the same place?  Let me ask my sysadmin colleague to look in the top-secret log files that only they can view...

Does this computation depend on that one, or can it be done in any order?  Is there any reason to keep this data after initialization?  What if we used this framework?  Asynchronously spawning new tasks would implicitly load balance this algorithm.  Your algorithm is not scalable.  The synchronizing you do will be a huge bottleneck as you scale up.  It may work okay now, but at the petascale or beyond there will be scalability issues coming out of the woodwork, things even beyond this synchronization issue.  Trust me, I have seen this happen even in my own codes.  Let my pain be your gain!

I may not be a scientist in your field, but I know a lot of things that can help you.  I've boosted the performance of codes by a factor of two with a single keystroke.  I may not have seen your problem before, but I've seen something like it.

Debugging in Parallel

Sometimes* when you write a computer program, there are bugs in it.  Some of those bugs can be easy to catch (e.g., I forgot to put a semicolon at the end of line 67 and my code won't compile), while others are not.  There are different types of bugs, too -- memory errors that cause a segmentation fault, typos that might cause one variable to be updated instead of another, and errors in your algorithm, to name a few.  Each of them is uniquely challenging to find and fix.

But when we add an additional layer of complexity to a code by making it run in parallel, the difficulty of finding and fixing bugs goes up by several orders of magnitude.  The most insidious of bugs will appear only at high process counts, or irregularly.  How then can we find out where our code is going wrong?

A classic method of finding bugs is by inserting print statements in the code.  Using the print statements and running the code, we can follow a sort of bisection algorithm to determine where things go bad.  Typically we insert a few print statements at the first pass, and then further hone down to the point where the error occurs with several subsequent runs.  But this is highly time consuming, and produces a lot of excess data.  I for one would hate to insert all those print statements in a complicated code, not to mention sift through the output of print statement debugging across 200,000 processes.  It can take weeks to find a bug in this way, especially if you have to wait for a batch system to run your jobs.

The best solution is to use a debugger.  Using a debugger, you can pinpoint the exact line at which the bug occurs in a single trial (for bugs such as segmentation faults).  And you can insert break points around areas of the code you suspect are faulty, and examine the contents of the variables.  You can also step through the code slowly and figure out how x came to equal 27 instead of 32 (for example).

Parallel debuggers exist, and do scale up to hundreds of thousands of processes.  Of course, these are commercial products but I'm guessing you don't have a 200K-core supercomputer in your basement.  Most supercomputing centers have a license for a commercial debugger such as Allinea DDT or TotalView.  Both of these are great products that will help you to find your bugs quickly and relatively painlessly.  And if you stubbornly insist on not using a commercial product, most mpirun or mpiexec commands allow you to attach your favorite free debugger to your parallel execution.

Do you think it is too hard to learn to use a debugger, that by the time you do learn it you could have already found that bug and moved on to something else?  Invest in your future and learn to use a debugger anyhow!  Let me tell you the sad, sad story of a graduate student I knew quite well.

This graduate student felt that by the time he/she learned to use a debugger, that final bug sitting between the student and graduation would have been found and fixed.  Because, of course, that was the final bug.  He/she said this, bug after bug after bug.  Looking back, this person realized that by investing a day learning to use a debugger, he/she could have graduated (and started earning for-real money instead of measly graduate student stipends) about six months earlier.

Don't be like that graduate student.  Learn to use a debugger and stop wasting your time!


* Actually, pretty much every time you write anything more complicated than "Hello, world!"

Adventures in Little Things Making a Big Difference

So, at work I work with some scientists in a field that rhymes with shmooclear shmisics.  These people are very smart application scientists, but definitely not computer scientists.  I love them because as long as they exist, I will always have a job.  They write pretty miserable code, because that's really not their thing.  They just want to do the science.

Half of my job with them is improving their code, but more importantly (if I want my efforts to not be wasted), I spend a lot of time developing a working relationship with them.  You see, they are a kind of insular community, and don't generally trust some "hot shot" outsider who doesn't know the science.  But I have been able to do a few simple things that have drastically improved the performance of their codes, so I think we are getting somewhere.

Most recently, I was profiling one of their codes, and discovered that it spent more than 50% of its time sorting.  I looked at their sorting algorithm and saw that it was some homebrew sorting algorithm that was kind of like bubble sort (with computational complexity order N², or the worst possible performance without doing something completely stupid).  My guess is, they didn't know that some smart computer scientists had thought a lot about sorting algorithms and developed smart ways to sort; they probably just thought of how they would sort things and implemented that.  So I replaced their Frankenstein sort with a heapsort algorithm (worst-case complexity N log N) and the sorting became an insignificant portion of the total runtime.  Then, I showed my primary collaborator what I had done, and they discussed it in a meeting the next week.  As it turned out, nobody knew why it was sorting; it was some legacy of an abandoned algorithm.  I removed the sorting altogether and am in the process of doing a little benchmarking study.

It was pretty amazing, though, that this piece of code that nobody realized was being executed was taking up more than 50% of the test problem runtime, and more than 20% of the benchmark problem runtime!

The next bottleneck in their code is the I/O.  They are reading the input in a very unintelligent way (all the processors opening the same file and reading it), so I plan to fix that for them when I get the chance.

Adventures in Conferences

I'm at a conference for students with a prestigious fellowship, in our nation's capital.  Yesterday there was a workshop on high-performance computing, which I attended.  I really enjoyed it because there was a high-level discussion of the future of HPC architectures and algorithms.

I talked to an old friend (we've known each other for a long time, not that he's old) about his work as a manager, and he said something that made me feel really good about my career plans (I see myself ten years from now more as a manager than a scientist, although I definitely enjoy what I currently do).  He said he may not be publishing any papers now, but that there is definitely a lot of intellectual work to do as a leader in the high-performance computing field, synthesizing ideas together and planning for the future of the field.  I am attracted more to the intellectual stimulation of computing in the abstract, and less to the down-and-dirty details of implementation (although I do enjoy coding from time to time, when I get the chance).

I'll talk more about HPC architectures and algorithms when I get a chance to really sit down and write something good.

Architectures and Algorithms

I used to not care one way or the other about supercomputer architecture, back when I was more on the math side of things. After all, math is math, right? It should always work no matter what the machine looks like.

But as it turns out, a supercomputer's architecture influences the feasibility of algorithms. An algorithm that requires a lot of communication will not perform well on a supercomputer with a slow interconnect, for example. There are many different architectures out there, and different algorithms work better on different machines.

There are seven common patterns in the scientific computations we encounter in the high-performance computing world: sparse linear algebra, dense linear algebra, structured grids, unstructured grids, N-body problems, fast Fourier transforms, and Monte Carlo algorithms. There are other patterns, but these are the top seven in HPC. Each of these types of algorithms thrive under different conditions.

When you are designing and building a supercomputer, you have constraints on budget, power consumption, and size. What elements of the machine do you beef up, and what elements do you cut corners with?

At this point, you have to think of your intended users. If all your users are computational biologists studying protein folding, then there's a machine already out there for them: the IBM BlueGene. This machine is great for the N-body algorithms employed in the study of protein folding and molecular dynamics in general.

But, if your users are nuclear physicists, then the BlueGene is about the worst way to go. BlueGenes are low processor power, low memory machines -- the antithesis of an ideal nuclear-physics machine. The two things nuclear physicists need the most for their sparse and dense linear algebra calculations are memory and floating-point operations. Nuclear physicists would do best on machines that had huge shared memory banks, but unfortunately, there aren't really any machines like that these days.*

The hard part is when you have a mixed group of target users, who use more than one or two of those seven fundamental patterns. Since each pattern stresses different elements of the machine, you would like your all-purpose machine to have top-of-the-line processor speed, memory, and interconnects. But, since you are constrained by cost, power consumption, and existing technologies, something's gotta give.

Today, floating-point operations (Flops) cost practically nothing, because fast processors are cheap. So today's supercomputers are capable of performing more Flops than application scientists are capable of consuming. The real bottlenecks lie in memory and communication.

Memory is constrained by two factors: cost and power consumption. The cost of memory on a single node does not scale linearly -- 4 GB per core costs more than twice as much as 2 GB per core. Memory also requires a lot of power, so the more memory you have, the less power you have remaining to be used by the processors.

As for the interconnect, it definitely costs more for faster communication. Not only does the fiber cost more, but it also depends on how many miles of cables you must use on your machine. (And yes, for the big machines, it is on the order of ten miles of interconnect.) How do you want your processors to be able to communicate -- do you want a direct connection from every processor to another (completely infeasible on large machines due to space constraints, to say nothing of expense), or by hopping along a network? What kind of network will work? Most machines today use a 3-D torus, as a balance between cost and efficiency.

At my workplace, we are a general-purpose center so we try to have a balanced machine. This pleases everyone and no one. The thing we're the most lacking is probably memory, but that is true everywhere. If you look at the ratio of flop capability to memory capability, it has skyrocketed in the past decade, and that trend will continue. So what ends up happening is that codes that require a lot of memory (such as the nuclear physics applications) end up using a lot of nodes inefficiently in terms of floating point operations, but filling up every last bit of the memory. Part of my job is to help these folks reduce their memory footprint, thereby being able to run bigger problems on the same number of processors.

Now that I am more on the practical implementation side of things, I see how much of a difference the architecture of a machine can make in terms of application performance. I wish I had realized this earlier, because I would have made an effort to learn more then about all the very interesting ideas in computer architecture!


* There were machines that were considered to have huge amounts of shared memory, at the time when they were new, but compared to the agregate memory of today's top supercomputer, they had only tiny amounts of memory.

HPC and the Future of Algorithms

As parallel computers get bigger and and more powerful, the way we use these machines has to change. The reason is that the machines are not just growing in clock speed, they're changing in architecture as well.

Over the past decade, leadership high-performance computing resources have evolved from systems with thousands of CPUs to systems with hundreds of thousands of multicore CPUs. And in this time, the algorithms in the best science application programs have adapted to this change. Today, the best programs exploit threading (such as OpenMP) within a node, and MPI between nodes. They use clever algorithms that minimize communication between nodes, with broadcasts and other all-to-all communication minimized.

But a radical change is about to happen. At this point, adding more cabinets of multicore CPUs to create an even bigger supercomputer is unsustainable in both space and power consumption. The most powerful supercomputer in the world takes up more than 4000 square feet of floor space -- the same footprint as a large house. It idles at 3 megawatts -- when it's just turned on but nobody's using the thing, it consumes enough electricity to power a large neighborhood. And during its full-machine runs of the Linpack benchmarks, it was demanding 7 MW. Quadrupling (or more) the machine size to reach 20 Petaflops* is not feasible, even here in the land of cheap land and plentiful power. So a new architecture is needed.

The harbinger of this new architecture was the first machine to cross the petaflop barrier, Roadrunner. Los Alamos National Laboratory, together with IBM, put together this novel machine which came online about two years ago. The novel part of the architecture was that it was no longer homogeneous -- not all the processors were the same. Roadrunner has three different types of processors in it.

Sadly, Roadrunner is going the way of the dodo, because it was too complicated to program. But it was a good experiment that led the way to the architecture that will be in the next 20 PF machines. In this next class of machines, additional floating-point operations will be provided by accelerators, kind of like the graphics cards in the machine you're probably using to read this post. This new architecture requires new algorithms to be able to exploit the accelerators. Accelerators are massively threaded -- on the order of a million different threads can be run at once on a single accelerator. So we're having to rethink our algorithms, and redefine them in a way that can exploit that kind of parallelism.

Looking to the future, the exascale** will be here before we know it. Early reports suggest that exascale machines will have millions of heterogeneous processors. At this point, we will have to completely rethink our algorithms.

Too many codes still rely on the manager-worker paradigm. There's one process, P0, who is in charge, who tells everybody else what to do, and collects and compiles results from them. This is a great paradigm if you don't have too many processes, but rapidly becomes inefficient when you reach more than a thousand. There are things you can do to improve the efficiency at higher processor counts, but in the end, this is not a scalable paradigm. Something will need to change radically before these codes will be able to run on millions of processors.

I like to think of the algorithm problem in analogy with music. Let's say that computations are like music, and computer processors are like musicians. Today's algorithms are like compositions for a marching band. When the algorithms are running, the band is in lock-step, each member with a very predefined role in the composition/part in the score. There's a leader, who keeps everybody in time. There's a predefined structure and order of operations. You can use different arrangements of the score to accommodate different sizes of marching bands.

But a marching band is not scalable. One conductor can be seen by only so many musicians. How would you lead a million musicians?

Maybe you could broadcast a picture of the conductor, or something like that, but it's not the same because the conductor can't keep track of all the musicians. Ultimately, you really can't lead a million musicians in lock-step. So you have to rethink your algorithm for creating music.

The musical equivalent of the algorithms that we must develop for the exascale are unfamiliar to the Western ear. If the ultimate goal is to create music, who says we have to do it in a scripted way? What if we provided certain parameters, such as the key and the starting note of the scale, and then let everybody improvise from there, perhaps with some synchronization between neighbors, kind of like a distributed, million-musician Raga?

In fact, the algorithms we have developed function very much in this way. The work is spread amongst all processes in a statistically even way. Due to variations in the machine, the algorithms may not run in precisely the same way every time, but this is controlled for and the answers we compute are still the same. The cost of communicating with millions of other processes is hidden by overlapping communication and computation. If you haven't heard from a process you need to complete the current task, move on to another task and come back to it later. The computations travel to the location where the data is, instead of the data being transported to the computation.

I've heard it said like this: let's say your goal is to reach the moon. There is a series of progressively taller trees that you can climb and get progressively closer to the moon. But there are not any trees tall enough to reach the moon by climbing them. So you have to think of another solution to reach your goal.

It will be interesting to see what application developers do to exploit exascale computing resources. How many of them will keep climbing trees, and how many others will abandon their tree-climbing programs in favor of something else?


* A flop is a floating point operation -- any basic arithmetic operation involving a decimal point, e.g., 1.1+1.1. A petaflop machine is capable of performing one quadrillion floating point operations per second -- a feat that would take everyone in the whole world, working together, doing one flop per second, roughly three days to complete.

** The exascale is the level above the petascale -- on the order of one quintillion flops. Exascale machines should come online in 2017 or 2018.

Math is Lucrative... Let's Be Computer Engineers!

I am pretty excited about the fact that Barbie's 126th career is Computer Engineer. I'm with blogfriend PhizzleDizzle, I'm happy that Barbie is becoming one of us. I'm more of the old school nerd than Barbie (or PhizzleDizzle, for that matter!) -- fashion is really not my thing. I might wear the shirt Barbie's sporting but only if it came in a looser cut, and even then, not to work.

The best thing about Computer Engineer Barbie, from my perspective, is that she's showing girls that they too can succeed in computer science. Computer scientists don't have to be male, they don't even have to be nerdy -- they just need to have an interest in computers/computing and follow their passion.

I for one am looking forward to the day that Barbie comes and installs our next supercomputer. In the meantime, I might just have to preorder her and display her prominently on my desk when she arrives late this year.

A Blonde Walked into an HPC Article...

I like to keep up on the latest news in high-performance computing (HPC) as much as any other computational scientist, but there are some websites that evidently don't want me as a reader. I don't fit their model of what it means to be a scientist, you see. I read this particularly problematic article and had to check my computer's date function to confirm that it is 2009, despite troubling statements like

Each Opteron core gets its own Cell chip to do its math for it, like the blonde who isn't dating the nerd but the nerd thinks is...

and

What Jaguar needs is some powerful nerds so its blondes can run code, and it looks like the next generation of machines at the supercomputer center are going to be using the Fermi GPUs.

Really, Turd Biscuit? Is it necessary to insult 50% of the population (because blonde jokes are not about people with light hair, they're about women), and impugn the abilities of accomplished women?

It is so depressing that these types of "jokes" are still an acceptable type of "humor." When I complained about the blonde "jokes" contained in this article on another forum, I was soon accused of being too uptight and having no sense of humor.

I knew when I did it that I was opening myself up to criticism, and I was counting down the minutes before somebody called me a humorless feminist. I did not need to wait long. I gave a short reply to that man, but here's a more in-depth explanation of why I object to these so-called jokes.

First, the stereotype that women use men to do their homework for them is so tired, untrue, and insulting to everyone involved. It's insulting to me and women like me, because it places doubt in people's minds about our abilities -- maybe I manipulated a man to do my work for me, and am actually incompetent! It also provides space in men's minds to think it's actually appropriate to ask whether I got my job because of my husband, upon meeting me for the first time.*

It's insulting to men, too, suggesting that they are so desperate to get women's affections that they will compromise their academic integrity, or so socially inept, that they don't know when they're being taken advantage of. Either way, it's an insulting insinuation.

Second, these types of jokes in a professional setting (and I would classify reporting about a new supercomputer on "one of the world's biggest online tech publications" as a professional setting) serve to remind the targets of the joke that they don't belong in this field. Thanks a lot for letting me know I'm not one of the nerds, for reminding me how different I am from everyone else in HPC, and for reminding me that some people think I'm too stupid to do my own work. That helps bolster my confidence and builds trust between me and my male colleagues.

Finally, humor legitimizes prejudices. Sexist humor acts as a 'releaser' of prejudices, according to a study by Professor Thomas E. Ford of Western Carolina University et al. The presence of sexist humor in a social environment creates an environment where men with sexist beliefs feel free to act upon those beliefs, because they believe that within that environment, sexist behavior is acceptable.

In their experiment, they asked men to imagine that they were members of a workplace. They then had the men read either sexist jokes, neutral jokes, or sexist statements, and subsequently asked them how much they would donate for a women's organization. Ford and his team found that "men with a high level of sexism were less likely to donate to the women's organization after reading sexist jokes, but not after reading either sexist statements or neutral jokes." Similarly, after viewing sexist skits disparaging women, the men allocated larger funding cuts to women's organizations in the hypothetical workplace. The studies show that "humorous disparagement creates the perception of a shared standard of tolerance of discrimination that may guide behavior when people believe others feel the same way."

I'm sure there are people out there who, even after reading this, would accuse me of political correctness. Sure, you may have the right to free speech, but how about tempering that freedom with respect for your fellow human beings? Treating others with respect is not such a huge constraint. Or, if the only way you know how to talk is by using sexist tropes, then you need psychological help.

Please, people, it's not hard to come up with inoffensive metaphors. I can think of so many better ways that he could have expressed his point, that wouldn't be offensive to anyone! What about Dilbert and the pointy-haired boss? That would have expressed the exact same dynamic, minus the antipathy for women. Or a brain and muscles. The brain tells the muscles what to do, and they have to do all the actual heavy lifting! Those are the first two jokes I thought of, in under 30 seconds, and they disparage no one.


* Yes, this happened to me. I should have either asked if he'd gotten his job because of his wife, or told him that I got my job through the powerful stay-at-home-dad cabal, but I was too stunned to think of those replies at the time.

Last night, Terminator 3 was on television. I'd never seen the movie, so this gave me a chance to make fun of all the computer stuff in it.

The computer that controlled our national defense was a 60 Teraflops machine, meaning that it was capable of doing sixty trillion floating point operations per second. (A floating point operation is just any basic arithmetic operation involving a decimal point: 1.1+1.1, for example.) I looked at the Top 500 list from 2003, the year the movie came out, and the fastest supercomputer was the Earth Simulator, at 36 Teraflops, which had come out the year before, so I suppose that machine would have been considered super-powerful.

It's just that, to me, a 60 Teraflops machine is quaint. I work with a machine that is 1.6 Petaflops (that's 1.6 quadrillion floating point operations per second). Let me say something about these machines, though.

First, they are very delicate. In the movie, John Connor talks about having enough C4 to take out ten supercomputers, which made me laugh again. You don't need C4 to take out a supercomputer. The easiest way is to destroy its air conditioning system. Without air conditioning, it will be a pile of silicon goo in no time. If it is so smart that it has a backup system (more on the intelligence of these machines in a minute, by the way), then seriously, it would be pretty easy to just go in and pull out a few boards and cables and do a lot of damage. A machine that is fault-tolerant enough to handle something like that is but a dream at this point in time. And furthermore, you could probably just wait a couple of days and the machine would go down on its own. Without human intervention, these machines are helpless.

Second, supercomputers are stupid. They are tremendously skilled at performing floating point operations, but that is a far cry from intelligence. Our brains operate a whole lot differently than a computer's processors. Artificial intelligence is really the holy grail of computer science. All the petaflops in the world aren't going to help anything. I mean, humans are pretty flops-deficient, yet we've accomplished a lot more with our intelligence than computers have.

Here's just how flops-deficient we are compared to computers: if we took everyone in the world (babies, old people, and everyone in between) and we all did floating point operations at a rate of one flop per second (which is a pretty fast pace), it would take us more than three days to do what it takes my friendly neighborhood supercomputer to do. But floating point operations aren't the way that our intelligence operates, whereas they are the only way that a computer's intelligence operates. And there's not a very good way to use floating point operations to mimic our type of intelligence, which is why even a petaflops machine would not be able to take over the world.

On Students

I have had the privilege of mentoring three students since I started working. While others I know have had bad experiences, working with these students has been a very positive and fulfilling experience for me.

Of course I was careful to select only the best students to hire, but I think that the main reason my experience has been so positive is because of my attitude going into the mentoring relationship.

I see an internship as an opportunity for an up-and-coming scientist to learn science, not as a way for me to get some extra work done. And because I have that attitude, I'm never disappointed.

I fully expect my students to be time sinks, and I have developed ways of mitigating the worst wastes of my time; for example, I provide them with a handout detailing the project parameters on the day they report, and I schedule weekly meetings with them and try to touch base briefly once a day. They can read the handout rather than having to rely on any notes they would have taken while I was verbally explaining the project, resulting in fewer gaps in their understanding. I schedule for one hour per week of my uninterrupted time, and I usually go touch base with them about 15-30 minutes before a meeting, allowing me an excuse to escape if my time is being wasted.

I also assign them a project that it would be nice to have completed, but that is not vital to my work. In this way I can be only pleasantly surprised by their progress on the project, rather than depending on their work.

So far I have not been disappointed. Even if my student gets nothing tangible done, I do not consider my time to have been wasted. Students don't learn high-performance computing in school; it's really something that has to be learned through experience, and that is what I have enabled them to do during their internship with me. And if we don't give them the chance to learn it, how are we ever going to be able to develop the next generation of computational scientists?

I was once a student who knew nothing about high-performance computing. Someone took a chance on me and I was hired as a graduate research assistant in our university's HPC center, despite my lack of knowledge. It took some mentoring and time-wasting on his part, but I learned the skills that I needed to get to where I am today. I think it's only fair that I give others the same opportunities that my mentor gave me.

Supercomputer Supermodel

Earlier this week, I spent nearly two hours in photo shoots at work. Pictures were being taken for our annual report and publicity materials.

Of course, since they wanted to make everything as realistic as possible, they chose two women and one man to pose between the rows of supercomputer cabinets. (After all, that is the gender ratio at my workplace.) In addition, we held a laptop while we examined the cabinets carefully. (Another thing that I'm always seeing people do.) We opened and closed cabinets, pointed out things to one another, and tried to be conversational despite the fact that we were wearing earplugs (it's loud enough in the machine room to damage your unprotected ears) and couldn't hear a thing. (Thanks to the wonders of Photoshop, those earplugs will disappear from the pictures.)

After the grueling hours in the machine room (hey, I was squatting for something like ten minutes, which gets really painful!), I told my boss that I really needed a personal upkeep allowance to buy clothing and have beauty treatments now that I'm a supercomputer supermodel. For whatever reason he didn't agree, claiming that he paid me enough for me to buy my own (damn) clothes and beauty treatments, with plenty left over for feeding my starving child. Personally, I think he refused because he's afraid he'd have to share the money they give him for that purpose. (Money he probably spends on conferences, just to obtain the conference shirts that are a staple of his wardrobe.)

Mother-Son Evening

This evening Jeff was taking a watercolor course so Vinny and I had an evening out on the town together.

We started by going to the "Pizza House" (as Vinny calls our local pizza buffet restaurant) for dinner, where we saw an older woman whom we recognized, sitting alone. I invited her to sit with us, and she did. I asked her about her past, and she told me she had a masters degree in mathematics, and that she'd worked as a programmer on my workplace's first supercomputer. I thought this was just about the coolest thing ever, and I asked her quite a few additional questions about her computing experience, and then told her a little about what things are like now.

After dinner, we went to play on the playground, but we didn't stay long because the sun was setting. We came home and it was soon time for bed. I tucked Vinny in just before Jeff came home.

Adventures in Pseudorandom Number Generation

When I made my Pi Day cake, a circle inscribed within a square, I decorated it with sprinkles to represent the Monte Carlo quadrature algorithm that could be used to compute π.

You can see that I tried to distribute the sprinkles evenly but somewhat irregularly over the cake. I did not want them to be in a grid, but at the same time I didn't want them to be clumped together.

In the case of computing a two-dimensional area, a grid and a pseudorandom distribution will yield the same order of accuracy, but for three dimensions and higher, the pseudorandom distribution always comes out ahead. This is because in finding the area or (hyper)volume of a D-dimensional object, the accuracy of the number you get from N points is proportional to one over the Dth root of N for a grid, but always one over the square root of N for a pseudorandom distribution. In other words, for two digits of accuracy in computing the volume of a three-dimensional blob, I need a million points on a 3-D grid, but only 10,000 points in a pseudorandom distribution.

So, these Monte Carlo algorithms can really save us a lot of effort. So how can we create pseudorandom distributions? Furthermore, what does pseudorandom even mean?

I'll start with the last question first. Pseudorandom means that something seems random but actually is not. A sequence of numbers that we generate using a mathematical formula cannot be random by definition. But if it shares certain desirable properties with random number sequences, then it is pseudorandom.

Basically, if a sequence of numbers that we generate looks random, meaning that there are no discernible patterns in it, then it is a pseudorandom sequence. A good pseudorandom sequence has the following qualities:

1. It has a very long period (meaning there are many millions or billions of numbers generated before the sequence starts repeating itself) -- generally they have a period of 2ⁿ, where n is the number of bits in the computer's representation of numbers, although longer periods are better.
   
2. It is uniformly distributed (meaning that the sequence lands on every possible value with equal frequency).
3. It is reproducible (meaning that you can regenerate the same sequence over and over again just by initializing it with the same seed value). This is the primary advantage of pseudorandom number generation: it is useful to use the same "random" numbers every time when you are debugging a program, for example.
4. There should be no correlations in higher dimensions, meaning that if I generate n-tuples from the sequence (for example, pairs (x, y) derived from elements a_2k and a_2k+1 in the sequence), there should be no discernible pattern.
   
5. If the sequence generation is quick and cheap, that would be helpful too.

How, then, can we generate a pseudorandom sequence? Pseudorandom number generation is hard! I had a tough time generating the points on my cake. At first, I had a lot of clumps of sprinkles, and I actually had to go back in and carefully fill in some of the bare spots. So "Rebecca sprinkling sprinkles over a cake" is not a very good generator.

Likewise, most pseudorandom number generators (PRNGs) aren't actually very good. For example, the RANDU generator, commonly used in the 1960's and 70's, was a very poor PRNG. Check out the graph in the Wikipedia article, and you will see how bad it was. If you used RANDU to generate triplets and then graphed them as (x, y, z) coordinates, all the points would fall into one of fifteen two-dimensional planes. So if you were using this for your 3-D Monte Carlo integration, it would almost be as if the points were pseudorandom in two dimensions, and gridded in the third, leading to inaccurate results.

The best PRNG for scientific applications is the Mersenne Twister, developed in 1997 by by Makoto Matsumoto and Takuji Nishimura. Its period is more than 10⁶⁰⁰⁰, it is equidistributed up to 627 dimensions (so you won't have the problem described above), and it is cheap and easy.

Most computer programming languages have a built-in PRNG. In C, for example, you can call the rand() function, which will output a number between 0 and RAND_MAX (a constant that is machine dependent). But these generators are usually pretty lousy, because they are linear congruential generators, sharing the correlation characteristics of RANDU. They are acceptable for program development and debugging, but when the time comes for production runs, you should replace the built-in PRNG with something better.

For serial pseudorandom number generation, the GNU Scientific Library (GSL) provides a large suite of PRNGs, including the Mersenne Twister. The GSL is open source and freely available online.

Generating pseudorandom sequences in a parallel application is a more difficult task. You want all the processes to generate different sequences; otherwise, you've gained no information because you duplicated the same Monte Carlo integration across all processes. The standard parallel PRNG is called SPRNG. The advantage of SPRNG over just generating sequences with different seed values on different processors is that SPRNG can generate multiple independent sequences, more than one per processor, with only a minimum of communication as each new stream of numbers is initialized.

Pseudorandom number generation is an important topic of study not only for those who use Monte Carlo simulations: it's also an important component of cryptographic applications. But that is a topic for its own post...

Adventures in Linear Programming

One of my fearless readers (okay, my brother-in-law!) lamented the recent lack of mathematical content in this blog. I'm sure that he's not the only person who reads this blog just for the math. So, without further ado, I present a topic I've been working on lately: linear programming.

Suppose that you're wanting to get back into shape, and want to develop a good, healthy diet to go along with your exercise regimen. You know that you need to eat 2000 calories (for example), less than 300 g carbohydrates, at least 25 but less than 75 g fat, and 90-120 g protein.*

Perhaps we want to minimize the cost of this new diet. Then if we knew the cost and nutritional content of all foods, we could set up the following optimization problem:

minimize _{diet ∈ foods} Cost(diet) subject to
Calories(diet) = 2000
Carbohydrates(diet) ≤ 300
25 ≤ Fat(diet) ≤ 75
90 ≤ Protein(diet) ≤ 120.

This is what's known as a linear programming problem. It's linear because the equations we're trying to solve or use as constraints are all linear -- x grams of potatoes has twice as many calories as x/2 grams. The term programming is historical and does not have anything to do with computers -- think programming as in scheduling.

As the name implies, linear programming problems often arise in the logistics and economics fields. For example, you own a chocolate factory and want to make the maximum profit, subject to constraints on demand, supplies, and labor. Or more generally, many commodity markets (e.g., soybeans, wheat, etc.) can be modeled with a linear program.

An Alabama sheriff who was recently convicted of starving his prisoners could have benefited from using linear programming. Alabama sheriffs are allotted $1.75 per prisoner per day for food, and get to keep the extra cash they don't end up spending. Instead of computing the optimal diet for his prisoners (for which he could have pocketed $0.79 per prisoner per day), he chose to skimp on their diets instead.

(Of course, the optimal diet is kind of disgusting, consisting of carrots, peanut butter, air-popped popcorn, baked potatoes, and skim milk. It may be optimal for cost but it's decidedly sub-optimal in terms of taste! Construct your own diet here.)

Suppose you want to make the maximum amount of profit from making widgets at your factory. You have labor, material, and shipping costs, which can be represented by linear functions of the number of widgets. The problem is, you can't make 5247.68 widgets: you have to make an integer number of them.

Problems that contain both integer and continuous variables are known as mixed-integer programs. Our diet example might be better posed as a mixed-integer linear program -- it would make more sense to eat an integer number of bananas than to eat 128.6 grams of banana (for example).

Mixed-integer linear programs are hard to solve -- they have been shown to be NP-hard. But for many of these problems, you can use a relaxation into a linear program (relax the requirement that the integer variables must be integer) as a lower bound, and find the solution using a branch-and-bound, branch-and-cut, or branch-and-price method.

Branching has to do with dividing the problem domain into pieces. If we have an integer variable constrained to be between 1 and 10, for example, we could branch it into two pieces, one containing the domain 1 through 5, and the other containing 6 through 10. If we know that the global bound from the linear program is bigger than the solution for any of the integer solutions in a given branch, we can remove that branch from consideration. We would then further subdivide the active branch until we are able to find a unique solution.

This type of branching algorithm is inherently parallelizable. First, we would solve the relaxation of the mixed-integer problem and broadcast it to all processes. Then, we would assign branches to processes, which would then eliminate or further subdivide branches as appropriate. If done naively, we would end up with all the work being done by the one process that originally owned the branch containing the solution, while all the rest of the processes are idle. Instead, good parallel implementations of branching algorithms adaptively reassign new sub-branches to idle processes.

I am working on solving a big mixed-integer linear program that represents the biofuel supply chain infrastructure. I know next to nothing about biofuel production, but my other collaborators do. My expertise lies in solving the problem in parallel on leadership supercomputing resources. I'm really excited about solving these complicated problems at this large scale!


* Note that I totally made up these numbers and if you're actually wanting to get back into shape you should consult your physician, not an applied mathematician.

Productive Week

Despite the fact that I took a sick day on Monday, and felt crappy for much of the remainder of the week, I accomplished a lot at work last week. I successfully compiled and ran a code I'd been trying to get working for three weeks, which felt really good. Also, I did some performance runs on my main project that I'd been meaning to do for a really long time and finally got around to doing. And finally, I started working on implementing some I/O for one of my other projects.

I don't know if I have it working right, but I was pleased that I got a good start on it. This project is particularly challenging because I don't really understand what the code is doing, and it's written in Fortran (not my first choice of programming languages, let me tell you...). What I have to do for them is to convert their checkpointing I/O from MPI-IO to another type of I/O. This is hard because this new type of I/O is completely foreign to me; in fact, I am kind of a guinea pig because I am the first person outside of the developers to try to use it. Luckily the developers live down the hall from me, so I can just talk to them when I run into trouble. The documentation isn't very clear yet (because, as I said, I am a beta tester) and I will have lots of feedback for them once I finally figure out what I'm doing.

But I can see that this new I/O system is extremely powerful and will make people's lives a lot easier. Something else that's bogging me down in converting from MPI-IO is deciphering from the I/O subroutines just what it is that the code developers want to be output and input. An analogy I used yesterday is this: I know that they want to write a capital letter of some sort, but instead of them just saying "I want to write out the letter A," I instead have only clues about how the letter is constructed: "A diagonal line beginning from the bottom and going up and to the right; another diagonal line beginning where that one ends and going down and to the left; and a straight line left-to-right connecting the two at the midline." From that, I follow the instructions and realize that they're writing a capital A. But it is hard to decipher.

Luckily I have a friend and colleague who works in this field and is proficient in Fortran. She's also supposed to be working with me on this project, although she works on different aspects than I do. So I have talked to her and had her help me decipher what they are trying to do. In one case, she was able to crack the code and figure out what the heck was going on, and determined that they were doing the output really inefficiently, kind of like saying "create a diagonal line from the bottom left corner to the midline, then create a diagonal line from the top and center down to the right, to the midline, then create a diagonal line up and to the right from where you ended the first stroke on the midline, then create a straight line left-to-right connecting the two diagonal lines at the midline, and then create a diagonal line from the right end of the midline horizontal line down to the lower right corner." Yes, that makes a capital A, but it's a kind of inefficient way of going about it.

So anyhow, I should be ready to start compiling this new code sometime next week. I'm pretty excited about it, although I know that there will be many errors to fix. But it feels good because I know this work has the potential to really transform their science capabilities.

Coming Attractions

This is the month of the big conference for which a colleague and I are in charge of placing thousands of signs. I have traveled four times this year to the conference planning meetings, and gotten well acquainted with the Austin (Texas) Convention Center. It's a big place, so we're going to be doing a lot of walking in order to place all these signs.

This conference is the biggest conference in the high-performance computing field, with nearly 10,000 attendees. I think we have almost everything done. There are just a few signs we have to finish up. We've also ordered twenty blank signs, for things we might have missed.

I've managed to convince my better half to come along too, and help us place the signs. He (foolishly?) agreed to help. We're leaving Vinny with my dad again, this time for ten days. The conference is the week before the week of (American) Thanksgiving. We're leaving for Austin on the Friday before the conference, and coming back the Saturday after it's over. Luckily, we're flying in and out of Lexington, so that will make things easier for my dad in terms of dropping us off and picking us up. Unluckily, I had to make Jeff's flight arrangements separately from my own (which were made by my workplace), and by the time I went to do his, my return flight was sold out, so he's taking a different flight back to Lexington than I am. The good news for him is that he leaves an hour later than I do and gets in an hour earlier. The bad news is that we're not together.

In preparation for the walking we're going to do at the conference, Jeff and I purchased some (expensive) walking shoes this past weekend. We went to the New Balance store and were fitted for some shoes. Jeff declared that his shoes were heavenly, like walking on air. Mine are comfortable, but not quite that nice.

I think we should have a lot of fun. I may get the opportunity to meet up with a fellow blogger, and if I do and assuming it's okay with this person, I'll let you know all about it. But even if I don't get to do the meet-up, there are so many things to do and people to see that I know we won't be bored!

Career Day

Thanks to everybody for all your advice on career day. I gave a 30-minute presentation full of slides with interesting pictures. I began by asking who liked math. I got a show of a few hands. Then I said, "I'm glad that some people here like math. But for the rest of you, I have bad news. Any career is going to involve math to a greater or lesser degree. And generally speaking, the more math that's involved, the more money you'll make."

I had some pictures from popular television shows to get them interested. I asked them if anybody watched "Gray's Anatomy." There was a show of a few hands. "Well," I said. "What if you're a doctor and you prescribe 200 mg of a very potent medicine instead of 200 µg?"
I also had a picture from the show "CSI." Again, I asked if anyone liked that show. And then I asked what would happen if you were working on the very last DNA sample and you added 5 mL of solvent when you meant to add 50 µL? In both of these cases, knowledge of math is vital for job success.
Then I talked about my job. I told them about our supercomputers, giving the really cool numbers about how many flops* the machines do; our huge, expensive cooling system (capable of cooling 640 large houses); how much our power bill is ($5-7 million/year), etc.

And I told them about the science. I showed some pretty pictures of various applications, starting off with combustion. I asked who got to school today thanks to the power of internal combustion. There was some confusion, but after it was established that I was talking about engines, just about everyone raised their hands. Then I asked who had heard their parents complaining about the high price of gas lately. Everyone raised their hands for that one. Well, I said, that's because some of the best cars, such as mine, get maybe 30-40 mpg. But wouldn't it be cool if we could get more like 300 or 400 mpg? That's why we study combustion.

I ended the presentation by talking about my educational background and then what they could do if they were interested in a career like mine. I told them what sort of educational activities they should do but above all encouraged them to be persistent and don't let other people discourage them. I also showed a slide with pictures of some of the youngest and most attractive people I work with. In addition to being more visually appealing, they are more diverse, and it is part of my mission as a member of an underrepresented group in computer science to encourage students from underrepresented groups to join us. (I showed pictures of three people, two of whom were women, and two of whom were African-American.)

After my presentation was over, I got quite a few good questions. One joker asked something about my advanced age, but otherwise the students were genuinely curious. I felt that career day was a success and I'm grateful for all your advice.


* A flop (in addition to being a bad joke that nobody laughs at)** is a FLoating-point OPeration -- basically, any arithmetic operation involving numbers with decimal points, such as 1.1+1.1. Our big machine does 263 teraflops per second, or 263 trillion floating point operations per second. If everyone in the world were capable of doing one floating point operation per second, and we all worked together, it would take us nearly half a day to do what it takes this machine one second to do.

** Standard leadership computing facility tour guide joke.

Growing the "Computity"

Something fun that I get to do in my job is give tours. My boss doesn't want me to do more than one a week, and because of his prohibition, I give tours infrequently enough that they are fun every time. I give a 15-minute spiel on the "observation deck" overlooking our machine room, before escorting them upstairs to the visualization lab.

There are some standard tour guide tricks that I perform. If you tour any cave, there are standard cave tour guide jokes (such as the wishing rock... the rock you wish you hadn't hit your head on), and likewise there are standard leadership computing facility tour guide jokes.

I make the jokes to keep people awake and interested. But I hope that I do more than provide light entertainment to all our visitors, but especially the students.

In particular, I hope that my words reach deeper than a light-hearted tickling of their funny-bones. I hope that some of the students who visit come away with new ideas about their futures. I hope that they discover that supercomputing is a fascinating field. I hope they can see all the things I love about my job, and seriously consider a career in high-performance computing. I hope that they can see that scientists are normal folks with people skills and good senses of humor.* I hope that I can be a role model, to girls in particular, who can remember me as a counterexample when people tell them (directly or indirectly) that science is not for them.

Even if they don't remember me later in life, I hope that I have planted a seed in their minds, and that someday, some of these children grow up to be computational scientists. The "computity" needs new members!


* Nerd joke: How do you know that you're talking to an extroverted {mathematician, computer scientist, physicist}? Because the {mathematician, computer scientist, physicist} is looking down at your shoes rather than his or her own while talking to you.

Another good (but only tangentially related) joke: How do you know that you're dealing with the mathematics mafia? Because they make you an offer you can't understand.


scientiae-carnival

Things I Love about My Job

I love the work I do for a living. Okay, so the excessive number of PowerPoint presentations, Excel spreadsheets, and Word documents I have to create and/or edit in order to impress Important People -- I could do without. But the science -- that is exciting stuff!

In my job, I work with power users of our supercomputers to get their codes up and running on the big machines. Depending on what the project PI wants, I just help them get started, or I get deeply involved as a member of the development team, or anything in between. These are people who have allocations of millions of CPU-hours, and run big codes that simulate scientific processes that are generally either impossible or too expensive or dangerous to do in the lab.

For example, we have users who simulate supernovae. As I say when I give tours, you can't simulate a supernova in the lab, or if you did, no one would live to tell about it. You also can't go check one out "in the field," because it's (hundreds or thousands of) light-years away and by the time you got there a) you'd be dead, and b) the event would be over. Furthermore, even if you did get there in time, a supernova is... shall we say... inhospitable to human life. So the only thing that astrophysicists can do is take the observations they can make from earth and near-space, combined with their knowledge of the laws of physics, and simulate supernovae on a computer. And there is so much physics involved that these computations require the use of thousands of CPUs for days at a time.

I don't work with the astrophysicists; I work with chemists and nuclear physicists. The nuclear physicists are my new project, so I don't know that much about what they do. But I do know what the chemists are doing, because I've been working with them since I came here as a postdoc.

One of the things they're studying is catalysis. A catalyst is a substance that speeds up a chemical reaction but is not used up by the chemical reaction process. The production of ninety percent of commercially-produced chemicals involves catalysis at some stage or another. You may have heard of the catalytic converter in your car's exhaust system, which converts toxic chemical byproducts of combustion into less toxic chemicals.

From what I understand, the discovery of most catalysts has been more-or-less serendipitous. Somebody accidentally contaminates a reaction, and discovers that the desired chemical reaction still occurs and actually goes faster! But it's inefficient, expensive, and possibly even dangerous to make discoveries in this way. If we instead simulate catalysis on a computer, we can be more systematic about it, and try a bunch of different catalyst candidates for a given reaction, without having to worry about safety or pollution. Then, we can pick the top-performing candidates, and actually try them out in the lab.

Something I really love about this job is the fact that I get to work on projects that make important breakthroughs in many different fields of science. I don't know much more than I've just described about catalysis, yet my work is instrumental in the true experts on catalysis learning even more about it.

Sometimes, the day-to-day stuff, such as tracking down a bug, or figuring out why the code doesn't compile, or why it gives incorrect answers, can be a real drag. But seeing the bigger picture is what makes all that boring stuff worthwhile.

Conference Blogging, Part Three

On Tuesday, I collected a lot of swag and finished up a lot of hunts. I'm now registered to win a laptop, an iPod, a PS3, and a Wii, and probably many other things I can't remember. The thing is, some drawings you have to be present for, while others you don't. If I were more organized, I would have written these things down.

I also went out to lunch with my classmate from graduate school. And I gave him an invitation to the vendor party I was planning to attend that night. We went to the party together that evening. He had never seen such a thing before. At the front of the room, the vendor had an ice sculpture of their logo. There was a lot of delicious but expensive food, and an open bar. I don't know how much money they must have spent on this party, but it was a lot. Many of my colleagues were at this party, and I also saw some more people I knew from way back when.

After the party, I was going to split a cab with a colleague who is staying in the same hotel as me, but he wanted to go out for dessert with another guy, so I tagged along. While we were out, we met up with a Somewhat Important Guy, who said we could all get a ride with a Pretty Important Guy to go back to our hotel. It was going to be a little crowded but it seemed like it would work out. Unfortunately, a Very Important Guy then decided that he wanted to go in the car, so my colleague and I were uninvited. The Somewhat Important Guy uninvited himself and the three of us took a cab back to the hotel.

Yesterday I worked at our booth. I got a big breakfast at a buffet restaurant in my hotel before heading over to the convention center. The buffet was enormous, and the food wasn't bad. I had wanted pancakes, but unfortunately their pancakes were kind of dried out and not very fresh. But they had a chef making omelets to order, so I partook of that.

Standing on a concrete floor really takes a toll on your feet and back. I think that a massage should be a reimbursable expense if you've spent the day working at the booth! I enjoyed talking to people when they came to our booth, and hooking them up with other people who knew more about the topic they were interested in than I did. It was especially nice because people who came to our booth were generally interested in what we do, rather than on the prowl for prizes. We can't give away fabulous prizes like the companies can.

In the evening, I went out to dinner with four men I work with, before coming back to my room and turning in early. There were parties but I was too tired to go out to them. Also, since I'd already had a really big meal that day (breakfast) I figured I should really just eat a salad for dinner, and they don't usually serve those at parties.

Plans for today: go to some of the technical program talks, pick up good tickets for tonight's conference banquet, and go to the banquet. They're having the Blue Man Group perform for us tonight. If you want to see them live inside the theater rather than on a screen outside, you have to get tickets. I plan to be one of the first people in line.

Tomorrow I leave for home. It has been a fun trip, but I am definitely looking forward to being back at home and seeing my family again!