[ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

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
included.

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
descriptions:

[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

[ANNOUNCE 1/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

Here is the base patch for the genetic-library.

It includes generic routines for modifying and manipulating genes of
children.  If a specific routine is needed, that can be used instead.


Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>

---


diff -puN fs/proc/proc_misc.c~genetic-lib fs/proc/proc_misc.c
--- linux-2.6.9/fs/proc/proc_misc.c~genetic-lib	Wed Jan  5 15:45:54 2005
+++ linux-2.6.9-moilanen/fs/proc/proc_misc.c	Wed Jan  5 15:45:54 2005
@@ -45,6 +45,7 @@
 #include <linux/sysrq.h>
 #include <linux/vmalloc.h>
 #include <linux/sched_cpustats.h>
+#include <linux/genetic.h>
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 #include <asm/io.h>
@@ -233,6 +234,35 @@ static int meminfo_read_proc(char *page,
 	return proc_calc_metrics(page, start, off, count, eof, len);
 #undef K
 }
+
+#ifdef CONFIG_GENETIC_LIB
+extern struct proc_dir_entry * genetic_root_dir;
+
+int genetic_read_proc(char *page, char **start, off_t off,
+			  int count, int *eof, void *data)
+{
+    int i;
+    int n = 0;
+    genetic_t * genetic = (genetic_t *)data;
+    
+    n  = sprintf(page,   "generation_number:\t%ld\n", genetic->generation_number);
+    n += sprintf(page+n, "num_children:\t\t%ld\n", genetic->num_children);
+    n += sprintf(page+n, "child_number:\t\t%ld\n", genetic->child_number);
+    n += sprintf(page+n, "num_mutations:\t\t%ld\n", genetic->num_mutations);
+    n += sprintf(page+n, "avg_fitness:\t\t%ld\n", genetic->avg_fitness);
+    n += sprintf(page+n, "last_gen_avg_fitness:\t%ld\n", genetic->last_gen_avg_fitness);
+
+    n += sprintf(page+n, "\nFitness history\n");
+
+    for (i = genetic->generation_number > GENETIC_HISTORY_SIZE ? GENETIC_HISTORY_SIZE
+	     : genetic->generation_number-1; i > 0; i--)
+	n += sprintf(page+n, "generation(%ld):\t%ld\n",
+		     genetic->generation_number - i,
+		     genetic->fitness_history[(genetic->fitness_history_index - i) & GENETIC_HISTORY_MASK]);
+
+    return proc_calc_metrics(page, start, off, count, eof, n);
+}
+#endif
 
 extern struct seq_operations fragmentation_op;
 static int fragmentation_open(struct inode *inode, struct file *file)
diff -puN /dev/null include/linux/genetic.h
--- /dev/null	Fri Mar 14 06:52:15 2003
+++ linux-2.6.9-moilanen/include/linux/genetic.h	Wed Jan  5 15:45:54 2005
@@ -0,0 +1,103 @@
+#ifndef __LINUX_GENETIC_H
+#define __LINUX_GENETIC_H
+/*
+ * include/linux/genetic.h
+ *
+ * Jake Moilanen <moilanen@austin.ibm.com>
+ * Copyright (C) 2004 IBM
+ *
+ * Genetic algorithm library
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <linux/list.h>
+#include <linux/timer.h>
+#include <linux/init.h>
+
+#define GENETIC_DEFAULT_NUM_MUTATIONS 	8
+#define GENETIC_HISTORY_SIZE		0x10
+#define GENETIC_HISTORY_MASK		(GENETIC_HISTORY_SIZE - 1)
+
+#define GENETIC_DEBUG			0
+
+#define gen_dbg(format, arg...) do { if (GENETIC_DEBUG) printk(KERN_EMERG __FILE__ ": " format "\n" , ## arg); } while (0)
+#define gen_trc(format, arg...) do { if (GENETIC_DEBUG) printk(KERN_EMERG __FILE__ ":%s:%d\n" , __FUNCTION__, __LINE__); } while (0)
+
+struct gene_param_s;
+
+struct genetic_child_s {
+	struct list_head 	child;
+	long			fitness;
+	unsigned long		num_genes;
+	void			*genes;
+	struct gene_param_s	*gene_param;
+	void			*stats_snapshot;
+};
+
+typedef struct genetic_child_s genetic_child_t;
+
+/* Here's a generic idea of what it the genes could look like */
+struct gene_param_s {
+	unsigned long	min;
+	unsigned long	max;
+	unsigned long	initial;
+	void	 	(*mutate_gene)(genetic_child_t *, unsigned long);
+};
+
+typedef struct gene_param_s gene_param_t;
+
+struct genetic_s {
+    struct list_head	children_queue[2];
+    struct list_head	*run_queue;
+    struct list_head	*finished_queue;
+    unsigned long	child_life_time;
+    unsigned long 	num_children;		/* Must be power of 2 */
+    unsigned long	natural_selection_cutoff; /* How many children
+						   * will survive
+						   */
+    unsigned long 	num_mutations;
+    
+    void 		(*natural_selection)(struct genetic_s *);
+    
+    char 		*name;
+    struct timer_list	timer;
+    struct genetic_ops	*ops;
+
+    genetic_child_t 	**child_ranking;
+
+    /* performance metrics */
+    long		avg_fitness;
+    long		last_gen_avg_fitness;
+
+    unsigned long	generation_number;
+    unsigned long	child_number;
+
+    unsigned long	fitness_history_index;
+    long		fitness_history[GENETIC_HISTORY_SIZE];
+
+};
+
+typedef struct genetic_s genetic_t;
+
+struct genetic_ops {
+    void		(*create_child)(genetic_child_t *);
+    void		(*set_child_genes)(void *);
+    void		(*calc_fitness)(genetic_child_t *);
+    void 		(*combine_genes)(genetic_child_t *, genetic_child_t *,
+					 genetic_child_t *, genetic_child_t *);
+    void		(*mutate_child)(genetic_child_t *);
+};
+
+extern int __init genetic_init(genetic_t * genetic, struct genetic_ops * ops, unsigned long num_children, unsigned long child_life_time, char * name);
+extern void genetic_generic_mutate_child(genetic_child_t * child);
+extern void genetic_generic_combine_genes(genetic_child_t * parent_a,
+					  genetic_child_t * parent_b,
+					  genetic_child_t * child_a,
+					  genetic_child_t * child_b);
+
+
+#endif
diff -puN lib/Kconfig~genetic-lib lib/Kconfig
--- linux-2.6.9/lib/Kconfig~genetic-lib	Wed Jan  5 15:45:54 2005
+++ linux-2.6.9-moilanen/lib/Kconfig	Wed Jan  5 15:45:54 2005
@@ -30,6 +30,12 @@ config LIBCRC32C
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
+config GENETIC_LIB
+	bool "Genetic Library"
+	help
+	  This option will build in a genetic library that will tweak
+	  kernel parameters autonomically to improve performance.
+
 #
 # compression support is select'ed if needed
 #
diff -puN lib/Makefile~genetic-lib lib/Makefile
--- linux-2.6.9/lib/Makefile~genetic-lib	Wed Jan  5 15:45:54 2005
+++ linux-2.6.9-moilanen/lib/Makefile	Wed Jan  5 15:45:54 2005
@@ -18,6 +18,7 @@ endif
 obj-$(CONFIG_CRC_CCITT)	+= crc-ccitt.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
+obj-$(CONFIG_GENETIC_LIB) += genetic.o
 obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff -puN /dev/null lib/genetic.c
--- /dev/null	Fri Mar 14 06:52:15 2003
+++ linux-2.6.9-moilanen/lib/genetic.c	Wed Jan  5 15:45:54 2005
@@ -0,0 +1,429 @@
+/*
+ * Genetic Algorithm Library
+ *
+ * Jake Moilanen <moilanen@austin.ibm.com>
+ * Copyright (C) 2004 IBM
+ *
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+/*
+ * Life cycle
+ * 
+ * 1.) Create random children
+ * 2.) Run tests
+ * 3.) Calculate fitness
+ * 4.) Take top preformers
+ * 5.) Make children
+ * 6.) Mutate
+ * 7.) Goto step 2
+ */
+
+#include <linux/genetic.h>
+#include <linux/timer.h>
+#include <linux/jiffies.h>
+#include <linux/proc_fs.h>
+#include <linux/init.h>
+#include <linux/random.h>
+
+#include <asm/uaccess.h>
+#include <asm/string.h>
+#include <asm/bug.h>
+
+static void genetic_ns_top_parents(genetic_t * genetic);
+static void genetic_ns_award_top_parents(genetic_t * genetic);
+static void genetic_create_children(genetic_t * genetic);
+static void genetic_split_performers(genetic_t * genetic);
+static void genetic_mutate(genetic_t * genetic);
+static void genetic_run_child(genetic_t * genetic);
+static void genetic_new_generation(genetic_t * genetic);
+
+void genetic_switch_child(unsigned long data);
+struct proc_dir_entry * genetic_root_dir = 0;
+extern int genetic_read_proc(char *page, char **start, off_t off,
+		      int count, int *eof, void *data);
+
+int __init genetic_init(genetic_t * genetic, struct genetic_ops * ops,
+			unsigned long num_children, unsigned long child_life_time,
+			char * name)
+{
+    struct proc_dir_entry *entry;
+	    
+    genetic = (genetic_t *)kmalloc(sizeof(genetic_t), GFP_KERNEL);
+    if (!genetic) {
+	printk(KERN_ERR "genetic_init: not enough memory\n");
+	return -ENOMEM;
+    }
+
+    genetic->name = (char *)kmalloc(strlen(name), GFP_KERNEL);
+    if (!genetic->name) {
+	kfree(genetic);
+	return -ENOMEM;
+    }
+
+    genetic->child_ranking = (genetic_child_t **)kmalloc(num_children * sizeof(genetic_child_t *), GFP_KERNEL);
+    if (!genetic->child_ranking) {
+	kfree(genetic->name);
+	kfree(genetic);
+	return -ENOMEM;
+    }
+
+    /* Init some of our values */
+    strcpy(genetic->name, name);
+
+    INIT_LIST_HEAD(&genetic->children_queue[0]);
+    INIT_LIST_HEAD(&genetic->children_queue[1]);
+
+    genetic->run_queue = &genetic->children_queue[0];
+    genetic->finished_queue = &genetic->children_queue[1];    
+
+    genetic->ops = ops;
+    genetic->num_children = num_children;
+    genetic->child_life_time = child_life_time;
+
+    genetic->generation_number = 1;
+    genetic->child_number = 0;
+    genetic->num_mutations = GENETIC_DEFAULT_NUM_MUTATIONS;
+    genetic->natural_selection = genetic_ns_top_parents;
+    genetic->natural_selection_cutoff = num_children / 2;
+    genetic->avg_fitness = 0;
+    genetic->last_gen_avg_fitness = 0;    
+    
+    /* Create some children */
+    genetic_create_children(genetic);
+
+    /* Setup how long each child has to live */
+    init_timer(&genetic->timer);
+    genetic->timer.function = genetic_switch_child;
+    genetic->timer.data = (unsigned long)genetic;
+
+#ifdef CONFIG_PROC_FS
+
+    /* Setup proc structure to monitor */
+    if (!genetic_root_dir)
+	genetic_root_dir = proc_mkdir("genetic", 0);
+
+    entry = create_proc_entry(name, 0644, genetic_root_dir);
+
+    if (entry) {
+	entry->nlink = 1;
+	entry->data = genetic;
+	entry->read_proc = genetic_read_proc;
+    }
+#endif    
+
+    genetic_run_child(genetic);
+
+    printk(KERN_INFO "%ld children started in %s genetic library\n", num_children, name);
+
+    return 0;
+}
+
+/* create some children, it is up to the lib user to come up w/ a good
+   distro of genes for it's children */
+static void genetic_create_children(genetic_t * genetic)
+{
+    unsigned long i;
+    genetic_child_t * child;
+
+    for (i = 0; i < genetic->num_children; i++) {
+	genetic->child_ranking[i] = (genetic_child_t *)kmalloc(sizeof(genetic_child_t), GFP_KERNEL);
+	child = genetic->child_ranking[i];
+
+	genetic->ops->create_child(child);
+
+	list_add_tail(&child->child, genetic->run_queue->next);
+    }
+}
+
+/* See how well child did and run the next one */
+void genetic_switch_child(unsigned long data)
+{
+    genetic_t * genetic = (genetic_t *)data;
+    genetic_child_t * child;
+
+    child = list_entry(genetic->run_queue->next, genetic_child_t, child);
+
+    list_del(&child->child);
+
+    list_add_tail(&child->child, genetic->finished_queue->next);
+
+    genetic->ops->calc_fitness(child);
+
+    genetic->child_ranking[genetic->child_number++] = child;
+
+    /* See if need more children */
+    if (list_empty(genetic->run_queue->next)) 
+	genetic_new_generation(genetic);
+
+    genetic_run_child(genetic);
+}
+
+/* Set the childs genes for run */
+void genetic_run_child(genetic_t * genetic)
+{
+    genetic_child_t * child = list_entry(genetic->run_queue->next, genetic_child_t, child);
+    void * genes = child->genes;
+
+    BUG_ON(!genes);
+
+    genetic->ops->set_child_genes(genes);
+
+    /* set a timer interrupt */
+    genetic->timer.expires = jiffies + genetic->child_life_time;
+    add_timer(&genetic->timer);
+
+}
+
+/* This natural selection routine will take the top
+ * natural_select_cutoff and use them to make children for the next
+ * generation and keep the top half perfomers
+ *
+ * This assumes natural_select_cutoff is exactly half of num_children
+ * and num_children is a multable of 4.
+ */
+static void genetic_ns_top_parents(genetic_t * genetic)
+{
+    unsigned long i,j,k = 0;
+    unsigned long num_children = genetic->num_children;
+    unsigned long cutoff = num_children - genetic->natural_selection_cutoff;
+
+    for (i = cutoff, j = num_children - 1; i < j; i++, j--, k += 2) {
+	genetic->ops->combine_genes(genetic->child_ranking[i],
+				    genetic->child_ranking[j],
+				    genetic->child_ranking[k],
+				    genetic->child_ranking[k+1]);
+    }
+}
+
+static void genetic_ns_clone_top_parents(genetic_t * genetic)
+{
+    unsigned long i,j,k = 0;
+    unsigned long num_children = genetic->num_children;
+    unsigned long cutoff = num_children - genetic->natural_selection_cutoff;
+
+    for (i = cutoff, j = num_children - 1; i < j; i++, j--, k += 2) {
+	genetic->ops->combine_genes(genetic->child_ranking[i],
+				    genetic->child_ranking[j],
+				    genetic->child_ranking[k],
+				    genetic->child_ranking[k+1]);
+    }
+}
+
+/* This natural selection routine just has top parents populating
+   bottom performers. */
+static void genetic_ns_award_top_parents(genetic_t * genetic)
+{
+	unsigned long i;
+	unsigned long num_children = genetic->num_children;
+	unsigned long cutoff = num_children - genetic->natural_selection_cutoff;
+	
+	for (i = 0; i < cutoff; i += 2) {
+		genetic->ops->combine_genes(genetic->child_ranking[num_children - 1],
+					    genetic->child_ranking[num_children - 2],
+					    genetic->child_ranking[i],
+					    genetic->child_ranking[i+1]);
+	}
+}
+
+
+static inline void genetic_swap(genetic_child_t ** a, genetic_child_t ** b)
+{
+    genetic_child_t * tmp = *a;
+
+    *a = *b;
+    *b = tmp;
+}
+
+/* bubble sort */
+/* XXX change this to quick sort */
+static void genetic_split_performers(genetic_t * genetic)
+{
+    int i, j;
+
+    for (i = genetic->num_children; i > 1; i--)
+	for (j = 0; j < i - 1; j++)
+	    if (genetic->child_ranking[j]->fitness > genetic->child_ranking[j+1]->fitness) 
+		genetic_swap(&genetic->child_ranking[j], &genetic->child_ranking[j+1]);
+}
+
+static void genetic_mutate(genetic_t * genetic)
+{
+    long child_entry = -1;
+    int i;
+
+    for (i = 0; i < genetic->num_mutations; i++) {
+	get_random_bytes(&child_entry, sizeof(child_entry));
+	child_entry = child_entry % genetic->num_children;
+
+	genetic->ops->mutate_child(genetic->child_ranking[child_entry]);
+    }
+}
+
+static void genetic_calc_stats(genetic_t * genetic)
+{
+    long total_fitness = 0;
+    int i;
+
+    /* calculate the avg fitness for this generation and avg fitness
+     * so far */
+    for (i = 0; i < genetic->num_children; i++) 
+	total_fitness += genetic->child_ranking[i]->fitness;
+
+    genetic->last_gen_avg_fitness = total_fitness / (long)genetic->num_children;
+
+    genetic->avg_fitness = ((genetic->avg_fitness * (long)(genetic->generation_number - 1)) +
+			    genetic->last_gen_avg_fitness) / (long)genetic->generation_number;
+
+    genetic->fitness_history[genetic->fitness_history_index++ & GENETIC_HISTORY_MASK] =
+	genetic->last_gen_avg_fitness;
+
+}    
+
+void dump_children(genetic_t * genetic)
+{
+	int i, j;
+	long * genes;
+	for (i = 0; i < genetic->num_children; i++) {
+		printk(KERN_EMERG "%d: %-8ld:\t", i, genetic->child_ranking[i]->fitness); 
+
+		for (j = 0; j < genetic->child_ranking[i]->num_genes; j++) {
+			genes = (long *)genetic->child_ranking[i]->genes;
+			printk("%ld\t", genes[j]);
+		}
+		printk("\n");
+	}
+
+	printk("\n");
+}
+
+void genetic_new_generation(genetic_t * genetic)
+{
+    struct list_head * tmp;
+
+#if GENETIC_DEBUG
+    printk(KERN_EMERG "-------------------------\n");
+    printk(KERN_EMERG "new generation performers: \n");
+    dump_children(genetic);
+#endif
+    
+    /* figure out top performers */
+    genetic_split_performers(genetic);
+
+#if GENETIC_DEBUG
+    printk(KERN_EMERG "split performers: \n");
+    dump_children(genetic);
+#endif
+    
+    /* calc stats */
+    genetic_calc_stats(genetic);
+
+    /* make some new children */
+    genetic->natural_selection(genetic);
+
+#if GENETIC_DEBUG
+    printk(KERN_EMERG "selected: \n");
+    dump_children(genetic);
+#endif
+
+    /* mutate a couple of the next generation */
+    genetic_mutate(genetic);
+
+#if GENETIC_DEBUG
+    printk(KERN_EMERG "mutated: \n");
+    dump_children(genetic);
+#endif
+
+    /* Move the new children still sitting in the finished queue to
+       the run queue */
+    tmp = genetic->run_queue;
+    genetic->run_queue = genetic->finished_queue;
+    genetic->finished_queue = tmp;
+
+    genetic->child_number = 0;
+    genetic->generation_number++;
+
+}
+
+void genetic_generic_mutate_gene(genetic_child_t * child, long gene_num)
+{
+	unsigned long *genes = (unsigned long *)child->genes;
+	unsigned long min = child->gene_param[gene_num].min;
+	unsigned long max = child->gene_param[gene_num].max;
+	unsigned long gene_value;
+	unsigned long range = max - min + 1;
+
+    	/* create a mutation value */
+	get_random_bytes(&gene_value, sizeof(gene_value));
+
+#if 0
+	/* XXX we shouldn't need this now that it's unsigned */
+	if (gene_value < 0)
+	    gene_value = -gene_value;
+#endif
+
+	gene_value = gene_value % range;
+	
+	genes[gene_num] = min + gene_value;
+}
+
+/* This assumes that all genes are a unsigned long array of size
+   num_genes */
+void genetic_generic_mutate_child(genetic_child_t * child)
+{
+	long gene_num = -1;
+
+	/* pick a random gene */
+	get_random_bytes(&gene_num, sizeof(gene_num));
+
+	if (gene_num < 0)
+	    gene_num = -gene_num;
+
+	gene_num = gene_num % child->num_genes;
+
+	if (child->gene_param[gene_num].mutate_gene)
+		child->gene_param[gene_num].mutate_gene(child, gene_num);
+	else 
+		genetic_generic_mutate_gene(child, gene_num);
+}
+
+
+/* combine the genes by randomly take a portion of A's and B's to make
+ * C.  Then flip that portion of B and A to make D */
+void genetic_generic_combine_genes(genetic_child_t * parent_a,
+				   genetic_child_t * parent_b,
+				   genetic_child_t * child_a,
+				   genetic_child_t * child_b)
+{
+	unsigned long * genes_a = (unsigned long *)parent_a->genes;
+	unsigned long * genes_b = (unsigned long *)parent_b->genes;
+	unsigned long * genes_c = (unsigned long *)child_a->genes;
+	unsigned long * genes_d = (unsigned long *)child_b->genes;	
+	/* Assume parent_a and parent_b have same num_genes */
+	unsigned long num_genes = parent_a->num_genes;
+	int combine_point;
+	int i;
+
+	get_random_bytes(&combine_point, sizeof(combine_point));
+
+	if (combine_point < 0)
+	    combine_point = -combine_point;
+
+	combine_point = combine_point % num_genes;
+
+	for (i = combine_point; i < num_genes; i++)
+	    genes_c[i] = genes_a[i];
+
+	for (i = 0; i < combine_point; i++)
+	    genes_c[i] = genes_b[i];
+
+	for (i = combine_point; i < num_genes; i++)
+	    genes_d[i] = genes_b[i];
+
+	for (i = 0; i < combine_point; i++)
+	    genes_d[i] = genes_a[i];
+}

_

[ANNOUNCE 2/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

This is the base patch for the io-schedulers.  

It contains the fitness routine, disk_calc_fitness(), that could use a
rework. 

Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>

---


diff -puN drivers/block/genhd.c~genetic-io-sched drivers/block/genhd.c
--- linux-2.6.9/drivers/block/genhd.c~genetic-io-sched	Wed Jan  5 15:45:57 2005
+++ linux-2.6.9-moilanen/drivers/block/genhd.c	Wed Jan  5 15:45:57 2005
@@ -32,6 +32,8 @@ static struct blk_major_name {
 
 static spinlock_t major_names_lock = SPIN_LOCK_UNLOCKED;
 
+LIST_HEAD(gendisks);
+
 /* index in the above - for now: assume no multimajor ranges */
 static inline int major_to_index(int major)
 {
@@ -556,6 +558,7 @@ struct gendisk *alloc_disk(int minors)
 		kobj_set_kset_s(disk,block_subsys);
 		kobject_init(&disk->kobj);
 		rand_initialize_disk(disk);
+		list_add_tail(&disk->gendisks, &gendisks);
 	}
 	return disk;
 }
diff -puN drivers/block/ll_rw_blk.c~genetic-io-sched drivers/block/ll_rw_blk.c
--- linux-2.6.9/drivers/block/ll_rw_blk.c~genetic-io-sched	Wed Jan  5 15:45:57 2005
+++ linux-2.6.9-moilanen/drivers/block/ll_rw_blk.c	Wed Jan  5 15:45:57 2005
@@ -28,6 +28,7 @@
 #include <linux/slab.h>
 #include <linux/swap.h>
 #include <linux/writeback.h>
+#include <linux/genetic.h>
 
 /*
  * for max sense size
@@ -2115,6 +2116,81 @@ static inline void add_request(request_q
 	__elv_add_request(q, req, ELEVATOR_INSERT_SORT, 0);
 }
  
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+extern struct list_head gendisks;
+
+void disk_stats_snapshot(void)
+{
+	struct list_head * d;
+	struct gendisk *disk;
+    
+	list_for_each(d, &gendisks) {
+	    disk = list_entry(d, struct gendisk, gendisks);
+
+	    disk_round_stats(disk);
+
+	    disk->reads_snap = disk_stat_read(disk, reads);
+	    disk->writes_snap = disk_stat_read(disk, writes);
+	    disk->read_sectors_snap = disk_stat_read(disk, read_sectors);
+	    disk->write_sectors_snap = disk_stat_read(disk, write_sectors);
+	    disk->time_in_queue_snap = disk_stat_read(disk, time_in_queue);
+	}
+}
+
+/* XXX is this the best method to calc fitness */
+unsigned long disk_calc_fitness(void)
+{
+	struct list_head * d;
+	struct gendisk *disk;
+	unsigned long reads, writes, time_in_queue;
+	unsigned long read_sectors, write_sectors;
+	unsigned long disk_fitness;
+	unsigned long total_fitness = 0;
+    
+	list_for_each(d, &gendisks) {
+	    disk = list_entry(d, struct gendisk, gendisks);
+
+	    disk_round_stats(disk);
+	    
+	    reads = disk_stat_read(disk, reads) - disk->reads_snap;
+	    writes = disk_stat_read(disk, writes) - disk->writes_snap;
+
+	    read_sectors = disk_stat_read(disk, read_sectors) - disk->read_sectors_snap;
+	    write_sectors = disk_stat_read(disk, write_sectors) - disk->write_sectors_snap;
+
+	    time_in_queue = disk_stat_read(disk, time_in_queue)	- disk->time_in_queue_snap;
+
+	    /* Various attempts at collecting good fitness */
+#if 0
+	    if (time_in_queue)
+		disk_fitness = ((reads + writes) 2 * HZ) / time_in_queue;
+	    else
+		disk_fitness = 0;
+
+#endif
+
+#if 1
+	    if (time_in_queue)
+		disk_fitness = ((read_sectors + write_sectors) * 2 * HZ) / time_in_queue;
+	    else
+		disk_fitness = 0;
+#endif
+
+#if 0
+	    disk_fitness = reads + writes;
+#endif
+
+#if 0
+	    disk_fitness = read_sectors + write_sectors;
+#endif
+	    
+	    total_fitness += disk_fitness;
+	}
+
+	return total_fitness;
+}
+#endif
+
 /*
  * disk_round_stats()	- Round off the performance stats on a struct
  * disk_stats.
@@ -2137,7 +2213,6 @@ void disk_round_stats(struct gendisk *di
 	disk_stat_add(disk, time_in_queue, 
 			disk->in_flight * (now - disk->stamp));
 	disk->stamp = now;
-
 	if (disk->in_flight)
 		disk_stat_add(disk, io_ticks, (now - disk->stamp_idle));
 	disk->stamp_idle = now;
diff -puN include/linux/genhd.h~genetic-io-sched include/linux/genhd.h
--- linux-2.6.9/include/linux/genhd.h~genetic-io-sched	Wed Jan  5 15:45:57 2005
+++ linux-2.6.9-moilanen/include/linux/genhd.h	Wed Jan  5 15:45:57 2005
@@ -120,11 +120,20 @@ struct gendisk {
 	atomic_t sync_io;		/* RAID */
 	unsigned long stamp, stamp_idle;
 	int in_flight;
+	struct list_head gendisks;
 #ifdef	CONFIG_SMP
 	struct disk_stats *dkstats;
 #else
 	struct disk_stats dkstats;
 #endif
+#ifdef CONFIG_GENETIC_LIB
+	unsigned reads_snap;
+	unsigned writes_snap;
+	unsigned read_sectors_snap;
+	unsigned write_sectors_snap;
+	unsigned time_in_queue_snap;
+#endif	
+
 };
 
 /* 

_

[ANNOUNCE 3/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

This is the hooked anticipatory IO scheduler.  

Here is an example of the hooked scheduler.  It should optimally tweak
the tunables for the current workload.

If nothing else, hopefully the genetic-lib will help scheduler writers
find the optimal tunable settings.

Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>

---


diff -puN drivers/block/Kconfig.iosched~genetic-as-sched drivers/block/Kconfig.iosched
--- linux-2.6.9/drivers/block/Kconfig.iosched~genetic-as-sched	Wed Jan  5 15:46:07 2005
+++ linux-2.6.9-moilanen/drivers/block/Kconfig.iosched	Wed Jan  5 15:46:07 2005
@@ -34,3 +34,12 @@ config IOSCHED_CFQ
 	  The CFQ I/O scheduler tries to distribute bandwidth equally
 	  among all processes in the system. It should provide a fair
 	  working environment, suitable for desktop systems.
+
+config GENETIC_IOSCHED_AS
+       bool "Genetic Anticipatory I/O scheduler (EXPERIMENTAL)" 
+       depends on IOSCHED_AS && GENETIC_LIB && EXPERIMENTAL
+       default n
+       ---help---
+       This will use a genetic algorithm to tweak the tunables of the
+       anticipatory scheduler autonomically and will adapt tunables
+       depending on the present workload.  
diff -puN drivers/block/as-iosched.c~genetic-as-sched drivers/block/as-iosched.c
--- linux-2.6.9/drivers/block/as-iosched.c~genetic-as-sched	Wed Jan  5 15:46:07 2005
+++ linux-2.6.9-moilanen/drivers/block/as-iosched.c	Wed Jan  5 15:46:07 2005
@@ -20,6 +20,8 @@
 #include <linux/hash.h>
 #include <linux/rbtree.h>
 #include <linux/interrupt.h>
+#include <linux/genetic.h>
+#include <linux/random.h>
 
 #define REQ_SYNC	1
 #define REQ_ASYNC	0
@@ -67,6 +69,8 @@
  */
 #define MAX_THINKTIME (HZ/50UL)
 
+unsigned long max_thinktime = MAX_THINKTIME;
+
 /* Bits in as_io_context.state */
 enum as_io_states {
 	AS_TASK_RUNNING=0,	/* Process has not exitted */
@@ -83,6 +87,47 @@ enum anticipation_status {
 				 * or timed out */
 };
 
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+
+static void as_create_child(genetic_child_t * child);
+static void as_set_child_genes(void * in_genes);
+static void as_calc_fitness(genetic_child_t * child);
+
+struct genetic_ops as_genetic_ops = {
+    .create_child = as_create_child,
+    .set_child_genes = as_set_child_genes,
+    .calc_fitness = as_calc_fitness,
+    .combine_genes = genetic_generic_combine_genes,
+    .mutate_child = genetic_generic_mutate_child,
+};
+
+#define AS_NUM_GENES 6
+#define AS_NUM_CHILDREN 8
+
+struct as_genes {
+    unsigned long read_expire;
+    unsigned long write_expire;
+    unsigned long read_batch_expire;
+    unsigned long write_batch_expire;
+    unsigned long antic_expire;
+    unsigned long max_thinktime;
+};
+
+gene_param_t as_gene_param[AS_NUM_GENES] = {
+	{ HZ/16, 3*HZ/16, default_read_expire, 0},	/* read_expire */
+	{ HZ/8, 3*HZ/8, default_write_expire, 0},    	/* write_expire */
+	{ HZ/16, 3*HZ/16, default_write_batch_expire, 0},/* write_batch_expire */
+	{ HZ/4, 3*HZ/4, default_read_batch_expire, 0},	/* read_batch_expire */
+	{ HZ/300, HZ/100, default_antic_expire, 0},	/* default_antic_expire */
+	{ HZ/100, 3*HZ/100, MAX_THINKTIME, 0}
+};
+
+extern void disk_stats_snapshot(void);
+extern unsigned long disk_calc_fitness(void);
+
+LIST_HEAD(as_data_list);
+#endif
+
 struct as_data {
 	/*
 	 * run time data
@@ -132,6 +177,9 @@ struct as_data {
 	unsigned long fifo_expire[2];
 	unsigned long batch_expire[2];
 	unsigned long antic_expire;
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+        struct list_head data_list;
+#endif
 };
 
 #define list_entry_fifo(ptr)	list_entry((ptr), struct as_rq, fifo)
@@ -869,7 +917,7 @@ static void as_update_iohist(struct as_d
 			if (test_bit(AS_TASK_IORUNNING, &aic->state)
 							&& in_flight == 0) {
 				thinktime = jiffies - aic->last_end_request;
-				thinktime = min(thinktime, MAX_THINKTIME-1);
+				thinktime = min(thinktime, max_thinktime-1);
 			} else
 				thinktime = 0;
 			as_update_thinktime(ad, aic, thinktime);
@@ -1854,6 +1902,11 @@ static void as_exit(request_queue_t *q, 
 
 	mempool_destroy(ad->arq_pool);
 	put_io_context(ad->io_context);
+
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+	list_del(&ad->data_list);
+#endif
+
 	kfree(ad->hash);
 	kfree(ad);
 }
@@ -1916,6 +1969,10 @@ static int as_init(request_queue_t *q, e
 	if (ad->write_batch_count < 2)
 		ad->write_batch_count = 2;
 
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+	list_add_tail(&ad->data_list, &as_data_list);
+#endif
+
 	return 0;
 }
 
@@ -2072,12 +2129,20 @@ static struct kobj_type as_ktype = {
 
 static int __init as_slab_setup(void)
 {
+	int rc;
+    
 	arq_pool = kmem_cache_create("as_arq", sizeof(struct as_rq),
 				     0, 0, NULL, NULL);
 
 	if (!arq_pool)
 		panic("as: can't init slab pool\n");
 
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+	rc = genetic_init(0, &as_genetic_ops, AS_NUM_CHILDREN, 2 * HZ, "as-ioscheduler");
+	if (rc)
+	    panic("as: failed to init genetic lib");
+#endif	
+
 	return 0;
 }
 
@@ -2106,3 +2171,70 @@ elevator_t iosched_as = {
 };
 
 EXPORT_SYMBOL(iosched_as);
+
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+
+/* need to create the genes for the child */
+static void as_create_child(genetic_child_t * child)
+{
+    int i;
+    static int child_num = 0;
+    unsigned long range;
+    int range_incr;
+    unsigned long * genes;
+
+    BUG_ON(!child);
+
+    child->genes = (void *)kmalloc(sizeof(struct as_genes), GFP_KERNEL);
+    if (!child->genes) 
+	panic("as_create_child: error mallocing space");
+
+    child->gene_param = as_gene_param;
+
+    genes = (unsigned long *)child->genes;
+
+    for (i = 0; i < AS_NUM_GENES; i++) {
+	    range = child->gene_param[i].max - child->gene_param[i].min + 1;
+	    range_incr = range / AS_NUM_CHILDREN;
+	    if (range_incr)
+		    genes[i] = child->gene_param[i].min +
+			    (range_incr * child_num);
+	    else
+		    genes[i] = child->gene_param[i].min +
+			    (child_num / (AS_NUM_CHILDREN / range));
+    }
+
+    child->num_genes = AS_NUM_GENES;
+
+    child_num++;
+}
+
+static void as_set_child_genes(void * in_genes)
+{
+    struct as_genes * genes = (struct as_genes *)in_genes;
+    struct list_head * d;
+    struct as_data * ad;
+    
+    list_for_each(d, &as_data_list) {
+	ad = list_entry(d, struct as_data, data_list);
+	ad->fifo_expire[REQ_SYNC] = genes->read_expire;
+	ad->fifo_expire[REQ_ASYNC] = genes->write_expire;
+	ad->antic_expire = genes->antic_expire;
+	ad->batch_expire[REQ_SYNC] = genes->read_batch_expire;
+	ad->batch_expire[REQ_ASYNC] = genes->write_batch_expire;
+    }
+    max_thinktime = genes->max_thinktime;
+
+    /* Set a mark for the start of this child to help calculate
+       fitness */
+    disk_stats_snapshot();
+}
+
+static void as_calc_fitness(genetic_child_t * child)
+{
+	child->fitness = disk_calc_fitness();
+}
+
+#endif
+
+

_

[ANNOUNCE 4/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

The hooked zaphod CPU scheduler patch.  

It depends on the zaphod-v6 patch.  

The ranges for the tunables could be tweaked better.

Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>

---


diff -puN kernel/sched_zaphod.c~genetic-zaphod-cpu-sched kernel/sched_zaphod.c
--- linux-2.6.9/kernel/sched_zaphod.c~genetic-zaphod-cpu-sched	Wed Jan  5 15:46:00 2005
+++ linux-2.6.9-moilanen/kernel/sched_zaphod.c	Wed Jan  5 15:46:00 2005
@@ -21,15 +21,12 @@
  */
 #include <linux/sched.h>
 #include <linux/proc_fs.h>
+#include <linux/genetic.h>
+#include <linux/random.h>
 
 #include <asm/uaccess.h>
 
-enum zaphod_mode_enum {
-	ZAPHOD_MODE_PRIORITY_BASED,
-	ZAPHOD_MODE_ENTITLEMENT_BASED
-};
-
-static enum zaphod_mode_enum zaphod_mode = ZAPHOD_MODE_PRIORITY_BASED;
+enum zaphod_mode_enum zaphod_mode = ZAPHOD_MODE_PRIORITY_BASED;
 
 #ifdef CONFIG_SYSCTL
 static const char *zaphod_mode_names[] = {
@@ -720,3 +717,81 @@ int proc_zaphod_mode(ctl_table *ctp, int
 
 	return res;
 }
+
+#ifdef CONFIG_GENETIC_CPU_SCHED
+
+extern unsigned long sched_rr_time_slice;
+extern unsigned long base_prom_interval;
+static void zaphod_sched_create_child(genetic_child_t *);
+static void genetic_mutate_proportion(genetic_child_t *, unsigned long);
+void zaphod_sched_set_child_genes(void *);
+void zaphod_sched_calc_fitness(genetic_child_t *);
+
+struct genetic_ops zaphod_sched_genetic_ops = {
+	.create_child = zaphod_sched_create_child,
+	.set_child_genes = zaphod_sched_set_child_genes,
+	.calc_fitness = zaphod_sched_calc_fitness,
+	.combine_genes = genetic_generic_combine_genes,
+	.mutate_child = genetic_generic_mutate_child,
+};
+
+/* Each gene and their attributes */
+gene_param_t zaphod_sched_gene_param[ZAPHOD_SCHED_NUM_GENES] = {
+	{ MIN_TIMESLICE, MAX_TIMESLICE, DEF_TIMESLICE, 0 },		/* time_slice */
+	{ MIN_TIMESLICE, MAX_TIMESLICE, (100 * HZ / 1000), 0 },		/* sched_rr_time_slice */
+//	{ MIN_TIMESLICE, ULONG_MAX, ((DEF_TIMESLICE * 15) / 10), 0 },	/* base_prom_interval */
+	{ MIN_TIMESLICE, MAX_TIMESLICE, ((DEF_TIMESLICE * 15) / 10), 0 },	/* base_prom_interval */
+	{ 0, MAX_MAX_IA_BONUS, DEFAULT_MAX_IA_BONUS, 0 },		/* max_ia_bonus */
+	{ 0, MAX_MAX_IA_BONUS, 1, 0 },					/* initial_ia_bonus */
+	{ 1, 1000, DEFAULT_IA_THRESHOLD, 0 },  				/* ia_threshold */
+	{ 1, 1000, DEFAULT_CPU_HOG_THRESHOLD, 0 }, 			/* cpu_hog_threshold */
+	{ 0, MAX_MAX_TPT_BONUS, DEFAULT_MAX_TPT_BONUS, 0 },		/* max_tpt_bonus */
+	{ 1, 1000, DEFAULT_UNPRIV_RT_THRESHOLD, 0 }, 			/* unpriv_rt_threshold */
+	{ 1, 100, 1, 0 }, 						/* bgnd_time_slice_multiplier */
+	{ 0, 1, 0, 0 },							/* zaphod_mode */
+};
+
+void __init genetic_cpu_sched_init()
+{
+	if(genetic_init(0, &zaphod_sched_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+			ZAPHOD_SCHED_CHILD_LIFESPAN, "zaphod-sched"))
+		panic("zaphod sched: failed to init genetic lib");
+}
+
+void zaphod_sched_create_child(genetic_child_t * child)
+{
+	int i;
+	static int child_num = 0;
+	unsigned long range;
+	int range_incr;
+	unsigned long * genes;
+	
+	BUG_ON(!child);
+	
+	child->genes = (void *)kmalloc(sizeof(struct zaphod_sched_genes), GFP_KERNEL);
+	if (!child->genes) 
+		panic("zaphod_sched_create_child: error kmalloc'n space");
+
+	child->gene_param = zaphod_sched_gene_param;
+
+	genes = (unsigned long *)child->genes;
+		
+	for (i = 0; i < ZAPHOD_SCHED_NUM_GENES; i++) {
+		range = child->gene_param[i].max - child->gene_param[i].min + 1;
+		range_incr = range / ZAPHOD_SCHED_NUM_CHILDREN;
+		if (range_incr)
+			genes[i] = child->gene_param[i].min +
+				(range_incr * child_num);
+		else
+			genes[i] = child->gene_param[i].min +
+				(child_num / (ZAPHOD_SCHED_NUM_CHILDREN / range));
+	}
+
+	child->num_genes = ZAPHOD_SCHED_NUM_GENES;
+	
+	child_num++;
+}
+
+core_initcall(genetic_cpu_sched_init);
+
+#endif /* CONFIG_GENETIC_CPU_SCHED */
diff -puN lib/Kconfig~genetic-zaphod-cpu-sched lib/Kconfig
--- linux-2.6.9/lib/Kconfig~genetic-zaphod-cpu-sched	Wed Jan  5 15:46:00 2005
+++ linux-2.6.9-moilanen/lib/Kconfig	Wed Jan  5 15:46:00 2005
@@ -36,6 +36,13 @@ config GENETIC_LIB
 	  This option will build in a genetic library that will tweak
 	  kernel parameters autonomically to improve performance.
 
+config GENETIC_CPU_SCHED
+	bool "Genetic Library - Zaphod CPU scheduler"
+	depends on GENETIC_LIB && EXPERIMENTAL && SCHEDSTATS
+	help
+	  This option will enable the genetic library on the zaphod
+	  CPU scheduler.
+
 #
 # compression support is select'ed if needed
 #
diff -puN kernel/sched.c~genetic-zaphod-cpu-sched kernel/sched.c
--- linux-2.6.9/kernel/sched.c~genetic-zaphod-cpu-sched	Wed Jan  5 15:46:00 2005
+++ linux-2.6.9-moilanen/kernel/sched.c	Wed Jan  5 15:46:00 2005
@@ -43,6 +43,7 @@
 #include <linux/kthread.h>
 #include <linux/seq_file.h>
 #include <linux/times.h>
+#include <linux/genetic.h>
 #include <asm/tlb.h>
 
 #include <asm/unistd.h>
@@ -71,19 +72,8 @@
 #define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 / HZ))
 #define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 / HZ))
 
-/*
- * These are the 'tuning knobs' of the scheduler:
- *
- * Default configurable timeslice is 100 msecs, maximum configurable
- * timeslice is 1000 msecs and minumum configurable timeslice is 1 jiffy.
- * Timeslices get renewed on task creation, on wake up and after they expire.
- */
-#define MIN_TIMESLICE		1
-#define DEF_TIMESLICE		(100 * HZ / 1000)
-#define MAX_TIMESLICE		(1000 * HZ / 1000)
-
 unsigned long time_slice = DEF_TIMESLICE;
-static unsigned long sched_rr_time_slice = (100 * HZ / 1000);
+unsigned long sched_rr_time_slice = (100 * HZ / 1000);
 
 static unsigned long task_timeslice(const task_t *p)
 {
@@ -116,6 +106,13 @@ struct prio_slot {
 	struct list_head queue;
 };
 
+static DEFINE_PER_CPU(struct runqueue, runqueues);
+
+#define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))
+#define this_rq()		(&__get_cpu_var(runqueues))
+#define task_rq(p)		((p)->rq)
+#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)
+
 /*
  * This is the main, per-CPU runqueue data structure.
  *
@@ -199,8 +196,6 @@ struct runqueue {
 #endif
 };
 
-static DEFINE_PER_CPU(struct runqueue, runqueues);
-
 /*
  * sched-domains (multiprocessor balancing) declarations:
  */
@@ -338,11 +333,6 @@ struct sched_domain {
 #define for_each_domain(cpu, domain) \
 	for (domain = cpu_rq(cpu)->sd; domain; domain = domain->parent)
 
-#define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))
-#define this_rq()		(&__get_cpu_var(runqueues))
-#define task_rq(p)		((p)->rq)
-#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)
-
 #ifdef CONFIG_SMP
 void fastcall set_task_cpu(struct task_struct *p, unsigned int cpu)
 {
@@ -1357,7 +1347,7 @@ void fastcall wake_up_new_task(task_t * 
 /**
  * (Optionally) log scheduler statistics at exit.
  */
-static int log_at_exit = 0;
+int log_at_exit = 0;
 /*
  * No more timeslice fiddling on exit
  */
@@ -4938,3 +4928,60 @@ ctl_table cpu_sched_table[] = {
 	{ .ctl_name = CPU_SCHED_END_OF_LIST }
 };
 #endif
+
+#ifdef CONFIG_GENETIC_CPU_SCHED
+
+extern enum zaphod_mode_enum zaphod_mode;
+
+void zaphod_sched_set_child_genes(void * in_genes)
+{
+	struct zaphod_sched_genes * genes = (struct zaphod_sched_genes *)in_genes;
+	int cpu;
+	runqueue_t * rq;
+
+	time_slice = genes->time_slice;
+	sched_rr_time_slice = genes->sched_rr_time_slice;
+	base_prom_interval = genes->base_prom_interval;
+	max_ia_bonus = genes->max_ia_bonus;
+	initial_ia_bonus = genes->initial_ia_bonus;
+	ia_threshold = ppt_to_proportion(genes->ia_threshold);
+	cpu_hog_threshold = ppt_to_proportion(genes->cpu_hog_threshold);
+	max_tpt_bonus = genes->max_tpt_bonus;
+	unpriv_rt_threshold = ppt_to_proportion(genes->unpriv_rt_threshold);
+	bgnd_time_slice_multiplier = genes->bgnd_time_slice_multiplier;
+	zaphod_mode = genes->zaphod_mode;
+	
+	/* Get snapshot for this child */
+	for_each_online_cpu(cpu) {
+		rq = cpu_rq(cpu);
+
+		rq->rq_sched_info.cpu_time_snapshot = rq->rq_sched_info.cpu_time;
+		rq->rq_sched_info.run_delay_snapshot = rq->rq_sched_info.run_delay;
+		rq->rq_sched_info.pcnt_snapshot = rq->rq_sched_info.pcnt;
+	}
+}
+
+void zaphod_sched_calc_fitness(genetic_child_t * child)
+{
+	int cpu;
+	runqueue_t * rq;
+	long cpu_time = 0;
+	long run_delay = 0;
+	long pcnt = 0;
+
+	/* XXX at some point make sure onlining or offlining a CPU
+	   doesn't screw us */
+	for_each_online_cpu(cpu) {
+		rq = cpu_rq(cpu);
+
+		cpu_time += rq->rq_sched_info.cpu_time - rq->rq_sched_info.cpu_time_snapshot;
+		run_delay += rq->rq_sched_info.run_delay - rq->rq_sched_info.run_delay_snapshot;
+		pcnt += rq->rq_sched_info.pcnt - rq->rq_sched_info.pcnt_snapshot;
+	}
+
+	child->fitness = cpu_time - run_delay;
+//	child->fitness = 1 - run_delay;
+}
+
+#endif
+
diff -puN include/linux/sched.h~genetic-zaphod-cpu-sched include/linux/sched.h
--- linux-2.6.9/include/linux/sched.h~genetic-zaphod-cpu-sched	Wed Jan  5 15:46:00 2005
+++ linux-2.6.9-moilanen/include/linux/sched.h	Wed Jan  5 15:46:00 2005
@@ -138,6 +138,17 @@ struct sched_param {
 #include <linux/spinlock.h>
 
 /*
+ * These are the 'tuning knobs' of the scheduler:
+ *
+ * Default configurable timeslice is 100 msecs, maximum configurable
+ * timeslice is 1000 msecs and minumum configurable timeslice is 1 jiffy.
+ * Timeslices get renewed on task creation, on wake up and after they expire.
+ */
+#define MIN_TIMESLICE		1
+#define DEF_TIMESLICE		(100 * HZ / 1000)
+#define MAX_TIMESLICE		(1000 * HZ / 1000)
+
+/*
  * This serializes "schedule()" and also protects
  * the run-queue from deletions/modifications (but
  * _adding_ to the beginning of the run-queue has
@@ -392,6 +403,12 @@ struct sched_info {
 	/* timestamps */
 	unsigned long	last_arrival,	/* when we last ran on a cpu */
 			last_queued;	/* when we were last queued to run */
+
+#ifdef CONFIG_GENETIC_CPU_SCHED
+	unsigned long	cpu_time_snapshot;
+	unsigned long	run_delay_snapshot;
+	unsigned long	pcnt_snapshot;
+#endif	
 };
 
 extern struct file_operations proc_schedstat_operations;
@@ -657,6 +674,8 @@ extern int task_nice(const task_t *p);
 extern int task_curr(const task_t *p);
 extern int idle_cpu(int cpu);
 
+extern void genetic_cpu_sched_init(void);
+
 void yield(void);
 
 /*
@@ -1031,8 +1050,35 @@ static inline void arch_pick_mmap_layout
 }
 #endif
 
+enum zaphod_mode_enum {
+	ZAPHOD_MODE_PRIORITY_BASED,
+	ZAPHOD_MODE_ENTITLEMENT_BASED
+};
+
+#ifdef CONFIG_GENETIC_CPU_SCHED
 extern long sched_setaffinity(pid_t pid, cpumask_t new_mask);
 extern long sched_getaffinity(pid_t pid, cpumask_t *mask);
+
+
+#define ZAPHOD_SCHED_NUM_GENES 11
+#define ZAPHOD_SCHED_NUM_CHILDREN 8
+//#define ZAPHOD_SCHED_CHILD_LIFESPAN (9 * (HZ / 2))
+#define ZAPHOD_SCHED_CHILD_LIFESPAN (4 * HZ)
+
+struct zaphod_sched_genes {
+	unsigned long time_slice;
+	unsigned long sched_rr_time_slice;
+	unsigned long base_prom_interval;
+	unsigned long max_ia_bonus;
+	unsigned long initial_ia_bonus;
+	unsigned long ia_threshold;
+	unsigned long cpu_hog_threshold;
+	unsigned long max_tpt_bonus;
+	unsigned long unpriv_rt_threshold;
+	unsigned long bgnd_time_slice_multiplier;
+	unsigned long zaphod_mode;
+};
+#endif /* CONFIG_GENETIC_CPU_SCHED */
 
 #endif /* __KERNEL__ */
 

_

Re: [ANNOUNCE 1/4][RFC] Genetic Algorithm Library

[Cal Peake]

On Thu, 6 Jan 2005, Jake Moilanen wrote:

Hi Jake,

> diff -puN fs/proc/proc_misc.c~genetic-lib fs/proc/proc_misc.c
> --- linux-2.6.9/fs/proc/proc_misc.c~genetic-lib	Wed Jan  5 15:45:54 2005
> +++ linux-2.6.9-moilanen/fs/proc/proc_misc.c	Wed Jan  5 15:45:54 2005
> @@ -45,6 +45,7 @@
>  #include <linux/sysrq.h>
>  #include <linux/vmalloc.h>
>  #include <linux/sched_cpustats.h>
> +#include <linux/genetic.h>
>  #include <asm/uaccess.h>
>  #include <asm/pgtable.h>
>  #include <asm/io.h>

This hunk fails, the line above the addition isn't in vanilla 2.6.9 - nor 
is the included file anywhere to be found either.

-- Cal

Re: [ANNOUNCE 1/4][RFC] Genetic Algorithm Library

[Cal Peake]

On Thu, 6 Jan 2005, Cal Peake wrote:

> This hunk fails, the line above the addition isn't in vanilla 2.6.9 - nor 
> is the included file anywhere to be found either.

nev mind, I see this also depends on the zaphod patch. sorry for the 
noise.

-- Cal

Re: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[James Bruce]

Do you have any crossover?  This is critical for GA to work well - 
without it, the algorithm is really only a parallel random search.  More 
specifically, is step 6 pure copies of a single parents, or can children 
inherit tunables from multiple parents?
  - Jim

Jake Moilanen wrote:
> ...
> 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.
 > ...

Re: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[James Bruce]

Ok I've read the patch and see you do indeed have crossover; Now I have 
a different question.  What is the motivation for generating two 
children at once, instead of just one?    Genes values shouldn't get 
"lost" since the parents are being kept around anyway.  Also, since the 
parameters in general will not have a meaningful ordering, it might make 
sense for the generic crossover to be the "each gene randomly picked 
from one of the two parents" approach.  In practice  I've found that to 
mix things up a bit better in the parameter optimization problems I've 
done with GAs.
   - Jim

James Bruce wrote:
> Do you have any crossover?  This is critical for GA to work well - 
> without it, the algorithm is really only a parallel random search.  More 
> specifically, is step 6 pure copies of a single parents, or can children 
> inherit tunables from multiple parents?
>  - Jim
> 
> Jake Moilanen wrote:
> 
>> ...
>> 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.
> 
>  > ...
> 

Re: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[Pedro Larroy]

Hi

>From a quick look I've seen your algorithm tends to converge to a global
optimum, but also as William Lee Irwin III has commentend on irc, it
might miss "special points" since there's no warranty of the function to
minize to be continuous.

I think it's a good idea to introduce this techniques to tune the
kernel, but perhaps userland would be the right place for them, to be
able to switch them off when in need or have more controll over them.
But it's a nice initiative in my opinion.

Regards.

-- 
Pedro Larroy Tovar | Linux & Network consultant |  pedro%larroy.com 
Make debian mirrors with debian-multimirror: http://pedro.larroy.com/deb_mm/
	* Las patentes de programación son nocivas para la innovación * 
				http://proinnova.hispalinux.es/

Re: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

On Sat, 08 Jan 2005 09:19:42 -0500
James Bruce <bruce@andrew.cmu.edu> wrote:

> Ok I've read the patch and see you do indeed have crossover; Now I have 
> a different question.  What is the motivation for generating two 
> children at once, instead of just one?    Genes values shouldn't get 
> "lost" since the parents are being kept around anyway.  Also, since the 
> parameters in general will not have a meaningful ordering, it might make 
> sense for the generic crossover to be the "each gene randomly picked 
> from one of the two parents" approach.  In practice  I've found that to 
> mix things up a bit better in the parameter optimization problems I've 
> done with GAs.

The intitial motivation for creating two children at once was so each
parent could pass on all of their genes.  The 75% of the parent's genes
might be in child A, but the other 25% would be in child B.  

Thinking about it more, there should be no reason that all of a parent's
genes have to be passed on in a child.  It would not be too difficult to
have each gene come randomly from one of the two parents.  I'll add that
in on the next rev of the patches. 

Thanks,
Jake 

Re: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library

[Jake Moilanen]

> From a quick look I've seen your algorithm tends to converge to a
> global optimum, but also as William Lee Irwin III has commentend on
> irc, it might miss "special points" since there's no warranty of the
> function to minize to be continuous.

This is a very good point, and is something that I'm working on now.  I
would like to be able to able to have multiple fitness rankings (ex. one
that ranks specifically for throughput and one specifically for
interactivity/latency).  Then tune specific genes, that actually
impact that specific fitness check.
 
> I think it's a good idea to introduce this techniques to tune the
> kernel, but perhaps userland would be the right place for them, to be
> able to switch them off when in need or have more controll over them.
> But it's a nice initiative in my opinion.

I considered doing this in userland at first, but I went away from it
for a couple reasons.  I wanted users of the library to have a lot of
flexibility.  There was also a concern with the extra overhead going
inbetween user/kernel space (important for users who's children have
very short life-spans).

Jake