|[home] [introduction] [types] [applications] [future] [about]|
|Types of Parallelism|
What Are The Different Types of Parallelism?
There are many different problems that the parallel approach can be applied to. This leads to several different types of parallelism. We shall look at an analogy in order to examine the different types. The different types, by the way, are known as paradigms of parallelism.
If we imagine a membership office for a book club, taking phone messages from prospective customers, checking records etc. If 20 people phoned up at the same time and there was only one person to accept calls from the switchboard then each person would have to be dealt with sequentially. However if you had two operators then you could deal with them two at a time. Assuming each caller takes roughly the same amount of time to deal with, then the more operators n there are to deal with customers m, the less time is taken in dealing with the total number of callers. The total time taken is reduced to the time it takes to deal with a single caller when m = n.
This is known as a trivially parallel system. It is easy to find a parallel solution. Obviously the operator should put customers in the shortest queue available or some operator could be left doing nothing while some are kept busy all the time. The other types are more complicated and thus will have an example and solution of their own. In our book club analogy, imagine that only one household may have a membership and the father of the family already has a membership. However he wishes to cancel his membership yet his daughter wishes to have one instead. She can't have her membership until he has cancelled his, yet if both try to do tese task over the phone at once we may have problems in a trivially parallel system. Therefore some kind of ordering is required. Thus the types described are broken down into two general forms to deal with this kind of problem : synchronous and asynchronous.
Synchronous or lockstep coordination forces the hardware to perform all operations at once in a manner that eliminates dependancy of one task on another.
Asynchronous forms rely upon mechanisms called locks to coordinate the processors.
If the book club office received a lot of calls where each call requires several identical steps to process, several different methods may be used to deal with this. The first synchronous method is the vector paradigm. If there was an inquiry operator to deal with the initial enquiry, a records assistant to fetch and examine the membership files and some other people with specific tasks to process a customer, then each person could perform the task passed on by the previous person. The accompanying diagram makes this clear. To a single customer the time taken is nearly the same (ignoring time taken to communicate between staff) yet the office can have up to four people (in the example given) being dealt with at the same time thus reducing the time waiting to be dealt with. This breaking up into small tasks is known as fine grain parallel processing. For programs involving many simple calculations ie matrix multiplication programs this is very useful.
SIMD (or Single Instruction Multiple Data) parallelism is another type of synchronous parallelism. In this case the four operators do the same thing at the same time or remain idle. The system is data driven, ie the data is available to the operators before the queiries arrive. There are two phases to this. First the data is partitioned and then distributed. All relevant information about a particular customer is given to a particular operator. Secondly the data is processed in parallel. So the switchboard directs the enquiries to the correct operator. The operators then cancel membership details then update new memberships where relevant. This prevents the problem of the father and daughter. Obviously this situation in a real office is unlikely to ever occur, yet processing of this type is very useful when the number of processors matches the number of data pieces. It is very good at computing regular numerical calculations such as vector algebra.
The Systolic Paradigm
The third and final type of synchronous parallelism we shall discuss is systolic parallelism. It incorperates several features of the previous two types of parallelism. When a computer calculates something from some input data and then has to output the results it engages in Input/Output (IO) operations. These are often the slowest operations of a computer and therefore cause a bottleneck (for those of you unfamiliar with bottles, the bottleneck is the tightest part!). In a parallel computer bottlenecks become a major obstacle to performance. The systolic paradigm aims to reduce the amount of bottlenecks. The data is circulated as much as possible around the processors as possible before being returned to memory. If membership details in the club office are kept in a separate central computer (for secure data protection of course) and require separate access then the IO time is quite high. This is reduced by having an two dimensional "array" of staff. This paradigm is suitable for fine grain tasks. The pipelines, like in the vector paradigm, are connected from the operators to the staff members.
This is the first asynchronous paradigm. Most real world human interactions are rather more like this. The acronym stands for Multiple Instruction Multiple Data. This system can simultaneously execute different instructions on different data. They almost operate as if they were several separate computers. There is no central controller so a synchronization mechanism is used to prevent any two given customers from using the same data at once. A simple kind of synchronization method is called mutual exclusion. This means that if one process is using an data item, then no other process can access it. This is, in a weird twist, a crucial principle in most single processor operating systems. In our example, if the office had no computer, just a large file cabinet (who knows, not everyone has embraced the digital age!), then if one operator had a customers folder then obviously no one else could have it. However, if a person merely wanted to look at data contained and not change it, this is clearly unsatisfactory. Time is wasted as only operators who need to write should lock up their files. A whole group of people who are only reading should be able to access the file.
So, to get round this you could apply read/write locks. Someone who is reading can lock out writers but not other readers and someone who is writing can lock out everybody else. This is called shared-memory MIMD.
There is yet another option. Everytime data is needed by an operator a copy is made at the file cabinet and given to the operator. There it stays for the rest of the day until a change needs to be made. Now, when a change needs to be made, there are different ways of doing this. Firstly, one could retrieve the data from the operators, update the original and repeat the process. Another way is to send a memo to each operator, telling them that changes have been made and that they should get new copies. This approach uses cache memory. However these methods do not prevent out of order access all the time. The programmer must ensure his mechanism can deal with this. This is also a method that is good with large grain applications as there woill be less overhead such as memory access and IO.