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:

Attributes

code[RW]
copyins[RW]
copyouts[RW]
depth[RW]
fused[RW]
id[RW]
level[RW]
name[RW]
outer_loops[RW]
reads[RW]
removed[RW]
species[RW]
verbose[RW]
writes[RW]

Public Class Methods

new(level, code, id, name, verbose, fused=0) click to toggle source

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

has_copyins?() click to toggle source

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

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

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

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

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

Method to print the end of an array reference characterisation (ARC).

print_arc_start() click to toggle source

Method to print the start of an array reference characterisation (ARC).

print_copyins() click to toggle source

Method to print the copyin pragma.

print_copyouts() click to toggle source

Method to print the copyout pragma.

print_species_end() click to toggle source

Method to print the end pragma of a species.

print_species_start() click to toggle source

Method to print the start pragma of a species.

translate_into_arc() click to toggle source

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

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