|
Parralel Computing Turorial |
|
|
|
|
Written by Hemanshu Patel
|
|
Sunday, 23 December 2007 |
|
Page 14 of 18
Designing Parallel Programs CommunicationsWho Needs Communications?
The need for communications between tasks depends upon your problem:
* You DON'T need communications
o Some types of problems can be decomposed and executed in parallel with virtually no need for tasks to share data. For example, imagine an image processing operation where every pixel in a black and white image needs to have its color reversed. The image data can easily be distributed to multiple tasks that then act independently of each other to do their portion of the work.
o These types of problems are often called embarrassingly parallel because they are so straight-forward. Very little inter-task communication is required.
* You DO need communications
o Most parallel applications are not quite so simple, and do require tasks to share data with each other. For example, a 3-D heat diffusion problem requires a task to know the temperatures calculated by the tasks that have neighboring data. Changes to neighboring data has a direct effect on that task's data.
Factors to Consider:
There are a number of important factors to consider when designing your program's inter-task communications:
* Cost of communications o Inter-task communication virtually always implies overhead.
o Machine cycles and resources that could be used for computation are instead used to package and transmit data.
o Communications frequently require some type of synchronization between tasks, which can result in tasks spending time "waiting" instead of doing work.
o Competing communication traffic can saturate the available network bandwidth, further aggravating performance problems.
* Latency vs. Bandwidth o latency is the time it takes to send a minimal (0 byte) message from point A to point B. Commonly expressed as microseconds.
o bandwidth is the amount of data that can be communicated per unit of time. Commonly expressed as megabytes/sec.
o Sending many small messages can cause latency to dominate communication overheads. Often it is more efficient to package small messages into a larger message, thus increasing the effective communications bandwidth.
* Visibility of communications o With the Message Passing Model, communications are explicit and generally quite visible and under the control of the programmer.
o With the Data Parallel Model, communications often occur transparently to the programmer, particularly on distributed memory architectures. The programmer may not even be able to know exactly how inter-task communications are being accomplished.
* Synchronous vs. asynchronous communications o Synchronous communications require some type of "handshaking" between tasks that are sharing data. This can be explicitly structured in code by the programmer, or it may happen at a lower level unknown to the programmer.
o Synchronous communications are often referred to as blocking communications since other work must wait until the communications have completed.
o Asynchronous communications allow tasks to transfer data independently from one another. For example, task 1 can prepare and send a message to task 2, and then immediately begin doing other work. When task 2 actually receives the data doesn't matter.
o Asynchronous communications are often referred to as non-blocking communications since other work can be done while the communications are taking place.
o Interleaving computation with communication is the single greatest benefit for using asynchronous communications.
* Scope of communications o Knowing which tasks must communicate with each other is critical during the design stage of a parallel code. Both of the two scopings described below can be implemented synchronously or asynchronously.
o Point-to-point - involves two tasks with one task acting as the sender/producer of data, and the other acting as the receiver/consumer.
o Collective - involves data sharing between more than two tasks, which are often specified as being members in a common group, or collective. Some common variations (there are more):
Collective communications examples
* Efficiency of communications o Very often, the programmer will have a choice with regard to factors that can affect communications performance. Only a few are mentioned here.
o Which implementation for a given model should be used? Using the Message Passing Model as an example, one MPI implementation may be faster on a given hardware platform than another.
o What type of communication operations should be used? As mentioned previously, asynchronous communication operations can improve overall program performance.
o Network media - some platforms may offer more than one network for communications. Which one is best?
* Overhead and Complexity
Callgraph of parallel hello world program
* Finally, realize that this is only a partial list of things to consider!!!
|
|
Last Updated ( Sunday, 23 December 2007 )
|
Technology 