Amdahl's Law for speed-up from parallelization

Optimally, the speed-up from parallelization would be linear—doubling the number of processing elements should halve the runtime, and doubling it a second time should again halve the runtime. However, very few parallel algorithms achieve optimal speed-up. Most of them have a near-linear speed-up for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements.

The potential speed-up of an algorithm on a parallel computing platform is given by Amdahl's law, originally formulated by Gene Amdahl in the 1960s. It states that a small portion of the program which cannot be parallelized will limit the overall speed-up available from parallelization. Any large mathematical or engineering problem will typically consist of several parallelizable parts and several non-parallelizable (sequential) parts. This relationship is given by the equation S = 1/(1-P)

where S is the speed-up of the program (as a factor of its original sequential runtime), and P is the fraction that is parallelizable. If the sequential portion of a program is 10% of the runtime, we can get no more than a 10× speed-up, regardless of how many processors are added. This puts an upper limit on the usefulness of adding more parallel execution units. "When a task cannot be partitioned because of sequential constraints, the application of more effort has no effect on the schedule. The bearing of a child takes nine months, no matter how many women are assigned."

Clock signals

Most integrated circuits (ICs) of sufficient complexity use a clock signal in order to synchronize different parts of the circuit and to account for propagation delays. As ICs become more complex, the problem of supplying accurate and synchronized clocks to all the circuits becomes increasingly difficult. The preeminent example of such complex chips is the microprocessor, the central component of modern computers, which relies on a clock from a crystal oscillator. The only exceptions are asynchronous circuits such as asynchronous CPUs.

Didn't know about this before. Another one of those points of difference which raises interesting questions about the nature of neural versus digital computation.

Algorithm Design

In scientific computing, optimality of algorithms is not always something which receives full consideration by users-- if you want to run a sort or solve some combinatorial problem, you are more concerned with making the algorithm work than looking into how fast it runs. But in dealing with very large data sets, reducing the limiting behavior of your algorithm from N^2 to NlogN can reduce your runtime from something on the order of years to something on the order of seconds. So while there are many computational problems out there for which solutions are known to exist, the practical matter of implementing such solutions is so expensive that they are effectively useless-- but if a new algorithm could be found which would reduce their runtime, we might suddenly be able to use them.

This is the driving motivation behind much of the work that goes into quantum computing. Because bit state in a quantum computer is probabilistic rather than binary, the computer operates in a fundamentally different way, and we can design algorithms which take such differences into account. One vivid example is Grover's Algorithm for searching an unsorted array. Here's a good description from Google labs:

Assume I hide a ball in a cabinet with a million drawers. How many drawers do you have to open to find the ball? Sometimes you may get lucky and find the ball in the first few drawers but at other times you have to inspect almost all of them. So on average it will take you 500,000 peeks to find the ball. Now a quantum computer can perform such a search looking only into 1000 drawers.

So if you were opening one drawer a second, the traditional algorithm would take you an average of six days to run, while the quantum algorithm would take you a little under 17 minutes.

