Tutorial - Parallel Constructs - Revision history

Polas: 5 revisions imported

2019-04-15T15:44:58Z

5 revisions imported

Polas at 18:26, 19 January 2013

2013-01-19T18:26:02Z

Polas at 15:40, 15 January 2013

2013-01-15T15:40:05Z

Polas: /* Allocation inference */

2013-01-15T15:27:36Z

‎Allocation inference

Polas at 15:23, 15 January 2013

2013-01-15T15:23:10Z

Polas: Created page with '== Introduction == In this tutorial we shall look at more advanced parallel constructs as to what were discussed in the Hello world tutorial. There wi…'

2013-01-15T14:51:56Z

Created page with '== Introduction == In this tutorial we shall look at more advanced parallel constructs as to what were discussed in the Hello world tutorial. There wi…'

New page

== Introduction ==

In this tutorial we shall look at more advanced parallel constructs as to what were discussed in the [[Tutorial - Hello world|Hello world]] tutorial. There will also be some reference made to the concepts noted in the [[Tutorial - Functions|functions]] and [[Tutorial - Simple Types|simple types]] tutorials too.

== Parallel composition ==

In the [[Tutorial - Hello world|Hello world]] tutorial we briefly saw an example of using parallel composition (||) to control parallelism. Let's now further explore this with some code examples:

#include <io>
#include <string>
#include <parallel>

function void main() {
{
var i:=pid();
print("Hello from PID "+itostring(i)+"\n");
} || {
var i:=30;
var f:=20;
print("Addition result is "+itostring(i+f)+"\n");
};
};

Which specifies two blocks of code, both running in parallel (two processes), the first will display a message with the process ID in it, the other process will declare two [[Int]] variables and display the result of adding these together. This approach; of specifying code in blocks and then using parallel composition to run the blocks in parallel, on different processes, is a useful one. As a further exercise try rearranging the blocks and view the value of the process ID reported, also add further parallel blocks (via more parallel composition) to do things and look at the results.

=== Unstructured parallel composition ===

In the previous example we structured parallel composition by using blocks, it is also possible to run statements in parallel using this composition, although it is important to understand the associativity and precedence of parallel composition and sequential composition when doing so.

#include <io>
#include <string>
#include <parallel>

function void main() {
var i:=0;
var j:=0;
var z:=0;
var m:=0;
var n:=0;
var t:=0;

{i:=1;j:=1||z:=1;m:=1||n:=1||t:=1;};

print(itostring(pid())+":: i: "+itostring(i)+", j: "+itostring(j)+", z: "+itostring(z)
+", m: "+itostring(m)+", n: "+itostring(n)+", t: "+itostring(t)+"\n");
};

← Older revision		Revision as of 18:26, 19 January 2013
Line 1:		Line 1:
		+	<metadesc>Tutorial describing how to structure parallel code in Mesham</metadesc>
		+	'''Tutorial number four''' - [[Tutorial_-_Functions\|prev]] :: [[Tutorial_-_Shared Memory\|next]]
	== Introduction ==		== Introduction ==

← Older revision		Revision as of 15:40, 15 January 2013
Line 73:		Line 73:

	If you try to compile this code, then you will get the error ''Process 0 in the single allocation is not in parallel scope'' which is because you have attempted to allocate variable ''i'' to process 0 but this is not in scope so can never be done. Whilst we have been experimenting with the [[Group\|group]] parallel construct, the same behaviour is true of all parallel structural constructs.		If you try to compile this code, then you will get the error ''Process 0 in the single allocation is not in parallel scope'' which is because you have attempted to allocate variable ''i'' to process 0 but this is not in scope so can never be done. Whilst we have been experimenting with the [[Group\|group]] parallel construct, the same behaviour is true of all parallel structural constructs.
		+
		+	== Nesting parallelism ==
		+
		+	Is currently disallowed, whilst it can provide more flexibility for the programmer it makes for a more complex language from the designer and compiler writer point of view.
		+
		+	function void main() {
		+	var p;
		+	par p from 0 to 3 {
		+	proc 0 {
		+	skip;
		+	};
		+	};
		+	};
		+
		+	If you compile the following code then it will result in the error ''Can not currently nest par, proc or group parallel blocks''.
		+
		+	== Parallelism in other functions ==
		+
		+	Up until this point we have placed our parallel constructs within the ''main'' function, but there is no specific reason for this.
		+
		+	#include <io>
		+
		+	function void main() {
		+	a();
		+	};
		+
		+	function void a() {
		+	group 1,3 {
		+	print("Hello from 1 or 3\n");
		+	};
		+	};
		+
		+	If you compile and run the following code then you will see that processes 1 and 3 display the message to standard output. An an exercise modify this code to include further functions which have their own parallel constructs in and call them from the ''main'' or your own functions.
		+
		+	An important point to bear in mind with this is that ''a'' is now a parallel function and there are some points to consider with this. Firstly, all parallel constructs ([[Par\|par]], [[Proc\|proc]] and [[Group\|group]) are blocking calls - hence all processes must see these, so to avoid deadlock all processes must call the function ''a''. Secondly, as discussed in the previous section, remember how we disallow nested parallelism? Well we relax this restriction here '''but''' it is still not safe
		+
		+	#include <io>
		+
		+	function void main() {
		+	var p;
		+	par p from 0 to 3 {
		+	a();
		+	};
		+	};
		+
		+	function void a() {
		+	group 1,3 {
		+	print("Hello from 1 or 3\n");
		+	};
		+	};
		+
		+	If you compile the following code then it will work, but you will get the warning ''It might not be wise calling a parallel function from within a parallel block''. Running the executable will result in the correct output, but changing a ''3'' to a ''2'' in the [[Par\|par]] loop will result in deadlock. Therefore it is best to avoid this technique in practice.
		+	[[Category:Tutorials\|Parallel Constructs]]

← Older revision		Revision as of 15:27, 15 January 2013
Line 72:		Line 72:
	};		};

