Microsoft Word – H63ESD Engineering Software_coursework_2016.docx
P Sewell Jan. 2017
H63ESD Engineering Software: Design and Implementation, COURSEWORK page 1 of 18
H63ESD Engineering Software: Design and Implementation:
COURSEWORK (100% of the Module Assessment)
Design and Structure of the Coursework.: The coursework has been structured to
both assess the Learning Objectives of the module and to help guide you in your studies.
I have split the work into a number of tasks with staged deadlines to help you manage
your overall workload for the year. I have been careful not to ask you for an excessive
volume of work as it is important that you have sufficient quality time for reflection on
the material. I hope the online voluntary quizzes will be helpful with this activity. I am
happy to receive opinions on workload and assessment issues as feedback from
previous students has constructively contributed to the fine-tuning of this assignment.
Coursework Deadlines and University Regulations …………………………………………. 2
Submission deadline Summary: ………………………………………………………………. 2
Tasks 1-3, Friday 31st March 2017 ………………………………………………………….. 2
Tasks 4-6, Friday 19th May 2017 ……………………………………………………………. 2
Submission format ……………………………………………………………………………………. 2
Required Platform for the Software …………………………………………………………….. 2
Course work style …………………………………………………………………………………….. 2
Your budget …………………………………………………………………………………………….. 3
Progress Reporting ……………………………………………………………………………………. 3
Friday 24th February: …………………………………………………………………………… 3
Friday 17th March:……………………………………………………………………………….. 3
Friday 7th April: …………………………………………………………………………………… 3
Plagiarism ……………………………………………………………………………………………….. 3
Coursework Assignment: Overview and Assessment Criteria …………………………….. 4
Scenario: (Your client’s field of business) ………………………………………………………… 5
Delaunay Triangulations ………………………………………………………………………………. 7
Numerical issues for Producing Delaunay Triangulations ………………………………… 8
Speed issues for Producing Delaunay Triangulations – Parallelisation? …………….. 8
Specific Coursework Tasks …………………………………………………………………………….. 9
Task 1: (15%) Code optimisation. Deadline 31st March 2017 ……………………………. 9
Task 2: (15%) Characterisation of the Jenna platform. Deadline 31st March 2017
…………………………………………………………………………………………………………………. 10
Task 3: (15%) An Interval Mathematics Component. Deadline 31st March 2017 .. 10
Task 4: (25%) Manipulation of Triangulated Meshes. Deadline 19th May 2017 …. 11
Task 5: (10%) Basic OpenMP Parallelisation. Deadline 19th May 2017 …………… 11
Task 6: (10%) Basic MPI Parallelisation. Deadline 19th May 2017 ………………….. 11
Progress Reporting and Time Management: (10%) ………………………………………… 12
Appendix #1: Linear Interpolation Over Individual Triangles ……………………….. 13
Appendix #2: The Circumcentre of Individual Triangles ……………………………….. 14
Appendix #3: File Formats ……………………………………………………………………………. 15
Appendix #4: Code for task#1 ………………………………………………………………………. 16
Appendix #5: Marking Scheme …………………………………………………………………….. 18
P Sewell Jan. 2017
H63ESD Engineering Software: Design and Implementation, COURSEWORK page 2 of 18
Coursework Deadlines and University Regulations
Submission deadline Summary:
Tasks 1-3, Friday 31st March 2017
Tasks 4-6, Friday 19th May 2017
Submission format
SUBMISSION VIA MOODLE – Zipped files containing all your work, programs and PDFs of
reports as detailed below.
The reports are not to contain general background material, just the required responses to the questions
and design tasks below.
Usual Faculty submission procedures and University rules regarding late submission apply.
Required Platform for the Software
All software MUST be in C++ and compile with g++ on the Jenna cluster and all required timings and memory
characterisations must be undertaken upon Jenna : this is part of the Design Specification.
You are permitted to use the STL, but no other 3rd party code or libraries (e.g. Boost) without prior
permission of P Sewell.
WARNING: failure to follow these requirements will cost you a notable amount of marks as I (the client) may
not be able to assess your work in proper comparison to that of other students and my own codes.
Course work style
Consider the coursework in the following manner. P Sewell wishes to place a contract to undertake a
major design and development project with a software developer. He is the client. In order to choose to
whom to award the work, he has produced a “test” that all hopeful developers must undertake in order to
demonstrate their skills. Therefore, as is not uncommon in such circumstances, the test may be:
1) Vague in places
2) Possibly open-ended – where to stop?
3) Lacking in some crucial details
You are expected to interact with your client – ask questions!
You are expected to make your own engineering judgements where the specification and/or the client
is unclear on, or else simply doesn’t explicitly mention, a particular aspect (e.g. expandability, robustness,
the use of a 3rd party library etc.).
For this reason, there are no overall page limits on the report – again, your engineering judgement on the
appropriate style of presentation given the context.
P Sewell Jan. 2017
H63ESD Engineering Software: Design and Implementation, COURSEWORK page 3 of 18
Your budget
A 10 credit module = 100 hours of student time. 22 hours of lectures and you will also have to undertake
general study of the module material: spend the budget wisely.
You will not be penalised for asking P Sewell questions or seeking any other form of help from him –
you are supposed/expected to!
Progress Reporting
As is the case for all real projects, the client (PS) requires to be able to monitor progress. For this reason,
you are required to submit a <1 page summary of your activities and/or project progress via Moodle on
the following dates. These are compulsory and are awarded a mark (see below). The intention of
these progress reports is partly to replicate a true industrial atmosphere, but primarily is to permit PS to
help you. These are not marked on technical content, but only from the point of view of project
management.
Friday 24th February:
PS would expect to hear about study of the lecture material and initial coursework progress
Friday 17th March:
PS would expect to hear about coursework tasks 1-3 and initial design thoughts for tasks 4-6
Friday 7th April:
PS would expect to hear about coursework tasks 4-6.
PS reserves the right to interview any student about their progress reports and to see demonstrations.
Plagiarism
Please refer to the University's rules on plagiarism and take them very seriously - The Faculty will
For this coursework, it is expected that students will talk to each other about the work and even jointly
investigate particular avenues of interest and exchange ideas - that's how engineers operate. However,
this is not a group project. Each student must design and implement their own work separately.
If in doubt, please ask PS
P Sewell Jan. 2017
H63ESD Engineering Software: Design and Implementation, COURSEWORK page 4 of 18
All Tasks Are Compulsory.
All tasks of the coursework, except task#1, are drawn from my real industrial experience working on the
same engineering scenario.
Coursework Assignment: Overview and Assessment Criteria
This assesses your knowledge and understanding of, and your ability to use, the techniques we have
studied on the smaller scale. There are a number of separate tasks each of which considers a particular
aspect of the material.
Marks will be allocated on the basis of:
1. Does the code compile properly without ignored warnings?
2. Does the code work properly, i.e. does it produce the correct behaviour?
3. Is the code robust?
4. Is the code efficient - speed/memory?
5. Is the code clearly understandable to our level of software engineer (by the end of this
module!): layout, structure, an appropriate level of documentation?
6. Has the code been designed with a view to future updates/modifications as well as to permit
recycling of its parts for other projects?
7. The technical correctness of the required explanations.
8. Demonstration of good engineering practice and judgement.
Credit will be given for correct and appropriate use of material that students discover themselves beyond
the lecture material - "impress the client".
The formal marking scheme that will be used is given in Appendix 5.
If in doubt on any aspect of the criteria used to assess your work for a particular task, please ask PS
The Scenario is described below. No expertise is expected in the area, but as software engineers we will
often have to understand the problem area before we can start our own work.
When you turn over the problem is going to look complicated!
That's the whole point! - Divide and conquer!
IF IN DOUBT - ASK THE CLIENT
P Sewell Jan. 2017
H63ESD Engineering Software: Design and Implementation, COURSEWORK page 5 of 18
Scenario: (Your client's field of business)
Many engineering disciplines use CAD/CAE
packages which require models of geometrical
structures.
Often, structures are modelled by a triangulated
approximation to their surfaces. Triangles offer
the ability to represent small and fine features
with different sized triangles.
Similarly, we might discretise a flat 2D problem
space in order to numerically solve some
equations representing a physical process of
interest - maybe current flow or temperature.
We might visualise this as shown here using a
colour map or as shown below using a "height"
surface.
In this work we are concerned with the second type of triangulation (also referred to as a mesh)
We can "triangulate" a particular problem with given fixed vertices in many different ways. However,
we will inevitably ask, or be asked: What is the "best quality" triangulation?
Note that a triangulation of given vertices is not unique: "any edge can be flipped".
Quasi-equilateral
triangles are
good
Sliver triangles
are bad
Not allowed
Same vertices, but different edges
to form different triangulations
The definition of a "good" mesh obviously depends upon its intended use. For example, people solving
a set of engineering equations are likely to prioritise different criteria than the computer games/animation
community.
A 1D Interpolation Error Measure: One interesting (meaningful?) measure of triangulation quality is
to consider the interpolation of a function over the mesh - how close is the interpolated sampled function
to the true continuous one?
Above is shown a 1D "mesh" example: How close are the Red and Green approximations to the true
black curve? We can consider the "area" of the solid green and red regions as error measures.
P Sewell Jan. 2017
H63ESD Engineering Software: Design and Implementation, COURSEWORK page 6 of 18
A 2D Interpolation Error Measure:
This idea also extends to 2D meshes - albeit it is harder to draw!
The "height" represents the
true function value f(x,y)
The "x-y" plane
Exact function values
given at the vertices
The sample points are the vertices of
the triangulation
Over a 2D x-y domain we are given a smooth continuous function f(x,y) that we need to sample it in an
analogous manner to the 1D case above.
We select some discrete sample points {xi, yi} for 0
struct timeval start_time,end_time;
gettimeofday(&start_time,NULL);
// Your code to time
gettimeofday(&end_time,NULL);
cout<<"\n\ngettimeofday wall time="<< end_time.tv_sec - start_time.tv_sec+(end_time.tv_usec-start_time.tv_usec)/1e6; With offset=0, investigate and plot the timings for different n. Briefly explain what you see. Does doubling n mean doubling the run time etc? Based upon the previous results, select a few "interesting" values of n and repeat for different offset values. Please provide no more than 1 page (excluding plots) of written explanation of what you see Required results: Submit both your test codes and the results obtained and the discussions in the report. Task 3: (15%) An Interval Mathematics Component. Deadline 31st March 2017 Produce an interval maths "component" to be used in the above scenario: suitable templating is required. Consider that this component may be recycled for future projects as well. Provide a suitable "test" main program to demonstrate the functionality of your component. Required results: Submit your component code and the test main. A very brief report is required that states any design decisions made and justification that the code functions correctly. P Sewell Jan. 2017 H63ESD Engineering Software: Design and Implementation, COURSEWORK page 11 of 18 Task 4: (25%) Manipulation of Triangulated Meshes. Deadline 19th May 2017 Assume that you are provided with a triangulation stored in files as described in Appendix 3: Design and implement a data structure and an interface for a C++ class to encapsulate the triangulation. Use of the STL is likely to be appropriate. The interface must permit the following: a) File streaming I/O b) Queries of the form: given a point x,y at run time which triangle contains it c) Queries of the form: given a function (known at compile time) f(x,y), return the integral of f(x,y) over the domain of the triangulation. For this we will approximate the integration in two possible ways - see Appendix #1 d) A check whether a triangulated mesh provided by the user is Delaunay Required results: Your codes and a brief section in the report to convince the client that it works correctly (evidence please). Task 5: (10%) Basic OpenMP Parallelisation. Deadline 19th May 2017 Parallelise task 4 using OpenMP: credit will be given for the degree of speedup achieved. Required results: Your codes and a brief section in the report to convince the client that it still works correctly and the speedup obtained. Task 6: (10%) Basic MPI Parallelisation. Deadline 19th May 2017 Design, implement and run test codes to assess the basic performance of the Jenna cluster when running simple MPI codes. Explore issues such as scaling with respect to number of processes launched, the load balancing used, how the performance changes if processes are launched on different cores of multi-core CPUS in comparison with each process being on a separate CPU etc. Infiniband versus ethernet, maybe even the MPI configuration settings. What sort of tests? The scope of MPI coverage in this module is simple point to point data transfer and we have a finite budget (i.e. your time!) : keep talking to the client! This is assessing your ability to "design a problem" rather than just "solving a problem". Required results: Up to you - consider the " Course work style" comment above. P Sewell Jan. 2017 H63ESD Engineering Software: Design and Implementation, COURSEWORK page 12 of 18 Progress Reporting and Time Management: (10%) The progress reports described earlier are a compulsory part of the coursework. A mark of 10% will be awarded for these in total and is based upon whether the client felt convinced at the time that the work was proceeding in a suitable manner and is likely to be successfully delivered at the end of the project. These are not marked on technical content, but only from the point of view of project management. Indeed, the client will be quite happy if the progress reports contain more questions than answers! Don't forget that in the real world your client is likely to have a boss to report to as well and he/she will need evidence from you to convince his/her management that they are monitoring the project correctly and thus doing their job properly as well! IF IN DOUBT ABOUT ANY OF THE TASKS OR THE ASSEMENT CRITERIA - ASK ME! P Sewell Jan. 2017 H63ESD Engineering Software: Design and Implementation, COURSEWORK page 13 of 18 Appendix #1: Linear Interpolation Over Individual Triangles The "x-y" plane The "height" represents the function value f(x,y) Exact function values given at the vertices Between vertices, linear interpolation An arc drawn on the true function surface f(x,y) true f(x,y) value Linearly Interpolated value If we have a triangulation and we know the true values of the function f(x,y) at its vertices, how do we interpolate to estimate the function at any point P in the x, y plane? Well we consult a friendly mathematician who provides the following: The "x-y" plane The "height" represents the function value f(x,y) Exact function values given at the vertices Between vertices, linear interpolation A1 V0 V1 V2 P(x,y) Triangle V0-V1-V2 has area A= A0+A1+A2 A2 A0 F2 F1 F0 FP true f(x,y) value Linearly Interpolated value If the values of the function f(x,y) are known to be F0, F1 and F2 at the vertices V0 , V1 and V2 then the linearly interpolated value at any point P(x,y) inside the triangle is, A FyxAFyxAFyxA yxFP 221100 ),(),(),(),( �� where the Ai are the areas of the sub-triangles shown in the figure - they are functions of where P is - hence x,y. A is the total area of the triangle. For interest the quantities ¿ ¾ ½ ¯ ® A yxA A yxA A yxA ),( , ),( , ),( 210 are called the area, or barycentric coordinates of the point P with respect to the triangle. These have many convenient properties. How to numerical approximate the integral of the function with respect to x and y ? Again the same friendly mathematician provides: There are two ways we could evaluate an approximation to ),( yxfdydx T ³³ where T is a triangle: 1) Constant value approximation ),(),( yTxTT T OOfAyxfdydx |³³ i.e. evaluate the function at the circumcentre, O, of each triangle and weight by the triangle's area. P Sewell Jan. 2017 H63ESD Engineering Software: Design and Implementation, COURSEWORK page 14 of 18 2) Linear interpolation approximation using the above and the useful, but non-obvious, fact that: 3/),( AyxAdydx i area Triangle ³³ Not sure about this - consult your client! Appendix #2: The Circumcentre of Individual Triangles R O V1 V0 V2 It can be shown that if vertex Vi has coordinates Xi , Yi that the coordinates of the circumcentre Ox , Oy and the circumradius R are found from solutions of, ¸̧ ¸ ¸ ¹ · ¨̈ ¨ ¨ © § ��¸ ¸ ¸ ¹ · ¨ ¨ ¨ © § ¸̧ ¸ ¸ ¹ · ¨̈ ¨ ¨ © § � � � 222 22 11 00 2 2 2 2 2 1 2 1 2 0 2 0 2 2 1 1 1 yx y x OOR O O YX YX YX YX YX YX (See if you can prove this - just for fun, no marks.) This order 3 matrix equation can be solved quite effectively using basic algebraic techniques. You are welcome to discuss and seek further information/detail/clarification regarding any aspect of the "geometry" or "algebra" from P Sewell