Discussion:
Parallel Processing Concepts

Overview of Parallel Processing

Parallel processing is the use of multiple processors to execute different parts of the same program simultaneously.

The main goal of parallel processing is to reduce wall-clock time. There are also other reasons, which will be discussed later on in this section.

Imagine yourself having to order a deck of playing cards: a typical solution would be to first order them by suit, and then by rank-order within each suit. If there were two of you doing this, you could split the deck between you and both could follow the above strategy, combining your partial solutions at the end; or one of you could sort by suit, and the other by order within suits, both of you working simultaneously. Both of these scenarios are examples of the application of parallel processing to a particular task, and the reason for doing so is very simple: reduce the amount of time before achieving a solution. If you've ever played card games that use multiple decks, you've almost certainly engaged in parallel processing by having multiple people help with the tasks of collecting, sorting and shuffling all of the cards.

You can use this analogy to see indications of both the power and the weakness of the parallel approach, by taking it gradually to its extreme: as you increase the number of helpers involved in a particular task, you'll generally experience a characteristic speedup curve demonstrating how up-to-a-certain-number of helpers is beneficial, but any over that simply get in each others' way and reduce the overall time to completion. Consider, for example, how little it would help to have 52 people crowding around a table, each responsible for putting one particular card into its proper place in the deck -- this is exactly what is meant by the adage Too many cooks spoil the broth.

Accepting reduction of wall-clock time as the fundamental goal of our activities, why necessarily focus on parallel programming as the means to this end? Aren't there other approaches that can also yield fast turnarounds? Yes, indeed there are, the most significant being the oldest: "beef up that old mainframe," make the standalone single-processor design larger (e.g., increase the amount of memory it can directly address) and more powerful (e.g., increase its basic wordlength and computational precision) and faster (e.g., use smaller-micron etching technology, packing more transistors into less space, and coupling everything with larger and faster communications pathways).

This approach, though, can only be pushed so far, and indications are getting stronger and stronger that fundamental limitations are going to put permanent roadblocks up before too much longer. Three of these are:

To set a foundation for our examination of parallel processing, we need to understand just what kinds of processing alternatives have already been identified, and where they fit into the "parallel picture", if you will. One of the longest-lived and still very reasonable classification schemes was proposed by Flynn, in 1966, and distinguishes computer architectures according to how they can be classified along two independent, binary-valued dimensions; independent simply asserts that neither of the two dimensions has any effect on the other, and binary-valued means that each dimension has only two possible states, as a coin has only two distinct flat sides. For computer architectures, Flynn proposed that the two dimensions be termed Instruction and Data, and that, for both of them, the two values they could take be Single or Multiple. The two dimensions could then be drawn like a matrix having two rows and two columns, and each of the four cells thus defined would characterize a unique type of computer architecture.

Single Instruction, Single Data (SISD)

This is the oldest style of computer architecture, and still one of the most important: all personal computers fit within this category, as did most computers ever designed and built until fairly recently. Single instruction refers to the fact that there is only one instruction stream being acted on by the CPU during any one clock tick; single data means, analogously, that one and only one data stream is being employed as input during any one clock tick. These factors lead to two very important characteristics of SISD style computers:

Few actual examples of computers in this class exist; this category was included more for the sake of completeness than to identify a working group of actual computer systems. However, special-purpose machines are certainly conceivable that would fit into this niche: multiple frequency filters operating on a single signal stream, or multiple cryptography algorithms attempting to crack a single coded message. Both of these are examples of this type of processing where multiple, independent instruction streams are applied simultaneously to a single data stream.

A less technological, but perhaps more cosmopolitan example, was suggested by a participant in the Cornell Theory Center's Virtual Workshop:

"I thought of another example of a MISD process that is carried out routinely at [the] United Nations. When a delegate speaks in a language of his/her choice, his speech is simultaneously translated into a number of other languages for the benefit of other delegates present. Thus the delegate's speech (a single data) is being processed by a number of translators (processors) yielding different results."

A very important class of architectures in the history of computation, single-instruction/multiple-data machines are capable of applying the exact same instruction stream to multiple streams of data simultaneously. For certain classes of problems, e.g., those known as data-parallel problems, this type of architecture is perfectly suited to achieving very high processing rates, as the data can be split into many different independent pieces, and the multiple instruction units can all operate on them at the same time.

