Parallel Objects Never Meet: What to do with all those cores

In the last few years the steady increase of microprocessor clock rates and decrease of power consumption has leveled out, due to physical causes that IC designers haven't been able to overcome. This change in a decades-long trend meant that companies like Intel, whose business model is based on continually increasing the performance of their products by following Moore's Law towards ever smaller individual features, and thus ever larger numbers of transistors on the silicon their chips are made of, have had to find another way to leverage the increased number of transistors to improve performance other than by adding more memory and computing elements that go faster. The strategy that Intel, and other companies trailing it down the Moore's Law curve, has taken is to freeze the speed and functionality of each processor, and then put multiple processors, called "cores" on each chip. The current generation of chips on the market has 4 or 6 cores per chip, with 8 core chips coming soon. Chip designs capable of 64 cores have been demonstrated in the lab.

Of course, it's not that simple to take advantage of those extra cores with existing software. Parallel processing was a very active field of research in the 1980's, but the conclusions about that research were that new programming languages would need to be needed, and all new software would have to be written, with the programmers having to control the parallelism of their code explicitly. Moreover, most research was in specialized application domains like numeric programming, and computer vision, where the required parallelism fell easily out of the problem descriptions. But most computing from the 90's on was business or personal computing, not scientific, so the chip manufacturers didn't see parallel computer architectures as an important part of their market. Parallel processing fell out of vogue even in research, and very little money was available for research and development in the commercial sector of the computer industry.

The rise of the web application and the development of large scale application servers provided one way to use parallelism for business and personal computers: since any given server is doing pretty much the same thing, only with different data, for each web client it serves, it's not hard to build server software that can take advantage of large numbers of processors. Server computers have been built with multiple processors for more than 10 years now; using multiple-core chips isn't difficult.

But that doesn't help the large number of personal and business desktop and laptop (and soon palmtop) computers. Utilizing 2 cores isn't too hard, and 4 cores can be kept somewhat busy, but after that it's not clear that there's a lot of benefit to more cores without completely rewriting the software, a monumental and very costly task for most computer applications. It's not surprising then that a lot of research and money is going into looking for ways to reduce the amount of rewriting necessary. Some of the ideas being investigated include extensions to existing programming languages to allow explicit control of parallelism and runtime support libraries that do the work of synchronizing and controlling code running on multiple processors.

I think there's another way to do the job, one that may even allow many existing programs to be just be recompiled, and will almost certainly allow tools to examine and modify or flag code that needs to be changed to take advantage of multiple core. It's based on the fundamental nature of object-oriented programming, in which an object is an encapsulated piece of computation, including code and data.

When I first learned about objects, they were described to me as conceptually little computers, with inputs and outputs. Each object could be, at least in theory, be run on a separate computer, as long as their internal states were not accessible to other objects. In some of the first object-oriented languages this was the basic model of computation; there was no way for one object to access another object's data, the only thing an object could do was send a message to another object and receive a reply. That model works very nicely in a parallel environment because the message-sending mechanism can have synchronization between processors or even distributed computers built into it.

In fact, there are several object-oriented environments that allow a message to be passed to a local object on the same computer as the sender, or to an object on another computer, depending on where the destination object is running. It's even possible for an object to move between computers and have its messages follow it correctly, without any change in the program that the sender or receiver are running. Smalltalk, for instance, does not allow one object to access another's data, only message passing is allowed between objects, so implementing such a system is relatively easy. Java does allow an object of a given class to access the data in an object of that same class, so it's not as easy. The difference between the two languages is that in Smalltalk any object of any class can be moved around, whereas in Java an interface has to be designed for the destination class, and the sending object has to use a reference of that interface type as the destination object; an arbitrary class cannot be used. And, of course, non-object-oriented languages need not apply.

Unfortunately this style of program design is not common even among object programmers. Most OO languages don't have any way to prevent an object of a given class from accessing the data of another object of that class, and many programmers have fallen into the habit of using this feature on the assumption that direct data access is faster than messaging in the local case. In fact, most programmers never think of the remote case unless their program requirements include it. So most OO programs have inter-object data accesses, and often global data (such as class variables) that would have to be modified into message sends or replicated and synchronized data.

