Parallel Programming 2nd Edition
43 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What are the key issues in network design?

Bandwidth, latency, and cost

What is bandwidth?

The number of bits that can be transmitted in unit time, given as bits/sec

Define network latency.

The time to make a message transfer through the network

What does message latency refer to?

<p>The time to send a zero-length message, including overhead</p> Signup and view all the answers

How is the diameter of a network defined?

<p>The minimum number of links between the two farthest nodes</p> Signup and view all the answers

What is bisection width?

<p>The minimum number of links that must be cut to divide the network into two equal parts</p> Signup and view all the answers

The number of physical links in a path between two nodes is a major factor in determining the ______ for a message.

<p>delay</p> Signup and view all the answers

Match the following types of network topologies with their characteristics:

<p>Mesh = Nodes connect to four nearest neighbors Hypercube = Nodes are arranged in a d-dimensional binary structure Tree = Has two links connecting to two switches below each node Multistage Interconnection = A network with levels of switches</p> Signup and view all the answers

A two-dimensional mesh can have a diameter of $2(p - 1)$.

<p>True</p> Signup and view all the answers

What is a notable advantage of the hypercube network?

<p>The diameter of the network is given by log2 p for a p-node hypercube</p> Signup and view all the answers

In a hypercube network, each node can connect to nodes whose addresses differ by two bits.

<p>False</p> Signup and view all the answers

What is a binary fat tree?

<p>A binary tree with additional links added toward the root</p> Signup and view all the answers

What is the function of the crossbar switch?

<p>To provide exhaustive connections between processors and memories</p> Signup and view all the answers

What kind of tree structure does a tree network typically use?

<p>Complete binary tree</p> Signup and view all the answers

What is the primary focus of this text?

<p>Parallel programming techniques</p> Signup and view all the answers

Which programming models are mentioned in the text?

<p>All of the above</p> Signup and view all the answers

The first edition of this text focused exclusively on shared memory programming.

<p>False</p> Signup and view all the answers

What does MPI stand for?

<p>Message Passing Interface</p> Signup and view all the answers

What is one of the main disadvantages of message-passing programming?

<p>The programmer must specify explicitly where and when the message passing should occur.</p> Signup and view all the answers

The shared memory model can be employed on a cluster with appropriate ___ software.

<p>distributed shared memory</p> Signup and view all the answers

What chapter has been added in the second edition regarding shared memory programming?

<p>A chapter on shared memory programming on clusters</p> Signup and view all the answers

What is a prerequisite for studying Part I of the text?

<p>Knowledge of sequential programming</p> Signup and view all the answers

All software for message-passing parallel programming is proprietary and requires a purchase.

<p>False</p> Signup and view all the answers

What is the formula for efficiency, E?

<p>E = ts / (tp × p)</p> Signup and view all the answers

What does the speedup factor S(p) represent?

<p>S(p) = ts / (fts + (1 - f)ts / p)</p> Signup and view all the answers

The maximum speedup is limited to a ratio of 1/f.

<p>True</p> Signup and view all the answers

Amdahl's law describes the speedup factor as _____.

<p>S(p) = ts / (fts + (1 - f)ts / p)</p> Signup and view all the answers

Which of the following is not a factor limiting speedup in parallel computing?

<p>Increased power supply</p> Signup and view all the answers

What does Scalability refer to in computing?

<p>Scalability refers to the ability of a system to handle a growing amount of work or its potential to be enlarged.</p> Signup and view all the answers

What is the computing/communication ratio?

<p>Computation/communication ratio = tcomp / tcomm</p> Signup and view all the answers

Which of the following types of parallel computers require multiple computers interconnected?

<p>Distributed-memory multicomputer</p> Signup and view all the answers

In message-passing systems, each computer has access to the memory of the others.

<p>False</p> Signup and view all the answers

Parallel execution time, tp, consists of _____ and _____.

<p>tcomm, tcomp</p> Signup and view all the answers

What is the demand for greater computational power from computers focused on?

<p>Numerical simulation of scientific and engineering problems.</p> Signup and view all the answers

Which of the following areas require great computational speed? (Select all that apply)

<p>Weather forecasting</p> Signup and view all the answers

Simulation that takes two weeks to reach a solution is acceptable in a design environment.

<p>False</p> Signup and view all the answers

What is a grand challenge problem?

<p>A problem that cannot be solved in a reasonable amount of time with today's computers.</p> Signup and view all the answers

The speedup factor, S(p), is a measure of relative performance which is defined as ________.

<p>Execution time using a single processor system (with the best sequential algorithm) divided by execution time using a multiprocessor with p processors.</p> Signup and view all the answers

What does S(p) represent?

<p>The relative performance of a multiprocessor compared to a single processor.</p> Signup and view all the answers

Superlinear speedup occurs when S(p) is less than p.

<p>False</p> Signup and view all the answers

What is required for achieving linear speedup in parallel processing?

<p>Equal-duration processes</p> Signup and view all the answers

Forecasting the weather involves dividing the air into a ________.

<p>three-dimensional grid of solution points.</p> Signup and view all the answers

Which of the following contributes to increased computational speed using parallel computing? (Select all that apply)

<p>Dividing the problem into independent parts</p> Signup and view all the answers

Study Notes

Preface

  • This is the second edition of a textbook on parallel programming techniques and applications using networked workstations and parallel computers.

Authors and Acknowledgments

  • The authors are Barry Wilkinson and Michael Allen from the University of North Carolina at Charlotte and Western Carolina University.
  • The authors acknowledge the support of the National Science Foundation and other institutions in the development of the textbook.

