Content deleted Content added
m Added section regarding OOP, NLUI and computer programmer psyche |
Added task-parallel and resolution skeleton sections |
||
Line 79:
These skeleton algorithms are used to develop programs that work on large data based software, usually identifying the connections between data for later use. Data parallel algorithms include ‘maps’, ‘forks’ and ‘reduces’ or ‘scans’.
* ‘Maps’ are the most commonly used data parallel algorithms, and typically involve a single operation completed on a large set of data. To increase efficiency, a number of data sets have this operation applied to them simultaneously, before the data is structured together again at the end.
* ‘Forks’ are similar to ‘maps’ but they use a different operation for certain data types. This is known as [[Data parallelism|multiple data parallelism]]<ref name=":1" />. ▼
* ‘Reduces’ or ‘scans’ are used to apply prefixes to a set of data, before then applying an operation upon the data. These are different to ‘maps’ as they have a set of partial results during the runtime of the method itself.
▲‘Forks’ are similar to ‘maps’ but they use a different operation for certain data types. This is known as multiple data parallelism<ref name=":1" />.
'''Task-Parallel'''
These operations, as their name suggests, work on tasks. Each type of algorithm under this is different due to a change in the behaviour between tasks. Task parallel algorithms include ‘sequentials’, ‘farms’, ‘pipes’, ‘if’, ‘for’ and ‘while’.
* ‘Sequential’ closes and terminates a nested set of skeleton algorithms. The methods and programs that are part of the skeletons are included as terminating aspects of the program, before closing.
* ‘Farms’ are known as a group of tasks, a worker, or as a master or slave of another function. It completes the given tasks by replicating the tasks over multiple threads and running these concurrently. This divides the load for a specific thread, effectively creating a master / slave relationship between the threads.
* ‘Pipes’ are the more traditional forms of algorithms, where each method or function is run in a sequence. This follows the order in which the programmer has written their code. This is made parallel by computing varied tasks on a set of data, typically input, simultaneously to improve performance and speed. Each simultaneous computation is known as a stage. The pipe algorithm can be nested, where one is within another, each splitting up responsibilities to increase speed and also the number of stages.
* ‘If’ gives the program a conditional split of tasks, where a set of skeleton code is split into two main sections. A conditional statement is given to the program, therefore giving it a specified algorithm to follow.
* ‘For’ operates a task a number of times, both specified by the programmer, allowing for a more efficient set of code. The number of times that the code runs is a preset value, indicating that at [[Run-time type information|runtime]], this cannot be changed. It must complete the task the number of times given.
* ‘While’ is an algorithm very similar to the operation of a ‘for’ algorithm, where a task is completed a number of times. However in ‘while’ algorithms, the program computes the task a number of times before a conditional statement is met. This means that the ‘while’ algorithm can perform its task a different number of times for each time it is run.
'''Resolution Skeletons'''
These skeletons are very different to the typical skeletons found above. ‘Resolution’ algorithms use a combination of methods to solve a specified problem. The algorithm’s given problem can be a “family of problems” <ref name=":1" />. There are two main types of these skeletons, ‘divide and conquer’ or ‘brand and bound’.
* ‘Divide and conquer’ uses a map skeleton as it’s basis, combining this with a while skeleton to solve the problem. In map algorithms, functions on data are applied simultaneously. In ‘divide and conquer’ the set of data provided has a function applied to it using the map skeleton, however this can be applied recursively using the ‘while’ algorithm. The ‘while’ is only broken when the entire problem is solved.
* ‘Branch and bound’ is an algorithm that also uses map algorithms, however instead of applying the ‘while’ algorithm to run the tasks simultaneously, this algorithm splits the tasks into branches. Each branch has a specific purpose, or ‘bound’, where the conditional statement will cause it to stop.
{{Portal|Computer programming}}
▲‘Reduces’ or ‘scans’ are used to apply prefixes to a set of data, before then applying an operation upon the data. These are different to ‘maps’ as they have a set of partial results during the runtime of the method itself. {{Portal|Computer programming}}
==References==
{{Reflist}}
| |||