In our last article, we discussed the motivation for wanting boot time reduction. As discussed, we are trying to create as "instantly on" an experience as we can for in-car computers. We're taking a holistic approach to the problem by looking at every place that the system delays during bootup and trying to list all our options for reducing the times in that area.

You may have noticed over the last several years that the delay has increased between when you start a car and when you hear the radio. When head units were simply analog FM and cassette adapters, music would start blaring out, at the current volume, the instant the car was started. These old stereo units had analog potentiometers for the volume control, analog tuners to get the FM signal and analog tapes that instantly started producing sound. Nowadays, a CD player/FM tuner is a mini-computer. The volume can be set to a non-blaring volume automatically between startups. The buttons and knobs now used rarely are potentiometers; they merely send plus/minus information to the tuner controls. To play a CD now requires spinning up the CD, and the firmware on these devices has to boot up, going through some sort of POST (power-on self-test). Sometimes the newest devices actually have to talk to the car's computer, adding additional delay.

There are other reasons for the increasing delay. When aftermarket amplifiers are installed in a car, you often have a staged system where the head unit turns on and sends 12 volts back to an amplifier, which then turns on, at which point you get sound. The amplifier has to charge up its capacitors and level out its power in order to produce high volume. Thus, you now have a cascading delay effect where the car turns on, then the head unit (radio) boots up, then it tells the amp to power on and then the amp boots up--thus, it takes several seconds before you hear anything. If the amp is wired to start up at the same time as the head unit, you may experience a loud pop as the amplifier pumps out transient voltages from the not-yet-powered head unit. They even sell devices that add several seconds of delay to a 12-volt line to solve these popping problems.

So while the BMW 7-series navigation unit is engineered to show a video splash within milliseconds, the norm for audio devices is to produce output after several seconds. Thus, it is reasonable to give this same leeway to an aftermarket in-car computer. However, fully booting an in-car PC can take almost a minute. The question is, how does one reduce that time?

Booting many homebrew in-car PCs can take, literally, a minute. A lot of the delay results from the operating system booting or waking up from hibernation, but it's worth looking at the entire sequence to establish a baseline for the hardware we're using. For the purposes of our analysis, booting up a computer in a car consists of the following steps:

Car power stabilization: The 13.8V power line, which dips down to as low as 6V or gets cut off during engine cranking, must stabilize over 12V. This takes fractions of a second but it does take time. (Cost: ~ tens of milliseconds)

Power supply/regulator stabilization: The circuitry that powers the engine, be it a 120V inverter or a DC-DC power supply, and the associated power regulation circuitry that delivers clean 12V/5V to the computer must stabilize. Inverters can take several seconds to deliver 120V, while DC-DC boards are pretty quick. (Cost: ~ hundreds of milliseconds to seconds)

Power sequencer hits ATX-on button: This step can add time. Many motherboards now have a wake on power loss feature (technically a wake after power loss) that makes them instantly start up when power becomes available. However, many power sequencer/shutdown controllers, which make sure computers turn on and off with the car, tend to add delays to start-up. They usually give the power supply 2-3 seconds to fully stabilize its voltage at 12V; if this doesn't occur, the motherboard can hang on boot. (Cost: up to 3 seconds)

POST: The power-on self-test is the first part of the bios code. This can be reduced greatly but not eliminated by disabling memory checks, startup flash screens, floppy seeks and the like. Without getting a custom BIOS, however, this still takes time. In practice, it can be reduced on some motherboards to less than a second. (Cost: ~ 1 second)

BIOS: These are the rest of the BIOS functions that occur after the possibly necessary self-test. They include a variety of auto-configuration of plug-and-play settings, auto-detection of hard drives, power management and the dreaded DMI pool message that lingers on the screen for many seconds. This is the bulk of the pre-OS boot time. (Cost: ~ 1-10 seconds)