−	If you try to compile this code, then you will get the error ''Process 0 in the single allocation is not in parallel scope'' which is because you have attempted to allocate variable ''i'' to process 0 but this is not in scope so can never be done.	+	If you try to compile this code, then you will get the error ''Process 0 in the single allocation is not in parallel scope'' which is because you have attempted to allocate variable ''i'' to process 0 but this is not in scope so can never be done. Whilst we have been experimenting with the [[Group\|group]] parallel construct, the same behaviour is true of all parallel structural constructs.

← Older revision		Revision as of 15:23, 15 January 2013
Line 45:		Line 45:
	+", m: "+itostring(m)+", n: "+itostring(n)+", t: "+itostring(t)+"\n");		+", m: "+itostring(m)+", n: "+itostring(n)+", t: "+itostring(t)+"\n");
	};		};
		+
		+	This is a nice little code to help figure out what, for each process, is being run. You can further play with this code and tweak it as required. Broadly, we are declaring all the variables to be [[Int\|Ints]] of zero value and then executing the code in the { } code block followed by the [[Print\|print]] statement on all processes. Where it gets interesting is when we look at the behaviour inside the code block itself. The assignment ''i:=1'' is executed on all processes, sequentially composed with the rest of the code block, ''j:=1'' is executed just on process 0, whereas at the same time the value of 1 is written to variables ''z'' and ''m'' on process 1. Process 2 performs the assignment ''n:=1'' and lastly process 3 assigns 1 to variable ''t''. From this example you can understand how parallel composition will behave when unstructured like this - as an exercise add additional code blocks (via braces) and see how that changes the behaviour my specifying explicitly what code belongs where.
		+
		+	The first parallel composition will bind to the statement (or code block) immediately before it and then those after it - hence ''i:=1'' is performed on all processes but those sequentially composed statements after the parallel composition are performed just on one process. Incidentally, if we removed the { } braces around the unstructured parallel block, then the [[Print\|print]] statement would just be performed on process 3 - if it is not clear why then have an experiment and reread this section to fully understand.
		+
		+	== Allocation inference ==
		+
		+	If we declare a variable to have a specific allocation strategy within a parallel construct then this must be compatible with the scope of that construct. For example:
		+
		+	function void main() {
		+	group 1,3 {
		+	var i:Int::allocated[multiple[]];
		+	};
		+	};
		+
		+	If you compile the following code, then it will work but you get the warning ''Commgroup type and process list inferred from multiple and parallel scope''. So what does this mean? Well we are selecting a [[Group\|group]] of processes (in this case processes 1 and 3) and declaring variable ''i'' to be an [[Int]] allocated to all processes; however the processes not in scope (0 and 2) will never know of the existence of ''i'' and hence can never be involved with it in any way. Even worse, if we were to synchronise on ''i'' then it might cause deadlock on these other processes that have no knowledge of it. Therefore, allocating ''i'' to all processes is the wrong thing to do here. Instead, what we really want is to allocate ''i'' to a group of processes that in parallel scope using the [[Commgroup\|commgroup]] type, and if omitted the compiler is clever enough the deduce this, put that behaviour in but warn the programmer that it has done so.
		+
		+	If you modify the type chain of ''i'' from ''Int::allocated[multiple[]]'' to ''Int::allocated[multiple[commgroup[]]]'' and recompile you will see a different warning saying that it has just inferred the process list from parallel scope (and not the type as that is already there.) Now change the type chain to read ''Int::allocated[multiple[commgroup[1,3]]]'' and recompile - see that there is no warning as we have explicitly specified the processes to allocate the variable to? It is up to you as a programmer and your style to decide whether you want to explicitly do this or put up with the compiler warnings.
		+
		+	So, what happens if we try to allocate variable ''i'' to some process that is not in parallel scope? Modify the type chain of ''i'' to read ''Int::allocated[multiple[commgroup[1,2]]]'' and recompile - you should see an error now that looks like ''Process 2 in the commgroup is not in parallel scope''. We have the same protection for the single type too:
		+
		+	function void main() {
		+	group 1,3 {
		+	var i:Int::allocated[single[on[0]]];
		+	};
		+	};
		+
		+	If you try to compile this code, then you will get the error ''Process 0 in the single allocation is not in parallel scope'' which is because you have attempted to allocate variable ''i'' to process 0 but this is not in scope so can never be done.

← Older revision	Revision as of 15:44, 15 April 2019
(No difference)