Qooiii.com blog

I’m trying to understand ROM-RAM tradeoffs on a project that’s constrained in both ways. So far, I’ve been using pretty flaky heuristic methods, like building similar code on other processors, to understand the limitations. Doing that, I was able to conclude that my code had about a 50% chance of meeting my constraints.

I’ve been looking for ways to get better confidence. ROM constraints are very hard to reason about because they’re so implementation dependent. But I realized that there is a lower bound to the RAM used: the amount of state the program has to maintain at any particular time. This basically comes down to the number of bits of global state in the program plus the estimated depth of the stack.

The advantage is that the bits of global state are entirely implementation independent. You absolutely cannot implement the program with fewer bits of RAM than that, no matter how smart you are. The stack depth is less useful; it might vary by +/- 50% depending on the implementation. I guess the main advantage of this approach is that it lets you make tradeoffs in the feature set based on RAM requirements before you’ve written any code.

After doing this estimate, I ran across a cool paper on a similar topic: how the compiler can automatically reduce RAM usage by allocating fewer bits for variables that never take on more than a handful of values.

I saw this on Planet Python: a programmer decides his techie lifestyle is crazy, quits his programming job to tend bar in a ski town, and purges the remnants of his old life.

In those posts is a critique of the introverted programmer lifestyle. He mentions that all of his hobbies are solo activities, for example, and that most of his apartment is just piles of untouched stuff except for his computer desk. He talks about using computers as an artificial, controlled environment to escape real, chaotic life.

It seems like it’s easier to be a virtual hermit today than it’s ever been. I can live in a megalopolis of eight million people and never have a single meaningful interaction with a stranger. My car is a wall between me and other commuters. Even in crowded places, my iPod is a virtual barrier, blocking out unwanted social interactions. All of my relationships can be carried out online, where they’re easy to control.

This is obviously no way to live. Making life utterly predictable is like living in a zoo—it’s no Kalahari.

I saw an article on Slashdot about how math education takes all the joy out of actually doing math. Educators confuse practicing mathematical methods with actually teaching people to do math.

This leads to a bigger problem: school. People who get good grades in math all throughout school aren’t necessarily good at math. They’re good at manipulating symbols and translating word problems into equations. As the paper says, this is being good at following directions, not being good at the creative subject of math.

We have a similar problem in my field. Engineering is about finding joy in creatively solving problems. Yet we churn out students who have spent most of their lives learning how to use the tools, but never solving actual problems. They end up in big companies where their bosses give them glorified homework problems. That’s not engineering.

Today at work, somebody was having a meeting in their cube and motioned for me to come over. There was some discussion about how to implement some obscure technical detail, and they wanted to know my opinion.

“It absolutely doesn’t matter. Just pick something,” was my reply, and then came two more questions. “Those decisions are totally arbitrary. Do whatever is easiest,” I answered.

In 2 minutes, I think I prevented about 2 hours of meetings. That’s like saving the company a thousand bucks.

Many decisions really are arbitrary. I guess people are sometimes just waiting for permission to make them.

On a similar theme, I do love this about Silicon Valley: people are happy to let you assume whatever role you fit into. If you know what you’re talking about, it doesn’t matter if you’re the youngest person in the group—people will listen to you anyway.

I guess they’ll also happily blame you later when something doesn’t work.

Say you have a counter driven by a programmable clock divider. The clock can be divided by 1, 2, 4, or 8.

The straightforward way to implement this is to design a clock divider, then use a mux to select the clock for the counter. This is totally wrong.

Instead, just make your counter 3 bits bigger and divide your clock in the least-significant bits. You need just as many flops and muxes to shift-adjust the output as you would to generate and select a clock. By making the change, you’ve reduced your design to using a single (ungated) clock, so now state transitions are atomic. Nice.

Apparently, WordPress has plugins to do automatic L^AT_EX formula insertion.

Here’s a formula to test this nerdy feature:

On my vacation last week, I decided to skim through Strogantz’s Nonlinear Dynamics And Chaos. It’s got a lot of interesting information, though most of it doesn’t seem particularly useful.

