October 7, 2009
Module : Console Development Part 3
Optimisation Techniques
After learning a little bit about the compiler and the way executables are made for the PSP, the main aim I have for writing my project is to keep my data structures and programming as simple as possible. The more complex calculation, the longer amount of time the complier will take to change my code into machine code and thus slowing down operations (usually). Below is a short list of methods I will be using when writing my program -
- Use inline functions for small functions called a lot.
- Avoid floating point arithmetic, especially for divide and multiplication operations.
- Use integers with integers and floats with floats as conversion can slow processing.
- Use bit shifting by powers of 2 for integer multiplication and division.
- When using matrix operations make use of sparseness i.e. zero entries.
- Avoid square roots and trigonometry functions.
- When performing mathematical calculations, see if I can reduce the expressions manually before coding them. For example, n*(f+1)/n is equivalent to (f+1) because the multiplication and division of n cancel out.
- Cache any complex mathematical results that may be used later on down the pipeline.
- Make effective use of loop unrolling.
- Make use of look up tables for fixed values, especially with cos and sin functions.
- Use ASM language to gain that little bit more speed.
- Use pro tools like VTune for effective profiling.
- Make use of effective memory allocation by using pools, keeping data structures together and reuse immediately.
The main focus is to get something working on screen as soon as possible then to make use of these techniques to make the demo run faster and more efficiently. There is no point in trying to write the most optimized code from the start as it is likely to not work or perform as well as refactored code. What I aim to do is to apply these techniques to code that is already working and behaving as well as it should to improve performance and speed.
“Pre-mature optimization is the root of all evil”
Implementation
After deciding to do try and implement the plasma fractal, I decided to first investigate exactly what happens to create this effect, and more importantly how quickly I can implement it for the PSP. I started working through one of the examples and reading up on the online documentation.
How the plasma effect is made
The plasma effects are generated by looping through colours and warping them in a way to create a fluid liquid type effect.
There are quite a few ways to implement the plasma effect so I decided to first look at the best methods to implement one relevant to the PSP’s hardware and then look at ways to optimise the performance once I had a demo up and running.
The first step for the demo is to set up the screen using a cosine wave. As cosine always gives a value between -1 and +1, I can use this to set the colour value of the pixel to the sine of its x co ordinate. This then can be set to 2 different colours, each representing the peaks and valleys of the wave.
Implementing a colour palette can also be done in many ways however the way I decided to do it was to have a data structure holding the hex values of the colours I wanted to use and then use the pre – calculated cos values stored in a buffer to re – draw the pixels.
Key Optimisation
Look Up Tables – Using functions like sin and cos can be expensive to compute and so instead I decided to use a look up table which instead only requires a simple array indexing operation. A value is returned from memory rather than working out a significantly more expensive operation. I used 2 look up tables to hold the data for the cosine computations as well as the hex values for the colour tables.
Loop unrolling – In the update method for my program I originally had the row colour data being worked out in 1 big for loop which meant that a lot of data was being processed all at once causing a slight bottleneck in my program. I decided to compute each row in its own loop rather than let the data all be done at once.
Using a 1D instead of a 2D array – The screenData.h file which holds the co – ordinate and colour data was originally in a 2D array which I was using to work out the 2 columns for the plasma. However after realising that the y co – ordinates was not really needed when working out this step in the program, I instead set just the x value as there is no change in the y value which meant that I had less data to process. I could have used a 2D array if I wanted to pass a cosine value through the y value as well, however for the purpose of this program it wasn’t needed.
Further Optimisations – Looking at my program there are still things I would like to implement and optimise. The screenData.h file holds a lot of data that I would prefer to be dynamically allocated and eventually I would like to do some more profiling on my code itself. I would also like to implement a sin function in the y co ordinate for each pixel to create a more traditional plasma effect.
Module : Console Development Part 2
Task
To write an individual project, to be written in assembly, C or C++, cross compiled using Sony’s patched GNU toolchain (psp-gcc or ProDG compiler and make) under the Cygwin environment, and running on the DTP-T1000A hardware tool (PSP devkit).
The project does not have to be a full working game (though it might optionally be a game), but a small tech demo that can be launched on a PSP devkit using the Windows debugger pspdbg. The demo design is almost completely up to me, but it must pack as many features as possible into the very tight technical constraints described below –
Technical Requirements
This assignment allows you to act freely within tight and well-defined constraints. You are encouraged to be as creative as possible with your demo, as long as it keeps within the following limits. The point is to use this creative invitation as a mission to squeeze as much as possible into this tiny space:
Technical essentials
_ No more than 1,024 bytes of total static data in (pre-linkage) object files
_ No more than 4,096 bytes of machine code in (pre-linkage) object files
_ Frame rate keeps to at least 30FPS after the first 30 secs of runtime
Design essentials
_ When executed on PSP devkit, PRX produces on-screen animation
_ Demo can be left unattended and will continue to animate (e.g. looping)
Platform essentials
_ Demo code is written in MIPS asm / C / C++ (or some mixture of these)
_ Demo compiles using either psp-gcc or ProDG’s PSP compiler
_ Does NOT use ProDG VS2008 Integration for build (recommend make)
_ Links with official PSP runtime libraries to produce executable PRX file
Optional features
_ PRX built from multiple source files with clearly distinguished roles
_ Demo includes user interaction elements, possibly even gameplay
_ Build options to include on-screen debug info code (e.g. FPS counter)
_ Code architecture uses clear techniques to minimize code size
_ Memory usage optimized through choice of type, layout and allocations
_ Audio libraries and software synthesis used to add an audio track
_ Frame update calculations optimized using vector instructions in VFPU
_ Inline MIPS assembly used to optimize critical sections of source code
Initial Ideas
L – System
The Lindenmayer system is a parallel rewriting system made famous by Hungarian biologist Aristid Lindenmayer. L – Systems can be used to generate fractals by iterating through a specific set of rules without changing the rules. A procedural approach creates content “on the fly” which would be advantageous to my project due to the small data constraint. One system I have been looking at is the Koch snowflake –
Alphabet: F
Constants: +, -
Axiom: F++F++F
“F” means to draw forward
“+” means to turn right 60 degrees
“_” means to turn left 60 degrees
Starting with a Line segment and iterating through each line uses the following
- Divide line into 3 equal segments
- Draw a triangle using the middle segment as the base
- Remove the line that was the base
Plasma Effects
The plasma effect has a history of being used in the demo scene and after looking at some examples online, there are also a lot of optimization methods that can be implemented. The main theory behind creating plasma effects is by combining 2 functions and redrawing the canvas using a 256 color palette. This gives a “plasma” style flow of colors which are redrawn based on a time value with the illusion that with every new step, the colors will flow.
Base function -
f (X, Y, T) = n
X and Y being the co ordinates for the Canvas, T being the time and n being an integer between 0 and 256 representing the color palette.
Mid Point Displacement
I have been looking at this in another module and have successfully been able to implement it using Microsoft’s directX platform. This is done using a “plasma fractal” or a “diamond square” to create mountain like terrain based on randomly displacing the midpoint of a line.
- Get midpoint of line and displace by some random height value.
- [-h, h]
- Repeat on new line segments.
- Multiply height range by 2 – roughness.
- Repeat until detail is achieved.
June 19, 2009
Module : Console Development Part 1
Console development stretched over both semesters in the second year as part of my degree and was by far the most challenging. The main focus of this module was to produce high performance code for an external fixed hardware platform. A huge part of this module was understanding the relationship between code performance and platform hardware architecture which meant looking much deeper into how computer systems work. The first semester was spent looking at low level programming and performance optimisation and really getting involved with machine level code whilst the second semester allowed me to test what I had learned and apply it to development on a PSP development kit. Having access to equipment and tools such as this once again shows Derby University’s amazing facilities for my course and demonstrates why it’s one of the best courses around for computer games programming.
The Project
The coursework for this module was not posted until the second semester and so the first semester was spend researching more theory based tasks and getting used to coding at a lower level than what we had been used using visual studios. Instead we worked through on-line MIPs tutorials on Mars’s Spin environment writing low level machine code working directly with registers.
In the second semester we were introduced to developing and profiling on the PSP platform before eventually being required to write a small 4kb raw data demo for the PSP. It is important to point out at this point that under no circumstances can I post or even discuss Sony’s code as it would be a breach of contract and could land myself and the University in trouble and so I will instead be discussing methods and approaches to solving problems I came across in my project.
For the first few weeks I spent most of my time re – looking at computer architecture and in particular binary operation, logic gates and computer pipeline structure. In the first year, computer architecture was one subject that I found really difficult to be interested in as I preferred coding and working in software rather than being involved with hardware. I understood most of the concepts and how hardware can play an important role in all manners of computing but if I’m truly honest, I just wasn’t interested in it. I knew that this module would be different as we would be working on the PSPs and so that changed my attitude towards hardware and eventually console development became my favorite module in the second semester.
