Changeset 1742

Timestamp:

09/12/14 14:30:21 (10 years ago)

Author:

rkrimmel

Message:

Parallel Replacement done

Location:

branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees

Files:

• alignment/algorithms/Match.java (modified) (3 diffs)
• temporalrelation/RuleUtils.java (modified) (1 diff)
• temporalrelation/SequenceForTaskDetectionRuleAlignment.java (modified) (31 diffs)

branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java

@@ -13 +13 @@
  * The Class Match.
  */
-public class Match implements Comparable<Match>,Serializable {
+public class Match implements Cloneable,Comparable<Match>,Serializable {
         
         /** The Constant serialVersionUID. */
@@ -133 +133 @@
 
         /**
-         * Ocurrence id sum. Used for comparing and sorting matches
+         * Occurrence id sum. Used for comparing and sorting matches
          *
-         * @return th
+         * @return the sum of all occurrence ids.
          */
         public int ocurrenceIDSum() {
@@ -168 +168 @@
         }
         
+        
+        
         /**
          * Size.

branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/RuleUtils.java

@@ -59 +59 @@
          * @return the replacement for the range
          */
-        static ISequenceInstance createNewSubSequenceInRange(
+        static synchronized ISequenceInstance createNewSubSequenceInRange(
                         ITaskInstanceList parent, int startIndex, int endIndex,
                         ISequence model, ITaskFactory taskFactory, ITaskBuilder taskBuilder) {

branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java

@@ -74 +74 @@
 public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {
 
-        
         /** The n threads. */
         public static int nThreads = Runtime.getRuntime().availableProcessors() - 1;
@@ -158 +157 @@
                         detectAndReplaceIterations(appData);
                         appData.getStopWatch().start("task replacement");
-                        //Just does anything if the substitution matrix is created with the option to do so
+                        // Just does anything if the substitution matrix is created with the
+                        // option to do so
                         appData.updateSubstitutionMatrix();
                         detectAndReplaceTasks(appData); //
                         appData.getStopWatch().stop("task replacement");
                         appData.getStopWatch().stop("whole loop");
-                        //appData.getStopWatch().dumpStatistics(System.out);
+                        // appData.getStopWatch().dumpStatistics(System.out);
                         appData.getStopWatch().reset();
 
@@ -179 +179 @@
                                         RuleApplicationStatus.FINISHED);
                 }
-                //new TaskTreeValidator().validate(appData.getSessions());
+                // new TaskTreeValidator().validate(appData.getSessions());
                 return appData.getResult();
         }
@@ -257 +257 @@
                 Console.traceln(Level.FINE, "Found " + appData.getMatchseqs().size()
                                 + " results");
-
+                
+                //Nothing found, we can end here
+                if(appData.getMatchseqs().size()==0) {
+                        appData.detectedAndReplacedTasks=false;
+                        return;
+                }
+                
                 // Searching each match in all other sessions, counting its occurences
                 searchMatchesInAllSessions(appData);
@@ -268 +274 @@
                         public int compare(Match m1, Match m2) {
                                 int cmp = m2.occurenceCount() - m1.occurenceCount();
-                                if(cmp != 0) {
+                                if (cmp != 0) {
                                         return cmp;
-                                }
-                                else {
-                                        cmp = m2.size()-m1.size();
-                                        if(cmp != 0) {
+                                } else {
+                                        cmp = m2.size() - m1.size();
+                                        if (cmp != 0) {
                                                 return cmp;
-                                        }
-                                        else {
-                                                //This should rarely happen
-                                                cmp = m2.ocurrenceIDSum()-m1.ocurrenceIDSum();
-                                                if(cmp !=0) {
+                                        } else {
+                                                // This should rarely happen
+                                                cmp = m2.ocurrenceIDSum() - m1.ocurrenceIDSum();
+                                                if (cmp != 0) {
                                                         return cmp;
-                                                }
-                                                else {
-                                                        cmp = m2.taskIdSum()-m1.taskIdSum();
-                                                        
+                                                } else {
+                                                        cmp = m2.taskIdSum() - m1.taskIdSum();
+
                                                         return cmp;
                                                 }
@@ -291 +294 @@
                         }
                 };
-                
+
                 Collections.sort(appData.getMatchseqs(), comparator);
                 appData.getStopWatch().stop("detecting tasks");
-        
-
-                // Replace matches in the sessions
+
+                Console.traceln(Level.INFO, "Preparing replacments");
+                prepareReplacements(appData);
                 Console.traceln(Level.INFO, "Replacing matches in sessions");
                 appData.getStopWatch().start("replacing tasks");
@@ -303 +306 @@
         }
 
-        
-        //TODO: DEBUG METHOD
+        // TODO: DEBUG METHOD
         @SuppressWarnings("unused")
         private void printMatches(RuleApplicationData appData) {
                 LinkedList<Match> matchseqs = appData.getMatchseqs();
-                if(iteration>1) {
-                System.out.println("PRINTING MATCHES");
-                for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) {
-                        Match m = it.next();
-                        m.getFirstSequence().printSequence();
-                        m.getSecondSequence().printSequence();
-                        for(Iterator<MatchOccurrence> jt = m.getOccurences().iterator();jt.hasNext();) {
-                                MatchOccurrence mo = jt.next();
-                                System.out.print(mo.getSequenceId() + " ");
-                        }
-                        System.out.println();
-                        System.out.println();
-                }
-                }
-        }
-
-        
+                if (iteration > 1) {
+                        System.out.println("PRINTING MATCHES");
+                        for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) {
+                                Match m = it.next();
+                                m.getFirstSequence().printSequence();
+                                m.getSecondSequence().printSequence();
+                                for (Iterator<MatchOccurrence> jt = m.getOccurences()
+                                                .iterator(); jt.hasNext();) {
+                                        MatchOccurrence mo = jt.next();
+                                        System.out.print(mo.getSequenceId() + " ");
+                                }
+                                System.out.println();
+                                System.out.println();
+                        }
+                }
+        }
+
         /**
          * <p>
@@ -557 +559 @@
                                                 i++;
                                         }
-                                         if ((i == (first.length - 1)) && selectionfound) {
-                                         taskBuilder.addChild(subsequence1, appData
-                                         .getNumber2Task().get(first[i]));
-                                         taskBuilder.addChild(subsequence2, appData
-                                         .getNumber2Task().get(second[i]));
-                                         }
+                                        if ((i == (first.length - 1)) && selectionfound) {
+                                                taskBuilder.addChild(subsequence1, appData
+                                                                .getNumber2Task().get(first[i]));
+                                                taskBuilder.addChild(subsequence2, appData
+                                                                .getNumber2Task().get(second[i]));
+                                        }
                                 }
                         } else {
@@ -659 +661 @@
         private void prepareReplacements(RuleApplicationData appData) {
                 appData.initializeQueues(appData.getSessions().size());
-                final int matchSeqSize = appData.getMatchseqs().size();
-                int count = 0;
-                for (Iterator<Match> it = appData.getMatchseqs().iterator(); it.hasNext();) {
+                
+                for (Iterator<Match> it = appData.getMatchseqs().iterator(); it
+                                .hasNext();) {
                         Match m = it.next();
-                        for(Iterator<MatchOccurrence> jt=m.getOccurences().iterator();jt.hasNext();) {
+                        for (Iterator<MatchOccurrence> jt = m.getOccurences().iterator(); jt
+                                        .hasNext();) {
                                 MatchOccurrence mo = jt.next();
-                                
+
                                 Match emptyMatch = null;
                                 try {
@@ -675 +678 @@
                                 appData.getPlannedReplacements()[mo.getSequenceId()].add(m);
                         }
-                        count++;
-                        
-                }
-        }
-        
+                }
+        }
+
         /**
          * Replace matches.
@@ -687 +688 @@
          */
         private void replaceMatches(RuleApplicationData appData) {
-                appData.setReplacedOccurences(new HashMap<Integer, List<MatchOccurrence>>());
-
-                final int matchSeqSize = appData.getMatchseqs().size();
-                int count = 0;
-                for (int i = 0; i < matchSeqSize; i++) {
-                        count++;
-                        // Every pattern consists of 2 sequences, therefore the minimum
-                        // occurrences here is 2.
-                        // We just need the sequences also occurring in other sequences
-                        // as well
-                        RuleUtils.printProgressPercentage("Replacement progress", count, matchSeqSize);
-                        if (appData.getMatchseqs().get(i).occurenceCount() > 2) {
-
-                                final ISequence task = matchAsSequence(appData, appData
-                                                .getMatchseqs().get(i));
-                                invalidOccurence: for (final Iterator<MatchOccurrence> it = appData
-                                                .getMatchseqs().get(i).getOccurences().iterator(); it
-                                                .hasNext();) {
-                                        final MatchOccurrence oc = it.next();
-
-                                        // Check if nothing has been replaced in the sequence we
-                                        // want to replace now
-                                        if (appData.getReplacedOccurrences()
-                                                        .get(oc.getSequenceId()) == null) {
-                                                appData.getReplacedOccurrences().put(
-                                                                oc.getSequenceId(),
-                                                                new LinkedList<MatchOccurrence>());
-                                        } else {
-                                                // check if we have any replaced occurence with
-                                                // indexes
-                                                // smaller than ours. If so, we need to adjust
-                                                // our start
-                                                // and endpoints
-                                                // of the replacement.
-                                                // Also do a check if we have replaced this
-                                                // specific
-                                                // MatchOccurence in this sequence already. Jump
-                                                // to the
-                                                // next occurence if this is the case.
-                                                // This is no more neccessary once the matches
-                                                // are
-                                                // harmonized.
-
-                                                for (final Iterator<MatchOccurrence> jt = appData
-                                                                .getReplacedOccurrences()
-                                                                .get(oc.getSequenceId()).iterator(); jt
-                                                                .hasNext();) {
-                                                        final MatchOccurrence tmpOC = jt.next();
-
-                                                        if ((oc.getStartindex() >= tmpOC.getStartindex())
-                                                                        && (oc.getStartindex() <= tmpOC
-                                                                                        .getEndindex())) {
-                                                                continue invalidOccurence;
-                                                        }
-                                                        if (oc.getEndindex() >= tmpOC.getStartindex()) {
-                                                                continue invalidOccurence;
-
-                                                        } else if (oc.getStartindex() > tmpOC.getEndindex()) {
-                                                                final int diff = tmpOC.getEndindex()
-                                                                                - tmpOC.getStartindex();
-                                                                // Just to be sure.
-                                                                if (diff > 0) {
-                                                                        oc.setStartindex((oc.getStartindex() - diff) + 1);
-                                                                        oc.setEndindex((oc.getEndindex() - diff) + 1);
-                                                                } else {
-                                                                        Console.traceln(Level.WARNING,
-                                                                                        "End index of a Match before start. This should never happen");
-                                                                }
-                                                        }
-                                                }
-                                        }
-                                        appData.detectedAndReplacedTasks = true;
-                                        final ISequenceInstance sequenceInstances = RuleUtils
-                                                        .createNewSubSequenceInRange(appData.getSessions()
-                                                                        .get(oc.getSequenceId()), oc
-                                                                        .getStartindex(), oc.getEndindex(), task,
-                                                                        taskFactory, taskBuilder);
-                                        oc.setEndindex((oc.getStartindex() + sequenceInstances
-                                                        .size()) - RuleUtils.missedOptionals);
-
-                                        // Adjust the length of the match regarding to the
-                                        // length of
-                                        // instance. (OptionalInstances may be shorter)
-
-                                        appData.getReplacedOccurrences().get(oc.getSequenceId())
-                                                        .add(oc);
-                                }
-                        }
+        
+                final int numberSeqSize = appData.getNumberSequences().size();
+                Console.traceln(Level.INFO, "replacing matches with " + nThreads + " threads");
+                int newThreads = nThreads;
+                if (numberSeqSize < nThreads) {
+                        newThreads = numberSeqSize;
+                }
+                final int interval = numberSeqSize / newThreads;
+                int rest = numberSeqSize % newThreads;
+                final ExecutorService executor = Executors.newFixedThreadPool(nThreads);
+                for (int i = 0; i <= (numberSeqSize - interval); i += interval) {
+                        int offset = 0;
+                        if (rest != 0) {
+                                offset = 1;
+                                rest--;
+                        }
+                        final int from = i;
+                        final int to = i + interval + offset - 1;
+                        Console.traceln(Level.FINE,
+                                        "Match replaceing: Creating thread with matches from " + from
+                                                        + " to " + to);
+                        // search each match in every other sequence
+                        final ParallelMatchReplacer replacer = new ParallelMatchReplacer(
+                                        appData, from, to);
+                        executor.execute(replacer);
+                        i += offset;
+                }
+                executor.shutdown();
+                try {
+                        executor.awaitTermination(2, TimeUnit.HOURS);
+                } catch (final InterruptedException e) {
+                        e.printStackTrace();
                 }
         }
@@ -833 +778 @@
                                 rest--;
                         }
-                
+
                         final int from = i;
-                        final int to = i + interval+offset-1;
-                        Console.traceln(Level.FINER, "Aligning: Creating thread for sessions " + from + " till " + to);
+                        final int to = i + interval + offset - 1;
+                        Console.traceln(Level.FINER,
+                                        "Aligning: Creating thread for sessions " + from + " till "
+                                                        + to);
                         final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(
                                         appData, from, to);
                         executor.execute(aligner);
-                        i+=offset;
+                        i += offset;
                 }
                 executor.shutdown();
@@ -850 +797 @@
         }
 
