Archive for December, 2009

HW and SW: the uneasy couple

Monday, December 14th, 2009

Yesterday I had a presentation at the 2009 New Directions in Computer Architecture (NDCA 2009) workshop, co-located with the MICRO conference. I’ll come back on the subjects of the workshop in a separate post, as here I would like to focus on an issue that was bugging me for a while and became all too apparent in the discussion around my talk.

So what was the talk about? I was advocating the need for more stronger coupling between HW and SW in terms of detailed semantic information passed on to the HW by the SW so that the HW can decide on how to best execute the SW. As one conrete way of doing this, we proposed the use of contracts (constraints describing relationships between data, control flow probabilities, side effects etc) as instruments to communicate semantic information and help the accuracy of speculative execution. The benefit of this is that sequential software can actually gain from multi-core hardware without the need of rewriting it. The paper was co-authored with professor Per Stenström from Chalmers.

Some of the reactions were, unfortunately, the ones I expected. ‘We did lots of HW-driven analysis of software, it doesn’t work’; ‘you are waisting transistors’ and my favorite one: ‘do you really believe programmers can tell the hardware more than the HW can detect?’. Make no mistakes – these comments were not coming from some rookies, but from seasoned HW architecture researchers.

To me, this underlines the problem I have been seeing over and over: computer (HW) architects seem to believe that they can solve all the computing problems on their own and provide tools and chips to SW guys that will just work brilliantly. In case it doesn’t, it’s likely the fault of the later ones, as they can’t really appreciate the beauty and power of the solution (multi-core, anyone?)

To be fair, we, the software community, have our own share of the fault. We took HW speedup for granted, without us having to do anything – after all, this is what the computer architects promised us and delivered on for decades. The name of the game has changed however – with real parallelism in HW, the partners in this marriage have to start talking to each other and the software side seems to be the first to wake up to this new reality. HW architects, unfortunately, still seem to believe that they can solve all the issues on their own – but if the past three-four years teach us anything, then it’s this one: the only way to continue the march of ever better performance is to strengthen the semantic coupling between SW and HW. There’s no way around it.

In this context, contracts driven speculative execution is just one (promising) idea. Or gesture, if you wish 😉 .

Pont, pont, vesszöcske…

Tuesday, December 8th, 2009

Üni nagyon megkedvelte a török basa rajzolást, söt már maga is próbálkozik. Vajda Ünige Anna az alkotás hevében:

A végeredmény:

Üni basái

Üni basái

My ancestors’ great journey

Monday, December 7th, 2009

For my last birthday I asked for as present – and received 🙂 – a genetic testing kit sold as part of the Genographic Project, a research project of National Geographic and IBM. Finally, the results were posted over the last weekend – so here’s the story of my ancestors.

I chose to have the Y-chromosome test, which would indicate my father lineage. Before going to the results, here’s a short intro to how testing is done and what the concepts of haplogroups and markers really mean. Quote from my report:

Each of us carries DNA that is a combination of genes passed from both our mother and father, giving us traits that range from eye color and height to athleticism and disease susceptibility. One exception is the Y chromosome, which is passed directly from father to son, unchanged, from generation to generation.

Unchanged, that is unless a mutation—a random, naturally occurring, usually harmless change—occurs. The mutation, known as a marker, acts as a beacon; it can be mapped through generations because it will be passed down from the man in whom it occurred to his sons, their sons, and every male in his family for thousands of years.

In some instances there may be more than one mutational event that defines a particular branch on the tree. This means that any of these markers can be used to determine your particular haplogroup, since every individual who has one of these markers also has the others.

When geneticists identify such a marker, they try to figure out when it first occurred, and in which geographic region of the world. Each marker is essentially the beginning of a new lineage on the family tree of the human race. Tracking the lineages provides a picture of how small tribes of modern humans in Africa tens of thousands of years ago diversified and spread to populate the world.

A haplogroup is defined by a series of markers that are shared by other men who carry the same random mutations. The markers trace the path your ancestors took as they moved out of Africa.

My haplogroup is R1b and it includes the markers M168, M89, M9, M45, M207, 173, M343 – in case you want to know the scientific version 😉 . The narrated one goes like this:

My earlieast identifiable forefather lived  roughly 50000 years ago in Eastern Africa – and he is the common ancestor of all non-African man living today. At about 45000 years ago, one of his grand-grand-…-sons moved to Middle East as part of the second exodus out of Africa and some of his descendants continued to Iran and Central Asia. 90-95% of all non-Africans are his descendants.

The next significant event happened about 40000 years ago when one of my forefathers, living in Iran or southern Central Asia spawned a lineage that over the next 30000 years populated much of the planet (except Africa and Australia).  Two clans formed in Tajikistan: some moved into Central Asia, some moved to Pakistan and the Indian subcontinent. My next forefather travelled with the first group and one of his descendants – about 35000 years ago – is at the origins of most Europeans and nearly all Native American men.

At about 30000 years ago, there was another split in the family, with one sub-clan turning south and making it all the way to India, while the other turning towards Europe – my direct forefather being one of them. They became the first Homo Sapiens to reach Europe, giving rise to the Aurignacian culture. Cooling climate forced my ancestors to move south – so 90% of all men in Spain belong to the same large family; the last big identifiable turn of genetic fortune happened at about this time, giving rise to my last known genetic forefather – the ancestor of those who formed the Cro-Magnon group during the last ice age and created the famous cave paintings, including the ones in the Altamira cave.

