Atom Observations

I just put a post up about my experiences with a new Intel Atom + NVIDIA Ion2 system on my homepage: http://www.stephenjenks.com/2010/10/atom-observations/

Since it isn't Asymmetric computing, I won't repeat it here, but take a look at the link if you are interested. (Hint: you won't be putting Atoms in your cluster anytime soon if you do floating point.)

Cheap GPU Computing may be over

For those of us interested in GPU computing, Greg Pfister has written an interesting article entitled "Nvidia-based Cheap Supercomputing Coming to an End" commenting on the future of NVIDIA's supercomputing technology that has been subsidized by gamers and commodity GPUs. It looks like Intel's Sandy Bridge architecture may end that.

If you don't read Greg Pfister's Perils of Parallel blog, you should. He's been doing parallel computing for a long time and is very good at exposing the pitfalls and hidden costs of parallelism.

A year later

Well, it has been a year since my last post on here. A lot has happened since then:

I have left UCI to become Chief Scientist at Hiperwall Inc. (http://www.hiperwall.com), where we make tiled display wall software. We are just about to release a new and greatly enhanced software version, which is both exciting and tiring, with all the testing and last minute tweaks.

I have moved most of my research material from the old UCI server to my personal site (http://www.stephenjenks.com), though it isn't fully organized yet. That is where I'll be updating things, so please bookmark that and keep watching.

I'm not done with Asymmetric Computing, as we use it for various things in Hiperwall, so I will continue to explore when I have time. For the moment, however, I'm learning how to program the iPhone and iPad, because I have fun plans for them.

On Hiatus

Because of intense Hiperwall development (we're nearly done with a new release) and lots of other busy stuff, I'm going to put this blog on hiatus for a bit.

I will be making posts on my site (http://www.stephenjenks.com/) regarding computing and other stuff.

I really enjoy computer architecture and parallel computing, so I won't completely give up on this blog just yet, but hope to get back to it during the academic year.

Virtual Machines

A slightly off-topic post, but still computing-oriented...

Many people have heard of virtual machines and some have even used them in various capacities. I've used VMWare virtual machines for years quite happily, but have had some recent experiences that have changed my mind (a bit).

I use VMs on my TabletPC so I can run Linux, which I'm more comfortable with for software development than Windows. I also run VMs on my MacBook Pro so I can run Windows for various reasons, including Hiperwall software development. When I got the MacBook Pro, I bought VMWare Fusion, because I figured it would be the best. It is very good, but didn't support OpenGL, which hurt the Hiperwall software development, so I didn't use it for a while. Then I saw that Parallels Desktop 4 supports OpenGL, so I bought it and it is great. Things seem more responsive than VMWare Fusion, and more importantly, it supports both DirectX and OpenGL. The only problem I had was that the installation wizard tried to be too smart and handle everything, but got hung up on some dialog boxes that it didn't expect. I sorted it out manually, though, so all it well. Parallel Desktop 4 works very well for me.

On my PCs, I've been using VMWare Server for years, because it is free and fast (once started). Starting it takes forever, though. Really. On my Core2Quad machine at home, it litterally stops the clock update on the display and my Logitech G15 keyboard for several minutes as the VM initializes. On my poor TabletPC with slower disk and (until recently) less memory, it was nearly interminable and intolerable. And, of course, VMWare Server didn't support much in the way of display devices and such, because it was for servers. So recently, I tried Sun's VirtualBox. I tried it a year or so ago and it was terrible, but it has now become really great. It starts right away, is very responsive, and supports OpenGL, so I can run several virtual Hiperwall tiles on one PC for testing! It's just great.

That doesn't mean you should throw away VMWare Server, though, because it does one thing that the others don't. It can let the guest OS use two processors. This is important for multithreaded apps and when I demonstrate parallel programming in my classes. So it still has its place, but not as my everyday VM.

These VMs execute native x86 code directly on the processor, but all I/O (disk reads and writes, network packets, even sound and graphics) is on virtual devices. These virtual devices then use your machine's physical devices to perform the real work requested. A problem is that interrupt handling is expensive for VMs, so most VMs batch interrupts and process them in groups. This means that responsiveness is often not as good as it should be, even though average throughput is reasonable. So playing a game in a VM is probably doable, but it may suffer from stutters and delays due to the nature of the VM's I/O handling.

So VMs are tremendously useful, and though VMWare makes terrific VMs and has been around for a long time, look at some of the others, too. They may meet your needs even better.

New CUDA

I just saw the announcement that the latest CUDA (2.2) contains a debugger (yay) and a profiler (I hope it's better than the old one) amidst a few other goodies. Check it out here.

If you're interested in the latest NVIDIA CUDA news, follow nvidiadeveloper on Twitter. They don't send too much junk.

Brains vs. Brawn

In the world of parallel computing, sometimes bigger isn't better. While some algorithms are well suited to vast parallel processing, like that provided by CUDA on the Tesla C1060, sometimes an algorithmic optimization may make the problem run faster on fewer processors. The N-Body problem is a prime example of this. The N-Body problem is a classical problem in astrophysics, molecular dynamics, and even graph drawing. The problem state consists of a number (n) of bodies, which may be stars or molecules or whatever. These bodies interact with each other via gravity or electromagnetic forces, etc. They exert these forces on each other, thus accelerating and causing movement. The forces on each body (from all the other bodies) are computed for each time step, then acceleration and movement can be calculated. This process means that O(n^2) force calculations are needed for each time step, and the simulation may run for many time steps. So, for 50000 bodies, roughly 2.5 billion force calculations are needed per time step.

The good news is that these force calculations are completely independent of each other, which means they can be done in parallel, so this type of problem is extremely well suited to CUDA computing. Each thread can compute the force on a single body by stepping through all the other bodies and determining the interaction with each. Using blocking and the fast shared memory as a cache, this can be quite an efficient operation in CUDA.

On the other hand, there are other ways to solve this type of problem that may be faster. The MDGRAPE system in Japan was designed specifically to perform molecular dynamics computations, and achieved petaFLOPS years ago, well before the current crop of petaFLOPS machines became operational. The reason it never made the Top 500 list is because it wasn't general purpose and wouldn't run the HPL benchmark Top 500 uses. So a special architecture designed to accelerate the N-Body-type problem is one way to speed things up.

Algorithmic enhancements are another way to speed up N-Body. If we observe that distant bodies exert little influence, then perhaps we can group a bunch of distant bodies, treat them as a single distant "body" with corresponding mass and center of mass, then compute the force in aggregate. This approach is used by the Barnes-Hut optimization. In Barnes-Hut, bodies are grouped into various combinations, each decreasing in size, until, at the smallest level, each group only contains a single body. A tree is used to store these groups, with larger groups at the top of the tree and smaller, refined, groups towards the bottom. A recursive algorithm is used to build the tree, then the force calculations can be performed against the largest portions of the tree that meet certain distance criteria. Barnes-Hut drastically reduces the number of force calculations to O(n log n), so rather than needing 2.5 billion force calculations per iteration, the number shrinks to fewer than 3 million! The problem is that, as bodies move, the tree needs to be rebuilt for each iteration (though that could be optimized, perhaps). Of course, Barnes-Hut is an approximation, however, so the results will vary slightly from the O(n^2) version.

I assigned my students to build 3 different versions of N-Body for my parallel architecture class last quarter: one using OpenMP to speed the force calculations, one using CUDA, and one using Barnes-Hut to reduce their number. I wanted the students to see the power of CUDA to speed massively parallel computations, but I also wanted them to see whether a smarter algorithm could overcome the benefit of tremendous hardware parallelism. As expected, the Core2Quads with OpenMP did get good speedups in the force calculations, but it wasn't enough to make the problem fast: with 50000 bodies it took about 15 seconds per time step. The CUDA version was much faster, bringing it down to about 2 seconds per time step on the Tesla cards.

The problem with Barnes-Hut is that it can be done badly. Building the tree is potentially very expensive, particularly if dynamic allocation is used. I assigned the students to do the tree building in parallel, and parallel memory allocation introduces locking delays. I also asked them to use self-scheduling, so managing a task queue meant more locks to slow things down. Some students managed to get no performance improvement in parallel tree building at all, while a few got some. I managed to get about 30-50% improvement by trading some parallelism for speedy recursive calls and avoiding the locks. In any case, the fastest Barnes-Hut implementations we came up with could run 10 time steps in the same 2 seconds it took the CUDA cards to run 1 time step.

So the final tally showed that CUDA provides an order of magnitude improvement over OpenMP on Core2Quad for the O(n^2) case, but the O(n log n) Barnes-Hut version is an order of magnitude faster than that! So it's nice to see that brains triumph over brawn.

OnLive

A company called OnLive has been making the news lately with their announcement of online purchases of games and a new model of gaming. This new model is intriguing, because it hooks our gaming experience into cloud computing. Essentially, we will game via streaming video, with the game video being rendered on a remote "cloud" computer somewhere. This has lots of advantages in terms of not needing noisy, expensive top-of-the-line hardware to play fancy games. Instead, THEY have the fancy hardware and render the game for us, then stream it to our browser or our TV via a presumably inexpensive console.

Will this work? There are many challenges, with latency being the biggest one. Controller events need to be captured, sent to the server system, where they impact the gameplay, which then causes feedback onscreen, which is streamed to you. This round-trip latency may be noticeable if it is much more than your brain's control loop time. Existing multiplayer games experience this as "lag" and it is very annoying, so it may be a problem here too. The LA Times quotes an OnLive exec as saying they want to bring that latency down to 1 millisecond. While they may be able to use prediction and other things to reduce perceived latency, actual packet transfer time is bounded by the speed of light. This means a packet could, at most, travel on the order of 186,000 miles in a second, or 186 miles in a millisecond. (Best case, of course, as there is overhead and signal propagation is often slower than the speed of light.) Therefore, unless they place their servers in every city, 1 ms doesn't make much sense. But then again, perhaps the newspaper misquoted or misunderstood and I am just interpreting it wrong.

I wish OnLive well and look forward to seeing how well it works.

Cluster and CUDA troubles abound

Running this cluster for my class is more trouble than it's worth and I won't do it again. Research cluster, yes - teaching cluster, no.

Yesterday, one of the students ran the frontend node out of memory. Of course, that meant I couldn't log in to reboot the thing, so I had to go to campus, find which entrance of the building is open on weekends and isn't closed by construction, and press the reset switch. Very annoying. I am disappointed that Linux is that fragile and that mechanisms wouldn't be in place to prevent this sort of problem. Surely crashing that program and freeing the memory should have solved it, but obviously didn't.

An even more annoying problem has to do with the Tesla cards. It looks like the drivers keep crashing. After a while, suddenly programs are no longer able to open the appropriate /dev entries for the NVIDIA cards. Clearly the students could be running buggy programs and such, but that should be expected. I think the drivers must not be recovering properly after a crash or something. Even running nvidia-smi won't fix it. A reboot will, but I discovered "rmmod nvidia" will remove the driver module and clear the problem, then nvidia-smi will cause the driver to reload and reinitialize. But bloody annoying, because the root user needs to do it, and I'm not giving the students root...

New cluster at UCI

Though it isn't an asymmetric system there is a new cluster at UCI for researchers and grad students. See the following link for details:

http://news.nacs.uci.edu/2009/02/new-computing-cluster/

This is good news and seems to be a nice resource for the UCI HPC community.

Interesting parallel computing blog

My wife pointed out an interesting parallel computing blog:

http://perilsofparallel.blogspot.com/

It's well worth checking out. The long posts are clearly written and helpful. Take a look. I particularly like the car analogy for multicore processors (i.e., two 62 MPH cars are better than one 120 MPH car?). The author, Greg Pfister, has wide interests, from cloud computing to Larrabee.

Cluster Stable

The cluster has been stable for several days now with a Core2Quad frontend node. I don't know what was causing the Phenom frontend node to fail, but as it was my personal machine, I'll take it home and diagnose it after the quarter ends. For now, the students are able to make their parallel programs work on the cluster and finish their projects. Yay!

Cluster still troubling

It turns out the cluster frontend was having memory errors. Reseating the DIMMs (Crucial Ballistix) seemed to help, as it passed Memtest86, but it failed again when put back in service. I tried to swap the disk into one of the cluster nodes to make it the frontend, but bloody Linux thwarted me completely, particularly because it was using disk labels not partition numbers and somehow they were not findable in the new machine. The disk wasn't corrupt, but the kernel panicked on boot each time, no matter what I did.

Eventually, I had to reformat, reinstall ROCKS, restore the users, and put the new frontend in service. It seems to be working now, though ROCKS is misbehaving a bit. Scripts that normally handle all the user adding tasks aren't handling the auto.home adding, which is a surprise. Anyway, I can use emacs and fix it myself. Bloody computers.

Technology troubles

Technology really failed me today. When I got to campus, I rebooted my cluster frontend, which failed on Saturday. It didn't come back up. Then I discovered that the bright guys in network security had blocked my IP address because someone who had it before me had a compromised machine. When I called the help desk, they said I needed to send an email to get it cleared up. Well, that would have been great, except email was blocked! So I plugged into the HIPerWall network, only to discover it didn't work either. The antique PowerMac G4 server that provided DHCP address, name service, and user accounts has failed, apparently permanently, as it won't even turn on the screen. So there are days I really hate technology.

But I think I'd enjoy digging ditches less, so I'll stick with the techology stuff for now.

I used my iPhone to send the email to unblock my IP address, then I configured the Linux storage server to serve DHCP, so HIPerWall is back up. The CUDA cluster is still hosed, however...

CUDA cluster troubles

The problem with running a cluster that other people use is that those other people rely on it and it sometimes breaks.

In this case, it looks like my frontend crashed and rebooted itself (why, I don't know) yesterday afternoon. Upon reboot, it seems to have not reinitialized the Tesla card, so the students couldn't do their testing. I ran "nvidia-smi" on it, which created the device entries and made it usable again. Perhaps I need to add that to init.d or rc.local

It also turns out that two of my compute nodes had problems, not related to reboots. In one case, the devices weren't present, but nvidia-smi didn't fix it. A reboot, followed by nvidia-smi did. In the other case, the machine with 2 Tesla cards had only one of them working. Again, nividia-smi didn't help, but a reboot did.

While I imagine the problem may stem from student code doing horrible things inside the card, I think it points to a driver problem. Perhaps the driver isn't correctly recovering after some crazy operation, but that's not a good sign for the robustness of the CUDA computing environment.

Some pain, no gain

I modified my program to take advantage of coalesced memory accesses (particularly loads in the N-body problem), having to change many, many things. After a fair bit of painful debugging, I got it to work and produce the same results as the original CUDA version. The bummer is that it is only slightly faster (like a percent or two). Now it seems likely that the memory accesses were already pretty good, but they certainly were a little more excessive than they should have been, so I really expected a significant gain. I am taking advantage of locality MUCH more than before, yet it didn't help.

I turned to the fancy profiler provided by NVIDIA. It's pretty nifty and told me what I already knew that the O(N^2) ComputeForces functions is taking all the time. What it couldn't tell me is the number of uncoalsced loads, because that performance counter is apparently not (yet?) supported on G200 model GPUs. Darn. It does tell me that I have a lot of coalesced loads and stores, but they may only be a portion of the total. So I'm not particularly thrilled with the profiler, since uncoalesced memory accesses can be the real performance killer in CUDA apps. But it looks pretty and has lots of other somewhat useful statistics. I'm glad I tried it.

N-Body

I have assigned my students to make a simple n-body simulation in CUDA to compare it to the OpenMP version they've already done. I know there are really great n-body program for CUDA out there, but starting simple is good for a class. I wrote my own, as well, because I want to see if any of the students can make theirs faster than mine.

My initial naive implementation is only about 5 times faster on the Tesla C1060 than the OpenMP version on the Core2Quad 8200. This version does nothing special to take advantage of locality, so my next version should be MUCH faster!

Two surprises:

1. Even with doubles, the floating point values differ from the Core2Quad after a good number of iterations. This wasn't the case in my previous FDTD program, so I'm a bit concerned. I am using sqrt(), so perhaps that implementation differs a bit.
2. When I tried 256 threads per block, the CUDA launch failed with error 4 (unspecified launch failure). I've never seen that one before, but the code works with 128 threads and fewer. Hmmm...

New cluster node

I put together a new node for the CUDA cluster. This one has the same el-cheapo Core2Quad 8200 and 4GB of Kingston DDR3 RAM, as well as the scrounged hard disk from the cluster node it replaced (the hard drive tests OK, but doesn't sound very quiet...) I got a bigger power supply this time so I could put 2 Tesla cards in. The documentation is somewhat weak on multiple Tesla cards per machine, so I wasn't sure if I should put in the SLI bridge or not. I didn't, mostly because I forgot - I had the bridge, but buttoned up the machine before I remembered to use it.

Both Tesla cards are detected with no trouble, but I notice an interesting delay as CUDA programs start. This delay does not occur with normal OpenMP or other programs, so must be something to do with the device detection in CUDA. So far, I'm not concerned, but will see if it causes any trouble. I will also look into how to use both cards by two separate programs to see if two of my students can use this node for CUDA simultaneously.

New CUDA

I updated the cluster with the recently-released CUDA 2.1 for Linux 64 and everything seems to work well.

I am disappointed that Mac CUDA trails at 2.0, but I presume 2.1 is coming.

I looked into putting a Tesla card into a Mac Pro, but it looks like it wouldn't be supported under Mac OS X. It would probably work under Windows, which we do run on our Mac Pros sometimes. I imagine the reason is that Apple's display drivers wouldn't bother to load for a Tesla card and Mac CUDA uses the bundled drivers. Darn.

HIPerWall makes news

I was pleased to discover that Information Week has named my company, Hiperwall Inc., as the startup of the week!