Top Level Namespace

Defined Under Namespace

Modules: Adarwin, Bones, C Classes: CodeGenError, String

Constant Summary collapse

NL =

Set the newline character

"\n"
INDENT =

Set the tab size (currently: 2 spaces)

"\t"
WEDGE =

A string representing the combination character (‘^’) of a species.

'^'
ARROW =

A string representing the production character (‘->’) of a species.

'->'
PIPE =

A string representing the pipe character (‘|’) of a species.

'|'
RANGE_SEP =

A string representing the colon character (‘:’) to separate ranges in dimensions.

':'
DIM_SEP =

A string representing the comma character (‘,’) to separate different ranges.

','
ASSUME_VAL =

Value to assume a variable to be

'1000'

Instance Method Summary collapse

Instance Method Details

#abs(expr) ⇒ Object

Return the absolute value (if possible)



173
174
175
176
 
# File 'lib/common.rb', line 173

def abs(expr)
	return expr.to_i.abs.to_s if expr.to_i.to_s == expr
	return expr
end

#code_from_loops(loops, statements) ⇒ Object

Generate code from a combination of loops and statements (the body)



155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
# File 'lib/adarwin/fusion.rb', line 155

def code_from_loops(loops,statements)
	code = ""
	
	# Start of the loops
	definition = "int "
	loops.each do |loop_datum|
		increment = (loop_datum[:step] == '1') ? "#{loop_datum[:var]}++" : "#{loop_datum[:var]}=#{loop_datum[:var]}+#{loop_datum[:step]}"
		code += "for(#{definition}#{loop_datum[:var]}=#{loop_datum[:min]}; #{loop_datum[:var]}<=#{loop_datum[:max]}; #{increment}) {"
	end
	
	# Loop body
	statements.each do |statement|
		code += statement.to_s
	end
	
	# End of the loops
	loops.size.times{ |i| code += "}" }
	
	C::Statement.parse(code)
end

#compare(expr1, expr2, loop_data, assumptions = []) ⇒ Object

Compare two expressions



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/common.rb', line 179

def compare(expr1,expr2,loop_data,assumptions=[])
	comparison = simplify("(#{expr1})-(#{expr2})")
	
	# Handle min/max functions
	if comparison =~ /max/ || comparison =~ /min/
		return comparison
	end
	
	# Process the assumptions
	assumptions.each do |assumption|
		comparison = simplify(comparison.gsub(assumption[0],assumption[1]))
	end
	
	# Known comparison
	if (comparison.to_i.to_s == comparison || comparison.to_f.to_s == comparison)
		return 'eq' if (comparison.to_i == 0)
		return 'gt' if (comparison.to_i > 0)
		return 'lt' if (comparison.to_i < 0)
	else
		
		# Comparison based on loop data
		get_vars(comparison).each do |var|
			loop_data.each do |loop_datum|
				if loop_datum[:var] == var
					assumptions << [var,loop_datum[:min]]
					#puts "WARNING: Modifying expression '(#{expr1}) vs (#{expr2})', assuming: #{var}=#{loop_datum[:min]}"
					return compare(expr1,expr2,loop_data,assumptions)
				end
			end
		end
		
		# Comparison based on a guess
		var = get_vars(comparison).first
		assumptions << [var,ASSUME_VAL]
		#puts "WARNING: Don't know how to compare '(#{expr1})' and '(#{expr2})', assuming: #{var}=#{ASSUME_VAL}"
		return compare(expr1,expr2,loop_data,assumptions)
	end
end

#create_if(loop_var, reference_bound, loop_bound, code, condition) ⇒ Object

Create an if-statement in front of a statement



147
148
149
150
151
152
 
# File 'lib/adarwin/fusion.rb', line 147

def create_if(loop_var,reference_bound,loop_bound,code,condition)
	if reference_bound != loop_bound
		return C::Statement.parse("if(#{loop_var} #{condition} #{loop_bound}) { #{code.to_s} }")
	end
	return code
end

#exact_max(expr1, expr2) ⇒ Object

Find the exact maximum value of 2 expressions



152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/common.rb', line 152

