NAGNews 105 - 19 April 2012


A High-Performance Brownian Bridge for GPUS: Lessons for Bandwidth Bound Applications

The Brownian bridge algorithm is a common technique for constructing Brownian sample paths and is widely used in simulations. The algorithm is memory bandwidth bound: there is very little numerical computation; most of the computation involves moving data around in memory. In addition the algorithm is in a sense under specified since the bridge construction order is arbitrary. At least two construction orders (bisection and depth-order) are commonly used in practice, and this can have an impact when the bridge is used with low discrepancy sequences (e.g. Sobol).

A new Brownian bridge function has been included in the latest release of the NAG Routines for GPUs. The bridge function has two key features:

(a) It achieves close to peak performance in an NVIDIA C2050 GPU. The GPU implementation is at least 10x faster than an OpenMP implementation run on top-end 12 core and 24 core x86-64 systems. The algorithm does not scale on the multicore CPU systems due to the memory bandwidth bottleneck.
(b) It allows arbitrary bridge construction orders and gives a simple, transparent mapping between low discrepancy dimensions and bridge time points.

In this white paper, we describe the optimization techniques employed to get a high performance GPU implementation. Many involved challenging the "conventional wisdom" regarding GPU programming, in particular the importance of occupancy, the speed of shared memory and the impact of branching. We also present full comparative results between the GPU and various x86-64 platforms.

Sven Hammarling made SIAM Fellow

We congratulate Sven Hammarling, NAG Principal Technical Consultant, on being named a SIAM Fellow. Sven received this honour for his outstanding contributions to numerical linear algebra and his work on the LAPACK project.

SIAM fellows are recognised for exemplary research as well as for making outstanding contributions to the community.

More information about the programme and the "Class of 2012" can be found here.

April is Mathematics Awareness Month

It seems that everything has an awareness month, and mathematics is no exception. Four big mathematical societies have launched 'Mathematics Awareness Month' (MAM) with this years' theme being 'Mathematics, Statistics and the Data Deluge'. On the MAM website there are various resources including essays, activities and other ways of getting involved.

NAG Student Prize Award

We're delighted to announce that Eduard Dubin is the most recent winner of a NAG Direct Student Award for his paper 'Habit Formation Heterogeneity: Implications for aggregate asset pricing'. Eduard is a Scientific Assistant at Goethe University.

Technical Seminars, Training and Events

Recent Blog Posts

Keep up to date with NAG's recent blog posts here:

Adding functionality to Excel using the NAG Library for .NET

How To: Call Brent's Root-Finding Algorithm from C#

NAG on the Cloud


NAGNews - Past Issues

We provide an online archive of past issues of NAGNews. For editions prior to these, please contact us.