Multicore Processors: Architecture & Programming Projects
Multicore Processors: Architecture & Programming
Projects
The project part of the course
• 50% of the total grade
• groups of 1 to 4 students
– One submission per group
• Presentations in the last two lectures of
• You have 3 choices:
– pick one of the suggested projects
– suggest a modifications to a suggested project – suggest a different project
the course
Regarding the Final Report
Regarding Final Report: Abstract
• The first thing in your report, but the last thing to write.
• 1 paragraph summarizing your problem and why it is important.
• 1-2 lines hinting on your technique
• 1-2 lines summarizing your finding(s)
Regarding Final Report: Introduction
• Expand the abstract to include why the problem you are solving is important.
• Then, give a general idea about your way of approaching the problem.
Regarding Final Report: Literature Review
-
Feel free to organize this section in any way you want: – Include any subsections you think you need.
– Draw any Figures you like. -
But you need to discuss at least the following items:
– What did others do regarding the topic at hand? Note: the worst survey ever is when you say “x has done y; z has done k; ...”. You must put the work of others in taxonomy. That is, “The solution to this falls in x categories: .... . In the first category x has done ...”.
-
– What are the pros and cons of what they are doing?
-
– Why their work is not enough, and your proposed project is
-
needed?
– Important: Literature must not be about papers solving exactly your same problem. But can include papers about different problems but have similar challenges.
Regarding Final Report: Proposed Idea
• This is a major part of this report.
• Describe in great details the solution to
the problem at hand.
– For example, if you are parallelizing something, you must explain how you did that and justify your choices. If you are comparing things, you must specify what is the criteria of comparison is/are and why you picked them; and so on...
Regarding Final Report: Experimental Setup
• State:
– The simulator you used (if any) or the specs of
the machine you used
– The benchmarks (if any),
– etc ...
• How do you know you have written a good experimental setup? If another researcher reads this section, the researcher must be able to replicate your experiments without asking you any questions.
Regarding Final Report: Results and Analysis
• Formatting tip: using tables, bullets, figures, diagrams, ... are better than words in presenting results.
-
What is/are the measures of success in your work? That is, what do you need to measure and what are you expecting the results to be in order to say that you succeeded?
-
What are the experiments that you did in order to get the measurements you mentioned in the above bullet?
• Analysis:
– Bad: “As we can see x is increasing with y” You won’t
get any credits for that!
– Much better: “x increases with y because 1, 2, 3, .... And under the conditions .... x may not increase with y. We learn from that ....”
Regarding Final Report: Conclusions
• What are the most important findings of your project?
– A bullets list is the best here. • No more than three points.
Regarding Final Report: References
-
If you only mention the references I provided you, it means you did not do any extra work.
-
Websiteslikewikipedia,stackoverflow,etcare not references, don’t use them.
-
Don’t use urls unless there is no paper about the topic.
-
Example of reference format:
– J. Lee and H. Kim. Tap: A tlp-aware cache management policy for a cpu-gpu heterogeneous architecture. In High Performance Computer Architecture (HPCA), 2012 IEEE 18th International Symposium on, pages 1–12, 2012.
Suggested Projects
Check the page on the course website whose link is in the “Comments” column of Sep 26th lecture.
Project 1:
Parallel Computational Model
• Survey of parallel computational models currently available (e.g. PRAM, BSP, logP,...).
– Do not limit to the three models we discussed in class.
-
Show their strengths and weaknesses, with examples.
-
Propose your own (major part of the project)
– Must take memory access, communication, and computation into account.
• Prepare the following benchmarks in OpenMP:
– Twodifferentsortingalgorithms
– Twodifferentsearchalgorithms
– Two other applications of your choice.
-
Compare the expected performance of each application using your model and the other models.
-
Execute the applications, with different problem sizes, and see how does your model compare to others in predicting the performance of a parallel algorithm.
Project 2:
Pick an application to parallelize
(YOU must pick the application.)
-
Must demonstrate lessons beyond "I implemented X on the multicore using this library/language/thread model, and it runs faster than a sequential version".
-
Better compare with another parallel version in addition to the sequential version.
-
Must clearly show the challenges facing the parallelization of this application and how you overcame it.
These lessons may include:
-
Interesting generalized algorithmic or data structure contributions that can be applied to other applications (and these other applications should be made explicit)
-
Interesting optimization techniques that can be applied beyond the application in the paper
-
Interesting data management/representation techniques: how to best leverage the memory hierarchy, how to represent data in the most suitable way
-
Rigorous comparisons with existing implementations.
Project 3: Comparing OpenMP and Rust
-
Programmability (i.e. how easy it is to program with the language)
-
Scalability (handling large number of threads)
-
Runtime overhead of the language (measure how long it takes to create threads, terminate threads, synchronize, etc)
-
The amount of control given to the programmer (can the programmer decide which thread goes to which core, can the programmer decide which variables to be shared and which ones to be prviate, etc).
-
Any other factor you can think of.
-
You need to create several benchmarks to test the above.
-
Based on your analysis about the performance of each language, make a flowchart showing developers when to use each language.
Project 4: Concurrent Data Structure
• Pick a data structure: queue, tree, ...
-
Build a library for that data structure
that can be used by OpenMP.
-
Test your implementation for performance and scalability using a set of benchmarks that you create.
Project 5 – version a: Performance Prediction of Multithreaded Applications
• Input:
– Specs of a multithreaded program (What are
these specs is part of the project.)
– Specs of the machine that will be used to run program (What are they is part of the project.)
– Problem size
– Speedup on some machines
• Output: Expected speedup, on a different machine, relative to a one thread execution.
Project 5 – version b: Performance Prediction of Multithreaded Applications
• Input:
– Specs of a multithreaded program (What
are these specs is part of the project.)
– Specs of the machine that will be used to run program (What are they is part of the project.)
– Problem size
• Output: Expected speedup relative to a one thread execution.
Project 6:
Compare Coherence Protocols
• Exhaustive list of coherence protocols
• Implement them using simulator
• Discuss effect on parallel programs in terms of:
– Scalability
– Bandwidth requirement
Project 7:
Evaluation of Memory Allocators in OpenMP Programs
• Input: Several memory allocators implemented for multithreaded applications
• Output:
– comparison of the different ones in terms of: • Speed
• Scalability
• False sharing avoidance
• Low fragmentation
– Implement your own and compare to others
Have Fun!
