test/loops/TSPExchangerTest.java

/*
 * Written by Doug Lea and Bill Scherer with assistance from members
 * of JCP JSR-166 Expert Group and released to the public domain, as
 * explained at http://creativecommons.org/licenses/publicdomain
 */

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;

/**
 * A parallel Traveling Salesperson Problem (TSP) program based on a
 * genetic algorithm using an Exchanger.  A population of chromosomes
 * is distributed among "pools".  The chromosomes represent tours, and
 * their fitness is the total tour length. A Task is associated with
 * each pool.  Each task repeatedly does, for a fixed number of
 * iterations (generations):
 * <ol>
 *   <li> Select a breeder b from the pool
 *   <li> Create a strand of its tour with a random starting point and length
 *   <li> Offer the strand to the exchanger, receiving a strand from 
 *        another pool
 *   <li> Combine b and the received strand using crossing function to 
 *        create new chromosome c.
 *   <li> Replace a chromosome in the pool with c.
 * </ol>
 *
 * See below for more details.
 * <p>
 * 
 */
public class TSPExchangerTest {
    static final int NCPUS = Runtime.getRuntime().availableProcessors();

    static final int DEFAULT_MAX_THREADS  = NCPUS + 6;

    /**
     * The problem size. Each city is a random point. The goal is to
     * find a tour among them with smallest total Euclidean distance.
     */
    static final int DEFAULT_CITIES = 144;

    // Tuning parameters. 

    /**
     * The number of chromosomes per pool. Must be a power of two.
     *
     * Smaller values lead to faster iterations but poorer quality
     * results
     */
    static final int DEFAULT_POOL_SIZE = 32; 

    /**
     * The number of iterations per task. Convergence appears
     * to be roughly proportional to #cities-squared
     */
    static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES;

    /**
     * The number of pools. The total population is #pools * poolSize,
     * which should be roughly on the order of #cities-squared
     *
     * Smaller values lead to faster total runs but poorer quality
     * results
     */
    static final int DEFAULT_NPOOLS = DEFAULT_GENERATIONS / DEFAULT_POOL_SIZE;

    /**
     * The minimum length for a random chromosome strand.
     * Must be at least 1.
     */
    static final int MIN_STRAND_LENGTH = 3;

    /**
     * The probablility mask value for creating random strands,
     * that have lengths at least MIN_STRAND_LENGTH, and grow
     * with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1)
     * Must be 1 less than a power of two.
     */
    static final int RANDOM_STRAND_MASK = 7;

    /**
     * Probablility control for selecting breeders.
     * Breeders are selected starting at the best-fitness chromosome,
     * with exponentially decaying probablility
     * 1 / (poolSize >>> BREEDER_DECAY). 
     *
     * Larger values usually cause faster convergence but poorer
     * quality results
     */
    static final int BREEDER_DECAY = 1;

    /**
     * Probablility control for selecting dyers.
     * Dyers are selected starting at the worst-fitness chromosome,
     * with exponentially decaying probablility
     * 1 / (poolSize >>> DYER_DECAY)
     *
     * Larger values usually cause faster convergence but poorer
     * quality results
     */
    static final int DYER_DECAY = 1;

    static final boolean verbose = false;
    static final long SNAPSHOT_RATE = 10000; // in milliseconds

    /**
     * The set of cities. Created once per program run, to
     * make it easier to compare solutions across different runs.
     */
    static CitySet cities; 

    public static void main(String[] args) throws Exception {
        int maxThreads = DEFAULT_MAX_THREADS;
        int nCities = DEFAULT_CITIES;
        int poolSize = DEFAULT_POOL_SIZE;
        int nGen = nCities * nCities;
        int nPools = nCities * nCities / poolSize;

        try {
            int argc = 0;
            while (argc < args.length) {
                String option = args[argc++];
                if (option.equals("-c")) {
                    nCities = Integer.parseInt(args[argc]);
                    nGen = nCities * nCities;
                    nPools = nCities * nCities / poolSize;
                }
                else if (option.equals("-p"))
                    poolSize = Integer.parseInt(args[argc]);
                else if (option.equals("-g"))
                    nGen = Integer.parseInt(args[argc]);
                else if (option.equals("-n"))
                    nPools = Integer.parseInt(args[argc]);
                else
                    maxThreads = Integer.parseInt(option);
                argc++;
            }
        }
        catch (Exception e) {
            reportUsageErrorAndDie();
        }

        System.out.print("TSPExchangerTest");
        System.out.print(" -c " + nCities);
        System.out.print(" -g " + nGen);
        System.out.print(" -p " + poolSize);
        System.out.print(" -n " + nPools);
        System.out.print(" max threads " + maxThreads);
        System.out.println();

        cities = new CitySet(nCities);

        for (int i = 2; i <= maxThreads; i += 2) 
            oneRun(i, nPools, poolSize, nGen);
    }

    static void reportUsageErrorAndDie() {
        System.out.print("usage: TSPExchangerTest");
        System.out.print(" [-c #cities]");
        System.out.print(" [-p #poolSize]");
        System.out.print(" [-g #generations]");
        System.out.print(" [-n #pools]");
        System.out.print(" #threads]");
        System.out.println();
        System.exit(0);
    }

