Install GPU Ocelot on Ubuntu 10.04

We've recently acquired a new machine to test Advanced Vector Extensions with GPU Ocelot's experimental vectorizing execution manager and code generator. I decided to document the complete set of procedures needed to build Ocelot on a fresh installation of Ubuntu 10.04.

1.) Install Ubuntu updates

2.) Install prerequisites:

sudo apt-get install g++ subversion libboost-all-dev
sudo apt-get install glutg3-dev libglew1.5-dev glew-utils
sudo apt-get install bison flex automake autoconf libtool


3.) Install NVIDIA CUDA 3.2 for Ubuntu 10.04. This includes an updated video driver and CUDA 3.2 Toolkit.

4.) Download, build, and install LLVM

svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm
cd llvm
./configure && make ENABLE_OPTIMIZED=1 -j 8
sudo make install ENABLE_OPTIMIZED=1


5.) Download, build, and install GPU Ocelot

svn checkout http://gpuocelot.googlecode.com/svn/trunk/ gpuocelot-read-only
cd gpuocelot-read-only/ocelot
libtoolize && aclocal && autoconf && automake && ./configure
make check -j 8
sudo make install


6.) Run built in unit tests:

make test


Taste of AVX

One can use Intel's Software Development Emulator to execute programs utilizing unsupported ISA extensions such as Advanced Vector Extensions. This tool, based on Pin, instruments binaries and emulates instructions not supported in hardware. It also provides detailed instruction opcode histograms so you can, for instance, figure out whether some video game or library was compiled with SSE support.

Here's an example x86-64 function implementing element-wise multiply-accumulate of two single-precision floating-point vectors of arbitrary length.

; void vectorFMA(float *R, float *A, float *B, int N)
;
; R[i] += A[i] * B[i] for i = 0 .. N-1
;
; uses AVX to multiply two vectors, elementwise, and add
; results to a third vector
;
; rdi - R
; rsi - A
; rdx - B
; rcx - N
;
vectorFMA:
 
.L1:
 ; load words from R, A, and B
 vmovups ymm1, [rdi]
 vmovups ymm2, [rsi]
 vmovups ymm3, [rdx]
 
 ; *R += *A * *B
 vmulps ymm4, ymm2, ymm3
 vaddps ymm5, ymm1, ymm4
 vmovups [rdi], ymm5
 
 ; R+=8, A+=8, B+=8
 add rdi, 32
 add rsi, 32
 add rdx, 32
 
 ; if (--rcx == 0) break;
 dec rcx
 jnz .L1
.L5:
 ret

When our SandyBridge machine arrives next week, I should have a handful of interesting microbenchmarks to run on it.

Constant-time Set Membership

While scouring the internet yesterday, I came upon an article written by Preston Briggs, currently at NVIDIA and a former office mate in Bellevue. Efficient representation for sparse sets.

This paper considers set representations of objects for which a bijection to the natural numbers exists and provides a novel alternative to bit vectors.

Sets represented by bit vectors are one of the more common approaches [what we use in Ocelot]. Given a universe of size u, bit vectors indicate whether element i is a member of a set by setting bit i providing access times on the order O(u). This representation also requires O(u) time to clear the bit vector initially. If short-lived sets with large u are needed frequently, overheads can be prohibitive. A sparse representation may be desirable, but it should have O(1) access times.

Preston's approach represents a sparse set with two arrays of size u, denoted dense and sparse, and an integer k representing the number of elements in the set. The array dense stores a packed sequence of elements that have been added to the set, and valid indices are 0 ... k-1. The array sparse provides a mapping of natural numbers to possible indices into dense. For example, assume j belongs to the set and is stored in location dense[p]; the following is true: sparse[j] = p.

With two array access, both O(1) we can efficiently determine whether element j is in the set:

def isIn(j, S):
  return (S.sparse[j] < S.k) and (S.dense[S.sparse[j]] == j)

That is, if sparse[j] is a valid index (from 0 to k-1) and the object at that index is indeed the element, then it belongs to the set. This technique has the advantage that neither dense nor sparse needs to be cleared initially. To clear the set, simply set k = 0.

Elements are added by:

def insert(S, j):
  S.dense[S.k] = j
  S.sparse[j] = S.k
  S.k += 1

Storage requirements are 2*(u+1) for a set of u integers. I thought this was interesting.

My Struggles in Trigonometry Class

During a period of restlessness last night, while lying in bed I recalled a project I completed during 11th grade trigonometry class in high school. Today, I don't remember the minimum scope requirements, but I chose to satisfy them by building a game that simulated artillery. The game environment consisted of a simulated island (a 3D heightfield) and two textured stone bunkers corresponding to each player's location.

In another window with GUI controls, the player submitted elevation, azimuth, and velocity of an artillery shell. Then, they would click FIRE and a shell would launch from their location, arc over the simulated island, and impact somewhere. If it impacted the other player's bunker (or their own), the player who's bunker survived received a point and the game restarted with new random locations. The camera was attached to the shell so the firing player would have a chance to observe the island, reconnoiter their opponents location, and update their trajectory. Differences in elevation between the two players' bunkers and physical obstructions such as the island itself meant each player needed to determine a unique trajectory to the other. I believe there was also simulated wind.

I spent plenty of time working on it and made it finally ready to present the day all projects were due. No one else did anything related to computing, let alone implement a real-time 3D renderer with a game built around it. The morning before class, I installed it on the antiquated classroom PC to test it out. To my horror, the low max-resolution of the video card prevented the GUI controls from appearing; the input window was obscured and not sizable. The controls for entering artillery parameters and firing the shell were out of view. Our teacher was perpetually suspicious of technology and told me I would have to submit it as is; no deadlines would be granted. I think she may have even been slightly pleased that smarty-pants Andykerr would finally be hoist with his own petard (when taken literally, 'sent into the air by one's own powder keg' -- a remarkably delightful metaphor given the context of my game).

I had until sixth period, classtime, to resolve the issue and make the game playable. Unfortunately, I did not have the source code, and even if I did, the machines I had access to with Visual Studio lacked the DirectX software development kit. Recompiling it was impossible.

So I edited the binary instead.

Windows applications store layouts of controls as resource files embedded in the executable. These are binary also, but I knew enough to expect the X and Y coordinates of the critical controls to be stored as 16-bit unsigned integers. Using MSPaint, I took a screenshot of the application to determine what the locations of the buttons and textboxes actually were. I visited the electronics lab where computers with Visual Studio were installed, and I used Visual Studio's hex editor to search and edit the executable. Fortunately for me, the coordinates made unique binary sequences for that particular application, so finding them was straightforward. I made up new values, overwrote the old ones, and hoped.

I brought it Trigonometry during sixth period, installed it on the classroom PC, and was met with pleased astonishment. The controls were in new positions, visible, and the game could be played as designed. The textures were crappy, and the slow video card made gameplay uninteresting, but it ran and I received full credit.

3D games rely heavily on trigonometric relationships to transform and project mathematical representations of a virtual world onto a raster display, but the math was by *far* not the most difficult part of that project. I don't think anyone else appreciated what I went through for that damn grade...