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

abs(expr) click to toggle source

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
code_from_loops(loops,statements) click to toggle source

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(expr1,expr2,loop_data,assumptions=[]) click to toggle source

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_if(loop_var,reference_bound,loop_bound,code,condition) click to toggle source

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
exact_max(expr1,expr2) click to toggle source

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
exact_min(expr1,expr2) click to toggle source

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
get_body(num_loops,code) click to toggle source

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_vars(expr) click to toggle source

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
kernel_fusion(nests, settings) click to toggle source

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
max(expr1,expr2,assumptions=[]) click to toggle source

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
min(expr1,expr2) click to toggle source

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
perform_copy_optimisations1(nests,options) click to toggle source

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
perform_copy_optimisations2(nests,options) click to toggle source

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
perform_copy_optimisations3(nests,options) click to toggle source

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(nests,options) click to toggle source

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
simplify(expr) click to toggle source

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(equality,variable,forbidden_vars) click to toggle source

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