1. Accuracy
Accuracy is the most basic requirement. If a simple arithmetic operation give a wrong answer, it will certainly damage the perception of the accountability of this software. Of course accuracy more likely defined as the nature of the algorithm. The accuracy of the algorithm is normally predictable by the notation of O(deltaX^n). For instance using Talyor Series to discretize a continuous function. Based on the polynomial to simulate it (a*x^n + ...), the error will be ~O(delatX^(N+1)).
Another common methods to evaluate the accuracy is the peer comparison. Compare it with competing algorithms or well-known problems/benchmark. This often can be done when mathematicians are developing the algorithm. Those peer comparison examples can be found on the academic publication, conference meeting or industrial known challenges.
Integration test is the another way to evaluate the accuracy of the newly developed algorithms by simple compare the result with the other peer in-house algorithms with the assumption that the software team have already accumulated considerable integration tests.
The accuracy often comes as the nature of the algorithm. But it can also be affected by the programming/computers, as the number that the computer can represent is not continuous and the computer has its resolution as well. Please read more about numerical errors in scientific computing in my previous blog entry, http://cpluspluslearning-petert.blogspot.co.uk/2014/03/scientific-computing-numerical-errors.html.
2. Speed
There are two aspects for this item. One is from the algorithm. In this territory it has a different name - convergence. This is normally defined when the algorithm is developed and accompanied together with peer comparison. For instance Linear search take O(n) and binary search takes O(log2n). This is the nature of the algorithms or solvers. If looking to improve the speed of software, this should be the first thing you should look at.
The second aspect is coming from programming. It includes the language you are using (Fortran, C. C++, Matlab) and the techniques using in the program (static polymorphism vs. dynamic polymorphism in C++)
The choice of language
This has been C/C++ playground for a long time in commercial business due to the performance and flexibility of this language. In academic world Fortran has been there for quite a long time. Of course I can't miss Matlab for quick idea modelling and experimenting. Surely for some simple application Microsoft Excel has been used for algorithm modelling as well. So far I have encounter a few combinations that are quick popular.
- Fortran and C/C++
- Matlab and C/C++
Most of time Fortran code still exists as the legacy code. And C/C++ code/module is implemented or wrapped on Fortran code to provide commercial deliverable package. Matlab is mostly existing for quick modeling only. Of course some C/C++ packages are developed as plug-ins for Matlab as well. I have seen these 3 languages working together very nicely. Comparing with the speed, Fotran code is at the top. In quite a few occasions I compared with the performance of C++ with Fortran. Fortran is ~25% faster than C++. (My guess: one of reasons causing the performance penalty in C++ is coming from the implementation of STL - memory reallocation) And some of my colleagues had experience on C, which has under but very close performance with Fortran.
Nowadays functional languages have been becoming more and more popular, like Microsoft F# and Scala. The key for their popularity is to bridge the workflow between the mathematician and developers. Often using the combinations of languages as shown above needs close work relationship between mathematicians and developers. Sometimes this could be very expensive and time-consuming, because the misunderstanding could happen between their communication and bugs could buried in the implementation as C/C++ is regarded as one of most difficult programming languages. These functional languages are developed purely for the purpose of work productivity and software quality. It simply makes programming easier for mathematicians to simplify the workflow and at the same time use cheap but more powerful hardware to compensate the speed.
Techniques used in C++
- Static polymorphism vs. dynamic polymorphism. See my other blog entry, http://cpluspluslearning-petert.blogspot.co.uk/2014/03/design-pattern-curiously-recurring.html.
- Inline functions
- General practice of more efficient C++. Except use better programming techniques, such as post-increment vs. pre-increment, how to use memory is also very key for performance of C/C++ programming. See my previous blog entries, http://cpluspluslearning-petert.blogspot.co.uk/2014/03/performance-running-out-of-memory-heap.html and http://cpluspluslearning-petert.blogspot.co.uk/2014/03/performance-running-out-of-stack.html.
3. Extensibility
It is often referring that the design has to be flexible enough to take extra algorithm to solve the existing problems/systems and new problems/systems can be constructed to be solved by existing algorithm. From this prospect we are talking about this issues from the programming point view. The software design/architecture has to be flexible to be expanded. In other words the architecture has to decouple between the system construction and algorithm implementation.
Fortunately there have been quite a few design patterns that are designed for this purpose. For instance strategy pattern and template method pattern. See my blog entry about strategy pattern, http://cpluspluslearning-petert.blogspot.co.uk/2014/04/design-patterns-for-scientific.html.
4. Implementation impact on accuracy and speed
Often when we are working on the commercial environment, the academic/programming techniques are developed/adopted to pursue higher accuracy and faster speed in order to gain competing advantages. Very often some techniques or even algorithms are supposed to achieve higher accuracy or/and faster speed in theory but in fact they fail to do so. I call it the impact of implementation.
The very first impact is the overhead of the techniques or algorithms. For example a common technique is to reduce the size of system or decompose a large system to a few smaller systems to achieve faster speed (at least for speed, could achieve higher accuracy or numerical robustness as well). Most often these techniques are not free to run at all. For some particular system the overhead could be very large. In my previous project I have seen some techniques can work really badly, a huge overhead, on some edging cases on optimization problem.
The second impact is coming from the problem/system itself. Even thought in some cases the overhead is neglect-able, the actual solving process does not speed up or even become worse than the original problem. In my previous projects I have seen much worse performance on problems with large discontinuity and sensitive cases. For instance the same problem but with varying constraints could result in tow polar performance on accuracy or/and speed.
The best practice to collect a reasonable large collection of integration tests for verifying accuracy and speed. Re-run these tests before releasing (after the feature is completed by reasonably ahead before releasing). Make sure each feature will delivery what it promises and not degrade the performance of the software. But be clear there is no techniques/algorithms have positive impact on all cases. Be realistic and practical about your target when deciding if a feature has positive impact on the performance. Have a representative collections of integration tests from your business unit and be clear of the main characteristic of this technique/algorithm, robustness, speed, accuracy and so on. If possible, work out the heuristic clause to decide if the feature is to run or not. However this has been proven very difficult in my previous projects.
5. Summary
Excellent scientific programming will needs,
- Competent mathematicians and developers
- Seamless communication between them
- Suitable choices of programming languages
- A representative collection of integration tests for accuracy and speed.
The very first impact is the overhead of the techniques or algorithms. For example a common technique is to reduce the size of system or decompose a large system to a few smaller systems to achieve faster speed (at least for speed, could achieve higher accuracy or numerical robustness as well). Most often these techniques are not free to run at all. For some particular system the overhead could be very large. In my previous project I have seen some techniques can work really badly, a huge overhead, on some edging cases on optimization problem.
The second impact is coming from the problem/system itself. Even thought in some cases the overhead is neglect-able, the actual solving process does not speed up or even become worse than the original problem. In my previous projects I have seen much worse performance on problems with large discontinuity and sensitive cases. For instance the same problem but with varying constraints could result in tow polar performance on accuracy or/and speed.
The best practice to collect a reasonable large collection of integration tests for verifying accuracy and speed. Re-run these tests before releasing (after the feature is completed by reasonably ahead before releasing). Make sure each feature will delivery what it promises and not degrade the performance of the software. But be clear there is no techniques/algorithms have positive impact on all cases. Be realistic and practical about your target when deciding if a feature has positive impact on the performance. Have a representative collections of integration tests from your business unit and be clear of the main characteristic of this technique/algorithm, robustness, speed, accuracy and so on. If possible, work out the heuristic clause to decide if the feature is to run or not. However this has been proven very difficult in my previous projects.
5. Summary
Excellent scientific programming will needs,
- Competent mathematicians and developers
- Seamless communication between them
- Suitable choices of programming languages
- A representative collection of integration tests for accuracy and speed.
No comments:
Post a Comment