Brandon Philips
Austin LTC Summer Intern
Oregon State University
brandon@ifup.org

The Linux kernel manages a number of complex devices and for most of these
devices a scheduler is designed to manage access to the hardware.  These
schedulers are like project managers managing access to a budget.  Each project
needs access to the budget but being too generous to one project will starve
the others guaranteeing at least a slip in the schedule.

Much of the CPU scheduler policy is defined by constants that were discovered
and set by Kernel developers through a process of trial and error.  These
constants make a reasonable compromise to perform well for most workloads but
they cannot be ideal and can be improved for specific workloads.

One solution would be to allow the system administrator to tune these constants
on their own system.  This has several disadvantages: new workloads require
re-tuning by the administrator, the average workload is the only workload
accounted for, and it is time consuming.  More than likely the administrator
would be setting values based on educated guesses gathered from analyzing of
benchmark results.  But, what if the computer did this analysis and made
educated guesses itself?

Enter the genetic library.  In the most simple form a genetic algorithm makes a
number of trials while measuring a set of statistics.  Using these statistics
the algorithm chooses the top performers, does some mutation and mixing, and
reruns the algorithm.  In other words while undergoing a workload the system is
constantly searching for a more optimal way to manage and schedule its
resources.  This can help systems running ever larger and more complex software
make even better use of hardware resources.

For example, when this library was used to tune the constants of the Linux
Anticipatory I/O scheduler an 8% improvement under most workloads was measured
with a 23% improvement under a random write workload.

This project applies the genetic library to the CPU scheduler and currently a
prototype implementation is running under both x86 and Power.  The benchmarks
to measure the performance impact from this implementation are still under
development but will be running soon.

These changes could eventually be included in the Linux kernel and would ship
with IBM products based on a Linux platform.