This is where my genetic story ends. It makes me proud knowing that I’m the direct descendants of the first colonizers of Europe – but it also tells me that, at least on the father line, I cannot be a ‘biological’ Hungarian: my male ancestors have lived in Europe since they first arrived here, 30000 years ago, most probably in Southern Europe – and did not arrive 1100 years ago with the rest of the Hungarians.

Which makes the prospect of checking my mother’s linage all the more interesting 😉 .

A brief history of writing software

Sunday, December 6th, 2009

Recently there was a long Ericsson-internal mail discussion thread around the statements made at a panel of Microsoft engineers. There were many interesting posts by colleagues near and far, but here’s my contribution – of course, in line with my beliefs expressed earlier on this blog 😉 .

“There has always been two dimensions to software development: one was the platform (HW and OS) dimension and the other was the problem domain dimension. For most of the past 50 years, software development focused almost exclusively on the first one, creating languages that allowed description of programs in a way that was easily translated to Neumann types of (sequential) machines. The problem domain, whatever it was, had to be squeezed into this paradigm.

During the 80s it became painfully clear that this approach is a big bottleneck, so we started tinkering with the high level assembler languages that we had (C, Fortran, Pascal, ADA etc) and invented stuff that was moving towards more genericity and somewhat higher level of abstraction (object oriented paradigm), while moving some of the obvious tasks to the tool/run-time system domain (such as memory management). The underlying assumption remained though the same: we must follow the platform – any attempt to raise abstraction level in general led to inefficiency when deployed on HW. Some argued that ‘well, this is the price you pay’.

Still, while this fixed some of the issues around actually writing code, the rift between domain knowledge and platform knowledge remained wide open – so we invented UML, agile etc. These, again, masked some of the discrepancies but didn’t fix the real problem – we took steps forward, but still not enough. We always hit the same wall: generic, high level of abstraction meant inefficient code and we still had the communication issue between domain and platform experts. Graphics were just aiding understanding – shortening getting up to speed times – but weren’t really giving the order of magnitude boost we all hoped for.

The key insight of the past few years was that while generic, high abstraction level, Neumann-paradigm focused design leads to inefficiency in deployed code and does not really bridge the gap between domain expertise and programming expertise, there may be a middle way that could re-concile these tensions: what you cannot solve in generic terms, becomes much simpler if you narrow the domain down so that the range of choices are greatly reduced; hence the proposal goes like this: focus on a specific, limited, well-defined domain (for example, DSP programming, communication stack development etc), create a language/modeling environment/infrastructure that allows domain experts to express what the software shall do (not how) and then focus on making the transformation within this limited, well-defined domain to Neumann architectures automatic. The key is being restricted: efficient automatic transformations become possible and the result is an eco-system where you design in the domain level (what, not how, possible by even domain experts) and then can generate efficient target code through specific, limited, targetted transformations (created by platform experts).

Cheers, Andras”

Reflections after MCC

Thursday, December 3rd, 2009

Last week I attended the Swedish Multicore Workshop in Uppsala, now in its second edition. It was a strangely good feeling being there and watching a “baby” growing to a significant event with 100+ attendees, after serving as its babysitter (read: program committee member) during the past two years.

I also had the honour of giving a key-note talk on our company’s views on the challenge of multicore. I built my whole presentation around two ideas: that economics are inevitably kicking in and slowing down the march of Moore’s law (see this post for more details) and the need for efficiency, portability and processing capabilities well beyond Moore’s law – all at the same time.

This, obviously, is an impossible challenge or at least a challenge that cannot be solved by step-wise improvements. This was, of course, the core of the message: the industry needs radical thinking from researchers, we need new ways to construct and execute software, at a scale that dwarfs anything we do today. Mobile broadband is set to explode worldwide and the computational challenge it’s posing is probably beyond the challenge Google or any other Web 2.0 companies are facing. Based on the feedback afterwards, our research colleagues seem to have got the point. Actually delivering the needed solutions is another thing…

All in all, it was a succesful event and I left impressed with the progress the UPMARC researchers are making.

The birth of Feldspar

Thursday, December 3rd, 2009

As I hinted in a previous post, Ericsson was working, together with Chalmers University (in Gothenburg) and ELTE University (in Budapest) on the development of a new language targeting DSP software development. After some brainstorming, the language was baptized Feldspar (Functional Embedded Language for DSP and PARallelism) and it’s available under open source license from sourceforge.

It is essentially a vector processing language with built-in mechanisms for parallelism that we plan to exploit even further in coming releases. Architecture-wise, it consists of a high level library that is mapped internally to a parallel C-like language, suitable for compilation to real targets. There are two key characteristics that are worth mentioning and I’ll elaborate a bit on those.

First is the C-like nature of the intermediate language that allows usage of well-known compilation techniques for getting efficient code out – but without the hassle of pointers, complex expressions etc. The existence of the intermediate language allows a fallback solution as well: if the high level constructs are not sufficient, the programmer can directly use the intermediate language. We still need to work on preserving e.g. variable and function names, but that shall be possible to fix.

Secondly, it’s a parallel language which opens up the possibility for greatly simplified automatic parallelization – for MACs within a core and for multiple cores. The first part is there and we are continuously working on improving it (whoever programmed DSPs will recognize the value of this); parallelism between cores is yet to be implemented.

The open-source version of Feldspar is not the end of a journey, but rather the first pit stop. We have ambitious plans for 2010, after seeing the huge potential of such languages. Stay tuned for new releases, but until then, make sure to download it, try it and let us know what you think.