class Adarwin::Nest
This class represents a loop nest. The end goal is to annotate the loop nest with the corresponding species information. If the loop nest cannot be parallelised (if there are dependences), the species information is not printed.
This class contains methods to perform among others the following:
-
Find all array references in the loop nest
-
Merge found array references into another array reference
-
Translate array references into species
-
Perform dependence tests to check for parallelism
Attributes
Public Class Methods
Method to initialise the loop nest. The loop nest is initialised with the following variables:
-
An identifier for the order/depth in which the nest appears (
level
) -
The loop nest body in AST form (
code
) -
A unique identifier for this loop nest (
id
) -
A human readable name for this loop nest (
name
) -
Whether or not verbose information should be printed (
verbose
)
# File lib/adarwin/nest.rb 30 def initialize(level, code, id, name, verbose, fused=0) 31 @depth = level.length 32 @level = level 33 @code = code 34 @id = id 35 @name = name+'_k'+(@id+1).to_s 36 @verbose = verbose 37 38 # Set the default values in case there are dependences 39 @species = '' 40 @fused = fused 41 @removed = false 42 @copyins = [] 43 @copyouts = [] 44 45 # Get all loops from the loop body and subtract the outer loops from all 46 # loops to obtain the set of inner loops (loops in the body). 47 @all_loops = @code.get_all_loops() 48 @outer_loops = @code.get_direct_loops() 49 @inner_loops = @all_loops - @outer_loops 50 51 # Get all local variable declarations 52 @var_declarations = @code.get_var_declarations() 53 54 # Process the read/write nodes in the loop body to obtain the array 55 # reference characterisations. The references also need to be aware of all 56 # loop data and of any if-statements in the loop body. 57 @references = @code.clone.get_accesses().map do |reference| 58 Reference.new(reference,@id,@inner_loops,@outer_loops,@var_declarations,@verbose) 59 end 60 61 # Perform the dependence test. The result can be either true or false. 62 # Proceed only if there are no dependences. 63 # Don't perform the dependence test if this is a fused loopnest 64 @has_dependences = (@fused > 0) ? false : has_dependences? 65 if !@has_dependences && !@references.empty? 66 67 # Merge array reference characterisations into other array references 68 merge_references() 69 70 # Translate array reference characterisations into species and ARC 71 translate_into_species() 72 translate_into_arc() 73 74 # Set the copyin/copyout data from the array references 75 @copyins = @references.select{ |r| r.tA == 'read' } 76 @copyouts = @references.select{ |r| r.tA == 'write' } 77 end 78 end
Public Instance Methods
Method to check if the loop nest has copyins.
# File lib/adarwin/nest.rb 232 def has_copyins? 233 return !(copyins.empty?) && !(copyins.select{ |r| r.tD if !r.tD.empty? }.empty?) 234 end
Method to check if the loop nest has copyouts.
# File lib/adarwin/nest.rb 237 def has_copyouts? 238 return !(copyouts.empty?) && !(copyouts.select{ |r| r.tD if !r.tD.empty? }.empty?) 239 end
Perform the dependence test for the current loop nest. This method gathers all pairs of array references to test and calls the actual dependence tests. Currently, the dependence tests are a combination of the GCD test and the Banerjee test.
# File lib/adarwin/nest.rb 156 def has_dependences? 157 158 # Gather all the read/write and write/write pairs to test 159 to_test = [] 160 writes = @references.select{ |r| r.tA == 'write' } 161 writes.each do |ref1| 162 @references.each do |ref2| 163 164 # Only if the array names are the same and they are not tested before 165 if ref1.tN == ref2.tN && !to_test.include?([ref2,ref1]) 166 167 # Only if the array references are different (e.g. don't test 168 # A[i][j+4] and A[i][j+4]). 169 if (ref1.get_references != ref2.get_references) 170 to_test << [ref1,ref2] 171 end 172 end 173 end 174 end 175 176 # Test all pairs using the GCD and Banerjee tests 177 #p to_test.map{ |t| t.map{ |r| r.to_arc }} 178 to_test.uniq.each do |pair| 179 dependence_test = Dependence.new(pair[0],pair[1],@verbose) 180 if dependence_test.result 181 return true 182 end 183 end 184 return false 185 end
Perform a check to see if the loop nest has species that are not just formed from shared or full patterns. If so, there is no parallelism.
# File lib/adarwin/nest.rb 189 def has_species? 190 return false if @removed 191 return false if @has_dependences 192 return false if @species == '' 193 return false if (@writes) && (@writes.select{ |a| a.pattern == 'shared' }.length > 3) 194 only_full = (@reads) ? @reads.select{ |a| a.pattern != 'full' }.empty? : false 195 only_shared = (@writes) ? @writes.select{ |a| a.pattern != 'shared' }.empty? : false 196 return !(only_full && only_shared) 197 end
Perform the algorithm to merge array reference characterisations into merged array references. This method is a copy of the merging algorithm as found in the scientific paper. TODO: Complete this algorithm to match the scientific paper version.
# File lib/adarwin/nest.rb 84 def merge_references 85 @references.each do |ref1| 86 @references.each do |ref2| 87 if ref1 != ref2 88 89 # Perform the checks to see if merging is valid 90 if ref1.tN == ref2.tN && ref1.tA == ref2.tA && ref1.tS == ref2.tS 91 92 # Merge the domain (ref2 into ref1) 93 ref1.tD.each_with_index do |tD,i| 94 tD.merge(ref2.tD[i]) 95 end 96 97 # Merge the number of elements (ref2 into ref1) 98 ref1.tE.each_with_index do |tE,i| 99 tE.merge(ref2.tE[i]) 100 end 101 102 # Delete ref2 103 @references.delete(ref2) 104 105 # Something has changed: re-run the whole algorithm again 106 merge_references() 107 return 108 end 109 end 110 end 111 end 112 end
Method to print the end of an array reference characterisation (ARC).
# File lib/adarwin/nest.rb 215 def print_arc_end 216 PRAGMA_DELIMITER_START+PRAGMA_ARC+' endkernel '+@name+PRAGMA_DELIMITER_END 217 end
Method to print the start of an array reference characterisation (ARC).
# File lib/adarwin/nest.rb 210 def print_arc_start 211 PRAGMA_DELIMITER_START+PRAGMA_ARC+' kernel '+@arc+PRAGMA_DELIMITER_END 212 end
Method to print the copyin pragma.
# File lib/adarwin/nest.rb 220 def print_copyins 221 copys = @copyins.map{ |a| a.to_copy(2*a.id) } 222 PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' copyin '+copys.join(' '+WEDGE+' ')+PRAGMA_DELIMITER_END 223 end
Method to print the copyout pragma.
# File lib/adarwin/nest.rb 226 def print_copyouts 227 copys = @copyouts.map{ |a| a.to_copy(2*a.id+1) } 228 PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' copyout '+copys.join(' '+WEDGE+' ')+PRAGMA_DELIMITER_END 229 end
Method to print the end pragma of a species.
# File lib/adarwin/nest.rb 205 def print_species_end 206 PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' endkernel '+@name+PRAGMA_DELIMITER_END 207 end
Method to print the start pragma of a species.
# File lib/adarwin/nest.rb 200 def print_species_start 201 PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' kernel '+@species+PRAGMA_DELIMITER_END 202 end
Method to translate the array reference characterisations into a string.
# File lib/adarwin/nest.rb 148 def translate_into_arc 149 @arc = @references.map{ |r| r.to_arc }.join(' , ') 150 end
Method to translate the array reference characterisations into species. The actual logic is performed within the Reference
class. In this method, only the combining of the separate parts is performed.
# File lib/adarwin/nest.rb 117 def translate_into_species 118 119 # Obtain the reads and writes 120 @reads = @references.select{ |r| r.tA == 'read' } 121 @writes = @references.select{ |r| r.tA == 'write' } 122 123 # Create a 'void' access pattern in case there is no read or no write. 124 # Else, set the species for the individual accesses. 125 read_names = (@reads.empty?) ? ['0:0|void'] : @reads.map{ |r| r.to_species } 126 write_names = (@writes.empty?) ? ['0:0|void'] : @writes.map{ |r| r.to_species } 127 128 # Remove a 'full' access pattern in case there is a same 'shared' write pattern 129 write_names.each do |write_name| 130 write_parts = write_name.split(PIPE) 131 if write_parts.last == 'shared' 132 read_names.each do |read_name| 133 read_parts = read_name.split(PIPE) 134 if read_parts.last == 'full' && read_parts.first == write_parts.first 135 read_names.delete(read_name) 136 end 137 end 138 end 139 end 140 141 # Combine the descriptions (using Reference's +to_s+ method) into species 142 species_in = read_names.uniq.join(' '+WEDGE+' ') 143 species_out = write_names.uniq.join(' '+WEDGE+' ') 144 @species = species_in+' '+ARROW+' '+species_out 145 end