class Adarwin::Dependence

This class represents the dependence tests. The dependence tests are not objects as such, the use of a class might therefore be a bit out of place. Instead, the class rather holds all methods related to dependence tests.

For an M-dimensional access, the problem of dependence testing is reduced to that of determining whether a system of M linear equations of the form >>> a_1*I_1 + a_2*I_2 + … + a_n*I_n = a_0 has a simultaneous integer solution satisfying the loop/if bounds given as >>> min_k <= I_k <= max_k

Currently, the following conservative tests are implemented:

In case the accesses are multi-dimensional, we perform a subscript-by- subscript checking. In other words, we test each dimension separately using the two tests. If we find a possible dependence in one dimension, we conclude that there is a dependence.

Attributes

result[RW]

Public Class Methods

new(access1,access2,verbose) click to toggle source

Method to initialise the dependence tests. This method actually already computes all the dependence tests and stores the result in a class variable. It takes as input the pair of accesses it needs to check for dependences.

   # File lib/adarwin/dependences.rb
28 def initialize(access1,access2,verbose)
29         @verbose = verbose
30         bounds = [access1.bounds,access2.bounds]
31         
32         # Iterate over the dimensions of the array reference
33         results = []
34         dimensions = [access1.indices.size,access2.indices.size].min
35         for dim in 1..dimensions
36                 ref1 = access1.indices[dim-1]
37                 ref2 = access2.indices[dim-1]
38                 loop_vars = [access1.all_loops.map{ |l| l[:var] },access2.all_loops.map{ |l| l[:var] }]
39                 
40                 # Conclude directly that there is no dependence if the references are
41                 # exactly the same.
42                 if ref1 == ref2
43                         results << false
44                         next
45                 end
46                 
47                 # TODO: Include the step in the dependence tests
48                 #p access1.tS[dim-1]
49                 
50                 # Get all variables, a linear equation, and the corresponding conditions
51                 all_vars, equation, conditions = get_linear_equation(ref1,ref2,bounds,loop_vars)
52                 
53                 # Conclude directly that there is no dependence if the variables are not
54                 # dependent on the loops.
55                 if equation[:ak].empty?
56                         results << false
57                         next
58                 end
59         
60                 # Perform the GCD test
61                 gcd_result = gcd_test(all_vars,equation)
62                 
63                 # End if the GCD test concludes that there are no dependences
64                 if gcd_result == false
65                         results << false
66                         
67                 # Continue with Banerjee if GCD concludes there might be dependences
68                 else
69                         ban_result = ban_test(all_vars,equation,conditions)
70                         results << ban_result
71                 end
72         end
73         
74         # Combine the results for all dimensions
75         if results.include?(true)
76                 @result = true
77         else
78                 @result = false
79         end
80 end

Public Instance Methods

ban_test(all_vars,equation,conditions) click to toggle source

This method implements the Banerjee test. This test takes loop bounds into consideration. The test is based on a linear equation in the form of >>> a_1*I_1 + a_2*I_2 + … + a_n*I_n = a_0 and loop bounds in the form of >>> min_k <= I_k <= max_k

The test proceeds as follows. First, the values a_k+ and a_k- are computed. Also, the bounds min_k and max_k are calculated from the loop conditions. Following, the test computes the extreme values ‘low’ and ‘high’. Finally, the test computes whether the following holds: >>> low <= a_0 <= high If this holds, there might be a dependence (method returns true). If this does not hold, there is definitely no dependence (method returns false).

    # File lib/adarwin/dependences.rb
