SystemManager.java

package mvd.jester.model;

import java.math.RoundingMode;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;
import com.google.common.math.LongMath;
import org.apache.commons.math3.distribution.GammaDistribution;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.graph.DefaultEdge;
import mvd.jester.utils.DagUtils;
import mvd.jester.model.SystemManager.Builder;

/**
 * TaskSet
 */
public class SystemManager<T extends Builder> implements SystemManagerInterface {

    private final T builder;

    public SystemManager(Class<T> builder) {
        try {
            this.builder = builder.getDeclaredConstructor().newInstance();
        } catch (Exception e) {
            throw new RuntimeException("Builder could not be instantiated!");
        }
    }

    /**
     * @return the numberOfProcessors
     */
    public long getNumberOfProcessors() {
        return builder.getNumberOfProcessors();
    }

    /**
     * @param numberOfProcessors the numberOfProcessors to set
     */
    public void setNumberOfProcessors(long numberOfProcessors) {
        builder.setNumberOfProcessors(numberOfProcessors);
    }

    public T getBuilder() {
        return builder;
    }

    public static interface Builder {

        public long getNumberOfProcessors();

        public Builder setNumberOfProcessors(long numberOfProcessors);

    }

    public static class SynchronousTaskBuilder implements Builder {
        private long numberOfProcessors = 4;
        private long minPeriod = 100;
        private long maxSequentialPeriod = 1000;
        private long maxParallelPeriod = 10000;
        private long minNumberOfSegments = 3;
        private long maxNumberOfSegments = 7;
        private long minNumberOfJobs = 2;
        private long maxNumberOfJobs = 3 * numberOfProcessors / 2;
        private final long minWcet = 1;
        private long ratio = randomTaskRatio(this.parallelTaskRatio);
        private final long parallelTaskRatio = 0;

        public SynchronousTaskBuilder() {
        }

        private long randomSequentialTaskPeriod() {
            return ThreadLocalRandom.current().nextLong(minPeriod, maxSequentialPeriod);
        }

        private long randomParallelTaskPeriod() {
            return ThreadLocalRandom.current().nextLong(minPeriod, maxParallelPeriod);
        }

        private long randomTaskRatio(final long min) {
            return ThreadLocalRandom.current().nextLong(min, 100);
        }

        private long randomNumberOfSegments() {
            return ThreadLocalRandom.current().nextLong(minNumberOfSegments, maxNumberOfSegments);
        }

        private long randomNumberOfJobs() {
            this.maxNumberOfJobs = 3 * this.numberOfProcessors / 2;
            return ThreadLocalRandom.current().nextLong(minNumberOfJobs, maxNumberOfJobs);
        }

        private long randomWcet(final long period, final long numberOfSegments) {
            final long maxWcet = period / numberOfSegments;

            return ThreadLocalRandom.current().nextLong(minWcet, maxWcet);
        }

        private SynchronousTask generateTask() {
            final boolean serial = randomTaskRatio(0) > this.ratio;
            final long period = serial ? randomSequentialTaskPeriod() : randomParallelTaskPeriod();
            final long numberOfSegments = serial ? 1 : randomNumberOfSegments();
            final long parallelNumberOfJobs = serial ? 1 : randomNumberOfJobs();
            final Set<Segment> segments = new LinkedHashSet<Segment>();

            for (int i = 0; i < numberOfSegments; ++i) {
                final long numberOfJobs = i % 2 == 1 ? parallelNumberOfJobs : 1;
                final long wcet = randomWcet(period, numberOfSegments);
                segments.add(new Segment(wcet, numberOfJobs));
            }
            return new SynchronousTask(segments, period, numberOfProcessors);
        }

        public Set<SynchronousTask> generateTaskSet() {
            this.ratio = randomTaskRatio(this.parallelTaskRatio);
            final Set<SynchronousTask> taskSet = new HashSet<>();

            for (int i = 0; i < numberOfProcessors; ++i) {
                final SynchronousTask task = generateTask();
                taskSet.add(task);
            }

            return taskSet;
        }

        public boolean addTask(final Set<SynchronousTask> taskSet) {
            return taskSet.add(generateTask());
        }

        @Override
        public SynchronousTaskBuilder setNumberOfProcessors(final long numberOfProcessors) {
            this.numberOfProcessors = numberOfProcessors;

            return this;
        }

