« October 2008 | Main | December 2008 »

November 17, 2008

Sorting out Pixels or How I Didn't Plan to Spend My Sunday

I wasted, well maybe wasted is too strong of a word. I used way more time than I should have on Sunday playing with Pixel Bender trying to figure out how to make it sort values. In my trend to make Pixel Bender do stuff besides manipulate pixels I thought a fun mental exercise would be to implement a parallel sort. Now I've not come up with any good use for this yet, considered if this is the best performing parallel sort, yadda, yadda, but it works, which is what I really wanted to get out of this experiment.

While quicksort and mergesort are efficient given their O(n*log(n)) runtimes, they require iteration which isn't what Pixel Bender is good at. I ran across one paper that outlined a parallel sort on a linear array of cellular automata algorithm but its running time was O(2*n-3) cycles. For a reasonably large array I was concerned about exceeding the size of an image that I could feed into Pixel Bender.

As always, Knuth had an answer. On page 111 of his Sorting and Searching tome, he outlines Batcher's sorting scheme which is characterized as a "merge exchange sort". The key piece that makes the algorithm attractive for what I wanted to do is that step "M3. [Loop on i.]" can be done for all relevant i in any order, even simultaneously. [Knuth 111]. It also scales nicely, with worst case steps required to sort being O(1/2*ceil(log_2(n))*(ceil(log_2(n)+1). At 4096 elements 78 steps are needed while at 262,144 elements only 171 steps are needed. I'm going to exceed the width much more quickly than the height.

Doing a rough implementation of the algorithm in ActionScript was straight forward:

/**
* Merge Exchange Sort using Batcher's Method
* Knuth, The Art of Computer Programming,
* Vol 3. Sorting and Searching, Page 111.
* @param data The data to be sorted, will be modified inplace
*/
private function mergeExchangeSort(data:Array):void {
    // Sanity check
    var n:int = data.length;
    if (n < 2) {
        return;
    }
    // M1. [Initialize p.]
    var t:int = Math.ceil(Math.log(n)/Math.log(2));
    var p:int = Math.pow(2, t - 1);
    do {
        // M2. [Initialize q, r, d.]
        var q:int = Math.pow(2, t - 1);
        var r:int = 0;
        var d:int = p;
        var loopOnQ:Boolean = true;
        
        do {
            // M3. [Loop on i.]
            for (var i:int = 0; i < n - d; i++) {
                if ((i & p) == r) {
                    // M4. [Compare/exchange R_(i+1):R_(i+d+1)]
                    if (data[i] > data[i + d]) {
                        var temp:Object = data[i];
                        data[i] = data[i + d];
                        data[i + d] = temp;
                    }
                }
            }
            // M5. [Loop on q.]
            if (q != p) {
                d = q - p;
                q = q / 2;
                r = p;        
            } else {
                loopOnQ = false;
            }
        }
        while (loopOnQ);
        
        // M6. [Loop on p.]
        p = Math.floor(p / 2);
    }
    while (p > 0);
}

The variables, p, q, r, and d are bookkeeping and my thoughts was that I would pass these in as values for each row in the pipeline. While the M3 and M4 piece would be the actual parallelized sorting piece. I quickly hit my first problem when I discovered that it doesn't look like I can do bitwise operators in Pixel Bender. The ((i & p) == r) line is vital to only testing possible exchanges at specific indexes for a particular step. It is in fact what gives the algorithm its complexity and beauty.

My next thought was to manually calculate the bitwise and using what functions I had available in Pixel Bender. In the back of my mind I think there is some eloquent way to do bitwise operations that I've forgotten since college (and some quick Google searches didn't refresh my memory). Just wanting to get something working I hacked together a quick little routine that used only operations available in Pixel Bender. Thankfully Pixel Bender does support modulus. This is the ActionScript version of the code:

private function bitwiseAnd(a:int, b:int):int {
    var result:int = 0;
    var n:int = 1;
    while ((a > 0) && (b > 0)) {
        if (((a % 2) == 1) && ((b % 2) == 1)) {
            result += n;    
        }
        a = a / 2;
        b = b / 2;
        n = n * 2;
    }
    return result;
}

I had forgotten that Pixel Bender, when exporting for Flash, doesn't support loops :( I unrolled the loop for the largest values that I thought I'd test with, yay cut and paste. Then I ran into another subtle aspect of the code that I'd skimmed over. Primarily the fact that when looping over i it is doing a swap of the elements. Given that I'd be running in parallel I really had to calculate not only if i was bigger than i+d but the opposite at the same time. That would mean another unrolled bitwise and operation. This was turning into more of a pain than I had hoped and I was far exceeding whatever playtime limit I'd set aside for this little project.