    /**
     * Perform one run with the given parameters.  Each run completes
     * when there are fewer than nThreads-2 tasks remaining.  This
     * avoids measuring termination effects, as well as cases where
     * the one last remaining task has no one left to exchange with,
     * so the pool is abruptly terminated.
     */
    static void oneRun(int nThreads, int nPools, int poolSize, int nGen) 
        throws InterruptedException {
        Population p = new Population(nThreads, nPools, poolSize, nGen);
        ProgressMonitor mon = null;
        if (verbose) {
            mon = new ProgressMonitor(p);
            mon.start();
        }
        p.printSnapshot(0);
        long startTime = System.nanoTime();
        p.start();
        p.awaitTasks();
        long stopTime = System.nanoTime();
        if (mon != null)
            mon.interrupt();
        p.shutdown();
        Thread.sleep(100);

        long elapsed = stopTime - startTime;
        long rate = elapsed / (nPools * nGen);
        double secs = (double)elapsed / 1000000000.0;
        p.printSnapshot(secs);
        System.out.printf("%10d ns per transfer\n", rate);
    }


    /**
     * A Population creates the pools, tasks, and threads for a run
     * and has control methods to start, stop, and report progress.
     */
    static final class Population {
        final Task[] tasks;
        final Exchanger<Strand> exchanger;
        final ThreadPoolExecutor exec;
        final CountDownLatch done;
        final int nGen;
        final int poolSize;
        final int nThreads;

        Population(int nThreads, int nPools, int poolSize, int nGen) {
            this.nThreads = nThreads;
            this.nGen = nGen;
            this.poolSize = poolSize;
            this.exchanger = new Exchanger<Strand>();
            this.done = new CountDownLatch(Math.max(1, nPools - nThreads - 2));
            this.tasks = new Task[nPools];
            for (int i = 0; i < nPools; i++) 
                tasks[i] = new Task(this);
            BlockingQueue<Runnable> tq = 
                new LinkedBlockingQueue<Runnable>();
            this.exec = new ThreadPoolExecutor(nThreads, nThreads,
                                               0L, TimeUnit.MILLISECONDS,
                                               tq);
            exec.prestartAllCoreThreads();
        }

        /** Start the tasks */
        void start() {
            for (int i = 0; i < tasks.length; i++) 
                exec.execute(tasks[i]);
        }

        /** Stop the tasks */
        void shutdown() {
            exec.shutdownNow();
        }

        /** Called by task upon terminations */
        void taskDone() {
            done.countDown();
        }

        /** Wait for (all but one) task to complete */
        void awaitTasks() throws InterruptedException {
            done.await();
        }

        /** 
         * Called by a task to resubmit itself after completing
         * fewer than nGen iterations.
         */
        void resubmit(Task task) {
            try {
                exec.execute(task);
            } catch(RejectedExecutionException ignore) {}
        }

        void printSnapshot(double secs) {
            int gens = 0;
            Chromosome bestc = tasks[0].chromosomes[0];
            Chromosome worstc = bestc;
            for (int k = 0; k < tasks.length; ++k) {
                gens += tasks[k].gen;
                Chromosome[] cs = tasks[k].chromosomes;
                if (cs[0].fitness < bestc.fitness)
                    bestc = cs[0];
                int w = cs[cs.length-1].fitness;
                if (cs[cs.length-1].fitness > worstc.fitness)
                    worstc = cs[cs.length-1];
            }
            double sqrtn = Math.sqrt(cities.length);
            double best = bestc.unitTourLength() / sqrtn;
            double worst = worstc.unitTourLength() / sqrtn;
            int avegen = (done.getCount() == 0)? nGen : gens / tasks.length;
            System.out.printf("Time:%9.3f Best:%7.3f Worst:%7.3f Gen:%6d Threads:%4d\n",
                              secs, best, worst, avegen, nThreads);
        }
        
    }

    /**
     * A Task updates its pool of chromosomes.. 
     */
    static final class Task implements Runnable {
        /** The pool of chromosomes, kept in sorted order */
        final Chromosome[] chromosomes;
        final Population pop;
        /** The common exchanger, same for all tasks */
        final Exchanger<Strand> exchanger;
        /** The current strand being exchanged */
        Strand strand;
        /** Bitset used in cross */
        final int[] inTour;
        final RNG rng;
        final int poolSize;
        final int nGen;
        final int genPerRun;
        int gen;

        Task(Population pop) {
            this.pop = pop;
            this.nGen = pop.nGen;
            this.gen = 0;
            this.poolSize = pop.poolSize;
            this.genPerRun = 4 * poolSize * Math.min(NCPUS, pop.nThreads);
            this.exchanger = pop.exchanger;
            this.rng = new RNG();
            int length = cities.length;
            this.strand = new Strand(length);
            this.inTour = new int[(length >>> 5) + 1];
            this.chromosomes = new Chromosome[poolSize];
            for (int j = 0; j < poolSize; ++j)
                chromosomes[j] = new Chromosome(length, rng);
            Arrays.sort(chromosomes);
        }

        /**
         * Run one or more update cycles.  An average of genPerRun
         * iterations are performed per run, and then the task is
         * resubmitted. The rate is proportional to both pool size and
         * number of threads.  This keeps average rate of breeding
         * across pools approximately constant across different test
         * runs.
         */
        public void run() {
            try {
                int maxGen = gen + 1 + rng.next() % genPerRun;
                if (maxGen > nGen) 
                    maxGen = nGen;
                while (gen++ < maxGen)
                    update();
                if (maxGen < nGen) 
                    pop.resubmit(this);
                else
                    pop.taskDone();
            } catch (InterruptedException ie) {
                pop.taskDone();
            }
        }