        public SynchronousTaskBuilder setNumberOfSegments(final long minNumberOfSegments,
                final long maxNumberOfSegments) {
            this.minNumberOfSegments = minNumberOfSegments;
            this.maxNumberOfSegments = maxNumberOfSegments;

            return this;
        }

        public SynchronousTaskBuilder setPeriods(final long minPeriod,
                final long maxSequentialPeriod, final long maxParallelPeriod) {
            this.minPeriod = minPeriod;
            this.maxSequentialPeriod = maxSequentialPeriod;
            this.maxParallelPeriod = maxParallelPeriod;

            return this;
        }

        /**
         * @param maxNumberOfJobs the maxNumberOfJobs to set
         */
        public SynchronousTaskBuilder setNumberOfJobs(final long minNumberOfJobs,
                final long maxNumberOfJobs) {
            this.minNumberOfJobs = minNumberOfJobs;
            this.maxNumberOfJobs = maxNumberOfJobs;
            return this;
        }

        @Override
        public long getNumberOfProcessors() {
            return numberOfProcessors;
        }
    }

    public static class DagTaskBuilder implements Builder {
        private long numberOfProcessors = 8;
        private long minimumWcet = 1;
        private long maximumWcet = 100;
        private long maxNumberOfBranches = 5;
        private long maxNumberOfThreads = numberOfProcessors;
        private long depth = 2;
        private long p_par = 80;
        private long p_add = 20; // TODO: Change back to 0.2

        public DagTaskBuilder() {
        }

        public double getBeta() {
            return 0.035 * numberOfProcessors;
        }

        private long randomProbability() {
            return ThreadLocalRandom.current().nextLong(0, 100);
        }

        public Set<DagTask> generateRenyiTaskSet(final double totalUtilization) {
            final LinkedHashSet<DagTask> taskSet = new LinkedHashSet<>();

            double currentUtilization = 0;
            while (currentUtilization <= totalUtilization) {
                final DagTask dagTask = generateRenyiTask(totalUtilization);

                if (currentUtilization + dagTask.getUtilization() < totalUtilization) {
                    currentUtilization += dagTask.getUtilization();
                    taskSet.add(dagTask);
                } else {
                    final double remainingUtilization = totalUtilization - currentUtilization;
                    final long period =
                            (long) Math.ceil(dagTask.getWorkload() / remainingUtilization);
                    if (period >= dagTask.getCriticalPath()) {
                        final DagTask modifiedTask =
                                new DagTask(dagTask.getJobDag(), period, numberOfProcessors);
                        taskSet.add(modifiedTask);
                        break;
                    }
                }
            }

            return taskSet;
        }

        public Set<DagTask> generateUUnifastTaskSet(final long numberOfTasks,
                final double totalUtilization) {
            final LinkedHashSet<DagTask> taskSet = new LinkedHashSet<>();

            if (numberOfTasks > 0) {
                double sumU = totalUtilization;
                for (int i = 1; i <= numberOfTasks - 1; i++) {
                    Double nextSumU = sumU * Math.pow(ThreadLocalRandom.current().nextDouble(),
                            (1.0 / (double) (numberOfTasks - i)));
                    DagTask task = generateTask(sumU - nextSumU);
                    taskSet.add(task);
                    sumU = nextSumU;
                }
                DagTask task = generateTask(sumU);
                taskSet.add(task);
            }

            return taskSet;
        }

        public Set<DagTask> generateTaskSet(final double totalUtilization) {
            final LinkedHashSet<DagTask> taskSet = new LinkedHashSet<>();
            double currentUtilization = 0;
            while (currentUtilization <= totalUtilization) {
                final DagTask dagTask = generateTask();

                if (currentUtilization + dagTask.getUtilization() < totalUtilization) {
                    currentUtilization += dagTask.getUtilization();
                    taskSet.add(dagTask);
                } else {
                    final double remainingUtilization = totalUtilization - currentUtilization;
                    final long period =
                            (long) Math.ceil(dagTask.getWorkload() / remainingUtilization);
                    if (period >= dagTask.getCriticalPath()) {
                        final DagTask modifiedTask =
                                new DagTask(dagTask.getJobDag(), period, numberOfProcessors);
                        taskSet.add(modifiedTask);
                        break;
                    }
                }
            }

            return taskSet;
        }

