Class: Adarwin::Reference

Inherits:
Object
  • Object
show all
Defined in:
lib/adarwin/reference.rb

Overview

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)

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(reference, id, inner_loops, outer_loops, verbose) ⇒ Reference

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)



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/adarwin/reference.rb', line 31

def initialize(reference,id,inner_loops,outer_loops,verbose)
  @id = id
  
  # Initialise the 5-tuple (already fill in N and A)
  @tN = reference[:name]
  @tA = reference[:type]
  @tD = []
  @tE = []
  @tS = []
  
  # Set the inner loops as the loop nest's inner loop intersected with all
  # loops found for this statement. Beware of the difference between loops
  # of a loop nest and loops of a statement.
  @all_loops = reference[:loop_data]
  @inner_loops = inner_loops & @all_loops
  @outer_loops = outer_loops
  
  # Set the indices of the array reference (e.g. 2*i+4). The size of this
  # array is equal to the number of dimensions of the array.
  @indices = reference[:indices]
  
  # Set the if-statements for the reference. Process them together with the
  # loop start/end conditions to obtain a final set of conditions/bounds.
  @bounds = []
  loop_vars = @all_loops.map{ |l| l[:var]}
  @all_loops.each do |loop_data|
    conditions = [loop_data[:min],loop_data[:max]]
    reference[:if_statements].each do |if_statement|
      condition_if = if_statement.map{ |c| solve(c,loop_data[:var],loop_vars) }
      conditions = [
        max(conditions[0],condition_if[0]),
        min(conditions[1],condition_if[1])
      ]
    end
    @bounds << { :var => loop_data[:var], :min => conditions[0], :max => conditions[1] }
  end
  
  # Compute the domain (D) based on the bounds. The bounds are derived from
  # the if-statements and for-loops.
  @tD = @indices.map do |i|
    index_to_interval(i,@bounds)
  end
  
  # Compute the number of elements (E) accessed every iteration (the size).
  # TODO: Clean-up this method.
  @tE = @indices.map do |i|
    #if !dependent?(i,@all_loops)
    # puts "independent"
    # index_to_interval(i,@inner_loops)
    #else
      #puts "dependent"
      get_base_offset(i)
    #end
  end
  
  # Compute the step taken. There are 3 cases considered the index is: 1)
  # dependent on the outer loops, 2) dependent on the inner loops, or 3)
  # indepdent of any loops.
  @tS = @indices.map do |i|
    if dependent?(i,@inner_loops)
      index_to_interval(i,@inner_loops).length
    elsif dependent?(i,@outer_loops)
      get_step(i,@outer_loops)
    else
      '0'
    end
  end
  
  # If the step and the domain are equal in size, the step can also be set
  # to zero to reflect accessing the full array.
  @tS.each_with_index do |tS,index|
    if (tS == @tD[index].length) || (@tD[index].length == '1')
      @tS[index] = '0'
    end
  end
  
  # Print the result
  puts MESSAGE+"Found: #{to_arc}" if verbose
end

Instance Attribute Details

#all_loops ⇒ Object

Returns the value of attribute all_loops.



22
23
24
 
# File 'lib/adarwin/reference.rb', line 22

def all_loops
  @all_loops
end

#bounds ⇒ Object

Returns the value of attribute bounds.



21
22
23
 
# File 'lib/adarwin/reference.rb', line 21

def bounds
  @bounds
end

#id ⇒ Object

Returns the value of attribute id.



21
22
23
 
# File 'lib/adarwin/reference.rb', line 21

def id
  @id
end

#indices ⇒ Object

Returns the value of attribute indices.



21
22
23
 
# File 'lib/adarwin/reference.rb', line 21

def indices
  @indices
end

#pattern ⇒ Object

Returns the value of attribute pattern.



21
22
23
 
# File 'lib/adarwin/reference.rb', line 21

def pattern
  @pattern
end

#tA ⇒ Object

Returns the value of attribute tA.



20
21
22
 
# File 'lib/adarwin/reference.rb', line 20

def tA
  @tA
end

#tD ⇒ Object

Returns the value of attribute tD.



20
21
22
 
# File 'lib/adarwin/reference.rb', line 20

def tD
  @tD
end

#tE ⇒ Object

Returns the value of attribute tE.



20
21
22
 
# File 'lib/adarwin/reference.rb', line 20

def tE
  @tE
end

#tN ⇒ Object

Returns the value of attribute tN.



20
21
22
 
# File 'lib/adarwin/reference.rb', line 20

def tN
  @tN
end

#tS ⇒ Object

Returns the value of attribute tS.



20
21
22
 
# File 'lib/adarwin/reference.rb', line 20

def tS
  @tS
end

Instance Method Details

#dependent?(index, loops) ⇒ Boolean

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.

Returns:

  • (Boolean) 


150
151
152
153
154
155
156
157
158
159
 
# File 'lib/adarwin/reference.rb', line 150

def dependent?(index,loops)
  index.preorder do |node|
    if node.variable?
      loops.each do |for_loop|
        return true if (node.name == for_loop[:var])
      end
    end
  end
  return false
end

#depends_on?(var) ⇒ Boolean

Method to find out if the reference is dependent on a variable. It is used by the copy optimisations.

Returns:

  • (Boolean) 


249
250
251
252
253
254
255
256
257
258
 
# File 'lib/adarwin/reference.rb', line 249

def depends_on?(var)
  @indices.each do |index|
    index.preorder do |node|
      if node.variable?
        return true if (node.name == var)
      end
    end
  end
  return false
end

#find_extreme(position, index, loops) ⇒ Object

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.



136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/adarwin/reference.rb', line 136

def find_extreme(position,index,loops)
  index = index.clone
  2.times do
    loops.each do |for_loop|
      search = C::Variable.parse(for_loop[:var])
      replace = C::Expression.parse(for_loop[position])
      index = index.search_and_replace_node(search,replace)
    end
  end
  return simplify(index.to_s.gsub(';','').gsub(' ','').gsub("\t",''))
end

#get_base_offset(index) ⇒ Object

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.



115
116
117
118
119
120
121
122
123
 
# File 'lib/adarwin/reference.rb', line 115

def get_base_offset(index)
  index = index.clone
  @outer_loops.each do |for_loop|
    search = C::Variable.parse(for_loop[:var])
    replace = C::Expression.parse('0')
    index = index.search_and_replace_node(search,replace)
  end
  return index_to_interval(index,@inner_loops)
end

#get_references ⇒ Object

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.



243
244
245
 
# File 'lib/adarwin/reference.rb', line 243

def get_references
  return @indices.to_ary.map{ |i| i.to_s }
end

#get_step(index, loops) ⇒ Object

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.



164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
# File 'lib/adarwin/reference.rb', line 164

def get_step(index,loops)
  
  # Replace the loop indices with 0
  index1 = index.clone
  loops.each do |for_loop|
    search = C::Variable.parse(for_loop[:var])
    replace = C::Expression.parse('0')
    index1 = index1.search_and_replace_node(search,replace)
  end
  
  # Replace the loop indices with the loop step
  index2 = index.clone
  loops.each do |for_loop|
    search = C::Variable.parse(for_loop[:var])
    replace = C::Expression.parse(for_loop[:step])
    index2 = index2.search_and_replace_node(search,replace)
  end
  
  # Return the difference
  return abs(simplify("(#{index2})-(#{index1})"))
end

#get_sync_id ⇒ Object

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).



222
223
224
 
# File 'lib/adarwin/reference.rb', line 222

def get_sync_id
  (@tA == 'write') ? 2*@id+1 : 2*@id
end

#index_to_interval(index, loops) ⇒ Object

Method to fill in the ranges for an array reference. This is based on information of the loop nests. The output is an interval.



127
128
129
130
131
 
# File 'lib/adarwin/reference.rb', line 127

def index_to_interval(index,loops)
  access_min = find_extreme(:min,index,loops)
  access_max = find_extreme(:max,index,loops)
  return Interval.new(access_min,access_max,@all_loops)
end

#step_smaller_than_num_elements? ⇒ Boolean

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.

Returns:

  • (Boolean) 


229
230
231
232
233
234
235
236
237
238
239
 
# File 'lib/adarwin/reference.rb', line 229

def step_smaller_than_num_elements?
  @tS.each_with_index do |step,index|
    if step != '0'
      comparison = compare(step,@tE[index].length,@all_loops)
      if (comparison == 'lt')
        return true
      end
    end
  end
  return false
end

#to_arc ⇒ Object

Method to output the result as an array reference characterisation (ARC).



208
209
210
 
# File 'lib/adarwin/reference.rb', line 208

def to_arc
  return "(#{tN},#{tA},#{tD},#{tE},#{tS})".gsub('"','').gsub(' ','')
end

#to_copy(id) ⇒ Object

Method to output a copyin/copyout statement. This indicates the name (N), the domain (D), and a unique identifier.



214
215
216
 
# File 'lib/adarwin/reference.rb', line 214

def to_copy(id)
  @tN+'['+@tD.join(DIM_SEP)+']'+'|'+id.to_s
end

#to_species ⇒ Object

Method to output the result as algorithmic species. This reflects the algorithm as presented in the scientific paper.



188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/adarwin/reference.rb', line 188

def to_species
  if @tS.reject{ |s| s == "0"}.empty?
    if (@tA == 'read') # Full (steps length 0 and read)
      @pattern = 'full'
    else # Shared (steps length 0 and write)
      @pattern = 'shared'
    end
  elsif @tE.reject{ |s| s.length == "1"}.empty? # Element (sizes length 1)
    @pattern = 'element'
  elsif step_smaller_than_num_elements? # Neighbourhood (tS < tE)
    @pattern = 'neighbourhood('+@tE.join(DIM_SEP)+')'
  else # Chunk (tS >= tE)
    @pattern = 'chunk('+@tE.join(DIM_SEP)+')'
  end
  
  # Fill in the name and the domain and return the result
  return @tN+'['+@tD.join(DIM_SEP)+']'+PIPE+@pattern
end