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:
-
The GCD (greatest common divisor) test
-
The Banerjee test
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
Public Class Methods
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
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
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
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
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
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