def exact_max(expr1,expr2)
	return expr1 if expr1 == expr2
	comparison = simplify("(#{expr1})-(#{expr2})")
	if (comparison.to_i.to_s == comparison || comparison.to_f.to_s == comparison)
		return expr1 if (comparison.to_i == 0)
		return expr1 if (comparison.to_i > 0)
		return expr2 if (comparison.to_i < 0)
	else
		return "max(#{expr1},#{expr2})"
	end
end

#exact_min(expr1, expr2) ⇒ Object

Find the exact minimum value of 2 expressions (based on the exact_max method)



165
166
167
168
169
 
# File 'lib/common.rb', line 165

def exact_min(expr1,expr2)
	return expr1 if expr1 == expr2
	maximum = exact_max(expr1,expr2)
	return (maximum == expr1) ? expr2 : ( (maximum == expr2) ? expr1 : maximum.gsub('max(','min(') )
end

#fusion_is_legal?(a, b) ⇒ Boolean

Determine whether kernel fusion is legal (see algorithm in paper/thesis)

Returns:

  • (Boolean) 


3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
# File 'lib/adarwin/fusion.rb', line 3

def fusion_is_legal?(a, b)
	(a.writes + a.reads).each do |x|
		(b.writes + b.reads).each do |y|
			if (x.tN == y.tN) && (x.tA == 'write' || y.tA == 'write')
				puts Adarwin::MESSAGE+"Evaluating #{x.to_arc} and #{y.to_arc} for fusion"
				if x.tD.to_s != y.tD.to_s || x.tE.to_s != y.tE.to_s || x.tS.to_s != y.tS.to_s
					puts Adarwin::MESSAGE+"Unable to fuse #{x.to_arc} and #{y.to_arc}"
					return false
				end
			end
		end
	end
	puts Adarwin::MESSAGE+"Applying fusion"
	return true
end

#get_body(num_loops, code) ⇒ Object

Return the body of a loop nest



135
136
137
138
139
140
141
142
143
144
 
# File 'lib/adarwin/fusion.rb', line 135

def get_body(num_loops,code)
	return code if num_loops == 0
	if code.first.for_statement? && code.first.stmt
		code = code.first
	end
	if code.for_statement? && code.stmt
		return get_body(num_loops-1,code.stmt.stmts)
	end
	raise_error("Not a perfect nested loop")
end

#get_vars(expr) ⇒ Object

Get the variables in an expression



79
80
81
 
# File 'lib/common.rb', line 79

def get_vars(expr)
	expr.split(/\W+/).reject{ |s| (s.to_i.to_s == s || s.to_f.to_s == s || s == "") }
end

#kernel_fusion(nests, settings) ⇒ Object

Perform the kernel fusion transformations



21
22
23
24
25
26
27
28
29
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
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
 
# File 'lib/adarwin/fusion.rb', line 21

