Parallel Computers
Can we make a computing pact with parallelism?
-----------------------------------------------------------------------------------
------------------------------------------------
A parallel computer is a computer that can process data in parallel. (Big deal!) Other terms with the same general meaning include parallel distributed processing and neural networks. To appreciate this utility, consider the following analogy:
Suppose you have to dig a ditch and you have one shovel and 1000 men. Say you line up the men in single file to take turns shoveling dirt. If each man digs for one minute and clears a cubic foot of dirt, it would take 1000 minutes to dig 1000 cubic feet of dirt, not to mention the shovel hand-over time. But if you had 1000 shovels and 1000 men working concurrently, it would take one minute to clear 1000 cubic feet of dirt. That's the real dirt on parallel processing.
The following course outline (Oct., '98) presented by Mike O'Boyle gives you an idea what it would take to "dig a ditch" with a parallel computer:
Overview of Course
The course considers the challenges, concepts, techniques and tools needed to produce software for parallel computers. It begins with the background of parallel computing. A small range of simple parallel algorithms and algorithmic paradigms are introduced as vehicles for the main body of the course, which examines and contrasts each of the main approaches. Each approach is viewed through its defining properties, the challenges of implementation and examples of representative languages. It concludes with case studies involving the mapping of real applications to real parallel machines.
Prerequisites
Familiarity with standard C (or C++) and a general sequential computing background (either from past experience or through the first term Software Practicals). Prior exposure to the Parallel Architectures and/or Design and Analysis of Parallel Algorithms modules is useful.
Syllabus
Introduction
Conceptual and architectural models of parallelism.
Parallel algorithmic paradigms and simple parallel algorithms.
Pipelines, task farms, divide & conquer. Prime sieve, finite difference problems, pairwise interactions.
Parallel programming issues
Co-operation and interference. Determinism and non-determinism. Dynamic and static parallelism. Implicit and explicit parallelism. Load balancing.
Explicitly parallel models.
• Message passing models. Communications primitives. Non-determinism. Routing abstractions. MPI, occam, Poly-ML, object oriented approaches. Implementing routing - randomization.
• Shared memory models. Access & control primitives. Non-determinism. Synchrony. Sequent C. PRAM and variants. Hashing. BSP.
• Associative models. Linda, tuple space and related primitives.
• Scheduling task graphs. Static & dynamic. Formalisations, restrictions & heuristics.
Implicitly parallel models.
• Data Parallelism. Bulk-data operations. C*, High Performance Fortran.
• Loop parallelisation. Data dependence analysis and scheduling.
• Declarative models. Pure functional parallelism, graph reduction.
• `Skeletal' models.
Case studies (contributed by Edinburgh Parallel Computing Centre).
----------------------------------------------------
----------------------------------------------
The Turing model for computing has proved to be a powerful tool for dealing with problems we've faced and continue to face. But the model has speed limits, restricting use to problems that, while complex, are mainly linear and still relatively simple compared to the massive non-linear computing tasks that lie ahead of us. To meet these growing challenges we need to devise techniques that multiply the processing power by orders of magnitude. Hopefully this can be achieved with massive computing parallelism.
--------------------------------------------