DistributedComputingCpp.md

Textbooks / Resources:

• “Parallel and Distributed Computation: numerical methods”. by D. Bertsekas and J. Tsisiklis. (Chapter 1 is on network topology and schedules.)

• “Introduction to Parallel Computing: Design and analysis of Algorithms”. V. Kumar, A. Grama, A. Gupta, G. Karypis. (First four chapters.)

Dependency extraction:

• The origins of the model: A. J. Bernstein. Analysis of programs for parallel processing. IEEE Transactions on Electronic Computers, 15:757–762, Oct. 1966.
• Voevodin V., Antonov A., Voevodin V. (2018) What Do We Need to Know About Parallel Algorithms and Their Efficient Implementation?. In: Prasad S., Gupta A., Rosenberg A., Sussman A., Weems C. (eds) Topics in Parallel and Distributed Computing.
• Chapter 2 to 5.1 of Oliver Sinnen. Task Scheduling for Parallel Systems. John Wiley & Sons, Inc. 2007. Access it through the library: https://librarylink.uncc.edu/login?url=https://onlinelibrary.wiley.com/doi/book/10.1002/0470121173
• Chapter 1 and 7 of. H. Casanova, A. Legrand, Y. Robert. Parallel Algorithms, CRC Press. 2008
• Chapter 2 to 5.1 of Oliver Sinnen. Task Scheduling for Parallel Systems. John Wiley & Sons, Inc. 2007. Access it through the library: https://librarylink.uncc.edu/login?url=https://onlinelibrary.wiley.com/doi/book/10.1002/0470121173

Cilk on graphs metrics:

• The Cilkview Scalability Analyzer, SPAA 2010.http://web.mit.edu/willtor/www/res/cilkview-spaa-10.pdf. a paper describing parallel application as a DAG and metrics.

Conflict graph and coloring:

• Conflict graphs: http://math.cmu.edu/~bkell/21110-2010s/conflict-graphs.html A. H Gebremedhin, F. Manne, Alex Pothen. What Color Is Your Jacobian? Graph Coloring for Computing Derivatives. Siam Review 2005.
• M. Deveci, E. Boman, K. Devine, and S. Rajamanickam. Parallel Graph Coloring for Manycore Architectures. IPDPS

Scheduling:

• A taxonomy of scheduling problems: Srishti Srivastava and Ioana Banicescu. Scheduling in Parallel and Distributed Computing Systems. Chapter 11 of Prasad, Gupta, Rosenberg, Sussman, and Weems. Topics in Parallel and Distributed Computing: Enhancing the Undergraduate Curriculum: Performance, Concurrency, and Programming on Modern Platforms, Springer International Publishing, 2018. https://grid.cs.gsu.edu/~tcpp/curriculum/?q=system/files/Ch11_4.pdf
• Scheduling is NP-Hard: M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. 1979.
• LS for independent tasks: R. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal. 1966
• LPT and LS with precedence: R. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics. 1969.
• Chapter 1 and 7 of. H. Casanova, A. Legrand, Y. Robert. Parallel Algorithms, CRC Press. 2008