def kernel_fusion(nests, settings)
	
	# Select
	candidates = nests.select{ |n| n.has_species? }
	
	# Iterate
	prev = nil
	candidates.each_with_index do |nest,nest_index|
		curr = nest
		if prev
			
			# Get the loop details
			loops_prev = prev.code.get_direct_loops
			loops_curr = curr.code.get_direct_loops
			if loops_prev.size != loops_curr.size
				puts Adarwin::MESSAGE+"Unable to apply fusion, loop count does not match"
				next
			end
			
			# Only proceed if fusion is legal for this combination
			if fusion_is_legal?(prev, curr)
				fused_code = []
			
				# Get the bodies 
				body_curr = get_body(loops_curr.size,curr.code.clone)
				body_prev = get_body(loops_prev.size,prev.code.clone)
				
				# Fuse everything together: include if-statements for non-matching loop bounds
				if settings == 1
					
					# Create new loops
					loops_target = []
					loops_prev.zip(loops_curr).each do |prevl,currl|
						raise_error("Unequal step count #{prevl[:step]} versus #{currl[:step]}") if prevl[:step] != currl[:step]
						minmin = exact_min(prevl[:min],currl[:min])
						maxmax = exact_max(prevl[:max],currl[:max])
						loop_datum = { :var => prevl[:var]+currl[:var], :min => minmin, :max => maxmax, :step => prevl[:step]}
						loops_target.push(loop_datum)
						
						# Replace all occurances of the fused loop variable in the current/previous codes
						body_prev = body_prev.replace_variable(prevl[:var],loop_datum[:var])
						body_curr = body_curr.replace_variable(currl[:var],loop_datum[:var])
						
						# Set minimum if-statement conditions
						body_prev = create_if(loop_datum[:var],minmin,prevl[:min],body_prev,'>=')
						body_curr = create_if(loop_datum[:var],minmin,currl[:min],body_curr,'>=')
						
						# Set maximum if-statement conditions
						body_prev = create_if(loop_datum[:var],maxmax,prevl[:max],body_prev,'<=')
						body_curr = create_if(loop_datum[:var],maxmax,currl[:max],body_curr,'<=')
					end
					
					# Generate the new code
					fused_code.push(code_from_loops(loops_target,[body_prev,body_curr]))
				
				# Create a prologue in case of mismatching loop bounds (experimental)
				elsif settings == 2
					
					# Generate the loop body
					loops_target = []
					loops_prev.zip(loops_curr).each do |prevl,currl|
						raise_error("Unequal step count #{prevl[:step]} versus #{currl[:step]}") if prevl[:step] != currl[:step]
						body_prev = body_prev.replace_variable(prevl[:var],prevl[:var]+currl[:var])
						body_curr = body_curr.replace_variable(currl[:var],prevl[:var]+currl[:var])
					end
					
					# Create the main loop nest
					loops_target = []
					loops_prev.zip(loops_curr).each do |prevl,currl|
						minmin = exact_min(prevl[:min],currl[:min])
						minmax = exact_min(prevl[:max],currl[:max])
						loop_datum = { :var => prevl[:var]+currl[:var], :min => minmin, :max => minmax, :step => prevl[:step]}
						loops_target.push(loop_datum)
					end
					fused_code.push(code_from_loops(loops_target,[body_prev,body_curr]))
					
					# Create the epilogue
					body = []
					loops_target = []
					loops_prev.zip(loops_curr).each do |prevl,currl|
						minmax = exact_min(prevl[:max],currl[:max])
						maxmax = exact_max(prevl[:max],currl[:max])
						loop_datum = { :var => prevl[:var]+currl[:var], :min => minmax, :max => maxmax, :step => prevl[:step]}
						loops_target.push(loop_datum)
						if prevl[:max] != currl[:max]
							body = (prevl[:max] == maxmax) ? [body_curr] : [body_prev]
						end
					end
					fused_code.push(code_from_loops(loops_target,body))
				end
				
				# Add the newly created code to the original code
				fused_code.each_with_index do |fused_codelet,nest_id|
					puts fused_codelet
					prev.code.insert_prev(fused_codelet)
				
					# Create a new nest
					nest = Adarwin::Nest.new(prev.level, fused_codelet, prev.id, prev.name.gsub(/_k(\d+)/,'_fused')+nest_id.to_s, prev.verbose, 1)
					nests.push(nest)
				end

				
				# Set the other nests as to-be-removed
				prev.removed = true
				curr.removed = true
			end
		end
	
		# Next nest
		prev = nest
	end
end

#max(expr1, expr2, assumptions = []) ⇒ Object

Find the maximum value of 2 expressions



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
 
# File 'lib/common.rb', line 103

def max(expr1,expr2,assumptions=[])
	return expr1 if expr2 == ""
	comparison = simplify("(#{expr1})-(#{expr2})")
	
	# Process the assumptions
	assumptions.each do |assumption|
		comparison = simplify(comparison.gsub(assumption[0],assumption[1]))
	end
	
	# Test to find the maximum
	if (comparison.to_i.to_s == comparison || comparison.to_f.to_s == comparison)
		return expr1 if (comparison.to_i == 0)
		return expr1 if (comparison.to_i > 0)
		return expr2 if (comparison.to_i < 0)
	else
	
		# Handle min/max functions
		if comparison =~ /max/ || comparison =~ /min/
			return "max(#{expr1},#{expr2})"
		end
		
		# Find the maximum based on a guess
		var = get_vars(comparison).first
		assumptions << [var,ASSUME_VAL]
		#puts "WARNING: Don't know how to find the max/min of '(#{expr1})' and '(#{expr2})', assuming: #{var}=#{ASSUME_VAL}"
		return max(expr1,expr2,assumptions)
	end