With some languages this may not be a great problem: the semantics of the language allow a smart compiler or runtime support system to recognize the data accesses and convert them into message sends. Global data accesses can be converted into message sends to class objects. This allows objects to communicate even if there is no shared memory area for global data. Smalltalk would require a minor modification to the compiler to handle class variable accesses. Java would require a new compiler to detect and modify data accesses. Both languages could benefit from compiler and runtime support to detect object dependencies and optimize the placement of objects in memory spaces and the grouping of obejcts in threads or processes. Python might require some constraints on use, as it has some non-object functionality in it (the module namespace might cause some trouble, for instance), but a suitably jiggered compiler might be able to catch the problems, and perhaps even fix them. CLOS (Common Lisp Object System) would be a good language to try; I suspect that some features of the base Lisp would have to be constrained (macros, for instance).

The more impure object languages like C++ are problematic; the more ways there are to code without or in spite of objects, the harder it will be to find all the dependencies that would break correct parallelism, and the more the culture of the languages users is likely to cause them to reject the idea. That's fine with me because I'm not a fan of those languages (because of having been a C++ programmer for years, and a member of the C++ language standard committee). All the arguments I've heard for low-level languages have left me cold: I don't believe that the language I use has to look like the inside of a crippled von Neumann machine because I don't see any advantage to that. Making it difficult to do things in a natural way because that's "good programming discipline" is just silly¹. And the efficiency and performance arguments are based on not understanding the alternatives; a good Lisp compiler can give a C program a run for its money any day.

I'm curious to see if there are software developers, programming language and compiler experts, or parallel system gurus out there who can tell me why this scheme won't work, or why it's obviously less practical than any other scheme for making use of multiple cores for existing software applications, not system software.

1. To me, programming languages are user interfaces to computer capabilities. Making a bad interface deliberately is downright perverse in my view, not matter what the justification. Instead of forcing the programmer to bend to some model of the computer, why not spend time and energy finding ways of optimizing programs written in user-friendly languages?

Of Languages and Wheels

I want to take a brief detour in my journey in the land of software rants. This rant would have gone deeper into the notions of reflection and introspection and how they affect the ways in which systems can be extended, topics I raised last time in talking about the relations between data and metadata. I'll get to that, trust me, it's one of my favorite parts of computer science, but for now I want talk about the Tower of Babel and the Great Wheel of Reincarnation. These are old ideas in the computer world, but I'm beginning to think that a lot of practitioners haven't heard about them, or don't understand that they're getting caught by them.

The Tower of Babel arises wherever implementors have to use multiple programming languages and/or multiple programming paradigms in a single application. Now, that's not necessarily a bad thing; sometimes it takes more than the functionality you can find in just one tool to do the job. But to see how this can be a problem, look at the goulash that webapplications are often made of. For an example, I'm working on an application now, a manufacturing system that serves up assembly instructions, keeps track of the work flow at each station, and provides instructional content creation functions. It's not very complex now, though in later phases of development more functions will be added. In order to serve up dynamically created pages of content on a web page, in even this simple an application the following progranming languages were used:

• Java was the programming language for the model objects that represent the basic functionality of the application: assembly procedures, the steps of a procedure, the parts and the tools used in the assembly. It's also used for the business logic managers that manipulate the model, and the http request actions that control the generation of the pages*.
• An Object-Relation Mapping system called Hibernate is used to persist the model objects in the tables of a relational database; Hibernate is a Java class library that maps Java method calls to SQL Database queries. It is configured to define the persistent objects and the relational tables using a mixture of Java annotations on the model class source files and xml configuration files.
• The mapping of input HTTP requests to page display and navigation are controlled by a combination of different annotations and yet more xml files, part of another framework called Webwork.
• What is displayed on a page is programmed using Java Server Pages, a framework that allows to combine html, tag markup in several different tag dialects, fragments of Java code, and an expression evaluation language called OGNL.
• After the page display HTML is generated it is modified by Freemarker expressions and Sitemesh decorators which each affect some set of pages with common transformations.
  
• And some of the interaction on the pages is programmed in the html and tags of the JSP, while some is programmed to run on the client webbrowser using JavaScript and an interaction paradigm called AJAX.
• The whole application is integrated using a Java framework called Spring that is responsible for creating and initializing the objects used by all the other pieces, which again requires annotations and xml files for configuration.
  

To implement this application requires half a dozen different technologies and languages; it was originally built by 2 people, and is currently maintained and enhanced by 1 person, who has to use all those tools and be constantly watching for the problems that arise because of incompatibilities among them (and, believe me, they arise).