Many believe that the next major advances in computational capabilities will be enabled by this approach to parallelism which provides for multiple instruction streams simultaneously applied to multiple data streams. The most general of all of the major categories, a MIMD machine is capable of being programmed to operate as if it were in fact any of the four.

A few systems are exploring hybrid designs, mixing SIMD and MIMD capabilities in order to take advantage of either when the algorithm benefits most from it. The CM-5 is an example of such a system:

• Control network for SIMD (synchronous)

  In order to provide maximum efficiency for SIMD-type applications, a separate communications network is maintained for the synchronous distribution of execution instructions to all participating processors.

• Data network for MIMD (asynchronous)

  As the characteristics of the SIMD control network would greatly hinder MIMD-style communications, a totally separate asynchronous network is maintained for just this purpose.

Parallel processing has its own lexicon of terms and phrases, emphasizing those concepts that are considered to be most important to its goals and the ways in which those goals may be achieved. The following are some of the more commonly encountered ones. They are listed in an order for you to learn them, assuming you do not know any, so you can start with the first and then build up to the rest.

Task

A logically discrete section of computational work.

This is a somewhat loose definition, but adequate for this introduction. For now, think of a task as computational work you can describe simply, such as, "calculate the mean and standard deviation of 100,000 numbers," or "calculate a Fast Fourier transform."

Execution of a program sequentially, one statement at a time.

A problem that can be divided into parallel tasks. This may require changes in the code and/or the underlying algorithm.

Example of Parallelizable Problem:

Calculate the potential energy for each of several thousand independent conformations of a molecule; when done, find the minimum energy conformation

The above is an example of a problem that is amenable to parallelization; each of the conformations is independently determinable, while the calculation of the minimum such conformation is itself a parallelizable problem.

Calculation of the Fibonacci series (1,1,2,3,5,8,13,21,...) by use of the formula:

F(k + 2) = F(k + 1) + F(k)

A non-parallelizable problem, such as the calculation of the Fibonacci sequence above, would entail dependent calculations rather than independent ones -- notice how calculation of the k + 2 value uses those of both k + 1 and k, hence those three terms cannot be calculated independently, nor, therefore, in parallel.

There are two basic ways to partition computational work among parallel tasks:

• Data parallelism: each task performs the same series of calculations, but applies them to different data. For example, four processors can search census data looking for people above a certain income; each processor does the exact same operations, but works on different parts of the database.

• Functional parallelism: each task performs different calculations, i.e., carries out different functions of the overall problem. This can be on the same data or different data. For example, 5 processors can model an ecosystem, with each processor simulating a different level of the food chain (plants, herbivores, carnivores, scavengers, and decomposers).

Observed speedup of a code which has been parallelized =

         wall-clock time of serial execution 
       --------------------------------------- 
        wall-clock time of parallel execution
    

One of the most widely used indicators of parallelizability, the calculation of observed speedup is both intuitively satisfying, and potentially misleading; the former because a well-parallelized code can be shown to run in a fraction of the time that it takes the serial version, the latter because, in many respects, this is a comparison of apples and oranges: the codes are different, they perform different tasks, the algorithms may be entirely distinct. Still, there is no discounting the fact that a good job of parallelization will be evident in the amount of wallclock time it has saved the user; what is debatable is the converse: if it is not evident that a lot of time has been saved, is it because the problem itself is not parallelizable, or because the parallelization simply wasn't done well? This, by the way, is where parallel profiling tools, covered later in this presentation, can help tremendously.

The temporal coordination of parallel tasks. It involves waiting until two or more tasks reach a specified point (a sync point) before continuing any of the tasks.

• Synchronization is needed to coordinate information exchange among tasks; e.g., the previous example finding minimum energy conformation: all of the conformations had to be completed before the minimum could be found, so any task that was dependent upon finding that minimum would have had to wait until it was found before continuing.

• Synchronization can consume wall-clock time because processor(s) sit idle waiting for tasks on other processors to complete.

• Synchronization can be a major factor in decreasing parallel speedup, because, as the previous point illustrates, the time spent waiting could have been spent in useful calculation, were synchronization not necessary.