        public DagTask generateRenyiTask(final double totalUtilization) {
            final DirectedAcyclicGraph<Job, DefaultEdge> jobDag =
                    new DirectedAcyclicGraph<>(DefaultEdge.class);
            final long numberOfVertices = randomNumberInRange(50, 250);
            for (int i = 0; i < numberOfVertices - 2; ++i) {
                final long wcet = randomNumberInRange(50, 100);
                Job j = new Job(wcet);
                jobDag.addVertex(j);
            }

            randomEdgesRenyi(jobDag);
            addSourceAndSink(jobDag);

            final long workload = DagUtils.calculateWorkload(jobDag);
            final long criticalPath = DagUtils.calculateCriticalPath(jobDag);
            final long period = randomRenyiPeriod(workload, criticalPath, totalUtilization);

            final long minNumberOfThreads = LongMath.divide(workload - criticalPath,
                    period - criticalPath, RoundingMode.FLOOR);

            // TODO: change back to following:
            // final long numberOfThreads = randomNumberOfThreads(minNumberOfThreads);

            return new DagTask(jobDag, period, minNumberOfThreads);
        }

        private long randomRenyiPeriod(final long workload, final long criticalPath,
                final double totalUtilization) {
            final double firstPart =
                    (criticalPath + (double) (workload) / (0.4 * totalUtilization));
            final double gamma = new GammaDistribution(2, 1).sample();
            final double secondPart = 1 + 0.25 * gamma;

            return (long) Math.ceil(firstPart * secondPart);
        }

        private void addSourceAndSink(final DirectedAcyclicGraph<Job, DefaultEdge> jobDag) {
            final Multimap<Job, Job> edgePairs = ArrayListMultimap.create();
            Job source = new Job(randomNumberInRange(50, 100));
            Job sink = new Job(randomNumberInRange(50, 100));
            jobDag.addVertex(source);
            jobDag.addVertex(sink);
            for (Job j : jobDag) {
                if (jobDag.inDegreeOf(j) == 0) {
                    edgePairs.put(source, j);
                }
                if (jobDag.outDegreeOf(j) == 0) {
                    edgePairs.put(j, sink);
                }
            }

            for (final Map.Entry<Job, Job> pairs : edgePairs.entries()) {
                try {
                    jobDag.addDagEdge(pairs.getKey(), pairs.getValue());
                } catch (final Exception e) {
                    // nothing to do here
                }
            }
        }

        public DagTask generateTask(double utilization) {
            final DirectedAcyclicGraph<Job, DefaultEdge> jobDag =
                    new DirectedAcyclicGraph<>(DefaultEdge.class);

            final Job j = fork(jobDag, Optional.empty(), this.depth);
            fork(jobDag, Optional.of(j), this.depth);
            randomEdges(jobDag);

            final long workload = DagUtils.calculateWorkload(jobDag);

            final long period = (long) Math.ceil(workload / utilization);

            return new DagTask(jobDag, period, numberOfProcessors);
        }

        public DagTask generateTask() {
            final DirectedAcyclicGraph<Job, DefaultEdge> jobDag =
                    new DirectedAcyclicGraph<>(DefaultEdge.class);

            final Job j = fork(jobDag, Optional.empty(), this.depth);
            fork(jobDag, Optional.of(j), this.depth);
            randomEdges(jobDag);

            final long workload = DagUtils.calculateWorkload(jobDag);
            final long criticalPath = DagUtils.calculateCriticalPath(jobDag);

            final long period = randomTaskPeriod(criticalPath, workload);

            final long minNumberOfThreads = LongMath.divide(workload, period, RoundingMode.CEILING);
            final long numberOfThreads = randomNumberOfThreads(minNumberOfThreads);

            return new DagTask(jobDag, period, numberOfThreads);
        }

        private Job join(final DirectedAcyclicGraph<Job, DefaultEdge> jobDag, final Job current,
                final Set<Job> childs) {
            if (childs.size() > 0) {
                final Job job = new Job(randomWcet());
                jobDag.addVertex(job);
                for (final Job c : childs) {
                    try {
                        jobDag.addDagEdge(c, job);
                    } catch (final Exception e) {
                        System.out.println("Failed to join nodes!");
                    }
                }
                return job;
            }
            return current;
        }

