Class: Adarwin::Nest

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

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(level, code, id, name, verbose, fused = 0) ⇒ Nest

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)



30
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
 
# File 'lib/adarwin/nest.rb', line 30

def initialize(level, code, id, name, verbose, fused=0)
	@depth = level.length
	@level = level
	@code = code
	@id = id
	@name = name+'_k'+(@id+1).to_s
	@verbose = verbose
	
	# Set the default values in case there are dependences
	@species = ''
	@fused = fused
	@removed = false
	@copyins = []
	@copyouts = []
	
	# Get all loops from the loop body and subtract the outer loops from all
	# loops to obtain the set of inner loops (loops in the body).
	@all_loops = @code.get_all_loops()
	@outer_loops = @code.get_direct_loops()
	@inner_loops = @all_loops - @outer_loops
	
	# Process the read/write nodes in the loop body to obtain the array
	# reference characterisations. The references also need to be aware of all
	# loop data and of any if-statements in the loop body.
	@references = @code.clone.get_accesses().map do |reference|
		Reference.new(reference,@id,@inner_loops,@outer_loops,@verbose)
	end

	# Perform the dependence test. The result can be either true or false.
	# Proceed only if there are no dependences.
	# Don't perform the dependence test if this is a fused loopnest
	@has_dependences = (@fused > 0) ? false : has_dependences?
	if !@has_dependences && !@references.empty?
	
		# Merge array reference characterisations into other array references
		merge_references()
		
		# Translate array reference characterisations into species and ARC
		translate_into_species()
		translate_into_arc()
		
		# Set the copyin/copyout data from the array references
		@copyins = @references.select{ |r| r.tA == 'read' }
		@copyouts = @references.select{ |r| r.tA == 'write' }
	end
end

Instance Attribute Details

#code ⇒ Object

Returns the value of attribute code.



16
17
18
 
# File 'lib/adarwin/nest.rb', line 16

def code
  @code
end

#copyins ⇒ Object

Returns the value of attribute copyins.



18
19
20
 
# File 'lib/adarwin/nest.rb', line 18

def copyins
  @copyins
end

#copyouts ⇒ Object

Returns the value of attribute copyouts.



18
19
20
 
# File 'lib/adarwin/nest.rb', line 18

def copyouts
  @copyouts
end

#depth ⇒ Object

Returns the value of attribute depth.



19
20
21
 
# File 'lib/adarwin/nest.rb', line 19

def depth
  @depth
end

#fused ⇒ Object

Returns the value of attribute fused.



17
18
19
 
# File 'lib/adarwin/nest.rb', line 17

def fused
  @fused
end

#id ⇒ Object

Returns the value of attribute id.



19
20
21
 
# File 'lib/adarwin/nest.rb', line 19

def id
  @id
end

#level ⇒ Object

Returns the value of attribute level.



19
20
21
 
# File 'lib/adarwin/nest.rb', line 19

def level
  @level
end

#name ⇒ Object

Returns the value of attribute name.



16
17
18
 
# File 'lib/adarwin/nest.rb', line 16

def name
  @name
end

#outer_loops ⇒ Object

Returns the value of attribute outer_loops.



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

def outer_loops
  @outer_loops
end

#reads ⇒ Object

Returns the value of attribute reads.



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

def reads
  @reads
end

#removed ⇒ Object

Returns the value of attribute removed.



17
18
19
 
# File 'lib/adarwin/nest.rb', line 17

def removed
  @removed
end

#species ⇒ Object

Returns the value of attribute species.



16
17
18
 
# File 'lib/adarwin/nest.rb', line 16

def species
  @species
end

#verbose ⇒ Object

Returns the value of attribute verbose.



16
17
18
 
# File 'lib/adarwin/nest.rb', line 16

def verbose
  @verbose
end

#writes ⇒ Object

Returns the value of attribute writes.



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

def writes
  @writes
end

Instance Method Details

#has_copyins? ⇒ Boolean

Method to check if the loop nest has copyins.

Returns:

  • (Boolean) 


215
216
217
 
# File 'lib/adarwin/nest.rb', line 215

def has_copyins?
	return !(copyins.empty?) && !(copyins.select{ |r| r.tD if !r.tD.empty? }.empty?)
end

#has_copyouts? ⇒ Boolean

Method to check if the loop nest has copyouts.

Returns:

  • (Boolean) 


220
221
222
 
# File 'lib/adarwin/nest.rb', line 220

def has_copyouts?
	return !(copyouts.empty?) && !(copyouts.select{ |r| r.tD if !r.tD.empty? }.empty?)
end

#has_dependences? ⇒ Boolean

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.

Returns:

  • (Boolean) 


140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
# File 'lib/adarwin/nest.rb', line 140

def has_dependences?
	
	# Gather all the read/write and write/write pairs to test
	to_test = []
	writes = @references.select{ |r| r.tA == 'write' }
	writes.each do |ref1|
		@references.each do |ref2|
			
			# Only if the array names are the same and they are not tested before
			if ref1.tN == ref2.tN && !to_test.include?([ref2,ref1])
				
				# Only if the array references are different (e.g. don't test
				# A[i][j+4] and A[i][j+4]).
				if (ref1.get_references != ref2.get_references)
					to_test << [ref1,ref2]
				end
			end
		end
	end
	
	# Test all pairs using the GCD and Banerjee tests
	#p to_test.map{ |t| t.map{ |r| r.to_arc }}
	to_test.uniq.each do |pair|
		dependence_test = Dependence.new(pair[0],pair[1],@verbose)
		if dependence_test.result
			return true
		end
	end
	return false
end

#has_species? ⇒ Boolean

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.

Returns:

  • (Boolean) 


173
174
175
176
177
178
179
180
 
# File 'lib/adarwin/nest.rb', line 173

def has_species?
	return false if @removed
	return false if @has_dependences
	return false if @species == ''
	only_full = (@reads) ? @reads.select{ |a| a.pattern != 'full' }.empty? : false
	only_shared = (@writes) ? @writes.select{ |a| a.pattern != 'shared' }.empty? : false
	return !(only_full && only_shared)
end

#merge_references ⇒ Object

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.



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/nest.rb', line 81

def merge_references
	@references.each do |ref1|
		@references.each do |ref2|
			if ref1 != ref2
			
				# Perform the checks to see if merging is valid
				if ref1.tN == ref2.tN && ref1.tA == ref2.tA && ref1.tS == ref2.tS
					
					# Merge the domain (ref2 into ref1)
					ref1.tD.each_with_index do |tD,i|
						tD.merge(ref2.tD[i])
					end
					
					# Merge the number of elements (ref2 into ref1)
					ref1.tE.each_with_index do |tE,i|
						tE.merge(ref2.tE[i])
					end
					
					# Delete ref2
					@references.delete(ref2)
					
					# Something has changed: re-run the whole algorithm again
					merge_references()
					return
				end
			end
		end
	end
end

#print_arc_end ⇒ Object

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



198
199
200
 
# File 'lib/adarwin/nest.rb', line 198

def print_arc_end
	PRAGMA_DELIMITER_START+PRAGMA_ARC+' endkernel '+@name+PRAGMA_DELIMITER_END
end

#print_arc_start ⇒ Object

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



193
194
195
 
# File 'lib/adarwin/nest.rb', line 193

def print_arc_start
	PRAGMA_DELIMITER_START+PRAGMA_ARC+' kernel '+@arc+PRAGMA_DELIMITER_END
end

#print_copyins ⇒ Object

Method to print the copyin pragma.



203
204
205
206
 
# File 'lib/adarwin/nest.rb', line 203

def print_copyins
	copys = @copyins.map{ |a| a.to_copy(2*a.id) }
	PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' copyin '+copys.join(' '+WEDGE+' ')+PRAGMA_DELIMITER_END
end

#print_copyouts ⇒ Object

Method to print the copyout pragma.



209
210
211
212
 
# File 'lib/adarwin/nest.rb', line 209

def print_copyouts
	copys = @copyouts.map{ |a| a.to_copy(2*a.id+1) }
	PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' copyout '+copys.join(' '+WEDGE+' ')+PRAGMA_DELIMITER_END
end

#print_species_end ⇒ Object

Method to print the end pragma of a species.



188
189
190
 
# File 'lib/adarwin/nest.rb', line 188

def print_species_end
	PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' endkernel '+@name+PRAGMA_DELIMITER_END
end

#print_species_start ⇒ Object

Method to print the start pragma of a species.



183
184
185
 
# File 'lib/adarwin/nest.rb', line 183

def print_species_start
	PRAGMA_DELIMITER_START+PRAGMA_SPECIES+' kernel '+@species+PRAGMA_DELIMITER_END
end

#translate_into_arc ⇒ Object

Method to translate the array reference characterisations into a string.



132
133
134
 
# File 'lib/adarwin/nest.rb', line 132

def translate_into_arc
	@arc = @references.map{ |r| r.to_arc }.join(' , ')
end

#translate_into_species ⇒ Object

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.



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/adarwin/nest.rb', line 114

def translate_into_species

	# Obtain the reads and writes
	@reads = @references.select{ |r| r.tA == 'read' }
	@writes = @references.select{ |r| r.tA == 'write' }
	
	# Create a 'void' access pattern in case there is no read or no write.
	# Else, set the species for the individual accesses.
	read_names = (@reads.empty?) ? ['0:0|void'] : @reads.map{ |r| r.to_species }
	write_names = (@writes.empty?) ? ['0:0|void'] : @writes.map{ |r| r.to_species }
	
	# Combine the descriptions (using Reference's +to_s+ method) into species
	species_in = read_names.uniq.join(' '+WEDGE+' ')
	species_out = write_names.uniq.join(' '+WEDGE+' ')
	@species = species_in+' '+ARROW+' '+species_out
end