I haven't even mentioned the apache webserver and tomcat application server that have to be configured for the application, and if I were to describe, even at the highest possible level, what each of these pieces I have mentioned does, I'd be writing a book, not a blog entry.

Just as in the story of the Tower of Babel, the challenge is for all the parts to be able to communicate well enough that the whole can function, and the problem for a software developer is the same as for the general contractor on the Tower: get everybody to work together so that each worker's output is what the next worker needs as input, even when none of them understand each other directly.

The Tower of Babel, despite ita name, is actually more horizontal than vertical, if you think of layers of software in the usual manner as divided from each other vertically. There are several layers in the system I described above, but the various languages and technologies aren't necessarily confined to single layers. The second problem I want to talk about is more a vertical one, involving multiple, often many, layers.

The Wheel of Reincarnation sounds like something from Buddhist theology, but in this case it refers to an insight by Ivan Sutherland into what designers often do wrong in trying to optimize layered systems.

For this rant, the key point of Sutherland's discovery is this:

The pit fall of reincarnation of function is still with us. Sometimes the layers are inhomogeneous which leads to conceptual costs, namely it is too hard to understand the layered systems. Sometimes the inhomogeneities linger in legacy architectures long after their original justifications are forgotten.

In other words, be careful how you layer things, because the layers may become permanently buried under yet more layers. And sometimes the functionality of a layer or layers has to be undone or redone by layers above, because it doesn't quite match the requirements of the upper layer.

In fact, the Wheel of Reincarnation is the explicit policy of some computer technology developers. Intel, for instance, calls it the "Silicon Treadmill": first you write software to perform a task on the current generation of processors, then you identify key parts of the code which can be optimized by putting specialized functionality (asy, by writing microcode) into the processor, then you design a special chip to implement the functionality completely in silicon. An example is the logical layer of the ethernet protocol. At first, it was implemented completely in software, then general purpose processors were modified with extra on-chip memory for buffers, and finally a specialized chip was designed to do the entire logic layer functionality.

Now take the Tower of Babel and build layers on the Wheel using it. Do that iteratively for a few turns of the Wheel, and try to figure out what you've got. Finding out will involve using techniques very like the ones that archaeologists use to investigate the various cultures that have used a midden over time: carefully peeling away a layer at a time and examining how all the parts you find fit together. But even if you figure out how it works, you can't change it and make it work differently, or fix a bug in it. And that's why knowing about the Tower and the Wheel might make a designer think twice about decisions that could cause someone great distress in years to come.

---

* If you're familiar with the Model-View-Controller architecture for interactive applications; the model objects are the Model aspect and the actions are the Controller aspect (along with some JavaScript on the pages). The View aspect is comprised of the Java Server Pages, containing JSP tags, Webwork tags, OGNL expressions, Freemarker markup, and Sitemesh decorators.

More Reflections On Software

A few days ago abi sutherland blogged about how artists and software designers are not in control of the outcome of their work, with particular application to devices and contrivances that are intended to be extended and customized by end users. That pushed some buttons in my head, and I posted a comment on the subject, which I've extracted below. I have some more to say on the subject, which I thought only fair to say on my own blog, so more posts will follow at less than the usual irregular intervals, I hope.

Oh-oh, you hit one of my current hot topics. I feel a rant bubbling up; I must take on my Aspect and wield my Attribute.

The system I'm working on now has some major design problems because some fundamental issues about valid character sets and the use and communication of metadata mixed with data weren't addressed at all. These things are central to building a system that's flexible, extensible, and allows mashups to be created without knowledge of the system internals (preferably without any sort of deep technical knowledge at all*).

I've been thinking about the sort of design criteria that are important in software that can meet these requirements. Here are my first thoughts; I'll continue on my own blog as they develop, but you got the juices flowing now, so I'll begin here if you don't mind.

1. Quoting is vital. It must be easy to encapsulate any string of valid data (e.g., text characters, images, the basic vocabulary of a web page) so that the system can treat it as an opaque object except where the data really is meaningful. It shouldn't be necessary for an admin or someone extending the system to deal with escaping characters significant to parts of the system, like '&' and ';' in HTML, or ''' or '"' in SQL literal strings, or (oh, help me Noshabkeming!) spaces in filenames. Always remember that a filename can come from most anywhere.

2. Metadata is data to any system that doesn't have to process it. Opaque objects have to remain opaque unless the software really needs access to the insides. Accidental access is a good creator of truly diabolic bugs. I created a test case yesterday with an object whose name contained an apostrophe. This caused the web application that read the name from the database to crash.