Parallelization doesn't come free, and one of the most insidious costs is the time and cycles put into making sure that all of those separate tasks are doing what they're supposed to be doing. Things that are simply taken for granted in serial execution, or that don't apply, take on special significance when there are many tasks instead of just one; the three most commonly encountered coordination tasks are:

• Time to start a task

  This involves, among other things:

  1. identifying the task
  2. locating a processor to run it
  3. loading the task onto the processor
  4. putting whatever data the task needs onto the processor
  5. actually starting the task

• Time to terminate a task

  Termination isn't a simple chore, either: at the very least, results have to be combined or transferred, and operating system resources have to be freed before the processor can be used for other tasks.

• Synchronization time, as previously explained.

A measure of the ratio of the amount of computation done in a parallel task to the amount of communication.

• Scale of granularity ranges from fine-grained (very little computation per communication-byte) to coarse-grained (extensive computation per communication-byte).
• The finer the granularity, the greater the limitation on speedup, due to the amount of synchronization needed. Remember from the very beginning of this module about considering how hard it would be to coordinate the activities of 52 people, all trying to help sort a single deck of cards?

A parallel system with many processors. "Many" is usually defined as 1000 or more processors.

A parallel system to which the addition of more processors will yield a proportionate increase in parallel speedup. Whether or not this increase occurs typically depends on some combination of:

• Hardware

  One of the most significant bottlenecks to scalability lies in the capability of the communications network -- adding more processors to a network that is already filled to capacity will not yield the expected increase in speedup, and could in fact do just the reverse.

• Parallel Algorithm

  Some algorithms are better suited to parallelism (i.e., more scalable) than others, and there are even economies of scale within parallel ones, i.e., algorithms that work well at certain scales of parallelism work poorly at higher scales, and vice versa. Generally speaking, scalable implies O(n) growth ("on the order of n"; i.e., linear) with data-size n, and preferably the growth should be O(log n).

  It should be emphasized here that great care should be taken to match the algorithm with the actual problem, and both of these with the actual size of the machine on which the problem will be attacked using that particular algorithm. A particular algorithm may appear to work quite nicely on the given problem when run on a small number of nodes, or on a part of the problem over the entire target machine, but when all three production versions are brought together, you may find that your initial tests were in fact misleading, and what worked well at a small scale works not at all at the desired scale.

• Your actual code

  Even if you use an algorithm well suited to your purposes, the way you implement it can determine how much parallelism is actually expressed in your application. Easy ways to negate the usefulness of a good algorithm include using unsuitable data objects, or failing to take into consideration how your programming language structures things like multi-dimensional arrays in order to maximize the efficiency of addressing natural blocks of data.

5. Models of Memory Access

Memory access refers to the way in which the working storage, be it "main-memory", "cache-memory", or whatever, is viewed by the programmer. Regardless of how the memory is actually implemented, e.g., if it's actually remotely located but is accessed as if it were local, the access method plays a very large role in determining the conceptualization of the relationship of the program to its data.

5.1 Shared Memory

Think of a single large blackboard, marked off so that all data elements have their own unique locations assigned, and all the members of a programming team are working together to test out a particular algorithmic design, all at the same time...this is an example of shared memory in action:

The other major distinctive model of memory access is termed distributed, for a very good reason:

Distributed memory is, for all intents and purposes, virtually synonymous with message-passing, although the actual characteristics of the particular communication schemes used by different systems may hide that fact.

