From 78def417b5fd79b82169ab3a9fef0cc5c4cf872e Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 12 Apr 2010 22:46:02 +0000 Subject: [PATCH] adjustments to stack-based method scheduling, debug controls, a micro benchmark, and interestingly with updated scheduling more benchmarks consistently exhibit the map reduce problem --- .../Analysis/Disjoint/DisjointAnalysis.java | 175 ++++++++++++------ Robust/src/Benchmarks/disjoint/makefile | 16 +- Robust/src/IR/State.java | 2 + Robust/src/Main/Main.java | 4 + .../disjoint/littleMapReduceTag/makefile | 4 +- .../disjoint/littleMapReduceTag/test.java | 34 +++- 6 files changed, 164 insertions(+), 71 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index f9f909de..49aebc74 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -368,7 +368,7 @@ public class DisjointAnalysis { // current descriptors to visit in fixed-point // interprocedural analysis, prioritized by // dependency in the call graph - protected Stack + protected Stack descriptorsToVisitStack; protected PriorityQueue descriptorsToVisitQ; @@ -391,7 +391,6 @@ public class DisjointAnalysis { protected Set calleesToEnqueue; - // maps a descriptor to its current partial result // from the intraprocedural fixed-point analysis-- // then the interprocedural analysis settles, this @@ -508,7 +507,7 @@ public class DisjointAnalysis { state.DISJOINTDVISITSTACKEESONTOP ) { descriptorsToVisitStack = - new Stack(); + new Stack(); } if( state.DISJOINTDVISITPQUE ) { @@ -657,32 +656,33 @@ public class DisjointAnalysis { // method's callees are updated, it must be reanalyzed protected void analyzeMethods() throws java.io.IOException { + // task or non-task (java) mode determines what the roots + // of the call chain are, and establishes the set of methods + // reachable from the roots that will be analyzed + if( state.TASK ) { - // This analysis does not support Bamboo at the moment, - // but if it does in the future we would initialize the - // set of descriptors to analyze as the program-reachable - // tasks and the methods callable by them. For Java, - // just methods reachable from the main method. - System.out.println( "Bamboo..." ); - Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + System.out.println( "Bamboo mode..." ); - while (taskItr.hasNext()) { - TaskDescriptor td = (TaskDescriptor) taskItr.next(); - if (!descriptorsToAnalyze.contains(td)) { - descriptorsToAnalyze.add(td); - descriptorsToAnalyze.addAll(callGraph.getAllMethods(td)); - } + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while( taskItr.hasNext() ) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + if( !descriptorsToAnalyze.contains( td ) ) { + // add all methods transitively reachable from the + // tasks as well + descriptorsToAnalyze.add( td ); + descriptorsToAnalyze.addAll( callGraph.getAllMethods( td ) ); + } } - + } else { + System.out.println( "Java mode..." ); + // add all methods transitively reachable from the // source's main to set for analysis mdSourceEntry = typeUtil.getMain(); descriptorsToAnalyze.add( mdSourceEntry ); - descriptorsToAnalyze.addAll( - callGraph.getAllMethods( mdSourceEntry ) - ); - + descriptorsToAnalyze.addAll( callGraph.getAllMethods( mdSourceEntry ) ); + // fabricate an empty calling context that will call // the source's main, but call graph doesn't know // about it, so explicitly add it @@ -690,43 +690,64 @@ public class DisjointAnalysis { descriptorsToAnalyze.add( mdAnalysisEntry ); } - // topologically sort according to the call graph so - // leaf calls are ordered first, smarter analysis order - // CHANGED: order leaf calls last!! - LinkedList sortedDescriptors = - topologicalSort( descriptorsToAnalyze ); - // add sorted descriptors to priority queue, and duplicate - // the queue as a set for efficiently testing whether some - // method is marked for analysis - int p = 0; - Iterator dItr = sortedDescriptors.iterator(); - while( dItr.hasNext() ) { - Descriptor d = dItr.next(); + // now, depending on the interprocedural mode for visiting + // methods, set up the needed data structures - mapDescriptorToPriority.put( d, new Integer( p ) ); - - if( state.DISJOINTDVISITSTACK || - state.DISJOINTDVISITSTACKEESONTOP - ) { - descriptorsToVisitStack.add( new DescriptorQWrapper( p, d ) ); - - } else if( state.DISJOINTDVISITPQUE ) { + if( state.DISJOINTDVISITPQUE ) { + + // topologically sort according to the call graph so + // leaf calls are last, helps build contexts up first + LinkedList sortedDescriptors = + topologicalSort( descriptorsToAnalyze ); + + // add sorted descriptors to priority queue, and duplicate + // the queue as a set for efficiently testing whether some + // method is marked for analysis + int p = 0; + Iterator dItr; + + // for the priority queue, give items at the head + // of the sorted list a low number (highest priority) + while( !sortedDescriptors.isEmpty() ) { + Descriptor d = sortedDescriptors.removeFirst(); + mapDescriptorToPriority.put( d, new Integer( p ) ); descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) ); + descriptorsToVisitSet.add( d ); + ++p; } - descriptorsToVisitSet.add( d ); - ++p; + } else if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + // if we're doing the stack scheme, just throw the root + // method or tasks on the stack + if( state.TASK ) { + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while( taskItr.hasNext() ) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + descriptorsToVisitStack.add( td ); + descriptorsToVisitSet.add( td ); + } + + } else { + descriptorsToVisitStack.add( mdAnalysisEntry ); + descriptorsToVisitSet.add( mdAnalysisEntry ); + } + + } else { + throw new Error( "Unknown method scheduling mode" ); } - // analyze methods from the priority queue until it is empty + + // analyze scheduled methods until there are no more to visit while( moreDescriptorsToVisit() ) { Descriptor d = null; if( state.DISJOINTDVISITSTACK || state.DISJOINTDVISITSTACKEESONTOP ) { - d = descriptorsToVisitStack.pop().getDescriptor(); + d = descriptorsToVisitStack.pop(); } else if( state.DISJOINTDVISITPQUE ) { d = descriptorsToVisitQ.poll().getDescriptor(); @@ -755,19 +776,36 @@ public class DisjointAnalysis { if( !rg.equals( rgPrev ) ) { setPartial( d, rg ); + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " complete graph changed, scheduling callers for analysis:" ); + } + // results for d changed, so enqueue dependents // of d for further analysis Iterator depsItr = getDependents( d ).iterator(); while( depsItr.hasNext() ) { Descriptor dNext = depsItr.next(); enqueue( dNext ); + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " "+dNext ); + } } if( state.DISJOINTDVISITSTACKEESONTOP ) { + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " contexts changed, scheduling callees for analysis:" ); + } + depsItr = calleesToEnqueue.iterator(); while( depsItr.hasNext() ) { Descriptor dNext = depsItr.next(); enqueue( dNext ); + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " "+dNext ); + } } calleesToEnqueue.clear(); } @@ -1145,6 +1183,11 @@ public class DisjointAnalysis { calleesToEnqueue.add( mdCallee ); } else { enqueue( mdCallee ); + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " context changed, scheduling callee: "+mdCallee ); + } + } } @@ -1191,6 +1234,10 @@ public class DisjointAnalysis { calleesToEnqueue.add( mdPossible ); } else { enqueue( mdPossible ); + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " callee hasn't been analyzed, scheduling: "+mdPossible ); + } } } else { @@ -1535,17 +1582,16 @@ public class DisjointAnalysis { protected void enqueue( Descriptor d ) { + if( !descriptorsToVisitSet.contains( d ) ) { - Integer priority = mapDescriptorToPriority.get( d ); if( state.DISJOINTDVISITSTACK || state.DISJOINTDVISITSTACKEESONTOP ) { - descriptorsToVisitStack.add( new DescriptorQWrapper( priority, - d ) - ); + descriptorsToVisitStack.add( d ); } else if( state.DISJOINTDVISITPQUE ) { + Integer priority = mapDescriptorToPriority.get( d ); descriptorsToVisitQ.add( new DescriptorQWrapper( priority, d ) ); @@ -1615,14 +1661,25 @@ public class DisjointAnalysis { } private AllocSite createParameterAllocSite( ReachGraph rg, - TempDescriptor tempDesc + TempDescriptor tempDesc, + boolean flagRegions ) { - FlatNew flatNew = new FlatNew( tempDesc.getType(), // type - tempDesc, // param temp - false, // global alloc? - "param"+tempDesc // disjoint site ID string - ); + FlatNew flatNew; + if( flagRegions ) { + flatNew = new FlatNew( tempDesc.getType(), // type + tempDesc, // param temp + false, // global alloc? + "param"+tempDesc // disjoint site ID string + ); + } else { + flatNew = new FlatNew( tempDesc.getType(), // type + tempDesc, // param temp + false, // global alloc? + null // disjoint site ID string + ); + } + // create allocation site AllocSite as = AllocSite.factory( allocationDepth, flatNew, @@ -1674,7 +1731,7 @@ private Set getFieldSetTobeAnalyzed(TypeDescriptor typeDesc){ if(i==dimCount){ as = alloc; }else{ - as = createParameterAllocSite(rg, tempDesc); + as = createParameterAllocSite(rg, tempDesc, false); } // make a new reference to allocated node hrnSummary = @@ -1732,7 +1789,7 @@ private Set getFieldSetTobeAnalyzed(TypeDescriptor typeDesc){ typeDesc.setArrayCount(0); if(!mapToExistingNode.containsKey(typeDesc)){ TempDescriptor tempDesc=new TempDescriptor(type.getSymbol(),typeDesc); - AllocSite as = createParameterAllocSite(rg, tempDesc); + AllocSite as = createParameterAllocSite(rg, tempDesc, false); // make a new reference to allocated node HeapRegionNode hrnSummary = rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one @@ -1796,7 +1853,7 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { TempDescriptor tempDesc = fm.getParameter(idx); - AllocSite as = createParameterAllocSite(rg, tempDesc); + AllocSite as = createParameterAllocSite(rg, tempDesc, true); VariableNode lnX = rg.getVariableNodeFromTemp(tempDesc); Integer idNewest = as.getIthOldest(0); HeapRegionNode hrnNewest = rg.id2hrn.get(idNewest); @@ -1847,7 +1904,7 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { //corresponding allocsite has already been created for a parameter variable. allocSite=as; }else{ - allocSite = createParameterAllocSite(rg, td); + allocSite = createParameterAllocSite(rg, td, false); } String strDesc = allocSite.toStringForDOT() + "\\nsummary"; diff --git a/Robust/src/Benchmarks/disjoint/makefile b/Robust/src/Benchmarks/disjoint/makefile index 7ae40543..fc58a826 100644 --- a/Robust/src/Benchmarks/disjoint/makefile +++ b/Robust/src/Benchmarks/disjoint/makefile @@ -13,7 +13,10 @@ BUILDSCRIPT=~/research/Robust/src/buildscript ## after capture (or let it run on normally) ## ################################################# -#DEBUGFLAGS= -disjoint-debug-callsite addInterOutput t6 50 5 false +#DEBUGFLAGS= -disjoint-debug-callsite addInterOutput t6 44 2 false +#DEBUGFLAGS= -disjoint-debug-callsite addElement addInterOutput 30 100 false + +#DEBUGFLAGS= -disjoint-debug-callsite setPartial reduceOutput 1 20 false ################################################# @@ -31,12 +34,17 @@ BUILDSCRIPT=~/research/Robust/src/buildscript ################################################# #SNAPFLAGS= -disjoint-debug-snap-method calcGoodFeatureTask 5 10 true #SNAPFLAGS= -disjoint-debug-snap-method calcGoodFeature 5 1 true -SNAPFLAGS= -disjoint-debug-snap-method t6 30 1 false -#SNAPFLAGS= -disjoint-debug-snap-method reduceOutput 5 50 true + +#SNAPFLAGS= -disjoint-debug-snap-method t6 20 1 false +#SNAPFLAGS= -disjoint-debug-snap-method addInterOutput 10 50 false + +#SNAPFLAGS= -disjoint-debug-snap-method reduceOutput 1 20 true #SNAPFLAGS= -disjoint-debug-snap-method setReduceFinish 5 50 true #SNAPFLAGS= -disjoint-debug-snap-method setPartial 1 50 true + + BAMBOOFLAGS= -recover JAVAFLAGS= -mainclass test @@ -47,7 +55,7 @@ VISITMODE= -disjoint-dvisit-stack-callees-on-top DEBUGMODE= -enable-assertions -disjoint-write-dots final -disjoint-alias-file aliases.txt normal -disjoint-desire-determinism RELEASEMODE= -disjoint-release-mode -disjoint-alias-file aliases.txt tabbed -BSFLAGS= -justanalyze -disjoint -disjoint-k 1 -flatirusermethods +BSFLAGS= -justanalyze -disjoint -disjoint-k 1 -flatirusermethods -flatirtasks all: echo 'pass another arg: ' diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index 97ee6e81..e12612dc 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -93,6 +93,8 @@ public class State { public boolean DISJOINTDVISITPQUE=false; public boolean DISJOINTDVISITSTACKEESONTOP=false; + public boolean DISJOINTDEBUGSCHEDULING=false; + public boolean OPTIONAL=false; public boolean ARRAYPAD=false; public boolean THREAD=false; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index c186b6c2..08e19581 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -255,6 +255,10 @@ public class Main { state.DISJOINTDVISITSTACKEESONTOP = true; state.DISJOINTDVISITPQUE = false; state.DISJOINTDVISITSTACK = false; + + + } else if( option.equals( "-disjoint-debug-scheduling" ) ) { + state.DISJOINTDEBUGSCHEDULING = true; } diff --git a/Robust/src/Tests/disjoint/littleMapReduceTag/makefile b/Robust/src/Tests/disjoint/littleMapReduceTag/makefile index cd46ac2b..2ae8bcc3 100644 --- a/Robust/src/Tests/disjoint/littleMapReduceTag/makefile +++ b/Robust/src/Tests/disjoint/littleMapReduceTag/makefile @@ -9,9 +9,9 @@ BAMBOOFLAGS= -recover #VISITMODE= -disjoint-dvisit-pqueue VISITMODE= -disjoint-dvisit-stack-callees-on-top -DEBUGMODE= -enable-assertions -disjoint-write-dots all -disjoint-alias-file aliases.txt normal -disjoint-desire-determinism +DEBUGMODE= -enable-assertions -disjoint-write-dots all -disjoint-alias-file aliases.txt normal -disjoint-desire-determinism -disjoint-debug-scheduling -BSFLAGS= -justanalyze -disjoint -disjoint-k 1 -flatirusermethods -flatirtasks +BSFLAGS= -justanalyze -disjoint -disjoint-k 1 #-flatirusermethods #-flatirtasks bamboo: $(BUILDSCRIPT) $(BAMBOOFLAGS) $(DEBUGMODE) $(VISITMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java diff --git a/Robust/src/Tests/disjoint/littleMapReduceTag/test.java b/Robust/src/Tests/disjoint/littleMapReduceTag/test.java index d05e749e..597447a8 100644 --- a/Robust/src/Tests/disjoint/littleMapReduceTag/test.java +++ b/Robust/src/Tests/disjoint/littleMapReduceTag/test.java @@ -4,19 +4,28 @@ task startup( StartupObject s{initialstate} ) { taskexit( s{!initialstate} ); } - +/* task reduceOutput( Master master{reduceoutput} ) { - master.setPartial( true ); + if( false ) { + master.addInterOutput(); + } else { + master.setPartial( true ); + taskexit( master{!reduceoutput} ); + } + taskexit( master{!reduceoutput} ); } - +*/ public class Master { flag reduceoutput; - boolean partial; + + boolean partial; + Vector[] interoutputs; public Master() { - this.partial = false; + this.partial = false; + this.interoutputs = new Vector[1]; } public boolean isPartial() { @@ -26,6 +35,19 @@ public class Master { public void setPartial( boolean partial ) { this.partial = partial || this.partial; } + + public void addInterOutput() { + interoutputs[0].addElement( new Vector() ); + } - public void assignMap() {} + public void assignMap() { + assignMap2(); + } + + public void assignMap2() { + assignMap3(); + } + + public void assignMap3() {} + } -- 2.34.1