Sometimes a Particle Isn’t Possible

That blob turns into two!
Figure 1. That blob splits into two! This animation shows what happens when we try to construct a single particle (with the given shape) and make it bounce between two mirrors.

Last time, I showed you how you could construct a photon, a light particle, in a configuration of mirrors called a ring cavity. This time I’ll show you that sometimes, you can’t make just one particle—they only come in pairs. And sometimes, the notion of a particle doesn’t make any sense at all. (This post relies heavily on last week’s post, so if you haven’t read that, I recommend you do so.)

Disclaimer: What I’m about to describe is only the simplest case, and I make simplifications for the sake of exposition. It is possible to capture and manipulate single photons between two mirrors for short times if you play tricks. In fact, that work recently won the Nobel prize.

Last time, I showed you what happens when you arrange three mirrors to make a ring. Now let’s see what happens when we bounce light between two parallel mirrors, as shown in Figure 2. This is called a Fabry-Perot cavity.

A Fabry-Perot Cavity
Figure 2. Light (yellow) bounces between two mirrors (light blue).

We’re going to put waves into our Fabry-Perot cavity and see if we can make just one particle. (Spoiler alert: it won’t quite be possible!)

As I’ve discussed before in some detail, light is an electromagnetic wave made up of electric and magnetic fields. To draw a parallel to our example last week, the strength of the electric field can very roughly be thought to correspond to the probability of measuring a photon. However, there are complications; for example, the quantum-mechanical wavefunction can be imaginary. It’s an experimental and theoretical fact that electric fields are zero inside conducting materials like metals. (This isn’t quite true…the field actually falls off slowly, based on something called the plasma frequency. But we’re making approximations.) Therefore, the electric field that makes up a photon must be zero at the metal mirrors.

This means that if we put a wave of light between the two mirrors and look at the strength of the electric field (which wiggles), it has to go to its center position at the mirrors, as shown in Figure 3. This restricts the type of wave that can fit in between the mirrors. (On our plot, the field is zero when it’s smack dab in the middle of the plot. Above the center line, it’s positive. Below the center line, it’s negative.)

fabry-perot_modes
Figure 3. If you put a light wave (red, green, blue) between two mirrors (dark blue), the wiggles have to end at the mirrors.

Last time, when we added a wave to our ring cavity, the wave travelled uniformly to the right with some speed. That’s not what happens now. Now the wave can’t travel, so the height just grows and shrinks. Let’s look at the longest possible wave that can fit in the cavity, shown in Figure 4. This is called a standing wave.

Fabry-Perot with one wave
Figure 4. Our Fabry-Perot cavity with the largest possible light wave sitting in it. The wave just grows and shrinks in time.

(There are complications, of course; I’m completely ignoring what the magnetic field is doing. But for explanatory purposes, this is enough.)

Now we can add additional waves to the cavity. If we add the first five that fit (in special amounts based on a mathematical calculation using Fourier analysis), we get a plot that looks something like Figure 5.

fabry_perot_n5
Figure 5. The first five largest waves in the Fabry-Perot cavity.

We seem to have some complicated wave motion here! Let’s add even more waves! If we add nine waves to the cavity, we get something like Figure 6.

Nine waves
Figure 6. Nine waves in a Fabry-Perot cavity.

If we add nineteen, we get something like Figure 7.

fabry_perot_n19
Figure 7. The Fabry-Perot cavity with 19 waves in it.

Now what’s happening is beginning to become clear. If we extrapolate to Figure 1, we see this:

We attempt to put a wave with a particle-like shape into our cavity, but it splits into two waves which fly apart, reflect off of the mirrors, pass through each other, and continue reflecting for all eternity.

In this case, it’s not possible to put just one particle in between the mirrors.

Sometimes Particles Just Don’t Make Sense

The example I’ve just described highlights a problem with the standard popular narrative of particle-wave duality. We’re told that particles sometimes act like particles and sometimes act like waves. But if this were true, a single particle would never split into two just because we dropped it between two mirrors. The truth of the matter is that everything is a wave. It’s just that sometimes, like in last week’s experiment, waves can be made to act like particles.

But this week’s experiment shows us that sometimes, waves can’t be made to act like particles–at least, not a single particle. And sometimes they refuse to behave like particles at all! What all of this means is that there are conditions where particles cannot exist. For example: We think that, about 13.8 billion years ago, the universe underwent a period of rapid inflation. During this expansion, for reasons that I promise to try to address in the future (see Mukhanov and Winitzky), the very notion of a particle broke down. In the inflationary period, the packets of waves that make up particles simply could not form.

Related Reading

Sources

I know I’ve been lazy about citing my sources on this blog and I should be better about it…even when the sources are not layperson-legible. So, for that reason, I offer the intrepid student a list of introductory texts he or she can use to learn more.

  • Introduction to Electrodynamics by Griffiths offers a comprehensive introduction to electromagnetic theory (e.g., how light behaves).
  • You can also find a simpler, more accessible introduction in the Feynman Lectures on Physics, which are available for free online.
  • A Fabry-Perot cavity can be approximated as a particle in an infinite square well. This problem, as well as particle wave duality and basic Fourier analysis, are all covered at an introductory level in the excellent text Modern Physics For Scientists and Engineers by Taylor, Zaphiratos, and Dubson.
  • A more advanced student may want to check out Introduction to Quantum Mechanics by Griffiths.
Posted in Physics, Quantum Mechanics | Tagged , , , , , , , , , , | Leave a comment

What’s in a Particle?

photon identity crisis
This photon doesn’t know whether it’s a particle or a wave. (Unknown source.)

If you’ve read or heard anything about quantum mechanics, you’ve heard the phrase “particle-wave duality.” The common wisdom is that this means that particles sometimes behave like waves and sometimes behave like particles. And although this is right, it’s a bit misleading. The truth is:

Everything is always a wave. It’s just that waves can be made to behave like particles.

To see what I mean, let’s actually show how one can make a set of waves behave like a particle. Specifically, let’s show how a set of light waves can be made to behave like a photon, a light particle.

Light Goes Round

Just to be concrete, let’s talk about light that bounces between a special configuration of mirrors. It looks something like this:

a ring cavity
The configuration of mirrors we’re considering. The light (yellow) starts at mirror A (light blue), bounces off of mirrors B and C, and ends up back where it started. The process repeats forever.

The idea is to configure three mirrors (light blue) so that the light (yellow) bounces around in a loop so that it ends up in the same place that it started from. In optics, this is called a ring cavity. It’s often used to make a type of laser called a ring laser.

We can represent the path of the light (which lives in two-dimensions) as a position along a single line. All we have to do is demand that the lefthand side of the line be the same point as the righthand side of the line so that it wraps around to where it started, as shown below. This is called a periodic representation.