Alas, for better or worse as Brian has aptly pointed out, I have a tenacious personality. I did take a break to run some errands, eat some more of the yummy chicken stew I made last night, and catch up on some saved TV shows. I came back, didn't have any insight, and figured I'd just write up this blog post. Half way through writing it I had an insight. The p, r, q, d, and i nonsense is just bookkeeping overhead. For a fixed size n, the values of p, r, q, d, and what swaps need to be made can be calculated once and reused as part of the pipeline.

Pixel Bender supports multiple source images. One could be my input data and the other could be the bookkeeping junk. (Insert long pause while I try this out). Success! I've now used way too much time putting this together. I only hope I haven't forgotten something else that I was supposed to be doing...

The couple of changes are before M3 in the algorithm mentioned above, I store the value of d in my bookkeeping bitmap:

// Pass along the value for d
step++;                        
bitmapData.setPixel(0, step + Y_OFFSET, d);

Then I replace M4 with the following change:

// M4. [Compare/exchange R_(i+1):R_(i+d+1)]
// Store the fact that we need to make this comparison
bitmapData.setPixel(X_OFFSET + i, step + Y_OFFSET, RIGHT);
bitmapData.setPixel(X_OFFSET + i + d, step + Y_OFFSET, LEFT);

This stores either a compare to the right or compare to the left value in the bookkeeping bitmap.

Lastly to get the pipelining working, the Pixel Bender code operates offset by one row. That is when working on row 1 it is pulling source pixels from row 0. This way each time the code runs the source row can be changed but the previous rounds values will continue to work down the sorting steps. This way if you can feed new data into the system every step and then after the minimum number of steps needed start pulling data off the other end that has been sorted. The cheesy UI I put together to test the code demonstrates this pipelining effect.

The Pixel Bender code ended up being straight forward once I introduced the bookkeeping bitmap. The only funky thing is doing the comparisons. Since I'm setting values as pixels, when in Pixel Bender it is chopped up into RGB which means a little special handling. Also, I've had some issues with float versus integer comparisons so don't be surprised if there are some stray oddities in the code. This then is the core of the algorithm on the Pixel Bender side:

// grab the data to figure out what which direction to compare with, if any
pixel4 bookdata = sampleNearest(book, outCoord());
// grab the d value to use, which is always stored at x = 0 for this row
pixel4 dData = sampleNearest(book, float2(0.0, outCoord().y));
// convert it into a real value, only need GB since we would create images too large otherwise
// although I don't know what the size limit is...
float d = dData.g * 65536.0 + dData.b * 256.0;
// grab the previous step's data, doing this makes for easier pipelining
pixel4 me = sampleNearest(src, outCoord() + float2(0.0, -1.0));
// default to doing nothing
dst = me;
// always skip x = 0 as that holds bookkeeping information
// and skip y = 0 as that is the start of the pipeline
// we read the previous row and write in this row
if ((int(outCoord().x) != 0) && (int(outCoord().y) != 0)) {
    // need to compare to the value on our right at me.x + d
    if (bookdata.r == 1.0) {
        pixel4 right = sampleNearest(src, outCoord() + float2(d, -1.0));
        // simplistic way to make the RGB compare like a number, can probably be optimized
        if ((me.r > right.r) || ((me.r == right.r) && ((me.g > right.g) || ((me.g == right.g) && (me.b > right.b))))) {
            dst = right;
        }
        // need compare to the value on our left at me.x - d
    } else if (bookdata.g == 1.0) {
        pixel4 left = sampleNearest(src, outCoord() + float2(-d, -1.0));
        // see note above
        if ((left.r > me.r) || ((left.r == me.r) && ((left.g > me.g) || ((left.g == me.g) && (left.b > me.b))))) {
            dst = left;
        }
    }
}

Give the finished application a try. Flash Player 10 required. It currently limits the values to 0xFFFF and the number of elements to 16 so they fit in the grid. View the full source if you want to play with it some more.

Tags: flex pixelbender sort

November 11, 2008

Architecting a Shared Codebase from Browser and Desktop

Architecting a Shared Codebase from Browser and Desktop
By David Coletta

Maybe more hacking than Architecting. First time giving the talk so all feedback is welcome.