-        
-        
-        
         /**
          * Search matches in all sessions.
@@ -860 +804 @@
          */
         private void searchMatchesInAllSessions(RuleApplicationData appData) {
-                
+
                 // Prepare parallel search of matchseqs
                 final int matchSeqSize = appData.getMatchseqs().size();
-                Console.traceln(Level.INFO,
-                                "searching for patterns ("+ matchSeqSize+") occuring most with " + nThreads
-                                                + " threads");
+                Console.traceln(Level.INFO, "searching for patterns (" + matchSeqSize
+                                + ") occuring most with " + nThreads + " threads");
                 int newThreads = nThreads;
                 if (matchSeqSize < nThreads) {
@@ -874 +817 @@
                 final ExecutorService executor = Executors.newFixedThreadPool(nThreads);
                 Console.traceln(Level.FINER, "Interval: " + interval + " Rest: " + rest);
-                for (int i = 0; i <= (matchSeqSize-interval); i += interval) {
+                for (int i = 0; i <= (matchSeqSize - interval); i += interval) {
                         int offset = 0;
                         if (rest != 0) {
@@ -881 +824 @@
                         }
                         final int from = i;
-                        final int to = i + interval + offset-1;
-                        Console.traceln(Level.FINE, "Match finding: Creating thread with matches from "
-                                                        + from + " to " + to);
+                        final int to = i + interval + offset - 1;
+                        Console.traceln(Level.FINE,
+                                        "Match finding: Creating thread with matches from " + from
+                                                        + " to " + to);
                         // search each match in every other sequence
                         final ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder(
                                         appData, from, to);
                         executor.execute(finder);
-                        i+=offset;
+                        i += offset;
                 }
                 executor.shutdown();
@@ -939 +883 @@
                         this.to = to;
                 }
+
                 /*
                  * (non-Javadoc)
@@ -947 +892 @@
                 public void run() {
                         int count = 0;
-                        final int size = to - from;
+                        final int size = to + 1 - from;
 
                         for (int i = from; i <= to; i++) {
@@ -981 +926 @@
                 }
         }
-        
-        
 
         /**
@@ -1022 +965 @@
                 public void run() {
                         int count = 0;
-                        final int size = to - from; 
+                        final int size = to +1 - from;
 
                         for (int i = from; i <= to; i++) {
@@ -1044 +987 @@
                 }
         }
-        
+
+        /**
+         * The Class ParallelPairwiseAligner.
+         */
+        private class ParallelMatchReplacer implements Runnable {
+
+                /** The app data. */
+                private final RuleApplicationData appData;
+
+                /** The from. */
+                private final int from;
+
+                /** The to. */
+                private final int to;
+
+                /**
+                 * Instantiates a new parallel pairwise aligner.
+                 *
+                 * @param appData
+                 *            the app data
+                 * @param from
+                 *            the from
+                 * @param to
+                 *            the to
+                 */
+                ParallelMatchReplacer(RuleApplicationData appData, int from, int to) {
+                        this.appData = appData;
+                        this.from = from;
+                        this.to = to;
+                }
+
+                /*
+                 * (non-Javadoc)
+                 * 
+                 * @see java.lang.Runnable#run()
+                 */
+                @Override
+                public void run() {
+                        for (int i = from; i <= to; i++) {
+                                
+                                /*
+                                 * HashMap for keeping track in which sequence which replacement has
+                                 * been performed. Neccessary for updating the indices of other
+                                 * occurrences accordingly
+                                 */
+                                LinkedList<MatchOccurrence> replacedOccurrences = new LinkedList<MatchOccurrence>();
+                                invalidOccurence: while (!appData.getPlannedReplacements()[i]
+                                                .isEmpty()) {
+
+                                        Match m = appData.getPlannedReplacements()[i].remove();
+                                        // Occurrences list has just one child
+                                        MatchOccurrence oc = m.getOccurences().getFirst();
+                                        // check if we have any replaced occurrence with
+                                        // indexes
+                                        // smaller than ours. If so, we need to adjust
+                                        // our start and end points of the replacement.
+                                        // Also do a check if we have replaced this
+                                        // specific MatchOccurence in this sequence already.
+                                        // Jump to the next occurrence if this is the case.
+                                        // This is no more necessary once the matches
+                                        // are harmonized.
+
+                                        for (final Iterator<MatchOccurrence> jt = replacedOccurrences
+                                                        .iterator(); jt.hasNext();) {
+                                                final MatchOccurrence tmpOC = jt.next();
+
+                                                if ((oc.getStartindex() >= tmpOC.getStartindex())
+                                                                && (oc.getStartindex() <= tmpOC.getEndindex())) {
+                                                        continue invalidOccurence;
+                                                }
+                                                if (oc.getEndindex() >= tmpOC.getStartindex()) {
+                                                        continue invalidOccurence;
+
+                                                } else if (oc.getStartindex() > tmpOC.getEndindex()) {
+                                                        final int diff = tmpOC.getEndindex()
+                                                                        - tmpOC.getStartindex();
+                                                        // Just to be sure.
+                                                        if (diff > 0) {
+                                                                oc.setStartindex((oc.getStartindex() - diff) + 1);
+                                                                oc.setEndindex((oc.getEndindex() - diff) + 1);
+                                                        } else {
+                                                                Console.traceln(Level.WARNING,
+                                                                                "End index of a Match before start. This should never happen");
+                                                        }
+                                                }
+                                        }
+                                        synchronized (appData) {
+                                                appData.detectedAndReplacedTasks = true;
+                                        }
+                                        final ISequence task = matchAsSequence(appData, m);
+                                        final ISequenceInstance sequenceInstances = RuleUtils
+                                                        .createNewSubSequenceInRange(appData.getSessions()
+                                                                        .get(oc.getSequenceId()), oc
+                                                                        .getStartindex(), oc.getEndindex(), task,
+                                                                        taskFactory, taskBuilder);
+
+                                        // Adjust the length of the match regarding to the
+                                        // length of
+                                        // instance. (OptionalInstances may be shorter)
+                                        oc.setEndindex((oc.getStartindex() + sequenceInstances
+                                                        .size()) - RuleUtils.missedOptionals);
+
+                                        replacedOccurrences.add(oc);
+                                }
+                        }
+                }
+        }
+
         /**
          * The Class RuleApplicationData.
@@ -1072 +1122 @@
                 private final ObjectDistanceSubstitionMatrix submat;
 
-                /**
-                 * HashMap for keeping track in which sequence which replacement has
-                 * been performed. Neccessary for updating the indices of other
-                 * occurrences accordingly
-                 */
-                private HashMap<Integer, List<MatchOccurrence>> replacedOccurences;
-                
-                private Queue<Match>[] plannedReplacements;
-                
+                private PriorityQueue<Match>[] plannedReplacements;
 
                 /** The list of all found matches */
@@ -1105 +1147 @@
                 /** Stop Watch to measure performance */
                 private final StopWatch stopWatch;
-                
-                
 
                 /**
@@ -1125 +1165 @@
                         this.detectedAndReplacedTasks = true;
                 }
-                
+
                 private void initializeQueues(int size) {
-                        plannedReplacements = new Queue[size];
-                        for(int i=0;i<size;i++) {
+                        plannedReplacements = new PriorityQueue[size];
+                        for (int i = 0; i < size; i++) {
                                 plannedReplacements[i] = new PriorityQueue<Match>();
                         }
@@ -1137 +1177 @@
                 }
 
-                public void setPlannedReplacements(Queue<Match>[] plannedReplacements) {
-                        this.plannedReplacements = plannedReplacements;
-                }
-
                 /**
                  * Detected and replaced tasks.
@@ -1151 +1187 @@
 
                 /**
-                 * Gets the matchseqs.
-                 *
-                 * @return the matchseqs
+                 * Gets the match sequences.
+                 *
+                 * @return the match sequences
                  */
                 public LinkedList<Match> getMatchseqs() {
@@ -1187 +1223 @@
 
                 /**
-                 * Gets the replaced occurrences.
-                 *
-                 * @return the replaced occurences
-                 */
-                public HashMap<Integer, List<MatchOccurrence>> getReplacedOccurrences() {
-                        return replacedOccurences;
-                }
-
-                /**
                  * Gets the result.
                  *
@@ -1223 +1250 @@
 
                 /**
-                 * Gets the submat.
-                 *
-                 * @return the submat
+                 * Gets the substitution matrix.
+                 *
+                 * @return the substitution matrix
                  */
                 private ObjectDistanceSubstitionMatrix getSubmat() {
@@ -1244 +1271 @@
                  *
                  * @param task
-                 *            can be called when new tasks are created to keep track of all newly created tasks
+                 *            can be called when new tasks are created to keep track of
+                 *            all newly created tasks
                  */
                 private void newTaskCreated(ITask task) {
@@ -1270 +1298 @@
 
                 /**
-                 * Sets the replaced occurences.
-                 *
-                 * @param replacedOccurences
-                 *            the replaced occurences
-                 */
-                public void setReplacedOccurences(
-                                HashMap<Integer, List<MatchOccurrence>> replacedOccurences) {
-                        this.replacedOccurences = replacedOccurences;
-                }
-
-                /**
                  * Update substitution matrix.
                  */
@@ -1290 +1307 @@
         }
 
-        
-
 }