134 def ban_test(all_vars,equation,conditions)
135         
136         # Pre-process the data to obtain the a_k+, a_k-, and lower-bounds and
137         # upper-bounds for a_k (min_k and max_k).
138         values = []
139         equation[:ak].each_with_index do |a,index|
140                 values << {
141                         :ak_plus => (a >= 0) ? a : 0,
142                         :ak_min => (a <= 0) ? -a : 0,
143                         :min_k => conditions[index][:min],
144                         :max_k => conditions[index][:max]
145                 }
146         end
147         
148         # Compute the extreme values 'low' and 'high'. This is done symbolically.
149         low, high = "0", "0"
150         values.each do |v|
151                 partial_low = simplify("
152                         (#{v[:ak_plus]}) * (#{v[:min_k]}) -
153                         (#{v[:ak_min]}) * (#{v[:max_k]})
154                 ")
155                 low = simplify("(#{low}) + (#{partial_low})")
156                 partial_high = simplify("
157                         (#{v[:ak_plus]}) * (#{v[:max_k]}) -
158                         (#{v[:ak_min]}) * (#{v[:min_k]})
159                 ")
160                 high = simplify("(#{high}) + (#{partial_high})")
161         end
162         
163         # Perform the actual test: checking if low <= a_0 <= high holds. This is
164         # implemented as two parts: check the lower-bound and check the upper-
165         # bound.
166         # FIXME: This method uses the +max+ which might make a guess.
167         base = equation[:a0]
168         test1 = (base.to_s == max(low,base.to_s))
169         test2 = (high == max(base.to_s,high))
170         ban_result = (test1 && test2)
171         
172         # Display and return the results
173         puts MESSAGE+"Banerjee '#{ban_result}' ---> (#{test1},#{test2}), '(#{low} <= #{base} <= #{high})'" if @verbose
174         return ban_result
175 end
gcd(args) click to toggle source

Implementation of a GCD method with any number of arguments. Relies on Ruby’s default GCD method. In contrast to the normal gcd method, this method does not act on a number, but instead takes an array of numbers as an input.

    # File lib/adarwin/dependences.rb
242 def gcd(args)
243         val = args.first
244         args.drop(1).each do |argument|
245                 val = val.gcd(argument)
246         end
247         return val
248 end
gcd_test(all_vars,equation) click to toggle source

This method implements the GCD test. The test is based on the computation of the greatest common divisor, giving it its name. The GCD test is based on the fact that a linear equation in the form of >>> a_1*I_1 + a_2*I_2 + … + a_n*I_n = a_0 has an integer solution if and only if the greatest common divisor of a_1, a_2,…,a_n is a divisor of a_0. The GCD test checks for this divisability by performing the division and checking if the result is integer.

This method returns true if there is an integer solution, not necessarily within the loop bounds. Thus, if the method returns true, there might be a dependence. If the method returns false, there is definitely no dependence.

TODO: If the result (division) is symbolic, can we conclude anything?

    # File lib/adarwin/dependences.rb
 96 def gcd_test(all_vars,equation)
 97         
 98         # Gather all the data to perform the test. Here, base represents a_0 and
 99         # data represents a_1,a_2,...,a_n.
100         base = equation[:a0]
101         data = equation[:ak]
102         
103         # Perform the greatest common divisor calculation and perform the division
104         result = gcd(data)
105         division = base/result.to_f
106         
107         # See if the division is integer under the condition that we can test that
108         if result == 0
109                 gcd_result = false
110         elsif division.class != Float
111                 gcd_result = true
112         else
113                 gcd_result = (division.to_i.to_f == division)
114         end
115         
116         # Display and return the result
117         puts MESSAGE+"GCD-test '#{gcd_result}' ---> (#{base})/(#{result}) = #{division}, gcd(#{data})" if @verbose
118         return gcd_result
119 end
get_linear_equation(access1,access2,bounds,all_loop_vars) click to toggle source

This method retrieves a linear equation from a pair of access. Accesses are transformed into a linear equation of the form >>> a_1*I_1 + a_2*I_2 + … + a_n*I_n = a_0 Additionally, this method returns a list of all variables and a list of loop bounds corresponding to the linear equation’s variables.

    # File lib/adarwin/dependences.rb
182 def get_linear_equation(access1,access2,bounds,all_loop_vars)
183         equation = { :a0 => 0, :ak => [] }
184         all_vars = []
185         conditions = []
186         hash = {}
187         
188         # Loop over the two accesses
189         [access1,access2].each_with_index do |access,index|
190                 access = simplify(access.to_s)
191                 
192                 # Get the variables (I_1 ... I_n) and modify the access expression
193                 vars = get_vars(access).uniq
194                 loop_vars = get_loop_vars(vars,all_loop_vars[index])
195                 all_vars = (all_vars + vars).uniq
196                 vars.each do |var_name|
197                         access = access.gsub(/\b#{var_name}\b/,"hash[:#{var_name}]")
198                 end
199                 
200                 # Create a hash of all the variables. For now, this is just the name of
201                 # the variable. The values will be set later. This uses the 'symbolic'
202                 # library.
203                 vars.each do |var_name|
204                         if !hash[var_name.to_sym]
205                                 hash[var_name.to_sym] = var :name => var_name
206                         end
207                         hash[var_name.to_sym].value = hash[var_name.to_sym]
208                 end
209                 
210                 # Find the constant term (a_0). This uses the +eval+ method together
211                 # with the 'symbolic' gem to compute the term.
212                 loop_vars.each do |var_name|
213                         hash[var_name.to_sym].value = 0
214                 end
215                 base = eval(access).value
216                 val = (index == 0) ? base : -base
217                 equation[:a0] = equation[:a0] + val
218                 
219                 # Find the other terms (a_1, a_2, ... a_n). This uses the +eval+ method
220                 # together with the 'symbolic' gem to compute the terms.
221                 loop_vars.each do |var_name|
222                         hash[var_name.to_sym].value = 1
223                         val = eval(access).value - base
224                         val = (index == 0) ? val : -val
225                         equation[:ak] << val
226                         hash[var_name.to_sym].value = 0
227                 end
228                 
229                 # Get the loop bound conditions corresponding to the linear equation's
230                 # variables.
231                 loop_vars.each do |var_name|
232                         conditions << bounds[index].select{ |c| c[:var] == var_name }.first
233                 end
234         end
235         return all_vars, equation, conditions
236 end
get_loop_vars(vars,all_loop_vars) click to toggle source

Method to obtain all variables in an array reference that are also loop variables.

    # File lib/adarwin/dependences.rb
252 def get_loop_vars(vars,all_loop_vars)
253         return vars & all_loop_vars
254 end