Boot Linux Faster by Starting Services in Parallel
For an overview of the technique, look through Boot Linux Faster. That said, I've made some modifications to the scripts: namely, I've made them work. Note that this isn't the only method of starting services in parallel. There is also the initng project, and Gentoo's native rc script supports running services in parallel via a configuration setting in /etc/conf.d/rc (RC_PARALLEL_STARTUP="yes").
Note: these files are unmaintained. They were written for Fedora Core 3 and 4, but they should work on most other distributions and versions with little work. However, I now use Gentoo Linux, which uses a rather different scheme for its init files. Thus, I will not continue to test these scripts, but I will make modifications when told that they are necessary.
This is a patch for my /etc/rc.d/rc file. It should work for yours, too. Apply it by running (as root): patch -p0 < rc.diff from wherever you decided to save it. The new script will search for start*.mk before starting services and stop*.mk before killing services, where * is the new runlevel. If it doesn't find one of them, then it will use the original script for that operation.
This is a modified version of the makefile provided in the link above. It now reads the list of services to start/stop from your /etc/rc*.d/ directories. This file needs to go into your /etc/rc.d/ directory.
This is an example of a list of dependencies for starting services in runlevel 5. It works on my system, but I don't start many services. If it causes problems for you, let me know what changes need to be made. This file also needs to go into your /etc/rc.d/ directory.