Reducing OS Boot Times for In-Car Computer Applications, Part II

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.
Car Stereo Boot Times
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?
In-Car PC Boot Time Overview
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.
In-Car TiVo for Radio and Other Cron-Job Functionality
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.
Reducing Boot Times Step by Step
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.
Conclusion
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.

Damien Stolarz is an, inventor, writer and engineer with years of
experience making different kinds of computers talk to one another. He
is the CEO of Carbot, Inc., an in-car computer company, and Robotarmy
Corp., a networking software development house.