[SOLVED] 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 thatthey 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 aircrafts 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

*

Lets 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 b?a:b);
}

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 // A template function with T as the wildcard

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<<
< is defined for type T

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<<
< (a,b)<< < (c,d);

Consider whether cout<<
< void do_something (T a, U b) {
..
}

Or numerical parameters (and bool)

template 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 (3.14);
}

*

A Design challenge
Theres a lot more to do on templates, but lets 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 cant 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 didnt define copy

*

Template Functions
Basic tool for Generic Programming

We dont 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()

Theres tons more useful stuff on templates but lets 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
Lets 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<<
< do_filtering(7.);
}

Which do_filtering is called cant 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 cant actually build a generic filter only one of its concrete sub-classes; filters 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 functions code and executes it

return arguments are copied back, maybe involving temporary objects

the callers 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< do_filtering(7.);

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 thats 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;

Lets 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 a(1.,2.);// float precision complex number

complex b(1.,2.);// double precision complex number
}

NOTE WELL complex and complex are two different classes

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