As a demonstration, I followed WordPress's five-minute installation process and the results are fairly gratifying. Thus, I plan on ceasing future updates to this blog (I write about 30 posts a year and publish 20 of them; it's not like they're that frequent).
Look for future updates at http://akerr.net/andrew/blog/.
See you there.
Tuesday, December 13, 2011
Thursday, September 1, 2011
Software Rasterization
The previous post awakened the part of me that is somewhat passionate about graphics programming. In the last three nights, I threw together a software rasterizer that is now capable of perspective-correct texture mapping in addition to point lights.
Here is a screenshot:
And here is a video that VLC should have no trouble playing.
Some details:
The rasterization algorithm is very primitive. Triangle setup first ensures clockwise vertex ordering (cross product of the two edge vectors followed by a sign comparison) and culls backfaces. Next, a transformation to Barycentric coordinates is computed, and blocks of pixels in the render target are transformed and compared. If their Barycentric coordinates are found to lie within the triangle, they are used to interpolate vertex color and texture samples.
It is not yet GPU accelerated, though expect a CUDA implementation to follow.
Here is a screenshot:
And here is a video that VLC should have no trouble playing.
Some details:
The rasterization algorithm is very primitive. Triangle setup first ensures clockwise vertex ordering (cross product of the two edge vectors followed by a sign comparison) and culls backfaces. Next, a transformation to Barycentric coordinates is computed, and blocks of pixels in the render target are transformed and compared. If their Barycentric coordinates are found to lie within the triangle, they are used to interpolate vertex color and texture samples.
It is not yet GPU accelerated, though expect a CUDA implementation to follow.
Friday, July 22, 2011
ASCII Torus
Inspired by this guy's 3D torus rendered to an ASCII palette, I decided to spend an hour last night implementing something similar. Here's the source, and here's the result. It was a fun exercise:
And here it is rendered by the same utility to a higher resolution.
@@@@@@@
@@@@$##*!!!===!!!*##$@@@@
@@@$$#*!=;;:~~-~~-~~~:~:;==!*#$$@@@
$@$$$#*!=;:~~~-~-----~~~~~~:::;=!!*#$$$@$
$$$$$##*=;~~~-----~~~~:::::::::~::;=!**#$$$$$
*$$$$$#*!=:~~------~~~~~::::::::::::::;!**#$$$$$#
*#$$$$$#*=:~--,,,-- ~:::::::=!*##$$$$#*
!*#$$$$$#*=~-,,, ~:~::!*#$$$$$#*!
;!*#$$$$$#*=,. ~~!*#$$$$$#*!;
-;!*#$$$$$$#!, ~*#$$$$$$#*!;,
~:;==**#$$$@@@$ #@@@$$$#**!=;~,
~~~:;=!*###$$@@@@ @@@@$$###*!=;:~-,
~~~::;=!***#$$$@@@@@@ @@@@@@$$$#***!=;:~~--
:~~~~~::;=!!**###$$$$@@@@@@@@@@@@@$$$$###**!!=;;:~~---,
::~~~~~~~:;;==!!****#############****!!==;;;:~~-----,
::~~~~-~~~~::;;=====!!!!!!!!!=====;;:::~---------
:::~~~~~~~-----~~:::::::::::::~~~-------------,
:::::~~~~~-~------------------------------,
:::::~~~~~~~~-----------------------,
:::::::~~~~~~~~~~~~~-----------
:::::::~~~~~~~~~~~~~-
And here it is rendered by the same utility to a higher resolution.
Wednesday, July 20, 2011
Screencapture Utility
I wrote a quick'n'dirty alternative to Skitch for Linux because Shutter was always so crappy. It's a simple Python script that enables on-the-fly cropping and immediate upload to the configured server. Took about ten minutes to research, write, and debug.
Here's a sample:
Here's a sample:
Wednesday, June 8, 2011
Alpine Ascents Successful Climb of Mount Everest
In brighter news, Seattle-based Alpine Ascents is currently wrapping up a successful summit assault on both Everest and nearby Lhotse a day later. A topological map illustrates the incredible vertical and horizontal distances covered.
This shows the route from base camp, traversal to Camp I across the Khumbu Icefall, Advanced Base Camp II at 21,000 ft, Camp III at 24,000 ft, Lhotse High Camp, and finally Camp IV at 26,000ft. From Camp IV, the route to the summit ascends 3,000 ft during a grueling 12 hour climb requiring a 9pm departure time to reach the summit by the next morning. The elevation profile shows the several returns to base camp from Camp II during the acclimatization period. It also shows the ascent of Lhotse by three of the climbers from the Everest group prior to the group's descent.
Alpine Ascents does a pretty thorough job listing their itinerary and equipment recommendations. Check it out, particularly the group electronics gear.
This shows the route from base camp, traversal to Camp I across the Khumbu Icefall, Advanced Base Camp II at 21,000 ft, Camp III at 24,000 ft, Lhotse High Camp, and finally Camp IV at 26,000ft. From Camp IV, the route to the summit ascends 3,000 ft during a grueling 12 hour climb requiring a 9pm departure time to reach the summit by the next morning. The elevation profile shows the several returns to base camp from Camp II during the acclimatization period. It also shows the ascent of Lhotse by three of the climbers from the Everest group prior to the group's descent.
Alpine Ascents does a pretty thorough job listing their itinerary and equipment recommendations. Check it out, particularly the group electronics gear.
Into Thin Air
I recently finished reading Into Thin Air, Jon Krakauer's incredible description of his summit attempt on Mount Everest during what became the 1996 Mount Everest Disaster. The narrative describes Krakauer's experience during the heyday of commercial mountaineering guide services. As a journalist writing for Outside magazine, Krakauer described what was hoped to be a routine climb along Mount Everest's South Col summit route used by Hillary and Norgay during their record-setting first summit in 1953, now the standard route.
During summit day, slow progress by inexperienced climbers and judgment errors by guides set the stage for tragedy when a storm quickly materialized along the southern ridge. Blowing 40 knots and producing incredible wind chills, many tardy climbers including the leader of Krakauer's expedition were trapped high on the upper mountain. By this time, Krakauer himself had nearly made it to high camp in the col and narrowly escaped incredible amounts of exposure in the high winds. Lack of visibility thwarted rescue attempts, and by the next day eight members from two expeditions had perished while others suffered extreme frost bite.
An expedition filming the IMAX documentary Everest offered assistance and supplies such as additional bottled oxygen in addition to arranging a helicopter evacuation of two frost bitten climbers. This film hauntingly documents their perspective of the disaster.
One of the most striking components of this story is how altitude clouded the judgments of the people involved. Several times, someone attempting to adjust their oxygen regulators would get it wrong and either turn off the flow of O2 entirely or drain the tank in minutes. Tragically, one of the guides who had reached high camp during the storm incorrectly stated that all of the oxygen bottles were empty when, in fact, at least two were not. Krakauer speculates this incorrect information changed the plans of Rob Hall, the lead climber, who elected to stay with a client near Hillary Step, just below the summit, where both he and his client perished.
The 1996 Everest Disaster demonstrates the consequences of hubris high on a mountain. One of the guides from an American expedition wasn't climbing with oxygen. While this might be a personal challenge to overcome at other times, doing so while employed to take care of others is exceedingly dangerous. When disaster struck, he was unable to assist; he couldn't even wait around with a distressed climber, for the lack of oxygen slows human metabolism such that the only substantial source of internal heat is produced from muscles as they are operating. Additionally, the many climbers from multiple commercial expeditions created bottlenecks that delayed summit times and increased exposure to weather-related hazards; if the storm had struck even an hour later, many more people are likely to have made it to [limited] shelter in the South Col. Finally, turn around times were ignored at great peril.
One of the other lessons here is no climb is guaranteed, and achieving the summit is only the half-way point. Mountaineering is inherently quite dangerous, particularly above 8000m where oxygen levels are so low that it's virtually impossible to carry someone. Anyone considering undertaking such a venture should come to terms with the fact that rescue is nearly impossible; doubts in one's abilities, fitness levels, and weather conditions should be headed. Underscoring this point, most of the climbing along the upper mountain is done without ropes linking the climbers; falls are so perilous on the steep slopes that doing so would simply increase the scope of one person's tragedy.
During summit day, slow progress by inexperienced climbers and judgment errors by guides set the stage for tragedy when a storm quickly materialized along the southern ridge. Blowing 40 knots and producing incredible wind chills, many tardy climbers including the leader of Krakauer's expedition were trapped high on the upper mountain. By this time, Krakauer himself had nearly made it to high camp in the col and narrowly escaped incredible amounts of exposure in the high winds. Lack of visibility thwarted rescue attempts, and by the next day eight members from two expeditions had perished while others suffered extreme frost bite.
An expedition filming the IMAX documentary Everest offered assistance and supplies such as additional bottled oxygen in addition to arranging a helicopter evacuation of two frost bitten climbers. This film hauntingly documents their perspective of the disaster.
One of the most striking components of this story is how altitude clouded the judgments of the people involved. Several times, someone attempting to adjust their oxygen regulators would get it wrong and either turn off the flow of O2 entirely or drain the tank in minutes. Tragically, one of the guides who had reached high camp during the storm incorrectly stated that all of the oxygen bottles were empty when, in fact, at least two were not. Krakauer speculates this incorrect information changed the plans of Rob Hall, the lead climber, who elected to stay with a client near Hillary Step, just below the summit, where both he and his client perished.
The 1996 Everest Disaster demonstrates the consequences of hubris high on a mountain. One of the guides from an American expedition wasn't climbing with oxygen. While this might be a personal challenge to overcome at other times, doing so while employed to take care of others is exceedingly dangerous. When disaster struck, he was unable to assist; he couldn't even wait around with a distressed climber, for the lack of oxygen slows human metabolism such that the only substantial source of internal heat is produced from muscles as they are operating. Additionally, the many climbers from multiple commercial expeditions created bottlenecks that delayed summit times and increased exposure to weather-related hazards; if the storm had struck even an hour later, many more people are likely to have made it to [limited] shelter in the South Col. Finally, turn around times were ignored at great peril.
One of the other lessons here is no climb is guaranteed, and achieving the summit is only the half-way point. Mountaineering is inherently quite dangerous, particularly above 8000m where oxygen levels are so low that it's virtually impossible to carry someone. Anyone considering undertaking such a venture should come to terms with the fact that rescue is nearly impossible; doubts in one's abilities, fitness levels, and weather conditions should be headed. Underscoring this point, most of the climbing along the upper mountain is done without ropes linking the climbers; falls are so perilous on the steep slopes that doing so would simply increase the scope of one person's tragedy.
Wednesday, May 11, 2011
Coquette
WindFinder is a coquette and a tease. Spectacular sailing conditions are always forecast four days out. When time moves forward, things always settle down to calm conditions that aren't worth the drive up.
Summer must be upon us.
Summer must be upon us.
Sunday, April 10, 2011
DEC is Dead
I was perusing Amazon and came upon this title: DEC is Dead. Long Live DEC. This book describes the rise and fall of Digital Equipment Corporation, a legend in the computing industry that introduced many innovations in processor and system design. Many of the architects went on to other companies such as AMD and Transmetta and continued to advance the state of the art. It's an appealing topic, to be sure.
I wanted to point that out.
Additionally, the title seems to confuse the etymological implications of "The x is dead. Long live y." In this case, even if x and y appear to be the same improper noun, lexically, they never refer to the same individual or entity; that'd be a contradiction. The phrase actually refers to a transitional event, where the life of an old entity, x, is over and we should now bestow praise and hope on the life of a new entity, y. See this for a foothold on more information.
I've seen a lot of smart people get this wrong, and evidently someone solidified their mistake as the title of their book. In this case, I suggest DEC is dead. Long live Intel, AMD, and Transmetta.
You're welcome.
I wanted to point that out.
Additionally, the title seems to confuse the etymological implications of "The x is dead. Long live y." In this case, even if x and y appear to be the same improper noun, lexically, they never refer to the same individual or entity; that'd be a contradiction. The phrase actually refers to a transitional event, where the life of an old entity, x, is over and we should now bestow praise and hope on the life of a new entity, y. See this for a foothold on more information.
I've seen a lot of smart people get this wrong, and evidently someone solidified their mistake as the title of their book. In this case, I suggest DEC is dead. Long live Intel, AMD, and Transmetta.
You're welcome.
Monday, April 4, 2011
Sailing Adventure
Saturday, I went sailing 420s on Lake Lanier with a labmate. Of five boats that went out, we were one of two that didn't both capsize and require a rescue. The other boat that avoided capsize spent much of the morning with only the jib flying and left early.
Winds were intense, from 15 to 20 mph, and waves were high. Our 420 achieved planing speed several times; the sudden boost in speed and rudder authority was reminiscent of a jetski.
Windfinder provides a great and detailed wind forecast.
Winds were intense, from 15 to 20 mph, and waves were high. Our 420 achieved planing speed several times; the sudden boost in speed and rudder authority was reminiscent of a jetski.
Windfinder provides a great and detailed wind forecast.
Thursday, March 10, 2011
Exploring R.M.S. Queen Mary
RMS Queen Mary is an ocean liner from the Cunard Line in service from 1936 to 1967. Propelled by four screws, each moved by a collection of high-speed steam turbines, Queen Mary offered the fastest civilian Atlantic crossings available. Her record setting voyage of 3 days, 21 hours earned her the Blue Riband which she held for 14 years. Unlike many of the other liners of the day, Queen Mary survived her service life and found a permanent home along the coast of Long Beach, California, where she now accommodates hotel guests, numerous restaurants, tourists, and a community center built into her forward engine room and aft boiler rooms.
On Sunday morning, I drove up to Long Beach along the Pacific Coast Highway to spend as much of the day as possible exploring Queen Mary's decks and interior spaces, hoping to see as much of the ship as possible. Displacing 81,000 tons and with a length of 1,020 ft, I would surely run out of daylight long before I ran out of things to see.
Hopefully this blog post captures some of the highlights of my visit.
Monday, February 21, 2011
Ferroequinology: More Running Boards
Saturday, I revisited SERM to spend some time on A&WP 290. The previous visit, we cleared several brackets and attached steam and air pipes to expose a nearly clear boiler shell. In preparation for Ultrasonic Thickness testing, a grid over each course of the shell must be arranged and test points ground to expose bare metal. To access the entire shell, running boards on the fireman's (left) side of the locomotive needed to be installed.
Installing the fireman's side running boards used all of the mounting hardware remaining and, to our chagrin, exposed mistakes in mounting the engineer's side running boards. This image depicts the two large castings that support both running boards and compressed air tanks. Each of the four castings is distinct, not correctly labeled, and not easily positioned even with a crane (of which I have become a precise and efficient operator).
Ultimately, we had to remove the engineer's side running boards, remove what we guessed was the incorrectly placed bracket, place a different bracket, reinstall the running board, install that bracket on the other side in both possible locations, and hopefully achieve the best fit. Moreover, studs can be bent so it's a matter of luck and judgment to determine whether a part doesn't fit because it's not the correct part or because you're not using a large enough hammer.
By end of day, with many possible combinations attempted, all air tank brackets were soundly mounted, running boards placed, and the boiler now accessible from all sides. During the next disassembly, we'll surely stamp each casting and avoid confusion in the future... ha.
Up next, ultrasonic thickness measurement over every square foot of a 37ft pressure vessel with working pressure 201 psi and operational temperature of 450 degF.
Installing the fireman's side running boards used all of the mounting hardware remaining and, to our chagrin, exposed mistakes in mounting the engineer's side running boards. This image depicts the two large castings that support both running boards and compressed air tanks. Each of the four castings is distinct, not correctly labeled, and not easily positioned even with a crane (of which I have become a precise and efficient operator).
Ultimately, we had to remove the engineer's side running boards, remove what we guessed was the incorrectly placed bracket, place a different bracket, reinstall the running board, install that bracket on the other side in both possible locations, and hopefully achieve the best fit. Moreover, studs can be bent so it's a matter of luck and judgment to determine whether a part doesn't fit because it's not the correct part or because you're not using a large enough hammer.
By end of day, with many possible combinations attempted, all air tank brackets were soundly mounted, running boards placed, and the boiler now accessible from all sides. During the next disassembly, we'll surely stamp each casting and avoid confusion in the future... ha.
Up next, ultrasonic thickness measurement over every square foot of a 37ft pressure vessel with working pressure 201 psi and operational temperature of 450 degF.
Sunday, February 20, 2011
Orthographic Meet 2011
Last night, Emma and I attended the Atlanta Open Orthographic Meet, an annual spelling competition held at Manuel's Tavern. My score was 19 total, although I feel bad pronunciation robbed me of of 'pharoah.' These are the words from each of four rounds with my best effort to recall the particular definition provided during the competition.
pharoah - a tyrant
shellacked - to defeat decisively
corpuscle - an unattached body cell, such as a blood or lymph cell
artisan - a skilled manual worker; a craftsperson
ululate - to howl or wail, as with grief
metallurgy - the study of metals and their properties in bulk and at the atomic level
bulwark - wall or embankment raised as a defensive fortification
privilege - a special advantage, immunity, permission
artesian - a well from which water flows spontaneously due to internal pressure
mischief - behavior that causes discomfiture or annoyance in anothe
sauerbraten - pot roast of beef marinated in vinegar, water, wine, and spices before being cooked
poltergeist - a ghost that manifests itself by noises, rappings, and the creation of disorder
deuce - a tied score in tennis
lien - right to take and hold the property of a debtor as security for a debt
apropos - being at once opportune and to the point
rendezvous - meeting at a prearranged time and place
vaudeville - theatrical performance of this kind; a variety show
pharisaic - hypocritically self-righteous and condemnatory
apiary - place where bees are kept
bamboozle - to take in by elaborate methods of deceit
grok - to understand profoundly through intuition
uxorious - excessively submissive or devoted to one's wife
apocopate - to omit the final sound or sounds of (a word)
diurnal - occurring or active during the daytime rather than at night
succedaneum - a substitute
poinciana - having large orange or red flowers
snollygoster - one, especially a politician, who is guided by personal advantage rather than by consistent, respectable principles
involucrar - ??
viand - a very choice or delicious dish
onomatopoeia - the formation or use of words such as buzz or murmur that imitate the sounds associated with the objects or actions they refer to
??? -
antipyretic - a medication that reduces fever
trepanation - the medical procedure of making a hole in the skull
anneal - to subject glass or metal to a process of heating and slow cooling in order to toughen and reduce brittleness
coccygodynia - pain in the coccyx or tailbone area
kuemmel - a sweet, colorless liqueur flavored with caraway seed
zugzwang - a situation where one player is put at a disadvantage because he has to make a movel the player would prefer to pass and make no move
fissiparous - inclined to cause or undergo division into separate parts or groups
psammite - a metamorphosed rock unit with a dominantly sandstone
smaragd - having the color of emeralds
coryphee - a ballet dancer
ratamacue -
majuscule - capital letters
mirliton - a pear-shaped vegetable or its vine
claquer - an organized body of professional applauders
cimicine -
rijstaffel - a dish originating in Indonesia; a wide variety of foods and sauces are served with rice
mbaqanga - a style of Black popular music of urban South Africa
jobbernowl - a blockhead
tchick - a slight sound such as that made by pressing the tongue against the roof of the mouth and explosively sucking out the air at one side, as in urging on a horse
Round 1
pharoah - a tyrant
shellacked - to defeat decisively
corpuscle - an unattached body cell, such as a blood or lymph cell
artisan - a skilled manual worker; a craftsperson
ululate - to howl or wail, as with grief
metallurgy - the study of metals and their properties in bulk and at the atomic level
bulwark - wall or embankment raised as a defensive fortification
privilege - a special advantage, immunity, permission
artesian - a well from which water flows spontaneously due to internal pressure
mischief - behavior that causes discomfiture or annoyance in anothe
sauerbraten - pot roast of beef marinated in vinegar, water, wine, and spices before being cooked
poltergeist - a ghost that manifests itself by noises, rappings, and the creation of disorder
deuce - a tied score in tennis
lien - right to take and hold the property of a debtor as security for a debt
apropos - being at once opportune and to the point
rendezvous - meeting at a prearranged time and place
vaudeville - theatrical performance of this kind; a variety show
pharisaic - hypocritically self-righteous and condemnatory
apiary - place where bees are kept
bamboozle - to take in by elaborate methods of deceit
Round 2
grok - to understand profoundly through intuition
uxorious - excessively submissive or devoted to one's wife
apocopate - to omit the final sound or sounds of (a word)
diurnal - occurring or active during the daytime rather than at night
succedaneum - a substitute
poinciana - having large orange or red flowers
snollygoster - one, especially a politician, who is guided by personal advantage rather than by consistent, respectable principles
involucrar - ??
viand - a very choice or delicious dish
onomatopoeia - the formation or use of words such as buzz or murmur that imitate the sounds associated with the objects or actions they refer to
??? -
antipyretic - a medication that reduces fever
trepanation - the medical procedure of making a hole in the skull
anneal - to subject glass or metal to a process of heating and slow cooling in order to toughen and reduce brittleness
coccygodynia - pain in the coccyx or tailbone area
Round 3
kuemmel - a sweet, colorless liqueur flavored with caraway seed
zugzwang - a situation where one player is put at a disadvantage because he has to make a movel the player would prefer to pass and make no move
fissiparous - inclined to cause or undergo division into separate parts or groups
psammite - a metamorphosed rock unit with a dominantly sandstone
smaragd - having the color of emeralds
coryphee - a ballet dancer
ratamacue -
majuscule - capital letters
mirliton - a pear-shaped vegetable or its vine
claquer - an organized body of professional applauders
Round 4
cimicine -
rijstaffel - a dish originating in Indonesia; a wide variety of foods and sauces are served with rice
mbaqanga - a style of Black popular music of urban South Africa
jobbernowl - a blockhead
tchick - a slight sound such as that made by pressing the tongue against the roof of the mouth and explosively sucking out the air at one side, as in urging on a horse
Monday, February 7, 2011
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:
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
5.) Download, build, and install GPU Ocelot
6.) Run built in unit tests:
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
Monday, January 31, 2011
Attention all Personnel
Update your blogs, folks! I know you've been up to something; what is it? What did you learn from it?
A short observation: I discovered the level of accuracy in my technique at pool vastly improved if I decreased the distance between cue and cue ball. Short stroke trumps long stroke.
Another short observation: Under sail, when preparing for a gybe, be sure you are running directly down wind. A gybe should not involve significant rudder/tiller movements, and one's heading should not change dramatically. In this video, the nose of the boat does not turn during the gybe; the main is simply sheeted in until the wind carries it across.
Strolls through Piedmont Park are best completed with Emma and a smoothie.
A short observation: I discovered the level of accuracy in my technique at pool vastly improved if I decreased the distance between cue and cue ball. Short stroke trumps long stroke.
Another short observation: Under sail, when preparing for a gybe, be sure you are running directly down wind. A gybe should not involve significant rudder/tiller movements, and one's heading should not change dramatically. In this video, the nose of the boat does not turn during the gybe; the main is simply sheeted in until the wind carries it across.
Strolls through Piedmont Park are best completed with Emma and a smoothie.
Tuesday, January 18, 2011
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.
When our SandyBridge machine arrives next week, I should have a handful of interesting microbenchmarks to run on it.
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.
Ferroequinology: Running Boards
We hoisted engineer's side running boards onto the brackets mounted the previous week. Now, it is possible to access the top of A&WP 290's boiler shell. We used the opportunity to heat and remove a handful of brackets to clear several sand and steam pipes.
Protip: when applying a socket wrench to a red-hot steel nut, make sure your gloves are dry to prevent any unwanted heat transfer...
Update: water soaked into gloves acts as a thermal conductor resulting in scalds if a gloved hand is applied to steel whose temperature is several hundred degrees above the boiling point of water.
Protip: when applying a socket wrench to a red-hot steel nut, make sure your gloves are dry to prevent any unwanted heat transfer...
Update: water soaked into gloves acts as a thermal conductor resulting in scalds if a gloved hand is applied to steel whose temperature is several hundred degrees above the boiling point of water.
Friday, January 14, 2011
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:
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:
Storage requirements are 2*(u+1) for a set of u integers. I thought this was interesting.
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.
Wednesday, January 12, 2011
Tuesday, January 11, 2011
Delegates in C++
I reimplemented the Baker valve gear simulator in C++ a few weeks ago. This involved adding a nonlinear equation solver to libkerr's matrix library, my custom-made high-performance linear algebra library that's been reused over the years in dozens of small projects and a few large ones.
The algorithm itself is nothing special: Newton's method. Implementing it in a general and yet efficient manner in C++, however, presents a design choice.
I was tempted to accept a template argument and call that class's operator() member function.
This, however, would require a separate class for each constraint function. In my case of coupled systems, I need to determine roots for two distinct constraint functions that shared both constant state and analytically computed state. Additionally, the zeros of the first function would be needed as input to the second function.
Instead, I opted for the delegate design pattern. The functor includes both the object as well as references to member functions.
Some additional features of my solver are the Jacobian can either be estimated by a default solver or computed analytically by a user-supplied function.
The implementation seems to work well and always converge. I haven't implemented an aesthetically pleasing visualization of its output, as this was mostly scratching an itch for implementing the constraint solver.
The algorithm itself is nothing special: Newton's method. Implementing it in a general and yet efficient manner in C++, however, presents a design choice.
I was tempted to accept a template argument and call that class's operator() member function.
template < typename Real, typename Functor >
int fsolve(matrix &x, const Functor &F, Real precision, int maxIterations) {
..
while () {
matrix fx = F(x); // operator()
}
..
}
This, however, would require a separate class for each constraint function. In my case of coupled systems, I need to determine roots for two distinct constraint functions that shared both constant state and analytically computed state. Additionally, the zeros of the first function would be needed as input to the second function.
Instead, I opted for the delegate design pattern. The functor includes both the object as well as references to member functions.
template <typename Real, typename Functor>
int fsolve(matrix<Real> &x, const Functor &F, matrix<Real> (Functor::*ptr)(matrix<Real>), Real precision, int maxIterations) {
..
while () {
matrix<Real> fx = (F.*ptr)(x); // delegate
}
..
}
..
BakerValve instance;
fsolve<double, BakerValve>(x1, instance, &BakerValve::constraintF1);
..
fsolve<double, BakerValve>(x2, instance, &BakerValve::constraintF2);
Some additional features of my solver are the Jacobian can either be estimated by a default solver or computed analytically by a user-supplied function.
The implementation seems to work well and always converge. I haven't implemented an aesthetically pleasing visualization of its output, as this was mostly scratching an itch for implementing the constraint solver.
Sunday, January 9, 2011
Ferroequinology: clearing A&WP 290's Boiler Shell
Yesterday, I visited the Southeastern Railway Museum and worked on A&WP 290 with Dale Grice.
In continuing with the goal of removing everything from the boiler shell to prepare for an eventual blast with baking soda, we removed a steam pipe carrying a "signal" that actuates cylinder cocks. A valve in the engineer's side of the cab raises steam pressure in this pipe which actuates valves at the bottoms of the main cylinders at the front of the locomotive that permit condensation and steam to blow out when the locomotive starts. This is why steam engines seem to start in a cloud of steam.
This required removing two unions coupling a network of steel pipes. I tried without luck during a previous visit to wrench them apart. Yesterday, we used a "rosebud" oxy-acetylene torch to heat the union coupling to dull cherry red then quenched it with a cup of water. The first coupling I tried this on came loose readily and after one revolution with the wrench [and plenty of time to cool], I removed it the rest of the way with torque applied by [gloved] hand.
The second union would not budge in spite of this treatment. Between heatings, I hit it with a hammer but it remained fast. Consequently, we used a cutting torch which emits a jet of oxygen gas through a flame and oxidizes steel. A short segment of pipe was cut between the union and a T-coupling thus freeing the main pipe along the boiler.
With unions apart, the cylinder cock pipe would come loose with the removal of a single bracket fastened to the boiler shell via a threaded stud. Unfortunately, the nut holding the bracket was corroded and could not be made to turn without heat. After heating to cherry red, a wrench with torque magnified by a breaker bar [steel pipe] eventually made some progress. Or we thought it was progress. After about half a revolution the nut fell off revealing we had literally torqued the 1/2" stud apart and never moved the nut. One more thing to fix on the boiler...
I manned the portable crane and we pulled the pipes off the boiler then applied a set of labels so they can be replaced or new copies made.
To reach the top of the boiler, the next step was to replace air cylinder brackets. These are large castings [weighing probably 50 or 60 pounds each] that suspend two large air cylinders along the locomotive, one on each side, and support running boards.
Again, I manned the crane lifting the castings up to the boiler while Dale aligned them with 1.5" diameter threaded studs. These studs were placed in the boiler from within when it was built and cannot be easily replaced without potentially compromising the boiler's integrity [not to mention incurring a laborious and detailed inspection]. The first bracket went on without much trouble but we discovered it was mis-labeled and didn't sit flush with the boiler shell. The next bracket didn't slide onto the studs at all, and we discovered the reason was due to the forward stud bent up and forward. The studs needed to be parallel for the bracket to slide on, and this clearly wouldn't do.
To straighten it, Dale fitted a large 12' steel pipe over the stud, and I climbed up on a scaffold. The plan was for me to bend the stud using the pipe as a lever. Doing this proved problematic; the pipe was not adequately stiff, and all force I applied deformed the pipe like a spring. I had visions of losing my grip and the pipe springing back; the last thing I would see is a 2.5" steel pipe swinging back to hit me in the face...
We abandoned this idea pretty quickly. When Dale attached a nut to the end of the stud and hit it with a sledgehammer without any success, he decided heat was the only solution. Again, the rosebud torch came out and in no time, the base of the stud was glowing cherry red. Each gentle stroke of the sledgehammer moved the end of it by about 1/4", and in no time we had straightened it.
Both brackets slid on without difficulty after this, and now we'll be able to add running boards and access the top of the boiler. Progress!
In continuing with the goal of removing everything from the boiler shell to prepare for an eventual blast with baking soda, we removed a steam pipe carrying a "signal" that actuates cylinder cocks. A valve in the engineer's side of the cab raises steam pressure in this pipe which actuates valves at the bottoms of the main cylinders at the front of the locomotive that permit condensation and steam to blow out when the locomotive starts. This is why steam engines seem to start in a cloud of steam.
This required removing two unions coupling a network of steel pipes. I tried without luck during a previous visit to wrench them apart. Yesterday, we used a "rosebud" oxy-acetylene torch to heat the union coupling to dull cherry red then quenched it with a cup of water. The first coupling I tried this on came loose readily and after one revolution with the wrench [and plenty of time to cool], I removed it the rest of the way with torque applied by [gloved] hand.
The second union would not budge in spite of this treatment. Between heatings, I hit it with a hammer but it remained fast. Consequently, we used a cutting torch which emits a jet of oxygen gas through a flame and oxidizes steel. A short segment of pipe was cut between the union and a T-coupling thus freeing the main pipe along the boiler.
With unions apart, the cylinder cock pipe would come loose with the removal of a single bracket fastened to the boiler shell via a threaded stud. Unfortunately, the nut holding the bracket was corroded and could not be made to turn without heat. After heating to cherry red, a wrench with torque magnified by a breaker bar [steel pipe] eventually made some progress. Or we thought it was progress. After about half a revolution the nut fell off revealing we had literally torqued the 1/2" stud apart and never moved the nut. One more thing to fix on the boiler...
I manned the portable crane and we pulled the pipes off the boiler then applied a set of labels so they can be replaced or new copies made.
To reach the top of the boiler, the next step was to replace air cylinder brackets. These are large castings [weighing probably 50 or 60 pounds each] that suspend two large air cylinders along the locomotive, one on each side, and support running boards.
Again, I manned the crane lifting the castings up to the boiler while Dale aligned them with 1.5" diameter threaded studs. These studs were placed in the boiler from within when it was built and cannot be easily replaced without potentially compromising the boiler's integrity [not to mention incurring a laborious and detailed inspection]. The first bracket went on without much trouble but we discovered it was mis-labeled and didn't sit flush with the boiler shell. The next bracket didn't slide onto the studs at all, and we discovered the reason was due to the forward stud bent up and forward. The studs needed to be parallel for the bracket to slide on, and this clearly wouldn't do.
To straighten it, Dale fitted a large 12' steel pipe over the stud, and I climbed up on a scaffold. The plan was for me to bend the stud using the pipe as a lever. Doing this proved problematic; the pipe was not adequately stiff, and all force I applied deformed the pipe like a spring. I had visions of losing my grip and the pipe springing back; the last thing I would see is a 2.5" steel pipe swinging back to hit me in the face...
We abandoned this idea pretty quickly. When Dale attached a nut to the end of the stud and hit it with a sledgehammer without any success, he decided heat was the only solution. Again, the rosebud torch came out and in no time, the base of the stud was glowing cherry red. Each gentle stroke of the sledgehammer moved the end of it by about 1/4", and in no time we had straightened it.
Both brackets slid on without difficulty after this, and now we'll be able to add running boards and access the top of the boiler. Progress!
Wednesday, January 5, 2011
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...
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...
Subscribe to:
Posts (Atom)