Subtly “ASYNC”

Warm-up

The much talked about in recent technology diaspora is async! It came with a flurry and still remains fuzzy to all of us, including me, until I recalibrated by research antenna up towards it. I come from primarily a web development platform and this article talks about async in client and server languages that I have predominantly used. This blog post expounds the theory behind asynchrony in modern languages like C# and JavaScript framework like Nodejs.

Short Sprint

Historically we have always dealt with predictable sequence of instructions that flows in certain predetermined order with its logical & control structures in place. Async is disrupting this. How? When single thread is assigned for the completion of a software program then it is synchronous operation. This way the thread in context is quasi utilised (or most of the times it’s just waiting for an I/O operation to complete). This is not the economical way of exploiting the precious thread execution time.

Figure 1 : Synchronous Operation

Figure 2: Asynchronous Operation

The downside of the above execution approach is the thread which performs execution of the three tasks (refer Figure 1) in certain order has to wait for the I/O operations and walk through a sequence in spite of lag or lull. On the other hand if one thread performs concurrently all the above three instruction (task) sets by efficient context switching like in the above figure (2), then its asynchronous operation.

Finish Line

There are multitudes of technologies out there and there is no unique tool which is sharp enough to solve all the real world problems out there. Likewise asynchronous techniques are suited to chop the thread execution time and switch between tasks when there is a lull due to I/O lag. This is suited for web related problems but not for high intensive processor heavy lifting tasks. And that’s where precisely my previous blog post kicks in <>.

Joy of Parallelism: Am I a Work Pirate (Stealer)?

Rise of Parallelism:

We are already well ahead of the curve that transformed single processor machines into multi core revolution in hardware. This transformation has not yet fully been exploited by, ordinary to critical applications running on current hardware. Thanks to Microsoft for helping even the masses to unleash the power of parallelism. This post after a long hiatus from my side, comes with a bang about the nuances that drive the parallelism into the fore of technology world. This post talks about the coveted and cool algorithm that takes the multicore machines and turns into a massive cruncher.

The Crux of Parallelism:

The CPU intensive iterative/routine/concurrent tasks(fine grained language instruction sets) need to be treated as chunks (partitioned) that run on various multi core processors simultaneously and thereby after completion, consolidate the results of individual iterations(that run on respective processors) and present it to caller. These are not I/O intensive tasks, but these are processor intensive.

Guts of Work Stealing Algorithm:

That said, work stealing algorithm efficiently deals with optimally assigning and exploiting the power of unused /idle processors and, also balances the overall load amongst the processors. How? Each processor has a special abstract data structure, double ended queue called as deque. This is a structure where one can push and pop on both the ends. There is a private deque assigned to each processor and also global deque common to all the processors.  As when a task is spawned or forked (remember how a task is spawned in UNIX), that task is assigned/pushed to the local deque of the respective processor and it pops from bottom of deque and the processor monitors it by context-switching if there are more than one tasks in its deque. During execution of a single task in a given processor, it can lead to spawning of multiple tasks which are pushed into the local (private) deque. The interesting part here is if the processor happens to run out of tasks to execute or in other words- idle, then that processor in context can steal tasks from other processor’s deque (private) or global deque, keeping them busy. Now you see why the word stealing is there in its name.    

Conclusion:

Existing popular solutions in multi core parallelism advocates a shared memory concept rather than private memory. The latter part comes with a drawback of data synchronization cost. On the other hand work stealing algorithm which when leveraged in solving the parallel conundrum, helps to optimally use the idle processor without the cost of accessing the public memory share but with private memory fenced deque.

Reference:

[1] Scheduling Parallel Programs by Work Stealing with Private Deque. (Arthur Chargueraud, Umut A. Acar and Mike Rainey).