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:

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:

Attributes

all_loops[RW]
bounds[RW]
id[RW]
indices[RW]
pattern[RW]
tA[RW]
tD[RW]
tE[RW]
tN[RW]
tS[RW]

Public Class Methods

new(reference,id,inner_loops,outer_loops,var_declarations,verbose) click to toggle source

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

array_includes_local_vars(array, loop_vars) click to toggle source

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
dependent?(index,loops) click to toggle source

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
depends_on?(var) click to toggle source

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
find_extreme(position,index,loops) click to toggle source

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
get_base_offset(index) click to toggle source

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

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

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

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

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
step_smaller_than_num_elements?() click to toggle source

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
string_includes_local_vars(string) click to toggle source
    # 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
to_arc() click to toggle source

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
to_copy(id) click to toggle source

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

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