About us and parallel programing

(this post reflects my ideas and my ideas alone – it may or may not be the same as those of my employer)

Sure enough, the net is full with arguments around net neutrality, on the wake of the leaked Google-Verizon talks and the subsequent officially released proposal that would treat mobile broadband (and some other future services) differently from traditional fixed internet access. Some went on a crusade on behalf of net neutrality; some defended the Google/Verizon proposal, but, for sure, everyone has an opinion. So do I .

The bottom line is that mobile access is different. While you can just lay more and more cables at relatively low cost, the frequency band usable for wireless access is limited by the laws of physics. There are just a limited amount of bits that can be transported over the air in a certain location – thus, radio resources differ from fixed access (cables) in that they are really a scarce resource. Sure enough, you can increase throughput to some extent by increasing the density of cells (base-stations), but this obviously requires both capital investment and generates operational costs. Even then, physics will eventually kick in.

Thus, someone has to pay for bandwidth over the air – it’s just the basics of economics when it comes to the access to scarce resources: (un)availability of supply and demand is driving the prices. In this case, there are four parties that may pay the bill: the mobile operator, content providers, the content consumer (end-user) and the government. The operator has little incentive to do any investment beyond gaining more (paying) customers – and the market is quickly reaching 100%+ penetration in developed countries (and some developing ones as well). That leaves the other three: content consumers, content providers and the government.

In their momentary lapse of reason, mobile operators decided to offer flat-rate mobile broadband to their customers – something that they surely regret by now. The hard fact is that this will be hard to change – and even charging for traffic that exceeds a certain limit will not mitigate the cost of providing good quality service (read: dense networks): most of the users will stay below the limit and the few heavy users are ‘good enough’ at consuming the scarce resource when it’s most needed. The result: low quality network, customer complaints – just look at the reputation of AT&T in the US  as a consequence of the popularity of the iPhone.

The government may be part of the solution: by enshrining the right to net access at a certain level (say, X MBits/s) and subsidizing network buildout that can guarantee such level of service. Such an approach would guarantee equal basic access, while not hindering innovation and further improvements: on top of requiring a minimal service, it shall give the freedom to content providers, consumers and mobile operators to negotiate commercial agreements on who gets access – and for what extra fee – to the additional bandwidth that may be built out – and sold – by the operator. It’s a bit like social security versus getting rich: everyone is eligible to a minimum standard of living, but beyond that he or she is free to get rich, according to his or her capabilities.

Sure enough, such a framework has a number of tricky issues (such as how to decide how much it really cost to build the minimum level of service and how much of the operator investment goes beyond that). But it’s my strong belief that such a public-private partnership and the combination of regulatory guarantees and requirements of certain level of service coupled with industry-driven differentiation of the access to a scarce resource is the way forward. No, not everyone will be a bit-millionaire – but everyone will have enough bits to feel OK and those with more demand will earn more.

Just as in our society otherwise. It’s the worst solution – except all other possible solutions.

Recently IEEE Spectrum published an article by professor David Patterson of Berkeley, titled The trouble with Multicore. In it, he makes an analysis of the state of the art of parallel computing research and the things we have tried (and failed: specific languages, ‘properly designed’ hardware, automatic parallelization); finally, he offers three visions for 2020: stop of performance increase; success for multicore processors in just a few areas; full-blown success where any application can benefit from a large number of cores. Patterson admits that he considers the latest scenario unlikely.

I have a great respect for David Patterson’s achievements (the RISC architecture, the RAID concept etc) and I feel privileged for having met him a couple of years back. However, I feel that, along with much of the community, his line of reasoning is somehow too narrowly placed within the limits of traditional wisdom: their focus is still on functional or data level parallelization, where, I must agree, it’s likely that we will fail to find an overall solution. However, there’s another direction worth exploring that I strongly believe can eventually lead us to a breakthrough that will keep the IT industry on the same track we got accustomed with the past 30 years.

So, let me give my modest prediction for year 2020.

As Moore’s law will likely continue, it’s fair to assume that for some time to come (at least down to 5nm – due by about 2020 -  leading industry experts claim) we will be able to cram more and more transistors (and memory) into one chip. True, instead of more powerful cores, we will design systems with more, but simpler cores – chips with lots (gigabytes) of on-chip memory and thousands to tens of thousands of cores surely look feasible in 10 years time. In fact, we will see a  sea of computing resources crammed together on one silicon – a sea, where a drop (one core) will have very little significance on its own. Such chips are certainly possible within today’s power budget (see also my related post on low power servers).