Purpose and Structure of the Textbook

  • The purpose of the textbook is to introduce parallel programming techniques to students.
  • The textbook is divided into two parts: Part I covers the basic techniques of parallel programming, and Part II covers problem-specific algorithms.
  • Part I consists of Chapters 1 to 9, which cover topics such as parallel computers, message-passing routines, performance evaluation, and programming strategies.
  • Part II consists of Chapters 10 to 13, which cover topics such as sorting, numerical algorithms, image processing, and searching and optimization.

Prerequisites and Course Structure

  • The prerequisite for studying Part I is a knowledge of sequential programming, which can be learned from using the C language.
  • The textbook can be used for both undergraduate and graduate-level courses on parallel programming.
  • A selection of topics from Part I can be used as an addition to a normal sequential programming class.

Home Page and Resources

  • A Web site has been developed for this book to aid students and instructors, which provides sample programs, step-by-step instructions, and details of DSM programming.
  • An Instructor's Manual is available to instructors, which provides MPI solutions.
  • A solutions manual is available electronically from the authors.

Changes in the Second Edition

  • The second edition includes a new chapter on shared memory programming on clusters.
  • The second edition also includes new material on partially synchronous computations, sorting algorithms for clusters, and analysis of algorithms in the first part of the book.
  • Extra problems have been added to the textbook.

Applications and Importance of Parallel Programming

  • Parallel programming is important for solving large problems that cannot be solved using a single computer.
  • Parallel programming offers the opportunity to tackle larger problems with more computational steps or larger memory requirements.
  • Applications of parallel programming include image processing, signal processing, and voice recognition.### The Demand for Computational Speed
  • There is a continuous demand for greater computational power from computer systems.
  • Areas that require great computational speed include:
    • Numerical simulation of scientific and engineering problems
    • Manufacturing, where engineering calculations and simulations must be achieved within seconds or minutes
    • Grand challenge problems, such as:
      • Modeling large DNA structures
      • Global weather forecasting
  • The time taken to complete computations is crucial, as simulations that take too long are often unacceptable in design environments.
  • Weather forecasting is a key example of an application that requires very powerful computers.
    • The atmosphere is modeled by dividing it into three-dimensional regions or cells.
    • Complex mathematical equations are used to capture various atmospheric effects.
    • Conditions in each cell are computed at time intervals using conditions from the previous time interval and nearby cells.
    • Calculations are repeated many times to model the passage of time.### Forecasting and N-Body Problems
  • Forecasting over days requires a large region to be considered and is affected by very distant events
  • Dividing the globe into 1 mile × 1 mile × 1 mile cells to a height of 10 miles would result in approximately 5 × 10^8 cells
  • Each calculation requires 200 floating-point operations, and one time step would require 10^11 floating-point operations
  • To forecast the weather over 7 days with 1-minute intervals, 10^15 floating-point operations are necessary
  • A computer capable of 1 Gflops would take 10^6 seconds (over 10 days) to perform the calculation
  • To perform the calculation in 5 minutes, a computer operating at 3.4 Tflops would be required

N-Body Problem

  • Predicting the motion of astronomical bodies in space requires calculating the gravitational forces between each body
  • For N bodies, there are N - 1 forces to calculate for each body, resulting in approximately N^2 calculations
  • Even with an efficient algorithm, the number of calculations is enormous, requiring significant time on a single-processor system
  • The N-body problem also appears in modeling chemical and biological systems at the molecular level

The Demand for Computational Speed

  • Traditional examples of applications requiring immense computational power include global weather forecasting and simulating large numbers of bodies
  • New applications, such as virtual reality, also require considerable computational speed
  • Whatever the current computational speed, there will always be applications that require more power

Parallel Computing

  • Using multiple processors within a single computer (multiprocessor) or multiple computers operating together on a single problem can increase computational speed
  • Writing programs for this form of computation is known as parallel programming
  • The approach should provide a significant increase in performance, with the ideal situation being p processors providing up to p times the computational speed of a single processor
  • However, problems often cannot be divided perfectly into independent parts, and interaction is necessary between parts for data transfer and synchronization of computations

Benefits of Parallel Computing

  • Allows for larger problems or more precise solutions to be solved in a reasonable amount of time
  • Enables tackling problems that require larger amounts of main memory
  • Allows for multiple instances of a program to be executed simultaneously with different input values
  • Used in Web servers to service requests from users, as well as in on-line banking and on-line retail

The Speedup Factor

  • Measures the relative performance of a multiprocessor compared to a single-processor system
  • Defined as the execution time using a single processor system divided by the execution time using a multiprocessor with p processors
  • The maximum speedup possible is usually p with p processors (linear speedup)
  • Superlinear speedup may be seen on occasion, but usually due to using a suboptimal sequential algorithm or an indeterminate nature of the algorithm

Amdahl's Law

  • Describes the maximum speedup possible with parallel computing
  • The fraction of the computation that cannot be divided into concurrent tasks (f) limits the speedup
  • The ideal situation would be for all available processors to operate simultaneously for the entire computation, but this is not always possible
  • The speedup factor is given by S(p) = [1 + (p - 1)f]^(-1)
  • Even with an infinite number of processors, the maximum speedup is limited to 1/f

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

dokumen.pub_parallel-programming-techniques-and-applications-using-networked-workstations-and-parallel-computers-2nd-ed-0131405632-9780131405639.pdf

Description

This quiz covers parallel programming techniques and applications using networked workstations and parallel computers, based on the 2nd edition of the book by Barry Wilkinson and Michael Allen. It explores the concepts and methods of parallel computing, its applications, and the use of networked workstations.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser