Dr. Dobb's Journal - April 2008 - (Page 38)

d04will_p3ds 2/13/08 9:39 AM Page 38 Core Technology by Anthony Williams Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Anthony is founder and managing director of Just Software Solutions. He is also maintainer of the Boost thread library and a member of the BSI C++ Standards Panel. He can be contacted at anthony@ justsoftwaresolutions.co.uk. Understanding and using fixed-point math can result in real performance gains Recently, I was working on an application that helps helicopter maintenance engineers adjust their helicopters to fly better. This application analyzes data collected during flight, and provides engineers with information to help them adjust the helicopter. This is a very computationally expensive operation, with extensive use of trigonometric and exponential functions, so though the initial prototypes ran very fast on a PC, they were very slow on the target platform—a handheld device running Windows CE on an ARM processor without hardware floating-point support. After several rounds of optimization focused on improving the algorithm, reducing the use of expensive operations, adjusting the memory-allocation patterns to avoid allocating, freeing memory in a loop, and so forth, the application was running considerably faster than the initial prototype. Unfortunately, it was still too slow, so it was time to pull out the “big guns” and use fixed-point math. This final push doubled the speed of the application, finally bringing the performance within acceptable limits. But it wasn’t easy. In this article, I explain the fixed-point techniques we used to achieve this performance gain. Fixed-Point Math I had put off using fixed-point math because the application made extensive use of sines, cosines, and exponential functions that are nontrivial to implement. However, profiling (see sidebar) showed that the mathematical operations were consuming a very high percentage of CPU time, and I had exhausted all other avenues. This was relatively unsurprising, given that the target CPU didn’t support floating-point operations in hardware, so all mathematical operations were performed by an emulation library. Before proceeding, it was important to check the range of possible values—the range for a double is far 38 Dr. Dobb’s Journal l www.ddj.com l April 2008 larger than can be represented in a simple fixed-point type. For this application, 64-bit fixed-point values (35 bits to the left of the point, 28 bits after, and one sign bit) were sufficient as a replacement. Initially, I hunted the Internet for a free, opensource implementation of fixed-point math. The only implementation I found that provided all the required mathematical operations did speed up the application, as simple operations such as addition and subtraction were considerably improved. Unfortunately, the overall gains weren’t as good as had been hoped for. However, seeing the naïve implementations of the more complex functions (calculating sines and http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - April 2008

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

Dr. Dobb's Journal - April 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.