class Object
Constants
- ARROW
A string representing the production character (‘->’) of a species.
- ASSUME_VAL
Value to assume a variable to be
- DIM_SEP
A string representing the comma character (‘,’) to separate different ranges.
- INDENT
Set the tab size (currently: 2 spaces)
- NL
Set the newline character
- PIPE
A string representing the pipe character (‘|’) of a species.
- RANGE_SEP
A string representing the colon character (‘:’) to separate ranges in dimensions.
- WEDGE
A string representing the combination character (‘^’) of a species.
Public Instance Methods
Return the absolute value (if possible)
# File lib/common.rb 173 def abs(expr) 174 return expr.to_i.abs.to_s if expr.to_i.to_s == expr 175 return expr 176 end
Generate code from a combination of loops and statements (the body)
# File lib/adarwin/fusion.rb 155 def code_from_loops(loops,statements) 156 code = "" 157 158 # Start of the loops 159 definition = "int " 160 loops.each do |loop_datum| 161 increment = (loop_datum[:step] == '1') ? "#{loop_datum[:var]}++" : "#{loop_datum[:var]}=#{loop_datum[:var]}+#{loop_datum[:step]}" 162 code += "for(#{definition}#{loop_datum[:var]}=#{loop_datum[:min]}; #{loop_datum[:var]}<=#{loop_datum[:max]}; #{increment}) {" 163 end 164 165 # Loop body 166 statements.each do |statement| 167 code += statement.to_s 168 end 169 170 # End of the loops 171 loops.size.times{ |i| code += "}" } 172 173 C::Statement.parse(code) 174 end
Compare two expressions
# File lib/common.rb 179 def compare(expr1,expr2,loop_data,assumptions=[]) 180 comparison = simplify("(#{expr1})-(#{expr2})") 181 182 # Handle min/max functions 183 if comparison =~ /max/ || comparison =~ /min/ 184 return comparison 185 end 186 187 # Process the assumptions 188 assumptions.each do |assumption| 189 comparison = simplify(comparison.gsub(assumption[0],assumption[1])) 190 end 191 192 # Known comparison 193 if (comparison.to_i.to_s == comparison || comparison.to_f.to_s == comparison) 194 return 'eq' if (comparison.to_i == 0) 195 return 'gt' if (comparison.to_i > 0) 196 return 'lt' if (comparison.to_i < 0) 197 else 198 199 # Comparison based on loop data 200 get_vars(comparison).each do |var| 201 loop_data.each do |loop_datum| 202 if loop_datum[:var] == var 203 assumptions << [var,loop_datum[:min]] 204 #puts "WARNING: Modifying expression '(#{expr1}) vs (#{expr2})', assuming: #{var}=#{loop_datum[:min]}" 205 return compare(expr1,expr2,loop_data,assumptions) 206 end 207 end 208 end 209 210 # Comparison based on a guess 211 var = get_vars(comparison).first 212 assumptions << [var,ASSUME_VAL] 213 #puts "WARNING: Don't know how to compare '(#{expr1})' and '(#{expr2})', assuming: #{var}=#{ASSUME_VAL}" 214 return compare(expr1,expr2,loop_data,assumptions) 215 end 216 end
Create an if-statement in front of a statement
# File lib/adarwin/fusion.rb 147 def create_if(loop_var,reference_bound,loop_bound,code,condition) 148 if reference_bound != loop_bound 149 return C::Statement.parse("if(#{loop_var} #{condition} #{loop_bound}) { #{code.to_s} }") 150 end 151 return code 152 end
Find the exact maximum value of 2 expressions
# File lib/common.rb 152 def exact_max(expr1,expr2) 153 return expr1 if expr1 == expr2 154 comparison = simplify("(#{expr1})-(#{expr2})") 155 if (comparison.to_i.to_s == comparison || comparison.to_f.to_s == comparison) 156 return expr1 if (comparison.to_i == 0) 157 return expr1 if (comparison.to_i > 0) 158 return expr2 if (comparison.to_i < 0) 159 else 160 return "max(#{expr1},#{expr2})" 161 end 162 end
Find the exact minimum value of 2 expressions (based on the exact_max
method)
# File lib/common.rb 165 def exact_min(expr1,expr2) 166 return expr1 if expr1 == expr2 167 maximum = exact_max(expr1,expr2) 168 return (maximum == expr1) ? expr2 : ( (maximum == expr2) ? expr1 : maximum.gsub('max(','min(') ) 169 end
Determine whether kernel fusion is legal (see algorithm in paper/thesis)
# File lib/adarwin/fusion.rb 3 def fusion_is_legal?(a, b) 4 (a.writes + a.reads).each do |x| 5 (b.writes + b.reads).each do |y| 6 if (x.tN == y.tN) && (x.tA == 'write' || y.tA == 'write') 7 puts Adarwin::MESSAGE+"Evaluating #{x.to_arc} and #{y.to_arc} for fusion" 8 if x.tD.to_s != y.tD.to_s || x.tE.to_s != y.tE.to_s || x.tS.to_s != y.tS.to_s 9 puts Adarwin::MESSAGE+"Unable to fuse #{x.to_arc} and #{y.to_arc}" 10 return false 11 end 12 end 13 end 14 end 15 puts Adarwin::MESSAGE+"Applying fusion" 16 return true 17 end
Return the body of a loop nest
# File lib/adarwin/fusion.rb 135 def get_body(num_loops,code) 136 return code if num_loops == 0 137 if code.first.for_statement? && code.first.stmt 138 code = code.first 139 end 140 if code.for_statement? && code.stmt 141 return get_body(num_loops-1,code.stmt.stmts) 142 end 143 raise_error("Not a perfect nested loop") 144 end
Get the variables in an expression
# File lib/common.rb 79 def get_vars(expr) 80 expr.split(/\W+/).reject{ |s| (s.to_i.to_s == s || s.to_f.to_s == s || s == "") } 81 end
Perform the kernel fusion transformations
# File lib/adarwin/fusion.rb 21 def kernel_fusion(nests, settings) 22 23 # Select 24 candidates = nests.select{ |n| n.has_species? } 25 26 # Iterate 27 prev = nil 28 candidates.each_with_index do |nest,nest_index| 29 curr = nest 30 if prev 31 32 # Get the loop details 33 loops_prev = prev.code.get_direct_loops 34 loops_curr = curr.code.get_direct_loops 35 if loops_prev.size != loops_curr.size 36 puts Adarwin::MESSAGE+"Unable to apply fusion, loop count does not match" 37 next 38 end 39 40 # Only proceed if fusion is legal for this combination 41 if fusion_is_legal?(prev, curr) 42 fused_code = [] 43 44 # Get the bodies 45 body_curr = get_body(loops_curr.size,curr.code.clone) 46 body_prev = get_body(loops_prev.size,prev.code.clone) 47 48 # Fuse everything together: include if-statements for non-matching loop bounds 49 if settings == 1 50 51 # Create new loops 52 loops_target = [] 53 loops_prev.zip(loops_curr).each do |prevl,currl| 54 raise_error("Unequal step count #{prevl[:step]} versus #{currl[:step]}") if prevl[:step] != currl[:step] 55 minmin = exact_min(prevl[:min],currl[:min]) 56 maxmax = exact_max(prevl[:max],currl[:max]) 57 loop_datum = { :var => prevl[:var]+currl[:var], :min => minmin, :max => maxmax, :step => prevl[:step]} 58 loops_target.push(loop_datum) 59 60 # Replace all occurances of the fused loop variable in the current/previous codes 61 body_prev = body_prev.replace_variable(prevl[:var],loop_datum[:var]) 62 body_curr = body_curr.replace_variable(currl[:var],loop_datum[:var]) 63 64 # Set minimum if-statement conditions 65 body_prev = create_if(loop_datum[:var],minmin,prevl[:min],body_prev,'>=') 66 body_curr = create_if(loop_datum[:var],minmin,currl[:min],body_curr,'>=') 67 68 # Set maximum if-statement conditions 69 body_prev = create_if(loop_datum[:var],maxmax,prevl[:max],body_prev,'<=') 70 body_curr = create_if(loop_datum[:var],maxmax,currl[:max],body_curr,'<=') 71 end 72 73 # Generate the new code 74 fused_code.push(code_from_loops(loops_target,[body_prev,body_curr])) 75 76 # Create a prologue in case of mismatching loop bounds (experimental) 77 elsif settings == 2 78 79 # Generate the loop body 80 loops_target = [] 81 loops_prev.zip(loops_curr).each do |prevl,currl| 82 raise_error("Unequal step count #{prevl[:step]} versus #{currl[:step]}") if prevl[:step] != currl[:step] 83 body_prev = body_prev.replace_variable(prevl[:var],prevl[:var]+currl[:var]) 84 body_curr = body_curr.replace_variable(currl[:var],prevl[:var]+currl[:var]) 85 end 86 87 # Create the main loop nest 88 loops_target = [] 89 loops_prev.zip(loops_curr).each do |prevl,currl| 90 minmin = exact_min(prevl[:min],currl[:min]) 91 minmax = exact_min(prevl[:max],currl[:max]) 92 loop_datum = { :var => prevl[:var]+currl[:var], :min => minmin, :max => minmax, :step => prevl[:step]} 93 loops_target.push(loop_datum) 94 end 95 fused_code.push(code_from_loops(loops_target,[body_prev,body_curr])) 96 97 # Create the epilogue 98 body = [] 99 loops_target = [] 100 loops_prev.zip(loops_curr).each do |prevl,currl| 101 minmax = exact_min(prevl[:max],currl[:max]) 102 maxmax = exact_max(prevl[:max],currl[:max]) 103 loop_datum = { :var => prevl[:var]+currl[:var], :min => minmax, :max => maxmax, :step => prevl[:step]} 104 loops_target.push(loop_datum) 105 if prevl[:max] != currl[:max] 106 body = (prevl[:max] == maxmax) ? [body_curr] : [body_prev] 107 end 108 end 109 fused_code.push(code_from_loops(loops_target,body)) 110 end 111 112 # Add the newly created code to the original code 113 fused_code.each_with_index do |fused_codelet,nest_id| 114 puts fused_codelet 115 prev.code.insert_prev(fused_codelet) 116 117 # Create a new nest 118 nest = Adarwin::Nest.new(prev.level, fused_codelet, prev.id, prev.name.gsub(/_k(\d+)/,'_fused')+nest_id.to_s, prev.verbose, 1) 119 nests.push(nest) 120 end 121 122 123 # Set the other nests as to-be-removed 124 prev.removed = true 125 curr.removed = true 126 end 127 end 128 129 # Next nest 130 prev = nest 131 end 132 end
Find the maximum value of 2 expressions
# File lib/common.rb 103 def max(expr1,expr2,assumptions=[]) 104 return expr1 if expr2 == "" 105 comparison = simplify("(#{expr1})-(#{expr2})") 106 107 # Process the assumptions 108 assumptions.each do |assumption| 109 comparison = simplify(comparison.gsub(assumption[0],assumption[1])) 110 end 111 112 # Test to find the maximum 113 if (comparison.to_i.to_s == comparison || comparison.to_f.to_s == comparison) 114 return expr1 if (comparison.to_i == 0) 115 return expr1 if (comparison.to_i > 0) 116 return expr2 if (comparison.to_i < 0) 117 else 118 119 # Handle min/max functions 120 if comparison =~ /max/ || comparison =~ /min/ 121 return "max(#{expr1},#{expr2})" 122 end 123 124 # Find the maximum based on a guess 125 var = get_vars(comparison).first 126 assumptions << [var,ASSUME_VAL] 127 #puts "WARNING: Don't know how to find the max/min of '(#{expr1})' and '(#{expr2})', assuming: #{var}=#{ASSUME_VAL}" 128 return max(expr1,expr2,assumptions) 129 end 130 end
Find the minimum value of 2 expressions (based on the max method)
# File lib/common.rb 133 def min(expr1,expr2) 134 return expr1 if expr2 == "" 135 s1 = simplify(expr1) 136 s2 = simplify(expr2) 137 comparison = simplify("(#{s1})-(#{s2})") 138 139 # Handle min/max functions 140 if comparison =~ /max/ || comparison =~ /min/ 141 return s1 if s2 =~ /^max\(#{s1},.*\)$/ || s2 =~ /^max\(.*,#{s1}\)$/ 142 return s2 if s1 =~ /^max\(#{s2},.*\)$/ || s1 =~ /^max\(.*,#{s2}\)$/ 143 return "min(#{expr1},#{expr2})" 144 end 145 146 # Run the 'max' method 147 maximum = max(expr1,expr2) 148 return (maximum == expr1) ? expr2 : ( (maximum == expr2) ? expr1 : maximum.gsub('max(','min(') ) 149 end
First set of copyin/copyout optimisations (recursive)
# File lib/adarwin/memorycopies.rb 18 def perform_copy_optimisations1(nests,options) 19 previous = nil 20 nests.each_with_index do |nest,nest_index| 21 current = nest 22 if previous 23 24 # Remove spurious copies (out/in) 25 if options[:mem_remove_spurious] 26 previous.copyouts.each do |copyout| 27 current.copyins.each do |copyin| 28 if copyout.tN.to_s == copyin.tN.to_s && copyout.tD.to_s == copyin.tD.to_s 29 current.copyins.delete(copyin) 30 return perform_copy_optimisations1(nests,options) 31 end 32 end 33 end 34 end 35 36 # Remove spurious copies (out/out) 37 if options[:mem_remove_spurious] 38 previous.copyouts.each do |copyout| 39 current.copyouts.each do |other_copyout| 40 if copyout.tN.to_s == other_copyout.tN.to_s && copyout.tD.to_s == other_copyout.tD.to_s 41 previous.copyouts.delete(copyout) 42 return perform_copy_optimisations1(nests,options) 43 end 44 end 45 end 46 end 47 48 # Move copyins to the front 49 if options[:mem_copyin_to_front] 50 current.copyins.each do |copyin| 51 if previous.writes && !previous.writes.map{ |w| w.tN }.include?(copyin.tN) 52 previous.copyins.push(copyin) 53 current.copyins.delete(copyin) 54 return perform_copy_optimisations1(nests,options) 55 end 56 end 57 end 58 59 end 60 61 # Next nest 62 previous = nest 63 end 64 end
Second set of copyin/copyout optimisations (non-recursive)
# File lib/adarwin/memorycopies.rb 67 def perform_copy_optimisations2(nests,options) 68 nests.each_with_index do |nest,nest_index| 69 current = nest 70 71 # Move copyouts to the back 72 if options[:mem_copyout_to_back] 73 current.copyouts.each do |copyout| 74 nests.each_with_index do |other_nest,other_nest_index| 75 if other_nest.id > nest.id && other_nest.depth == nest.depth 76 if other_nest.writes && !other_nest.writes.map{ |w| w.tN }.include?(copyout.tN) 77 copyout.id = copyout.id+1 78 else 79 break 80 end 81 end 82 end 83 end 84 end 85 86 # Remove spurious copies (double in) 87 if options[:mem_remove_spurious] 88 current.copyins.each_with_index do |copyin,index| 89 current.copyins.each_with_index do |other_copyin,other_index| 90 if index != other_index 91 if copyin.tN.to_s == other_copyin.tN.to_s && copyin.tD.to_s == other_copyin.tD.to_s 92 if copyin.id > other_copyin.id 93 current.copyins.delete(copyin) 94 else 95 current.copyins.delete(other_copyin) 96 end 97 end 98 end 99 end 100 end 101 end 102 103 end 104 end
Third set of copyin/copyout optimisations (inter-level)
# File lib/adarwin/memorycopies.rb 107 def perform_copy_optimisations3(nests,options) 108 nests.each do |nest| 109 current = nest 110 children = get_children(nest) 111 if !children.empty? 112 113 # Inter-level loop optimisations (move to outer loop) 114 if options[:mem_to_outer_loop] 115 116 # Move copyouts to outer loops 117 max_id = children.map{ |c| 2*c.id+1 }.max 118 children.each do |child| 119 child.copyouts.each do |copyout| 120 to_outer_loop = true 121 nest.outer_loops.map{ |l| l[:var] }.each do |var| 122 to_outer_loop = false if copyout.depends_on?(var) 123 end 124 children.each do |other_child| 125 to_outer_loop = false if other_child.copyins.map{ |c| c.tN }.include?(copyout.tN) 126 end 127 to_outer_loop = false if copyout.get_sync_id < max_id 128 if to_outer_loop 129 copyout.id = nest.id 130 nest.copyouts.push(copyout) 131 child.copyouts.delete(copyout) 132 end 133 end 134 end 135 136 # Move copyins to outer loops 137 children.first.copyins.each do |copyin| 138 to_outer_loop = true 139 nest.outer_loops.map{ |l| l[:var] }.each_with_index do |var,lindex| 140 if copyin.depends_on?(var) 141 to_outer_loop = false 142 if copyin.tD[0].a == var && copyin.tD[0].b == var 143 loopinfo = nest.outer_loops[lindex] 144 if loopinfo[:step] == "1" 145 copyin.tD[0].a = loopinfo[:min] 146 copyin.tD[0].b = loopinfo[:max] 147 to_outer_loop = true 148 end 149 end 150 end 151 end 152 children.drop(1).each do |child| 153 to_outer_loop = false if child.copyins.map{ |c| c.tN }.include?(copyin.tN) 154 to_outer_loop = false if child.copyouts.map{ |c| c.tN }.include?(copyin.tN) && child != children.last 155 end 156 if to_outer_loop 157 nest.copyins.push(copyin) 158 children.first.copyins.delete(copyin) 159 end 160 end 161 162 end 163 end 164 end 165 end
Recursive copy optimisations
# File lib/adarwin/memorycopies.rb 4 def recursive_copy_optimisations(nests,options) 5 2.times do 6 perform_copy_optimisations1(nests,options) 7 perform_copy_optimisations2(nests,options) 8 nests.each do |nest| 9 children = get_children(nest) 10 recursive_copy_optimisations(children,options) if !children.empty? 11 end 12 perform_copy_optimisations3(nests,options) 13 perform_copy_optimisations3(nests,options) 14 end 15 end
Helper method to evaluate mathematical expressions, possibly containing symbols. This method is only used for readability, without it the code is functionally correct, but expressions might be larger than needed.
# File lib/common.rb 49 def simplify(expr) 50 raise_error('Invalid expression to simplify') if !expr 51 expr = expr.gsub(' ','') 52 53 # Immediately return if there is an array index in the expression 54 return expr if expr =~ /\[/ 55 56 # Handle min/max functions 57 if expr =~ /max/ || expr =~ /min/ 58 return expr 59 end 60 61 # Get all the variables 62 vars = get_vars(expr) 63 64 # Set all the variables 65 hash = {} 66 vars.uniq.each do |var_name| 67 hash[var_name.to_sym] = var :name => var_name 68 expr = expr.gsub(/\b#{var_name}\b/,"hash[:#{var_name}]") 69 end 70 71 # Simplify the string using the 'symbolic' gem. 72 symbolic_expr = eval(expr) 73 74 # Return the result as a string 75 return symbolic_expr.to_s 76 end
Solve a linear equality (work in progress)
# File lib/common.rb 84 def solve(equality,variable,forbidden_vars) 85 return "" if equality == "" 86 87 # Perform the subtitution of the current variable 88 expr = '-('+equality.gsub('=','-(').gsub(/\b#{variable}\b/,"0")+'))' 89 90 # Simplify the result 91 result = simplify(expr) 92 93 # Return the result or nothing (if it still contains forbidden variables) 94 vars = get_vars(result) 95 if vars & forbidden_vars == [] 96 return result 97 else 98 return "" 99 end 100 end