# HG changeset patch # User Nina Engelhardt # Date 1331722959 -3600 # Node ID f81ebd8d3b85ccc0f3390314ea06b7435116d8cb # Parent 81c3737cd23bd769a3005caf3cafb59187479e55 holistic model general description diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic.bib --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic.bib Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,7 @@ +@misc{countersdesign, + title = {Performance Counters for Linux Design description}, + publisher = {Linux Source Code}, + url = {linux/tools/perf/design.txt}, + edition = {}, + year = {} +} diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Animating_a_processor.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Animating_a_processor.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,337 @@ + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + Scheduler + + WorkingState + + + Namespace + + + + Matcher and Manipulator + + + + + + + + + Scheduler + + WorkingState + + + Namespace + + + + Matcher and Manipulator + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/App_processor_hier_w_animators.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/App_processor_hier_w_animators.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,709 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + Task-processor + Function-processor + Primitiveprocessor + create_task( work_fn, data )work_fn( input ) { a = input + 1 inner_fn( a ) } + + + + + + + + + + + + + + + + + + + + + + + + work_fn + + + + Snapshot in the sequence of processor creations. Here, the task processor has been created. It, in turn,has caused creation of a function-processor, which behaves according to the work_fn specification. Lastly,that function-processor has caused creation of a primitive-processor, which has the behavior of the "+"primitive operation. The physical processor on the bottom plane has alternately animated the task-animator, function-animator, and the primitive "+" animator. At the time of this snapshot, the physical processor is animatingthe primitive "+" animator, while the function-animator and task-animator are stalled. Note that the language is sequential, so the code of the work_fn can only be animated (ultimately) byone physical processor. Also, the other physical processor hasn't been assigned to a task as of thissnapshot. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Application_processor_hierarchy.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Application_processor_hierarchy.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,593 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Task-processor + Function-processor + Function-processor + Primitive-processors + + + + + + + + Task-processor + Function-processor + Primitiveprocessor + create_task( work_fn, data )work_fn( input ) { a = input + 1 inner_fn( a ) } + work_fn + inner_fn + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Application_processor_hierarchy_in_plane.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Application_processor_hierarchy_in_plane.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,560 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + Task-processor + Function-processor + Primitiveprocessor + create_task( work_fn, data )work_fn( input ) { a = input + 1 inner_fn( a ) } + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1495 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Top-LevelVirtual Machine + + + Submit work to top-level + + Hierarchy of Grid "Computer" + PhysicalMachine + + + PhysicalMachine + + + + + Rack inMachine + + + + Rack inMachine + + + + + + + + + + + . + . + . + + . + . + . + + + Board inRack + + + + Board inRack + + + + . + . + . + + + Socket onBoard + + + + Socket onBoard + + + + . + . + . + + + + Core inSocket + + + + Core inSocket + + + + . + . + . + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy_w_divider_etc.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy_w_divider_etc.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1571 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + GP Core(Runs Linux) + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + Mem + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy_w_mem_type.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy_w_mem_type.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1561 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Top-LevelVirtual Machine + + + Submit work to top-level + + Hierarchy of Grid "Computer" + PhysicalMachine + + + PhysicalMachine + + + + + Rack inMachine + + + + Rack inMachine + + + + + + + + + + + . + . + . + + . + . + . + + + Board inRack + + + + Board inRack + + + + . + . + . + + + Socket onBoard + + + + Socket onBoard + + + + . + . + . + + + + Core inSocket + + + + Core inSocket + + + + . + . + . + + + Shared, coherent + Shared, coherent + Distributed + Distributed + Distributed + Distributed + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy_w_runtimes.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Grid_hierarchy_w_runtimes.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1561 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Top-LevelVirtual Machine + + + Submit work to top-level + + Hierarchy of Grid "Computer" + PhysicalMachine + + + PhysicalMachine + + + + + Rack inMachine + + + + Rack inMachine + + + + + + + + + + + . + . + . + + . + . + . + + + Board inRack + + + + Board inRack + + + + . + . + . + + + Socket onBoard + + + + Socket onBoard + + + + . + . + . + + + + Core inSocket + + + + Core inSocket + + + + . + . + . + + + Runtime + Runtimes + Runtimes + Runtimes + Runtimes + Runtimes + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/How_use_VMS.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/How_use_VMS.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,532 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + Application + + + + + WrapperLib + + + + VMS + + + + Plugin + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/IterTimeVsThinkTime.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/IterTimeVsThinkTime.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1421 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + Think-Time + Quality + + + + Think-Time + Quality + + Single Point + + + + + + Quality + Latency + Bandwidth + + + + + + + Quality + Latency + Bandwidth + + + + + + Quality + Latency + Bandwidth + + + + + + + Think-Time + Iter-Time + Comm-Time + + + Comm Time + Iter Time + + + + + + + Think-Time + Iter-Time + Comm-Time + + Comm Time + Iter Time + + + + + + + Think-Time + Iter-Time + Comm-Time + + + Comm Time + Iter Time + + + + + + + Think-Time + Quality + + + + + + Think-Time + Iter-Time + Comm-Time + + + + + + Think-Time + Iter-Time + Comm-Time + + + + + + + Think-Time + Comm-Time + Iter-Time + + + + + + + Think-Time + Iter-Time + Comm-Time + + + + + + + + Think-Time + Iter-Time + Comm-Time + + + + + + Think-Time + Iter-Time + Comm-Time + + + + Worst Case + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Logical_view_of_system.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Logical_view_of_system.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,644 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + void updateSlicing(SliceStruc *slicingStruc) { for( col = rightStartCol; col < rightEndCol; col += colIncrement ) { rightSliceStartCols[ sliceIdx ] = col; colIncrement = (int) colAccumulator; if( colIncrement == 0 ) colIncrement = 1;//apply at end curr iter colAccumulator -= colIncrement; } } + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Application + SlaveVPs + Physical Core + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Logical_view_of_system_2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Logical_view_of_system_2.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,765 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + void updateSlicing(SliceStruc *slicingStruc) { for( col = rightStartCol; col < rightEndCol; col += colIncrement ) { rightSliceStartCols[ sliceIdx ] = col; colIncrement = (int) colAccumulator; if( colIncrement == 0 ) colIncrement = 1;//apply at end curr iter mutex_lock( someMutex, animatingVP ); } } + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Application + SlaveVPs + Physical Core + + + + + + + + MasterVP + + + PluginCode + + + + Core Controller + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Logical_view_of_system_3.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Logical_view_of_system_3.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,645 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + void updateSlicing(SliceStruc *slicingStruc) { for( col = rightStartCol; col < rightEndCol; col += colIncrement ) { rightSliceStartCols[ sliceIdx ] = col; colIncrement = (int) colAccumulator; if( colIncrement == 0 ) colIncrement = 1;//apply at end curr iter mutex_lock( someMutex, animatingVP ); } } + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Application + Language Animator + Physical Core + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Loop.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Loop.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,181 @@ + + + +image/svg+xmlScheduleDo WorkCommDataCommStatus +Loop + \ No newline at end of file diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,2127 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + This shows a UCC, the forest of processor-trees created in accordance with it, and the loop-graph measured from the processor-forest.The UCC is a dependency graph among SSR-delimited tasksNote that the processor trees are different for different tasks -- that's because there is different code-data for each task.Each task has a decision made for it by the SSR-animator, of which physical animator to animate the instruction-data of the task.The Loop-graph has one node for each of those decisions. The boxes inside the node account for the time used by physical animatorson all the things related to that task: checking constraints, picking a free one, assigning physical animator, communicating data, animatingthe processor-tree, and updating constraint-conditions (to trigger next round of checking constraint conditions) + + + + + + + W + + + + C + St + S + + + + + + + W + + + + + C + St + S + + + + + + W + + + + + C + St + S + + + + + W + + + + + C + St + S + + + + Syn + + + + + + + + + + UCC + Processor Forest + Loop Graph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,2922 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + Timelines added, to show how physical-processor time is broken up and allocated to boxes in the Loop-graphThis shows a UCC, the forest of processor-trees created in accordance with it, and the loop-graph measured from the processor-forest.The UCC is a dependency graph among SSR-delimited tasksNote that the processor trees are different for different tasks -- that's because there is different code-data for each task.Each task has a decision made for it by the SSR-animator, of which physical animator to animate the instruction-data of the task.The Loop-graph has one node for each of those decisions. The boxes inside the node account for the time used by physical animatorson all the things related to that task: checking constraints, picking a free one, assigning physical animator, communicating data, animatingthe processor-tree, and updating constraint-conditions (to trigger next round of checking constraint conditions) + + + + + + + W + + + + C + St + S + + + + + + + W + + + + + C + St + S + + + + + + W + + + + + C + St + S + + + + + W + + + + + C + St + S + + + + Syn + + + + + + + + + + UCC + Processor Forest + Loop Graph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + SSR-AnimSchedTask 2 + Func-AnimCreate Fn.PTask 2 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 2 + 3 + 4 + 1 + Prim-AnimCreate +.PTask 2 + WaitData forTask 2 + Prim-AnimAnimateTask 2 + WaitStatus fromTask 2 + + + + + + + + + + + + + + + + + + + + + + + + + + + PhysicalProcessor 1timeline + PhysProc 1 + PhysProc 2 + SSRAnimator + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines_2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines_2.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,3823 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + On the top-left is the top level of the used-UCC, showing the units scheduled by SSR. In the middle is an indication of how the original application-UCC collapses into this used-UCC. Each processor-tree is a collapsed level of UCC that is inside one of the scheduled units (As shown, none of the functions invokes a VMS escape). It shows that the processors in the trees are different for different tasks, because there is different code for each task-type.On the right is the loop-graph, with scheduling decisions made according to the top level of UCC. The Loop-graph has one node for each unit. The node accounts for the physical-processor time taken by the scheduling decision, communication of the task data, the work, and getting completion status back to the scheduler for the next decision. Scheduling includes checking constraints, picking a free one, and assigning to a physical animator. This implies that the "St" box accounts time the phys animator loses while notice of work completion travels to update the constraint-conditions (which in turn triggers the next round of checking constraint conditions).On the bottom, the timeline shows how physical-processor time is broken up, and allocated to boxes in the Loop-graph. Notice that the C language and SSR animator levels collapse down onto the physical animator level.That's because the C language animator reuses the processor's instruction fetch, Program Counter, and Branch machinery as its own animator implementation. The SSR animator is a bit different -- it can be see as either "handing off" to the C animator, or also reusing the physical processors' animation machinery. Except that SSR has its own scheduler implementation, so that part of the SSR animator is physical, and so the SSR tasks show up in the used-UCC. + + + + + + + W + + + + C + St + S + + + + + + W + + + + C + St + S + + + + + + + + + + + W + + + + + C + St + S + + + + + + W + + + + + C + St + S + + + Syn + + + + + + + + W + + + + C + St + S + + + + + + + + W + + + + C + St + S + + + + + + + + + Loop Graph + + + SSR-AnimSchedTask 4 + Func-AnimCreate Fn.PTask 4 + Prim-AnimCreate +.PTask 4 + WaitData forTask 4 + Prim-AnimAnimateTask 4 + WaitStatus fromTask 4 + + + + + + + + + + + + + + + + + + + + + + + + + + + PhysicalProcessor 1timeline + + Processor Forest + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + PhysProc 1 + PhysProc 2 + SSR + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + C Lang. + Physical + Application + + 4 + 2 + 3 + 5 + 6 + 1 + + + + 1 + 2 + 3 + 5 + 4 + 6 + + Top level of Used-UCC + + + + + + 6 + 1 + + + + + + + 3 + 2 + 4 + 5 + + + + + + + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines_3.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines_3.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,5415 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + On the top-left is the top level of the used-UCC, showing the units scheduled by SSR. In the middle is an indication of how the original application-UCC collapses into this used-UCC. Each processor-tree is a collapsed level of UCC that is inside one of the scheduled units (As shown, none of the functions invokes a VMS escape). It shows that the processors in the trees are different for different tasks, because there is different code for each task-type.On the right is the loop-graph, with scheduling decisions made according to the top level of UCC. The Loop-graph has one node for each unit. The node accounts for the physical-processor time taken by the scheduling decision, communication of the task data, the work, and getting completion status back to the scheduler for the next decision. Scheduling includes checking constraints, picking a free one, and assigning to a physical animator. This implies that the "St" box accounts time the phys animator loses while notice of work completion travels to update the constraint-conditions (which in turn triggers the next round of checking constraint conditions).On the bottom, the timeline shows how physical-processor time is broken up, and allocated to boxes in the Loop-graph. Notice that the C language and SSR animator levels collapse down onto the physical animator level.That's because the C language animator reuses the processor's instruction fetch, Program Counter, and Branch machinery as its own animator implementation. The SSR animator is a bit different -- it can be see as either "handing off" to the C animator, or also reusing the physical processors' animation machinery. Except that SSR has its own scheduler implementation, so that part of the SSR animator is physical, and so the SSR tasks show up in the used-UCC. + + + + + + + W + + + + C + St + S + + + + + + W + + + + C + St + S + + + + + + + + + + + W + + + + + C + St + S + + + + + + W + + + + + C + St + S + + + Syn + + + + + + + + W + + + + C + St + S + + + + + + + + W + + + + C + St + S + + + + + + + + + Loop Graph + + + SSR-AnimSchedTask 4 + Func-AnimCreate Fn.PTask 4 + Prim-AnimCreate +.PTask 4 + WaitData forTask 4 + Prim-AnimAnimateTask 4 + WaitStatus fromTask 4 + + + + + + + + + + + + + + + + + + + + + + + + + + + PhysicalProcessor 1timeline + + Processor Forest + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + PhysProc 1 + PhysProc 2 + SSR + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + C Lang. + Physical + Application + + 4 + 2 + 3 + 5 + 6 + 1 + + + + 1 + 2 + 3 + 5 + 4 + 6 + + Top level of Used-UCC + + + + + + 6 + 1 + + + + + + + 3 + 2 + 4 + 5 + + + + + + + + + + + + + + + + + + + + W + + + + C + St + S + + + + + + W + + + + C + St + S + + + + + + + + + + + W + + + + + C + St + S + + + + + + W + + + + + C + St + S + + + Syn + + + + + + + + W + + + + C + St + S + + + + + + + + W + + + + C + St + S + + + + + + + + Loop Graph + 1 + 2 + 3 + 5 + 4 + 6 + + + Syn + + + Top level of Used-UCC + + + + + + 6 + 1 + + + + + + + 3 + 2 + 4 + 5 + + + + + + + + + + + + + + + + 6 + + + + + + + Top level of Used-UCC + + + + + + 6 + 1 + + + + + + + 3 + 2 + 4 + 5 + + + + + + + + + + + + + + + + Top level of Used-UCC + + + + + + 6 + 1 + + + + + + + 3 + 2 + 4 + 5 + + + + + + + + + + + + + + + + 7 + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/LoopGraph_seq.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/LoopGraph_seq.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,826 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + Syn + + + + + + + W + + + + C + St + S + + + + + + + + W + + + + C + St + S + + + + + + + + + + W + + + + C + St + S + + + + + + + + + W + + + + C + St + S + + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/LoopGraph_w_dep_graph.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/LoopGraph_w_dep_graph.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,827 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + W + + + + C + St + S + + + + + + + W + + + + + C + St + S + + + + + + + W + + + + + C + St + S + + + + + + W + + + + + C + St + S + + + + Syn + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Portability_eco-system.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Portability_eco-system.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1936 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + VMS + + Hardware 2 + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + + + + OpenMP + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 1 + App 2 + App 3 + + + + Cilk + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 4 + App 5 + App 6 + + + + NewLang + + C + + C + + + + Source-to-C-plus-Lib-calls + + + + + + + + App 7 + App 8 + App 9 + + + + + + + + + + + + + + HW Class B + HW Class A + + VMS + + Hardware 1 + + + + + VMS + + Hardware 3 + + + + VMS + + Hardware 4 + + + + VMS + + Hardware 5 + + + + Eco-system for performant portability + Source-to-C + Plugins + Hardware + + + + + + + + + + + Interfaces + C Compilers + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Portability_eco-system_middle_layer.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Portability_eco-system_middle_layer.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1960 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + VMS + + Hardware 2 + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + + + + OpenMP + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 1 + App 2 + App 3 + + OpenMP + + + Cilk + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 4 + App 5 + App 6 + + Cilk + + + NewLang + + C + + C + + + + Source-to-C-plus-Lib-calls + + + + + + + + App 7 + App 8 + App 9 + + + + + + + NewLang + + + + + + + + HW Class B + HW Class A + + VMS + + Hardware 1 + + + + + VMS + + Hardware 3 + + + + VMS + + Hardware 4 + + + + VMS + + Hardware 5 + + + + Eco-system for performant portability + Source-to-C + "Middle-ware" + + + + + + + + + + + C Compilers + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Portability_software_stack.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Portability_software_stack.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,2013 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + VMS + + Hardware 2 + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + + + + OpenMP + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 1 + App 2 + App 3 + + + + Cilk + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 4 + App 5 + App 6 + + + + NewLang + + C + + C + + + + Source-to-C-plus-Lib-calls + + + + + + + + App 7 + App 8 + App 9 + + + + + + + + + + + + + + HW Class B + HW Class A + + VMS + + Hardware 1 + + + + + VMS + + Hardware 3 + + + + VMS + + Hardware 4 + + + + VMS + + Hardware 5 + + + + Software Stack for performant portability + Application + HardwareAbstraction + + + + + + + + + + + LanguageToolchain + + + + + + + + LanguageRuntime + Hardware + + Change + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Portability_software_stack_w_BLISS.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Portability_software_stack_w_BLISS.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1958 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + VMS + + Hardware 2 + + OpenMP+PPlugin + + MPI+PPlugin + + NewLang+PPlugin + + OpenMP+PPlugin + + MPI+PPlugin + + NewLang+PPlugin + + + + + OpenMP+P + Transformand Extract + + + + + CC + + CC + + + + App 1 + App 2 + App 3 + MPI+P + Transformand Extract + + + + + CC + + CC + + + + App 4 + App 5 + App 6 + NewLang+P + CC + + CC + + Transformand Extract + + + + App 7 + App 8 + App 9 + + + + + + + + + + HW Class B + HW Class A + VMS + + Hardware 1 + + VMS + + Hardware 3 + + VMS + + Hardware 4 + + VMS + + Hardware 5 + + Software Stack for Performant Portability + Application + HardwareAbstraction + + + + + + + + + + + LanguageToolchain + + + + + + + + LanguageRuntime + Hardware + + Changes + Constant + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Runtime_Hierarchy_on_Grid_machine.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Runtime_Hierarchy_on_Grid_machine.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1936 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + VMS + + Hardware 2 + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + OpenMPPlugin + + CilkPlugin + + NewLangPlugin + + + + + + + OpenMP + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 1 + App 2 + App 3 + + + + Cilk + + Source-to-C-plus-Lib-calls + + + + + + + + + C + + C + + + + + + + + App 4 + App 5 + App 6 + + + + NewLang + + C + + C + + + + Source-to-C-plus-Lib-calls + + + + + + + + App 7 + App 8 + App 9 + + + + + + + + + + + + + + HW Class B + HW Class A + + VMS + + Hardware 1 + + + + + VMS + + Hardware 3 + + + + VMS + + Hardware 4 + + + + VMS + + Hardware 5 + + + + Eco-system for performant portability + Source-to-C + Plugins + Hardware + + + + + + + + + + + Interfaces + C Compilers + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Scheduling_Loop.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Scheduling_Loop.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,260 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + Schedule + Do Work + CommData + CommStatus + + + + + + + Scheduling Loop + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Scheduling_states_2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Scheduling_states_2.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,210 @@ + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + Blocked + + + + Ready + + + + + + Progressing + + Suspended + + + + Animated + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Sync_split_2_parts.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Sync_split_2_parts.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,462 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + Semantics + + + + Order Access + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Time_in_VMS_1.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Time_in_VMS_1.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,407 @@ + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + Suspend Point 1 + + + + Suspend Point 2 + + Program Time 1 + TraceSegment + + + + Suspend Point 1 + + + + Suspend Point 2 + + Program Time 2 + TraceSegment + + + + Tie Point + + VirtualTime + + + + + + + Suspend 1,1start + + + + Suspend2, 1 start + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Time_in_VMS_2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Time_in_VMS_2.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,480 @@ + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + Ordering Point 1.1 + + + + Ordering Point 1.2 + + Slave 1 Time + TraceSegment 1.2 + + + + Ordering Point 2.1 + + + + Ordering Point 2.2 + + Slave 2 Time + TraceSegment 2.2 + + + + + VirtualTime + + + + + + + + + + + + + + + TraceSegment 1.1 + AnimatedtoBlocked + Ready toAnimated + + + AnimatedtoBlocked + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/Time_layers.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/Time_layers.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,198 @@ + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Program Time + + Program Time + + Physical Time + + Scheduler Time + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_and_circles.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_and_circles.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,669 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Application-Unit + Task-Units + Function-Units + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + UCC Hierarchy + + + + + + + + + Task-processor + Function-processor + Primitiveprocessor + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_and_processors.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_and_processors.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1200 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Application-Unit + Task-Units + Function-Units + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + UCC Hierarchy + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_hierarchy.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_hierarchy.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,600 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Application-Unit + Task-Units + Instructions + OS-animator + createsapplication-unit + + + Language-animator + + + + assigns application-unit + + + + + + + + Physical-processors + + + + + + + + + + + assigns task-units + to animator + to physical processors + assign instructions + to function units + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_hierarchy_units_only.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_hierarchy_units_only.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,280 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + Application-Unit + Task-Units + Instructions + MatrixMultiply + subMatrixMult() + mul ecx + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_hierarchy_vs_processors.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_hierarchy_vs_processors.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,839 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + Application-Unit + Task-Units + Function-Units + + Application-processor ("process") + + + + + + + + Task-processors + + + + + + + + + causes creation of task-processors + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + function-processors + + + + + + + + + UCC Hierarchy + Processors Created During Run + and communicates to them + and communicates to them + and communicates to them + causes creation of primitive-processors + causes creation of function-processors + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_related_to_LoopG.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_related_to_LoopG.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,800 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Application-Unit + Task-Units + Instructions + OS-animator + createsapplication-unit + + + Language-animator + + + + assigns application-unit + + + + + + + + Physical-processors + + + + + + + + + + + assigns task-units + to animator + to physical processors + assign instructions + to function units + + + + + + Schedule + Do Work + CommData + CommStatus + + + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_related_to_processor_hierarchy.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_related_to_processor_hierarchy.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1255 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + work_fn + inner_fn + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + This shows a UCC and the forest of processor-trees created in accordance with it. (The UCC is a dependency graph among SSR-delimited tasks)Note that the processor trees are different for different tasks -- that's because there is different code-data for each task. + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/UCC_with_many_to_many.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/UCC_with_many_to_many.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,424 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 1:1 + + + + + + + + + + + + 1:1 + Group-Constructs in UCCOne from tail group to one from head group + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/VMS-core__internal_workings.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/VMS-core__internal_workings.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,1042 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + Green = VMS-core + Blue = application + Red = plug-in + + + + + + + Physical-Core Controller(pthread) + + + core_loop + + + + + + slaveVP + + + top_VP_fn + + + Shared Parallelism-Semantic State + + + + + + Switch VPs + Switch VPs + + + schedSlot + + schedSlot + slaveVP ptr + + + Repeated for each physical core + 1 + + + + + comm_handler_fn + + + + scheduler_fn + + + + localMasterVP + + + + + master_loop + + + + readyQ + + + + 2 + 3 + 4 + 5 + + 6 + 8 + 9 + 10 + + + Switch VPs + Switch VPs + 7 + 11 + (Animated) + (Blocked) + (Ready) + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/VMS-core__plugins.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/VMS-core__plugins.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,196 @@ + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + VMS-core + + Master + + LanguagePlug-in + SemanticState + PhysicalState + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Figs_for_Nina/multiple_cores.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Figs_for_Nina/multiple_cores.svg Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,612 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + Slave VPs + + + + Heap + + + + Plugin Data + + + + Core + + M + + CC + + + + Core + + M + + CC + + + Shared Memory + + diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/Makefile Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,24 @@ +# Makefile + +TOPFILE=holistic_model_detailed + + +all:: $(TOPFILE).pdf + + +%.pdf: %.tex + pdflatex $< + #bibtex $(TOPFILE) + pdflatex $< + pdflatex $< + + +clean:: + rm -f $(TOPFILE).aux $(TOPFILE).log $(TOPFILE).out\ + $(TOPFILE).bbl $(TOPFILE).blg *~ + + +really-clean: clean + rm -f $(TOPFILE).pdf $(TOPFILE)-2.pdf + +# Ende des Makefiles. diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/holistic_model.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/holistic_model.tex Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,370 @@ +\documentclass{beamer} + +\usetheme[incompatible]{BerlinAES} + +\usepackage[utf8]{inputenc} +%\usepackage[ngerman]{babel} +\usepackage{listings,fancyvrb} +\usepackage{graphicx} + +\setcounter{tocdepth}{4} + +\begin{document} +\title{The Holistic Model of Parallel Computation} +\author{Nina Engelhardt} +\date{\today} +\fachgebiet{AES} + + +\begin{frame}{~} +\maketitle +\end{frame} + + +\begin{frame}{Table of Contents} +\tableofcontents +\end{frame} + +\section{Introduction} +\begin{frame}{Introduction} +\begin{itemize} +\item Investigate interaction between Application, Hardware, and Scheduling +\item Created models that isolate these interactions: +\begin{itemize} +\item Processor representation of software +\item Animation of processors +\item Unit Constraint Collection +\item Loop Graph +\end{itemize} +\item Models are previewed in reverse order +\end{itemize} +\end{frame} + +\begin{frame}{Motivation: get Spectra} +\begin{minipage}[t]{0.33\linewidth} +\begin{figure} +\includegraphics[width=0.9\textwidth]{Figs_for_Nina/IterTimeVsThinkTime.pdf} +\end{figure} +\end{minipage} +\begin{minipage}[t]{0.65\linewidth} +Spectra +\begin{itemize} +\item Identifies important characteristics of App and Hardware for Scheduling +\item Shows effect of those characteristics +\item Given App-HW combo, tells best result (for a given metric) +\item Evaluate effectiveness of given scheduler strategy for specific App-HW combo +\end{itemize} +\end{minipage} +\end{frame} + +\begin{frame}{Spectra} +\begin{figure} +\includegraphics[width=0.7\textwidth]{Figs_for_Nina/IterTimeVsThinkTime.pdf} +\end{figure} +\end{frame} + +\begin{frame}{Preview} +\begin{itemize} +\item Spectra come from Loop Graph +\item Loop Graph relates software to hardware processors +\item Shape of Loop Graph is bounded by UCC +\item Understanding Loop Graph requires understanding Animation \& Processor representation of software +\end{itemize} +\end{frame} + +\AtBeginSection[] +{ + \begin{frame} + \frametitle{Outline} + \tableofcontents[currentsection] + \end{frame} +} + + +\section{Background} + +\subsection{Processor representation of software} + +\begin{frame}{Processor representation of software} +\begin{itemize} +\item Represent application as a forest of processors +\item Ex: function call is creation of a processor +\item Behaviour of processor is specified by function body +\item Each loop in Loop Graph creates one SW processor and assigns a physical animator to it +\end{itemize} +\begin{figure} +\includegraphics[width=0.8\textwidth]{Figs_for_Nina/Application_processor_hierarchy.pdf} +\end{figure} +\end{frame} + +\subsection{Animation} + +\begin{frame}{Animation} +\begin{itemize} +\item Time in application is moved forward by an animator +\item Multiple levels of animator, physical animators at the bottom +\item Task animator picks physical animator for tasks +\end{itemize} +\begin{figure} +\includegraphics[width=0.6\textwidth]{Figs_for_Nina/App_processor_hier_w_animators.pdf} +\end{figure} +\end{frame} + +%\begin{frame}{Specification and Execution} +%\begin{itemize} +%\item Specification (source code) + data $\rightarrow$ everything needed to create a \emph{processor} +%\item Execution: \emph{animate} a specified \emph{processor} +%\end{itemize} +% +%\end{frame} + + + +\AtBeginSubsection[] +{ + \begin{frame} + \frametitle{Outline} + \tableofcontents[currentsection,currentsubsection] + \end{frame} +} + + +\section{The Holistic Model} + +\begin{frame}{A Tale of Two Models} +Two Models: +\begin{itemize} +\item \emph{Unit Constraint Collection} +\begin{itemize} +\item isolates scheduling-relevant information about the application +\item composed of schedulable units and constraints on scheduling +\item used to generate all valid loop graphs +\end{itemize} +\item \emph{Loop Graph}\begin{itemize} +\item relates scheduling behaviour to execution metrics +\item one loop for each scheduling event +\item loop is broken into phases +\item each phase has a measurement +\item measurements are values in spectra +\end{itemize} +\end{itemize} +\end{frame} + +\subsection{Unit Constraint Collection} + +\begin{frame}{Unit Constraint Collection} +\begin{itemize} +\item Separate scheduling-specific information from other language details $\rightarrow$ generally applicable model + +\item Represents all valid scheduling choices for an application +\item Extracts from the application schedulable units and constraints +\begin{itemize} +\item Language constructs that invoke scheduling decisions mark boundaries of schedulable units +\end{itemize} +\end{itemize} +\end{frame} + +\begin{frame}{Units} +\begin{itemize} +%\item Primitives that can be animated +\item Unit = specification + data = potential processor +\begin{itemize} +\item Specification = everything between two scheduling-relevant constructs +\end{itemize} +\item Whether processor actually gets created may depend on data or other factors +\end{itemize} + +\begin{figure} +\includegraphics[width=0.8\textwidth]{Figs_for_Nina/UCC_related_to_processor_hierarchy.pdf} + +\end{figure} +\end{frame} + + + +\begin{frame}{Scheduling constraints} + +\begin{itemize} +\item Usually partial order +\item Some models impose total order: sequential models +\item Some models allow more complicated relationships +\item Constraints on unit order +\begin{itemize} +\item due to communication +\item due to limitations of model +\end{itemize} +\end{itemize} + +\begin{figure} +\centering +\includegraphics[height= 0.35\textheight]{Figs_for_Nina/test.png} +\hspace{3em} +%\caption{The most common form of UCC: a dependency graph} +\includegraphics[height= 0.35\textheight]{Figs_for_Nina/UCC_with_many_to_many.pdf} +\end{figure} + +\end{frame} + +\subsection{Loop Graph} + +\begin{frame}{Loop Graph} +\begin{minipage}[t]{0.7\linewidth} +\begin{itemize} +\item Accounts for all physical-animator time. +\item Each node is a loop, comprised of phases, annotated with measurements +\item Internal edges represent accumulation +\item External edges represent scheduling condition update +\end{itemize} +\vspace{-2em} +\begin{figure} +\includegraphics[width=0.7\linewidth]{Figs_for_Nina/LoopGraph_w_dep_graph.pdf} +\end{figure} +\end{minipage} +\begin{minipage}[t]{0.29\linewidth} +\begin{figure} +\includegraphics[width=0.7\linewidth]{Figs_for_Nina/LoopGraph_seq.pdf} +\end{figure} +\end{minipage} +%For each loop, note which unit was chosen and how long each step took. +\end{frame} + + +\begin{frame}{Details of Loop} + +Loop consists of several elements: + +\begin{itemize} +\item Check which units have all constraints satisfied, pick one to animate +\item Communication +\item Do the work of the unit +\item Advise scheduler of completion +\end{itemize} +\begin{figure} +\includegraphics[width=0.4\textwidth]{Figs_for_Nina/Loop.pdf} +\end{figure} +\end{frame} + +\begin{frame}{Loop Graph} +\begin{figure} +\includegraphics[width=0.8\textwidth]{Figs_for_Nina/LoopG_to_Processors_to_UCC_w_timelines.pdf} +\end{figure} +\end{frame} + +\section{Validating the Model} + +\begin{frame}{Validating the Model} +\begin{itemize} +\item For spectra conclusions to be correct, loop graph needs to be correct $\rightarrow$ need to verify it +\item Check that execution time predictions from loop graph match with actual execution time +\item For a given App-Hardware combo, have to measure each box in the loop +\item Compare length of critical path to actual execution time +\end{itemize} +\end{frame} + +\begin{frame}{Recording the Loop Graph} +\begin{itemize} +\item Monitor program run in VMS +\item Note scheduling choices (= which VPs get scheduled) +\item Note constraints (= communication dependencies in SSR) +\item Measure length of phases +\end{itemize} +\end{frame} + +\begin{frame}{Tasks in VMS} +\begin{itemize} +\item Schedulable units are delimited by VMS calls +\item Loop phases correspond to blocks in VMS code +\item Read hardware counters at borders of each blocks +\item Record choices of plugin scheduler\_fn +\item Recording communication in SSR's comm\_handler\_fn +%\item Everything except blocking/unblocking happens in MasterLoop or CoreLoop code +%\item Blocking is VMS code +%\item Unblocking is Plugin code +\end{itemize} +\begin{figure} +\includegraphics[width=0.8\textwidth]{Figs_for_Nina/VMS-core__internal_workings.pdf} +\end{figure} +\end{frame} + +\begin{frame}{Using recorded data} +Transforming recorded data into Loop Graph: +\begin{itemize} +\item Scheduling choices \& communication records $\rightarrow$ nodes and edges +\item Counter values $\rightarrow$ phase measurements +\item Find critical path \& compare to total run length of app +\end{itemize} +\end{frame} + + +\begin{frame}{Loop Graph} +\begin{figure} +\centering +\includegraphics[height=0.8\textheight]{Figs_for_Nina/loopg1.png}~ +\includegraphics[height=0.8\textheight]{Figs_for_Nina/loopg2.png} +\end{figure} +\end{frame} + +\section[Outlook]{Simulator for Scheduler-Application-Hardware interactions} + +\begin{frame}{Outlook} +\begin{itemize} +\item Replace hardware with simulator and replace application with UCC +\item Record same things from simulation as we got from VMS +\item Construct loop graph +\item Use it to generate spectra +\item In simulator, systematically control scheduling choices +\item Correlate spectra features to scheduling choices +\begin{itemize} +\item Overall best possible result +\item Best category of scheduler for app on hardware +\item Performance of given scheduling approach +\item Sensitivity of app-HW combo to scheduling +\end{itemize} +%\item Obtain runtime behaviour under various scheduling strategies +\end{itemize} +\end{frame} + +\begin{frame}{The End} +\begin{center} +Thank you for your time. + +Questions? +\end{center} +\end{frame} + +\end{document} + +\begin{frame}{Title} +\begin{itemize} +\item +\end{itemize} +\end{frame} +basic model of computation + +how to animate a Processor? + +Processor, at every level, a collection of computational units that need to communicate data + +semantics fixed, but order not always + +constraints on unit animation order +-due to communication +-due to limitations of model + +animators = limited resources + +process of animation: +-pick unit to animate +-fetch data (communication) +-do work described in unit +-sync, if necessary +-return status + +each animator loops through these steps -> can be represented as a graph. +edges = status communication + +scheduling = making choices about how to construct loop graph + +hierarchy of animators -> hierarchy of units + +最終決定　早業P⇒音ずれP⇒イカサマP⇒風呂場P⇒シャイP⇒緊張P⇒トリッP⇒早業P⇒七色P⇒ヲタP⇒万能P⇒早業P diff -r 81c3737cd23b -r f81ebd8d3b85 0__Papers/holistic_model/holistic_model_detailed.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/holistic_model/holistic_model_detailed.tex Wed Mar 14 12:02:39 2012 +0100 @@ -0,0 +1,167 @@ +\documentclass[a4paper, + 12pt, + pdftex, + headings=normal, + headinclude=false, + footinclude=false, + DIV16 + ]{scrartcl} + +\usepackage[utf8]{inputenc} +\usepackage{listings} +\usepackage{graphicx} +\usepackage{subfig} + +\bibliographystyle{plain} + +\begin{document} +\title{The Holistic Model} +\author{Nina Engelhardt} +\date{\today} +\maketitle +\tableofcontents + +Problem statement -- as processors multiply and communication models diversify in systems, increasing attention must be paid to scheduling, as the limiting factor for performance becomes the organisation of communications in such a way as to minimize stalling or idling in wait for data. In this context, good scheduling results can only be obtained if scheduled units follow Application logic. + +Purpose -- to investigate interactions between Application, Hardware, and Scheduler, and its effects on desired metrics - execution time, energy, etc. + +\section{Overview} + +Spectra serve to correlate execution behaviour -- as defined by the chosen metric -- with scheduling decisions. From these correlations we hope to extract, in turn, the important characteristics of Application and Hardware and their effects on execution, as well as the effectiveness of different types of Scheduler for different combinations of Application and Hardware. + +Spectra show + +The measurements to construct the Spectra are obtained by constructing a Loop Graph representing specific Scheduling choices made during one execution of a given Application on a given Hardware. The possible scheduling choices (and therefore, possible Loop Graphs) are limited by the Application, more specifically, by scheduling-relevant Application features such as communication. These scheduling-relevant features can be extracted, and the Application distilled into a collection of schedulable units and constraints on permissible schedulings called \emph{Unit Constraint Collection} (UCC). + +The Loop Graph builds upon a more fundamental model of software and its execution, called the Processor Representation of Software. + +%\section{Spectra} + + + +\section{Processor Representation of Software} + +In this model, everything is represented as \emph{processors}. Time in processors is moved forward through \emph{animation}. + +\subsection{Processors} +A processor is something that has a working state, a way to modify the working state, and an interface to communicate with other processors. To create a processor, two elements are needed: a specification, which describes the processor's behaviour, and input data to populate the initial working space. + +Take the following code: +\begin{lstlisting} +create_task(work_fn,data) + +work_fn(input) { + a = input + 1 + inner_fn(a) +} +\end{lstlisting} + +The first line creates a task processor (according to some non-represented specification that describes task behaviour). Its input data is a specification for a function processor, and some data to pass along. This task processor then requests the creation of a function processor according to the \lstinline+work_fn+ specification, which in practical terms of e.g. C code, means reserving space on the stack for local variables. The data is then placed in the working state of this new processor (the parts of the stack reserved for function parameters). + +This new processor's behaviour is defined in terms of a language primitive, +, and another function processor specification, \lstinline+inner_fn+. Language primitives are processors whose specification is provided by the language. The \lstinline+work_fn+ processor thus first sends data (\lstinline+input+ and \lstinline+1+) to the primitive \lstinline'+' processor, then waits for it to return a datum \lstinline+a+, which it then sends to the processor defined by \lstinline+inner_fn+. + +In a sequential language like C, the + processor dissipates before the \lstinline+inner_fn+ function is created. The tree in figure \ref{fig:app_processor_hierarchy} represents the application, but does not at any moment exist as such. + + +\begin{figure}[ht] +\centering +\includegraphics[width=0.9\textwidth]{Figs_for_Nina/Application_processor_hierarchy.pdf} +\caption{Processor hierarchy for an example task} +\label{fig:app_processor_hierarchy} +\end{figure} + +\subsection{Animation} + +Progress in an application is made by successive changes to the working state of its processors. The sequence of changes to a processor's working state constitutes its timeline, thereby defining the notion of time local to a processor. Time in different processors progresses independently, except where communication(, creation, dissipation) ties the timelines of two processors together (tiepoint). + +In the context of executing an application, the physical processor is seen as the fundamental, lowest-level animator. Time in the physical processor progresses spontaneously. Time in virtual processors progresses via animation: the virtual processor is loaded into the working state of another processor that knows how to emulate it, called an animator. This animator may be another virtual processor, or an actual physical processor. As the animator's time progresses and its working state changes, so does the working state of the animated processor (where several changes in animator working state can effect a single change in animatee working state). + +\begin{figure}[ht] +\centering +%\includegraphics[width=0.9\textwidth]{Figs_for_Nina/App_processor_hier_w_animators.pdf} +\caption{Animation hierarchy during execution of previous example task} +\label{fig:app_animation_hierarchy} +\end{figure} + +For an application written in C, the physical processor does not know how to animate a specific function processor, or a + primitive. It can only animate sequences of instructions. The C compiler will therefore generate processor descriptions in the form of sequences of instructions, animatable by the physical processor (i.e. assembler code), that in turn animate the language primitive processors or function processors. The physical processor will switch between these assembler processors and animate them each in turn. + +Animators are transparent to the application. When writing in C, nothing is known about the resulting animator code. Animators are also not unique: the same code may be animated by a large variety of processors, or even the brain of some developer reading the code. + +\emph{Scheduling}, then, in this model, is the choice of which virtual processor to animate with which animator at what time. This happens at each level of animation, though in some cases (e.g. sequential C program) there is no choice as by construction only one processor is ready to be animated at any one time. + +\section{UCC} + +When reasoning about scheduling decisions, the specifications of each individual processor are irrelevant, only a reduced amount of information is necessary: +\begin{itemize} +\item that the processor may be created +\item under what conditions it will be ready to be animated +\item optionally, how long it takes to be animated by a given animator. +\end{itemize} +This scheduling-relevant information can be isolated in the form of an (annotated) Unit Constraint Collection. + +The \emph{Unit Constraint Collection}, UCC for short, represents all valid scheduling choices for an application given specific data. It consists of schedulable units extracted from the application and of constraints pertaining to the scheduling of these units. It is a generally applicable model, since it discards all language and implementation details. + +In many cases it is possible to extract all possible UCCs from the application without the data. Then, a UCC-generator may be used instead of a concrete UCC for reasoning about the application's behaviour under scheduling. + +It is common to be able to extract a UCC-generator without being able to predict the UCC for a specific data set, for instance when control flow depends on data. + +\subsection{Units} +A unit is delimited by scheduling-relevant language constructs. The work between two invocations, then, is scheduled as a unit, hence the name. The code inbetween the two statements is, as per the processor model, a specification for a certain number of processors. Combined with data, these specifications become potential processors. When a unit gets scheduled, these processors are actually created. The UCC, especially when statically extracted, may contain units that are never actually scheduled. + +\begin{figure}[h] +\centering +\includegraphics[width=0.8\textwidth]{Figs_for_Nina/UCC_related_to_processor_hierarchy.pdf} +\caption{Units related to the processor hierarchy} +\label{fig:inside_ucc} +\end{figure} + +It is necessary to include this property into the UCC, as many parallel languages have non-deterministic features, and these features are essential for performance. For a simple example, if a calculation is split up into a number of parallel sub-calculations, and results need to be aggregated in the end, it is faster to accept results from the sub-calculations in whatever order they finish, instead of enforcing a pre-determined order with waits. + + +%unit contains tree of processors->needs group of animators?? + +\subsection{Constraints} + +Constraints in a UCC are relationships of order between units that the scheduling needs to respect/enforce. The kind of relationships are determined/limited by the language. In theory they may be of any form, but for the model to be useful in practice they usually need to be reduced to forms that are easy to reason about. + +Many models/languages limit constraints to dependencies between units, resulting in a partial ordering of units: the classic dependency graph (cf. fig. \ref{fig:dep_graph}). Sequential languages enforce total order of units. + +On the other hand, in cases such as the previously-described non-deterministic sequentialisation, more complex constraints are necessary, which are more difficult to represent graphically (an attempt is nonetheless made in fig. \ref{fig:many_to_many}). + +\begin{figure}[h] +\centering +\subfloat[Dependency Graph]{\label{fig:dep_graph}\includegraphics[width=0.2\textwidth]{Figs_for_Nina/test.png}} +\subfloat[Non-deterministic sequentialisation]{\label{fig:many_to_many}\includegraphics[width=0.3\textwidth]{Figs_for_Nina/UCC_with_many_to_many.pdf}} +\caption{Different types of constraints} +\label{fig:constraint_types} +\end{figure} + +\subsection{Levels of UCC} +%each level of UCC is one level of animator scheduling +%some levels get collapsed when decisions get re-used/deferred + +Whenever the application is not directly written for a physical animator, but for a virtual animator (essentially all code except assembler), the intermediary layers of animator may make choices about how to animate a unit. In particular, they will often break up units into smaller units and assign them to sub-animators. In this case, additional, animator-implementation-dependent scheduling decisions can be observed during execution, but they are "invisible" from the original application. + +Thus several levels of UCC, one for each level of animator, can be observed during animation. + +A good example case is Java bytecode. Even if the application code is sequential and never invokes the scheduler -- i.e. the application UCC consists of a single unit -- the application is rarely executed at once and with a fixed animator hierarchy, as it would be if all animators were considering it as a single unit. Instead, the scheduler in the JVM (a virtual animator that can animate Java bytecode) will assign different portions of the unit to different animators: some parts will be interpreted, others will be just-in-time compiled. Both the interpreter and the compiled code are implementations of animators that can animate application sub-units, but the interpreter is a slower animator that can animate all kinds of units while the compiled code is a fast animator that only knows how to animate this one specific type of unit (same code, but generally for any data). These different Java animators are animated by a collection of virtual physical animators -- vulgo: OS threads -- which again are scheduled invisibly to the higher levels of animator. To top it all, the physical animator will itself cut up the code into smaller units -- instructions, sometimes sub-instructions -- that it dispatches to different animators (functional units). + +In a simple, interpreted system, the relationship between the levels is straightforward: each animator will consider the unit it is animating in its individuality, and only make scheduling decisions about its constituting parts, while keeping any constraints on the unit as a whole intact. In this case, any conclusion drawn from the higher levels of UCC is still valid in the lower levels. + +However, we generally consider it acceptable for an animator to do whatever it wants, as long as the end result is the same as the one that would have been obtained by following the simplistic model outlined above. Thus, many animators perform \emph{optimizations}, and construct lower level UCCs that no longer conform to all the constraints or unit boundaries laid out in the higher levels. + +(Indeed, many programming languages contain unnecessarily broad constraints in order to make the mental model of the language easy to understand and to use. These superfluous constraints will then in many cases be detected by an optimizer and ignored.) + +This introduces two problems: for UCC analysis, either the transformations an animator implementation is likely to apply need to be known in addition to the source-code-derived UCC, or the actual dynamically generated UCC needs to be observed during animation. For the higher-level language schedulers, dynamic optimizations introduce variability and unpredictability of animation metrics such as execution time, communication amounts and times, etc, making it more difficult to make high-quality scheduling decisions. + +%animation->additional scheduling decisions->new level of ucc +%relation between levels of ucc defined by transformation that creates it (eg compilation) +%if we know something about transformation, we can say something about lower level only from higher level +%only lowest level is one that really determines what happens (?) + +\section{Scheduling Consequence Graph} +The Scheduling Consequence Graph (SCG) is a visual representation of the causality chain throughout the run of an application. + +\bibliography{../holistic}{} + +\end{document}