class Adarwin::Reference
This class represents an array reference characterisation. This reference is constructed as a 5-tuple (tN,tA,tD,tE,tS) with the following information:
-
tN: The name of the reference.
-
tA: The access direction (read or write).
-
tD: The full domain accessed.
-
tE: The number of elements accessed each iteration (the size).
-
tS: The step of a accesses among iterations.
To be able to compute the 5-tuple, the reference also stores information about the loops and conditional statements to which the original array reference is subjected.
This class contains methods to perform among others the following:
-
Initialise the class and sets the 5-tuple (N,A,D,E,S)
-
Retrieve information on array indices
-
Print in different forms (species, ARC, copy/sync pragma’s)
Attributes
Public Class Methods
This method initialises the array reference class. It takes details of the reference itself and details of the loop nest it belongs to. The method performs among others the following:
-
It initialises the 5-tuple (N,A,D,E,S)
-
It constructs the sets of loops (all,inner,outer) for this reference
-
It computes the bounds based on loop data and on if-statements
-
It computes the domain (D), number of elements (E), and step (S)
# File lib/adarwin/reference.rb 31 def initialize(reference,id,inner_loops,outer_loops,var_declarations,verbose) 32 @id = id 33 34 # Initialise the 5-tuple (already fill in N and A) 35 @tN = reference[:name] 36 @tA = reference[:type] 37 @tD = [] 38 @tE = [] 39 @tS = [] 40 41 # Set the inner loops as the loop nest's inner loop intersected with all 42 # loops found for this statement. Beware of the difference between loops 43 # of a loop nest and loops of a statement. 44 @all_loops = reference[:loop_data] 45 @inner_loops = inner_loops & @all_loops 46 @outer_loops = outer_loops 47 48 # Set the list of all local variables 49 @var_declarations = var_declarations 50 51 # Set the indices of the array reference (e.g. 2*i+4). The size of this 52 # array is equal to the number of dimensions of the array. 53 @indices = reference[:indices] 54 55 # Set the if-statements for the reference. Process them together with the 56 # loop start/end conditions to obtain a final set of conditions/bounds. 57 @bounds = [] 58 loop_vars = @all_loops.map{ |l| l[:var]} 59 @all_loops.each do |loop_data| 60 conditions = [loop_data[:min],loop_data[:max]] 61 reference[:if_statements].each do |if_statement| 62 if !array_includes_local_vars(if_statement,loop_vars) 63 condition_if = if_statement.map{ |c| solve(c,loop_data[:var],loop_vars) } 64 conditions[0] = max(conditions[0],condition_if[0]) 65 conditions[1] = min(conditions[1],condition_if[1]) 66 end 67 end 68 @bounds << { :var => loop_data[:var], :min => conditions[0], :max => conditions[1] } 69 end 70 71 # Compute the domain (D) based on the bounds. The bounds are derived from 72 # the if-statements and for-loops. 73 @tD = @indices.map do |i| 74 index_to_interval(i,@bounds) 75 end 76 77 # Compute the number of elements (E) accessed every iteration (the size). 78 # TODO: Clean-up this method. 79 @tE = @indices.map do |i| 80 #if !dependent?(i,@all_loops) 81 # puts "independent" 82 # index_to_interval(i,@inner_loops) 83 #else 84 #puts "dependent" 85 get_base_offset(i) 86 #end 87 end 88 89 # Compute the step taken. There are 3 cases considered the index is: 1) 90 # dependent on the outer loops, 2) dependent on the inner loops, or 3) 91 # indepdent of any loops. 92 @tS = @indices.map do |i| 93 if dependent?(i,@inner_loops) 94 index_to_interval(i,@inner_loops).length 95 elsif dependent?(i,@outer_loops) 96 get_step(i,@outer_loops) 97 else 98 '0' 99 end 100 end 101 102 # If the step and the domain are equal in size, the step can also be set 103 # to zero to reflect accessing the full array. 104 @tS.each_with_index do |tS,index| 105 if (tS == @tD[index].length) || (@tD[index].length == '1') 106 @tS[index] = '0' 107 end 108 end 109 110 # Check for local variables in the domain. If they exist ask the user to fill 111 # in the bounds. 112 # TODO: Make this a command-line question asked to the user. For now, several 113 # known values are simply put here - for ease of automated testing. 114 @tD.each do |bounds| 115 116 # Bounds are equal (e.g. [t:t]) 117 if bounds.a == bounds.b && string_includes_local_vars(bounds.a) 118 119 # Default (assume 'char') 120 a = '0' 121 b = '255' 122 123 # Overrides (see notice above) 124 b = 'NUM_CLUSTERS-1' if bounds.a == 'cluster_index' 125 b = 'no_of_nodes-1' if bounds.b == 'id' 126 127 # Output a warning 128 puts WARNING+"Bounds of '#{bounds.a}' variable unknown, assuming #{a}:#{b}" 129 bounds.a = a 130 bounds.b = b 131 132 # Not equal but both problematic 133 elsif string_includes_local_vars(bounds.a) && string_includes_local_vars(bounds.b) 134 135 # Default (assume 'char') 136 a = '0' 137 b = '255' 138 139 # Overrides (see notice above) 140 b = 'no_of_nodes-1' if bounds.a == 'val2' 141 142 # Output a warning 143 puts WARNING+"Bounds of '#{bounds.a}' and '#{bounds.b}' variables unknown, assuming #{a}:#{b}" 144 bounds.a = a 145 bounds.b = b 146 147 end 148 end 149 150 151 # Print the result 152 puts MESSAGE+"Found: #{to_arc}" if verbose 153 end
Public Instance Methods
Method to find if local variables are included
# File lib/adarwin/reference.rb 305 def array_includes_local_vars(array, loop_vars) 306 vars = @var_declarations - loop_vars 307 array.each do |string| 308 vars.each do |decl| 309 if string =~ /\b#{decl}\b/ 310 return true 311 end 312 end 313 end 314 return false 315 end
Method to check whether the an index is dependent on a given set of loops. For example, A is independent of j, but dependent on i.
# File lib/adarwin/reference.rb 194 def dependent?(index,loops) 195 index.preorder do |node| 196 if node.variable? 197 loops.each do |for_loop| 198 return true if (node.name == for_loop[:var]) 199 end 200 end 201 end 202 return false 203 end
Method to find out if the reference is dependent on a variable. It is used by the copy optimisations.
# File lib/adarwin/reference.rb 293 def depends_on?(var) 294 @indices.each do |index| 295 index.preorder do |node| 296 if node.variable? 297 return true if (node.name == var) 298 end 299 end 300 end 301 return false 302 end
Substitute loop data with the upper-bound or lower-bound of a loop to find the minimum/maximum of an array reference. The body is executed twice, because a loop bound can be based on another loop variable.
# File lib/adarwin/reference.rb 180 def find_extreme(position,index,loops) 181 index = index.clone 182 2.times do 183 loops.each do |for_loop| 184 search = C::Variable.parse(for_loop[:var]) 185 replace = C::Expression.parse(for_loop[position]) 186 index = index.search_and_replace_node(search,replace) 187 end 188 end 189 return simplify(index.to_s.gsub(';','').gsub(' ','').gsub("\t",'')) 190 end
This method replaces loop variables for a given set of loops with 0. This basically gives us the offset of array references with respect to the loop variable. For example, A and A will give us [4,j+3] with repsect to an i-loop.
# File lib/adarwin/reference.rb 159 def get_base_offset(index) 160 index = index.clone 161 @outer_loops.each do |for_loop| 162 search = C::Variable.parse(for_loop[:var]) 163 replace = C::Expression.parse('0') 164 index = index.search_and_replace_node(search,replace) 165 end 166 return index_to_interval(index,@inner_loops) 167 end
Method to print out a human readable form of the array references (e.g. [4*i+6]). This is basically what the puts
method also does.
# File lib/adarwin/reference.rb 287 def get_references 288 return @indices.to_ary.map{ |i| i.to_s } 289 end
Method to retrieve the step for a given array index and loops. The method returns the difference between two subsequent iterations: one with the loop variable at 0 and one after the first increment.
# File lib/adarwin/reference.rb 208 def get_step(index,loops) 209 210 # Replace the loop indices with 0 211 index1 = index.clone 212 loops.each do |for_loop| 213 search = C::Variable.parse(for_loop[:var]) 214 replace = C::Expression.parse('0') 215 index1 = index1.search_and_replace_node(search,replace) 216 end 217 218 # Replace the loop indices with the loop step 219 index2 = index.clone 220 loops.each do |for_loop| 221 search = C::Variable.parse(for_loop[:var]) 222 replace = C::Expression.parse(for_loop[:step]) 223 index2 = index2.search_and_replace_node(search,replace) 224 end 225 226 # Return the difference 227 return abs(simplify("(#{index2})-(#{index1})")) 228 end
Method to print the unique identifier of the loop nest in terms of synchronisation statements to be printed. This is a per-reference id instead of a per-loop id, because it depends on the type of access (read or write).
# File lib/adarwin/reference.rb 266 def get_sync_id 267 (@tA == 'write') ? 2*@id+1 : 2*@id 268 end
Method to fill in the ranges for an array reference. This is based on information of the loop nests. The output is an interval.
# File lib/adarwin/reference.rb 171 def index_to_interval(index,loops) 172 access_min = find_extreme(:min,index,loops) 173 access_max = find_extreme(:max,index,loops) 174 return Interval.new(access_min,access_max,@all_loops) 175 end
Helper method for the to_species
method. This method compares the step with the number of elements accessed to determine which one is smaller. FIXME: This is based on the compare
method which might take a guess.
# File lib/adarwin/reference.rb 273 def step_smaller_than_num_elements? 274 @tS.each_with_index do |step,index| 275 if step != '0' 276 comparison = compare(step,@tE[index].length,@all_loops) 277 if (comparison == 'lt') 278 return true 279 end 280 end 281 end 282 return false 283 end
# File lib/adarwin/reference.rb 316 def string_includes_local_vars(string) 317 @var_declarations.each do |decl| 318 if string =~ /\b#{decl}\b/ 319 return true 320 end 321 end 322 return false 323 end
Method to output the result as an array reference characterisation (ARC).
# File lib/adarwin/reference.rb 252 def to_arc 253 return "(#{tN},#{tA},#{tD},#{tE},#{tS})".gsub('"','').gsub(' ','') 254 end
Method to output a copyin/copyout statement. This indicates the name (N), the domain (D), and a unique identifier.
# File lib/adarwin/reference.rb 258 def to_copy(id) 259 @tN+'['+@tD.join(DIM_SEP)+']'+'|'+id.to_s 260 end
Method to output the result as algorithmic species. This reflects the algorithm as presented in the scientific paper.
# File lib/adarwin/reference.rb 232 def to_species 233 if @tS.reject{ |s| s == "0"}.empty? 234 if (@tA == 'read') # Full (steps length 0 and read) 235 @pattern = 'full' 236 else # Shared (steps length 0 and write) 237 @pattern = 'shared' 238 end 239 elsif @tE.reject{ |s| s.length == "1"}.empty? # Element (sizes length 1) 240 @pattern = 'element' 241 elsif step_smaller_than_num_elements? # Neighbourhood (tS < tE) 242 @pattern = 'neighbourhood('+@tE.join(DIM_SEP)+')' 243 else # Chunk (tS >= tE) 244 @pattern = 'chunk('+@tE.join(DIM_SEP)+')' 245 end 246 247 # Fill in the name and the domain and return the result 248 return @tN+'['+@tD.join(DIM_SEP)+']'+PIPE+@pattern 249 end