One interesting insight is that you cannot create an oscillator from a continuous-time system if it has only a single degree of freedom (that is, a single state variable). For an oscillator to work, it has to ping-pong back and forth between two states, like “1″ and “0.” This means that the current state of the oscillator has to be encoded in one of the degrees of freedom. This isn’t enough information, though, because the oscillator can either be approaching or leaving the “1″ state—this information cannot be derived from whether the oscillator is in the “1″ or “0″ state.

What’s interesting here is that you can glance at systems and figure out whether it’s possible for them to oscillate just by counting degrees of freedom. If you have a bunch of state variables, but they’re very weakly coupled to each other, then you can say with high certainty that oscillation won’t occur.

On the other hand, in discrete-time systems, you can build an oscillator with only a single state variable. For the 0-1 oscillator, you could just say
q_n+1 = 1 - q_n.

John Gall’s Systemantics states the following principle:

“A complex system that works is invariably found to have evolved from a simple system that works.”

There are a few cases where this isn’t true, like B-2 bombers and nuclear power plants, but they cost billions of dollars each.

With this principle in hand, we can almost always reject calls to tear down a system and rebuild it from scratch, even if that system seems broken. Otherwise, when catastrophe inevitably strikes, we’re bound to hear that classic utterance of shocked systems engineers: “Oh, I hadn’t thought of that.”

I have this vision of closed-loop feedback systems becoming more important as we demand greater efficiency.

There’s some debate about whether the most important invention of the industrial resolution wasn’t actually the governor on steam engines. A governor keeps the engine running at a constant speed of rotation by adjusting the throttle when the speed is incorrect. Without it, drive shafts would be driven very erratically.

The governor is a simple case of mechanical negative feedback. It mechanically computes the error in rotational speed and converts this into a change in amount of fuel used.

The same principle of sensors providing feedback transformed our dirty, gas-guzzling carbureted gasoline engines into (relatively) clean, efficient fuel-injected ones. It also gives us dryers that can sense when clothes are dry instead of running on a timer. Thermostats form simple feedback loops.

Still, there are a lot of opportunities where feedback could save electricity, resources, or time. Cooking is a great example. You can buy thermometers to embed in things as you roast them, so they come out exactly done. You can buy regulated water baths for sous-vide cooking. Expect ovens in the future measure surface temperatures with IR thermometers and turn off before your food burns.

My dishwasher requires me to experimentally determine the correct amount of detergent for the water here. It could easily sense the mineral content of the water and dispense the right amount of detergent for me. In fact, it may have to in the future to reduce the amount of unused detergent sent down the drain.

The key to all of this is sensors. They’re expensive and finicky. Exotic materials seem like the rule. The oxygen sensor in your car, for example, is plated with platinum (currently over $1000/oz).

However, all we really need is for the sensor output to be well correlated with the thing we want to measure. The worse of a signal we can tolerate, the cheaper the sensor can be.

Electronic sensors are ideal for two reasons. First, we can do a lot of signal processing to extract the information we want from the output signal. Second, electronic systems have virtually unlimited gain.

Back to the governor example, the signal processing corresponds to the way the mass of the spinning balls prevents quick changes in the throttle. The governor cannot respond very quickly, so it ignores brief errors. The gain corresponds to the leverage of the linkage to the throttle: with high gain, a tiny speed mismatch will cause the throttle to open or close a lot. High gain can lead to faster response and better efficiency (though in poor designs it can cause instability or oscillation).

All of this is pretty exciting to a sensors guy like me. If we can just get sensors cheap enough, they will be everywhere. Imagine running with insoles that selectively firm up to correct your posture. Or an oven that knows when your cookies are done. Or a bathroom fan that stays on until the humidity has dropped to normal so you don’t get mildew. There are also sustainability applications, like using soil sensors in fields to make sure we don’t overfertilize or overwater crops.

The applications are endless. Wherever there is inefficiency, feedback can come to the rescue.

The other day, I was staring at some sample chip layouts. One had a hand-designed processor core, while the other used a roughly equivalent processor synthesized from an HDL. Someone commented that the hand-designed processor would easily fit several times inside the synthesized one.