(Now, say each of those million drawers represented a different combination of letters and numbers, and you were trying to find the drawer/combination which corresponded to the password to someone's email account. Encryption standards which would be secure against attacks from a traditional computer are easily bypassed by quantum algorithms.)

While quantum computing still has a ways to go, parallel programming is already providing another alternative to traditional computer architecture. In parallel programming, you split your code up and send it to a number of computers running simultaneously (for our million-drawer problem: say you had 9 other people to help you, you could each search a different set of 100,000 drawers and it would only take 50,000 steps on average for the ball to be found.) So the trick in parallel programming is to figure out the right way to eliminate all the bottlenecks in your code and split up your task across processors as efficiently as possible.

Now, what about a task like image recognition? If you had a couple thousand processors at your disposal and a single image to feed them, what is the most efficient way for your processors to break up that image so that between them they can reconstruct an understanding of what it depicts? You might decide to give each computer a different small piece of the image, and tell it to describe what it sees there-- maybe by indicating the presence or absence of certain shapes within that piece. Then have another round of computers look at the output of this first batch and draw more abstract conclusions-- say computers 3, 19, and 24 all detected their target shape, so that means there's a curve shaped like such-and-such. And continue upwards with more and more tiers representing higher and higher levels of abstraction in analysis, until you reach some level which effectively "knows" what is in the picture. This is how our current understanding of the visual cortex goes-- you have cells with different receptive fields, tuned to different stimulus orientations and movements, which all process the incoming scene in parallel, and in communication with higher-level regions of the brain.

It would be interesting, then, to see what sensory-processing neuroscience and parallel programming could lend one another. Could the architecture of the visual cortex be used to guide design of a parallel architecture for image recognition? Assuming regions like the visual cortex have been evolutionarily optimized, an examination of the parallel architecture of the visual processing system could tell us a lot about how to best organize information flow in parallel computers, and how to format the information which passes between them. Or in the other direction, could design of image-recognition algorithms for massively parallel computers guide experimental analysis of the visual cortex? If we tried to solve for the optimal massively-parallel system for image processing, what computational tasks would the subunits perform, and what would their hierarchy look like-- and could we then look for these computational tasks and overarching structure in the less-understood higher regions of the visual processing stream? It's a bit of a mess because the problem of image processing isn't solved from either end, but that just means each field could benefit from and help guide the efforts of the other.

So! Brains are awesome, and Google should hire neuroscientists. Further reading:

NIPS: Neural Information Processing Systems Foundation
Cosyne: Computational and Systems Neuroscience conference
Introduction to High-Performance Scientific Computing (textbook download)
Message-Passing Interface Standards for Parallel Machines
Google on Machine Learning with Quantum Algorithms
Quantum Adiabatic Algorithms employed by Google
Optimal Coding of Sound

High Speed Sequencing

This video dedicated to my undergraduate degree in biology, in which it was never deemed necessary to introduce the fact that sequencing technology more sophisticated than the Sanger method exists. This is an animation explaining the process behind Helicos's new single-molecule sequencing technology. Like all other modern sequencing methods, this technique is based on short-read sequences-- DNA is replicated and then broken into millions of tiny fragments (25-50 base pairs at the low end), all of which are sequenced simultaneously. Given about 30-fold coverage of your genome, you can align these fragments to confidently reconstruct it as a single sequence.

Also of note, the Velvet algorithm is one cool sequence assembly program which, instead of aligning DNA fragments by simply looking for overlapping regions between them, plots all the fragment sequences generated onto a De Bruijn graph, and then uses principles of graph theory to condense them into a single sequence. Yay math!

23 Questions

Darpa's 23 mathematical challenges in modern scientific efforts, with a distinct emphasis on computational biology.

Larry Abbott's 23 questions in computational neuroscience.

23 is a reference to the father of all such lists, Hilbert's 23 problems posed to the International Congress of Mathematicians in 1900; these problems shaped much of 20th century mathematics, and some remain unresolved to this day.

Visualizing Music and Looking for Patterns

Found this and many other impressive videos on one Stephen Malinowski's YouTube channel. I really like the way the colored bar visualization separates out the different voices in a piece, especially the fugues.

The opening to Gödel, Escher, Bach has a fun discussion on the structure of the fugue-- the gist of it is that the composer develops the piece out of one short theme (a few measures of some simple melody), carried by a fixed number of voices. Starting with one voice expressing the theme, each additional voice chimes in repeating the theme until all are present. The theme is further explored and varied throughout the piece via transformations of the original melody: inverting, reversing, transposing, compressing. Soooo the video above is really cool, because the visualizations make it that much easier to pick out all the transformations that are taking place. Yay!

I wonder if you could make other visualization methods which help you pick out recurring themes in a piece, and are robust to transformations from the original theme (or measure distance from the original). It seems like a problem that crops up a lot, in problems from network analysis to predicting structural motifs in proteins. For instance, all integral membrane proteins will have a hydrophobic region which crosses the lipid bilayer-- this requires an extended sequence of hydrophobic amino acids, which will be reflected in the genetic code. There would be variation in sequence (not all membrane proteins would have the same arrangement of hydrophobic amino acids), but there might still be trends which might be picked up. Fourier/Laplace transforms can break a signal down into its periodic components; is there some way to transform a signal to visualize it in the space of its recurrent themes and their variations?

Sound to Pixels

Found a nifty article about a piece of digital music software called Photosounder, posted on a blog called Create Digital Music. Photosounder is an image-sound editing program-- that is, music creation is done visually, by drawing and editing the sound's spectrogram. The videos in the CDM article show some of the ways in which this software is being used; it's pretty impressive stuff. I also found this plugin for winamp which produces a simple spectrogram of your music as a visualization, if you're just curious to see what the music you're listening to would look like.

The spectrogram is actually a good representation of how sound is coded in the brain-- the cochlea in your ear breaks down sound input into narrow frequency bands, just as we see on the X axis of the spectrogram, and cells in each frequency band fire in proportion with the intensity of sound at that frequency (so, you have a physical structure in your ear which performs a Fourier transform-- how cool is that?) As seen in this video, a single sound object usually consists of several harmonics, and a full spectrogram can be quite complex-- and yet our brain can easily segment that spectrogram to identify different instruments, even when there's a lot of frequency overlap. We are even able to focus our attention on one specific instrument, which means selectively responding to one particular batch of signals as they move up and down across frequency channels/cell populations. Brains are pretty awesome, guys.

(And on another note: as you can see in the aforelinked video, one of the easiest ways to pick out one instrument from a spectrogram is to look for elements which "move together" in time/across the spectrum-- this notion drives a lot of work in both auditory processing and the corresponding problem of object recognition in computer vision.)

GhostNet

Investigators with Infowar Monitor have recently exposed a vast spy system dubbed GhostNet which has been gathering intelligence information from over 1200 government, military, and NGO computers across 103 countries, mostly in South and Southeast Asia. The system is based almost entirely in China, but it is yet unclear whether it is the work of the Chinese government, independent Chinese citizens, or some outside organization.

A recent New York Times article on the system is full of spooky facts, such as evidence of the system's use against the Dalai Lama and the Tibetan rights movement, and descriptions of its capacities including the ability to activate infected computers' audio and visual recording equipment to covertly eavesdrop on their surroundings.

View the 53-page report detailing the GhostNet investigation here.