Ganesh Swami

One of the papers nominated for the best paper award at Supercomputing 06 is titled “Scalable Algorithms for Molecular Dynamics Simulations on Commodity Clusters” from the DE Shaw Research group. If your standard of a modern molecular dynamics code is Computer Simulations of Liquids, then this paper is definitely worth a look. I’ve summarized the innovations below:

Midpoint method

Published earlier this year in the Journal of Chemical Physics, this is a parallelizing algorithm which is a hybrid between spatial decompositions and force decompositions. The major innovation of this method is the reduced communication bandwidth, which can be a problem when you scale simulations to hundreds of computers.

Bitwise Time Reversibility

One of the most important requirements for an integrator solving Newton’s equations of motion is symplecticity. One way to check to check for this is by running your integrator in negative time. Doing so should return the system to the initial state. Though not an absolute requirement, this is a nice thing to have for minimizing the energy drift, which ultimately leads to a more realistic simulation. These guys have an integrator that does this.

Constraints in single precision

To reduce high frequency motions (like vibrations of Carbon-Hydrogen bonds for example), simulations typically make use of constraints to hold bond lengths or atom velocities fixed. Typical codes RATTLE and SHAKE need to be done in double precision for accuracy and to maintain energy conservation. This paper talks about the use of an (unpublished) algorithm that is stable in single precision.

Normalized local coordinates

Instead of representing coordinates in an absolute global frame, these guys normalize coordinates. This gives them more precision (due to operations done on floating points of the same magnitudes.) It also makes handling periodic boundary conditions simple. Another advantage they mention is that doing pressure control is time reversible.

Interpolation schemes

Personally, I think this is the cornerstone of the paper. The paper mentions that instead of interactions being a function of distance between the particles, they compute it as a function of . The advantage is that the same set of polynomial coefficients can be used for computing both forces and energies.

SIMD instructions

I’m just mentioning this for completeness. As far as I know, every high performance engine makes use of these instructions. In fact, GROMACS has hand tuned kernels written using these instructions. In theory, this makes your code four times faster.

In conclusion, I was pretty impressed with the quality of work and the innovations these guys have brought to the community. Download the paper here.

I was recently pulled over by the Web 2.0 police for the inappropriate use of tags and categories. When I initially setup Wordpress, I decided to use categories to tag my posts. This wasn’t elegant – the number of categories quickly got out of hand.

After reading a bunch of sites around the web, I still can’t figure out the difference. This shouldn’t be so hard, but I’m impatient. So, I’ve settled on an aggregate of what ever I’ve read on the web. I’m going to use categories to broadly classify and tags to pick out the keywords from the post. These tags are also going to be added as meta keywords to the head of each post.

The new mantra: Category = Classification. Tag = Keyword.

Two other things I’ve done:

• An AJAX archive browser.
• Significantly cleaned up the sidebar. Less is more.

You’ve probably heard by now that the stock price of Google has crossed the five hundred dollar mark.

A couple of months back, I attended a talk by Dr. Prabhakar Raghavan. This was right after he was hired to lead the Research & Development for Yahoo! He spoke about a bunch of stuff, but the subject of advertisement pricing is what I found most interesting.

In 1996, James Mirrles and William Vickerey won the Nobel prize in Economics for coming up with the idea of Vickerey auctions in decision theory. The problem with ordinary auctions is that a big player can easily outbid a small player. Imagine the fair market price of a divisible commodity being $500, but a big player uses his monetary strength to outbid everyone by bidding for $1000. This might outprice the commodity for the small players making them less likely to compete. What would the auctioneer rather have: one sale at $1000 or ten sales at $500, the true market price?

The Vickerey method uses the second highest bid as the fair market price of the commodity.

From Google’s perspective, it doesn’t have to follow the Vickerey style strictly by the book. Instead it can pick a price midway between the first and second highest bids. This has a direct impact on the GOOG top line (revenue.)

For a fair perspective, you’ll also have to look at how other players in the market are doing. The management at the other big player in the market, YHOO posted less than spectacular results recently. You could attribute this to poor execution on Yahoo’s part, but the top brass also commented on the general poor performance of the overall market. This is key.

The cynic in me asks: Is GOOG screwing over the market for short term gain? If that’s so, will the Efficient Market Hypothesis re-adjust the market and dictate a slowdown in growth rate for GOOG over the next few quarters?

Is my reasoning correct, or am I missing something fundamental here?