MCA-245
Parallel Computing
Making many processors work on one problem — parallel models and Amdahl's law, memory hierarchy and pipelining, parallel algorithms, and programming platforms.
- Semester
- Semester 3
- Credits
- 3
- Scheme
- 3 lectures a week
- Contact hours
- 44 across four units
- Category
- Core Elective - III
What the paper is
Parallel Computing overlaps substantially with Advanced Computer Architecture and approaches the same material from the software side. Where that paper asks how a parallel machine is built, this one asks how a problem is decomposed to run on one.
Unit I is the theory: Flynn's and Feng's classifications, shared memory versus message passing, Amdahl's law, speedup and efficiency. Those measures are the paper's yardstick and they recur in every later unit.
Unit III's parallel algorithms — PRAM, mesh, hypercube and combinational circuit algorithms — are the part with no equivalent elsewhere in the degree, and Unit IV closes on the practical side: communication costs, routing mechanisms, and the language and compiler support that makes any of it writable.
What to concentrate on
- Amdahl's law is the most examined single result: compute the maximum speedup given a serial fraction, and explain why adding processors stops helping. Gustafson's counterpoint is worth knowing alongside it.
- Be able to compare shared-memory and message-passing models on programming difficulty, scalability and cost. It is the standing comparative question.
- For Unit III, learn one PRAM algorithm properly — parallel sum or prefix sum — including its cost and efficiency. The technique generalises to most of what else is asked.
Syllabus, unit by unit
Summarised from the approved scheme. Hours are the contact hours the scheme allots, which is a fair guide to where the marks sit.
Unit I · Theory of parallelism and parallel models
12 hours- Parallelism, reasons for parallel processing, concepts and challenges, applications
- The state of computing; classification of parallel computers; Flynn's and Feng's classifications
- SIMD and MIMD operations; shared memory versus message passing multiprocessors; distributed shared memory
- Amdahl's law, speedup and efficiency; hybrid multiprocessors, multiprocessors and multicomputers
- Multivector and SIMD computers, PRAM and VLSI models
- Conditions of parallelism, program partitioning and scheduling, program flow mechanisms, system interconnection architecture
Unit II · Memory hierarchy and instruction-level parallelism
10 hours- Memory technologies and optimisation; inclusion, coherence and locality
- Cache memory organisation and performance optimisation, shared memory organisation, memory protection, virtual memory
- Buses, crossbars and multi-stage switches
- Instruction-level parallelism: concepts and challenges, overcoming data hazards with dynamic scheduling
- Pipelining: instruction and arithmetic pipeline design, branch handling, linear and non-linear pipelines, superscalar and super pipeline design
Unit III · Parallel architectures and algorithms
10 hours- Message passing mechanisms, vector processing principles, multi-vector multiprocessors, compound vector processing
- Principles of multithreading; latency hiding techniques: shared virtual memory, pre-fetching, distributed coherent cache
- Scalable and multithreaded architectures, dataflow and hybrid architecture
- Parallel algorithms: cost and efficiency, PRAM algorithms, mesh algorithms, hypercube algorithms, combinational circuit algorithms
Unit IV · Programming platforms, languages and compilers
12 hours- Implicit parallelism and trends in microprocessor architectures; limitations of memory system performance
- The dichotomy of parallel computing platforms and their physical organisation
- Communication costs in parallel machines and routing mechanisms for interconnection networks
- Language features for parallelism and parallel language constructs
- Optimising compilers for parallelism, dependency analysis, code optimisation and scheduling, loop parallelisation and pipelining
How it is examined
- Question 1 is compulsory, covers the whole syllabus, and is made of objective or short-answer questions. It carries 12 marks.
- The rest of the paper is four units matching the four above. Each unit sets two questions and you attempt one, so there are four more answers at 12 marks each.
- Examiners are asked to map every question to a course outcome using Bloom's taxonomy, which is why questions are phrased as “apply”, “analyse” or “evaluate” rather than only “explain”.
The pass mark is 40 out of 100 in every paper.
Learning objectives
- Concepts of parallelism and how they improve the speed of operations
- The various architectures of multiprocessors
Assumed beforehand
- Computer system and architecture
- Introduction to operating systems
Paired in the scheme with MCA-267 Lab based on Core Elective III.
Books it is taught from
- TB1Ananth Grama, Anshul Gupta, George Karypis and Vipin Kumar, “Introduction to Parallel Computing”, Pearson, 2nd edition, 2003
- TB2Kai Hwang and Naresh Jotwani, “Advanced Computer Architecture”, Tata McGraw Hill, 3rd edition, 2017
- TB3Michael J. Quinn, “Parallel Computing: Theory and Practice”, McGraw-Hill, 2nd edition, 2002
Notes for MCA-245
Lecture notes, question papers and assignments filed against MCA-245 are in the library. Everything there has been checked by a moderator before it appears, and an account is free — new ones are approved by hand, which is what keeps the shelf clean.