I think this is similar to the assembly-language debate. Sure, you can write all your code in assembly, and it will be faster (and smaller) than if you wrote it in a high-level language. Since programmers write roughly the same number of lines of code per day, regardless of the language, high-level languages should result in huge productivity gains. Your software is slower, but you can release your product much sooner.

This would be true if you took a program that was already designed, with data structures and flowcharts, and implemented it in both assembly and a high-level language. In the assembly program, you’d be spending lots of time shuffling things in and out of processor registers, managing call stacks, and other tedious tasks. The program in the high-level language would have none of these things.

In practice, something funny happens when the tools get better: the designs get more complex. Assembly language forced programmers to stick to solving the actual problem at hand, but higher-level languages free them to think about other things. For example, it’s difficult to find a C++ or Java program that doesn’t have at least one long inheritance chain for a single deeply nested subclass. Also, for awhile, almost every nontrivial program supported its own implementation of GUI skins.

Complexity is the problem. The more complex a design is, the harder it is to make it work. Some problems, like fighter jets and nuclear power plants, really do merit complex solutions (though not necessarily in software). Most other problems can get by with much simpler designs.

If you really want huge productivity gains from new tools, use the tools to simplify designs. Quit adding features. Quit adding states to the system.

I keep promising myself, “no more engineering textbooks!” but then I go and buy them anyway. Lately at work, I’ve been watching our ASIC team design a chip, and now I want to know everything about chip design. Since nobody is going to take time out of their lives to teach me, I might as well buy the books and teach myself. The goal isn’t to design chips—it’s to be able to converse intelligently about them. For example, I should know what’s hard to design versus what’s well-understood.

The problem is that I’m several books behind already. I have books on detection and estimation theory already in the queue, and my stubborn insistence on working through the exercises means it’s slow going.

Maybe it’s worth trying a different strategy. In his DSP course, Doug Jones at UIUC had a good ramble about how university courses go deep into their topics, but that they don’t try to give students breadth. I’m looking more for general design principles and strategies than for understanding of how, for example, to design a high-performance PLL on a deep-submicron process. The best way to get this kind of exposure is probably just reading through lots of books, but being very choosy about which problems to work.

I guess that’s a cheaper way to learn than taking classes (typically thousands of dollars per semester). Still, I wish I had a better way to get this kind of knowledge.

Being topical always seems pretentious, but here goes.

Government bailouts of failed industries seem like a horrible idea. It distorts the market by changing the rules after the game is over. The fact that auto bailouts are favoring some creditors, the unionized workers, over others, bondholders, makes things a little worse, since it also messes up the normal working of the credit markets.

But all that aside, letting any of these companies fail is subjecting the economy to a huge step function. Since our economy has a lot of short-term positive feedback, step functions usually end in disastrous oscillations far worse than the steps themselves.

In effect, we’re pumping lots of money into failing companies so that they can go out of business slowly. We’re supplying the negative feedback terms that the economy itself is unable to provide.

Tony Hoare had a lot of good things to say in “The Emperor’s Old Clothes,” his Turing Award speech to the ACM. For example,

“I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies.”

He recounts the story of how he watched his own programmers fail to produce a usable ALGOL 60 compiler after 30 man-years of effort. Then, he says,

“At that time I was reading the early documents describing the concepts and features of the newly announced OS 360, and of a new time-sharing project called Multics. These were far more comprehensive, elaborate, and sophisticated than anything I had imagined, even in the first version of the 503 Mark II software. Clearly IBM and MIT must be possessed of some secret of successful software design and implementation whose nature I could not even begin to guess at. It was only later that they realized they could not either.”

OS/360 was the gargantuan software effort that convinced Fred Brooks to write The Mythical Man-Month. Multics, with its overwhelming complexity, heavily influenced Unix to take the opposite approach—be as simple as possible.

He offers a critique of PL/I (one of the most complicate programming languages ever specified):

“The price of reliability is the pursuit of the utmost simplicity. It is a price which the very rich find most hard to pay.”

The implication is that the rich know how to ask for features, but don’t know how to ask for good design.

