Class: Adarwin::Reference

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

Overview

This class represents an array reference characterisation. This reference is constructed as a 5-tuple (tN,tA,tD,tE,tS) with the following information:

  • tN: The name of the reference.

  • tA: The access direction (read or write).

  • tD: The full domain accessed.

  • tE: The number of elements accessed each iteration (the size).

  • tS: The step of a accesses among iterations.

To be able to compute the 5-tuple, the reference also stores information about the loops and conditional statements to which the original array reference is subjected.

This class contains methods to perform among others the following:

  • Initialise the class and sets the 5-tuple (N,A,D,E,S)

  • Retrieve information on array indices

  • Print in different forms (species, ARC, copy/sync pragma’s)

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(reference, id, inner_loops, outer_loops, var_declarations, verbose) ⇒ Reference

This method initialises the array reference class. It takes details of the reference itself and details of the loop nest it belongs to. The method performs among others the following:

  • It initialises the 5-tuple (N,A,D,E,S)

  • It constructs the sets of loops (all,inner,outer) for this reference

  • It computes the bounds based on loop data and on if-statements

  • It computes the domain (D), number of elements (E), and step (S)



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
76
77
78
79
80
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/adarwin/reference.rb', line 31

def initialize(reference,id,inner_loops,outer_loops,var_declarations,verbose)
	@id = id
	
	# Initialise the 5-tuple (already fill in N and A)
	@tN = reference[:name]
	@tA = reference[:type]
	@tD = []
	@tE = []
	@tS = []
	
	# Set the inner loops as the loop nest's inner loop intersected with all
	# loops found for this statement. Beware of the difference between loops
	# of a loop nest and loops of a statement.
	@all_loops = reference[:loop_data]
	@inner_loops = inner_loops & @all_loops
	@outer_loops = outer_loops

	# Set the list of all local variables
	@var_declarations = var_declarations
	
	# Set the indices of the array reference (e.g. 2*i+4). The size of this
	# array is equal to the number of dimensions of the array.
	@indices = reference[:indices]
	
	# Set the if-statements for the reference. Process them together with the
	# loop start/end conditions to obtain a final set of conditions/bounds.
	@bounds = []
	loop_vars = @all_loops.map{ |l| l[:var]}
	@all_loops.each do |loop_data|
		conditions = [loop_data[:min],loop_data[:max]]
		reference[:if_statements].each do |if_statement|
			if !array_includes_local_vars(if_statement,loop_vars)
				condition_if = if_statement.map{ |c| solve(c,loop_data[:var],loop_vars) }
				conditions[0] = max(conditions[0],condition_if[0])
				conditions[1] = min(conditions[1],condition_if[1])
			end
		end
		@bounds << { :var => loop_data[:var], :min => conditions[0], :max => conditions[1] }
	end
	
	# Compute the domain (D) based on the bounds. The bounds are derived from
	# the if-statements and for-loops.
	@tD = @indices.map do |i|
		index_to_interval(i,@bounds)
	end
	
	# Compute the number of elements (E) accessed every iteration (the size).
	# TODO: Clean-up this method.
	@tE = @indices.map do |i|
		#if !dependent?(i,@all_loops)
		#	puts "independent"
		#	index_to_interval(i,@inner_loops)
		#else
			#puts "dependent"
			get_base_offset(i)
		#end
	end
	
	# Compute the step taken. There are 3 cases considered the index is: 1)
	# dependent on the outer loops, 2) dependent on the inner loops, or 3)
	# indepdent of any loops.
	@tS = @indices.map do |i|
		if dependent?(i,@inner_loops)
			index_to_interval(i,@inner_loops).length
		elsif dependent?(i,@outer_loops)
			get_step(i,@outer_loops)
		else
			'0'
		end
	end
	
	# If the step and the domain are equal in size, the step can also be set
	# to zero to reflect accessing the full array.
	@tS.each_with_index do |tS,index|
		if (tS == @tD[index].length) || (@tD[index].length == '1')
			@tS[index] = '0'
		end
	end

	# Check for local variables in the domain. If they exist ask the user to fill
	# in the bounds.
	# TODO: Make this a command-line question asked to the user. For now, several
	# known values are simply put here - for ease of automated testing.
	@tD.each do |bounds|

		# Bounds are equal (e.g. [t:t])
		if bounds.a == bounds.b && string_includes_local_vars(bounds.a)

			# Default (assume 'char')
			a = '0'
			b = '255'

			# Overrides (see notice above)
			b = 'NUM_CLUSTERS-1' if bounds.a == 'cluster_index'
			b = 'no_of_nodes-1' if bounds.b == 'id'

			# Output a warning
			puts WARNING+"Bounds of '#{bounds.a}' variable unknown, assuming #{a}:#{b}"
			bounds.a = a
			bounds.b = b

		# Not equal but both problematic
		elsif string_includes_local_vars(bounds.a) && string_includes_local_vars(bounds.b)

			# Default (assume 'char')
			a = '0'
			b = '255'

			# Overrides (see notice above)
			b = 'no_of_nodes-1' if bounds.a == 'val2'

			# Output a warning
			puts WARNING+"Bounds of '#{bounds.a}' and '#{bounds.b}' variables unknown, assuming #{a}:#{b}"
			bounds.a = a
			bounds.b = b

		end
	end

	
	# Print the result
	puts MESSAGE+"Found: #{to_arc}" if verbose
