SOLVING PROBLEMS IN
PARALLEL
CONTENTS
• Utilizing temporal parallelism
• Utilizing data parallelism
• Comparison
TEMPORAL PARALLELISM
• There are two major types of parallelism, namely temporal and spatial parallelism
• Temporal parallelism refers to the execution of a task as a 'cascade' of sub-tasks.
• There exists one functional unit to carry out each sub-task.
• This case is called SIMD (Single Instruction stream, Multiple Data stream),
• All these successive units can work at the same time, in an overlapped fashion.
• As data are processed by a given unit Uj , they are sent to the next unit Uj+1 and the unit Uj
restarts its processing on new data.
• Each functional unit can be seen as a "specialized" processor in the sense that it always execute
the same sub-task.
SPATIAL PARALLELISM
• Spatial parallelism - the simultaneous execution of tasks by several processing units.
• At a given instant, these units can be executing the same task (or instruction) or different
tasks.
• This case is called MIMD (Multiple Instruction stream, Multiple Data stream).
• Within the MIMD category, the physical realization can involve a shared-memory or a
distributed-memory organization
Example – Temporal parallelism
Example - Temporal parallelism
• The type of parallel processing used in this method is called temporal parallelism.
• The term temporal means pertaining to time.
• As this method breaks up a job into a set of tasks to be executed overlapped in time, it is
said to use temporal parallelism.
• It is also known as assembly line processing, pipeline processing, or vector processing
Example - Submission Of Electricity Bills
Assume that there are 10000 residents in a society and they are thought to submit their electricity bills in one workplace.
Let us suppose the steps to submit the bill are as pursue:
1) Go to the suitable counter to take the form to give in the bill.
2) Submit the cash with along the filled form.
3) Get the payment receipt of submitted bill.
Imagine that there is only one counter with just single office person performing all the tasks of giving application forms, accepting the forms, counting the cash,
returning the cash if the need be, and giving the receipts.
Let us the take estimated time taken by several of events is as follows:
In Giving request form = 5 seconds
Accepting filled request form and counting the money and persistent, if required = 5mnts, i.e., 5 ×60= 300 sec.
Giving payment receipts = 5 seconds.
Total time taken in processing the process of one bill = 5+300+5 = 310 seconds.
Example - Submission Of Electricity Bills
Suppose if we have 3 peoples sitting at three dissimilar counters with
i) One person submit the bill submission form
ii) One person taking the cash and returning, if necessary
iii) One person giving the receipt.
The time necessary to complete the process of one bill will be 300 sec because the First and third
activity will be related with the second activity which takes 300 sec.
However, the first and last activity takes only 10 seconds each.
This is a best example of a parallel processing process as here 3 peoples work in parallel. As three
peoples work in the common time, it is called temporal parallelism.
Mathematical representation
• Let the number of jobs = n ; Let the time to do a job = p
• Let each job be divisible into k tasks and let each task be done by a different teacher.
• Let the time for doing each task = p/k.
• Time to complete n jobs with no pipeline processing = np.
• Time to complete n jobs with a pipeline organization of k teachers
• If n >> k then (k – 1)/n = 0 and the speedup is nearly equal to k, the number of teachers in the
pipeline.
Issues in implementing temporal parallelism
1. Synchronization. Identical time should be taken for doing each task in the pipeline so that
a job can flow smoothly in the pipeline without holdup.
2. Bubbles in pipeline. If some tasks are absent in a job “bubbles” form in the pipeline. For
example, if there are some answer books with only 2 questions answered, two teachers will
be forced to be idle during the time allocated to them to correct these answers.
3. Fault tolerance. The system does not tolerate faults. If one of the teachers takes a coffee
break, the entire pipeline is upset.
Issues in implementing temporal parallelism
4. Inter-task communication. The time to pass answer books between teachers in the pipeline
should be much smaller as compared to the time taken to correct an answer by a teacher.
5. Scalability. The number of teachers working in the pipeline cannot be increased beyond a
certain limit. The number of teachers would depend on how many independent questions a
question paper has.
Further, the time taken to correct the answer to each of the questions should be equal and the
number of answer books n must be much larger than k, the number of teachers in the pipeline.
Utilization Of Data Parallelism
• Assuming each teacher takes 20 minutes to correct an answer book, the time taken to
correct all the 1000 answer books is 5000 minutes as each teacher corrects only 250
papers and all teachers work simultaneously.
• This type of parallelism is called data parallelism as the input data is divided into
independent sets and processed simultaneously.
• We can quantify this method as shown below:
Let the number of jobs = n
Let the time to do a job = p
Let there be k teachers to do the job
Mathematical Representation
Let the time to distribute the jobs to k teachers be kq. Observe
that this time is proportional to the number of teachers.
The time to complete n jobs by a single teacher = np
The time to complete n jobs by k teachers = kq + np/k
Speedup due to parallel processing =
If k2q << np then the speedup is nearly equal to k, the number
of teachers working independently.
Observe that this will be true if the time to distribute the jobs is
small.
Example
Let n = 1000, p = 20 and k = 4.
Let the time to create one subset of jobs q = 1. Then kq = 4.
If we define efficiency as the ratio of actual speedup to maximum possible speedup we get:
If k = 100 then
Observe that the speedup is not directly proportional to the number of teachers as the time to distribute jobs
to teachers (which is an unavoidable overhead) increases as the number of teachers is increased.
Advantages
1. There is no synchronization required between teachers. Each teacher can correct papers
independently at his own pace.
2. The problem of bubbles is absent. If a question is unanswered in a paper it only reduces
the time to correct that paper.
3. This method is more fault tolerant. One of the teachers can take a coffee break without
affecting the work of other teachers.
4. There is no communication required between teachers as each teacher works
independently. Thus, there is no inter-task communication delay.
Issues In Implementing Data Parallelism
Static assignment of jobs is not efficient.
The assignment of jobs to each teacher is pre-decided (static assignment). Thus, if a teacher is
slow then the completion time of the total job will be slowed down. If another teacher gets many blank
answer books he will complete his work early and will thereafter be idle. Thus, We must be able to
divide the set of jobs into subsets of mutually independent jobs. Each subset should take the same time
to complete.
Each teacher must be capable of correcting answers to all questions.
This is to be contrasted with pipelining in which each teacher specialized in correcting the answer
to only one question.
The time taken to divide a set of jobs into equal subsets of jobs should be small.
Further, the number of subsets should be small as compared to the number of jobs.
Combined Temporal And Data Parallelism
• Here two pipelines of teachers are formed and each pipeline is given half the total number
of jobs.
• This is called parallel pipeline processing.
• This method almost halves the time taken by a single pipeline.
• If it takes 5 minutes to correct an answer book, the time taken by the two pipelines is (20
+ 499 × 5) = 2515 minutes.
Eight teachers working in two pipeline to
evaluate 2 sets of answer books
Even though this method reduces the time to complete the set of
jobs, it also has the disadvantages of both temporal parallelism and
to some extent that of data parallelism.
The method is effective only if the number of jobs given to each
pipeline is much larger than the number of stages in the pipeline.
Multiple pipeline processing was used in supercomputers such as
Cray and NEC-SX, this method is very efficient for numerical
computing in which a number of long vectors and large matrices
are used as data and could be processed simultaneously.
Data Parallelism With Dynamic Assignment
• Here a head examiner gives one answer paper to each teacher and keeps the rest with
him. All teachers simultaneously correct the paper given to them.
• A teacher who completes correction goes to the head examiner for another paper which is
given to him for correction.
• If a second teacher completes correction at the same time, then he queues up in front of
the head examiner and waits for his turn to get an answer paper.
• The procedure is repeated till all the answer papers are corrected.
Data Parallelism With Dynamic Assignment
Advantage
• The balancing of the work assigned to each teacher dynamically as work progresses.
• A teacher who finishes his work quickly gets another paper immediately and he is not
forced to be idle.
• The time to correct a paper may widely vary without creating a bottleneck.
• The method is not affected by bubbles, namely, unanswered questions or blank answer
papers.
• The overall time taken for paper correction will be minimized.
Disadvantages
1. If many teachers complete correcting an answer paper simultaneously only one of
them will get the next paper at once as the examiner can attend to only one teacher at
a time. The other teachers have to wait in a queue to get their next answer paper.
2. The head examiner can become a bottleneck. If he takes a coffee break, all teachers
will be idle. However, a teacher taking a coffee break does not cause breakdown of
the system.
3. The head examiner himself is idle between handing out papers.
4. It is difficult to increase the number of teachers as it will increase the probability of
many teachers completing their jobs simultaneously thereby leading to long queues of
teachers waiting to get an answer paper
Mathematical Representation
If the speedup of a method is directly proportional to the number of processors, then the method is said to scale well.
The scalability of the dynamic assignment method:
Let the total number of papers = n.
The time to correct n papers (no parallel processing) = np, where p is the average time to correct a paper.
Let k teachers be employed to work in parallel.
Let the time a teacher waits to get an answer book from the head examiner and to return it to the head examiner
be q.
The time taken by each teacher to get a paper from the head examiner, grade, and return it = (q + p).
Assuming that each teacher corrects (n/k) papers and all teachers work simultaneously the total time taken to
correct all the papers by k teachers
Comparison Of Temporal And Data Parallelism
Temporal parallel processing Data Parallel processing
1. Job is divided into a set of independent tasks and 1. Full jobs are assigned for processing.
tasks are assigned for processing. 2. Jobs may take different times. No need to
2. Tasks should take equal time. Pipeline stages synchronize beginning of jobs.
should thus be synchronized. 3. Bubbles do not cause idling of processors.
3. Bubbles in jobs lead to idling of processors. 4. Processors should be general purpose and may not
do all tasks efficiently.
4. Processors specialized to do specific tasks
efficiently.
Comparison Of Temporal And Data Parallelism
Temporal parallel processing Data Parallel processing
5. Task assignment static. 5. Job assignment may be static, dynamic, or quasi-
dynamic.
6. Not tolerant to processor faults.
6. Tolerates processor faults.
7. Efficient with fine grained tasks
7. Efficient with coarse grained tasks and quasi-
8. Scales well as long as number of data items to be dynamic scheduling.
processed is much larger than the number of 8. Scales well as long as number of jobs is much greater
than the number of processors and processing time is
processors in the pipeline and time taken to
much higher than the
communicate task from one processor to the next is
negligible.
Exercise
1. An examination paper has 8 questions to be answered and there are 1000 answer books.
Each answer takes 3 minutes to correct.
If 4 teachers are employed to correct the papers in a pipeline mode, how much time will
be taken to complete the job of correcting 1000 answer papers?
What is the efficiency of processing?
If 8 teachers are employed instead of 4, what is the efficiency?
What is the job completion time in the second case? Repeat with 32 teachers and 4
pipelines.
Exercise
2. An examination paper has 4 questions. The answers to these questions do not take equal
time to correct. Answer to question 1 takes 2 minutes to correct, question 2 takes 3 minutes,
question 3 takes 2.5 minutes and question 4 takes 4 minutes. Due to this speed mismatch,
storage should be provided between teachers (e.g., a tray where a teacher finishing early can
keep the paper for the slower teacher to take it). Answer the following questions assuming
1000 papers are to be corrected by 4 teachers.
(i) What is the idle time of teachers?
(ii) What is the system efficiency?
(iii) How much tray space should be provided between teachers due to speed mismatch?
Reference
• “ Parallel Computers Architecture and Programming”, PHI publishers, V.
RajaRamam & C. Siva Ram Murthy