ring-cavity-flattened
The ring cavity reduced to a single line so that the path of the light starts at the left and ends on the right… the left and right points represent the same point.

So, given our periodic plot of the path of the light in the cavity, what does a light wave look like? Since the wave has to wrap around to where it started, the wave on the left side of the line must look the same as it does on the right… In other words, it has to become itself after it travels around the cavity, as shown below:

sine it!
A sine wave in the ring cavity. The left side of the wave looks the same as the right because it must be periodic.

One important consequence of this periodicity is that the waves in the cavity can’t be whatever they want. Only certain waves fit. In the figure above, if the wave stopped a little earlier on the right (say at the peak, the highest point), as shown below, then the right and left sides of the wave wouldn’t be the same. This would obviously be a problem.

sinfivex_trunc
This wave doesn’t fit in our ring cavity because the left and right sides are not the same.

 

Now, given a bunch of light waves that fit in our cavity, we want to combine them in such a way that we get a particle travelling around the ring in the cavity. An important idea that we’ll need is the principle of superposition. 

The Superposition Principle

I’ve previously discussed wave interference and the superposition principle, so if you remember my previous discussions, feel free to skip to the next section.

Imagine waves as wiggles on a very stretchy string. If I try and push up on the string (make a wiggle that goes up) and you try and push down on the string (make a wiggle that goes down) at the same time, neither of us ends up moving the string as much as we intended. This is called destructive interference. Similarly, if I push up on the string at the same time that you push up on the string, we’ll probably stretch it quite a lot. This is called constructive interference. The process of overlaying one wave over another is called superposition.

Interference between two waves on a string
If we both try to make waves on a string, we may interfere with each other. If, as in the image on the left, we both try making the same wave, we may get a bigger wave than we intended. This is called constructive interference. If, on the other hand, we try to make waves exactly offset from each other, we may completely negate each others’ efforts. This is called destructive interference (source).

Light waves work the same way. If we make two waves overlap

What’s in a Particle

Okay, so let’s build our particle! As a first step, let’s put the largest wave that can possibly fit into our cavity, shown below. Note how the height of the wave on the left is always the same as the height of the wave on the right.

ring_cavity_n1
A single, low-frequency, wave travelling through a ring cavity.

Now, we add more, higher frequency, waves to the cavity. (By higher-frequency, I mean the waves have more wiggles in them.) If we take a wave that has exactly twice the number of wiggles as our first wave and add the two waves together, we get something like this:

ring_cavity_n2
Two waves superposed in the ring cavity. Already we start to see some particle-like structure.

Interesting! Now we get a big wiggle and a small wiggle. Perhaps that big wiggle will become a particle?

(Note that I added a wave of a specific height to the first wave. There’s a lot of math involved in knowing precisely what height to add. I’m going to completely ignore that detail for now.)

After we add five waves to the cavity and sum up the wiggle heights, we get:

ring 5
Five waves superposed in the ring cavity.

Now there’s one wiggle that’s clearly much bigger than the others. If we add enough waves to the cavity, we can make that wiggle all we can see:

ring_cavity_n20
20 waves superposed in a ring cavity.

Wow! That doesn’t even look like a wave! What is that? That, my friends, is a particle. The point where the peak is highest represents the average position of the particle and the width of the peak represents the quantum uncertainty in the position of the particle.

(Actually, the little wiggles around the peak are still there. They’re just too small to see in my plot. In principle, you can get rid of them entirely by adding up infinitely many waves.)

Enter Heisenberg

What if we wanted to make the peak narrower, thus making it possible to measure the particle’s position more precisely? Well, you might have noticed that our central peak got narrower as we added more waves to our ring cavity. This means that we would need to add more, increasingly wiggly, waves to the cavity to make the peak narrower.

How do we interpret that? We know that the number of wiggles in a wave determines both its energy and its momentum, meaning that the particle is not only made up of many waves, but has many different energies.

It has an average energy, of course, and an average momentum. But if we measure the particle, we might not measure that energy or that momentum. Instead, we’ll measure each energy some fraction of the time. The percentages look something like this:

energy-distribution
The percentage of the particle that has a given energy.

This is a visible manifestation of the Heisenberg uncertainty principle. If we want to know the particle’s position better, we need to add waves with different energies to it, meaning that it has more energies and we know the energy (and thus the momentum) less well.

Particles Can Act Like Waves

So I’ve just described how we can make a bunch of waves like a particle. But, of course, a bunch of particles can wiggle to make a wave. This is, after all, what’s going on when you wiggle a string, since that string is made up of particles. So you might ask… can you make a wave out of particles, add a bunch of such waves together, and get a new particle?

Amazingly, you can! If you add up a bunch of sound waves travelling through a material (which is made of particles which are made up of waves), you can get a particle called a phonon!

So now we’re ready to state the principle of particle-wave duality one last time:

Everything is a wave. But particles can be constructed out of waves… and waves can be constructed out of particles.

Disclaimer: It’s Often Useful to Think in Terms of Particles

I just told you everything is a wave. But that doesn’t mean physicists always think in terms of waves. Often it’s more useful to think in terms of particles. For example, the width of the peak I constructed above can be very narrow on human terms and it can be very difficult to notice or measure uncertainty in the particle’s position. This is why we didn’t discover quantum mechanics until the early twentieth century.

But even at the quantum level, it’s often valuable to think in terms of particles. Richard Feynman’s diagrams, and Werner Heisenberg’s formulation of quantum mechanics, for example, treat particles as particles in some sense. This isn’t inconsistent, however, because one can prove that Feynman and Heisenberg’s formulations imply the wave nature of, well, Nature.

Alright folks, that’s all I have for now.

Play With it Yourself

I generated all of my animations in Python. If you’d like to play with them yourself, you can find my code here:

https://github.com/Yurlungur/make-a-particle

Related Reading

I’ve written about quantum mechanics before. If you enjoyed this post, you might also enjoy the following posts:

  • In this article, I introduce particle-wave duality by describing the experiments that convinced physicists that particles have to be waves.
  • In this article, I describe how Niels Bohr used particle-wave duality to unravel the mysteries of the atom.
  • In this article, I explain how we should interpret particles-as-waves.
  • In this article, I use particle-wave duality to explain quantum tunneling.
  • Everything I just described is based on something called Fourier Analysis. I discuss Fourier analysis in a very similar context in this article.
Posted in Physics, Quantum Mechanics, Science And Math | Tagged , , , , , , , , , , | 2 Comments

The Most Important Scientist in my Life: My Mom

my mom
My mom, holding her published Ph.D. thesis (Acta Genet Med Gemollol 31: 10-61; 1982).

January 6th is my mother’s birthday. As a present, I decided to showcase the first scientist I ever knew—one who I met before I was even born.

Arleen Garfinkle (one day to be Arleen Miller) entered graduate school  at the University of Colorado in the fall of 1973 and graduated in 1979. During that time she developed a battery of tests designed to track a child’s numerical and logical reasoning skills, based on the theories of psychologist Jean Piaget.

Once she developed the test, she gave it (and several other tests) to over 200 pairs of twins aged four through eight and correlated their success rates to other factors, such as their gender and how much their parents emphasized success. One of her most significant findings was that a young child’s ability to learn math was highly dependent on genetics. Another was that gender had no effect on performance—i.e., girls and boys were equally good at math.

Despite being offered a prestigious position at Yale University, my mother left academia to pursue other interests. But to me, she’ll always be my favorite scientist.

While I visited home for the holidays, I sat down with my mom and asked her about her research, her time as a scientist, and her thoughts on science.

Here’s the interview:

J. Let’s start with the research. Can you tell me what your goals were for the study?

A. I was interested in the heritability of the ability to learn math, because my background was in biology and math and I was interested in genetics and math.

J. Can you describe what heritability means?

A. It’s a statistical measure comparing the difference between identical twins and the difference between fraternal twins. The higher number, the more similar identical twins are than fraternal twins.

J. So it’s a measurement of how much a particular trait depends on genetics compared to the environment?

A. Yeah, but it’s a statistical analysis. You’re comparing the differences over all the pairs of twins.

J. Then this study is really trying to address the age-old question about nature vs. nurture. Is that right?

A. Yes.

J. And what would you say were the significant results of your study?

A. There was a significant heritability for the ability to learn math and logical ability in four- to eight-year-olds. But visual memory had no heritability. In addition, for this age range, there were no significant sex differences. And there was also no significant effect of age on the heritability.

J. I remember your thesis said that previous studies showed a gender difference in the ability to learn math…and that this was because those tests had introduced biases. Can you tell me a little bit about what you did to avoid bias?

A. Every child was tested [by] a male and female, so there was no potential administrator sex bias. And they [were all] trained so that they basically had a script so that every child heard the same words and directions.

J. And this was new? People didn’t do that before?

A. Apparently not. I don’t think so. Also, this is an age where sex differences don’t necessarily show up […] although other people found them. I think that’s why we didn’t find any sex differences…because we were very careful to not bias for sex differences.

J. Do you think your result and results like it help contribute to a more gender-equal society?

A. [laughs] I don’t think the general public has any knowledge of this. But if it got out there, maybe. Also, the world is evolving to be more egalitarian. This test was done forty years ago.

J. You also tested for environmental factors that influenced cognitive development. What did find there? In general terms?

A. Parental education had an influence […] on numerical and logical thinking, but not on visual memory.  Intellectual/cultural background also had an influence. Age was the most significant factor in the tests, which is not surprising at all.

J. So would it be fair to say that, as far as nature vs. nurture goes, it’s complicated?

A. Oh, it’s definitely complicated.

J. Let’s step back from the details of the research for a minute. Can you tell me why you used twins? Why are twin-studies a useful tool?

A. Because identical twins have the same genetics. Fraternal twins have (theoretically) fifty percent of the same genes. So if you compare the difference between the twins, if whatever you’re testing for is genetic, the identical twins should have a closer score than the fraternal twins. So twin studies are used to compare the difference between identical twins and fraternal twins to get a handle on genetic influence.

J. Very cool. Okay, now I want to ask you not about your research, but about you. Why did you decide to get a Ph.D.?

A. I was teaching high school math and biology, and although it was very emotionally fulfilling…I wanted something more intellectually stimulating. And I combined my interest in biology and my interest and aptitude in math. I was interested in not just “adult” stuff, but in the development of the ability to learn math, and that’s how Piaget got into the mix.

J. What about math and biology appeal to you? Why did you decide to devote years of your life to them?

A. Because I was good at math and it was fun for me, and biology is fascinating, so I put the two together.

J. Why is math fun for you? Is it a puzzle…or is there something else?

A. Yeah, it’s kind of like a puzzle. It’s a challenge and you know the answer is there somewhere…and there’s often more than one way to get the answer, which lets you be creative. I can discuss that further.

J. Please do.

A. When I went to teach math in Sierra Leone, the students in Sierra Leone in high school were taught with the old-fashioned British method where they memorized how to do something. And if you tried to get them to do it a different way to find the same solution, they couldn’t do it. Like a recipe, they memorized how to solve an equation. So my big challenge in Sierra Leone was to teach these kids how to think mathematically. Get them out of the habit of “there’s only one way to solve a problem.”

J. That sounds hard.

A. It was hard because these kids were teenagers already and they were set in their ways. But most of them got it. For them, my teaching was really hard because they didn’t know how to think mathematically.

J. What strategies did you use?

A. I don’t remember…games, puzzles.

J. While you were working towards your Ph.D., did you perceive any kind of sexism? Not necessarily from your committee or your professors, but from society or the bureaucracy of the university?

A. Hm…I don’t think so. Not that I can remember. When I was at Berkeley, where I started [my undergraduate degree], there was definitely an element of being surprised that I was a math major.

J. Surprised “good” or surprised “bad?”

A. Sex bias. All my classes were many more men than women.

J. It’s still that way in my math classes. And my female friends say that that creates an intimidating environment. Would you agree?

A. I wasn’t intimidated. I do have an experience that I could share with you. When I was a junior or a senior in a math class where you had to do proofs, I skipped a step [on an exam] because I understood it […] and my professor accused me of cheating. He said, “There’s no way you could do this without that step.” That didn’t seem sexist to me at the time, but maybe it was. It made me very angry. On the other hand, it just proved I was smarter than he was. But I didn’t think of that at the time.

J. On that note, would you have any advice for a young woman, perhaps entering college, who would like to study science or math?

A. Get to know a professor in a class you really like. You have to do well and get to know them. And they’ll be an advocate for you.

J. That’s good advice. I’ve had that experience.

At that point, the interview basically ended. Thanks, Mom! And happy birthday!

Posted in Biology, Science And Math | Tagged , , , , , , | 1 Comment

Pope Francis says Evolution and the Big Bang are Compatible with Catholicism

Pope Francis (left) and Georges Lemaitre (right)
Pope Francis (left) and Georges Lemaitre (right). Source: Wikimedia Commons

You’ve probably heard, the news. Pope Francis has announced that Big Bang cosmology and evolutionary theory are compatible with Catholicism and “may even be required.”

This is, of course, wonderful news. It’s evidence that science and religion are not necessarily incompatible and that people of faith can modify their beliefs based on the evidence around them.

