程序代写代做代考 c++ flex Fortran algorithm case study chain Excel cache c/c++ data structure compiler H62SED: Software Engineering Design
H62SED: Software Engineering Design
*
H63ESD:Software Design and Implementation
10 Credits
P Sewell
7th Floor Tower Building
*
Introduction to the Module
This is not a level 1 beginners course
This is not a level 2 intermediate course
This is a level 3 advanced course
Mandatory Prerequisites
Programming in C – equivalent to H61ICP
Working knowledge of object oriented programming and its implementation in C++ – equivalent to H62SED
See online “self-assessments”
Without these you will seriously struggle
If in doubt please speak to me IMMEDIATELY
*
Introduction to the Module
Assessment: 100% course work: see handout for details of work and required report
50% for a number of structured exercises
50% for a design and implementation project
Submission deadline: Friday 17th May 2013
Usual Faculty submission procedures and University rules regarding late submission apply
Lectures: 2 hours per week: Thursdays 2-4pm
Weeks: Monday 28 January 2013 – Friday 22 March 2013 (lectures 1-8)
Weeks: Monday 22 April 2013 – 9 May 2013 (lectures 9-11)
(General exam period starts: Monday 20 May 2013)
*
Introduction to the Module
What and Why?
Large scale Computing: core to much technology
Computer platforms have evolved – multicore, GPU, cloud …
Issues of efficiency, complexity, robustness, maintenance – cost!
Particular Subjects
Parallel computing
Generic programming
Advanced object oriented programming
Design patterns
Data structures
Optimisations – speed/memory
*
Introduction to the Module
Style: it will be challenging, but if you get stuck/confused – talk to me
My preferred approach here: I want to help you gain both knowledge and hands-on experience of the real world of a computational engineer – not to “teach” a succession of artificially packaged subjects;
We need to balance depth and breadth:
I want to go deep enough into selected areas so that you appreciate their value and the major issues involved,
but I also want to cover a sufficient variety of topics that arise in practice and appreciate that they are often “coupled”
So, the lectures will contain a lot of material:
But, no exam – so no memorisation
However you are expected to study between lectures (I really mean it – and will assume you are doing so)
The 2 hours per week should be proper two-way conversations: ask questions, argue with me, ideally find out additional information and contribute it to the mix
*
Introduction to the Module
My availability
Every week I will leave a reasonable amount of time to discuss issues with individual students at the end of the lecture
Email me to make individual appointments
Dynamic feedback
There are range of topics – see previous comment on “balance”
There are range of ways to present,
“lectures on new material”
“Small scale illustrative examples”
“Larger scale case studies”
So as we go along, feel free to let me know if you want to change the balance/presentation or find something particularly interesting/boring!
*
Introduction to the Module
Online Support: Moodle
Lecture material
Coursework material – including info re the “Jenna” cluster
Self study material
Example quizes/sheets
Book list
Forums
For coursework
and your contributions to the module
*
Introduction to the Module
Books/software/facilities: On Moodle, there is a full reference list, but the key references are
General C/C++/STL reference
http://www.cplusplus.com/reference/ – bookmark it!
http://www.parashift.com/c++-faq/index.html
Parallel Programming in OpenMP and MPI
https://computing.llnl.gov/?set=training&page=index#training_materials – bookmark it
Advanced C++
Effective C++, 3rd Edition, 2005 and More Effective C++, 1996, Scott Meyers
http://www.aristeia.com/books.html
Standard Template Library, STL
Effective STL, 2001, Scott Meyers – see http://www.aristeia.com/books.html
Generic Programing and design patterns
Modern C++ Design: Generic Programming and Design Patterns Applied, Andrei Alexandrescu
Design patterns : elements of reusable object-oriented software, Gamma etc
Please contribute via the Student posted references forum on Moodle
*
Introduction to the Module
I am bound to use some C features you may not be familiar with – STOP ME AND ASK!!!!
Please report typos
CODE EXAMPLES – SKIP CONSTRUCTORS ETC ETC
*
A Case Study
I want to use this case study as a “reason” why we ought to consider the material covered in this module: we will consider the issues – not actually produce a working code
Modern aircraft are made of Carbon Fibre Composites, CFCs, rather than aluminimum
Lightning strike studies require computer simulations of how currents and electromagnetic fields penetrate the aircraft’s skin and structures
*
A Case Study
As part of a larger simulation package the following software requirement was identified.
The (thin) skin of the aircraft is triangulated – possibly different on both sides
Each triangular patch on one side is connected by a digital filter that models the penetration of fields through the skin, to a (number of) patches on the other side
The filter has a number of parameters and degrees of freedom
*
A Case Study
So a simplistic diagram of the algorithm is;
Each filter is bidirectional, ie each end has an input and an output
The next output is some combination of the current and previous inputs and outputs (for example an IIR or FIR structure)
*
A Case Study
Some starting issues:
1) A LOT of computation – many patches – millions, 100s of millions!
2) The filters are really vaguely specified – deliberately, we are researching the best choices so need the flexibility
3) Trivial point: double precision or float – depends
4) How do we “store” the patches – indexing? E.g. patch 1 couples to patch 23012
*
A Case Study
Some Object Oriented thinking:
What are the objects
Patches
Filters
We identify the basic member variables and functions as in year 2 right
How about the vagueness?
Inheritance – virtual functions – are we masters of these yet?
A subtely: when do have the vagueness at compile time or run time – does it matter?
Digital Filter
*
Let’s take a huge leap forward to something like
class patch;
class filter;
main(){
int no_patches(? from where);
int no_filters(? from where);
patch* patches=new patch[no_patches];
filter* filters=new filter[no_filters];
“read the setup data” // some files of patches and filters exist
int no_time_steps(? from where);
for(int i=0;i
}
int max(int a,int b) {
return(a>b?a:b);
}
float max(float a,float b) {
return(a>b?a:b);
}
Would be nice to provide just one generic version and have the compiler generate any particular versions it needs
“Inline conditional statement”
condition?result_if_true:result_if_false
*
A Design challenge
Template functions
template
T max(T a,T b) { // T is the “wildcard” type to be used for both
// arguments and return in this example
return(a>b?a:b);
}
main() {
int a(1),b(2);
float c(2.1),d(-7.1);
cout<<“
”<
template
T max(T a,T b) {
return(a>b?a:b); // will fail to compile if operator> not defined for type T
}
Warning: compiler messages regarding templates can be very very convoluted
Not all compilers are fully up to speed with templates as defined by ANSI
*
A Design challenge
Basically, compilers process templates by simple pattern recognition; if it recognises the particular type to be used for T or can deduce what T is, UNAMBIGUOUSLY, then it will proceed
Note that in the above example
main() {
int a(1),b(2);
float c(2.1),d(-7.1);
cout<<“
”<
Consider whether cout<<“
”<
……..
}
Or numerical parameters (and bool)
template
void do_something_else (T a) { void do_something_further (T a) {
T array[n]; if(flag) { // decision at compile time
…..… …..…
}
Note that types are resolved at compile time – so here n is used for static not dynamic memory allocation. n is NOT A VARIABLE, it is TEMPLATE PARAMETER
main(){
do_something_else
}
*
A Design challenge
There’s a lot more to do on templates, but let’s reconsider our integration design example
template
T simpsons_rule(T (*fptr)(T, … parameters??) , T a, T b,… parameters?? );
Simpsons_rule returns a T after integrating a function that accepts a T between limits given as Ts
We have solved the float/double problem now but have still used function pointers
How about ALSO templating the function itself – the argument will be “something” that acts like a function. How about the declaration
template
T simpsons_rule(U u, T a, T b); // U is the type of a “function like thing” to be integrated
Surely can’t be this easy or vague?
float simpsons_rule(float (*fptr)(float,float*), float a, float b, float* array_of_parameters);
*
A Design challenge
What would the function definition look like
template
T crude_integration(U u, T a, T b){
return(0.5*(u(a)+u(b)) );
}
When the compiler sees U u it recognises that u is an instance of the Type U
What does u(a) mean – u is an object surely ?
When it sees u(a) it actually recognises this as a shorthand for
u.operator()(a);
Just like u=v is shorthand for
u.operator=(v);
Recall, operators are standardised interfaces that we can overload (redefine) for any of our own objects (i.e. classes) and often have a shorthand calling form
e.g. operator+ etc
With the usual caveats about wikepedia a convenient list is at
http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B
*
A Design challenge
The prototype interface for the so called function operator is
any return type you wish operator() (any number/types of arguments you wish);
Example:
class myobject {
public:
usual constructors etc
void operator()();
float operator()(double a,double b);
};
main {
my_object A;
float c=A(1.0,2.0);
A();
}
Recall:Polymorphism!
Multiple versions of the same
function OK as long as compiler
can identify by the arguments
which one it is intended to call
*
A Design challenge
The solution
//——————————————————————————————————–
template
T crude_integration(U u, T a, T b){
return(0.5*(u(a)+u(b)) );
}
//——————————————————————————————————–
class my_object {
public:
etc
float operator()(float x);
};
//——————————————————————————————————–
main(){
my_object A;
float integral=crude_integration(A,0,1);
}
//——————————————————————————————————–
We can now integrate any “function” packaged as an object
*
A Design challenge
And it gets better – remember that parameter passing problem – no more!
//——————————————————————————————————–
class power_functioner {
public:
power_functioner (const int _n):n(_n){}
etc
float operator()(float x);
private:
const int n;
};
//——————————————————————————————————–
main(){
power_functioner A(7); // Make an object
float integral=crude_integration(A,0,1); // Compiler should deduce that U= power_functioner and T=float
}
//——————————————————————————————————–
Elegant or what ?
Function and parameter together
in one object
*
A Design challenge
Be careful though
//——————————————————————————————————–
main(){
power_functioner A(7);
float integral=crude_integration(A,0,1);
}
//——————————————————————————————————–
How about this?
//——————————————————————————————————–
main(){
float integral=crude_integration(power_functioner(7),0,1);
}
//——————————————————————————————————–
The object is created directly as an argument to the integrator – better efficiency and cleaner – but consider if the object a constant instance?
Object copied – we didn’t define copy
*
Template Functions
Basic tool for Generic Programming
We don’t write code, we write templates, “code patterns”, and the compiler does the code production
Think of the flexibility and scope for expansion this gives us, not to mention the time saved by not having to cut, paste and substitute – and then debug multiple versions of the same basic piece of code
We have discovered FUNCTORS
Functors are objects that behave as functions – many good properties
Usually relies on overloading operator()
There’s tons more useful stuff on templates but let’s keep an eye on our first case study and see what we may have gained
*
A Case Study
From slide 11: Some starting issues:
1) A LOT of computation – many patches – millions, 100s of millions!
2) The filters are really vaguely specified – deliberately, we are researching the best choices so need the flexibility ✓SHOULD HELP
3) Trivial point: double precision or float – depends ✓OBVIOUSLY HELPS
4) How do we “store” the patches – indexing? E.g. patch 1 couples to patch 23012
From slide 12: Some Object Oriented thinking:
What are the objects ✓SHOULD HELP
Patches,Filters, We identify the basic member variables and functions as in year 2 right
How about the vagueness? ✓SHOULD HELP
Inheritance – virtual functions – are we masters of these yet?
A subtely: when do have the vagueness at compile time or run time – does it matter?
OK, seems relevant, but any other advantages – boxed points?
*
A Case Study
Inheritance – virtual functions versus templates?
So we want to have flexibility in the filters
We could examine the inheritance route:
class filter {
public:
virtual float do_filtering(float ip);
};
class FIR:public filter {
public:
virtual float do_filtering(float ip);
};
class IIR:public filter {
public:
virtual float do_filtering(float ip);
};
The base class filter defines the interface for
the filtering function
each particular type of filter redefines it
in its own way
*
A Case Study
Let’s play some thought games
main() {
filter f; // ???????????? should we allow this to be possible: NO not sensible!
IIR(some constructor parameters) a; // An actual “buildable” filter
FIR(some constructor parameters) b; // An actual “buildable” filter
cout<<“
”<
}
Which do_filtering is called can’t be known at compile time in general so the decision is left to run time – bad?
*
A Case Study
Issue 1: filter f; // should we allow this to be possible: NO not sensible!
The base class is suppose to represent the abstract concept of a filter, you can’t actually “build” a generic filter only one of its concrete sub-classes; filter’s only purpose is to act as a base class from which realisable filters are derived.
So to keep ourselves honest (and to get the compiler to check for this potential source of error) we will introduce the concept of an Abstract class
class filter { // An abstract class
public:
virtual float do_filtering(float ip)=0; // pure virtual function, hence
};
class FIR:public filter {
public:
virtual float do_filtering(float ip); // This will be defined somewhere
};
The =0 denotes that filter::do_filtering is just an interface that derived classes must redefine: such a function is called a pure virtual function and it is never defined for the base class filter.
Any class containing at least one pure virtual function is an Abstract Class – no instances of it can be constructed – compiler policed
Remember good practice, the code should reflect as much as possible our “understanding/view” of the scenario
*
A Case Study
Issue 2: for(int i=0;i<10;++i) outputs[i]=patch_filters[i]->do_filtering(7.);
This worries me!
Let us presume that the actual machine code to do the different flavours of do_filtering exist
in memory somewhere
At compile we CANNOT PREDICT where the “instruction flow” will jump to for each i – so what? – this seriously impacts on speed
First, recognise that when we call a function:
Any local variables in the calling function are pushed onto the stack
Arguments are copied, maybe involving temporary objects
the code jumps to the function’s code and executes it
return arguments are copied back, maybe involving temporary objects
the caller’s local variables are popped from the stack
A lot of “time” is consumed in this “overhead” – especially if the function is fairly trivial to execute such as
float get_crude_pi(){return(3.14):}
But you say (I hope), you have forgotten about Inlining
*
A Case Study
Inlining
float get_crude_pi(){return(3.14):}
The machine code for small functions may be directly embedded in the calling code
main {
cout<
Does it know for certain at compile time here? NO
So inlining is thwarted – lots (I mean really lots) of repeated jumps to our filters could totally kill the run time.
So am I saying the inheritance/virtual functions are bad – no at all – just be aware of their overhead
Actually, each instance of a filter must be “carry with it” – which consumes memory as well, a way of determining its particular type at run time and which version of do_filtering it uses.
Essentially, each instance of a concrete filter must “look up in a table” where to jump to for each of its virtual functions – that’s yet another overhead on top of the general jump to function overhead.
Key point: most speed optimisations require predictability – not so here
*
A Case Study
Inheritance – virtual functions versus templates?
All the “vagueness” with templates is resolved at compile time: code is predictable, but rigid
All the “vagueness” with inheritance is resolved at run time: code is less predictable, but more flexible
We obviously want to exploit the benefits of each together
Just for completeness, let us consider inlining with templates
*
A Case Study
From slide 29
main(){
power_functioner A(7);
float integral=crude_integration(A,1,0);
// Or
float integral=crude_integration(power_functioner(7),1,0);
}
I think inlining will work a treat here because …
template
T crude_integration(U u, T a, T b){
return(0.5*(u(a)+u(b)) );
}
class power_functioner {
public:
power_functioner (const int _n):n(_n){}
etc
float operator()(float x){return(pow(x,n);}
private:
const int n;
};
*
A Case Study
Choosing
float integral=crude_integration(power_functioner(7),1,0);
The compiler probably never actually bothers to construct an instance of power_functioner !
Chances are the machine code generated will be as if we had typed
main(){
const int n(7);
const double a(0),b(1); // use of const means that 0 and 1 directly embedded in the code
float integral=0.5*(pow(a,n)+pow(b,n))
}
So we have all the attractions of templates but no speed penalty over explicit typing the “fastest” implementation
template
T crude_integration(U u, T a, T b){
return(0.5*(u(a)+u(b)) );
}
class power_functioner {
public:
power_functioner (const int _n):n(_n){}
etc
float operator()(float x){return(pow(x,n);}
private:
const int n;
};
*
A Design challenge
Templates are really good at giving us compile time flexibility and by exploiting inlining we avoid “jump” overheads
Remember templates are patterns for building particular instances;
Let’s consider how flexible our integration template really is;
template
T crude_integration(U u, T a, T b){
return(0.5*(u(a)+u(b)));
}
What if I want to integrate f(x)+g(x) ?
template
T crude_integration(U u, V v, T a, T b){
return(0.5*(u(a)+v(a)+u(b)+v(b)));
}
OK, but now (f(x)+g(x))*h(x)? – we are back to that “cut and past scenario”
*
A Design challenge
What would be good is to define a functor that is a sum of two other functors and pass that to the integrator
Now we need template classes
So far we have templated functions, but we can also template a whole class, e.g.
//——————————————————————————————————–
template
class complex {
public:
complex(T _r=0, T _i=0):r(_r),i(_i){}
etc
private:
T r;
T i;
};
//——————————————————————————————————–
main {
complex
complex
}
NOTE WELL complex
We have provided a pattern for building object classes!
*
What would be good is to define a functor that is a sum of two other functors and pass that to the integrator
//—————————————————-
template
class summer {
public:
summer(X _x, Y _y):y(_y),x(_x){}
T operator()(T t){return(X(t)+Y(t));}
private:
X x;
Y y;
};
//—————————————————–
class F; // a functor class
class G; // a functor class
main {
F f;
G g;
summer sum_f_g(f,g); “sum of an f instance and a g instance” object
float result=crude_integration(sum_f_g,1,0);
}
A Design challenge
Or obviously nicer would be
main {
F f;
G g;
float result= crude_integration(summer(f,g),1,0);
}
*
Think about the inlining going on here, I doubt a “summer” is ever built just the code for its operator()(T t) is generated. So in effect the machine code is as if we had typed
float result=0.5*(f(0)+g(0)+f(1)+g(1)));
If we now also define
template
class multiplier {
public:
multiplier(X _x, Y _y):y(_y),x(_x){}
T operator()(T t){return(X(t)*Y(t));}
private:
X x;
Y y;
};
We have huge flexibility by recursively embedding these
crude_integration(summer(f,summer(g,h)),1,0); // f+g+h
crude_integration(summer(f,multipler(g,h)),1,0); // f+g*h
crude_integration(summer(f,multipler(g,summer(h+f))),1,0); // f+g*(h+f))
All benefiting from the speed wonders of inlining – no jumps we hope
A Design challenge
*
Our practice to date is to place declarations in header files and definitions in .cpp files.
However templates must be fully available in the header file as must be inlined functions – think about why
inline and Templates in headers
class tpena