Goal: Build a browser application and an AIR application from a single shared codebase.

Four areas of concern: UI design (People have different expectations for a desktop based word processor versus a web based word processor), shared code packaging (giant pile of code delivered in two different forms, downloaded modules versus bundled with application), abstracting the AIR APIs (clipboard access is different in the two models), many other things including Singletons.

Primary UI differences: Browser version surrounded by browser chrome with AIR the application looks cleaner. Demo of Buzzword in browser and the AIR desktop version. Native menus in desktop menus versus flex based menus.

UI issues: Installation, automatic updates (Much improved in 1.5), menu bars (browser to native menu translation, native menu model is different between Mac and Windows, AIR APIs insulate from menu accelerators), multiple windows (on Mac you need to manually switch which menu is active based on the window, versus on Windows it is attached to the window), transition between the two (link to Buzzword opening in browser versus desktop if you have it installed, do runtime detection if AIR application is installed, if Application is running can use local connection), opening hyper-links, remember me (skipped talking about this), URL display (command that copies URL of document into clipboard), going to sleep and waking up, modal dialogs (in browser best you can be is window modal in AIR you can block the entire application), language preference.

Shared Code

Two modes: Browser SWFs loaded by AIR version, mostly SWCs linked in by two level application.
Went with loaded SWFs as browser version was already doing that, looser coupling meant faster builds, did require Ant to package it all together for development and production
In browser downloading latest version always happens. AIR application captures static version of modules. AIR does version checking at startup to see if it running the latest.

How much updating of an installed application will a user tolerate? Will things still work after the update? Old code running against new version of the server was already handled since people maybe using Buzzword in a browser during an upgrade, but its still an issue.

Abstract AIR APIs

Writing code like "if (isAIR) {} else {}" just won't work. Easy to forget its shared code. Errors when code is loaded and trying to run.
Common approach is to create an interface with two implementations. PlatformBroker with AIRPlatformBroker and FlexPlatformBroker as subclasses. As it for an interface and get that back. IPersistenceSecureToken is the interface with BrowserCookie (using ExternalInterface) and EncryptedLocalStorageCookie (using AIR facilities) implementations. Flex version is okay to live in AIR application, but not vice versa.

Singletons

Convenient but breaks when a single application is running with multiple windows on the desktop versus separate VM instance per window in browser. Solving the singleton issue for AIR required rewriting the browser version since the majority of the code was shared. Singleton was easier to get going but had issues when adding multiple window support.

Rich text support

Major problem for Buzzword. Needed to support copy and paste of rich text. Had to have hacks for browser support with hidden div. Very fragile. AIR has it's own issues since you only get raw HTML, not formatted, normalized, or parsed for validity. Ran it through HTMLLoader.

Other issues

Relaunching (browser errors just reload the page, no real way to do it in AIR, but can hack it with relaunch via air.swf but you have to be online), AIR update framework (much improved with AIR 1.5), Flex menus versus native menus from single model (created XML reader with factory methods), internationalization and localization (Buzzword currently has multiple versions, localized in SWF and loaded based on preference at runtime), Runtime CSS versus compiled CSS, idle tracking (rolled own for browser, AIR has API for idle tracking, used for autosaving and turning off server session).

99% of the code is shared between the browser and desktop applications.

Session is primarily serving XML, co-authoring shared batton is server based, does long polling (server holds client request until it has data to send to it).

Tags: air architecture flex

November 7, 2008

Change

With the election of Obama as the 44th president the transition process has begun. In continuing his use of new technology and grass root movements the new administration is looking for your ideas. Read about what Obama's plans are and contribute at Change.gov.

Tags: obama

November 3, 2008

Tripping on NeoPhi

As most regular readers of this blog know my housemates and I are having the house de-leaded. This unfortunately means temporarily vacating part of the house while it is worked on. Thankfully despite the age of Gilman Manor it had very little lead. One area that did have lead was near where NeoPhi lives. This of course necessitated moving NeoPhi. That went smoothly and should have only been seen as a short network blip and NeoPhi's and its UPS moved smoothly into another room. Alas the short blip turned into a two hour nightmare for me as once in its new home while trying to get something I forgot I was going to need I knocked NeoPhi's power cord out from the UPS.

