SYLLABUS
In COMP 481 you will learn about parallel algorithms and how they are helping with the acceleration of computation. The emphasis will be shared and distributed memory models of parallel programing. The course will include theoretical and programming aspects in which students will be able to apply their knowledge.
You will also learn how to measure efficiency in parallel algorithms, as well as time complexity, speedups, the cost of communication, data and task parallelism, synchronization, and how to prepare your personal computers for parallel programing.
As an added bonus, you will be exposed to other computer science tools, such as Jupyter (for interactive computing), and the Linux operating system (using Unix commands, accessing a remote server, and so on).
Goals
At the conclusion of this course, you should have a basic understanding of parallel algorithms and their applications, particularly how to choose the appropriate parallel programming paradigm, as well as how to parallelize a given problem. This includes understanding the methodologies of the different programming models, the hardware in which your algorithm will run, and how to make sure your algorithm is efficient. You will also have some awareness of the current state of parallel algorithms and computations.
Quick Overview of COMP 485
| Prerequisites | COMP 210 (Data Structures). COMP 215 (Computer Algorithms). |
|---|---|
| Instructor |
Sandino Vargas-Pérez Dr. Vargas-Pérez • he, him, his pronouns Olds/Upton 208D (269) 337-7564 Office Hours:
|
| Reference Books |
Peter S. Pacheco, An Introduction to Parallel Programming, Elsevier, 2011. Readings will be assigned from this book.
Roman Trobec et al. Introduction to Parallel Computing: from Algorithms to Programming on State-of-the-Art Platforms, Springer, 2018.  Link to K Library You can find other references in the class resources page. |
Computing Resources and Software
To be able to successfully complete this course, you will be required to have the following tools:
- Programming Language: C/C++
- Development Environment: There are several C/C++ dedicated GUIs. I recommend Sublime Text 3 since you will be running your programs remotely. For your own personal purposes, you can install Eclipse CDT, CLion, or Visual Studio (VS) Code.
- Other: Miscellaneous resources will be provided to you during class in the form of handouts or links to electronic tools in the web, which will help you visualize, practice, and/or have fun while learning the concepts.
Topics to be Covered
The following are the topics we will be learning about and discussing during COMP 481 (and a tentative schedule for when each of them will be covered).
| Week 1 | Introduction to Parallel Computing and Algorithms Types of Parallelism What can Parallelism do? |
|---|---|
| Week 2 | Basic notions and concepts in Parallel Algorithms Computational complexity for parallel algorithms Laws and Theorems |
| Week 3 | Modelling parallel computations Interconnection Networks and Communication |
| Week 4 - 5 | Shared-memory programing with OpenMP Multi-threaded programs Parallelization of loops Task parallelization |
| Week 6 | Distributed-Memory programing with MPI Basic MPI operations Process-to-Process communication |
| Week 7 | Massively Parallel Graphic Processors NVidia and the CUDA API |
| Weeks 8 - 9 | Special Topics |
| Weeks 10 | Research project presentations |
Final Grade
Final grade will be based on:
- Participation 15%
- Quizzes 25%
- Assignments 30%
- Final Research Project 30%
- Bonus 5%
Community Guidelines
The following are a set of guidelines to create an inclusive and supportive learning environment in our class. It was adapted from the Center for Research on Learning and Teaching (CRLT) at the University of Michigan, by Dr. Josephine Mitchell.
Take care of each other
Get to know your classmates and call each other by your preferred names and pronouns.
Be an engaged scholar
Complete the pre-class readings and assignments, be on time to class, and engage with your classmates, professor, and the material in class.
Respectfully contribute to the learning environment
Treat each other with kindness, listen and develop awareness for ideas and opinions that are different from your own, be accountable to each other in discussions and group work, and foster an environment where everyone feels welcome.
Adopt an open mindset
Learning is a process! Strive for intellectual humility. Recognize that we will make mistakes as we learn. Think critically about how your perspectives have been shaped and be open to exploring new ideas and points of view.
Share responsibility for welcoming everyone to participate
If we tend to have a lot to say, make sure we leave space to hear and learn from others. If we tend to be quieter in group discussions, let us challenge ourselves to contribute so others can learn from us.
Challenge the idea, not the person
It is expected that different opinions and perspectives will be shared during discussions. We will be respectful of each other when debating an idea that may differ from our own. Personal attacks, divisive language, etc. will not be tolerated in our class.
Be accountable
We are in control of our learning and will get out of it what we put in. When working in groups, we will respect other group members and push ourselves to contribute to the group in ways that stretch our learning. We will maintain the highest standards of Academic Honesty and give credit to ideas that are not our own.
Attendance and Participation
Your regular attendance and fully engaged participation are expected in this course. Your grade will be partially based on in-class practices, discussions, and occasional quizzes, so your attendance will affect your grade. Active participation in the class means being on time, being prepared, listening to others, contributing ideas of your own, and asking questions as they come up.
Assignments and Class Evaluation
Assignments, announcements, class notes, and other material will be made available on the course web site and via MS TEAMS. We will use Kit to submit those assignments. All assigments, as well as anything that needs to be submitted to Kit, will be due by 11:59 p.m. of the date shown in the the schedule . You are responsible for checking these resources frequently.
Reading assignments and discussion questions may be assigned for each class. You are expected to come to class having completed the assignment and being prepared to discuss both the ideas from the reading and your solutions to any exercises. You should also bring questions you have from the reading to class. You are encouraged to work on the discussion questions and exercises in groups; just be sure that each group member understands each answer well enough to present it to the class.
There will be 4 to 5 assignments throughout the quarter, which may take a week or longer to complete. The time required to write a program and debug it is difficult to predict, but time-management skills are as critical in industry as they are in college. I will make programming assignments available online far enough in advance that you will have some flexibility in scheduling your work. Assignments must always be turned in on time unless you clear it with me in advance, but of course I'm flexible accepting late work or changing due dates. The class will also have 5 quizzes.
There will be a final research project paper that will be done in teams. Each of the team members will fill out a form evaluating their teammate. This evaluation will be used to decide if both members will receive the same final grade or if one (or both) members should receive less than the total mark. Ideally, both members of the team should work together and be in constant communication with each other in order to make great programming projects... sometimes it doesn't happen, hence the need for fairness in the project evaluations. If you prefer to work on your own, please let me know.
Collaboration and the Honor System
This course operates in accordance with the principles of the Kalamazoo College Honor System: responsibility for personal behavior, independent thought, respect for others, and environmental responsibility. In particular, academic integrity is a fundamental principle of scholarship. Representing someone else's work as your own, in any form, constitutes academic dishonesty. Unauthorized collaboration and receiving help from others outside the bounds permitted by the instructor are also violations of the College honor system. You are responsible for working within the permitted bounds and acknowledging any help from others or contributions from other sources.
For discussion questions feel free to work with others. As you work with others, keep in mind that the goal is not just getting a solution to the problem, but learning how to solve the problem yourself.
Quizzes should be entirely your own work.