Cornell Theory Center

Presentation:
Tariff Case Study Part 2, MPI Implementation

10/98

This is the presentation layer of a two-part module. For an explanation of the layers and how to navigate within and between them, return to the top page of this module.

Introduction

Parallel Issues

• 2.1 Problem Partition
• 2.2 Data Partition
• 2.3 Communication
• 2.4 Load Balance
• 2.5 Performance

MPI Implementation

• 3.1 MPI Calls Needed
• 3.2 Changing the Serial Code
• 3.3 Parallel I/O
• 3.4 Performance Analysis
• 3.5 Conclusions

References Lab Exercise Evaluation



---

1. Introduction

• Anna Nagurney's Tariff Program
• Parallel issues
  • Problem partition
  • Data partition
  • Load balancing
  • Communication
  • Parallel performance
• A simple parallel implementation



---

2. Parallel Issues

2.1 Problem Partition
• Functional vs Data partition
• Tariff model characteristics
  • Few, short computations
  • Iterate over all data elements
• Use data for partitioning

---

2.2 Data Partition

• Partition data column-wise
  • Better memory access performance
  • Less programmer effort
  • No communication effects for this problem
    • Indirect addressing via ind1 & ind2
    • Entire demand & supply array needed
• Partition only computed portions of data
Figure 2. Data partition



---

2.3 Communication

• Calculations split among processors
  • Supply
  • Demand
  • Apatho (Q)
  • Convergence test
• Complete data needed by each processor
  • Supply
  • Demand
  • Convergence test
• Use collective "sum & broadcast" message
  • MPI_Allreduce

---

2.4 Load Balance

• Communication load: is uniform here
  • Message Size
  • Number of messages sent/received
  • Type of communication call
• Computation load: can be uniform here
  • Amount of data - key for this problem
  • Number of computations
  • Types of computations

---

2.4.1 Balancing the Data Partition

Figure 2. Graphical View of the Data Partition

---

2.4.1 Balancing the Data Partition

Figure 3. Pseudo-code for the Data Partition

!         number of columns per processor chunk = ndemm / total_processors !         number of columns "left over" extra = mod( ndemm, total_processors ) !         skip past data assigned to lower !         ranked processors, including "extra" lower = chunk * rank + 1 + min( extra, rank ) !         "extra" processors get 1 more column if( rank .lt. extra ) then     upper = lower + chunk else     upper = lower + chunk - 1 endif

---

2.5 Performance

• Scalability
  • More processors
  • More data
• speedup = sequential run time / parallel run time
• efficiency = speedup / number of processors



---

3. Implementation

3.1 MPI Calls Needed

• Initialization routines
  • MPI_Init
  • MPI_Comm_Size
  • MPI_Comm_Rank
• Communication routine
  • MPI_Allreduce
• Closing routine
  • MPI_Finalize

---

3.2 Changes to the Program

• new declarations
• initialize MPI & communicator
• data partitioning code
• Change demand index limits

  Initialization

  approximation phase, demp calculation,

  approximation phase, apath calculation,

  adaptation phase, demp calculation,

  adaptation phase, apatho calculation,

  non-zero shipment path final count

• Reset entire demand array

  Initialization

  Approximation phase

  Adaptation phase

• Add message passing for Supply & Demand

  Approximation phase

  Adaptation phase

• Add message passing for the convergence test result
• Add message passing for shipment path final count

---

3.3 Parallel I/O

• Input has not been changed
• AFS can't handle significant parallel I/O
• Use mcp to copy data to each processor
  • mcp man page
  • Handling I/O for Parallel Jobs

---

3.4 Performance

• Basic measure: Wallclock times
• Runs on 1 to 8 processors per dataset
• Three datasets:
  • 100 supply and 100 demand markets
  • 300 supply and 300 demand markets
  • 500 supply and 500 demand markets
• Runs must be made in batch mode

---

Figure 4. Wallclock Time in Seconds


Number of Processors

---

Speedup:

Figure 5. Speedup over Serial Program


Number of Processors

---

Efficiency:

Figure 5. Efficiency of Processor Use


Number of Processors

---

3.5 Conclusions

• Simple, quick conversion
• Gets "right" answers
• Scalable for large data sets
• Good efficiency for 4 or 5 processors



---

References

Franke, H., Wu, C.E., Riviere, M., Pattnaik, P. and Snir, M. (1995) MPI Programming Environment for IBM SP1/SP2. Proceedings of ICDCS 95, Vancouver, 1995. Available in postscript, at http://www.tc.cornell.edu/UserDoc/Software/PTools/mpi

Gropp, W., Lusk, E. and Skjellum, A. (1994) Using MPI. Portable Parallel Programming with the Message-Passing Interface. The MIT Press. Cambridge, Massachusetts.

Message Passing Interface Forum (1995) MPI: A Message Passing Interface Standard. June 12, 1995. Available in postscript at http://www.epm.ornl.gov/~walker/mpi

---

Tariff Case Study Part 2: MPI Version Lab

Please complete this short evaluation form. Thank you!

---





URL http://www.tc.cornell.edu/Edu/Talks/Tariff.Case.Study/Part2/less.html