Bootstrap: This doesn't take long at all, but this step can vary based on the boot device. Because it could be hard drive or Flash, at the minimum you have the access time and transfer speed of the device, so it can take several tens to hundreds of milliseconds. If this is a two-staged process, as can be the case with boot loaders (that redirect from the beginning of the disk to some offset on the disk, if I understand correctly) that can add a bit more time. Although the latency of the disk or solid-state memory can change this bootstrap timing, the more important impact of changing the disk is in the boot times discussed below. (Cost: ~hundreds of milliseconds for bootstrap; tens of seconds to minutes for actual OS load)

Run boot loader: This step of the process is the first time we get to run code we may have written. In the Linux case, this would be GRUB or LILO. (Cost: less than a second)

Operating System and Drivers: This step is the long (potentially upwards of a minute) leg of our journey to a user prompt. The baseline we used when benchmarking this particular step is the venerable DOS, which boots in about the same time as the Linux boot loader. The worst case would be a full install of some operating system, un-tuned, with tons of unnecessary drivers, which could take another minute to boot. (Cost: Un-optimized, over 60 seconds. Somewhat optimized, as low as 15 seconds. Goal, less than five seconds).

Show user prompt: The OS eventually must finish booting and show the prompt, whether that is a GUI screen, a text prompt or a voice prompt for audio commands. At this point the system must be fully functional and able to accept any commands.

There are several good reasons to reduce boot times besides getting the system up quickly when the car starts. PVRs (personal video recorders) such as TiVo are available everywhere, but there are no good, well-integrated PMRs (personal media recorders) for in the car. Two key ingredients are needed to make this type of device work well with an in-car computer: the ability to download dynamically a list of program times; and the ability for the in-car computer to wake up on a schedule, do some work and go back to sleep.

The ability to download dynamically program times requires some sort of network connectivity. The second ingredient requires an in-car computer that can wake up when it needs to, day or night, to record a program. However, most PCs, including most small, low power motherboards that are being used for in-car PCs, take too much power even when they are sleeping. They consume 200mW of power, supplying standby power to Ethernet (for Wake-on-LAN features) to the USB ports and to whatever circuitry is needed to start the computer. This is the power equivalent of leaving the dome light on in a car, unsuitable for long use.

At CarBot we've taken the approach of reprogramming the power sequencer in order to implement a power budget. Instead of the car computer being on only when the car is on and for a short time after, the computer starts up on a schedule--in our case, every two hours--checks for Wi-Fi connectivity, downloads any new e-mail, geoblogs or software updates and takes care of any other cron-job type tasks. Because the unit uses about 1.5-2 Amps of power while running and accessing the hard disk, we've calculated that the unit can run for about 45 minutes between drives, to be ultra-conservative about not draining the car battery. As a simplified explanation, when the car is driven for roughly 15 minutes, we assume the battery has recharged and we reset the budget.

Based on a four-minute round trip cold boot->powered and checking for tasks->shutdown, the CarBot can go about 2.5 days before it must shut down for good. That means if we woke up every hour (the kind of granularity needed for PVR functionality), we would go for only 1.5 days between drives. If the driver didn't drive their car for two days (say, the weekend) and expected to have NPR waiting for her on Monday morning, it might not work out.

If we can reduce that boot time by half, we can double the frequency of startups. For a point of reference, OnStar starts up and phones home by way of the analog cellular network every ten minutes. This is because of the feature of OnStar where you can call and ask your car to be unlocked if you locked your keys inside. In order for CarBot or other in-car computers to do useful cron-job type work, the boot times need to be reduced to almost nothing, more for power reasons than time reasons. Examples of cron-job functions would be waking up and taking time lapse photographs of the environment for surveillance; waking up during the night and downloading a large batch of MP3s from the house over Wi-Fi in-car PMR; recording on-air radio; and downloading software updates blogs, news and so on, on a schedule.

In our current power budget scheme, at 2 Amps we support only 45 minutes of uptime when the car is not driving. Obviously, most radio shows last more than 45 minutes, so the current power budget is insufficient for true PMR functionality. However, by reducing boot times, using very low-power sleep modes and using low-power solid state storage instead of hard drives, we should be able to get this functionality going.

Now we're going to look at each step of our boot process and see where we can shave off time.

1) Power stabilization in car: The ideal solution for this step would be to have a sleeping computer that simply woke up the moment the user started cranking the ignition. In fact, this sometimes is possible. If the aforementioned cron functionality exists in the car, the software can be programmed to learn when the daily commuter starts their car in the morning and adaptively wake up in time for the person to start their car.

2) Power supply stabilization: Because engine cranking lasts several seconds itself, starting the computer at the beginning of engine cranking can shave time off booting. This functionality requires a power supply that can survive engine cranking, such as the Morex 80W power supply.

3) Power sequencer hits ATX button: There are two common approaches to starting an ATX-based computer. One is wake-on-power-loss feature, available in many motherboard BIOS settings. When the board loses power for any reason, it reboots when power is reapplied. This is fairly low-latency, but measurements show it still runs on the order of a second. An ideal situation would be to go back to the old AT days where power-on automatically would boot the PC; alas, those days are gone. Even if the ATX power supply is shorted (purple to ground) to automatically power itself up, the motherboard does not automatically power up unless the power switch is hit. This is the other approach, and power sequencer boards such as the ITPS from Mini-Box can connect to the power header on the motherboard and press the switch when the car's accessory power (key on) is activated. However, the drawback of these systems is they add their own delays, both to help with 2) (waiting until a smooth 12V is achieved) and waiting for the ignition cranking to stop. For instance, this ITPS sequencer has exactly three seconds of additional delay from key on to pressing the computer's power switch. To alleviate this delay, the firmware on this ITPS can be reprogrammed, which we've done, and the wake-on-power-loss feature can be used instead.

4) Power-on self-test (POST): There's not much to be done about POST without replacing the BIOS. With a BIOS replacement, memory testing and initial board diagnostics can be exactly controlled. However, it is a good idea to have a hardware test when any system boots up to determine properly if it's safe to go on booting. You wouldn't want to get in an undefined state that drained the car's battery, for instance, and part of controlling what state the machine gets into is making sure it is working. POST generally takes a second, and for our purposes we assume that even if we reprogrammed the BIOS we would not completely eliminate POST.

5) BIOS: This part of the boot process can take 2-10 or more seconds to complete, because of all the mostly unnecessary functions it performs. We've already been able to get it down to several seconds by disabling any unused devices and disabling auto-detection of any kind. However, because the OS simply reinitializes all the devices anyway, this time should be zero.

Several BIOS replacements were found in the process of trying to get the boot times down, including Linuxbios, Tinybios, General Software's embedded BIOS 4.3/2000 and Phoenix's embedded BIOS.

The most interesting candidate for BIOS replacement is, of course, from linuxbios.org, which uses it for bootstrapping nodes in a high-performance computing environment. The Epia-M motherboards we are using are one of the more popular boards they support. The Tinybios option would cost us about $3000, but it also looked extremely promising from a time reduction standpoint. This link from 2001 documents merely 800ms from power up to LILO using General Software's embedded BIOS. Both General Software and Phoenix BIOSes look increasingly more expensive (judging from their Web sites; I haven't received pricing yet), but so did the original $10,000 quote we got when we asked one company if they could help us boot Linux faster. So we're getting better.

Some vendors are giving up on the OS altogether and putting application functionality into the BIOS itself. This article on LinDVD is a Linux-flavored example of a general trend to replace the PC BIOS. And that may be the approach we eventually have to take. If we simply took the GRUB boot loader and added a splash screen, sound drivers, an MP3 player and a DMR, we would be pursuing a similar path to other pre-OS multimedia environment vendors.

In the research for this article, I learned of a general desire to replace all PC BIOS with some more modern firmware. The Extensible Firmware Interface has been introduced by Intel and other vendors and is available on some boards. I imagine, however, this would tend in the direction of lengthening boot times with more digital-rights management, diagnostics and other bric-a-brac instead of helping our goals of creating an embedded system.