So how can software benefit?

I think we need to give up on our ideas of automatic parallelization as well as the pervasive quest for scalable algorithms, at least for the so called embarrasingly sequential applications. Instead – as I briefly described earlier - let’s focus on strengthening the semantic knowledge the hardware will have about what (not how) the software wants to achieve; use this information to intelligently perform run-ahead calculations on behalf of a sequential program. Granted, no amount of cores would suffice to completely explore the execution space of a reasonably sized software, but if we can limit the scope of exploration by telling the hardware which are the potential branches, one can make good use of the sea of computational resources to make an application run faster – by simply pre-executing all the likely branches (narrowed down by the extra semantic information made available to the hardware). In this approach, the more cores you have, the better the chances of success and thus the speedup- hence, the sea of computing resources will make perfect sense.

One could consider such an approach a waste of energy: many of the cores will perform work that is discarded, thus waste energy. This argument is flawed, due to the same reasons for which natural selection is not a waste from life’s evolution point of view: any failure branch actually helps the eventual winner to succeed; thus, you may think of it as part of the same bigger entity that works succesfully on the problem. If you get a certain speed (or throughput) for one unit of energy, but perhaps double the performance for eight time the energy – is that worth it? For many applications, where continuous performace improvement is a must the answer is a clear yes.

So, here’s my vision for 2020: chips with a sea of computing entities and matching memory; software that can provide by orders of magnitude more semantic information to the hardware than today; run-ahead exploration of execution space by the sea of computing entities using the semantic information provided by the software.

As a closing remark, I can only agree with David Patterson: “No matter how the ball bounces, it’s going to be fun to watch, at least for the fans. The next decade is going to be interesting.” Couldn’t disagree with that .

I’ve  just returned from a few weeks of vacation so I guess it’s time to start blogging again

There were two pieces of news over July that I would like to highlight here: the announcement by Amazon that they will start providing Cluster Compute Instances, targetting high-performance computing and the release of the Scope Alliance newsletter, with further details on the cloud computing workshop (and a small interview with me ).

What makes the Amazon announcement of particular interest is the following feature (quoute from their press release): “customers can also group Cluster Compute Instances into clusters allowing applications to get the low-latency network performance required for tightly coupled, node-to-node communication”. It is exactly the issue we’ve been highlighting recently: networking (besides security) is the ultimate roadblock for cloud computing uptake and it’s an impediment that makes the promise of completely opaque computing infrastructure hard to fulfill. It’s good to see that Amazon came to the same conclusion and chose essentially the same, constraint based approach that I also advocated as the most promising approach.

Regarding the Scope Alliance newsletter, I wanted to highlight here since it gives a bit more insight into what was presented at their cloud computing in telecom workshop (the full material is under non-disclosure agreement and available to members only, hence I can’t share it here). Again, the cost of networking, security and management of quality of service through service level agreements and automatic enforcement of these were the main topics I’ve highlighted.

Stay tuned, I’ll return to some of these issues during the autumn. Till then, enjoy the summer .

Recently there was an announcement by the U.S. Department of Energy regarding some of their results on using cloud computing for scientific computations. Unsurprisingly, it concludes that cloud computing fails to live up to the promise for applications that heavily rely on MPI (Message Passing Interface), while it performs well for serial computations (computations done on the same machine). It underlies one of the fundamental challenges of cloud computing, again: communication bottlenecks.

In a presentation to the SCOPE Alliance (that was very well received by the attendees) I emphasized exactly this point: in order to make cloud computing usable more widely and for applications with more stringent quality of service requirements, one has to focus on a few issues, of which communications management and security clearly stand out. There’s a deeper issue that needs to be addressed and goes somewhat against the promise of uniform, unlimited computing: in order to optimize communication, structure of the cloud needs to be exposed and locality managed.  It’s a major challenge that has been identified by several research groups and industry analysts; I will quote just one of them, BitCurrent:  ”one dirty secret of cloud computing is that from a cost perspective, everything is pretty much free compared to the price of moving data around“