        /**
         * Choose a breeder, exchange strand with another pool, and
         * cross them to create new chromosome to replace a chosen
         * dyer.
         */
        void update() throws InterruptedException {
            int b = chooseBreeder();
            int d = chooseDyer(b);
            Chromosome breeder = chromosomes[b];
            Chromosome child = chromosomes[d];
            chooseStrand(breeder);
            strand = exchanger.exchange(strand);
            cross(breeder, child);
            fixOrder(child, d);
        }

        /**
         * Choose a breeder, with exponentially decreasing probability
         * starting at best.
         * @return index of selected breeder
         */
        int chooseBreeder() {
            int mask = (poolSize >>> BREEDER_DECAY) - 1;
            int b = 0;
            while ((rng.next() & mask) != mask) {
                if (++b >= poolSize)
                    b = 0;
            }
            return b;
        }

        /**
         * Choose a chromosome that will be replaced, with
         * exponentially decreasing probablility starting at
         * worst, ignoring the excluded index
         * @param exclude index to ignore; use -1 to not exclude any
         * @return index of selected dyer
         */
        int chooseDyer(int exclude) {
            int mask = (poolSize >>> DYER_DECAY)  - 1;
            int d = poolSize - 1;
            while (d == exclude || (rng.next() & mask) != mask) {
                if (--d < 0)
                    d = poolSize - 1;
            }
            return d;
        }

        /** 
         * Select a random strand of b's.
         * @param breeder the breeder
         */
        void chooseStrand(Chromosome breeder) {
            int[] bs = breeder.alleles;
            int length = bs.length;
            int strandLength = MIN_STRAND_LENGTH;
            while (strandLength < length &&
                   (rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK)
                strandLength++;
            strand.strandLength = strandLength;
            int[] ss = strand.alleles;
            int k = (rng.next() & 0x7FFFFFFF) % length;
            for (int i = 0; i < strandLength; ++i) {
                ss[i] = bs[k];
                if (++k >= length) k = 0;
            }
        }

        /**
         * Copy current strand to start of c's, and then append all
         * remaining b's that aren't in the strand.
         * @param breeder the breeder
         * @param child the child
         */
        void cross(Chromosome breeder, Chromosome child) {
            for (int k = 0; k < inTour.length; ++k) // clear bitset
                inTour[k] = 0;

            // Copy current strand to c
            int[] cs = child.alleles;
            int ssize = strand.strandLength;
            int[] ss = strand.alleles;
            int i;
            for (i = 0; i < ssize; ++i) {
                int x = ss[i];
                cs[i] = x;
                inTour[x >>> 5] |= 1 << (x & 31); // record in bit set
            }

            // Find index of matching origin in b
            int first = cs[0];
            int j = 0;
            int[] bs = breeder.alleles;
            while (bs[j] != first) 
                ++j;

            // Append remaining b's that aren't already in tour
            while (i < cs.length) {
                if (++j >= bs.length) j = 0;
                int x = bs[j];
                if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
                    cs[i++] = x;
            } 

        }

        /**
         * Fix the sort order of a changed Chromosome c at position k
         * @param c the chromosome
         * @param k the index 
         */
        void fixOrder(Chromosome c, int k) {
            Chromosome[] cs = chromosomes;
            int oldFitness = c.fitness;
            c.recalcFitness();
            int newFitness = c.fitness;
            if (newFitness < oldFitness) {
                int j = k;
                int p = j - 1;
                while (p >= 0 && cs[p].fitness > newFitness) {
                    cs[j] = cs[p];
                    j = p--;
                }
                cs[j] = c;
            } else if (newFitness > oldFitness) {
                int j = k;
                int n = j + 1;
                while (n < cs.length && cs[n].fitness < newFitness) {
                    cs[j] = cs[n];
                    j = n++;
                }
                cs[j] = c;
            }
        }
    }

    /**
     * A Chromosome is a candidate TSP tour.
     */
    static final class Chromosome implements Comparable {
        /** Index of cities in tour order */
        final int[] alleles;
        /** Total tour length */
        int fitness;

        /** 
         * Initialize to random tour
         */
        Chromosome(int length, RNG random) {
            alleles = new int[length];
            for (int i = 0; i < length; i++)
                alleles[i] = i;
            for (int i = length - 1; i > 0; i--) {
                int idx = (random.next() & 0x7FFFFFFF) % alleles.length;
                int tmp = alleles[i];
                alleles[i] = alleles[idx];
                alleles[idx] = tmp;
            }
            recalcFitness();
        }

        public int compareTo(Object x) { // to enable sorting
            int xf = ((Chromosome)x).fitness;
            int f = fitness;
            return ((f == xf)? 0 :((f < xf)? -1 : 1));
        }

        void recalcFitness() {
            int[] a = alleles;
            int len = a.length;
            int p = a[0];
            long f = cities.distanceBetween(a[len-1], p);
            for (int i = 1; i < len; i++) {
                int n = a[i];
                f += cities.distanceBetween(p, n);
                p = n;
            }
            fitness = (int)(f / len);
        }

        double unitTourLength() {
            int[] a = alleles;
            int len = a.length;
            int p = a[0];
            double f = cities.unitDistanceBetween(a[len-1], p);
            for (int i = 1; i < len; i++) {
                int n = a[i];
                f += cities.unitDistanceBetween(p, n);
                p = n;
            }
            return f;
        }