end

Instance Attribute Details

#all_loops ⇒ Object

Returns the value of attribute all_loops.



22
23
24
 
# File 'lib/adarwin/reference.rb', line 22

def all_loops
  @all_loops
end

#bounds ⇒ Object

Returns the value of attribute bounds.



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

def bounds
  @bounds
end

#id ⇒ Object

Returns the value of attribute id.



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

def id
  @id
end

#indices ⇒ Object

Returns the value of attribute indices.



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

def indices
  @indices
end

#pattern ⇒ Object

Returns the value of attribute pattern.



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

def pattern
  @pattern
end

#tA ⇒ Object

Returns the value of attribute tA.



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

def tA
  @tA
end

#tD ⇒ Object

Returns the value of attribute tD.



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

def tD
  @tD
end

#tE ⇒ Object

Returns the value of attribute tE.



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

def tE
  @tE
end

#tN ⇒ Object

Returns the value of attribute tN.



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

def tN
  @tN
end

#tS ⇒ Object

Returns the value of attribute tS.



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

def tS
  @tS
end

Instance Method Details

#array_includes_local_vars(array, loop_vars) ⇒ Object

Method to find if local variables are included



305
306
307
308
309
310
311
312
313
314
315
 
# File 'lib/adarwin/reference.rb', line 305

def array_includes_local_vars(array, loop_vars)
	vars = @var_declarations - loop_vars
	array.each do |string|
		vars.each do |decl|
			if string =~ /\b#{decl}\b/
				return true
			end
		end
	end
	return false
end

#dependent?(index, loops) ⇒ Boolean

Method to check whether the an index is dependent on a given set of loops. For example, A is independent of j, but dependent on i.

Returns:

  • (Boolean) 


194
195
196
197
198
199
200
201
202
203
 
# File 'lib/adarwin/reference.rb', line 194

def dependent?(index,loops)
	index.preorder do |node|
		if node.variable?
			loops.each do |for_loop|
				return true if (node.name == for_loop[:var])
			end
		end
	end
	return false
end

#depends_on?(var) ⇒ Boolean

Method to find out if the reference is dependent on a variable. It is used by the copy optimisations.

Returns:

  • (Boolean) 


293
294
295
296
297
298
299
300
301
302
 
# File 'lib/adarwin/reference.rb', line 293

def depends_on?(var)
	@indices.each do |index|
		index.preorder do |node|
			if node.variable?
				return true if (node.name == var)
			end
		end
	end
	return false
end

#find_extreme(position, index, loops) ⇒ Object

Substitute loop data with the upper-bound or lower-bound of a loop to find the minimum/maximum of an array reference. The body is executed twice, because a loop bound can be based on another loop variable.



180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/adarwin/reference.rb', line 180

def find_extreme(position,index,loops)
	index = index.clone
	2.times do
		loops.each do |for_loop|
			search = C::Variable.parse(for_loop[:var])
			replace = C::Expression.parse(for_loop[position])
			index = index.search_and_replace_node(search,replace)
		end
	end
	return simplify(index.to_s.gsub(';','').gsub(' ','').gsub("\t",''))
end

#get_base_offset(index) ⇒ Object

This method replaces loop variables for a given set of loops with 0. This basically gives us the offset of array references with respect to the loop variable. For example, A and A will give us [4,j+3] with repsect to an i-loop.



159
160
161
162
163
164
165
166
167
 
# File 'lib/adarwin/reference.rb', line 159

def get_base_offset(index)
	index = index.clone
	@outer_loops.each do |for_loop|
		search = C::Variable.parse(for_loop[:var])
		replace = C::Expression.parse('0')
		index = index.search_and_replace_node(search,replace)
	end
	return index_to_interval(index,@inner_loops)
