Parallel Processing Predictions: Part II

Last we left off, I stuck to my theory that applications would remain sequential - and that parallelization would be done implicitly through interaction with the OS. I gave a hint to my thinking by specifying that there is a delay between creation of an object, and it's actual use.

Previous Work First, Amdahl's Law [Wikipedia has a good write-up on it]. You can't go faster than the slowest serial portion of your code. DrDobb's has an article on beating Amdahl's law[DrDobb's Article]. I disagree - speeding up the execution on a single processor still means your are bound by the serial portions of your code.

For your reference - I consider SIMDizing[Intel has a good intro to get the idea] to be parallelizing code; as well as reordering instructions to maximize the use of the underlying execution units[Apple's write-up is a bit dated, but I like it.].

So - you must be laughing. I should explain in this post a miraculous way to make all of today's code parallel. Well, most of today's code parallel -- as long as the OS incorporates these changes.

I will give credit to Intel's Thread Building Blocks and distant relative CILK. I shouldn't forget Grand Central Dispatch - if only for it's ability to do task-scheduling with a view of the entire system load.

Aren't these great solutions? Oh yes. Brilliant. Tackling issues of data locality and efficiently doing work across multiple cores. Essential given the future is parallel.

Then what's the problem? If they optimally express the intentions of the programmer, none what-so-ever. For me, just keeping track of what is running, and can be run is not a "good thing".

Inspiration: When I think of implicit parallel programming, I think OpenGL. Even though drawing requests are done in sequence. For example, you can draw plenty of geometry - but that geometry is just cached in a buffer and drawn when the GPU has time. So while the code is doing whatever logic it needs to do, OpenGL is working in the background getting stuff done. And it's not only the video-card that's running, but part of the API. States need not take effect until they are actually needed.

The other thing I'd like to point out is the intelligence of compilers - more exactly, how much optimizations they can do. I'm not suggesting the Octopiler or something similar.

I'm suggesting devising APIs that are designed from the ground up to do work in parallel. But also increasing the integration of the compiler within the process (I'm sure someone else thought of this, there are brilliant people in CS departments around the world. I'm thinking aloud since I enjoy it. It also helps me coherently determine how my code should evolve.)

To avoid the simplicity that is a graphics API, let's consider another object. Let's say an object that does set manipulations. We have intersections, unions, enumerations, and all the wonderful related dangers to parallelizing these operations. A quick google search will lead to results of people writing codes using atomic operations, and making mistakes using atomic operations. So, in this part I'll document how this API would be presented to the end-user and how it could be implemented.

First, I can feel the temptation to say that all objects are immutable - that all mutations happen over copies. However, that is - how to say this - cheating. Our goal is to not change existing code as much as possible.

The API: The end-user of the API can do whatever they're used to doing with scalar code. It's the API itself that must do the miracles.

The Inner Workings: Finally, the moment of truth, how would it work? Let's assume that we are building on Grand Central Dispatch; with cache coherency methods similar to those of Thread Building Blocks (hybridized - these would do a great team for the next few years).

The general strategy is that the API has a series of sequential tasks. These tasks can run in parallel (even later) until the user actually makes a request for data. This leaves us with a few cases - the major ones are Immutable and Mutable.

Ok, Immutable objects are the easiest. We will add a state to the objects: "Pending". An Immutable object is in a "Pending" state if it hasn't completed initialization. We will also add a sequential list of tasks that can run asynchronously.

The entire API's logic is run on this asynchronous task list. Each task is sequentially numbered by the sequential portion of the API.

The easiest methods are those that return a new object. That might be a list, or something else. As long it's all part of the same API; it doesn't matter. This new object, Immutable or not, is not really an object, but more like an IOU. It holds the ID of the task and is put into a "pending" state. The same is true for existing objects stored within the data structure.

The next easiest method is functions that return basic data types. These could be defined to return a special wrapping object; so they'd behave like their object counter-parts. I'd suggest making the compiler hide these gory details, and use decent heuristics to determine if the overhead of creating an object is worth it.

But back to those returning basic data types. We'd get an ID of a task; but would stall the execution of the sequential code until the data was received.

Wouldn't we always be stalling? Here's the beauty of the solution - we know what work we must do sequentially. We can also do dependency checks. If one operation doesn't depend on another, it can be scheduled to run in parallel. Even; individual tasks could be made to run in parallel (like the intersection of two sets).

Next are the Mutable objects. Surprisingly, these aren't that different. Really.

What I've just done is outline how to parallelize a sequential application by properly engineering the backend libraries. This parallelization is completely transparent to the end-user of the API.

This basic solution might be enough to divorce an application's serial logic from the immensely parallel nature of the underlying computational hardware.

Parallel Processing Predictions: Part I

I've been thinking of parallel processing as of late. I've coded a task scheduler with a few swappable algorithms in the backend to test performance; seen my programs degrade in performance as the number of cores increase; and literally learn everything the "oops I made a mistake" way.

So, standing upon my pile of errors; I'm going to attempt to predict what will happen (some of it very long term). Some of it we already know - hardware will make a massive shift. Others; well - let's see if I'm right about any in the next decade.

No Change For Most: 99% of applications will remain sequential in nature and never directly deal with threads. This sounds crazy; I know given this massive push towards multi-core - but it's an unshakable conclusion in my mind.

Rather, libraries will be parallel and asynchronous - making "DIY" algorithms an even sillier affair. As a simple example: consider comparing two strings. There is a time since the request to compare the strings is sent, and when the value is actually used. If we use something like Grand Central where the threads are already spawned and just need to be used, then we're talking low-overhead implicit parallelization.

Essentially, libraries will present a sequential interface. User-land code will not need to know about parallelism - but will take advantage of the hardware when the programmer leverages the underlying frameworks.

Right about now, some people probably want to remind me that the GUI runs in the main thread whereas heavy processing is normally put into a secondary thread with mutexes to coordinate the two. I'll recall olde code that actually split up the processing so that the GUI event-pump could run. Even, olde code that would, at explicit times, yield execution to the GUI. Just yield when data is available to update the GUI, much less messy than having locks in obscure places. Normally, for such things, I have one lock that synchronizes events from the GUI on the separate thread with my work thread. The more sequential my code, the easier it is to work with.

Procedural Over Functional: Again, the Haskell fans will most likely disagree. Actually, I'd rather code parallel code in Haskell at times... But; let's not get distracted - I believe procedural code will maintain it's reign. The reason is simplicity. Everyone understands a TO-DO list, a sequence of instructions, manuals, etc. No manual I know asks you to trace to the desired result to get to the start of the solution (sometimes I feel like I'm rigging code to have side-effects to get it to run in functional languages).

Even if languages like Haskell are "better"; the rich and parallel underlying libraries of the system will make the entire thing moot.

Software Diets: Back-end system libraries will overthrow software complexity. That is, the OS will provide so much functionality that an application will simply have to connect the pieces. Some specialization might be needed; but very little.

This availability of features in the OS will change the software landscape. Software that does not properly integrate into the OS (that will have a global strategy for multiprocessing, with libraries optimized for that strategy) will slow down.

Think of it this way: the OS and it's libraries will shift together. And as hardware changes, so will the OS-provided libraries. Software using it's own libraries will need to adapt; but those using the OS-provided libraries won't.

This raises problems for multi-platform toolkits as I figure that certain functionality will be radically different on different OSes, even though they accomplish a similar thing.

Hardware Rollercoaster: See the disconnect between the user-land software and the hardware? Well, that means the underlying hardware can change more drastically. If the OS is the only one that needs to know about the specifics of the hardware and the user-land software just needs to focus on the algorithm; then people shouldn't even notice the insanity that is going on underneath the hood.

This implies that something akin to the LLVM project would be used to compile to a machine-independant level and complete compilation on the final hardware.

More Open-Source: Not the year of Linux; but the year of the open-source libraries. The added complexity of the underlying libraries will mean that they are more costly to develop. I'm not advocating using the spare time of developers to advance a corporations heavy work; but rather problems will be shared among OS vendors. Open-source is just a way to save money by reducing the amount of redundant work among companies.

If I had to wager, I'd say a BSD-style license - so each vendor can advertise having an upper-hand when marketing to consumers.

In the end... We aren't headed towards great doom when it comes to multi-core. Yes, people are panicking now as they realize all the caveats, however we've known for quite a while that 10% of the code is responsible for 90% of the execution time. That 10% of the code, in most cases, should be part of the OS and supporting library.

Final Ramblings: I referred to Apple's technology since I'm more familiar with it. I'm sure Microsoft is doing something similar - and that the .NET runtime might be better suited to the type of parallelism that I'm describing.

Now that I've predicted that nothing much will change for your average programmer; I'm going to do a part 2 - and detail exactly how I see the underlying libraries and hardware shifting. In part 3 - I'll explore how the development environment could change.

These predictions aren't final. As I learn more and read more of the results from the scientific community, my predictions may be refined over time. I won't delete these pages; but admit my mistakes and document how I erred.

One last thing. As a reader, you must have noticed the lack of references in this document. I don't trust texts without references. Neither should you. This part essentially puts forward the theory that user applications will just, in the worst case, need a recompile and keep on running using all the available hardware.

All this despite the move to multicore.

The wonders of NSString

This post is much less of a rant, and more of a regurgitation of how to use NSString as a way to solidify it in my memory and provide a useful way to look it up (I think it'll get buried and I'll forget about this post, making it a form of future e-waste.  Where e-waste is knowledge that accumulates, but serves no purpose in the present except take up space.).

So... the lowly NSString.  Where shall I begin?  Maybe with the simple idea that whatever text processing I needed to do, NSString (and supporting objects) always seems to provide a means to do it (sometimes thanks to methods added after-the-fact to the NSString object).  And also that getting a C string is almost never needed unless interacting with a C library (the standard C library shouldn't be needed).

NSString is very similar (for historical reasons) to Java's String object.  Both can not be changed after being created, changes are rather require the creation of a new object (In such cases - NSAutoReleasePool is your friend if you find yourself doing innumerable string manipulations):

NSAutoreleasePool *p
    = [[NSAutoreleasePool alloc] init];
//Do plenty of string operations using
//[NSString string*] methods.
[p release];

That's the beginning. Ok; time for some fun! Let's say there are plenty of string constants that need to be internationalized? The simplest solution is to write the following for strings:

NSString *s = NSLocalizedString(@"Hello", @"Greeting String");

If you've set up your translation files correctly (get them using genstrings), then "Hello" is the word to get in the current language, and "Greeting String" is a hint to the translator.

Can we do more with NSString? Of course! splitting, loading a string from a file, and all sorts of other operations can be done.

I'll just note a few objects that can be useful rather than give a complete tutorial on them (the Apple docs are very good).

NSCharacterSet defines a set of unicode characters.  This object provides a quick way to get all white-space, all punctuation, and even all newline character sets.  Very useful when parsing files or breaking up strings.

NSScanner provides a nice way to scan any arbitrary file.  It is much more flexible than the standard C/C++ file operations in that it returns the data (String, float, etc. - even delimited to an NSCharacterSet) and a boolean specifying whether the data was obtained.  This makes parsing more complex files... easier.  (I don't doubt that it can be done in C/C++ - just that assuming the structure might vary rather than be fixed is a nice one.  eg.  optional floating-point number would be read as 0 in C++ if memory serves.)

NSXMLParser is nice - but I'm not really a fan of XML.  Let's say that there are neater ways to represent data than XML.  XML is nice for being standard - but the tags are just too much for me.  But it's there and works great!

NSString can also do everything that the standard C library does.  Just that I don't worry about memory buffer sizes.  I'm not familiar enough with the C++ String class to comment on it.

And for speed, CFString allows quick access to the underlying data:

//Direct cast -
//toll-free-bridge as Apple calls it.
CFStringRef r = (CFStringRef)@"NSString";
CFStringLineBuffer b; //... inline buffer used to iterate...

So yes - this has devolved into a rant. It's conclusion: look at what NSString does. It does a lot more than what you think. Especially thanks to categories that allow for any programmer to give NSString more functionality (that's how it can render text to views - and how external libraries could use it - to render strings to textures, etc.).

Unfortunately, this is true of most modern APIs - and for all objects. That is; the objects can do so much. It's no longer a question of knowing how to do something - but knowing the magic keyword that will return the proper function in a search result.

OK, a mini-rant,

<rant>
Programmers now work at such a high-level. And that high-level will allow us to keep on coding as normal while everything transparently becomes parallel (something I've been thinking a lot about recently - the challenge may appear great; but in retrospect abstraction makes it easier. As a hint - we parallelize like the CPU does with instructions. Branches are our undoing - yes I'm captain obvious. I think QT Concurrent is the closest to what I'm thinking - but there is a way to provide a sequential API with parallel underpinnings. It already in the form of OpenGL. The real trick - which I'm almost done tinkering with - is how to get modules that don't know about each other communicating in a relevant way in parallel.).
</rant>

iPhone 4 Ranting

<rant>

Note: as usual - no research, just a personal opinion.  I like the opinions page in newspapers by the way!  If there's a massive flaw in what's said below; just leave a comment.

So today; we have the results.  Owners of the first batch of the devices (as per the Apple standard, there's a problem with them) can easily get a full refund, or get a free case.  Which, I believe, to be a good result.

For those complaining about the delivery:  if they were to admit fault in the product, they'd probably open themselves to more trouble than it's worth.  The delivery ensures people get a working device or a refund (good for the customer) while minimizing the impact of the negative consequences due to the device malfunctioning (good for Apple).  It's win-win if it all plays through as expected (unless if some die-hard person/fanatic desperately wants the device to work without a case and survive a death-grip: where the death-grip hasn't been replicated by everyone).

So... now, what's more interesting than the actual response from Apple?  the comments on various forums.  I'll classify them into the following categories:
- Emotional: I don't know how I could get emotional over an Apple product.  Some are infatuated, some are angry.  It's a device - if I want to play with my emotions, give me a good story!
- Quick Point: Some use it as a bargaining chip to advocate the Android platform / open source / etc.  Of course, that platform hasn't been without it's own issues - and certain vendors do lock it down.  Shouldn't people just walk into a store, try out the machines, and see which one best matches how they expect to use it?  And if it doesn't work - return it?  In the store of some wireless provider, I'd rather muck with menus/devices rather than compare feature-sets.  Yes - some have a lot of features; but when accidentally pressing other buttons is possible, it gets annoying.  Feature-sets and statistics can be equally rigged I believe.
- Realists:  Actually work out the numbers of the statistics thrown out at the event and question their validity.  The result is that things probably aren't as rosy as the statistics intuitively say.

There might have more; but that's enough for now.

I'm waiting until the dust settles until even considering that device.  Actually, I'm more interested in an iPad.

On a side-note: people completely driven by emotion scare me.  It's not funny how people's emotions play such a role in who gets elected here...

</rant>

Rant on The Concept of Task Scheduler

<rant>
A few days ago; browsing Wikipedia; a small little detail caught my eye.  The .NET framework is finally getting a means to schedule tasks.  Task schedulers are nothing new (they have a fairly long history), the most prominent at the moment are Intel's Thread Building Blocks and Apple's Grand Central Dispatch + Operation Queues.

In general, the idea is very simple.

Threads + critical sections + error-prone humans writing code = race conditions + deadlocks + other "joys".

Ok.  That's not good!

The race conditions are never a good thing.  What we want is to get rid of race conditions (or eliminate their likelihood).  Race conditions arise from bad use of critical sections, such as two threads mutually blocked for each others' held resource.

Eg.  Thread A needs fish and thread B needs bread.  Thread B has the fish and won't relinquish until it has the bread.  Thread A has the bread and won't relinquish it until it has the fish.  Deadlock.

Eg.  Thread A should complete it's tasks first, but thread B manages to get started ahead of time due to a programming mistake.  Race Condition.

For deadlocks, we just need ensure that a task only starts when it has all it's resources available, and when it ends it doesn't keep a hold on any resources.

For race conditions.  We do the same; make sure that the order is properly specified.  Rather than specify a list of things to do with convoluted gates keeping everything running in order; we tell the underlying system what the order is as a tree of dependencies.

Grand Central (from my quick reading) helps with the former and a bit with the latter (it uses semaphores).  Operation Queues and Intel Thread Building Blocks focus on the latter (I'm more familiar with this model of operations).

I'd go into details of the specific APIs; but that can be found all over the web - and more coherent than I'd ever manage to write it.  And the APIs are moving targets, the concepts not so much.
</rant>

Rating Software Goods

<rant>
Normally, when rating a piece of software, I think numbers.  How many features?  How fast?  Kitchen sink?  It's starting to dawn on me that this thinking is what leads to abominations that Visual Basic is so well known for - forms with countless features.  Quickly wired up - frais-du-jour!

So my thinking is starting to shift towards: how can we quantify the usability of a user interface?  Looking at the runaway success of the iPhone's UI - there must have a way to assign a metric?

In the physical world, we'd call it the quality of the product.  Something made of cheap parts is expected to die sooner than something made of quality parts designed to last.  It's common sense - in a sense.

How do we build a UI?  Maybe the construction will lead to the quality questions.  Hmm, Windows Forms, drag a few text boxes, connect it to an Access database - and voila - instant abomination!

Wait, a quality UI....  That requires thought.

Recently, my thinking is that a good UI is like a good book.  A good book does not need a manual to read - in and of itself consists of the manual.  Some books are technical in nature demanding a certain background - just like certain software demands more knowledge of their users.

A good book does not confuse the reader by overloading them with information.  Neither does a good UI.

A good book will have information that is easily accessed.  So does a good UI.

A good book will have a consistent writing style.  So will a UI be consistent.

A good book requires a lot of forethought and consideration as to how all the chapters will flow.  A good UI, I'd argue, requires just as much thought.  Blindly throwing text boxes is the equivalent of a rough draft of a book where ideas are present without any links or structure.

For example, a good book will usually try to use a person's intuition into a given matter before burdening the person with the technical aspects.  Therefore, once the technical aspects are presented, the reader just needs to learn terminology as the concept already makes sense.  UIs generally miss the boat in this regard.  And that's a challenge to resolve...

Note:  I'm aware of the click count as a metric in web pages.  But I'm inclined to say that UI design trumps click count.  And good UIs don't require that much effort on the user (the comment is circular on purpose).
</rant>

Rant on Rapid Prototyping of Software

<rant>

I tend to vote for throwaway prototypes.  Something whose initial purpose is to test something, whose design doesn't really matter.  Where the prototype is not intended to become the final product.  My reasoning is that organized code actually distracts from getting the goal done.

Why?  because a prototype is supposed to answer some form of feasibility question.  If the prototype is designed to become the entire system, then something's wrong.  It could, in retrospect, become the final product - but this shouldn't be planned.

Why again?  agility.  If you're testing the stability of  the algorithm of a physical system, do you need to run it in the final application?  Most likely no - you know the performance characteristics of the algorithm and any computational limits that are imposed.  The goal is to write, as quickly as possible, an application to display the results and to set up the system with harsher conditions than what is expected in the final application.

Expanding on this idea - if the code is expected to be used as-is - maybe the programmer might spend extra time organizing the code, making it legible, documenting.  Actually, a prototype just needs code and a person that understands it.  Organization is over-rated - whatever gets the code written the fastest is most important (why use accessor functions when variables can be directly accessed?  why comment if the algorithm will be quickly swapped out?  why worry about aesthetics of the visualization when the goal is to observe stable and correct behaviour?

Again - let's consider a user-interface.  A very touchy subject, as reading a user's mind and knowing what's best for them is actually harder than it seems.  A good user interface does not need a manual as it is intuitive  (that's a comment on the current state of UIs though - if training on a UI is needed - something's wrong in my opinion).  I believe it more to be a hit or miss situation - UI will either be good or bad.  It's like throwing plenty of things at a wall and seeing what sticks.  Now - if we create a prototype designed to evolve into the final product, then there is a layer of organization which implies assumptions.  There is structure.  There is documentation.  Comments.  Plenty of work that has the real potential of actually being trashed rather than seeing the light of day.  It should be done as fast as possible just to ensure that users can test.  It doesn't even need real data - just a realistic progression so that users can judge of the ease of use.

What could change in a UI?  Buttons need to shift around.  Sub-windows?  Lists?  Custom controls?  Special effects?  Each of these could be added and removed at will.  A good UI should have several test versions.

Then - what happens when a prototype has discovered the path to follow?  We pillage what's salvageable and good, as quickly as possible.  We document.  We comment.  We organize.  And tackle the next challenge.

Isn't a small amount of spaghetti code to prove a concept worth it if concepts get validated or disproved quickly as opposed to developing a large framework?

As in quickly - a prototype should not take more than 4 hours.  It should be focused.  If the prototype includes building a functional version of everything - then maybe you aren't building a prototype...

</rant>