I wrote a while ago about the benefits of space-shared operating systems in comparison with today’s SMP-based operating systems. One of the issues I raised relates to the intrusive nature of the OS in the sense that it usually destroys the cache content – either when it is explicitly invoked or when it decides to reschedule applications.

Yesterday, at WIOSCA (Workshop on Interaction between Operating Systems and Computer Architecture) there was an interesting paper that addressed the first issue. The proposal is basically to move the execution of some (long to execute) OS services to another core – pending certain conditions – a technique the researchers called ‘OS offloading’. The idea is really interesting and it comes amazingly close to the idea of space-shared operating systems (minus the scheduling issues, still unresolved). The results – unsurprisingly – have shown good performance improvement and it was good to see that current OSes can be tweaked relatively easily to become less intrusive.

Another interesting paper – this time at the PESPMA (Parallel Execution of Sequential Programs) workshop – has finally shown a realistic use-case for transactional memory: the guys (actually, gal )at the Barcelona Supercomputing Center have used transactional memory techniques to perform double execution of critical software and detect possible radiation related faults, essential in e.g. aviation systems. I’ve been a long-time critic of transactional memory, but this research caught me by surprise: there may, eventually, be some use for this idea (albeit from an unexpected corner – something that’s not so un-common for new technologies).

Stay tuned, I will return to some interesting topics up for discussion at ISCA and associated workshops.

Yes, it has finally arrived: SeaMicro, a startup in stealth mode until yesterday, announced their low power, low cost server rack in a press release posted on their site. It’s based on Intel Atom chips, which makes it ISA-compatible with current software – yet, they still claim 4x reduction in power consumption, 4x reduction in footprint, while delivering the same performance as current server configurations.

I’ve been advocating and predicting the advancement of low-power chips ever since my revelation at last year’s SOSP. With the iPad, they entered the domain of netbooks/laptops; with today’s announcement, the server domain seems to be the next target. To be sure, there are still mountains to climb until such technology may become mainstream and for some workloads, that will never happen (just take a look at James Hamilton’s blog, one of AWS’s VPs) – but the previously “impossible challenge” has just tipped its toe into the sea of possibilities.

SeaMicro is not the only company working in this domain. There are several other companies that focus on ARM’s Cortex A9 core for building server chips, which promise a further factor of 4-5x improvement in power usage, at about the same device density. These systems will be built, sooner or later, by current or emerging companies – but the problems lie elsewhere: what kind of workloads can you put on these systems? How do you manage data centers with tens of thousands of cores – an order of magnitude more than today?

It’s interesting to note the parallel between low power servers, many-core chips and cloud computing. Both share the basic issue of large scale, sporting large numbers of cores that are co-operating on a specific problem. This scale is larger by at least one order of magnitude compared to today and magnifies many of the problems: the resource sharing bottleneck, partitioning etc. We really need programming models that can make use of massive parallelism without a lot of overhead – and that’s the challenge of the day we really need to focus on.

Yesterday, while browsing through the news of the new iPhone and its comparision with the latest Android-based stuff, an idea started bugging me: there’s an interesting parallel between how Google and Apple do business and how societies in different parts of the world are organized.

In many ways, Google is the technology company version of what is usually called the ‘American way’: gang-ho approach, openness, diversity, do it yourself etc. Android is an open source OS; companies building phones based on Android are in a cut-throat competition; there are dozens and dozens of products – all produced under the benevolent, not-so-controlling eyes of ‘government’ (read: Google).

Enter Apple. iWhatever (minus the Macs) + iTunes is a walled garden: you pay a premium and you get a controlled, in many ways limited but safe and uniform treatment. The stuff is nice, well organized and it works. Sense the analogy? To me, Apple is similar to many European countries with their social market economies, high taxes, government-provided (in many cases, from a monopoly position) services. Everyone has a basic safety net, but in many respects, the choices (like social security, pensions etc) are limited.

I’m not arguing for or against any of these models here – both have their benefits and drawbacks and it’s notoriously difficult to strike a balance. It’s two different ways to look at business (and society) and only time will tell which – or a third one? or both? – will prevail.

As I hinted at it in a previous post, I’m working – together with two co-authors – on a book on programming many-core chips. It was commissioned by Springer, the world’s best known publisher of scientific work. It’s due to be delivered as manuscript by end of Q3 2010 (remains to be seen how good we are at keeping dead-lines ). As it’s implied by the subject, we focus on the programming of massively multi-core processors, with tens-to-hundreds of cores.

