Accelerating Financial Computations on Multicore and Manycore Processors

By Michael D. McCool and Stefanus Du Toit

September 22, 2008

High-performance computation is a necessity in modern finance. In general, the current value of a financial instrument, such as a stock option, can only be estimated through a complex mathematical simulation that weighs the probability of a range of future possible scenarios. Computing the value at risk in a portfolio of such instruments requires running a large number of such simulations, and optimizing a portfolio to maximize return or minimize risk requires even more computation. Finally, these computations need to be run continuously to keep up with constantly changing market data.

Although a large amount of computation is a necessity, doing it efficiently is crucial since financial datacenters are under severe power and cooling constraints. Multicore processors promise improved computational efficiency within a fixed power and cooling budget. However, achieving high efficiency execution on these processors is non-trivial. In the case of finance, new algorithms are constantly being developed by application specialists called quantitative analysts (or “quants”). Time is literally money in finance, and so high-productivity software development is just as important as efficient execution.

In this article, we will discuss high-productivity strategies for developing efficient financial algorithms that can take advantage of multicore processors, including standard x86 processors but also manycore processors such as GPUs and the Cell BE processor. These strategies can lead to one and even two orders of magnitude improvement in performance per processor.

Multicore processors allow for higher performance at the same power level by supporting multiple lightweight processing elements or “cores” per processor chip. Scaling performance by increasing the clock speed of a single processor is inefficient since the power consumed is proportional to (at least) the square of the clock rate. At some point, it is not practical to increase the clock rate further, as the power consumption and cooling requirements would be excessive. The air-cooling limit in particular was reached several years ago, and clock rates are now on a plateau. In fact, clock rates on individual cores have been decreasing slightly as processor vendors have backed away from the ragged edge in order to improve power efficiency. However, achievable transistor density is still increasing exponentially, following Moore’s Law. This is now translating into an exponentially growing number of cores on each processor chip.

Processors from Intel and AMD supporting the x86 instruction set are now available with four cores, but six and eight core processors are expected soon. Manycore processors such as GPUs and the Cell BE can support significantly more cores, from eight to more than sixteen. In addition, in modern multicore processors each core also supports vector processing, where one instruction can operate on a short array (vector) of data. This is another efficient way to increase performance via parallelism. Vector lengths can vary significantly, with current x86 processors and the Cell BE supporting four-way vectors and GPUs supporting anywhere from five to thirty-two. Vector lengths are also set to increase significantly on x86 processors, with the upcoming Intel AVX instruction set supporting 8-way vectors and the Intel Larrabee architecture supporting 16-way vectors.

Developing software for multicore vectorized processors requires fine-grained parallel programming. A fine-grained approach is needed because the product of the number of cores and the vector length in each core, which defines the number of numerical computations that can be performed in each clock cycle, can easily be in the hundreds. The other difference between modern multicore processors and past multi-processor parallel computers is that all the cores on a multicore processor must share a finite off-chip bandwidth. In order to achieve significant scalability on multicore processors, optimizing the use of this limited resource is absolutely necessary. In fact, in order to hide the latency of memory access it may be necessary to expose and exploit even more algorithmic parallelism, so one part of a computation can proceed while another is waiting for data.

The financial community has significant experience with parallel computing in the form of MPI and other cluster workload distribution frameworks. However, MPI in particular is too heavyweight for the lightweight processing elements in multicore processors (not to mention manycore processors) and cannot, by itself, optimize memory usage or take advantage of the performance opportunities made available through vectorization. Some alternative strategies are needed to get the maximum performance out of multicore processors.

We will now discuss financial workloads. Option pricing is one of the most fundamental operations in financial analytics workloads. More generally, the current value of an “instrument,” of which an option is one example, needs to be evaluated through probabilistic forecasting.

Monte Carlo methods are often used to estimate the current value of such instruments in the face of uncertainty. In a Monte Carlo simulation, random numbers are used to generate a large set of future scenarios. Each instrument can then be priced under each given future scenario, the value discounted back to the current time using an interest calculation (made complicated by the fact that interest rates can also vary with time), and the results averaged (weighted by the probability of the scenario) to estimate the current value.

Simple versions of Monte Carlo seem to be trivially parallelizable, since each simulation can run independently of any other. However, even “simple” Monte Carlo simulations have complications. First, high-quality random numbers need to be generated and we must ensure that each batch of parallel work gets a unique set of independent, high-quality random numbers. This is harder than it sounds. The currently accepted pseudo-random number generators such as Mersenne Twister are intrinsically sequential algorithms, and may involve hundreds of bytes of state.

