PERFORMANCE
PROGRAMMING
Introduction to Performance Programming
Copyright By PowCoder代写 加微信 powcoder
• This course aims to teach:
• Overview of performance programming • Methodology, the optimisation cycle.
• Designing for performance
• Encapsulation as an aid to performance tuning.
• Tools for performance programming • Profilers and code instrumentation.
• Compilers and compiler optimisation.
• Memory hierarchies, Memory structures and associated
optimisations.
• Performance tuning for shared memory.
• Floating point performance • Pipelines,SIMD, vectorisation.
• Lectures and practical exercises • Assessed through coursework
• Code optimisation project
• Twoparts,1⁄4and3⁄4
• More details in a couple of weeks
• Why do we optimise
• What is performance optimisation • When do we optimise
• The optimisation cycle
• Trends in computer architecture
• Types of optimisation
• Large computer simulations are becoming common in many scientific disciplines.
• These often take a significant amount of time to run.
• Sometimes they take too long.
• There are three things that can be done
• Change the science (compromise the research)
• Change the computer (spend more money)
• Change the program (this is performance optimisation)
• There are usually many different ways you can write a program and still obtain the correct results.
• Some run faster than others.
• Interactions with the computer hardware. • Interactions with other software.
• Performance optimisation is the process of making an existing working computer program run faster in a particular Hardware and Software environment.
• Converting a sequential program to run in parallel is an example of optimisation under this definition!
• You may want to optimise for a different quantity like memory or energy use.
• Performance optimisation can take large amounts of development time.
• Some optimisations improve program speed at the cost of making the program harder to understand (increasing the cost of future changes)
• Some optimisations improve program speed at the cost of making the program more specialised and less general purpose.
• It is always important to evaluate the relative costs and benefits when optimising a program
• This requires the ability to estimate potential gains in advance
• Lattice QCD
• Simulation of the underlying theory of particle physics.
• Requires very large amounts of computer time.
• A single simulation can take months of supercomputer
• Over 90% of the runtime is in a very small number of kernel routines
• Almost any amount of optimisation effort expended on the kernel routines will be justified.
• Performance optimisation usually follows a cycle: Measure performance
Verify results
Change code
Propose change
Measuring performance
• It is not enough to just measure overall speed • You need to know where the time is going.
• There are tools to help you do this • They are called profiling tools.
• They give information about:
• Which sections of code are taking the time
• Sometimes line by line but usually only subroutines.
• Sometimes the type of operation • memory access
• floating point calculations
• file access
• Make sure you understand how variable your results are • Are the results down to my changes or just random variation
Input dependence
• Many codes perform differently with different input data.
• Use multiple sets of input data when measuring performance.
• Make sure these are representative of the problems where you want the code to run quickly.
Variability
• If codes that make significant uses of shared resources (like the file-systems) there performance may depend on external factors like other users.
Only optimise important sections
• Its only worth working on parts of the code that take a lot of time.
• Large speed-up of unimportant sections have little impact on the overall picture.
• Amdahl’s law is this concept applied to parallel processing. • Same insight applies to other forms of optimisation.
• Optimisation is an experimental process.
• You propose reasons why a code section is slow.
• Make corresponding changes.
• The results may surprise you • Need to revise the theory
• Never “optimise” without measuring the impact.
• It is important to know when to stop.
• Each time you propose a code change consider:
• The likely improvement
• Code profile and Amdahl`s law helps here.
• Take account of how long much use you expect for the optimised code. Single use programs are rarely worth optimising.
• The likely cost
• Programming/debuggingtime.
• Delay to starting simulation • “Damage” to the program
Changing code
• Many proposed changes will turn out not be useful.
• You may have to undo your changes. • At the very least keep old versions
• Better to use revision control software.
• Always check the results are still correct !!
• No point measuring performance if the results are wrong • A good test framework will help a lot
Damaging code
• Performance changes can damage other desirable aspects of the code.
• Loss of encapsulation. • Loss of clarity
• Loss of flexibility
• Think about down-side of changes.
• Look for alternative changes with same performance benefit but less damage.
Back-tracking
• Just because a code change made the code faster does not mean you have to keep it.
• Some performance problems can be addressed in many different ways.
• Cache conflicts can be addressed by array padding or loop re- ordering.
• Loop re-ordering is often the cleaner solution but will give little benefit once the arrays have been padded.
• Be prepared to back-track and apply optimisations to earlier versions.
• If you find a code change with good speed-up
• Ask how you can persuade the compiler to make an equivalent change.
Key points
• Optimisation tunes a code for a particular environment
• Not all optimisations are portable.
• Optimisation is an experimental process.
• Need to think about cost/benefit of any change. • Always verify the results are correct.
Experimental frameworks
• Like any experiment you need to keep good records.
• You will be generating large numbers of different versions
of the code.
• You need to know exactly what the different version were. • How you compiled them.
• Did they get the correct answer.
• How did they perform.
• You may need to be able to re-run or reproduce your experiments
• You discover a bug
• A new compiler is released
• A new hardware environment becomes available. • Etc.
Making things easier
• Keep everything under version control (including results)
• Script your tests so they are easy to run and give a clear yes/no answer.
• Write timing data into separate log-files in easily machine readable format.
• Keep notes.
Types of optimisation
• Compiler Optimisation • Auto Tuning
• Hand Optimisation
Compiler Optimisation
• Automatic Optimisation performed by the compiler.
• Compiler takes the source code you give it and tries to find best machine code implementation for the target hardware.
• Compiler only has limited information about the target hardware
• Constrained by the source code you give it. Can only make changes allowed within the language specification.
• Compiler is not intelligent but is much better at some kinds of optimisation than a human programmer.
• Compiler can afford to optimise the entire program.
Auto tuning
• Experiment driven automatic optimisation.
• A wide range of possible implementations are run on
the target hardware to determine the fastest. • Different implementation parameters
• Alternative algorithms.
• May be pure run-time parameters or may generate new source code for each experiment.
• Can only look at the options coded into the auto- tuning.
• Usually specific to one application or library.
• Augments compiler based optimisation.
Hand optimisation
• Changing the source code to improve performance. • Used to augment compiler/auto-tuning not as a
substitute.
• Compiler and auto-tuning code is part of the environment you optimise for.
• Main focus of this course.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com