But it should have been this way all along. Indeed, it originally _was_ this way. One of the people who developed Big Bang cosmology, Monseigneur Georges Henri Joseph Édouard Lemaître was a catholic priest who believed that his studies of physics brought him closer to the mind of God. Indeed, Pope Pius XII completely accepted Big Bang cosmology when Lemaitre developed it, even going so far as to claim that it supported catholic beliefs.

At the same time, Pius XII declared that evolution was not at odds with Catholic beliefs. 

What happened?

Nothing went wrong! Francis was citing long-standing Church policy. The Catholic church has always accepted evolution, as I was surprised to learn.

Our Story Isn’t Over

The astute reader will remember that there may not have been a Big Bang. We now believe that instead, the early universe may have undergone a period of extremely rapid inflation. To learn about the discovery of the Big Bang and why we feel it might not be true, check out my three part series on the topic:

Posted in Astrophysics, Physics, Science And Math | Tagged , , , , , , | Leave a comment

Hiatus

I am buried in homework
I am buried in homework

Hi everyone. You probably haven’t heard from me in a while. This is because I have been completely overwhelmed by class work this semester, which has prevented me from doing the things I want to do, like blogging and doing my own research.

For the time being, I don’t think I can expect myself to blog every week, or even every other week. So I’m putting the blog on hold until the semester ends (which should be around the holidays).

As always, thanks for reading, everybody.

Posted in Uncategorized | Leave a comment

What Space Projects Excite Me: Multi-Messenger Astronomy