6) Bootstrap from disk: This particular step is noted mostly because the disks can vary in speed and because parts of the OS might be able to be crammed into the BIOS chip itself. However, the fractions of a second that can be recovered at bootstrap are less useful than the many tens of seconds that can be reduced through improving the speed of storage device during OS load (see 8) below).

7) Run boot loader: This is the beginning of our journey into OS code. Although the boot loader is strictly not the OS, it was found in testing that boot times for Win98 DOS are almost identical to the boot times for GRUB. In fact, over several tests with our hardware, we got about 13-14 seconds from power on to a GRUB screen or DOS prompt.

Looking at it another way, ignoring the OS, GRUB is actually our first chance to do some useful work for the end user. Several eye candy solutions for Linux boot screens were found for LILO, and I'm sure GRUB has some of the same. Adding only the EPIA-M sound driver, it would be possible to emit both a product splash screen and start playing some music--either off the disk or canned--while the OS loaded.

Using DOS boot times as the baseline, we found that it should be possible to get the system displaying an image and playing sounds within approximately 15 seconds of boot, without any of the aforementioned BIOS time reductions.

8) OS load all drivers: After all the prior optimizations, we have to look at how actually to get the system up and fully running by booting the operating system. One question yet unsolved is that if we use a boot loader hack to get audio playing, we may not be able to keep audio playing without interruption. The solution to this is instead of shoving the OS functions into the BIOS or the boot loader, we keep them where they belong while starting the essential (video and sound) services first. So there are two aspects involved. One, because we have a controlled hardware configuration, we can create a deterministic boot process, analyze it carefully for dependencies and parallelize boot tasks that don't depend on one another. Two, because we need splash screens and sound as soon as possible, we would put these as early in the boot process as possible and perhaps finish the booting process as a lower priority task.

An IBM article written by James Hunt documents how to speed up the Linux boot process by parallelizing dependencies in the boot process. This article confirmed my long-held suspicions that the computer was sitting there waiting for much of the boot process.

On the vendor-supplied front, FSMlabs documents a 200ms boot until user code execution with its optimized Linux boot. However, FSMlabs are focused on delivering Linux with a hard real-time kernel, something we don't need. They were one of the two vendors that offered to solve our problem for $10,000, a rather steep budget for a solution that would be tied to the particular hardware we were using.

And for our motherboard in particular, Mini-box provides a fine-tuned Linux distribution that suppresses all text output and goes straight to an OS prompt. We purchased and tested their distribution. Out of the box, it did a full Linux boot--all drivers for our board--to a prompt in less than 30 seconds. Unfortunately, this still isn't quick enough for our needs, so we're going to need to optimize further, as well as adding video display to the booting process.

9) Show user prompt: The system can't be considered booted until it stops thrashing and can provide uninterrupted functionality of all applications. If the boot process is going to make the MP3 playback sound choppy, then it's going to need to be modified to take a lower priority than the sound driver. However, if the user immediately tries to have their e-mail read to them or tries to activate a GPS, the illusion of readiness provided by getting audio and splash screens up quickly is be broken. Thus, the entire boot process must be fast enough. Getting the user prompt available (or its equivalent, such as a menu, or a spoken "I'm ready to accept input" for voice activated systems), is the primary concern of the system. Although this is easy to do for a single-purpose embedded computer, such as a navigation system, the real challenge of our system is to get a general purpose computing device to behave like an embedded device.

In this second installment, we explored the methodology we've been using to attack the boot time reduction problem. I've split the boot process up into about nine steps, analyzing each, and assessed how much it will cost me in development time and in licensing fees to cut down the time for that step. I have sent e-mails out to the least expensive and most relevant vendors (LinuxBios, General Bios), and I'm working on how quickly we can get our car PC unit booted.

In Part III, I will summarize the boot time reducing solutions I have found and will report on the boot times we've achieved on our hardware.