end

#min(expr1, expr2) ⇒ Object

Find the minimum value of 2 expressions (based on the max method)



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/common.rb', line 133

def min(expr1,expr2)
	return expr1 if expr2 == ""
	s1 = simplify(expr1)
	s2 = simplify(expr2)
	comparison = simplify("(#{s1})-(#{s2})")
	
	# Handle min/max functions
	if comparison =~ /max/ || comparison =~ /min/
		return s1 if s2 =~ /^max\(#{s1},.*\)$/ || s2 =~ /^max\(.*,#{s1}\)$/
		return s2 if s1 =~ /^max\(#{s2},.*\)$/ || s1 =~ /^max\(.*,#{s2}\)$/
		return "min(#{expr1},#{expr2})"
	end
	
	# Run the 'max' method
	maximum = max(expr1,expr2)
	return (maximum == expr1) ? expr2 : ( (maximum == expr2) ? expr1 : maximum.gsub('max(','min(') )
end

#perform_copy_optimisations1(nests, options) ⇒ Object

First set of copyin/copyout optimisations (recursive)



16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
 
# File 'lib/adarwin/memorycopies.rb', line 16

def perform_copy_optimisations1(nests,options)
	previous = nil
	nests.each_with_index do |nest,nest_index|
		current = nest
		if previous
	
			# Remove spurious copies (out/in)
			if options[:mem_remove_spurious]
				previous.copyouts.each do |copyout|
					current.copyins.each do |copyin|
						if copyout.tN.to_s == copyin.tN.to_s && copyout.tD.to_s == copyin.tD.to_s
							current.copyins.delete(copyin)
							return perform_copy_optimisations1(nests,options)
						end
					end
				end
			end
	
			# Remove spurious copies (out/out)
			if options[:mem_remove_spurious]
				previous.copyouts.each do |copyout|
					current.copyouts.each do |other_copyout|
						if copyout.tN.to_s == other_copyout.tN.to_s && copyout.tD.to_s == other_copyout.tD.to_s
							previous.copyouts.delete(copyout)
							return perform_copy_optimisations1(nests,options)
						end
					end
				end
			end
		
			# Move copyins to the front
			if options[:mem_copyin_to_front]
				current.copyins.each do |copyin|
					if previous.writes && !previous.writes.map{ |w| w.tN }.include?(copyin.tN)
						previous.copyins.push(copyin)
						current.copyins.delete(copyin)
						return perform_copy_optimisations1(nests,options)
					end
				end
			end
		
		end
		
		# Next nest
		previous = nest
	end
end

#perform_copy_optimisations2(nests, options) ⇒ Object

Second set of copyin/copyout optimisations (non-recursive)



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

def perform_copy_optimisations2(nests,options)
	nests.each_with_index do |nest,nest_index|
		current = nest
			
		# Move copyouts to the back
		if options[:mem_copyout_to_back]
			current.copyouts.each do |copyout|
				nests.each_with_index do |other_nest,other_nest_index|
					if other_nest.id > nest.id && other_nest.depth == nest.depth
						if other_nest.writes && !other_nest.writes.map{ |w| w.tN }.include?(copyout.tN)
							copyout.id = copyout.id+1
						else
							break
						end
					end
				end
			end
		end
		
		# Remove spurious copies (double in)
		if options[:mem_remove_spurious]
			current.copyins.each_with_index do |copyin,index|
				current.copyins.each_with_index do |other_copyin,other_index|
					if index != other_index
						if copyin.tN.to_s == other_copyin.tN.to_s && copyin.tD.to_s == other_copyin.tD.to_s
							if copyin.id > other_copyin.id
								current.copyins.delete(copyin)
							else
								current.copyins.delete(other_copyin)
							end
						end
					end
				end
			end
		end
		
	end
end

#perform_copy_optimisations3(nests, options) ⇒ Object

Third set of copyin/copyout optimisations (inter-level)



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/memorycopies.rb', line 105

def perform_copy_optimisations3(nests,options)
	nests.each do |nest|
		current = nest
		children = get_children(nest)
		if !children.empty?
			
			# Inter-level loop optimisations (move to outer loop)
			if options[:mem_to_outer_loop]
				
				# Move copyouts to outer loops
				max_id = children.map{ |c| 2*c.id+1 }.max
				children.each do |child|
					child.copyouts.each do |copyout|
						to_outer_loop = true
						nest.outer_loops.map{ |l| l[:var] }.each do |var|
							to_outer_loop = false if copyout.depends_on?(var)
						end
						children.each do |other_child|
							to_outer_loop = false if other_child.copyins.map{ |c| c.tN }.include?(copyout.tN)
						end
						to_outer_loop = false if copyout.get_sync_id < max_id
						if to_outer_loop
							copyout.id = nest.id
							nest.copyouts.push(copyout)
							child.copyouts.delete(copyout)
						end
					end
				end
			
				# Move copyins to outer loops
				children.first.copyins.each do |copyin|
					to_outer_loop = true
					nest.outer_loops.map{ |l| l[:var] }.each do |var|
						to_outer_loop = false if copyin.depends_on?(var)
					end
					children.drop(1).each do |child|
						to_outer_loop = false if child.copyins.map{ |c| c.tN }.include?(copyin.tN)
						to_outer_loop = false if child.copyouts.map{ |c| c.tN }.include?(copyin.tN) && child != children.last
					end
					if to_outer_loop
						nest.copyins.push(copyin)
						children.first.copyins.delete(copyin)
					end
				end
				
			end
		end
	end
end

#raise_error(message) ⇒ Object

:nodoc:

Raises:



9
10
11
12
 
# File 'lib/bones.rb', line 9

def raise_error(message) #:nodoc:
	puts Bones::ERROR+message
	raise CodeGenError, 'Error encountered, stopping execution of Bones'
end

#recursive_copy_optimisations(nests, options) ⇒ Object

Recursive copy optimisations



4
5
6
7
8
9
10
11
12
13
 
# File 'lib/adarwin/memorycopies.rb', line 4

def recursive_copy_optimisations(nests,options)
	perform_copy_optimisations1(nests,options)
	perform_copy_optimisations2(nests,options)
	nests.each do |nest|
		children = get_children(nest)
		recursive_copy_optimisations(children,options) if !children.empty?
	end
	perform_copy_optimisations3(nests,options)
	perform_copy_optimisations3(nests,options)
end

#simplify(expr) ⇒ Object

Helper method to evaluate mathematical expressions, possibly containing symbols. This method is only used for readability, without it the code is functionally correct, but expressions might be larger than needed.



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
 
# File 'lib/common.rb', line 49

def simplify(expr)
	raise_error('Invalid expression to simplify') if !expr
	expr = expr.gsub(' ','')
	
	# Immediately return if there is an array index in the expression
	return expr if expr =~ /\[/
	
	# Handle min/max functions
	if expr =~ /max/ || expr =~ /min/
		return expr
	end
	
	# Get all the variables
	vars = get_vars(expr)
	
	# Set all the variables
	hash = {}
	vars.uniq.each do |var_name|
		hash[var_name.to_sym] = var :name => var_name
		expr = expr.gsub(/\b#{var_name}\b/,"hash[:#{var_name}]")
	end
	
	# Simplify the string using the 'symbolic' gem.
	symbolic_expr = eval(expr)
	
	# Return the result as a string
	return symbolic_expr.to_s
end

#solve(equality, variable, forbidden_vars) ⇒ Object

Solve a linear equality (work in progress)



84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/common.rb', line 84

def solve(equality,variable,forbidden_vars)
	return "" if equality == ""
	
	# Perform the subtitution of the current variable
	expr = '-('+equality.gsub('=','-(').gsub(/\b#{variable}\b/,"0")+'))'
	
	# Simplify the result
	result = simplify(expr)
	
	# Return the result or nothing (if it still contains forbidden variables)
	vars = get_vars(result)
	if vars & forbidden_vars == []
		return result
	else
		return ""
	end
end