3. Objects shouldn't have to have knowledge of each others' lifecycles. If an object is created in one system and another system creates another object to collaborate with it, then either the first has to exist for as long as the second needs it (and that's often not easy or even possible to guarantee), or the second system has to make sure that it copies everything the second object needs from the first, without creating any issues of staleness of the copies during the life of the second object (and that's as close to an intractable problem in a distributed system as I know about). Anybody who's ever slaved over request-scoped webapp variables has been bitten by this one.

Akk! This is growing from a screed into a tome; not what I intended. I'll stop now and go get ready for work. Let me know what you think of this.

* Librarians are technically-oriented, but don't necessarily have specific knowledge about the administration of software, especially web-based systems. The manufacturing workers who administrate my system are not technically sophisticated at all; they're bright people, but don't have technical educations, so they're not familiar with some basic concepts that would make it easy for them to create a mental model of what they can do with the software. And I can't expect to train them in something that's irrelevant to their jobs.

Why is Software Development the Butt of All Those Jokes?

This is the first in an irregular series of posts on the subject of software development, its history, its current state, and its potential futures. Software development is a subject I've been passionate about for a long time, and one which has demanded a lot of my professional life. I'd like to present some of my experience and the conclusions I've drawn from it for others to use.

I've been a software developer for almost three decades now, and I probably know all the jokes about how bad software development is. There's some reason for the jokes. Software is too hard to develop, it takes too long, costs too much, and has too many bugs. Big systems aren't reliable, are too hard to understand. No one understands how to manage software development, how to plan it, or how to design it so that it performs the functions that are required.

Probably the best known joke about software is the old line, "If buildings and bridges were built the way we build software, the first woodpecker to come along would destroy civilization." True or not, the fact that so many software professionals repeat the joke indicates that someone believes there's truth in it. It shows a bad case of what I call "concrete envy" in the field, a feeling of inferiority to the older, notionally more mature, engineering disciplines.

Now that I've said the things that everyone knows, let's talk about the real elephant in the living room. The reason nobody knows how to manage software is that nobody really knows what software is. Computing is a bastard field, out of electronics by mathematics. Computer science as a research or educational discipline at first was organized in either Electrical Engineering or Mathematics departments, and the two had very different ideas of what "programming" was. Was it science or engineering? Mathematical formulae or electrical diagrams? Abstract symbology or concrete instructions? And then it got more complicated as new generations of computer languages came into use by programmers who had never constructed a patch block or written a program in machine code. They took the abstractions of the languages for granted as real things, not combinations of registers and arithmetic units. Several generations of languages and tools later almost no one in the field has any connection with the original concepts, which are buried under layers of other abstractions.

To most practitioners now, software is neither science nor engineering but a technical craft with its own rules and requirements, its own language and symbology. Its purpose isn't learning about nature or about what can possibly be constructed, it's about building specific devices for specific purposes. It's not done by universities or by engineering labs but by corporations that need software to operate their businesses, and need to manage the cost and schedule of projects to construct it. And the people responsible for the creation of software are often managers who were never programmers themselves and don't have any understanding of what what needs to be done, or what the result of the work will be. Sometimes (especially in open source software communities) the people responsible are also the ones who do the development, but they are less concerned by how the software is used than by how it is designed and built.

Now this is starting to sound like a common software rant, I know. But consider the implications of there being many different kinds of people with different kinds of expertise involved in the software industry. There's no agreement on what they're working on, let alone how to work on it. And then we get into the deep quagmire of requirements versus specifications: the question of how to determine what the software should do, and how to translate that into a description of how the software should work. Many's the project that's bogged down in that pit only to be dug up later by paleontologists in chunks of peat.

So here's the task I've taken on for these posts. I'm going to describe the state that software development is in today, with some attempts to understand how that state came to be. Then I'm going to prescribe what I think is a good, but certainly not the only good, treatment regime to improve matters. Along the way I'll talk about some of the prescriptions that have been handed out before, and why they did or didn't work. I promise that this will not be a completely objective analysis: I have strong opinions, and a particular viewpoint to work from, and that will color what I have to say. I hope that means that it will be colorful as well.

Some topics I will definitely touch on: the checkered history of programming languages, tools, and paradigms, the business of development methodologies, and the effect of the high-tech economy on progranmming. I welcome your comments on what I have to say, and will respond as I can.

Next up: what is software, and what does it mean to "build" it?