• Message-passing approach: tasks communicate by sending data packets to each other

  Messages are discrete units of information, discrete meaning that they have a definite identity, and can be distinguished from all other messages ... well, that's the theory, at least. In practice, one of the most common programming errors is to forget to actually make the messages distinctly different, by giving them unique identifiers or tags. Regardless, parallel tasks use these messages to send information and requests for same to their peers.

  • Overhead is proportional to size and number of packets (more communication means greater costs; sending data is slower than accessing shared memory.)

    Message-passing isn't cheap: every one of those messages has to be individually constructed, addressed, sent, delivered, and read, all before the information it contains can be acted upon. Obviously, then, the more messages being sent, the more time and cycles spent in servicing message-oriented duties, and the less spent on the actual tasks that the messages are supposed to be subservient to. It is also clear from this portrayal that, in the general case, message-passing will take more time and effort than shared-memory.

    Having said that, it should be pointed out that shared memory scales less well than message passing, and, once past its maximum effective bandwidth utilization, the latency associated with message-passing may actually be lower than that encountered on an over-extended shared memory communications network.

  • Effective message-passing schemes overlap calculations & message-passing.

    There are ways to decrease the overhead associated with message-passing, the most significant being to somehow arrange to do as much valuable computation as possible while communication is occurring. The most easily conceived method of doing this is to have two completely separate processors, each dedicated to either computation or communication, and coupled via a dual-ported DMA (direct memory access) in order to cooperate. This is something of the nature of shared-memory being put in the service of distributed-memory, and does require a multi-processor configuration for a single entity in the distributed system.

    Other schemes involve time-slicing between the two tasks, or active-waiting where a processor waiting for a communications event, such as receipt of an awaited message or acknowledgment of delivery of a sent message, arranges for a preemptive signal to be generated when the event occurs, and then goes off and does independent computation. These alternatives require considerably more sophistication in the control programs than simply sitting and twiddling one's thumbs until the communication process completes, but can be made to be very effective.

  • Examples:

    The following are two examples of common types of message-passing systems:

    • IBM SPx

      Utilizing standard RS6000-type processors coupled via a very high speed, high bandwidth switch networking architecture, the nodes within an SPx system use a special very low-level message-passing library for the lowest-level (i.e., most efficient, fastest) mechanism for communicating with one another. On top of this is built the MPI message-passing facility, but other libraries, e.g., PVM and the IBM Proprietary MPL, are also available.

    • hypercube machines (e.g., nCube)

      Hypercube architectures typically utilize off-the-shelf processors coupled via proprietary networks (both hardware and message-passing software); the processor, as is the case in the above example, can also be proprietary, and often is when the decision is to trade price for performance, especially communications performance.

• Kendall Square ALLCACHE approach: memory was physically distributed, but appeared to the user as a single shared memory (single address space). This approach generically is referred to as "virtual shared memory" or "distributed shared memory."

  The KSR system provided the programmer with a shared-memory programming model, even though the actual design of the hardware and the network was distributed. A very sophisticated address-mapping scheme insured that the entire distributed memory space could be uniquely represented as a single shared resource. The actual communication model utilized at the lowest level, however, was in fact "message-passing", but that "lowest level" was not accessible to the programmer: all message mechanisms were used solely by the various levels of the operating system and the network, in order to assure that message traffic was running as efficiently as possible.

There are a number of bottlenecks typically encountered in the transition from serial processing to parallel processing. One of the most pernicious is that of mindset: people who have been in the computing business for a long time are understandably reluctant to have to learn a new way of designing their codes, and an efficient parallel algorithm often has little similarity to an efficient serial algorithm. The very first task in the conversion effort is to step way back from the existing serial application, and re-examine the intent it was written to serve: can this task be effectively and efficiently performed in parallel, and, if so, how best can that be accomplished?

Very often existing serial code has to be almost completely ignored, and the parallel version written virtually from scratch. This can be a major commitment of resources, and for some dusty-deck codes the projected return from such an investment is often considered to be insufficient to warrant the effort.

However, once the decision has been made to move from serial to parallel, the real nitty-gritty work of code conversion can very often be helped along by application of the growing number of automatic tools, well seasoned by the manual use of hard-learned rules of thumb.

6.1 Automatic vs. Manual Conversion

For years, ever since the first parallel system was constructed, the parallelization of existing codes has been largely the realm of manual conversion. The ultimate future goal of parallel support is to build tools capable of accepting the before-mentioned dusty-deck serial code, and returning a perfectly parallelized program suitable for execution on a particular state-of-the-art parallel system.

• Automatic parallelization

  SURPRISE!!! We're not there yet ... but we're a lot closer now than we were just a few years ago, and the effort is gaining a lot of momentum. A number of significant factors affecting parallelization and effective speedup have been identified and automated in new compilers,

  • Many compilers attempt to do some automatic parallelization, especially of DO-loops

    As will be shown in more detail later, DO-loops are natural candidates for parallelization ... just seeing one doesn't guarantee that you'll be able to parallelize, obviously, but they're a clear marker of where to start looking. Modern parallel compilers immediately examine DO-loops for the appropriate characteristics, basically independence of one type or another, and do whatever they can to take advantage of what is often called "natural parallelism" exhibited by the code.

  • Significant speedups usually require going beyond automatic level

    But, just as indicated, things aren't as automatic yet as we'd like them to be. There are still too many interlocking factors, too complex to be captured in code, that require even the best automatic tools to be used in conjunction with well-trained conversion experts. At the very minimum, it is usually necessary to alter the code so as to expose parallelism to the compiler.