The remnants of a supernova found in 1987
The remnants of a core-collapse supernova discovered in 1987. (Image credit: ESO / L. Calçada. Via http://scienceblogs.com/startswithabang/2013/05/24/how-to-find-your-very-own-supernova/)

A few weeks ago, awesome blogger and space advocate Zain Husain asked me to contribute to a roundup post he wrote. He contacted a bunch of people (most of them much more prestigious than me) and asked them one question:

What NASA or space project are you most excited about and why?

You can (and should) read everybody’s response to Zain’s question on his blog, here. However, I wanted to expand on part of my answer and tell you why I’m excited about multi-messenger astronomy.

Supernova Supernova

It all starts with the title image above. That’s an image of SN 1987A, the first supernova discovered in 1987. This is an example of a core-collapse supernova, where a star runs out of nuclear fuel and implodes on itself to form a black hole. (There are other types of supernovae, too. For a nicely accessible review, see this article.) After the implosion, the shockwave creates an explosion which we call the supernova.

SN 1987A is really special.  It is the only core-collapse supernova in the last century to have exploded close enough to Earth that it could be seen with the naked eye—only 168,000 light years away! But, amazingly, we didn’t detect SN 1987A from its light. We detected it because of the high-energy subatomic particles it gave off.

When a core-collapse supernova explodes, it gives off most of its energy in the form of tiny, extremely energetic particles called neutrinos. On Earth, we can only make neutrinos in supercolliders like the LHC. But in space, things are wild, and neutrinos are generated in all sorts of cataclysmic events.

For me, this is why SN 1987A is special.

Multi-Messenger Astronomy

When we talk about astronomy, we imagine using light. We think of an astronomer pointing a telescope into the sky and looking through its eyepiece. Things are more complicated nowadays, of course. We shoot telescopes into space. We take pictures in the infrared and the ultraviolet. But in general, we’re still looking at light to see space…right?

For now, this is still roughly true. But scientists are increasingly moving towards “multi-messenger astronomy,” where astronomers studying some object in space look at the light it emits, the subatomic particles it emits, and even the ripples in spacetime that it causes.

Here are two exciting projects that are just coming online (or came online recently) that move astronomy in this direction.

Advanced LIGO

We know from Einstein that space and time are not separate things, but intertwined to form a single spacetime. And this spacetime can be curved or warped, which we perceive as a distortion of the very notion of distance. The motion of large objects creates “ripples” in spacetime which we perceive as distance itself oscillating in time. We call these ripples “gravitational waves.”Check out this video of a simulation of two black holes colliding and the gravitational wave signature that can be extracted:

Since a gravitational wave is a warping of how we measure distance, we should be able to detect this warp with a big enough ruler. And we’re making a bunch of gigantic rulers to do just that. Meet Advanced LIGO, the gravitational wave observatory:

LIGO Luisianna
Advanced LIGO in Louisiana. (Source: http://www.ligo.caltech.edu/)

Actually, this is only one of the tow Advanced LIGO systems. This one is in Louisiana, but there’s another in Washington State. The coolest thing about LIGO is that it detects gravitational waves. The second coolest thing about LIGO is how it does it.

Light makes an extremely good ruler and LIGO takes advantage of this. It’s essentially a four-kilometer-long giant laser. If that’s not cool, I don’t know what is.

I know this has been a bit vague, so I promise I’ll write a more in-depth article on gravitational waves and LIGO in the future.

Ice Cube

The IceCube Laboratory on the Surface of the Ice
The IceCube Laboratory on the surface of the Antarctic ice (source: IceCube)

As I mentioned above, astrophysical events like core-collapse supernovae emit subatomic particles called neutrinos. Neutrinos are tricky little things, though. Just as X-rays pass through walls, neutrinos pass through miles of solid rock and meters of dense lead. X-rays are stopped by bone and metal and can interact with our bodies, but neutrinos pass right through bone, so they’re completely harmless. Thus, if we make a neutrino detector, the probability that we’ll stop and detect a given neutrino passing through our detector is very small. To catch even one neutrino, then, we need to cast a very wide net.

And when I say wide, I mean WIDE.

Just recently, our widest net came online: the IceCube, a neutrino observatory at the South Pole. In the case of IceCube, our net is one cubic kilometer of detector dug into the ice of the South Pole. This should allow us to detect more energetic neutrinos than ever before. For a sense of scale, the IceCube collaborators helpfully diagrammed the under-ice structure next to the Eiffel Tower:

IceCube Array
IceCube underneath the ice. Source: the IceCube Collaboration.

Applications

I mentioned supernovae at the top of the article for a reason: We still don’t completely understand the nature of core-collapse supernovae, and neutrino and gravitational wave observations would really help us understand these objects better.

But the applications are far wider than that. Neutron stars are some of the densest things known to man; they’re held apart simply by the Pauli exclusion principle. However, it’s very hard to make predictions about this exotic fluid they’re made of. Hopefully gravitational wave and neutrino observations would help us understand them better. The same goes for black holes, which emit gravitational waves and neutrinos.

Thanks, Zain!

A big thanks to Zain for putting together his post and prompting me to think about this. Zain puts a lot of work into his incredible blog, and it shows.

Related Reading

This is one of many articles I’ve written that involve general relativity. If you’d like to know more, check out these articles.

  • In this article, I talk about special relativity and how it implies that space and time are unified in a single spacetime.
  • In this article, I introduce general relativity as a way to travel faster than light.
  • In this article, I discuss the geometry of spacetime.
  • In a pair of articles here and here, I answer some questions about general and special relativity.
Posted in Astrophysics, Physics, Relativity, Science And Math | Tagged , , , , , , , | Leave a comment

Non-Digital Computers

Non-Digital Computers

This is the last installment of my many-part series on computers. Last time we used the notion of a Turing machine to define what a computer is. We discovered something surprising: that not all computers need to be digital, or even electronic! A computer can be mechanical,  made of dominoes, or even just a rules system in a card game.

To give you of a flavor of how inclusive the definition of a computer really is, I’ll now give you a whirlwind tour of some notable examples of non-digital computers.

The Antikythera Mechanism

Antikythera
A piece of the Antikythera Mechanism. (source: Wikipedia)

In April of 1900, Greek sponge divers found a shipwreck off the coast of Antikythera. They found a lot of artifacts aboard the ship, but by far the most valuable piece was a device made of bronze gears. This is the Antikythera mechanism, and it’s not only the oldest known complex gear mechanism, but the oldest known purpose-built computer.

The Antikythera mechanism seems to have been made around 100 BC. It seems to have been designed to predict the motions of stars and other celestial objects. Scientists and historians are still studying it, but some replicas have been attempted.

To learn more, check out the Antikythera Mechanism Research Project’s website and their promotional video:

The website.

The video.

Charles Babbage’s Analytical Engine

Analytical_Engine_(2290032530)
A piece of Charles Babbage’s analytical engine, constructed by his son in 1910. (Source: Wikipedia.)

In 1837, inspired by his successful creation of a mechanical calculator (the difference engine—see the title image of last week’s post), polymath and all around amazing dude Charles Babbage designed a fully programmable mechanical computer called the analytical engine. This is widely regarded as the first fully programmable computer.

The mathematician (and countess) Ada Lovelace corresponded with Babbage regarding his analytical engine and she is credited with much of its theoretical underpinnings. She also designed the first and only algorithm for the device, making her the world’s first computer programmer.

Unfortunately, because of the huge scale of the analytical engine and the precision with which the parts needed to be machined, Babbage never finished constructing it.

Tide-Predicting Machines

kelvin tide predictor.
A tide-predicting machine by Lord Kelvin. (Source: Wikipedia)

In 1872, physicist Lord Kelvin developed a mechanical computer to predict the tides.

The Enigma Machine

enigma machine
An Enigma Machine. (Source: Wikipedia)

In World War II, the Axis powers encoded and decoded their military orders using an electromechanical computer called an Enigma machine. Enigma was so sophisticated that the code could be changed by programming the machine. Some historians credit the Allied victory to the help of Alan Turing and the world’s first true digital computer, Colossus, which allowed the Allies to crack Enigma’s famously difficult code.

For more information, check out Numberphile’s excellent video on the device.

Other Examples

Some more, less historically interesting examples include:

  • It’s possible to make arbitrarily good approximations of purpose-built Turing machines using dominoes. They’ll never be as good as a real Turing machine, though, because they can only write to a bit in memory once (by knocking down a domino). Check out this awesome video, again by Numberphile.
  • In the card game Magic the Gathering, one can construct a situation where, just by following the rules, the players become components in a universal Turing machine. The “mathematical” proof is here.
  • It’s possible to build a fully working computer using the physics engine of the video game Minecraft. Here’s one guy’s computer. And here’s a tutorial on how to make your own.

Any I Missed?

If you know of any cool non-digital computers I missed, let me know in the comments!

Related Reading

This is the sixth article in my multi-part series on computing. These are the other parts:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.
  • In this article, I show how to use triodes to make logic gates.
  • In this article, I explain how to build computer memory.
  • In this article, I explain how a Turing machine works.
  • In this article, I use the idea of a Turing machine to try and nail down what exactly a computer is.

EDIT: Cracked.com covers this topic!

I’m a big fan of the comedy website Cracked.com. They often teach you something in a pretty entertaining way. So imagine my surprise when I discovered this morning that they ran an article covering the same idea as this one, but with some really awesome examples of pre-microchip computers that I’d never heard about!

It’s a beautiful article by the awesome ex-physicist Luke McKinney. You can check out his blog here: lukemckinney.net

Without further ado, here’s the article:
http://www.cracked.com/blog/4-amazing-computers-made-before-microchips-existed/

Posted in Computer Related, Electronics, logic, Mathematics, Physics, Science And Math | Tagged , , , , , , , | 1 Comment

What Is A Computer, Really?

Charles Babbage's Difference Engine
This  a difference engine, built from Charles Babbage‘s blueprints. (Source: Wikipedia)

Look at the picture above. Believe it or not, that person is operating an extremely sophisticated mechanical calculator, capable of generating tables that evaluate functions called “polynomials.” Although a graphing calculator can do that, a pocket calculator certainly can’t. The device above is a mechanical purpose-built computer!

This article is the next installment of my series on computing. In the previous parts, we learned about Boolean logic, the language computers think in. We then learned how to implement this logic electronically and, using our newfound understanding of electronics, how to make computer memory so that computers can record results of calculations. Finally, last time, we discussed a theoretical computer called a Turing machine (named after, of  course, Alan Turing). It is believed that the answer to a problem can be computed if and only if one can build a Turing machine to compute it.

This time, we use our discussion of the Turing machine to try and nail down what a computer really is.

(If you haven’t read the article on the Turing machine, I recommend you do so now. I’ll be relying on it extensively. It’s here.)

The Universal Turing Machine

Recall from our discussion last time that a Turing machine has three parts:

  1. A ticker tape consisting of cells that can be written in. We select an alphabet of symbols we’re allowed to write. For example, you could easily use the real alphabet or every character available in unicode—whatever you like.
  2. A “head” that can read from the tape and write to it. The head also has a finite number of “states” or modes. You can think of these in the same way as the modes available to your printer at home: a “scan” mode, a “print” mode, mavbe a “fax” mode. These determine what the printer does with the input it’s given. Similarly, the state of the head determines what it does when it reads a symbol.
  3. A rules table. The table tells the head what to do when it reads a symbol off of the tape, given the state it’s currently in.

Given a computable problem to solve, one can design a Turing machine to solve it by constructing an appropriate rules table. But what if we want to go the other way? What if we want to design a Turing machine that can solve any computable problem?

Turing realized that it’s possible to design a Turing machine that can mimic any other Turing machine. The simplest, most obvious way to do this is just add more modes to the head. For example, suppose we had two problems we wanted to solve, problem 1 and problem 2. And suppose we know how to construct a Turing machine to solve each problem respectively: machine 1 and machine 2. And, for simplicity, let’s say that both machines use the symbols “1” and “0” and have three modes, “red,” “green,” and “blue.”

Now let’s construct a new Turing machine, machine 3, with SIX modes: “red1,” “red2,” “green1,” “green2,” blue1,” and “blue2.” We’ll give it the following symbols to use: “1,”0,” “A,” and “B.”

Then we construct the rules table such that if the state is red1, green1, or blue1, and the symbol is either 0 or 1, then machine 3 behaves like machine 1. The rules for the state red1 correspond to the rules for machine 1 in the red state, and likewise for green1 and blue1.  Similarly, if the state is red2, green2, or blue2 and the symbol on the tape is either 0 or 1, then the machine behaves like machine 2.

The only thing we have to do is determine whether the machine uses the states for machine 1 or for machine 2. We do that with the special symbols A and B. If the machine reads symbol A on the tape, it knows to behave like machine 1. If the machine reads symbol B on the tape, it knows to behave like machine 2.

Now machine 3 can solve either problem 1 or problem 2! And we can keep going like this—if we add an arbitrary number of states, we can solve an arbitrary number of problems. A Turing machine that can mimic any other Turing machine (and thus solve any computable problem) is called a universal Turing machine. A universal Turing machine is the standard model of a fully programmable computer.

Can You Build One?

But if we needed an arbitrarily large number of modes to solve all problems and thus make a computer, that would be pretty useless. Since the number of problems we’d like a computer to solve is incredibly huge, it would be impossible to construct a computer with one mode for every single type of problem in existence (including those we haven’t even thought of yet).

So are modern computers only pale approximations of universal Turing machines? Fortunately, no. AI researcher Marvin Minsky showed in 1962 that you can construct a universal Turing machine with only seven modes and a four-symbol alphabet. Later, it was discovered that we only need a binary alphabet (1 and 0) if we use 15 modes. So yes, it’s possible to build a real-life universal Turing machine. That’s good to know, since you’re probably reading this post on one of them!

So What Is A Computer, Really?

We’re finally ready to answer our title question and tie all of this abstract computational theory back to practical electronics. A “computer” is any device that can be shown to be equivalent to a universal Turing machine. (This property is called Turing completeness.) For a device to be Turing complete, it needs the following three pieces, roughly speaking:

  1. A set of logical rules dictating how it should behave given some input. On a Turing machine, this is the rules table. In an electronic computer, it’s the Boolean logic gates we constructed out of vacuum tubes or transistors.
  2. A way to record the results of a calculation and read these results in as new input. On a Turing machine, this is the ticker tape. In an electronic computer, this is the computer memory constructed from electronic flip-flops.
  3. A way to control the device’s logic so that the same input data can be manipulated in many different ways. On a Turing machine, this is enabled by having many modes for the head. I didn’t discuss how to achieve this in an electronic computer, but we’ll suffice to say that it exists.

With these three components, it is possible to construct a universal Turing machine, or at least something equivalent. But notice that these criteria don’t limit us to electronic devices! Any device that meets them can do anything a laptop can do (albeit probably much much slower)!

Next time we’ll take a break from hardcore theory to discuss some cool examples of non-electronic computers.

A Historical Note

Although electronic computers have been shown to be Turing complete, this may or may not have really been considered during their design. Computer pioneer John von Neumann and people the working on early digital computers were certainly inspired by Turing and von Neumann extended Turing’s work. However, modern architectures weren’t really known to be related to Turing machines. It was only later that mathematician Hao Wang demonstrated that electronic computers were Turing complete.

Other Approaches

Turing’s machines aren’t the only mathematical description of what it means to be a computer. Mathematician Alonzo Church developed a completely equivalent description based on the mathematical definition of a function, called Lambda calculus. I find it beautiful, but I’m not going to try to describe it here because it’s very abstract–check out the link if you’re a fellow math nerd.

Further Reading

There are many many resources on the Turing machine, but most skip what’s special about a universal Turing machine. Here’s what I could find.

Related Reading

This is the sixth article in a multi-part series on computing. These are the other parts:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.
  • In this article, I show how to use triodes to make logic gates.
  • In this article, I explain how to build computer memory.
  • In this article, I explain how a Turing machine works.

That’s all for now. Thanks for reading!

Posted in Computer Related, Education, logic, Mathematics, Science And Math | Tagged , , , , , , , , , | 1 Comment

The Turing Machine

Artists rendition of a turing machine
Artist’s representation of a Turing machine. (Source: Wikipedia)

This is the sixth part in my multi-part series on computing. In the previous parts, we learned about Boolean logic, the language computers think in. We then learned how to implement this logic electronically. And finally, we learned how to make computer memory, so that computers can record results of calculations.

Now before we conclude the series, we’re going to take a quick detour into computational theory and the Turing machine.

Alan Turing’s Machine of the Mind

In 1936, mathematician, WWII codebreaker, and all around awesome guy Alan Turing wanted to investigate a problem in formal logic. Specifically, he wanted to find the answer to a question first posed by David Hilbert. Simplistically, the problem is this:

We know from Godel’s incompleteness theorems that some mathematical questions simply do not have answers. But Godel opens up a Hydra’s den. Are there some mathematical questions that have answers… but answers… but answers that it is impossible for a human being or machine to discover, even in principle?

To answer this question, Turing devised a theoretical machine designed to compute the answer to any question one can pose in mathematics. You’ve probably heard of it, even if you don’t know what it does. This is the Turing machine.

To Build a Turing Machine

A Turing machine is a pretty simple device, but it sounds complicated when you describe it. So I think the best way to understand what’s going on is by example. So let’s try a little experiment where we play the role of the “brains” of a Turing machine. I’m going to give you three things and you’re going to manipulate them to form a Turing machine.

First, I’m giving you a tape, say a long ribbon of paper, partitioned into little blocks or cells. With nothing written on it, it looks something like this:

The ticker tape in a Turing machine
The ticker tape in a Turing machine

(In principle the tape could be infinitely long, but we’ll ignore that.)

Initially, the tape WILL have some symbols written on it. It’ll look like this:

The ticker tape I give you.
The ticker tape I give you.

But let’s say I wrote on the tape in pencil. This means you can erase any symbol I’ve written on it and replace it with something else. Just make sure you use pencil!

I’m only going to allow you to write one symbol in each of the cells on the tape. And I’m going to restrict what you can write. Here are the symbols you can use: “1”, ” “, “-“,  and “=”, where ” ” represents a blank space.

Next I’m going to give you a spinner like the one you might get for a game of Twister. Ours will have an arrow that can point at one of four colors: Red (R), Green (G), Blue (B), and Yellow (Y).

You won’t just randomly spin the arrow. You’ll move the arrow to keep track of a color. Let’s start the spinner pointing to red, as shown below.

the spinner I give you
The spinner I give you. Let’s start it pointing to “red.”

Finally, I give you the following table. The table tells you what to do based on the symbol you read on the tape and the color of the spinner. Here’s the table:

The instruction set you have to use.
The instruction set you have to use.

Let’s work through it.

Now, just start by looking at the symbol in the leftmost cell of the tape, as shown below.

The starting state for our Turing machine.
The starting state for our Turing machine.

The symbol is a “1” and the spinner is pointing to “Red.” If you look at your table, you see it tells you to do nothing and just look at the symbol in the cell one to the right. If you do, you see that this symbol is also a “1” and we’re just supposed to move right again.

This process repeats for a while. The instruction table doesn’t tell us to do anything different until we reach the “=” sign shown below.

Where our Turing machine is when things start to get interesting.
Where our Turing machine is when things start to get interesting.

If we look at our instruction set, it tells us to “erase the symbol and replace it with a space” and then “move one cell to the left and change the spinner to point to Blue.” So let’s do that. After we do, the Turing machine looks like this.

Our turing machine after we erase the "=" sign.
Our turing machine after we erase the “=” sign.

Now the rules tell us to replace this symbol with an “=” sign, move one cell to the left, and change our spinner to point to “Green.” Let’s do that. The results are shown below.

Our Turing machine after we erase the "1."
Our Turing machine after we erase the “1.”

Now the rules tell us to move once cell to the left and change the spinner to “Yellow.”T he results are shown below.

Our Turing machine now that we've moved left past the "-" sign.
Our Turing machine now that we’ve moved left past the “-” sign.

Now the rules tell us to erase the “1”, replace it with a blank space, move to the right, and change the spinner to red, as shown below.

Our Turing machine now that we've changed our state back to "Red."
Our Turing machine now that we’ve changed our state back to “Red.”

Well, we know what to do when the spinner points to “Red.” We move right! This continues until we get to the equals sign, as shown below.

Our Turing machine after we reach the equals sign for a second time.
Our Turing machine after we reach the equals sign for a second time.

And we erase the equals sign, as shown below…

Our Turing machine after we erase the equals sign for the second time.
Our Turing machine after we erase the equals sign for the second time.

But now our spinner is pointing to “Green” and we’re looking at a “-” sign. The instructions tell us we’re done!

 So… What?

So what have we done, exactly? Well, our tape started with an expression that looked roughly like

    \[111 - 1 =\]

and we ended up with an expression that looked roughly like

    \[11 -\]

In other words, we used a simple tally mark system to take the number “3” and subtract “1!” This sounds simplistic, but it’s not. We wrote down a set of rules so that given any number of tallies left of the equals sign and any number of tallies right of the equals sign, we can subtract the tallies on the right from the tallies on the left. And we can do so without any thinking at all, just by looking at the rules in our table.

So What’s a Turing Machine?

A Turing machine is only a little bit more general than what we just described. It has three parts:

  1. A ticker tape consisting of cells that can be written in. We select an alphabet of symbols we’re allowed to write. In our simplistic example, our alphabet consisted of “1”, ” “, “-“, and “=” but it could easily describe more symbols. For example, you could easily use the real alphabet or every character available in unicode. Whatever you like.
  2. A “head” that can read from the tape and write to it. The head also has a finite number of “states” or modes. You can think of these the same way you think of the modes available to your printer at home. A printer probably has a “scan” mode, a “print” mode, and mavbe a “fax” mode. These determine what the printer does given some input. Similarly, the state of the head determines what it does when it reads a symbol. In our example, the states were the four colors: “Red,” “Green,” “Blue,” and “Yellow.”
  3. A rules table. The table tells the head what to do when it reads a symbol off of the tape given the state it’s currently in.

Turing postulated that if there is a problem in mathematics that you can find the answer to, you can build a Turing machine that can find the answer. We currently believe this to be true, though the answer isn’t really known. (Aside: this hypothesis is called the Church-Turing Thesis.)

But, more relevantly (for us anyway), a Turing machine is a model of a single-purpose computer. Next time I’ll explain how and explain how to get from this to a fully programmable computer.

Further Reading

Here are some resources on Turing machines.

  • The Wikipedia article on Turing machines is, of course, a good place to start.
  • Mark C. Chu-Carroll has a very nice introductory article on Turing machines, from which I stole my example machine. You can find it here.
  • I-Programmer also has a nice article on Turing machines. It’s clearly meant for programmers and software engineers, but a layperson should be able to follow it. Find it here.
  • You can download a Turing machine emulator for your android phone here.
  • Want to learn how to build a Turing machine with a Raspberry Pi? Learn how here.
  • Google made a doodle Turing machine for Turing’s birthday. It’s archived here.
  • Want to build a Turing machine out of legos? You can! Find out more here.

Related Reading

This is the sixth article in a multi-part series on computing. These are the other parts:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.
  • In this article, I show how to use triodes to make logic gates.
  • In this article, I explain how to build computer memory.

Posted in Computer Related, logic, Mathematics, Science And Math | Tagged , , , , , | Leave a comment

A Parallel Computing Primer

Janus
The Janus Supercomputer at the University of Colorado is one example of a parallel computer.

So, Jonah is moving and he asked me to write a guest post. Jonah’s recent articles about computing prompted me to write about distributed computing. The question I will answer is: how do you go from computing with a sequential program to computing on many core machines (aka Parallel Computation)?

Parallel Computation

First of all, what is parallel computation? In a nutshell, parallel computation is the science which allows you to use a many processors to compute faster. You certainly would want to do this if you worked on the stock market where the faster you are at calculating the faster you can buy and sell and make money. If you are trying render a TV show you’ll want to finish it before it is supposed to air. Many newer computers have many processors in them allowing them to take advantage of this speedup gained from using them.

I now want to discuss what it means to have a sequential program, which is the case when only one processor is used. To solve most problems you have a sequence of steps you must complete to get an answer. For example, suppose you want to find the sum of the numbers:
1 2 3 4 5 6 7 8

Computers can only do binary addition, that is add two numbers at the same time. Because of this we must add only two numbers at a time. Two possible ways are outlined below:

(((((((1 + 2) + 3) + 4) + 5) + 6) +7) +8) +9
or like this
((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8))

The second way might not seem obvious but it lends itself to parallelization so we’ll use it as our primary example. Since we are only adding pairs of numbers we can give each pair a letter to represent it. So, in this case A represents the action of adding 1 and 2 and B represents adding 3 and 4, and so on. It’s a bit more abstract but E equals the sum of the results from A and B and similarly for F and G.

((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8)) = ((A + B) + (C + D)) = (E + F) = (G)

To exemplify the sequential case: suppose you have a single processor which can only do one operation at a time. It would look like a single channel which you could send commands to which would be operated on sequentially.
====================================
CPU 0 | A B C D E F G
====================================

This is called the sequential method where only one processor is utilized.  If each step took 1 second to complete, this code would take 7 seconds. The steps could be performed in other orders as long as A and B come before E, C and D before F, and E and F before G. If this wasn’t the case, you wouldn’t have the output from the steps before and the code wouldn’t work.

Now, the trouble occurs when you have two processors. How do you decide how to run the commands in parallel? This example is pretty straight forward, you can only use commands that have left and right answers available for them. Using the example above, an efficient order could be
=====================================
CPU0 | A | B | E | G
=====================================
CPU1 |  C | D | F |
=====================================

Here A and C, B and D, and E and F are all performed in parallel. We can’t parallelize G as it just adds the two last numbers together and that can only be run on one processor. Now, again if each operation only takes one second then this would take 4 seconds. We seemed to have achieved a 3 second speed up in our code.

Flynn’s Taxonomy

Our example before this outlines one of the most common ways to run a program in parallel. However, there are many way to do multi-processing. To help identify the different types Michael J. Flynn created a taxonomy. His taxonomy, simply called Flynn’s Taxonomy, splits all programs into four groups denoted by SISD, MISD, SIMD, MIMD. You can visualize the taxonomy in the following graphic:

Flynn's Taxonomy
Flynn’s Taxonomy (By Wikipedia’s User:Cburnett)

The four types are separated into if they have one or more of each an instruction set and data set. The four combinations yield the four types in Flynn’s Taxonomy.

The four types with their names expanded are as follows:

  1. SISD – Single Instruction Single Data
  2. MISD – Multiple Instruction Single Data
  3. SIMD – Single Instruction Multiple Data
  4. MIMD – Multiple Instruction Multiple Data

The sequential addition code is an example of the SISD type, and our parallel addition example is illustrative of the SIMD (Single Instruction Multiple Data) type. This is because each processor does the same thing, take four numbers and add them pairwise. However, CPU0 gets the numbers 1 2 3 4 and CPU1 gets 5 6 7 8. This means each set of instructions get a unique set of inputs.

So, you might ask, how do the other two types come into play. Well the MISD case can be an instance when say you have medical records of many patients, and you want to know if your model (A) predicts cancer better than another model (B). You would want to check it on the same data but you want to run two different instructions or models; in this case A and B.

As for MIMD, this usually comes about when processing large amounts of different data. For example, suppose you are Google and you have billions of photographs. If you want to store them in the most compact form possible you’ll probably want to compress them. Since different photos lend themselves to different compression algorithms you might want to compress it with two different algorithms (the instructions) and keep the best one. I’m not saying this is how they do it but it does illustrate an instance where you might use a MIMD type program.

An Example of Parallel Code

Weather simulations need to be fast and accurate. To accomplish the accuracy, software divides the surface of the earth up into little squares. Each square represents the whole area and contains the data for its temperature, humidity, wind, etc. To make the simulation doable the whole area is represented as a single point usually located in the center of the region.

To simulate the weather, the program will move air from such one point to another to represent wind. The wind carries water and clouds which change the temperature and, not to make it sound too simple, changes the weather. By simulating this we can predict to a reasonable extent how the weather will unfold tomorrow.

Of course, if the region is too large it will not reflect the weather accurately. For instance, if the region was chosen to be the size of the US, it would represent all the weather in the US as the same, which certainly isn’t true. The size of a region is usually about the size of a large neighborhood as seen below:

A NWS prediction area
A prediction area for south Boulder. (Credit: NWS www.weather.gov)

There is a cost to choosing a small area, you need more memory to store all the information for all of the regions. Additionally, each time you add more regions you must do computations on those new regions increasing the computing time.

To overcome this, the National Weather Society (NWS) predictions weather on large distributed computer systems putting a few areas onto each computer. Then each computer applies the same instructions to each set of areas progressing the simulation one small amount of time into the future. This is then done many times until the future time is reached.

This way they can have predictions about tomorrow’s weather before tomorrow gets here.

The Trouble With Parallelized Programs

At this point it might seems as if we could continue to use more computers and get better and better performance. This would be nice but we run into the issue that not all code is parallelizable. Remember the sum of numbers problem, the last step required us to use only one processor to add the two final numbers together. In fact if we add more processors to that example we see more steps that can only be run sequentially.

=====================================
CPU0 | A | E | G
=====================================
CPU1 |  B | F |
=====================================
CPU2 | C |
=====================================
CPU4 |  D |
=====================================

Here, if we assume each step takes a second, we use 3 seconds. This means when we have 1 processor it took 7 seconds, with 2 it took 4 seconds, and with 4 it took 3 seconds. It seems as we add more processors we get a diminishing return in speedup. In fact if we add more than four there will be no additional speedup. This fact is called Amdahl’s Law.

"AmdahlsLaw" by Daniels220 at English Wikipedia - Own work based on: File:AmdahlsLaw.png. Licensed under Creative Commons Attribution-Share Alike 3.0 via Wikimedia Commons - https://commons.wikimedia.org/wiki/File:AmdahlsLaw.svg#mediaviewer/File:AmdahlsLaw.svg
Amdahl’s Law showing potential speedup for different parallel portions. (Daniels220 at Wikipedia)

Amdahl’s Law gives us a set of equations which depend of the portion of the code that is parallelizable and number of processors used. The graphic above shows us that for any proportion of parallelizable code, there is an upper limit to the speedup. Past a certain point, it is not possible to get more speed by adding more processors.

This fact has forced people to look for alternative methods to speedup their code. Most of the time they find better algorithms and mathematics which simplify what they must do to solve a problem and this make it run faster.

Conclusion

Parallel computing makes it possible to do large calculations in a timely manner but it is not a simple situation and there are certainly caveats to be aware of. But as computers become more parallel (which is a discussion for another day), parallel computing becomes a bigger and bigger deal. For example, Google recently created a  system for processing big data in an efficient way called MapReduce.

Jonah uses very parallel computers to study gravitational physics and he’ll discuss the intricacies of scientific computing in this environment sometime soon.

Hope this inspired some of you to investigate further. Feel free to ask any questions you might have.

Posted in Computer Related, Science And Math | Tagged , , , , | 1 Comment