        private Job fork(final DirectedAcyclicGraph<Job, DefaultEdge> jobDag,
                final Optional<Job> predecessor, final long depth) {
            final Job job = new Job(randomWcet());
            jobDag.addVertex(job);
            final Set<Job> childs = new HashSet<>();
            if (predecessor.isPresent()) {
                try {
                    jobDag.addDagEdge(predecessor.get(), job);
                } catch (final Exception e) {
                    System.out.println("Adding fork edge failed!");
                }
            }
            if (depth >= 0 && randomProbability() < p_par) {
                final long numberOfJobs = randomNumberOfBranches();
                for (int i = 0; i < numberOfJobs; ++i) {
                    childs.add(fork(jobDag, Optional.of(job), depth - 1));
                }
            }

            return join(jobDag, job, childs);
        }

        private void randomEdges(final DirectedAcyclicGraph<Job, DefaultEdge> jobDag) {
            final Multimap<Job, Job> edgePairs = ArrayListMultimap.create();
            for (final Job j1 : jobDag) {
                for (final Job j2 : jobDag) {
                    if (randomProbability() < p_add) {
                        edgePairs.put(j1, j2);
                    }
                }
            }

            for (final Map.Entry<Job, Job> pairs : edgePairs.entries()) {
                try {
                    jobDag.addDagEdge(pairs.getKey(), pairs.getValue());
                } catch (final Exception e) {
                    // nothing to do here
                }
            }
        }

        private void randomEdgesRenyi(final DirectedAcyclicGraph<Job, DefaultEdge> jobDag) {
            final Multimap<Job, Job> edgePairs = ArrayListMultimap.create();
            for (final Job j1 : jobDag) {
                for (final Job j2 : jobDag) {
                    if (j2 == j1) {
                        break;
                    }
                    if (randomProbability() < p_add) {
                        edgePairs.put(j1, j2);
                    }
                }
            }

            for (final Map.Entry<Job, Job> pairs : edgePairs.entries()) {
                try {
                    jobDag.addDagEdge(pairs.getKey(), pairs.getValue());
                } catch (final Exception e) {
                    // nothing to do here
                }
            }
        }

        private long randomNumberOfThreads(final long minNumberOfThreads) {
            return ThreadLocalRandom.current().nextLong(minNumberOfThreads, maxNumberOfThreads);
        }

        private long randomTaskPeriod(final long criticalPathLength, final long workload) {
            return ThreadLocalRandom.current().nextLong(criticalPathLength,
                    (long) (workload / getBeta()));
        }

        private long randomNumberOfBranches() {
            return ThreadLocalRandom.current().nextLong(2, maxNumberOfBranches);
        }

        private long randomNumberInRange(final long min, final long max) {
            return ThreadLocalRandom.current().nextLong(min, max);
        }

        private long randomWcet() {
            return ThreadLocalRandom.current().nextLong(minimumWcet, maximumWcet);
        }

        /**
         * @param numberOfProcessors the numberOfProcessors to set
         */
        @Override
        public DagTaskBuilder setNumberOfProcessors(final long numberOfProcessors) {
            this.numberOfProcessors = numberOfProcessors;
            return this;
        }

        /**
         * @return the numberOfProcessors
         */
        @Override
        public long getNumberOfProcessors() {
            return numberOfProcessors;
        }

        public DagTaskBuilder setWcets(final long minimumWcet, final long maximumWcet) {
            this.minimumWcet = minimumWcet;
            this.maximumWcet = maximumWcet;
            return this;
        }

        /**
         * @param maxNumberOfBranches the maxNumberOfBranches to set
         */
        public DagTaskBuilder setMaxNumberOfBranches(final long maxNumberOfBranches) {
            this.maxNumberOfBranches = maxNumberOfBranches;
            return this;
        }

        public DagTaskBuilder setPropabilities(final long p_par, final long p_add) {
            this.p_par = p_par;
            this.p_add = p_add;
            return this;
        }

        public DagTaskBuilder setNumberOfThreads(final long maxNumberOfThreads) {
            this.maxNumberOfThreads = maxNumberOfThreads;

            return this;
        }

        /**
         * @param depth the depth to set
         */
        public DagTaskBuilder setDepth(final long depth) {
            this.depth = depth;
            return this;
        }
    }
}