Saturday, November 06, 2010

Ride the Cloud at Lightning Speed

How can you make your computationally intensive application run like lightning on the cloud? Use Cloud Parallel Processing!


Some computational tasks are so demanding that a single machine cannot process them within a reasonable amount of time. Applications that leverage massive amounts of data from the Web, a social media network or any other large-scale system can easily overwhelm a single machine. Many other examples exist of analytical tasks that operate on large data sets.  

Parallel processing has been automated and widely practiced at the processor level. In order to utilize the cloud efficiently it is necessary to scale out. Scaling out means that multiple nodes share the workload and therefore get things done faster. Parallel processing at the application level is necessary to harness the power of the cloud.

Creating a Scalable and Elastic Application
With the advent of cloud computing a large-scale and virtually unbounded grid of compute nodes becomes a reality. In principle, this makes the cloud an ideal substrate for on-demand high-performance parallel processing. The cloud can adapt elastically when CPU requirements change and spin-up or tear-down nodes accordingly.

In the latest Gartner Hype Cycle for Cloud Computing (July 2010), Cloud Parallel Processing is an entrant of the Cloud technology adoption curve. They note that “as cloud-computing concepts become a reality, the need for some systems to operate in a highly dynamic grid environment will require these techniques to be incorporated into some mainstream programs. [] The application developer can no longer ignore this as a design point for applications.”



Parallel Programming is hard!

This points to the caveat of parallel processing: it is very hard to build scalability and elasticity into general purpose applications. But if you cannot make multiple nodes share the workload then the cloud will not help you get things done faster.

How can you make your computationally intensive application run in parallel on several nodes? A parallel programmer must address these steps:
  •          Partition the workload into smaller items
  •          Map these onto processors or machines
  •          Communicate between these subtasks
  •          Synchronize between subtasks as required

Note that synchronization is a real bugger – because it is anathema to parallelism. Yet it is unavoidable in most applications. 


Shift of Programming Model

Even with the use of toolkits that offer communication and synchronization primitives (such as PMI) parallel programming is a bit like rocket science. Without a shift in programming model parallel programming will stay elusive. Programmers will have to deal with parallelism to some degree at least – they can no longer rely on middleware, databases and operating systems to exploit parallelism.

Chris Haddad mentions the following programming model shifts that happen with the cloud:
  •  Actor Model: Dispatching and scheduling instead of direct invocation Queues and asynchronous interactions
  • RESTful interactions Message passing instead of function calls or shared memory
  • Eventual consistency instead of ACID


Fortunately, parallel programming has been a research topic for some decades already – long before the cloud existed. Demand for high performance computation stemmed from various domains, such as weather prediction, finite element simulation and other data analysis. During my PhD I worked on object-oriented parallel programming using COTS (commercial-off-the-shelf) workstation clusters. These are called distributed memory machines in parallelism jargon. The cloud is nothing else than a distributed memory machine - albeit at a much larger scale. And my work also touched the Actor model that Chris mentioned. 

Watch this space

The principles and models that apply to distributed memory machines would also apply to the cloud (essentially, the cloud is a very large distributed memory machine). In a follow-up series of posts I will look at those topics in more detail and examine how they can be applied to Cloud Parallel Processing. I’ll dig deeper into programming models shifts (such as Actors) and outline some parallel algorithms (such as map reduce, n-body and others of the 13 computational dwarfs). 

16 comments:

herbjorn said...

You said that
"Parallel processing at the application level is necessary to harness the power of the cloud."

I would rather say that it may be necessary. If the kind of scalability you need is to take care of many tasks at the same time then you do not need to worry about parallel programming. If you need to improve performance for one single task, you need parallel processing in your application.

I also wonder if the build it parallelism of certain products could help achieve parallel processing in the application to some extent without doing any parallel programming?

Giovanni Scheepers said...

Within financial risk management parallel computing is a hot topic. Liability portfolio's have to be made 'risk free' by European Legislation (Basel II / Solvency II, etc.). They have to do this so that we consumers will trust them again (sad thing unfortunately is that we as consumers have to pay for this also in our premiums and interest).

To make liability portfolio's risk free, you need to know how and what market risks have influence on the value of the portfolio's and how much capital have to be hold to satisfy the liabilities on the long run.

In these days, value of the liability portfolio's and the amount of capital are stochasticly calculated by using economic scenario's which you can buy for instance at Milliman (and this goes well as long as Mrs Merkel is not making stupid remarks about Greece).

Depending on the size of your liability portfolio, you could spend a whole day or even longer on calculating a 'best estimate'; to find out afterwards that your assumptions were wrong or that your sensitivities were not complete.