Needless to say it wasn't happy. The fsck during reboot was taking an extremely long time and I thought that it had died on me. When I was about to give it it started beeping horribly. A sound I'd never heard before and hope to not hear again. In a panic I killed the power again, the beeping stopped. I turned it back on and during the RAID firmware startup the beeping started again. After another quick reboot I went into the RAID BIOS. It was in the middle of a rebuild and the alarm was the indication that bad stuff was going on. No problem. While I could have let the system startup and run in a degraded mode while rebuilding I figured it was best under the circumstances to finish the rebuild in the BIOS.

That looked like it was going to take about an hour to do. Fine I finished moving stuff around, read my email, and worked on other stuff to pass the hour. Upon returning it was stuck at 90.1% complete on the rebuild. I waited, still at 90.1%. I waited some more. Finally after 10 minutes is ticked up to 90.2%. I'm like this can't be good. I went into the the event log and it was slowing filling up with Read Error on Channel 4. Great. Thankfully since I'm running RAID 6 I wasn't too concerned about lost data. Maybe just some corrupt data due to the power loss.

Looking around the BIOS some more though I couldn't find anything about my hot spare drive. Instead I found 2 RAID sets one which was incomplete and the other had only 4 disks (one of which was my hot spare). Guess this is why they highly recommend buying the battery backup for your RAID controller. Given how long the read failure for drive 4 were taking I took an unorthodox step and just yanked its cable from the controller. The event log quickly reported that the device had been detached and in a couple of minutes the last 10% of the rebuild finished.

At this point I was able to boot up in single user mode and ran a manual fsck on all the partitions. I got some really nasty errors from fsck that I've never seen before. A little research said there wasn't much hope of really fixing them so I just said Yes and let fsck do its thing. Once all disks passed fsck cleanly I rebooted again. I deleted the single drive that was part of the incomplete RAID set (which was really one of the primary drives of the original RAID set), added it as a hot spare and rebooted again.

NeoPhi is now back up and running. While I type this the RAID is doing another rebuild in the background and I have the one drive that was getting read errors sitting next to me soon to be replaced with a new drive from Newegg. Unfortunately along the way I again learned how limited RAID control support is for OpenBSD as I couldn't even use the alarm silence function of bioctl to shut the damn thing up. I must say though that the Areca support under OpenBSD at least exists, unlike my previous 3Ware card. Now I can at least get the status of the rebuild even if some of the other features like seeing the event log don't seem possible.

I'll probably do a reboot when the new drive comes in since I don't think hot plugging an internal drive is the best thing to do, even if I did unplug one that way. The thing that gets me the most about this little incident is a friend of mine had serious problems with his VPS at Dreamhost. Seems like no matter what you do eventually hardware or software failures will catch up with you.

Update: Seems the network port and or cable that I plugged NeoPhi into last night degraded over the night or possibly something got fried when the house lost power for 20 minutes this morning. In either case, slightly before the construction crew got fully setup I swapped out the cable and that seems to have made the network happier.

Tags: gilmanmanor neophi

November 1, 2008

Randy Pausch Quotes

Many months ago I watched Randy Pausch's last lecture. Below are some of the quotes from the talk that I took away and just found under a pile of other stuff on my desk. Some of these he credits to other people, see the transcript for details.

Fundamentals, fundamentals, fundamentals.
When you’re screwing up and nobody’s saying anything to you anymore, that means they gave up.
Have something to bring to the table, right, because that will make you more welcome.
Experience is what you get when you didn’t get what you wanted.
Brick walls are there to stop the people who don’t want it badly enough.
I think that that’s one of the best things you can give somebody – the chance to show them what it feels like to make other people get excited and happy.
Get a feedback loop and listen to it.

Tags: life quotes

Nude Riding a Bicycle and In Bed with Google

It feels like ages ago that I made a post even though its only been a few weeks. I've been a little busy and writing a blog entry was fairly low on the list. After last night's activities I feel compelled to fill the gap.

Awhile ago Allurent moved and in the process I acquired a mannequin. At the time I solicited suggestions but nothing inspired me. Earlier this week Annalisa sent me information about a Halloween Bike Ride that was taking place around Boston. Given that I hadn't come up with any other Halloween plans it sounded like a grand idea. It also served as the inspiration for decorating my bike, with what else but, a mannequin. Given the reactions I got while bringing it home on my back I figured a more elaborate setup (and one that I could ride with for the night was in order).

