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.