Parallel processing can be king in this arena. However, it is not as simple as 'give us your valuation model' and we will run it for you on our grid in the cloud. To effectively make use of the grid, your valuation model needs to be ready for parallelism; in other words, has to be split up in little chunks.

And this is not all. We are talking about very sensitive data. It could do real harm to a financial institute if any data in that grid gets available to the open market.

Financial institutes have to gain knowledge and experience in altering their valuation models. But only if they can trust the parallel cloud.

Thomas Rischbeck said...

@herbjorn: I agree - some tasks can be run in parallel without the need for parallel programming. A good example are JEE application servers. The programmer doesn't deal with concurrency (is banned from doing so in fact) or distribution (at least in theory). Still, the app server will intelligently distribute the sessions for e.g. a Servlet around the available nodes in a cluster.

In this situation, the application server essentially provides a layer of abstraction that shields the JEE programmer from having to deal with mapping, communication & synchronization. The application server, however, must deal with all the messy details of parallelism.

There's a good paper by Skillicorn (http://portal.acm.org/citation.cfm?id=280278) where he defines a spectrum of parallel programming models that reach from explicit (the programmer deal with all the steps mentioned in my article) to implicit (the programming model or runtime system does it under the covers). To my knowledge, fully implicit models have not worked yet despite decades of research. However, there certainly is a lot of promise in "almost-implicit" models.

This is really good input in fact and I think I'll delve more into the Skillicorn classification in one of my next posts.

Cheers mate!

Thomas Rischbeck said...

@giovanni: excellent comments and a good possible real-world case study! thanks a lot for this. Maybe we can expand this into more of a fully-fledged out story? That would be great!

You mention that the Basel II or other regulatory compliance scenarios and computations are quite demanding and long-lasting. A parallel approach could certainly speed things up. You also say that the computation must be "split up into little chunks". That's the partitioning problem that I mention in my article. In my follow-up posts I'm planning to write a little more about how this can be achieved by using different parallel programming models.

You also mention security - which is crucial for the kind of data analysed in financial risk management. Anonymization of person-related data may be one option. Is this a possible solution here? Otherwise all that remains is a good trust relationship with your cloud operator and legal frameworks around this trust. There's some work going on here to address these problems but they do remain a main inhibitor of cloud usage according to my experience.

One issue that remains is how to get the data into the cloud (unless it is already stored in there?). The bandwidth requirements for transferring large data sets may be so high that they offset the time gain from cloud parallel processing!

Thomas Rischbeck said...

Thanks to Giovanni Scheepers for providing another domain, where parallel processing is useful to handle the sheer workload. He notes an example from the financial domain, where parallelism can be used to speed up portfolio risk analysis. SOA in this context stands for "Society of Actuaries".


http://www.soa.org/files/pdf/2010-hk-ifrs-gaap-22.pdf

formaldresses4us said...

Your blog article is very intersting and fanstic,at the same time the blog theme is unique and perfect,great job.To your success.

----------------------------------------------------------
Flower Girl Dresses|Empire Wedding Dresses|New Style Wedding Dresses

iPad POS said...

Thank you for this post. Thats all I are able to say. You most absolutely have built this blog website into something speciel. You clearly know what you are working on, youve insured so many corners.thanks .

Texas attorney Joe Garza said...

The information and the aspect were just wonderful. I think that your viewpoint is deep, it’s just well thought out and truly incredible to see someone who knows how to put these thoughts so well.

automaty do gier said...

I can understand your writting. It make me know more about this iterm.

Web Design Manchester said...

Thanks for giving us opportunity to post in your blog. This gonna be fun lots of people will comment and provides information that make this page so interesting. Thanks for giving us opportunity to post in your blog.

SEO Liverpool said...

Wonderful article. It is useful for me, thanks a lot for giving everyone an exceptionally splendid possiblity to read in detail from this blog. I really enjoy reading in your blog!

Anonymous said...

Thank you for another important article. Where else can you get this information in a comprehensive way of writing? It took me a week, and I am looking for information. Buy Facebook Fans

Anonymous said...

This topic has always fascinated me. Thank you for writing an article that has great content and is well written. Well I am inspired by your writing style.Social Media Marketing Manchester

paul sam said...

Strive not to be a success, but rather to be of value.
Timber Merchants Manchester

Anonymous said...

Thanks so much with this fantastic new web site. I’m very fired up to show it to anyone. It makes me so satisfied your vast understanding and wisdom have a new channel for trying into the world. White Label SEO

mical clark said...

Flaming enthusiasm, backed up by horse sense and persistence, is the quality that most frequently makes for success.
Security Roller Shutters