• Manual parallelization

  The bulk of parallelization is still the realm of the human programmer, and this necessary resource cannot be emphasized too strongly:

  • Programmer must spend time to parallelize

    Expect this to be a time-consuming process, and budget for it ...if you expect to simply have to change a few lines, then you've likely got a nasty shock in store.

  • Some possible actions ("Rules of thumb")

    Over the years, a body of hard-learned wisdom has grown regarding how one can most efficiently extract parallelism from serial seeds; here are a few:

    • Remove inhibitors to parallelization

      Unnecessary serialization, for example, making all processes wait while one of them does something that could have been put off until a later required serial section.

      Re-arranging of loop-indices, to minimize inter-loop dependency.

    • Insert constructs or calls to library routines

      Some packages of often-used algorithms, for example, linear algebra routines, have already been parallelized. If your application has a need for such tasks, use someone else's work if at all possible.

      Constructs are commented-out keywords that are intended to be read by pre-processors and code-generators, allowing the programmer to indicate what kinds of parallelism should be attempted in certain parts of the program. Sometimes directives, which insist that things be done a certain way, and sometimes suggestions, indicating potentially useful directions, constructs often make it possible for the programmer to leave a section of serial code completely alone and still have it parallelized because of the actions taken upon recognition of the commented-out information.

    • Run code through preprocessors

      When parallel constructs, such as explained above, are used, it is typically possible to have the resulting parallel code displayed rather than simply compiled. Being able to look at what has been done by automatic means, as reflected in the modified source code, gives the programmer the opportunity both to learn how parallelism can be implemented, and to check a particular case against human knowledge and intuition.

    • Restructure algorithm

      Always be willing to re-examine the design upon which your application is based -- sometimes a simple change, such as moving a calculation outside of a loop, can have dramatic effects on parallelization.

  • Software tools are available to assist

    As indicated earlier, there is a small but growing number of software tools focused on providing assistance in the parallelization effort. These are language-dependent (mostly oriented towards Fortran), and still limited in their scope, but they can be very useful when appropriately applied. Here, "Parallel Compiler" means a compiler that understands parallel constructs and/or automatically extracts parallelism.

    More information on these tools can be found in later tutorials.

In this section, we'll spend some time discussing a major factor relevant to successful code parallelization: dependency.

Since DO-loops are prime candidates for very effective parallelization, identification of dependence is very important, even more so the determination of whether or not the dependence found will render the loop incapable of the desired parallelization.

• A LOOP-CARRIED DEPENDENCE exists when a storage location is used by a statement or statements, with at least one write, during different iterations of the loop.

  This cannot parallelize, because the order of execution of the loop's iterations is important for correct results.

  The important point, here, is that iteration-based parallelization, where different execution-streams are going to be responsible for different portions of the iteration-space of the loop, are going to wind up using incorrect values for the overlapping variable.

  Here's a piece of code demonstrating this:

  DO 500 J = 2,9
     A(J) = A(J-1) * 2.0
  500 CONTINUE
      

  

• A LOOP-INDEPENDENT DEPENDENCE exists when a storage location is used by successive statements within an iteration, but not by different iterations.

  This can parallelize, because loop iterations can be executed independently and asynchronously. As all references to the same location are being executed by the same instruction stream, hence serially, there is no possibility for untimely access.

By this point, I hope you will have gotten the joint message that:

1. Parallel processing can be extremely useful, but...
2. ... TANSTAAFL (There Ain't No Such Thing As A Free Lunch)

Here are some of the more significant ways that you can expect to spend time and encounter problems:

This section provides access to a sample program that demonstrates parallel techniques. A simple program uses the Message Passing Interface (MPI) to send the message "Hello, world" from one task to several others. The same program runs on each node, determining whether it is a sender or receiver through a variable named "me."

Here are some of the most important things you should take with you from this presentation: