archive mirror
 help / color / mirror / Atom feed
From: Jake Moilanen <>
Subject: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library
Date: Thu, 6 Jan 2005 10:08:44 -0600	[thread overview]
Message-ID: <20050106100844.53a762a0@localhost> (raw)

I'm pleased to announce a new in-kernel library to do kernel tuning
using a genetic algorithm.  

This library provides hooks for kernel components to take advantage of a
genetic algorithm.  There are patches to hook the different schedulers

The basic flow of the genetic algorithm is as follows:

1.) Start w/ a broad list of initial tunable values (each set of
	tunables is called a child) 
2.) Let each child run for a timeslice. 
3.) Once the timeslice is up, calculate the fitness of the child (how
well performed).
4.) Run the next child in the list.
5.) Once all the children have run, compare the fitnesses of each child
	and throw away the bottom-half performers. 
6.) Create new children to take the place of the bottom-half performers
	using the tunables from the top-half performers.
7.) Mutate a set number of children to keep variance.
8.) Goto step 2.

Over time the tunables should converge toward the optimal settings for
that workload.  If the workload changes, the tunables should converge to
the new optimal settings (this is part of the reason for mutation). 
This algorithm is used extensively in AI.

Using these patches, there are small gains (1-3%) in Unixbench &
SpecJBB.  I am hoping a scheduler guru will able to rework them to give
higher gains.

The main area that could use reworking is the fitness calculation.  The
problem is that the kernel is looking more at the micro of what's going
on, instead of the macro.  I am thinking of moving the fitness
calculation to outside the kernel.

However, I would advocate keeping the number of layers needed to communicate
between the genetic library and the hooked component down in order to
keep it as lightweight as possible.

The patches are based on 2.6.9 and still a little rough, but here is the

[1/4 genetic-lib]: This is the base patch for the genetic algorithm. 
	It's based against 2.6.9.

[2/4 genetic-io-sched]: The base patch for the IO schedulers to use the
	genetic library.

[3/4 genetic-as-sched]: A genetic-lib hooked anticipatory IO scheduler.

[4/4 genetic-zaphod-cpu-sched]: A hooked zaphod CPU scheduler.  Depends
	on the zaphod-v6 patch.

Please send comments,
Jake Moilanen

             reply	other threads:[~2005-01-06 16:12 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2005-01-06 16:08 Jake Moilanen [this message]
2005-01-06 16:14 ` [ANNOUNCE 1/4][RFC] Genetic Algorithm Library Jake Moilanen
2005-01-06 17:20   ` Cal Peake
2005-01-06 17:26     ` Cal Peake
2005-01-06 16:18 ` [ANNOUNCE 2/4][RFC] " Jake Moilanen
2005-01-06 16:22 ` [ANNOUNCE 3/4][RFC] " Jake Moilanen
2005-01-06 16:27 ` [ANNOUNCE 4/4][RFC] " Jake Moilanen
2005-01-08 14:05 ` [ANNOUNCE 0/4][RFC] " James Bruce
2005-01-08 14:19   ` James Bruce
2005-01-08 22:56     ` Jake Moilanen
2005-01-08 15:37 ` Pedro Larroy
2005-01-10 15:54   ` Jake Moilanen

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20050106100844.53a762a0@localhost \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).