Typically a lookup table of starting states needs to be generated so that the random number sequence can be restarted at different points in a parallel computation. Since restarting the state of a random number generator is significantly more expensive than stepping serially to the next value, in practice the parallelism is done over “batches” of Monte Carlo experiments, with each batch using a serial subsequence of the random number generator’s output. The size of the batch should be tuned to match the amount of local memory and number of cores in the processor. Also, despite the name, random number generators need to be deterministic and repeatable. For various reasons (including validation, legal and institutional), pricing algorithms need to give the same answer every time they run. Given these issues, some infrastructure that supports parallel random number generation in a consistent way is essential.

The last step in Monte Carlo algorithms can also be troublesome: averaging. First, high precision is often needed here. In practice, the results of millions of Monte Carlo experiments need to be combined. Unfortunately, sum of more than a million numbers cannot easily be done reliably using only single precision, since single precision numbers themselves only have about six to seven digits of precision. Fortunately, manycore accelerators have recently added double-precision capabilities. Second, different strategies for doing the summation, a form of what is often called “reduction,” are possible by exploiting the associativity of the addition operation. There is no single strategy of parallelism for reduction that is optimal for all processors. As with random number generation, in order to make an implementation portable it is useful if reduction operations are abstracted and done by a parallel runtime platform or framework.

Not all Monte Carlo simulations are “simple.” More sophisticated examples manipulate data structures to allow the reuse of results, or use “particle filters” to iteratively focus computation on more important parts of the search space in order to improve accuracy. Simple Monte Carlo simulations often scale very well because they use relatively little memory bandwidth. More sophisticated versions that reuse results via data structures may not scale as well unless care is taken to ensure that memory access does not become a bottleneck. Reuse of results and theoretical improvements in convergence rates need to be weighed against the reduced efficiency of more complex algorithms. However, with some care taken to ensure that the data locality present in a complex algorithm is properly exploited, good scalability is possible even for algorithms with a lot of data reuse and communication.

In order to achieve significant performance improvement on multicore processors, two things are needed: efficient use of low-level operations such as vector instructions, and second, an appropriate choice of parallelization and data decomposition strategy. The latter is obviously important, but how can it be achieved without interfering with the former, or vice-versa? The solution is to use a meta-strategy based on code generation. The dataflow pattern gives the decomposition strategy, and this is managed by one level of abstraction. After the computation has been laid out, it can be optimized for a particular set of low-level operations using a second stage of compilation.

Fortunately, good decomposition strategies can be designed for a relatively small number of recurring patterns. We’d like to figure out how to implement these patterns once, encapsulate them, and then reuse them for all occurrences of the pattern. The trick is to abstract the strategies for dealing with these patterns without introducing additional runtime overhead. Staged code generation accomplishes this. First, a high-level program serves as scaffolding for describing the dataflow of the computation, but is not involved in the actual execution. Instead, the scaffolding only serves to collect the computation into components and organize it for vectorization. Once each component is collected, a second stage of code generation can be used to perform low-level optimizations. This strategy is simpler to implement than it sounds, given the support of a suitable software development platform.

Multicore and manycore processors provide many opportunities for increased performance and greater efficiency. However, actually obtaining good scalability on any multicore processor requires both a fine-grained parallelization strategy and a dataflow design that optimizes memory usage. Memory bandwidth in particular is a limiting resource in multicore processors. Using a high-level framework, it is possible to abstract patterns of dataflow and strategies for dealing with them so they can be used efficiently, while still maintaining processor independence.

About the Authors

Dr. Michael McCool is chief scientist and co-founder of RapidMind and an associate professor at the University of Waterloo. He continues to perform research within the Computer Graphics Lab at the University of Waterloo. Professor McCool has a diverse set of published papers, and his research interests include high-quality real-time rendering, global and local illumination, hardware algorithms, parallel computing, reconfigurable computing, interval and Monte Carlo methods and applications, end-user programming and metaprogramming, image and signal processing, and sampling. He has degrees in Computer Engineering and Computer Science.

Stefanus Du Toit is chief architect and co-founder of RapidMind, and has led the development and evolution of the RapidMind platform since 2003. Stefanus has extensive experience in the areas of graphics, GPGPU, systems programming and compilers. He holds a Bachelors of Mathematics degree in Computer Science.

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industy updates delivered to you every week!