No matter what will happen, it is  a great learning journey. When you have to write down stuff that many people will read and comment, you really have to be 100% sure of what you are doing, what you include and what you leave out. I spent a considerable amount of time on the chapters dealing with state-of-the-art multi-core operating systems as well as future many-core operating systems and all the fact gathering, sorting, distilling process brought me to a deeper understanding of where the issues with OSes really are; why OS will become layered, why OSes and hypervisors are bound to overlap and eventually merge, how memory management and processor scheduling are becoming almost equivalent, what are really the fundamental principles that will allow operating systems to scale up – hopefully indefinitely. Unfortunately, I can’t share parts of the book here, but will return to some of the issues in an edited form.

Another interesting subject that got cleared up for me is the relationship between Amdahl’s law and Gustafson’s law; I urge everyone to read this paper, which explains clearly how the two are actually the expression of the same fundamental law. Researching for the book also allowed me to discover Gunther’s law (or rather, conjecture, see this blog post for analysis), which seems to be backed up by experimental data, but no well-founded theory. It includes Amdahl’s and Gustafsson’s laws as special cases, but it also covers the phenomenon of retrograde scaling.

I hope I made you interested in this book – so stay tuned

Recently, two British newspapers announced their plans to start charging for access to their online content. According to their estimates, over 95% of their current on-line readers were essentially economically useless or worse, in the sense that these generated no ad revenues, while pumping up the traffic towards the sites. Their calculations forecast that they will loose over 90% of their visitors, but revenues from paying customers should surpass current advertisement based revenues.

Whether they will succeed or not, remains to be seen. However, their choice of starting  to charge for on-line content underlines three fundamental issues: information and quality analysis did not become free just because of internet; pure advertisement based models may not always work; it’s getting harder and harder (read: costlier) to cater for an avalanche of visitors, in the absence of a reliable revenue stream.

I’ll skip the first item for now and focus on the second two. Obviously, advertisement based models worked out nicely for some of the companies – like Google – but it has a fundamental, subtle characteristic to it that makes deployment in many contexts tricky. When you visit Google, you are likely searching for something, so Google can offer you sponsored answers that you are likely to choose; if you visit a page to flip through information, the site owner may only know your location – so it’s like searching for a nail in a haystack: the probability of hitting the visitor’s pain point is significantly lower. It’s all about knowing your customer: Google, through the search you are entering, knows much more about you then, say, the web server of a newspaper. In many ways, Apple does the same thing with their new advertising platform than Google: through the walled garden of iTunes and AppStore, they know their customers pretty well and hence can deliver much more targeted ads – increasing the probability of a hit. Remains to be seen, but I believe it will be a successful model.

So, what’s the alternative for the rest? Obviously, to survive, they’ll have to find new revenue streams, they need to charge for content. Apple’s model, again,  has shown how: set the price right, and they will come. Since I bought my iPad, I became the happy subscriber of a service that, for 29,99USD/month delivers, legally, every morning, digitally, the full latest edition of about 10 daily newspapers. If I would have subscribed separately to all of these, I would have easily exceeded 100 or even 200 USD and the delivery would have likely been less reliable (there are newspapers published in the UK, US, Hungary and Romania – I challenge the postal service to deliver all those every morning at 7am for less).  The point is: charge for your content, but at a level that makes it worth it; use the benefits of digital, over the internet delivery for cutting your operational expenses and make up for the lower income / user figure (having more paying users also helps).

Which brings me to the third issue – the cost of running a server and related communication infrastructure. It’s an unchallenged truth that the traffic over the internet is exploding, which is good news for equipment vendors, but bad for service and content providers. Granted, most of this traffic is made up by largely illegal file-sharing, but the rest of it will likely move towards a model of paid content (at reasonable pricing level), coupled with a targeted, ad-supported free service (the Google model). This makes for a more sustainable, more fair and economically viable model, without sacrificing the fundamentals of fair and easy access to information.

As for illegal traffic – there are already signs that ISPs will move to block access for the worst offenders. While I have my doubts about it, I think they have little choice – after all, stealing used to land you in prison with constrained rights, wasn’t it so?