Strive for simplicity.

At one point, I was living in Albuquerque with a decent job and everything figured out. Then, I started listening to everyone tell me how the Space Shuttle project I was working on was one of the most exciting things they’d ever done in their whole careers…and I decided that maybe I didn’t want to be bored for the next 40 years.

I’ve always been interested in sensors, so I thought about starting a company to do something with cheap microcontroller-based sensor nodes. I started building some and saw that the costs quickly rose out of control. The simplest sensor circuit I could build, using microcontroller and almost no other components, cost about $12. Generally, companies sell stuff for twice what it costs to make, so that’s about $25 for a simple light sensor or photogate. A sound sensor would cost almost $20 to build.

Those sensors just communicate with a digital output—just on or off. To make them talk over USB raises the parts price to $25—so they’d sell for $50 minimum. A wireless part might sell for $70. Nobody could ever afford to buy this stuff.

When I moved to California, I was looking to learn more about integrated circuits and mass production. I picked a company that builds capacitive sensing chips, and so far, I’ve learned a lot.

I need to remember this more often. The goal is to use inexpensive sensors to make the world a better place (or at least a more efficient place, which is the same thing to an engineer). Focusing on that far-off goal should help keep the day-to-day stuff in perspective!

In summary, goals are good. Forgetting goals is counterproductive.

Wikipedia has a long write-up of what systems engineering is supposed to be. I have a very hard time believing that any of this actually exists.

It looks like the basic idea is to formalize project management as an engineering discipline. The goal of the project is to build a system (the product) that solves some problem, given some constraints. Systems engineering is supposed to be the process that gets you through the full lifecycle of the project, from defining requirements to customer support and product end-of-life. It seems to involve a lot of diagramming and documentation.

I don’t really buy most of this stuff. The fact is, we don’t understand good system design well enough to institutionalize it. Pretending that we can complete projects on time and under budget with more rigorous project management misses the point.

Here’s another idea: eliminate complexity wherever you can. Look at this draft paper on “Robustness and the Internet.” Though you’re usually unaware of it, the Internet is full of built-in negative feedback mechanisms designed specifically to kill tricky emergent behaviors. The designers of the Internet consciously put most of the intelligence at the edges of the network, making the core deliberately simple. Compare this to the phone system, with dumb nodes on the edges and fantastically expensive switches in the middle. Then notice that phone traffic is increasingly routed over packet-switched networks like the Internet.

As I see it, systems engineering should be about taking all of the rules of thumb that system designers use and giving them rigorous theoretical footing. I want to see papers on how decomposing computer programs into modules can be done to minimize a complexity metric. Or a paper telling me how to design computer systems that are more robust to programming errors. I want to see the gaps bridged between nonlinear system theory and actual design.

Maybe there are people doing this already, but for whatever reason, nobody knows about them.

Call me bourgeois, but I keep having cravings for Chipotle burritos. The problem is that the nearest Chipotle is 3.4 miles from my apartment.

There are 9 stop lights between here and there, and I can expect to stop at half of them. Each time I stop, I have to accelerate my 2000-kg Jeep to about 20 m/s when the light turns green again. If my Jeep were perfectly efficient, this would take 1/2*m*v^2, or 400,000 joules per stop. Let’s say it’s only 50% efficient (though I’m sure it’s less than that), so my trip to Chipotle requires 8 million joules at the very minimum.

These sound like big numbers, but it’s less than 3 kWh, or about 30 cents worth of electricity. Still that’s maybe 2-3 pounds of coal, or about 1 cup of diesel.

Cycling that distance would be better. Getting a 100-kg object to 10 m/s only takes 5,000 joules. I could do that a few hundred times with the energy from the burrito I bought (which has 3 million joules).

One of these days, we’re going to have to all agree to use the same energy units so people can do these calculations in their heads before deciding to drive to Chipotle.

When my mom was visiting and we drove down to Monterey, she pointed out the conspicuous lack of billboards along US 101. In fact, all throughout California, there just don’t seem to be that many billboards.

The reason: California’s 1967 Outdoor Advertising Act. Here’s an updated version of the rules.

The restrictions are simple: no billboards along scenic highways/byways or landscaped freeways. Businesses can only advertise on the same property they’re actually selling something from.

In addition to these rules, individual cities can and do ban off-site advertising altogether. Oakland made a fuss about this a few years ago when somebody sued them over their own 1997 ban on new billboards.

These last two recessions have been great for highway aesthetics as billboards erected before the bans have come done.

The only problem, then, is how to find a place to eat when you’re driving across this enormous state. Luckily, this is a problem GPS can solve without destroying the views!

I saw this on Planet Python or some such site awhile back:
10 Papers Every Programmer Should Read (At Least Twice). It’s a pretty good list.

I’m trying to get through the 1978 Backus paper right now. Though he was inventing a functional programming language that didn’t exist, it sounds a lot like today’s ML or Haskell. I love the idea that von Neumann programming’s emphasis on state transitions (which maps well into hardware) has created programs that are impossible to transform or reason about because they’re so tied to the hardware.

It seems likely that functional programming will come to dominate one of these days because the only state transitions in the system are at the level the programmer actually cares about. The compiler doesn’t have to reason about which side effects were important in some intermediate calculation, and can focus on finding the optimal implementation for the whole operation.

The Self paper is pretty interesting as well, because the authors tried to write a language that mapped well into human intuition.

Wow. Muir Woods is wonderful.

My mom and I got up at 6:30 AM and headed across the Golden Gate Bridge to hike a 6-mile loop in Muir Woods. The trail started at the visitor center, then went up Bootjack Trail to T.C.C., then back around on the Ben Johnson Trail to complete the loop.

Getting there early turned out to be an excellent idea. We had the trails almost all to ourselves until we got back to the visitor center. Also, they don’t charge you the $5/person entrance fee if you get there before they open the ticket window (the park itself opens at 8, and the ticket window a little after that). Even better, we cut an ugly half a mile off of our hike by getting one of the last parking spots in the tiny front lot.

Muir Woods is every bit as impressive as the larger Humboldt and Del Norte County parks. If you beat the crowds, it’s absolutely worth the trouble.

I’ve been using an Alesis QS 8.2 as a piano for awhile. It’s fine for Bach, which wasn’t written for modern pianos anyway. Unfortunately, it’s no good for later stuff that I want to learn, like Beethoven and Chopin.

The Alesis has hammer-action weighted keys. The “hammer action” means the keyboard models the nonlinear response to pressure of a real piano’s hammer mechanism, so it feels sort of like a piano. However, the keyboard doesn’t really go to a lot of effort to model how a piano sounds. It may just be that I’m not very good, but I’ve been having a hard time getting any subtle dynamic expression out of the thing.

Fixing this turns out to be expensive. The best option is just to buy a piano. For an apartment, an upright works, and they’re easy to find for less than $1000. Uprights actually have a totally different key mechanism to strike the strings than grands do, but a hundred years of engineering have made them quite acceptable. The only problem is the noise: you can’t turn them down.

The apartment-friendly option is a digital piano. Since they’re designed to be smaller replacements for grand pianos, they can cost just as much. For example, Yamaha’s Clavinova line tops out at $12,000 or so. The key mechanism is basically the same as a grand piano, (folded up a little more) but the hammer hits a sensor instead of a string. The Clavinovas go to a lot of trouble to model all of the physical things happening in a real piano. The marketing copy is downright frightening.

When I went to the piano store to look at these things, I found out the scary truth. The digital stuff, like the sympathetic vibration modeling, comes on every model down to the cheapest one. The price differences seem to be focused on the key mechanism. As it mimics a grand piano better, the price goes up. Lower-end stuff is fine for banging out pop tunes, but a lot of classical stuff requires you to build up finger muscles. The price differential between fast plastic keys like my Alesis and a Clavinova’s heavy, slow-moving wooden keys is more than the cost of a used baby grand. The price of renting a house to put the baby grand in tilts things back, though.

I made a deal with myself that I could buy a nice one if I get rid of my TV. Now I just need to find someone willing to come take the TV off my hands.