TR gave me the idea of mounting it to my bike rack which would better support the weight than strapping it to my bike like I did in order to get it home. The tricky part was figuring out how to get it on the bike so that it made some sense and could still be ridable. Thankfully with some help from Clara, 3M Packaging Tape, and a little ingenuity it came together. Hence was born "Nude Riding a Bicycle". The ride itself was a blast with over 240 riders starting it off. Some dropped off as the route meandered around Boston but there was a strong presence to the end. My hats off to the organizers for a great night and to New England weather for making the night tolerable.

In other news I've gotten in bed with Google more than I thought I ever would. For a long time I've been running this little neck of the Internet known as NeoPhi including my own web server, mail server, etc. It's given me the freedom to do just about whatever I want. This month I changed some of that. In particular I changed my mobile phone. While for some this maybe a common occurrence, it isn't for me. This is only my third mobile phone, ever. My previous two were each with me about 5 years. It's not that I haven't thought about getting a new phone I just didn't find anything worth switching to.

I seriously considered the iPhone but couldn't justify the price and frankly wasn't that interested in switching from T-Mobile. I looked into some other 3G phones that debuted in European markets but T-Mobile's 3G service either wasn't compatible (since it used a different spectrum) or didn't exist were I would have been using it. Flash forward to a couple of months ago when the G1 was announced. A form factor that was close to my old phones, a platform I could easily develop for if I wanted to, it worked with my provider of choice, and had some cool apps. Without ever seeing one in person I pre-ordered it and picked it up the night of Oct 21.

My impressions so far have been very favorable! My biggest complaint is that with only some of the features turned on the battery drains pretty quickly. My last phone would last at least 3 days between charges while with the G1 I'm having to charge it every night. The touch screen is great and having access to a full physical QWERTY keyboard has made working with it a breeze. The web browser has handled various sites I've thrown at it and I've already downloaded and used some other applications from the Android Market.

In order to start using the phone though you must tie it to a Google account. While I do have a GMail account, it isn't my primary email address. I mostly created it to get access to Google features before they let you sign up with any email address. Given the tight integration between the phone and Google I thought it worth considering what life with Google would be like. I previously used a Palm to track my calendar and contacts (those details that my phone couldn't handle like addresses). With my new smart phone it felt like overkill to carry around both devices. The biggest hurdle though was email.

I figured my insistence on using procmail, SpamAssassin, and Pine to read me email while serving me well for the past 13 years may have been due for an update. To enact the change I signed up for a Google Apps Premier account. Which means that Google and Postini now handle email for my domain. The premier account also lets you import old mail via IMAP which made migrating 13 years and a couple gigs of email a breeze. Well not an entire breeze. My local cataloging system didn't directly translate into Google's label system so after all of my email was in my GMail account I did have to spend a few hours massaging labels to make it work. Now that it's all done though I must say GMail is a reasonable replacement for my old system. More importantly I have complete and easy access to all of it from my new phone.

My contacts and calendar on the other hand are an on going effort to migrate them to Google. In particular getting the data out of Palm Desktop into a format that could be imported into Google was not straight forward. While there are some applications that can synchronize between the two, I didn't want to shell out the cash for them since I wasn't planning on continuing to use my Palm once the transition was done.

I ended up using Apple's Address Book and Calendar to read in vCal and vCard exports from Palm Desktop. I then used a 3rd party utility to export my address book into a Google friendly format and iCal's native export format. Like my email the translation process isn't perfect and I suspect there will be a couple hours of cleanup for each data set before it's Google friendly. In retrospect though it's also prompting me to do some house cleaning of the data which is sometime I've been trying to do in general.

In the process of moving my digital life to Google I also moved my computing life to a new Mac Book Pro. While trying to do the development on PPE the speed of Java on my old G5 PPC was really starting to annoy me. Conveniently the rumor mill said that Apple was about ready to release new some Mac laptops. Turns out the rumors were true and on Oct 14th that happened. I'm very pleased with the new solid case design. While at first I lamented about the lack of a matte finish for the screen, given when I most often use my laptop it hasn't been something that has bothered me as much as I thought it would.

Needless to say between the new laptop, phone, visiting Elissa, having the house de-leaded, and migrating my digital life to Google, my free time has been minimal. For me busy is happiness which has made these past few weeks fly by nicely. I'm hoping to get back to PPE as I really want to move that along so it doesn't become an abandoned project of mine. My closing hint is that when copying files from a Mac with rsync be sure to add the -E flag. Thankfully I had backups and you should to. Time capsule is overpriced but the convenience of wireless piece of mind backups is great.

Tags: android g1 google life mac neophi

About