        void validate() { // Ensure that this is a valid tour.
            int len = alleles.length;
            boolean[] used = new boolean[len];
            for (int i = 0; i < len; ++i) 
                used[alleles[i]] = true;
            for (int i = 0; i < len; ++i) 
                if (!used[i])
                    throw new Error("Bad tour");
        }

    }

    /**
     * A Strand is a random sub-sequence of a Chromosome.  Each task
     * creates only one strand, and then trades it with others,
     * refilling it on each iteration.
     */
    static final class Strand {
        final int[] alleles;
        int strandLength;
        Strand(int length) { alleles = new int[length]; }
    }

    /**
     * A collection of (x,y) points that represent cities. 
     */
    static final class CitySet {

        final int length;
        final int[] xPts;
        final int[] yPts;
        final int[][] distances;

        CitySet(int n) {
            this.length = n;
            this.xPts = new int[n];
            this.yPts = new int[n];
            this.distances = new int[n][n];

            RNG random = new RNG();
            for (int i = 0; i < n; i++) {
                xPts[i] = (random.next() & 0x7FFFFFFF);
                yPts[i] = (random.next() & 0x7FFFFFFF);
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    double dx = (double)xPts[i] - (double)xPts[j];
                    double dy = (double)yPts[i] - (double)yPts[j];
                    double dd = Math.hypot(dx, dy) / 2.0;
                    long ld = Math.round(dd);
                    distances[i][j] = (ld >= Integer.MAX_VALUE)? 
                        Integer.MAX_VALUE : (int)ld;
                }
            }
        }

        /**
         *  Returns the cached distance between a pair of cities
         */
        int distanceBetween(int i, int j) {
            return distances[i][j];
        }

        // Scale ints to doubles in [0,1)
        static final double PSCALE = (double)0x80000000L;

        /**
         * Return distance for points scaled in [0,1). This simplifies
         * checking results.  The expected optimal TSP for random
         * points is believed to be around 0.76 * sqrt(N). For papers
         * discussing this, see
         * http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
         */
        double unitDistanceBetween(int i, int j) {
            double dx = ((double)xPts[i] - (double)xPts[j]) / PSCALE;
            double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE;
            return Math.hypot(dx, dy);
        }
            
    }

    /**
     * Cheap XorShift random number generator
     */
    static final class RNG {
        /** Seed generator for XorShift RNGs */
        static final Random seedGenerator = new Random();

        int seed;
        RNG(int seed) { this.seed = seed; }
        RNG()         { this.seed = seedGenerator.nextInt() | 1;  }

        int next() {
            int x = seed;
            x ^= x << 6;
            x ^= x >>> 21;
            x ^= x << 7;
            seed = x;
            return x;
        }
    }