IBM, D-Wave Report Quantum Computing Advances

May 18, 2017

IBM said this week it has built and tested a pair of quantum computing processors, including a prototype of a commercial version. That progress follows an an Read more…

By George Leopold

PRACEdays 2017 Wraps Up in Barcelona

May 18, 2017

Barcelona has been absolutely lovely; the weather, the food, the people. I am, sadly, finishing my last day at PRACEdays 2017 with two sessions: an in-depth loo Read more…

By Kim McMahon

US, Europe, Japan Deepen Research Computing Partnership

May 18, 2017

On May 17, 2017, a ceremony was held during the PRACEdays 2017 conference in Barcelona to announce the memorandum of understanding (MOU) between PRACE in Europe Read more…

By Tiffany Trader

NSF, IARPA, and SRC Push into “Semiconductor Synthetic Biology” Computing

May 18, 2017

Research into how biological systems might be fashioned into computational technology has a long history with various DNA-based computing approaches explored. N Read more…

By John Russell

HPE Extreme Performance Solutions

Supercomputers Helping Researchers Predict Climate Change

Today’s weather and climate scientists are tasked with analyzing a massive tidal wave of data in order to better understand and predict significant changes affecting the climate. Read more…

DOE’s HPC4Mfg Leads to Paper Manufacturing Improvement

May 17, 2017

Papermaking ranks third behind only petroleum refining and chemical production in terms of energy consumption. Recently, simulations made possible by the U.S. D Read more…

By John Russell

PRACEdays 2017: The start of a beautiful week in Barcelona

May 17, 2017

Touching down in Barcelona on Saturday afternoon, it was warm, sunny, and oh so Spanish. I was greeted at my hotel with a glass of Cava to sip and treated to a Read more…

By Kim McMahon

NSF Issues $60M RFP for “Towards a Leadership-Class” System

May 16, 2017

In case you missed it, the National Science Foundation issued the request for proposals (RFP) for the next ‘Towards a Leadership-Class Computing Facility – Read more…

By John Russell

Cray Offers Supercomputing as a Service, Targets Biotechs First

May 16, 2017

Leading supercomputer vendor Cray and datacenter/cloud provider the Markley Group today announced plans to jointly deliver supercomputing as a service. The init Read more…

By John Russell

Cray Offers Supercomputing as a Service, Targets Biotechs First

May 16, 2017

Leading supercomputer vendor Cray and datacenter/cloud provider the Markley Group today announced plans to jointly deliver supercomputing as a service. The init Read more…

By John Russell

HPE’s Memory-centric The Machine Coming into View, Opens ARMs to 3rd-party Developers

May 16, 2017

Announced three years ago, HPE’s The Machine is said to be the largest R&D program in the venerable company’s history, one that could be progressing tow Read more…

By Doug Black

What’s Up with Hyperion as It Transitions From IDC?

May 15, 2017

If you’re wondering what’s happening with Hyperion Research – formerly the IDC HPC group – apparently you are not alone, says Steve Conway, now senior V Read more…

By John Russell

Nvidia’s Mammoth Volta GPU Aims High for AI, HPC

May 10, 2017

At Nvidia's GPU Technology Conference (GTC17) in San Jose, Calif., this morning, CEO Jensen Huang announced the company's much-anticipated Volta architecture a Read more…

By Tiffany Trader

HPE Launches Servers, Services, and Collaboration at GTC

May 10, 2017

Hewlett Packard Enterprise (HPE) today launched a new liquid cooled GPU-driven Apollo platform based on SGI ICE architecture, a new collaboration with NVIDIA, a Read more…

By John Russell

IBM PowerAI Tools Aim to Ease Deep Learning Data Prep, Shorten Training 

May 10, 2017

A new set of GPU-powered AI software announced by IBM today brings automation to many of the tedious, time consuming and complex aspects of AI project on-rampin Read more…

By Doug Black

Bright Computing 8.0 Adds Azure, Expands Machine Learning Support

May 9, 2017

Bright Computing, long a prominent provider of cluster management tools for HPC, today released version 8.0 of Bright Cluster Manager and Bright OpenStack. The Read more…

By John Russell

Microsoft Azure Will Debut Pascal GPU Instances This Year

May 8, 2017

As Nvidia's GPU Technology Conference gets underway in San Jose, Calif., Microsoft today revealed plans to add Pascal-generation GPU horsepower to its Azure clo Read more…

