parallel processing and bash reduce

It’s sad that after all this time, one can look at any random article on parallel programming and find some variation of:

for i = 1 ... n
      create thread i
             do something
end for

as if that was the only way to express parallel computation. This is such an awkward way of looking at problems.  I think many problems come from the sloppy “non-determinism” of the operating systems and multi-core machines.  One of the few  interesting ideas seen in the last 20 years on parallel processing is the Google map-reduce scheme ( . But what I find impressive is bashreduce. This is really a clever trick and a great validation of the UNIX toolset design (as if it needed another validation).

Advertisements

RTOS design and embedded system development

Real-time operating systems are either a solved problem or a backwater of engineering design. Threads, semaphores, mutexes, some basic I/O, priority scheduling all of this has been more or less standardized in the  POSIX 1003.13 smaller profiles (51,52) for many years. The basic programming model has not changed in years. Even FSM’s original RTOS and QNX, the two most unusual RTOS’s, are pretty similar from a programming point of view except for the split between real-time and non-real-time in our old product.  My suspicion is that the programming model provided by these RTOS designs can be replaced by something better mostly because I think synchronization is a painful and error prone exercise that only gets worse as systems become more complicated. On the other hand, although many of our customers really loved it, and I think it was a huge advantage, the split mode approach in the old RTLinux* was a difficult learning experience for a lot of people.

Consider a simple design:

  1. Task A: collect data from an Analog/Digital converter, sampling at rate 1/t seconds and filling a small buffer (1/t)*n seconds.
  2. Task B:  Aggregate A data and produce 3 streams of processed data that are functions of the input data and some settings.
  3. Task C:  produce control data from the processed data at an output rate of 1/t2 seconds
  4. Task D: provide a secure internet port which will process requests to interrogate data, to setup data push at some rate maximum 1/t3 pushes per second and update the settings with worst case delay from arrival of input packet to reset of 1/t4 seconds.
  5. Task E: operate a touch screen display that has some of the same functionality as task D

That seems like it should be straightforward, but it’s not: it’s a one year project that has a 70% chance of failing. Making sure shared data is efficiently and correctly shared, validating that the scheduling and timing is ok, and optimizing for hardware limits and power are all hard.  And that seems wrong because there is nothing in such a project that has not been done thousands of times before.  As the electric power industry stumbles into modern software based control,  the slow development times and poor reliability of products developed under this model is a serious problem.

* NOTE: RTLinux is a trademark of WindRiver Systems.

[note: edited to remove garbage characters]

 

Mathematics education needs probability and art

I agree with this but really, basic ideas of calc are simple and could be taught easily early on too. Found here. But this paper is also good and even though I don’t agree with it 100%, I think it is a brilliant diagnosis

A musician wakes from a terrible nightmare. In his dream he finds himself in a society where music education has been made mandatory. “We are helping our students become more competitive in an increasingly sound-filled world.” Educators, school systems, and the state are put in charge of this vital project. Studies are commissioned, committees are formed, and decisions are made— all without the advice or participation of a single working musician or composer. Since musicians are known to set down their ideas in the form of sheet music, these curious black dots and lines must constitute the “language of music.” It is imperative that students become fluent in this language if they are to attain any degree of musical competence; indeed, it would be ludicrous to expect a child to sing a song or play an instrument without having a thorough grounding in music notation and theory. Playing and listening to music, let alone composing an original piece, are considered very advanced topics and are generally put off until college, and more often graduate school. As for the primary and secondary schools, their mission is to train students to use this language— to jiggle symbols around according to a fixed set of rules: “Music class is where we take out our staff paper, our teacher puts some notes on the board, and we copy them or transpose them into a different key. We have to make sure to get the clefs and key signatures right, and our teacher is very picky about making sure we fill in our quarter-notes completely. One time we had a chromatic scale problem and I did it right, but the teacher gave me no credit because I had the stems pointing the wrong way.” (found here )

musician wakes from a terrible nightmare. In his dream he finds himself in a society where
music education has been made mandatory. “We are helping our students become more
competitive in an increasingly sound-filled world.” Educators, school systems, and the state are
put in charge of this vital project. Studies are commissioned, committees are formed, and
decisions are made— all without the advice or participation of a single working musician or
composer.
Since musicians are known to set down their ideas in the form of sheet music, these curious
black dots and lines must constitute the “language of music.” It is imperative that students
become fluent in this language if they are to attain any degree of musical competence; indeed, it
would be ludicrous to expect a child to sing a song or play an instrument without having a
thorough grounding in music notation and theory. Playing and listening to music, let alone
composing an original piece, are considered very advanced topics and are generally put off until
college, and more often graduate school.
As for the primary and secondary schools, their mission is to train students to use this
language— to jiggle symbols around according to a fixed set of rules: “Music class is where we
take out our staff paper, our teacher puts some notes on the board, and we copy them or
transpose them into a different key. We have to make sure to get the clefs and key signatures
right, and our teacher is very picky about making sure we fill in our quarter-notes completely.
One time we had a chromatic scale problem and I did it right, but the teacher gave me no credit
because I had the stems pointing the wrong way.”

Process algebra (updated)

The first part of a critique of process algebra is below.  This relates to the Recursion and State paper and explicatory blog entry where I show how to compose classical automata and define them “abstractly” and to a complaint about the weak critique of automata theory in standard process algebra literature and also to a remark about Dijkstra’s error.   There are other parts of it scattered around in some recent posts and some other issues that need to be raised, but the basic argument is in place.

Wind Power slowdown in Germany

The idea that Germany is playing catch-up with Europe’s most promising strategy for renewable energy is jarring. This is Germany, after all, the country that 11 years ago put the Green Party in government, decided to phase out nuclear power, and pushed wind energy and photovoltaics to grid scale. Today Germany’s installed wind-turbine capacity of 24 gigawatts ranks second only to that of the United States (which has 25 GW). But despite the promises, greenhouse-gas emissions there haven’t plummeted. Rather, they have gone down only slightly since 2000. Germany, it seems, has lost its groove.

The result is a turnabout that would have seemed preposterous even six months ago: ”Everyone in the environmental community is looking to the U.S. now,” says Elias Perabo, who codirects a campaign against the use of coal for Germany’s Berlin-based Climate Alliance. IEEE Spectrum

powerbookOne problem is the old grid which is not capable of dealing with wind as a serious power source.  Germany, like the US, has a legacy power grid that is designed around a few big stable power sources, but distributed energy resources (DERs) and especially sources like wind put very different stress on the system. Suddenly you need a lot of high speed, low-cost, distributed control systems – and they better be secure.

chrome OS

SAN FRANCISCO — In a direct challenge to Microsoft, Google announced late Tuesday that it is developing an operating system for PCs based on its Chrome Web browser.

The move sharpens the already intense competition between Google and Microsoft, whose Windows operating system controls the basic functions of the vast majority of personal computers. NYT

Google sez

Speed, simplicity and security are the key aspects of Google Chrome OS. We’re designing the OS to be fast and lightweight, to start up and get you onto the web in a few seconds. The user interface is minimal to stay out of your way, and most of the user experience takes place on the web. And as we did for the Google Chrome browser, we are going back to the basics and completely redesigning the underlying security architecture of the OS so that users don’t have to deal with viruses, malware and security updates. It should just work.

Google Chrome OS will run on both x86 as well as ARM chips and we are working with multiple OEMs to bring a number of netbooks to market next year. The software architecture is simple — Google Chrome running within a new windowing system on top of a Linux kernel. For application developers, the web is the platform. All web-based applications will automatically work and new applications can be written using your favorite web technologies. And of course, these apps will run not only on Google Chrome OS, but on any standards-based browser on Windows, Mac and Linux thereby giving developers the largest user base of any platform. Press release

Looks like the revenge of Plan9 is on.

The source of error (updated)

Here’s Edsger Dijkstra discussing the birth of the use of axiomatics in computer science – the start of “formal methods” research.  What’s striking is the assumed choice between “axiomatic” and “mechanistic” as if there was no other way. In a later note he writes:

And now we are back at our old dilemma. Either we take by definition all properties of the model as relevant, or we specify in one way or another which of its properties are the relevant ones. In the first case we have failed to introduce in the name of “divide et impera” an interface that would allow us to divide and rule and the study of how we could build upon the (only implicitly defined) interface seems bound to deteriorate into a study of the model itself; in the second case we are again close to the axiomatic method….

[…]

Or, to put it in another way: if the traditional automata theory tends to make us insensitive to the role interfaces could and should play in coping with complex designs, should it then (continue to) occupy a central position in computing science curricula?

And I’m struck by the idea  that seems utterly wrong to me, that one either uses the methods of formal logic OR one is stuck without any ability to abstract or underspecify

The reason mathematics has advanced so much was not because of the Euclidean axioms-lemma-theorem straitjacket, but in spite of it. Luckily, when we actually discover mathematics, we do it the Babylonian way, empirically and algorithmically. It is only when it is time to present it, that we put on the stifling Greek formal attire.

so says Doron Zeilberger

UPDATE: I have a draft of the “process algebras considered harmful” note up.