    static final class ProgressMonitor extends Thread {
        final Population pop;
        ProgressMonitor(Population p) { pop = p; }
        public void run() {
            double time = 0;
            try {
                while (!Thread.interrupted()) {
                    sleep(SNAPSHOT_RATE);
                    time += SNAPSHOT_RATE;
                    pop.printSnapshot(time / 1000.0);
                }
            } catch (InterruptedException ie) {}
        }
    }
}
Revision:	1.3
Committed:	Mon Dec 12 20:06:20 2005 UTC (18 years, 5 months ago) by dl
Branch:	MAIN
Changes since 1.2:	+94 -78 lines
Log Message:	Improve as performance test
#	User	Rev	Content
1	dl	1.1	/*
2	dl	1.2	* Written by Doug Lea and Bill Scherer with assistance from members
3			* of JCP JSR-166 Expert Group and released to the public domain, as
4			* explained at http://creativecommons.org/licenses/publicdomain
5	dl	1.1	*/
6
7	dl	1.2	import java.util.*;
8	dl	1.1	import java.util.concurrent.*;
9			import java.util.concurrent.atomic.*;
10			import java.util.concurrent.locks.*;
11
12	dl	1.2	/**
13			* A parallel Traveling Salesperson Problem (TSP) program based on a
14			* genetic algorithm using an Exchanger. A population of chromosomes
15			* is distributed among "pools". The chromosomes represent tours, and
16	dl	1.3	* their fitness is the total tour length. A Task is associated with
17			* each pool. Each task repeatedly does, for a fixed number of
18			* iterations (generations):
19	dl	1.2	* <ol>
20			* <li> Select a breeder b from the pool
21			* <li> Create a strand of its tour with a random starting point and length
22			* <li> Offer the strand to the exchanger, receiving a strand from
23			* another pool
24			* <li> Combine b and the received strand using crossing function to
25			* create new chromosome c.
26			* <li> Replace a chromosome in the pool with c.
27			* </ol>
28			*
29			* See below for more details.
30			* <p>
31			*
32			*/
33	dl	1.1	public class TSPExchangerTest {
34	dl	1.3	static final int NCPUS = Runtime.getRuntime().availableProcessors();
35
36			static final int DEFAULT_MAX_THREADS = NCPUS + 6;
37	dl	1.2
38			/**
39			* The problem size. Each city is a random point. The goal is to
40			* find a tour among them with smallest total Euclidean distance.
41			*/
42			static final int DEFAULT_CITIES = 144;
43
44			// Tuning parameters.
45
46			/**
47			* The number of chromosomes per pool. Must be a power of two.
48			*
49			* Smaller values lead to faster iterations but poorer quality
50			* results
51			*/
52			static final int DEFAULT_POOL_SIZE = 32;
53	dl	1.1
54	dl	1.2	/**
55			* The number of iterations per task. Convergence appears
56			* to be roughly proportional to #cities-squared
57			*/
58			static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES;
59
60			/**
61			* The number of pools. The total population is #pools * poolSize,
62			* which should be roughly on the order of #cities-squared
63			*
64			* Smaller values lead to faster total runs but poorer quality
65			* results
66			*/
67			static final int DEFAULT_NPOOLS = DEFAULT_GENERATIONS / DEFAULT_POOL_SIZE;
68
69			/**
70			* The minimum length for a random chromosome strand.
71			* Must be at least 1.
72			*/
73			static final int MIN_STRAND_LENGTH = 3;
74
75			/**
76			* The probablility mask value for creating random strands,
77			* that have lengths at least MIN_STRAND_LENGTH, and grow
78			* with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1)
79			* Must be 1 less than a power of two.
80			*/
81			static final int RANDOM_STRAND_MASK = 7;
82
83			/**
84			* Probablility control for selecting breeders.
85			* Breeders are selected starting at the best-fitness chromosome,
86			* with exponentially decaying probablility
87			* 1 / (poolSize >>> BREEDER_DECAY).
88			*
89			* Larger values usually cause faster convergence but poorer
90			* quality results
91			*/
92			static final int BREEDER_DECAY = 1;
93
94			/**
95			* Probablility control for selecting dyers.
96			* Dyers are selected starting at the worst-fitness chromosome,
97			* with exponentially decaying probablility
98			* 1 / (poolSize >>> DYER_DECAY)
99			*
100			* Larger values usually cause faster convergence but poorer
101			* quality results
102			*/
103			static final int DYER_DECAY = 1;
104
105	dl	1.3	static final boolean verbose = false;
106	dl	1.2	static final long SNAPSHOT_RATE = 10000; // in milliseconds
107
108			/**
109			* The set of cities. Created once per program run, to
110			* make it easier to compare solutions across different runs.
111			*/
112			static CitySet cities;
113	dl	1.1
114			public static void main(String[] args) throws Exception {
115	dl	1.2	int maxThreads = DEFAULT_MAX_THREADS;
116	dl	1.1	int nCities = DEFAULT_CITIES;
117	dl	1.2	int poolSize = DEFAULT_POOL_SIZE;
118			int nGen = nCities * nCities;
119			int nPools = nCities * nCities / poolSize;
120	dl	1.1
121			try {
122	dl	1.2	int argc = 0;
123	dl	1.1	while (argc < args.length) {
124			String option = args[argc++];
125	dl	1.2	if (option.equals("-c")) {
126	dl	1.1	nCities = Integer.parseInt(args[argc]);
127	dl	1.2	nGen = nCities * nCities;
128			nPools = nCities * nCities / poolSize;
129			}
130			else if (option.equals("-p"))
131			poolSize = Integer.parseInt(args[argc]);
132	dl	1.1	else if (option.equals("-g"))
133	dl	1.2	nGen = Integer.parseInt(args[argc]);
134			else if (option.equals("-n"))
135			nPools = Integer.parseInt(args[argc]);
136			else
137	dl	1.1	maxThreads = Integer.parseInt(option);
138			argc++;
139			}
140			}
141			catch (Exception e) {
142			reportUsageErrorAndDie();
143			}
144
145	dl	1.2	System.out.print("TSPExchangerTest");
146			System.out.print(" -c " + nCities);
147			System.out.print(" -g " + nGen);
148			System.out.print(" -p " + poolSize);
149			System.out.print(" -n " + nPools);
150			System.out.print(" max threads " + maxThreads);
151			System.out.println();
152
153			cities = new CitySet(nCities);
154	dl	1.1
155	dl	1.2	for (int i = 2; i <= maxThreads; i += 2)
156			oneRun(i, nPools, poolSize, nGen);
157	dl	1.1	}
158
159	dl	1.2	static void reportUsageErrorAndDie() {
160			System.out.print("usage: TSPExchangerTest");
161			System.out.print(" [-c #cities]");
162			System.out.print(" [-p #poolSize]");
163			System.out.print(" [-g #generations]");
164			System.out.print(" [-n #pools]");
165			System.out.print(" #threads]");
166			System.out.println();
167	dl	1.1	System.exit(0);
168			}
169
170	dl	1.2	/**
171			* Perform one run with the given parameters. Each run completes
172	dl	1.3	* when there are fewer than nThreads-2 tasks remaining. This
173			* avoids measuring termination effects, as well as cases where
174			* the one last remaining task has no one left to exchange with,
175			* so the pool is abruptly terminated.
176	dl	1.2	*/
177			static void oneRun(int nThreads, int nPools, int poolSize, int nGen)
178			throws InterruptedException {
179			Population p = new Population(nThreads, nPools, poolSize, nGen);
180			ProgressMonitor mon = null;
181			if (verbose) {
182			mon = new ProgressMonitor(p);
183			mon.start();
184			}
185			p.printSnapshot(0);
186			long startTime = System.nanoTime();
187			p.start();
188			p.awaitTasks();
189			long stopTime = System.nanoTime();
190			if (mon != null)
191			mon.interrupt();
192			p.shutdown();
193			Thread.sleep(100);
194
195	dl	1.1	long elapsed = stopTime - startTime;
196	dl	1.2	long rate = elapsed / (nPools * nGen);
197			double secs = (double)elapsed / 1000000000.0;
198			p.printSnapshot(secs);
199			System.out.printf("%10d ns per transfer\n", rate);
200			}
201	dl	1.1
202
203	dl	1.2	/**
204			* A Population creates the pools, tasks, and threads for a run
205			* and has control methods to start, stop, and report progress.
206			*/
207	dl	1.1	static final class Population {
208	dl	1.2	final Task[] tasks;
209			final Exchanger<Strand> exchanger;
210			final ThreadPoolExecutor exec;
211			final CountDownLatch done;
212			final int nGen;
213			final int poolSize;
214	dl	1.1	final int nThreads;
215
216	dl	1.2	Population(int nThreads, int nPools, int poolSize, int nGen) {
217	dl	1.1	this.nThreads = nThreads;
218	dl	1.2	this.nGen = nGen;
219			this.poolSize = poolSize;
220			this.exchanger = new Exchanger<Strand>();
221	dl	1.3	this.done = new CountDownLatch(Math.max(1, nPools - nThreads - 2));
222	dl	1.2	this.tasks = new Task[nPools];
223			for (int i = 0; i < nPools; i++)
224			tasks[i] = new Task(this);
225			BlockingQueue<Runnable> tq =
226			new LinkedBlockingQueue<Runnable>();
227			this.exec = new ThreadPoolExecutor(nThreads, nThreads,
228			0L, TimeUnit.MILLISECONDS,
229			tq);
230			exec.prestartAllCoreThreads();
231			}
232
233			/** Start the tasks */
234			void start() {
235			for (int i = 0; i < tasks.length; i++)
236			exec.execute(tasks[i]);
237			}
238
239			/** Stop the tasks */
240			void shutdown() {
241			exec.shutdownNow();
242			}
243
244			/** Called by task upon terminations */
245			void taskDone() {
246			done.countDown();
247			}
248
249			/** Wait for (all but one) task to complete */
250			void awaitTasks() throws InterruptedException {
251			done.await();
252			}
253
254			/**
255			* Called by a task to resubmit itself after completing
256			* fewer than nGen iterations.
257			*/
258			void resubmit(Task task) {
259	dl	1.3	try {
260			exec.execute(task);
261			} catch(RejectedExecutionException ignore) {}
262	dl	1.2	}
263
264			void printSnapshot(double secs) {
265			int gens = 0;
266	dl	1.3	Chromosome bestc = tasks[0].chromosomes[0];
267			Chromosome worstc = bestc;
268	dl	1.2	for (int k = 0; k < tasks.length; ++k) {
269			gens += tasks[k].gen;
270			Chromosome[] cs = tasks[k].chromosomes;
271	dl	1.3	if (cs[0].fitness < bestc.fitness)
272			bestc = cs[0];
273			int w = cs[cs.length-1].fitness;
274			if (cs[cs.length-1].fitness > worstc.fitness)
275			worstc = cs[cs.length-1];
276			}
277			double sqrtn = Math.sqrt(cities.length);
278			double best = bestc.unitTourLength() / sqrtn;
279			double worst = worstc.unitTourLength() / sqrtn;
280	dl	1.2	int avegen = (done.getCount() == 0)? nGen : gens / tasks.length;
281	dl	1.3	System.out.printf("Time:%9.3f Best:%7.3f Worst:%7.3f Gen:%6d Threads:%4d\n",
282	dl	1.2	secs, best, worst, avegen, nThreads);
283			}
284
285			}
286	dl	1.1
287	dl	1.2	/**
288			* A Task updates its pool of chromosomes..
289			*/
290			static final class Task implements Runnable {
291			/** The pool of chromosomes, kept in sorted order */
292			final Chromosome[] chromosomes;
293			final Population pop;
294			/** The common exchanger, same for all tasks */
295			final Exchanger<Strand> exchanger;
296			/** The current strand being exchanged */
297			Strand strand;
298			/** Bitset used in cross */
299			final int[] inTour;
300			final RNG rng;
301			final int poolSize;
302			final int nGen;
303	dl	1.3	final int genPerRun;
304	dl	1.2	int gen;
305	dl	1.1
306	dl	1.2	Task(Population pop) {
307			this.pop = pop;
308			this.nGen = pop.nGen;
309			this.gen = 0;
310			this.poolSize = pop.poolSize;
311	dl	1.3	this.genPerRun = 4 * poolSize * Math.min(NCPUS, pop.nThreads);
312	dl	1.2	this.exchanger = pop.exchanger;
313			this.rng = new RNG();
314			int length = cities.length;
315			this.strand = new Strand(length);
316			this.inTour = new int[(length >>> 5) + 1];
317			this.chromosomes = new Chromosome[poolSize];
318			for (int j = 0; j < poolSize; ++j)
319			chromosomes[j] = new Chromosome(length, rng);
320			Arrays.sort(chromosomes);
321			}
322
323			/**
324	dl	1.3	* Run one or more update cycles. An average of genPerRun
325			* iterations are performed per run, and then the task is
326			* resubmitted. The rate is proportional to both pool size and
327			* number of threads. This keeps average rate of breeding
328			* across pools approximately constant across different test
329			* runs.
330	dl	1.2	*/
331			public void run() {
332	dl	1.1	try {
333	dl	1.3	int maxGen = gen + 1 + rng.next() % genPerRun;
334			if (maxGen > nGen)
335			maxGen = nGen;
336			while (gen++ < maxGen)
337	dl	1.2	update();
338	dl	1.3	if (maxGen < nGen)
339			pop.resubmit(this);
340			else
341			pop.taskDone();
342	dl	1.2	} catch (InterruptedException ie) {
343			pop.taskDone();
344	dl	1.1	}
345			}
346
347	dl	1.2	/**
348			* Choose a breeder, exchange strand with another pool, and
349			* cross them to create new chromosome to replace a chosen
350			* dyer.
351			*/
352			void update() throws InterruptedException {
353			int b = chooseBreeder();
354			int d = chooseDyer(b);
355			Chromosome breeder = chromosomes[b];
356			Chromosome child = chromosomes[d];
357			chooseStrand(breeder);
358			strand = exchanger.exchange(strand);
359			cross(breeder, child);
360			fixOrder(child, d);
361			}
362
363			/**
364			* Choose a breeder, with exponentially decreasing probability
365			* starting at best.
366			* @return index of selected breeder
367			*/
368			int chooseBreeder() {
369			int mask = (poolSize >>> BREEDER_DECAY) - 1;
370			int b = 0;
371			while ((rng.next() & mask) != mask) {
372			if (++b >= poolSize)
373			b = 0;
374			}
375			return b;
376			}
377
378			/**
379			* Choose a chromosome that will be replaced, with
380			* exponentially decreasing probablility starting at
381			* worst, ignoring the excluded index
382			* @param exclude index to ignore; use -1 to not exclude any
383			* @return index of selected dyer
384			*/
385			int chooseDyer(int exclude) {
386			int mask = (poolSize >>> DYER_DECAY) - 1;
387			int d = poolSize - 1;
388			while (d == exclude \|\| (rng.next() & mask) != mask) {
389			if (--d < 0)
390			d = poolSize - 1;
391			}
392			return d;
393			}
394
395			/**
396			* Select a random strand of b's.
397			* @param breeder the breeder
398			*/
399			void chooseStrand(Chromosome breeder) {
400			int[] bs = breeder.alleles;
401			int length = bs.length;
402			int strandLength = MIN_STRAND_LENGTH;
403			while (strandLength < length &&
404			(rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK)
405			strandLength++;
406			strand.strandLength = strandLength;
407			int[] ss = strand.alleles;
408			int k = (rng.next() & 0x7FFFFFFF) % length;
409			for (int i = 0; i < strandLength; ++i) {
410			ss[i] = bs[k];
411			if (++k >= length) k = 0;
412			}
413			}
414
415			/**
416			* Copy current strand to start of c's, and then append all
417			* remaining b's that aren't in the strand.
418			* @param breeder the breeder
419			* @param child the child
420			*/
421			void cross(Chromosome breeder, Chromosome child) {
422			for (int k = 0; k < inTour.length; ++k) // clear bitset
423			inTour[k] = 0;
424
425			// Copy current strand to c
426			int[] cs = child.alleles;
427			int ssize = strand.strandLength;
428			int[] ss = strand.alleles;
429			int i;
430			for (i = 0; i < ssize; ++i) {
431			int x = ss[i];
432			cs[i] = x;
433			inTour[x >>> 5] \|= 1 << (x & 31); // record in bit set
434			}
435
436			// Find index of matching origin in b
437			int first = cs[0];
438			int j = 0;
439			int[] bs = breeder.alleles;
440			while (bs[j] != first)
441			++j;
442
443			// Append remaining b's that aren't already in tour
444			while (i < cs.length) {
445			if (++j >= bs.length) j = 0;
446			int x = bs[j];
447			if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
448			cs[i++] = x;
449			}
450	dl	1.1
451			}
452
453	dl	1.2	/**
454			* Fix the sort order of a changed Chromosome c at position k
455			* @param c the chromosome
456			* @param k the index
457			*/
458			void fixOrder(Chromosome c, int k) {
459			Chromosome[] cs = chromosomes;
460	dl	1.3	int oldFitness = c.fitness;
461	dl	1.2	c.recalcFitness();
462	dl	1.3	int newFitness = c.fitness;
463	dl	1.2	if (newFitness < oldFitness) {
464			int j = k;
465			int p = j - 1;
466			while (p >= 0 && cs[p].fitness > newFitness) {
467			cs[j] = cs[p];
468			j = p--;
469	dl	1.1	}
470	dl	1.2	cs[j] = c;
471			} else if (newFitness > oldFitness) {
472			int j = k;
473			int n = j + 1;
474			while (n < cs.length && cs[n].fitness < newFitness) {
475			cs[j] = cs[n];
476			j = n++;
477	dl	1.1	}
478	dl	1.2	cs[j] = c;
479	dl	1.1	}
480			}
481			}
482
483	dl	1.2	/**
484			* A Chromosome is a candidate TSP tour.
485			*/
486			static final class Chromosome implements Comparable {
487			/** Index of cities in tour order */
488			final int[] alleles;
489			/** Total tour length */
490	dl	1.3	int fitness;
491	dl	1.2
492			/**
493			* Initialize to random tour
494			*/
495			Chromosome(int length, RNG random) {
496	dl	1.1	alleles = new int[length];
497			for (int i = 0; i < length; i++)
498			alleles[i] = i;
499			for (int i = length - 1; i > 0; i--) {
500	dl	1.2	int idx = (random.next() & 0x7FFFFFFF) % alleles.length;
501	dl	1.1	int tmp = alleles[i];
502			alleles[i] = alleles[idx];
503			alleles[idx] = tmp;
504			}
505			recalcFitness();
506			}
507	dl	1.2
508			public int compareTo(Object x) { // to enable sorting
509	dl	1.3	int xf = ((Chromosome)x).fitness;
510			int f = fitness;
511	dl	1.2	return ((f == xf)? 0 :((f < xf)? -1 : 1));
512	dl	1.1	}
513	dl	1.2
514	dl	1.1	void recalcFitness() {
515	dl	1.2	int[] a = alleles;
516			int len = a.length;
517			int p = a[0];
518	dl	1.3	long f = cities.distanceBetween(a[len-1], p);
519	dl	1.2	for (int i = 1; i < len; i++) {
520			int n = a[i];
521			f += cities.distanceBetween(p, n);
522			p = n;
523			}
524	dl	1.3	fitness = (int)(f / len);
525			}
526
527			double unitTourLength() {
528			int[] a = alleles;
529			int len = a.length;
530			int p = a[0];
531			double f = cities.unitDistanceBetween(a[len-1], p);
532			for (int i = 1; i < len; i++) {
533			int n = a[i];
534			f += cities.unitDistanceBetween(p, n);
535			p = n;
536			}
537			return f;
538	dl	1.2	}
539
540			void validate() { // Ensure that this is a valid tour.
541			int len = alleles.length;
542			boolean[] used = new boolean[len];
543			for (int i = 0; i < len; ++i)
544			used[alleles[i]] = true;
545			for (int i = 0; i < len; ++i)
546			if (!used[i])
547			throw new Error("Bad tour");
548	dl	1.1	}
549	dl	1.2
550			}
551
552			/**
553			* A Strand is a random sub-sequence of a Chromosome. Each task
554			* creates only one strand, and then trades it with others,
555			* refilling it on each iteration.
556			*/
557			static final class Strand {
558			final int[] alleles;
559			int strandLength;
560			Strand(int length) { alleles = new int[length]; }
561	dl	1.1	}
562	dl	1.2
563	dl	1.1	/**
564	dl	1.3	* A collection of (x,y) points that represent cities.
565	dl	1.1	*/
566			static final class CitySet {
567	dl	1.2
568	dl	1.1	final int length;
569	dl	1.2	final int[] xPts;
570			final int[] yPts;
571	dl	1.3	final int[][] distances;
572	dl	1.2
573			CitySet(int n) {
574	dl	1.1	this.length = n;
575	dl	1.2	this.xPts = new int[n];
576			this.yPts = new int[n];
577	dl	1.3	this.distances = new int[n][n];
578	dl	1.2
579			RNG random = new RNG();
580	dl	1.1	for (int i = 0; i < n; i++) {
581	dl	1.2	xPts[i] = (random.next() & 0x7FFFFFFF);
582			yPts[i] = (random.next() & 0x7FFFFFFF);
583	dl	1.1	}
584	dl	1.2
585	dl	1.1	for (int i = 0; i < n; i++) {
586			for (int j = 0; j < n; j++) {
587	dl	1.3	double dx = (double)xPts[i] - (double)xPts[j];
588			double dy = (double)yPts[i] - (double)yPts[j];
589			double dd = Math.hypot(dx, dy) / 2.0;
590			long ld = Math.round(dd);
591			distances[i][j] = (ld >= Integer.MAX_VALUE)?
592			Integer.MAX_VALUE : (int)ld;
593	dl	1.1	}
594			}
595			}
596	dl	1.2
597	dl	1.3	/**
598			* Returns the cached distance between a pair of cities
599			*/
600			int distanceBetween(int i, int j) {
601	dl	1.2	return distances[i][j];
602			}
603	dl	1.3
604			// Scale ints to doubles in [0,1)
605			static final double PSCALE = (double)0x80000000L;
606
607			/**
608			* Return distance for points scaled in [0,1). This simplifies
609			* checking results. The expected optimal TSP for random
610			* points is believed to be around 0.76 * sqrt(N). For papers
611			* discussing this, see
612			* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
613			*/
614			double unitDistanceBetween(int i, int j) {
615			double dx = ((double)xPts[i] - (double)xPts[j]) / PSCALE;
616			double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE;
617			return Math.hypot(dx, dy);
618			}
619
620	dl	1.2	}
621
622			/**
623			* Cheap XorShift random number generator
624			*/
625			static final class RNG {
626			/** Seed generator for XorShift RNGs */
627			static final Random seedGenerator = new Random();
628
629			int seed;
630			RNG(int seed) { this.seed = seed; }
631	dl	1.3	RNG() { this.seed = seedGenerator.nextInt() \| 1; }
632	dl	1.2
633			int next() {
634			int x = seed;
635			x ^= x << 6;
636			x ^= x >>> 21;
637			x ^= x << 7;
638			seed = x;
639			return x;
640	dl	1.1	}
641			}
642
643	dl	1.2	static final class ProgressMonitor extends Thread {
644	dl	1.1	final Population pop;
645	dl	1.2	ProgressMonitor(Population p) { pop = p; }
646	dl	1.1	public void run() {
647	dl	1.2	double time = 0;
648	dl	1.1	try {
649	dl	1.2	while (!Thread.interrupted()) {
650			sleep(SNAPSHOT_RATE);
651			time += SNAPSHOT_RATE;
652			pop.printSnapshot(time / 1000.0);
653	dl	1.1	}
654	dl	1.2	} catch (InterruptedException ie) {}
655	dl	1.1	}
656			}
657			}