By Tiffany Trader

Quantum Bits: D-Wave and VW; Google Quantum Lab; IBM Expands Access

March 21, 2017

For a technology that’s usually characterized as far off and in a distant galaxy, quantum computing has been steadily picking up steam. Just how close real-wo Read more…

By John Russell

Google Pulls Back the Covers on Its First Machine Learning Chip

April 6, 2017

This week Google released a report detailing the design and performance characteristics of the Tensor Processing Unit (TPU), its custom ASIC for the inference Read more…

By Tiffany Trader

Trump Budget Targets NIH, DOE, and EPA; No Mention of NSF

March 16, 2017

President Trump’s proposed U.S. fiscal 2018 budget issued today sharply cuts science spending while bolstering military spending as he promised during the cam Read more…

By John Russell

HPC Compiler Company PathScale Seeks Life Raft

March 23, 2017

HPCwire has learned that HPC compiler company PathScale has fallen on difficult times and is asking the community for help or actively seeking a buyer for its a Read more…

By Tiffany Trader

CPU-based Visualization Positions for Exascale Supercomputing

March 16, 2017

Since our first formal product releases of OSPRay and OpenSWR libraries in 2016, CPU-based Software Defined Visualization (SDVis) has achieved wide-spread adopt Read more…

By Jim Jeffers, Principal Engineer and Engineering Leader, Intel

Nvidia Responds to Google TPU Benchmarking

April 10, 2017

Last week, Google reported that its custom ASIC Tensor Processing Unit (TPU) was 15-30x faster for inferencing workloads than Nvidia's K80 GPU (see our coverage Read more…

By Tiffany Trader

TSUBAME3.0 Points to Future HPE Pascal-NVLink-OPA Server

February 17, 2017

Since our initial coverage of the TSUBAME3.0 supercomputer yesterday, more details have come to light on this innovative project. Of particular interest is a ne Read more…

By Tiffany Trader

Facebook Open Sources Caffe2; Nvidia, Intel Rush to Optimize

April 18, 2017

From its F8 developer conference in San Jose, Calif., today, Facebook announced Caffe2, a new open-source, cross-platform framework for deep learning. Caffe2 is Read more…

By Tiffany Trader

Leading Solution Providers

Tokyo Tech’s TSUBAME3.0 Will Be First HPE-SGI Super

February 16, 2017

In a press event Friday afternoon local time in Japan, Tokyo Institute of Technology (Tokyo Tech) announced its plans for the TSUBAME3.0 supercomputer, which w Read more…

By Tiffany Trader

Nvidia’s Mammoth Volta GPU Aims High for AI, HPC

May 10, 2017

At Nvidia's GPU Technology Conference (GTC17) in San Jose, Calif., this morning, CEO Jensen Huang announced the company's much-anticipated Volta architecture a Read more…

By Tiffany Trader

Is Liquid Cooling Ready to Go Mainstream?

February 13, 2017

Lost in the frenzy of SC16 was a substantial rise in the number of vendors showing server oriented liquid cooling technologies. Three decades ago liquid cooling Read more…

By Steve Campbell

MIT Mathematician Spins Up 220,000-Core Google Compute Cluster

April 21, 2017

On Thursday, Google announced that MIT math professor and computational number theorist Andrew V. Sutherland had set a record for the largest Google Compute Eng Read more…

By Tiffany Trader

IBM Wants to be “Red Hat” of Deep Learning

January 26, 2017

IBM today announced the addition of TensorFlow and Chainer deep learning frameworks to its PowerAI suite of deep learning tools, which already includes popular Read more…

By John Russell

HPC Startup Advances Auto-Parallelization’s Promise

January 23, 2017

The shift from single core to multicore hardware has made finding parallelism in codes more important than ever, but that hasn't made the task of parallel progr Read more…

By Tiffany Trader

HPC Technique Propels Deep Learning at Scale

February 21, 2017

Researchers from Baidu's Silicon Valley AI Lab (SVAIL) have adapted a well-known HPC communication technique to boost the speed and scale of their neural networ Read more…

By Tiffany Trader

US Supercomputing Leaders Tackle the China Question

March 15, 2017

As China continues to prove its supercomputing mettle via the Top500 list and the forward march of its ambitious plans to stand up an exascale machine by 2020, Read more…

By Tiffany Trader

  • arrow
  • Click Here for More Headlines
  • arrow
Share This