Software Lab: Parallel Graph Algorithms
We run through the main stages of a typical software development process inspired by practically relevant graph algorithms.
General Information
... on the administrative structure of the lab can be found here.
Topic
Parallel Graph Algorithms for OpenFOAM
User Requirements
Read in OpenFOAM mesh files (in ascii or binary format)
https://www.openfoam.com/documentation/user-guide/2-openfoam-cases/2-2-basic-inputoutput-file-format
We will need
constant/polyMesh/{points,faces,owner,neigbor}
Example meshes: squareBend_ascii squareBend_binary motorBike pipe
https://openfoamworkshop.org/validation-challenge/
On the mesh representation we can apply a variety of (parallel) graph algorithms:
- Reverse Cuthill–McKee Algorithm for bandwidth reduction
- Graph Partitioning for mesh decomposition (e.g. k-d clustering, Kernighan–Lin algorithm)
- Graph coloring (distance two)
Agenda
KW = Calendar week, specific date to be announced soon
Kickoff: 13:10.2023 14:00
Proposal: 27.10.2023 14:00
Requirements: 10.11.2023 14:00
Design: 24.11.2023 14:00
Implementation 12.01.2023
Final Presentation: 26.01.2023
PROPOSAL (10% of final grade)
The aim of the project proposal incl. its oral presentation is to get first and early feedback on the work plan.
- Use the LaTeX template for slides covering
- problem description and technical background
- Stay within the allocated time frame.
- All team members must participate equally.
REQUIREMENTS (10% of final grade)
A formal use case analysis is supposed to yield a list of functional and nonfunctional system requirements
- user requirements
- work plan including milestones and risk management. + proposal for infrastructure (language, libraries)
- Illustrate the static and dynamic perspectives (e.g, use case).
- Add explanatory annotation wherever appropriate.
- Use the LaTeX template for slides.
- Stay within the allocated time frame.
- All team members must participate equally.
DESIGN (10% of final grade)
The formal object-oriented software design should be suitable for seamless implementation using the programming language of your choice.
- Use UML to illustrate the static and dynamic perspectives (e.g, class and sequence diagrams).
- Add explanatory annotation wherever appropriate.
- Use the LaTeX template for slides.
- Stay within the allocated time frame.
- All team members must participate equally.
IMPLEMENTATION (10% of final grade)
The implementation should meet the user requirements. It should be accompanied by a test suite and meaningful source code documentation
- Discuss details of the implementation.
- Describe the software test strategy.
- Use the LaTeX template for slides.
- Stay within the allocated time frame.
- All team members must participate equally.
PUBLICATION (40% of final grade)
The final written report is the ultimate outcome of your work. It should be based on the LaTeX template provided and cover
- user requirements and technical details
- use cases and system requirements
- software design
- implementation and software tests
- project management
- user documentation including case studies
- developer documentation providing entry points into the source code
FINAL PRESENTATION (20% of final grade)
Sell your product including the software and the written report. Products are supposed to be used (bought) by other people. You need to generate interest in your work if you want it to become a best seller.
- Present a live demo of your software.
- Provide an overview of your written report's contents
- Give an outlook to potential follow-up projects.
- Use the provided LaTeX template for slides.
- Stay within the allocated time frame.
- All team members must participate equally.
Selected Ideas:
- Geometric split (either by sorting or binning of cell centerpoints)
- Clustering by e.g. k-means on centerpoints + (optional) minimizing shared faces (edges in cell adjacency graph) on processor boundary
- potentially use Keringham Lin as a refinement step
- (reverse) CutHill McKee using non-speculative parallel BFS