end

#get_references ⇒ Object

Method to print out a human readable form of the array references (e.g. [4*i+6][j]). This is basically what the puts method also does.



287
288
289
 
# File 'lib/adarwin/reference.rb', line 287

def get_references
	return @indices.to_ary.map{ |i| i.to_s }
end

#get_step(index, loops) ⇒ Object

Method to retrieve the step for a given array index and loops. The method returns the difference between two subsequent iterations: one with the loop variable at 0 and one after the first increment.



208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/adarwin/reference.rb', line 208

def get_step(index,loops)
	
	# Replace the loop indices with 0
	index1 = index.clone
	loops.each do |for_loop|
		search = C::Variable.parse(for_loop[:var])
		replace = C::Expression.parse('0')
		index1 = index1.search_and_replace_node(search,replace)
	end
	
	# Replace the loop indices with the loop step
	index2 = index.clone
	loops.each do |for_loop|
		search = C::Variable.parse(for_loop[:var])
		replace = C::Expression.parse(for_loop[:step])
		index2 = index2.search_and_replace_node(search,replace)
	end
	
	# Return the difference
	return abs(simplify("(#{index2})-(#{index1})"))
end

#get_sync_id ⇒ Object

Method to print the unique identifier of the loop nest in terms of synchronisation statements to be printed. This is a per-reference id instead of a per-loop id, because it depends on the type of access (read or write).



266
267
268
 
# File 'lib/adarwin/reference.rb', line 266

def get_sync_id
	(@tA == 'write') ? 2*@id+1 : 2*@id
end

#index_to_interval(index, loops) ⇒ Object

Method to fill in the ranges for an array reference. This is based on information of the loop nests. The output is an interval.



171
172
173
174
175
 
# File 'lib/adarwin/reference.rb', line 171

def index_to_interval(index,loops)
	access_min = find_extreme(:min,index,loops)
	access_max = find_extreme(:max,index,loops)
	return Interval.new(access_min,access_max,@all_loops)
end

#step_smaller_than_num_elements? ⇒ Boolean

Helper method for the to_species method. This method compares the step with the number of elements accessed to determine which one is smaller. FIXME: This is based on the compare method which might take a guess.

Returns:

  • (Boolean) 


273
274
275
276
277
278
279
280
281
282
283
 
# File 'lib/adarwin/reference.rb', line 273

def step_smaller_than_num_elements?
	@tS.each_with_index do |step,index|
		if step != '0'
			comparison = compare(step,@tE[index].length,@all_loops)
			if (comparison == 'lt')
				return true
			end
		end
	end
	return false
end

#string_includes_local_vars(string) ⇒ Object 



316
317
318
319
320
321
322
323
 
# File 'lib/adarwin/reference.rb', line 316

def string_includes_local_vars(string)
	@var_declarations.each do |decl|
		if string =~ /\b#{decl}\b/
			return true
		end
	end
	return false
end

#to_arc ⇒ Object

Method to output the result as an array reference characterisation (ARC).



252
253
254
 
# File 'lib/adarwin/reference.rb', line 252

def to_arc
	return "(#{tN},#{tA},#{tD},#{tE},#{tS})".gsub('"','').gsub(' ','')
end

#to_copy(id) ⇒ Object

Method to output a copyin/copyout statement. This indicates the name (N), the domain (D), and a unique identifier.



258
259
260
 
# File 'lib/adarwin/reference.rb', line 258

def to_copy(id)
	@tN+'['+@tD.join(DIM_SEP)+']'+'|'+id.to_s
end

#to_species ⇒ Object

Method to output the result as algorithmic species. This reflects the algorithm as presented in the scientific paper.



232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
 
# File 'lib/adarwin/reference.rb', line 232

def to_species
	if @tS.reject{ |s| s == "0"}.empty?
		if (@tA == 'read') # Full (steps length 0 and read)
			@pattern = 'full'
		else # Shared (steps length 0 and write)
			@pattern = 'shared'
		end
	elsif @tE.reject{ |s| s.length == "1"}.empty? # Element (sizes length 1)
		@pattern = 'element'
	elsif step_smaller_than_num_elements? # Neighbourhood (tS < tE)
		@pattern = 'neighbourhood('+@tE.join(DIM_SEP)+')'
	else # Chunk (tS >= tE)
		@pattern = 'chunk('+@tE.join(DIM_SEP)+')'
	end
	
	# Fill in the name and the domain and return the result
	return @tN+'['+@tD.join(DIM_SEP)+']'+PIPE+@pattern
end