Barrel scheduled processors interleave instructions from a number of hardware threads to remove in-pipeline dependencies and avoid stalls. Thread scheduling approaches range from low resource static scheduling to high resource but more flexible dynamic scheduling. A key advantage of the more costly dynamic scheduling is the ability to hide memory latencies. This work proposes DySCI, a new method of dynamic scheduling that utilises pre-existing logic in pipelined memory buses to carry thread indices, reducing the required scheduling resources without sacrificing flexibility. DySCI has been implemented on the statically scheduled BRISKI core to add dynamic scheduling capability at a cost of only a 5% LUT increase.

This article proposes an event-driven solution to genotype imputation, a technique used to statistically infer missing genetic markers in DNA. The work implements the widely accepted Li and Stephens model, primary contributor to the computational complexity of modern x86 solutions, in an attempt to determine whether further investigation of the application is warranted in the event-driven domain. The model is implemented using graph-based Hidden Markov Modeling and executed as a customized forward/backward dynamic programming algorithm. The solution uses an event-driven paradigm to map the algorithm to thousands of concurrent cores, where events are small messages that carry both control and data within the algorithm. The design of a single processing element is discussed. This is then extended across multiple cores and executed on a custom RISC-V NoC cluster called POETS. Results demonstrate how the algorithm scales over increasing hardware resources and a multi-core run demonstrates a 270X reduction in wall-clock processing time when compared to a single-threaded x86 solution. Optimisation of the algorithm via linear interpolation is then introduced and tested, with results demonstrating a wall-clock reduction time of ∼ 5 orders of magnitude when compared to a similarly optimised x86 solution.

Manycore architectures are increasingly favouring message-passing or partitioned global address spaces (PGAS) over cache coherency for reasons of power efficiency and scalability. However, in the absence of cache coherency, there can be a lack of hardware support for one-to-many communication patterns, which are prevalent in some application domains. To address this, we present new hardware primitives for multicast communication in rack-scale manycore systems. These primitives guarantee delivery to both colocated and distributed destinations, and can capture large unstructured communication patterns precisely. As a result, reliable multicast transfers among any number of software tasks, connected in any topology, can be fully offloaded to hardware. We implement the new primitives in a research platform consisting of 50K RISC-V threads distributed over 48 FPGAs, and demonstrate significant performance benefits on a range of applications expressed using a high-level vertex-centric programming model.

Barrier primitives provided by standard parallel programming APIs are the primary means by which applications implement global synchronisation. Typically these primitives are fully-committed to synchronisation in the sense that, once a barrier is entered, synchronisation is the only way out. For message-passing applications, this raises the question of what happens when a message arrives at a thread that already resides in a barrier. Without a satisfactory answer, barriers do not interact with message-passing in any useful way.In this paper, we propose a new refutable barrier primitive that combines with message-passing to form a simple, expressive, efficient, well-defined API. It has a clear semantics based on termination detection, and supports the development of both globally-synchronous and asynchronous parallel applications.To evaluate the new primitive, we implement it in a prototype large-scale message-passing machine with 49,152 RISC-V threads distributed over 48 FPGAs. We show that hardware support for the primitive leads to a highly-efficient implementation, capable of synchronisation rates that are an order-of-magnitude higher than what is achievable in software. Using the primitive, we implement synchronous and asynchronous versions of a range of applications, observing that each version can have significant advantages over the other, depending on the application. Therefore, a barrier primitive supporting both styles can greatly assist the development of parallel programs.

Neuromorphic computing is gaining momentum as an alternative hardware platform for large-scale neural simulation. However, with several major devices and systems available and planned, often with very different characteristics, it is not always clear which platform is suitable for which application. Simulating the platform on conventional computers is typically too slow to be of use, but an alternative approach is to implement an `emulation' of the hardware in FPGAs which can execute at near-hardware speeds but does not commit to a specific hardware architecture. We present an overlay model - a method which superimposes bespoke features on top of a standard template - in both hardware and software to implement neuromorphic architectures using the POETS (Partially Ordered Event Triggered Systems) system. This combination of overlays permits very large-scale simulations to be performed in real time for hardware exploration or application verification, while retaining the flexibility to redefine either the hardware or software layer, if results indicate potential to improve performance, or significant design problems. Using this system we simulate up to 500,000 neurons on a single-box system, that can be scaled to ~4,000,000 neurons in an 8-box configuration. Results indicate the crucial constraint for real-time simulation: peak input spike rate per neuron; and help to optimise both hardware and software around neural application requirements. The preliminary architecture demonstrates the feasibility of an overlay model, while indicating directions for future neuromorphic systems. With POETS, we introduce a platform that can help to shape and investigate the neuromorphic architectures of the future.

High-Level Synthesis (HLS) tools usually treat floating-point operators as black-box IP cores, and then schedule them as primitives when synthesising code to circuits. This approach relies on a library of IP blocks for chosen floating-point formats, which are pre-characterised to determine latency and area properties needed at compilation time. Two weaknesses of this approach are that it limits the number of floating-point formats - typically to half, single, and double - and that it requires conservative per-cycle scheduling of operators. Modern HLS tools have sophisticated intra-cycle scheduling of integer primitives, as well as C++ front-ends that can execute substantial algorithms at compile-time. This has enabled the creation of platform-independent C++ floating-point libraries which generate custom-precision operators at compile-time, while providing similar or better results as vendor-supplied IP blocks. However, certain problems and questions related to compilation performance and verification remain, so it is not yet clear how widely applicable this technique is.

High-level synthesis (HLS) tools such as VivadoHLS interpret C/C++ code supplemented by proprietary optimization directives called pragmas. In order to perform loop pipelining, HLS compilers have to deal with non-trivial loop-carried data dependencies. In VivadoHLS, the dependence pragma could be used to enforce or to eliminate such dependencies, but, the behavior of this directive is only informally specified through examples. Most of the time programmers and the compiler seem to agree on what the directive means, but the accidental misuse of this pragma can lead to the silent generation of an erroneous register-transfer level (RTL) design, meaning code that previously worked may break with newer more aggressively optimised releases of the compiler. We use the Coq proof assistant to formally specify and verify the behavior of the VivadoHLS dependence pragma. We first embed the syntax and the semantics of a tiny imperative language Imp in Coq and specify a conformance relation between an Imp program and a dependence pragma based on data-flow transformations. We then implement semi-automated methods to formally verify such conformance relations for non-nested loop bodies.

High-level Synthesis (HLS) tools have greatly increased the productivity of FPGA application development, making it possible to easily create highly-parallel application-accelerators. However, while FPGAs are known for the ability to customise the number representation of data-paths, most HLS work only uses custom-precision for fixed-point representations, and for floating-point relies on the 64-, 32-, and 16-bitformats provided by vendors. This paper presents a solution for parametrised floating-point in HLS via C++ templates, allowing for compile-time selection of exponent and fraction widths, including the use of mixed precisions for input arguments and result types. By using arbitrary width integers and compile-time logic the resulting operators describe the same data-path as an external floating-point IP generator, while still allowing the HLS tool to perform detailed optimisation and scheduling of the internal components. We show that the resulting custom-width HLS cores provide similar area and performance to platform-native vendor IP blocks, while adding full support for heterogeneous precision floating-point data-paths to HLS tools.

Document ranking is used to order query results by relevance with ranking models. ListNet is a well-know ranking approach for constructing and training learning to rank models. Compared with traditional learning approaches, ListNet delivers better accuracy, but is computationally too expensive to learn models with large datasets due to the large number of permutations involved in computing the gradients. This paper introduces a position-aware sampling approach, which takes the importance of ranking positions into account and shows better accuracy than previous sampling methods. We also propose an effective quantisation method based on FPGA devices for the ListNet algorithm, which organises the gradient values to several batches, and associates each batch with a different fractional precision. We implemented our approach on a Xilinx Ultrascale+ board and applied it to the MQ 2008 benchmark dataset for ranking. The experiment results show a 4.42x speedup over an Nvidia GTX 1080T GPU implementation with 2% accuracy loss.

Commodity FPGA boards with advanced networking facilities have great potential in the construction of high-performance compute clusters that scale. However, low-level design tools and long synthesis times are major barriers to productivity for application developers. In this paper, we explore the potential of a distributed soft-processor overlay, programmed in software at a high-level of abstraction, to deliver a useful level of performance for FPGA clusters. In particular, we demonstrate the use of hardware multhreading to achieve a fast, space-efficient, high-throughput overlay, and compare a 12-FPGA instance of it (12,288 RISC-V threads) against a conventional Xeon cluster on the problem of distributed graph processing.

When using SRAM-based FPGA devices in safety critical applications testing against bitflips in the device configuration memory is essential. Often such tests are achieved by corrupting configuration memory bits of a running device, but this has many scalability, reliability, and flexibility challenges. In this paper, we present a framework and a concrete implementation of a parallel fault injection cluster that addresses these challenges. Scalability is addressed by using multiple identical FPGA devices, each testing a different region in parallel. Reliability is addressed by using reconfigurable system-on-chip devices, that are isolated from each other. Flexibility is addressed by using a pending commit structure, that continually checkpoints the overall experiment and allows elastic scaling. We test and showcase our approach by exhaustively flipping every bit in the configuration memory of the CHStone benchmark suite and a VivadoHLS generated k-means clustering image processing application. Our results show that: linear scaling is possible as the number of devices increases; the majority of error inducing bitflips in the k-means application do not significantly impact the output; and that the Xilinx Essential bits tool may miss some bits that can induce errors.

Document ranking is used to order query results by relevance, with different document ranking models providing trade-offs between ranking accuracy and training speed. ListNet is a well-known ranking approach which achieves high accuracy, but is infeasible in practice because training time is quadratic in the number of training documents. This paper considers the acceleration of ListNet training using FPGAs, and improves training speed by using hardware-oriented algorithmic optimisations, and by transforming algorithm structures to remove dependencies and expose parallelism. We implemented our approach on a Xilinx ultrascale FPGA board and applied it to the MQ 2008 benchmark dataset for ranking. Compared to existing ranking approaches ours shows an improvement from 0.29 to 0.33 in ranking accuracy on the same dataset using the NDCG@10 metric. Taking into account the communication between software and hardware, we are able to achieve a 3.21x speedup over an Intel Xeon1.6 GHz CPU implementation.

The binomial-tree model is a numerical method widely used in finance with a computational complexity which is quadratic with respect to the solution accuracy. The existing research has employed reconfigurable computing to provide faster solutions compared with general-purpose processors, but they require low-level manual design by a hardware engineer, and can only solve American options. This paper presents a formal mathematical framework that captures a large class of binomial-tree problems, and provides a systolic data-movement template that maps the framework into digital hardware. This paper also presents a fully automated design flow, which takes C-level user descriptions of binomial trees, with custom data types and tree operations, and automatically generates fully pipelined reconfigurable hardware solutions in field-programmable gate array (FPGA) bit-stream files. On a Xilinx Virtex-7 xc7vx980t FPGA at a 100-MHz clock frequency, we require 54-µs latency to solve three 876-step 32-bit fixed-point American option binomial trees, with a pricing rate of 114k trees/s. From the same device and in comparison to the existing solutions with equivalent FPGA technology, we always achieve better throughput. This ranges from 1.4× throughput compared with a hand-tuned register-transfer level systolic design, to 9.1× and 5.6× improvement with respect to scalar and vector architectures, respectively.

Reads and writes to global data in off-chip RAM can limit the performance achieved with HLS tools, as each access takes multiple cycles and usually blocks progress in the application state machine. This can be combated by using data prefetchers, which hide access time by predicting the next memory access and loading it into a cache before it's required. Unfortunately, current prefetchers are only useful for memory accesses with known regular patterns, such as walking arrays, and are ineffective for those that use irregular patterns over application-specific data structures. In this work, we demonstrate prefetchers that are tailor-made for applications, even if they have irregular memory accesses. This is achieved through program slicing, a static analysis technique that extracts the memory structure of the input code and automatically constructs an application-specific prefetcher. Both our analysis and tool are fully automated and implemented as a new compiler flag in LegUp, an open source HLS tool. In this work we create a theoretical model showing that speedup must be between 1x and 2x, we also evaluate five benchmarks, achieving an average speedup of 1.38x with an average resource overhead of 1.15x.

Users of heterogeneous computing systems face two problems: first, in understanding the trade-off relationships between the observable characteristics of their applications, such as latency and quality of the result, and second, how to exploit knowledge of these characteristics to allocate work to distributed computing platforms efficiently. A domain specific approach addresses both of these problems. By considering a subset of operations or functions, models of the observable characteristics or domain metrics may be formulated in advance, and populated at run-time for task instances. These metric models can then be used to express the allocation of work as a constrained integer program. These claims are illustrated using the domain of derivatives pricing in computational finance, with the domain metrics of workload latency and pricing accuracy. For a large, varied workload of 128 Black-Scholes and Heston model-based option pricing tasks, running upon a diverse array of 16 Multicore CPUs, GPUs and FPGAs platforms, predictions made by models of both the makespan and accuracy are generally within 10 percent of the run-time performance. When these models are used as inputs to machine learning and MILP-based workload allocation approaches, a latency improvement of up to 24 and 270 times over the heuristic approach is seen.

C-based HLS tools continue to improve in analysis and optimisation, but are still restricted to a subset of C functionality. A C language feature missing from all common HLS tools is recursion, which makes it difficult and time consuming to write many types of programs in HLS. This paper presents a technique for implementing recursion as an Embedded Domain Specific Language (EDSL) in C++, utilising the C++ front-end of a HLS compiler to build the state machines and stacks, while ensuring the code presented to the back-end is completely synthesisable. While the EDSL is not pure C, it provides a user-friendly language that can be trivially translated from a recursive C program, and can contain calls to plain C for compute-intensive leaf functions. HLSRecurse is a platform independent library that allows the same program to be compiled using g++, clang, Legup, or Vivado HLS, and have the same execution semantics. The performance of HLSRecurse is evaluated in software and hardware using three micro-benchmarks of the underlying state-machine builder, and five practical examples of real recursive programs including a Sudoku solver, Strassen multiplication, and adaptive Monte-Carlo integration. We show that for Vivado HLS the DSL provides the same area-time product as manually converted programs, while in Legup the DSL increases the area-time product by 1.5×.

Soft-error detection in FPGAs typically requires replication, doubling the required area. We propose an approach which distinguishes between tolerable errors in data-flow, such-as arithmetic, and intolerable errors in control-flow, such as branches and their data-dependencies. This approach is demonstrated in a new high-level synthesis compiler pass called StitchUp, which precisely identifies the control critical parts of the design, then automatically replicates only that part. We applied StitchUp to the CHStone benchmark suite and performed exhaustive hardware fault injection in each case, finding that all control-flow errors were detected while only requiring 1% circuit area overhead in the best case.

Restricted Boltzmann Machines (RBMs) are widely used in modern machine learning tasks. Existing implementations are limited in network size and training throughput by available DSP resources. In this work we propose a new algorithm and architecture for FPGAs called dropout-RBM (dRBM) system. Compared to the state-of-art design methods on the same FPGA, dRBM with a dropout rate 0.5 doubles the maximum affordable network size using only half of DSP and BRAM resources. This is achieved by an application of a technique called dropout, which is a relatively new method used to avoid overfitting of data. Here we instead apply dropout as a technique for reducing the required DSPs and BRAM resources, while also having the side-effect of increasing robustness of training. Also to improve the processing throughput, we propose a multi-mode matrix multiplication module that maximizes the DSP efficiency. For the MNIST classificationbenchmark, a Stratix IV EP4SGX530 FPGA running dRBM is 34x faster than a single-precision Matlab implementation running on Intel i7 2.9GHz CPU.

Abstract Data Types (ADTs) such as dictionaries and lists are essential for many embedded computing applications such as network stacks. However, in heterogeneous systems, code using ADTs can usually only run in CPUs, because components written in HLS do not support dynamic data structures. HLS tools cannot be used to synthesise dynamic data structures directly because the use of pointers is very restricted, such as not supporting pointers to pointers or pointer casting. Consequently, it is unclear what the API should look like and how to express dynamic data structures in HLS so that the tools can compile them. We propose SynADT, which consists of a methodology and a benchmark. The methodology provides classic data structures (linked lists, binary trees, hash tables and vectors) using relativeaddresses instead of pointers in Vivado HLS. The benchmark can be used to evaluate the performance of data structures in HLS, ARM processors and soft processors such as MicroBlaze, CPUs can utilise either the default C memory allocator or a hardware memory allocator. We evaluate the data structures in a Zynq FPGA demonstrating scaling to approximately 10MB memory usage and 1M data items. With a workload that utilises 10MB memory, the HLS data structures operating at 150MHz are on average 1.35× faster than MicroBlaze data structures operating at 150MHz with the default C allocator and 7.97× slower than ARM processor data structures operating at 667MHz with the default C allocator.

Users in many domains, including urban planning, transportation, and environmental science want to execute analytical queries over continuously updated spatial datasets. Current solutions for large-scale spatial query processing either rely on extensions to RDBMS, which entails expensive loading and indexing phases when the data changes, or distributed map/reduce frameworks, running on resource-hungry compute clusters. Both solutions struggle with the sequential bottleneck of parsing complex, hierarchical spatial data formats, which frequently dominates query execution time. Our goal is to fully exploit the parallelism offered by modern multi-core CPUs for parsing and query execution, thus providing the performance of a cluster with the resources of a single machine. We describe AT-GIS, a highly-parallel spatial query processing system that scales linearly to a large number of CPU cores. AT-GIS integrates the parsing and querying of spatial data using a new computational abstraction called associative transducers (ATs). ATs can form a single data-parallel pipeline for computation without requiring the spatial input data to be split into logically independent blocks. Using ATs, AT-GIS can execute, in parallel, spatial query operators on the raw input data in multiple formats, without any pre-processing. On a single 64-core machine, AT-GIT provides 3x the performance of an 8-node Hadoop cluster with 192 cores for containment queries, and 10x for aggregation queries.

A barrier to wide-spread use of Field Programmable Gate Arrays (FPGAs) has been the complexity of programming, but recent advances in High-Level Synthesis (HLS) have made it possible for non-experts to easily create floating-point numerical accelerators from C-like code. However, HLS users are limited to the set of numerical primitives provided by HLS vendors and designers of floating-point IP cores, and cannot easily implement new fast or accurate numerical primitives. This paper presents a method for automatically creating high-performance pipelined floating-point function approximations, which can be integrated as IP cores into numerical accelerators, whether derived from HLS or traditional design methods. Both input and output are floating-point, but internally the function approximator uses fixed-point polynomial segments, guaranteeing a faithfully rounded output. A robust and automated non-uniform segmentation scheme is used to segment any twice-differentiable input function and produce platform-independent VHDL. The approach is demonstrated across ten functions, which are automatically generated then placed and routed in Xilinx devices. The method provides a 1.1x-3x improvement in area over composite numerical approximations, while providing similar performance and significantly better relative error.

Genetic Algorithms (GAs) are a class of numerical and combinatorial optimisers which are especially useful for solving complex non-linear and non-convex problems. However, the required execution time often limits their application to small-scale or latency-insensitive problems, so techniques to increase the computational efficiency of GAs are needed. FPGA-based acceleration has significant potential for speeding up genetic algorithms, but existing FPGA GAs are limited by the generational approaches inherited from software GAs. Many parts of the generational approach do not map well to hardware, such as the large shared population memory and intrinsic loop-carried dependency. To address this problem, this paper proposes a new hardware-oriented approach to GAs, called Pipelined Genetic Propagation (PGP), which is intrinsically distributed and pipelined. PGP represents a GA solver as a graph of loosely coupled genetic operators, which allows the solution to be scaled to the available resources, and also to dynamically change topology at run-time to explore different solution strategies. Experiments show that pipelined genetic propagation is effective in solving seven different applications. Our PGP design is 5 times faster than a recent FPGA-based GA system, and 90 times faster than a CPU-based GA system.

Devices with tightly coupled CPUs and FPGA logic allow for the implementation of heterogeneous applications which combine multiple components written in hardware and software languages, including first-party source code and third-party IP. Flexibility in component relationships is important, so that the system designer can move components between software and hardware as the application design evolves. This paper presents a system-level type system and linker, which allows functions in software and hardware components to be directly linked at link time, without requiring any modification or recompilation of the components. The type system is designed to be language agnostic, and exhibits higher-order features, to enables design patterns such as notifications and callbacks to software from within hardware functions. We demonstrate the system through a number of case studies which link compiled software against synthesised hardware in the Xilinx Zynq platform.

FPGA systems are moving towards a system-on-chip model, both at the architectural level and in the development tools. Developers are able to design and implement IP using a mixture of HLS, RTL, and software, then integrate them with third-party IP cores and hardened CPUs using one or more shared memory buses. This allows functionality to be easily connected together at the bus level, but accessing IP core functionality requires designers to support each component's protocol and co-ordinate hardware from a CPU. This paper presents a protocol called PushPush, which allows HLS, RTL, and software components to expose functionality as strongly typed functions, and allows any component to access functions exposed by any other component in the system. The protocol is designed for maximum efficiency in memory buses such as AXI and Avalon, reducing each function call to two burst writes delivering both data and control, minimising bus traffic and eliminating the need for global polling or interrupt delivery. We demonstrate this approach in a Zynq environment, using components written in C++ (ARM/Linux), C (Microblaze), Vivado HLS (Logic), and Verity (Logic). We show that any component can call functions exposed by any other component, without knowing where or how that function is located. Performance is at least 1 million function calls/sec between any pair of components, and rises to 4 million function calls/sec between pairs of Vivado HLS components.

The bilevel optimisation problem (BLP) is a subclass of optimisation problems in which one of the constraints of an optimisation problem is another optimisation problem. BLP is widely used to model hierarchical decision making where the leader and the follower correspond to the upper level and lower level optimisation problem, respectively. In BLP, the optimal solutions to the lower level optimisation problem are the feasible solutions to the upper level problem, which makes it particularly difficult to solve. This paper proposes a novel hardware architecture known as Recursive Pipelined Genetic Propagation (RPGP), to solve BLP efficiently on FPGA. RPGP features a graph of genetic operation nodes which can be scaled to exploit hardware resources. In addition, the topology of the RPGP graph can be changed at run-time to escape from local optima. We evaluate the proposed architecture on an Altera Stratix-V FPGA, using a benchmark bilevel optimisation problem set. Our experimental results show that RPGP can achieve a significant speed-up against previous work.

System-on-chip designs are increasingly complex and dynamic, with many IP cores, CPUs and off-chip Memories interconnected via shared buses. Static allocation of RAM resources requires designers to analyse the memory needs of each component, which can lead to poor memory efficiency, and is infeasible in a dynamically changing system. Dynamic memory allocation is one solution to this problem, but is usually only supported in software. We propose SysAlloc, a hardware-based dynamic memory allocation scheme for heterogeneous systems, which allows software and hardware to access a shared memory allocator, and allows dynamic memory allocation in the absence of software. Our allocation protocol is accessible to any client which can perform memory reads and writes over a shared bus, including software, RTL, and HLS clients, and can scale at run-time to any number of active clients. In contrast to existing designs, the proposed allocator can manage DDR-scale memories while having constant FPGA resource utilisation. We evaluate SysAlloc's protocol and memory manager in a Zynq system with both software and hardware clients, demonstrating scaling to 15 concurrent clients, and a peak system allocation rate of 1.36 million allocations/second when managing 128MB of DDR for 4 clients.

Gaussian random number generators (GRNGs) are an important component in parallel Monte Carlo simulations using FPGAs, where tens or hundreds of high-quality Gaussian samples must be generated per cycle using very few logic resources. This article describes the Table-Hadamard generator, which is a GRNG designed to generate multiple streams of random numbers in parallel. It uses discrete table distributions to generate pseudo-Gaussian base samples, then a parallel Hadamard transform to efficiently apply the central limit theorem. When generating 64 output samples, the Table-Hadamard requires just 130 slices per generated sample, which is a third of the resources needed by the next best technique, while still providing higher statistical quality.

This work demonstrates the capabilities of a high-level synthesis tool-chain that allows the compilation of higher order functional programs to gate-level hardware descriptions. Higher order programming allows functions to take functions as parameters. In a hardware context, the latency-insensitive interfaces generated between compiled modules enable late-binding with libraries of pre-existing functions at the place-and-route compilation stage. We demonstrate the completeness and utility of our approach using a case study; a recursive k-means clustering algorithm. The algorithm features complex data-dependent control flow and opportunities to exploit both coarse and fine-grained parallelism.

Many types of stochastic algorithms, such as Monte-Carlo simulations and Bit-Error-Rate testing, require very high run-times and are often trivially parallelisable, so are natural candidates for execution using FPGAs. However, the applications are reliant on Gaussian Random Number Generators (GRNGs) with good statistical properties, as very small biases over trillions of random samples can lead to incorrect results. Previous hardware GRNGs have focussed on area-efficient algorithms to produce Gaussian distributions under idealised assumptions, but do not make statements about the actual distribution coming out of real fixed-point hardware. In this paper, we present a new type of GRNG called a Piecewise-CLT, which uses a weighted blend of many small smooth distributions to approximate the Gaussian. By adjusting the weights, it is possible to directly target the distribution of the Gaussian, resulting in a circuit with an exactly quantified output distribution. Three members of the PwCLT family are presented, ranging from medium-area with good quality, up to a generator providing guaranteed statistical accuracy out to 12-sigma. We also show that PwCLT provides a better area-accuracy tradeoff than all existing high-speed scalar FPGA GRNGs, and can provide extremely high levels of statistical quality not possible in any previous methods.

Modern computer systems are formed from many interacting systems and heterogeneous components, that face increasing constraints on performance, power consumption, and temperature. Such systems have complex run-time dynamics which cannot easily be predicted or modelled at design-time, creating a need for online dynamic systems management. The Heartbeats API is a popular open source project which provides a standardised way for applications to monitor and publish their progress in multi-core CPU systems, but it does not allow hardware components to be monitored or to observe the progress of other components of the system. This paper presents work which extends the capacities of the Heartbeats API across the whole system while maintaining backwards compatibility with the legacy software API. To demonstrate the framework's capabilities an Autonomous Underwater Vehicle (AUV) case study is explored, where a power-aware HW/SW image processing application is implemented on a reconfigurable SoC and an approximate energy saving of 30% is observed for an example input video. Current progress is also discussed on some applications which build upon the framework, including an CubeSat experiment for an Adaptive Heterogeneous FDIR system that will launch in 2016 by the European Space Agency.

FPGAs normally have numerous independent memory banks that can be accessed simultaneously, potentially offering a very large memory bandwidth. Adopting a suitable application-based memory partitioning strategy is thus vital to take full advantage of the memory architecture. In addition to improving the potential memory bandwidth, partitioning also affects the area complexity of the generated system because the required steering logic depends on the partitioning scheme. This work describes the area implications of a lattice-based memory partitioning technique in the context of high-level synthesis for FPGAs. Experimental results with a commercial HLS tool show that the proposed partitioning technique improves area efficiency compared to alternative approaches.

Parallel genetic algorithms (pGAs) are a variant of genetic algorithms which can promise substantial gains in both efficiency of execution and quality of results. pGAs have attracted researchers to implement them in FPGAs, but the implementation always needs large human effort. To simplify the implementation process and make the hardware pGA designs accessible to potential non-expert users, this paper proposes a general-purpose framework, which takes in a high-level description of the optimisation target and automatically generates pGA designs for FPGAs. Our pGA system exploits the two levels of parallelism found in GA instances and genetic operations, allowing users to tailor the architecture for resource constraints at compile-time. The framework also enables users to tune a subset of parameters at run-time without time-consuming recompilation. Our pGA design is more flexible than previous ones, and has an average speedup of 26 times compared to the multi-core counterparts over five combinatorial and numerical optimisation problems. When compared with a GPU, it also shows a 6.8 times speedup over a combinatorial application.

High Level Synthesis (HLS) tools for Field Programmable Gate Arrays (FPGAs) have made considerable progress, and are now sufficiently mature that a novice developer could create functionally correct implementation with limited understanding of the target hardware. In this case study, a novice developer considers a benchmark of financial problems for implementation upon FPGA via HLS. This novice starts by extending an existing implementation for a CPU or GPU using tools such as Xilinx's Vivado HLS, the Altera OpenCL SDK or Maxeler's MaxCompiler. When their direct source code translation inevitably didn't meet performance expectations, this developer then applies optimisations such as exploiting task or pipeline parallelism as well as C-slowing. When a combination of these optimisations are considered for a range of devices and process technologies, an acceleration of up to 220 times is achieved using these tools, the sort of acceleration expected of custom architectures. Compared to the 31 times improvement shown by an optimised Multicore CPU implementation, the 60 times improvement by a GPU and 207 times by a Xeon Phi, these results suggest that HLS is indeed ready for industrial adoption.

This paper presents a novel reconfigurable hardware accelerator for the pricing of American options using the binomial-tree model. The proposed architecture exploits both pipeline and coarse-grain parallelism in a highly efficient and scalable systolic solution, designed to exploit the large numbers of DSP blocks in modern architectures. The architecture can be tuned at compile-time to match user requirements, from dedicating the entire FPGA to low latency calculation of a single option, to high throughput concurrent evaluation of multiple options. On a Xilinx Virtex-7 xc7vx980t FPGA this allows a single option with 768 time steps to be priced with a latency of less than 22 micro-seconds and a pricing rate of more than 100 K options/sec. Compared to the fastest previous reconfigurable implementation of concurrent option evaluation, we achieve an improvement of 65 x in latency and 9x in throughput with a value of 10.7 G nodes/sec, on a Virtex-4 xc4vsx55 FPGA.

Gaussian Random Number Generators (GRNGs) are an important component in parallel Monte-Carlo simulations using FPGAs, where tens or hundreds of high-quality Gaussian samples must be generated per cycle using very few logic resources. This paper describes the Table-Hadamard generator, which is a GRNG designed to generate multiple streams of random numbers in parallel. It uses discrete table distributions to generate pseudo-Gaussian base samples, then a parallel Hadamard transform to efficiently apply the central limit theorem. When generating 64 output samples the TableHadamard requires just 100 slices per generated sample, a quarter the resources of the next best technique, while providing higher statistical quality.

Real time systems must guarantee tasks can be completed by a given deadline. Typically they are designed around the worst case execution time (WCET) of tasks in the system. In general this creates systems with excess slack compared to the average case. Since, real time systems are often embedded devices which are typically battery operated, developing systems with large amounts of slack is undesirable because more slack means more energy usage. There exist scheduling methods that try to adapt to the current environment, for example adaptive reservation scheduling, which assigns a dynamic fraction of the computational resources to each process. However these and more advanced scheduling techniques are rarely adopted in practice due to their high computational overhead. My research hypothesis is that the overheads of complex scheduling and power saving techniques in real time systems can be reduced through developing a coprocessor in the FPGA fabric. Recent developments in reconfigurable device technology include the introduction of new hybrid FPGA/CPU chips, such as the Xilinx Zynq extensible processing platform, where an ARM core is coupled to an FPGA fabric using an AXI bus. By locating the FPGA and CPU on the same die it possible to obtain low-latency power-efficient communication between user logic in the FPGA and tasks on the CPU. This paper presents my preliminary work, which uses a software application with real time deadlines, and creates a controller in the FPGA fabric to dynamically scale the operating frequency of the CPUs, while still guaranteeing that the deadlines can be met. This coprocessor is totally agnostic to the software running on the CPU and provided that some measure of slackness, which is the deadline period subtracted from the execution time, can be obtained it will be able to scale the frequency in a safe manner and reduce dynamic power consumption.

Simulation of chemical systems allows bio-chemists to understand how the interactions of individual molecules can lead to cellular and organism level behaviour. When the concentration of moleculesis very small, it is necessary to model every single chemical interaction in a Monte-Carlo simulation, presenting a huge computational burden. This paper presents a new fully pipelined architecture for chemical simulation, which avoids the traditional approach of optimising for minimum operation count, and instead optimises for throughput and parallelism. We show that even though this leads to a higher asymptotic operation count per simulation step, it allows for a much greater degree of spatial and pipeline parallelism, and the increased area is offset by much greater throughput. The new architecture is implemented in a Virtex-6 SX475T and can sustain a rate of over 1 billion reactions per second for problems with less than 64 reactions. Compared against existing chemical simulators on small to medium size chemical models, the new architecture is 30-100 times faster than a commercial software simulator running on an 8-core 3.4GHz Core i7, and 12-30 times faster than the best existing FPGA simulators.

This paper presents the Forward Financial Framework (F3), an application framework for describing and implementing forward looking financial computations on high performance, heterogeneous platforms. F3allows the computational finance problem specification to be captured precisely yet succinctly, then automatically creates efficient implementations for heterogeneous platforms, utilising both multi-core CPUs and FPGAs. The automatic mapping of a high-level problem description to a low-level heterogeneous implementation is possible due to the domain-specific knowledge which is built in F3, along with a software architecture that allows for additional domain knowledge and rules to be added to the framework. Currently the system is able to utilise domain-knowledge of the run-time characteristics of pricing tasks to partition pricing problems and allocate them to appropriate compute resources, and to exploit relationships between financial instruments to balance computation against communication. The versatility of the framework is demonstrated using a benchmark of option pricing problems, where F3achieves comparable speed and energy efficiency to external manual implementations. Further, the domain-knowledge guided partitioning scheme suggests a partitioning of subtasks that is 13% faster than the average, while exploiting domain dependencies to reduce redundant computations results in an average gain in efficiency of 27%.

In online social networking, network monitoring and financial applications, there is a need to query high rate streams of XML data, but methods for executing individual XPath queries on streaming XML data have not kept pace with multicore CPUs. For data-parallel processing, a single XML stream is typically split into well-formed fragments, which are then processed independently. Such an approach, however, introduces a sequential bottleneck and suffers from low cache locality, limiting its scalability across CPU cores. We describe a data-parallel approach for the processing of streaming XPath queries based on pushdown transducers. Our approach permits XML data to be split into arbitrarilysized chunks, with each chunk processed by a parallel automaton instance. Since chunks may be malformed, our automata consider all possible starting states for XML elements and build mappings from starting to finishing states. These mappings can be constructed independently for each chunk by different CPU cores. For streaming queries from the XPathMark benchmark, we show a processing throughput of 2.5 GB/s, with near linear scaling up to 64 CPU cores.

Field-programmable gate array (FPGA) optimized random number generators (RNGs) are more resource-efficient than software-optimized RNGs because they can take advantage of bitwise operations and FPGA-specific features. However, it is difficult to concisely describe FPGA-optimized RNGs, so they are not commonly used in real-world designs. This paper describes a type of FPGA RNG called a LUT-SR RNG, which takes advantage of bitwise xor operations and the ability to turn lookup tables (LUTs) into shift registers of varying lengths. This provides a good resource-quality balance compared to previous FPGA-optimized generators, between the previous high-resource high-period LUT-FIFO RNGs and low-resource low-quality LUT-OPT RNGs, with quality comparable to the best software generators. The LUT-SR generators can also be expressed using a simple C++ algorithm contained within this paper, allowing 60 fully-specified LUT-SR RNGs with different characteristics to be embedded in this paper, backed up by an online set of very high speed integrated circuit hardware description language (VHDL) generators and test benches.

The multivariate Gaussian distribution is used to model random processes with distinct pair-wise correlations, such as stock prices that tend to rise and fall together. Multivariate Gaussian vectors with length n are usually produced by first generating a vector of n independent Gaussian samples, then multiplying with a correlation inducing matrix requiring O(n2) multiplications. This paper presents a method of generating vectors directly from the uniform distribution, removing the need for an expensive scalar Gaussian generator, and eliminating the need for any multipliers. The method relies only on small read-only memories and adders, and so can be implemented using only logic resources (lookup-tables and registers), saving multipliers, and block-memory resources for the numerical simulation that the multivariate generator is driving. The new method provides a ten times increase in performance (vectors/second) over the fastest existing field-programmable gate array generation method, and also provides a five times improvement in performance per resource over the most efficient existing method. Using this method, a single 400-MHz Virtex-5 FPGA can generate vectors ten times faster than an optimized implementation on a 1.2-GHz graphics processing unit, and a hundred times faster than vectorized software on a general purpose quad core 2.2-GHz processor.

In many application domains, data are represented using large graphs involving millions of vertices and billions of edges. Graph exploration algorithms, such as breadth-first search (BFS), are largely dominated by memory latency and are challenging to process efficiently. In this paper, we present a reconfigurable hardware methodology for efficient parallel processing of large-scale graph exploration problems. Our methodology is based on a reconfigurable hardware architecture which decouples computation and communication while keeping multiple memory requests in flight at any given time, taking advantage of the hardware capabilities of both FPGAs and the parallel memory subsystem. To validate our methodology, we provide a detailed design description of the Breadth-First Search algorithm on an FPGA-based high performance computing system. Using graph data based on the power-law graphs found in real-word problems, we are able to achieve performance results that are superior to those of high performance multi-core systems in the recent literature for large graph instances, and a throughput in excess of 2.5 billion traversed edges per second on RMAT graphs with 16 million vertices and over a billion edges. Using four Virtex-5 LX330 FPGAs based on 65nm technology and running at 75MHz, our BFS design achieves more than twice the speed of a 32-core Xeon X7560 based on 45nm technology and running at 2.26GHz.

This paper introduces a novel mixed precision methodology applicable to any Monte Carlo (MC) simulation. It involves the use of data-paths with reduced precision, and the resulting errors are corrected by auxiliary sampling. An analytical model is developed for a reconfigurable accelerator system with a field-programmable gate array (FPGA) and a general purpose processor (GPP). Optimisation based on mixed integer geometric programming is employed for determining the optimal reduced precision and optimal resource allocation among the MC data-paths and correction datapaths. Experiments show that the proposed mixed precision methodology requires up to 11 % additional evaluations while less than 4 % of all the evaluations are computed in the reference precision; the resulting designs are up to 7.1 times faster and 3.1 times more energy efficient than baseline double precision FPGA designs, and up to 163 times faster and 170 times more energy efficient than quad-core software designs optimised with the Intel compiler and Math Kernel Library. Our methodology also produces designs for pricing Asian options which are 4.6 times faster and 5.5 times more energy efficient than NVIDIA Tesla C2070 GPU implementations.

This paper proposes a highly parallel and scalable reconfigurable design for the All-Pairs Shortest-Paths (APSP) algorithm for very sparse networks. Our work is motivated by a computationally intensive bioinformatics application that employs this memory-latency bound algorithm. The proposed design methodology takes advantage of distributed on-chip memory resources of modern FPGAs to reduce accesses to high-latency off-chip memories. We develop design optimisations that yield different FPGA configurations which are selected at run time based on the input graph data. Using human brain network data, we are able to achieve performance results superior to those from multi-core CPU and GPU, while attaining linear scaling over the number of processors introduced. Our FPGA-based APSP design is over 10 times faster than a quad-core CPU implementation and 2-5 times faster than an AMD Cypress GPU implementation.

This paper provides a novel way of trading increased resource utilisation for decreased latency when computing a single Discrete Fourier Transform on the FPGA. Analysis conducted on the Cooley-Tukey FFT optimisation shows that it increases the number of operations in the critical path of the transform computation. Consequentially an algorithm is proposed which allows control over the degree to which the Cooley-Tukey optimisation is utilised, trading between resource utilisation and absolute latency. The resource utilisation and latency results for the MyHDL implementation of the proposed algorithm upon the Rhino platform are provided which demonstrate that a practical Pareto curve has been established for a variety of dataset sizes. This implementation is also compared to Xilinx's FFT IP core, providing 14% better latency performance than the manufacturer's implementation albeit at a greater resource cost.

This paper demonstrates a novel optimisation methodology to adjust stencil based numerical procedures from the algorithm level, so as to reduce not only the amount of hardware resource consumption per kernel but also the amount of computation required to achieve desired result accuracy, when mapping the algorithm to reconfigurable hardware using dynamic constant reconfiguration. As a result, less area is needed to support run-time reconfiguration, and less computational steps are required in the numerical procedure to obtain a result with given error tolerance. We analyse one thousand fixed point implementations on a Virtex-6 XC6VLX760 FPGA for randomly generated option pricing problems, which are representative of industrial computation. When comparing optimised implementations to the un-optimised ones, the reconfiguration area upper bound is reduced by 22%; the average number of computational steps is reduced by 23%; and the area-computation-time product is reduced by 40%; while the numerical errors of the results are kept below the error tolerant level used in industry.

This paper presents a novel parallel architecture for accelerating quadrature methods used for pricing complex multi-dimensional options, such as discrete barrier, Bermudan and American options. We explore different designs of the quadrature evaluation core including optimized pipelined hardware designs in reconfigurable logic and a compute unified device architecture (CUDA)-based graphics processing unit (GPU) design. A parametrizable automated system is presented for generating hardware quadrature evaluation cores with an arbitrary number of dimensions. The performance and energy consumption of field-programmable gate arrays (FPGAs), GPUs, and central processing units (CPUs) are compared across different number of dimensions and precisions. Our evaluation shows that the 100 MHz Virtex-4 xc4vlx160 FPGA design is 4.6 times faster and 25.9 times more energy efficient than a multi-threaded optimized software implementation running on a Xeon W3504 dual-core CPU. It is also 2.6 times faster and 25.4 times more energy efficient than a GPU with comparable silicon process technology.

A number of different numerical methods for accelerating financial option pricing using FPGAs have recently been investigated, such as Monte-Carlo, finite-difference, quadrature, and binomial trees. However, these papers only compare acceleration of each method against the same method in software, and do not consider a more important practical question, which is to identify the method that provides the best FPGA performance for a given option pricing application, regardless of raw speed-up over software. This paper proposes a framework for comparing the performance of numerical option pricing methods using FPGAs, taking into account both speed (time to solution) and accuracy (quality of solution), and examines how the speed-accuracy trade-off curve varies for each method. We apply the framework to European and American option pricing problems using Virtex-4 parts, and show that the quadrature solver converges fastest for both European and American options, and is also the most accurate in terms of root mean squared error for European options. However, when very accurate American results are needed the finite-difference solver is the most efficient method. Our results also show that the Monte-Carlo solver is at least 100 times less accurate in log scale than those based on other pricing methodologies, this drawback outweighs its benefit of having large raw speed-ups found in previous papers.

Explicit finite difference method is widely used in finance for pricing many kinds of options. Its regular computational pattern makes it an ideal candidate for acceleration using reconfigurable hardware. However, because the corresponding hardware designs must be optimised both for the specific option and for the target platform, it is challenging and time consuming to develop designs efficiently and productively. This paper presents a unifying framework for describing and automatically implementing financial explicit finite difference procedures in reconfigurable hardware, allowing parallelised and pipelined implementations to be created from high-level mathematical expressions. The proposed framework is demonstrated using three option pricing problems. Our results show that an implementation from our framework targeting a Virtex-6 device at 310MHz is more than 24 times faster than a software implementation fully optimised by the Intel compiler on a four-core Xeron CPU at 2.66GHz. In addition, the latency of the FPGA solvers is up to 90 times lower than the corresponding software solvers.

In many application domains, data are represented using large graphs involving millions of vertices and edges. Graph analysis algorithms, such as finding short paths and isomorphic subgraphs, are largely dominated by memory latency. Large cluster-based computing platforms can process graphs efficiently if the graph data can be partitioned, and on a smaller scale partitioning can be used to allocate graphs to low-latency on-chip RAMs in reconfigurable devices. However, there are many graph classes, such as scale-free social networks, which lack the locality to make partitioning graph data an efficient solution to the latency problem and are far too large to fit in on-chip RAMs and caches. In this paper, we present a framework for reconfigurable hardware acceleration of these large-scale graph problems that are difficult to partition and require high-latency off-chip memory storage. Our reconfigurable architecture tolerates off-chip memory latency by using a memory crossbar that connects many parallel identical processing elements to shared off-chip memory, without a traditional cached memory hierarchy. Quantitative comparison between the software and hardware performance of a graphlet counting case-study shows that our hardware implementation outperforms a quad-core software implementation by 10 times for large graphs. This speedup includes all software and IO overhead required, and reduces execution time for this common bioinformatics algorithm from about 2 hours to just 12 minutes. These results demonstrate that our methodology for accelerating graph algorithms is a promising approach for efficient parallel graph processing.

The multi-variate Gaussian distribution is used to model random processes with distinct pair-wise correlations, such as stock prices that tend to rise and fall together. Multi-variate Gaussian vectors with length n are usually produced by first generating a vector of n independent Gaussian samples, then multiplying with a correlation inducing matrix requiring 0(n2) multiplications. This paper presents a method of generating vectors directly from the uniform distribution, removing the need for an expensive scalar Gaussian generator, and eliminating the need for any multipliers. The method relies only on small ROMs and adders, and so can be implemented using just logic resources (LUTs and FFs), saving DSP and block-RAM resources for the numerical simulation that the multi-variate generator is driving. The new method provides a ten times increase in raw performance over the fastest existing FPGA generation method, and also provides a five times improvement in performance per resource over the most efficient existing method. Using this method a single 400MHz Virtex-5 FPGA can generate vectors ten times faster than an optimised CUDA implementation on a 1.2GHz GPU, and a hundred times faster than SIMD optimised software on a quad core 2.2GHz CPU.

FPGA-optimised Random Number Generators (RNGs) are more resource efficient than software-optimised RNGs, as they can take advantage of bit-wise operations and FPGA-specific features. However, it is difficult to concisely describe FPGA-optimised RNGs, so they are not commonly used in real-world designs. This paper describes a new type of FPGA RNG called a LUT-SR RNG, which takes advantage of bit-wise XOR operations and the ability to turn LUTs into shift-registers of varying lengths. This provides a good resource-quality balance compared to previous FPGA-optimised generators, between the previous high-resource high-quality LUT-FIFO RNGs and low-resource low-quality LUT-OPT RNGs. The LUT-SR generators can also be expressed using a simple C++ algorithm contained within the paper, allowing 60 fully-specified LUT-SR RNGs with different characteristics to be embedded in the paper, backed up by an online set of VHDL generators and test-benches.

Exotic options are financial derivatives which have complex features including path-dependency. These complex features make them difficult to price, as only computationally intensive Monte-Carlo methods can provide accurate prices. This paper proposes an FPGA-accelerated control variate Monte-Carlo (CVMC) framework for pricing exotic options. An optimised implementation of arithmetic Asian option pricing under this framework in a Virtex-5 xc5vlx330t FPGA at 200 MHz is 24 times faster than a multi-threaded software implementation on a Xeon E5420 at 2.5 GHz; it is also 2.4 times faster than the Tesla C1060 GPU at 1.3 GHz.

This paper provides the first comparison of performance and energy efficiency of high productivity computing systems based on FPGA (Field-Programmable Gate Array) and GPU (Graphics Processing Unit) technologies. The search for higher performance compute solutions has recently led to great interest in heterogeneous systems containing FPGA and GPU accelerators. While these accelerators can provide significant performance improvements, they can also require much more design effort than a pure software solution, reducing programmer productivity. The CUDA system has provided a high productivity approach for programming GPUs. This paper evaluates the High-Productivity Reconfigurable Computer (HPRC) approach to FPGA programming, where a commodity CPU instruction set architecture is augmented with instructions which execute on a specialised FPGA co-processor, allowing the CPU and FPGA to co-operate closely while providing a programming model similar to that of traditional software. To compare the GPU and FPGA approaches, we select a set of established benchmarks with different memory access characteristics, and compare their performance and energy efficiency on an FPGA-based Hybrid-Core system with a GPU-based system. Our results show that while GPUs excel at streaming applications, high-productivity reconfigurable computing systems outperform GPUs in applications with poor locality characteristics and low memory bandwidth requirements.

Monte-Carlo (MC) simulation is an effective tool for solving complex problems such as many-body simulation, exotic option pricing and partial differential equation solving. The huge amount of computation in MC makes it a good candidate for acceleration using hardware and distributed computing platforms. We propose a novel MC simulation framework suitable for a wide range of problems. This framework enables different hardware accelerators in a multi-accelerator heterogeneous cluster to work collaboratively on a single application. It also provides scheduling interfaces to adaptively balance the workload according to the cluster status. Two financial applications, involving asset simulation and option pricing, are built using this framework to demonstrate its capability and flexibility. A cluster with 8 Virtex-5 xc5vlx330t FPGAs and 8 Tesla C1060 GPUs using the proposed framework provides 44 times speedup and 19.6 times improved energy efficiency over a cluster with 16 AMD Phenom 9650 quad-core 2.4GHz CPUs for the GARCH asset simulation application. The Efficient Allocation Line (EAL) is proposed for determining the most efficient allocation of accelerators for either performance or energy consumption.

Artificial neural networks are a key tool for researchers attempting to understand and replicate the behaviour and intelligence found in biological neural networks. Software simulations offer great flexibility and the ability to select which aspects of biological networks to model, but are slow when operating on more complex biologically plausible models; while dedicated hardware solutions can be very fast, they are restricted to fixed models. This paper uses FPGAs to achieve a compromise between model complexity and simulation speed, such that a fully-connected network of 1024 neurons,based on the biologically plausible Izhikevich spiking model,can be simulated at 100 times real-time speed. The simulator is based on a re-usable interconnection architecture for storing synapse weights and calculating thalamic input, which makes use of the large number of available block-RAMs and huge amounts of fine-grain parallelism. The simulator achieves a sustained throughput of 2.26 GFlops in double-precision, and a single Virtex-5 xc5vlx330t without off-chip storage running at 133 MHz is 16 times faster than a 3 GHz Core2 CPU, and 1.1 times faster than a single-precision 1.2 GHz 30-core GPU.

This paper presents an architecture for FPGA acceleration of quadrature methods used for pricing complex options, such as discrete barrier, Bermudan, and American options. The architecture can be optimized for speed and power consumption by exploiting pipelining and parallelism to produce efficient implementations in reconfigurable logic. An optimised implementation using Graphics Processing Units (GPUs) is also developed, to provide a performance and efficiency comparison with an FPGA accelerator. Our 100 MHz FPGA implementation demonstrates a 32.8 times speedup over a software implementation running on a Pentium 4 3.6 GHz processor, and is 8.3 times more power efficient than a Tesla C1060 GPU with 240 processors at 1.3 GHz.

The future of high-performance computing is likely to rely on the ability to efficiently exploit huge amounts of parallelism. One way of taking advantage of this parallelism is to formulate problems as "embarrassingly parallel" Monte-Carlo simulations, which allow applications to achieve a linear speedup over multiple computational nodes, without requiring a super-linear increase in inter-node communication. However, such applications are reliant on a cheap supply of high quality random numbers, particularly for the three main maximum entropy distributions: uniform, used as a general source of randomness; Gaussian, for discrete-time simulations; and exponential, for discrete-event simulations. In this paper we look at four different types of platform: conventional multi-core CPUs (Intel Core2); GPUs (NVidia GTX 200); FPGAs (Xilinx Virtex-5); and Massively Parallel Processor Arrays (Ambric AM2000). For each platform we determine the most appropriate algorithm for generating each type of number, then calculate the peak generation rate and estimated power efficiency for each device.

This paper explores the application of reconfigurable hardware and graphics processing units (GPUs) to the acceleration of financial computation using the finite difference (FD) method. A parallel pipelined architecture has been developed to support concurrent valuation of independent options with high pricing throughput. Our FPGA implementation running at 106 MHz on an xc4vlx160 device demonstrates a speed up of 12 times over a Pentium 4 processor at 3.6 GHz in single-precision arithmetic; while the FPGA is 3.6 times slower than a Tesla C1060 240-Core GPU at 1.3 GHz, it is 9 times more energy efficient.

This article explores the application of reconfigurable hardware to the acceleration of financial computation using tree-based pricing models. Two parallel pipelined architectures have been developed for option valuation using binomial trees and trinomial trees, with support for concurrent evaluation of independent options to achieve high pricing throughput. Our results show that the tree-based models executing on a Virtex 4 field programmable gate array (FPGA) at 82.7 MHz with fixed-point arithmetic can run over 160 times faster than a Core2 Duo processor at 2.2 GHz. The FPGA implementation is two times faster than the nVidia Geforce 7900GTX processor with 24 pipelines at 650 MHz, and 27%--35% slower than the nVidia Geforce 8600GTS processor with 32 Pipelines at 1450 MHz. Our preliminary experiments also indicate that while an FPGA implementation can be slower than a GPU, it could be more efficient when power consumption is taken into account.

Monte-Carlo simulations and many other stochastic algorithms are almost ideal applications for FPGAs, as the huge amount of available parallelism allows deep pipelining without loop-carried dependencies and spatial scaling across large devices without shared resource bottlenecks. Another key advantage is that random number generation is very cheap (when compared to software), and can be tailored to meet the performance and quality needs of each application. However, in many cases this advantage is not exploited, either because an inefficient but simple to implement generator is chosen, or because a generator with properties that far exceed the needs of the application is used. This paper describes generators for the floating-point uniform and exponential distributions, which provide efficient resource usage, while remaining sufficiently simple to make them attractive to users.

The recent turmoil in global credit markets has demonstrated the need for advanced modeling of credit risk, which can take into account the effects of changing economic conditions on portfolios of loans. Such models are most easily described as Monte-Carlo simulations, but take too long to converge in software based simulators. This paper describes a hardware implementation of a loan portfolio simulator, which uses an event based model to describe changes both in prevailing economic conditions, and the behaviour of individual loans within the portfolio. Three distinct variants of the simulator are developed using transformations of the simulation algorithm, with each variant trading off area utilisation against the efficiency with which different event types can be processed. As the distribution of event types is highly dependent on the input data, each of the three variants provides the highest overall performance per FPGA for some set of input data characteristics. The hardware simulators are implemented using a Virtex-4 xc4vsx55 device running at 233 MHz in an RC2000 PCI card, and compared to four parallel software simulation threads running in a quad-core Pentium-4 Core2 at 2.4 GHz, providing a speed-up of between 60 and 100 times.

This paper introduces a method of constructing random numbergenerators from four of the basic primitives provided by FPGAs: Flip-Flips, Lookup-Tables, Shift Registers, and RAMs. The construction methodis designed to ensure maximum clock rates, while using the minimum of resources, and providing statistical quality at the level of the best software generators. In all platforms tested, the generators are limited in speed only by the clock distribution network or the maximum clockspeed of the underlying RAM primitives, using a platform independent VHDL description with no placement or other hints. The area utilisation is also very low, with a Virtex-5 generator requiring just one Block-RAMand 41 slices to produce 48Gb/s at 550MHz: over 14 times faster than the commonly used Mersenne-Twister RNG on an Opteron at 2.2GHz, while providing the same level of quality

The exponential distribution is a key distribution in many event-driven Monte-Carlo simulations, where it is used to model the time between random events in the system. This paper shows that each bit of a fixed-point exponential random variate is an independent Bernoulli variate, allowing the bits to be generated in parallel. This parallelism is of little interest in software, but is particularly well suited to FPGA generators, where huge numbers of independent uniform bits can be cheaply generated per cycle. Two generation architectures are developed using this approach, one using only logic elements to generate individual bits, and another using block-RAMs to group multiple bits together. The two methods are evaluated at three different quality-resource trade-offs, and when compared to existing methods have both higher performance and better resource utilisation. The method is particularly useful for very high performance applications, as extremely high-quality 36-bit exponential variates can be generated at 600MHz in the Virtex-4 architecture, using just 880 slices and no block-RAMs or embedded DSP blocks.

Monte-Carlo simulations are able to provide estimates of solutions for problems that are otherwise intractable, by examining the aggregate behaviour of large numbers of random simulations. Because these simulations are independent and embarrassingly parallel, FPGAs are increasingly being used to implement Monte-Carlo applications. However, as the number of simulation runs increases, the problem of accurately accumulating the aggregate statistics, such as the mean and variance, becomes very difficult. This paper examines three accumulation methods, adapting them for use in FPGA applications. In particular, we develop a mean and variance calculator based on cascading accumulators, which is able to process streams of floating-point data in one pass, while operating in fixed-point internally. This method has the advantage that it calculates the exact sample mean and an accurate numerically stable sample variance, while using few logic resources and providing performance to match commercial floating-point operators: clock rates of 434 MHz are achieved in Virtex-5, 1.46 times faster than a double-precision accumulator, while using one eighth of the resources.

The multivariate Gaussian distribution is often used to model correlations between stochastic time-series, and can be used to explore the effect of these correlations across N time-series in Monte-Carlo simulations. However, generating random correlated vectors is an O ( N 2 ) process, and quickly becomes a computational bottleneck in software simulations. This article presents an efficient method for generating vectors in parallel hardware, using N parallel pipelined components to generate a new vector every N cycles. This method maps well to the embedded block RAMs and multipliers in contemporary FPGAs, particularly as extensive testing shows that the limited bit-width arithmetic does not reduce the statistical quality of the generated vectors. An implementation of the architecture in the Virtex-4 architecture achieves a 500MHz clock-rate, and can support vector lengths up to 512 in the largest devices. The combination of a high clock-rate and parallelism provides a significant performance advantage over conventional processors, with an xc4vsx55 device at 500MHz providing a 200 times speedup over an Opteron 2.6GHz using an AMD optimised BLAS package. In a case study in Delta-Gamma Value-at Risk, an RC2000 accelerator card using an xc4vsx55 at 400MHz is 26 times faster than a quad Opteron 2.6GHz SMP.

Monte-Carlo simulations are used in many applications, such as option pricing and portfolio evaluation. Due to their high computational load and intrinsic parallelism, they are ideal candidates for acceleration using reconfigurable hardware. However, for maximum efficiency the hardware configuration must be parametrised to match the characteristics of both the simulation task and the platform on which it will be executed. This paper presents a methodology for the automatic implementation of Monte-Carlo simulations, starting from a high-level mathematical description of the simulation and resulting in an optimised hardware configuration for a given platform. This process automatically generates fully-pipelined hardware for maximum performance; it also maximises thread-level parallelism by instantiating multiple pipelines to optimise device utilisation. The configured hardware is used by an associated software component to execute simulations using run-time supplied parameters. The proposed methodology is demonstrated by five different Monte-Carlo simulations, including log-normal price movements, correlated asset Value-at-Risk calculation, and price movements under the GARCH model. Our results show that hardware implementations from our approach, on a Xilinx Virtex-4 XC4VSX55 FPGA at 150 MHz, can run on-average 80 times faster than software on a 2.66 GHz Xeon PC.

The multivariate Gaussian distribution models random processes as vectors of Gaussian samples with a fixed correlation matrix. Such distributions are useful for modelling real-world multivariate time-series such as equity returns, where the returns for businesses in the same sector are likely to be correlated. Generating random samples from such a distribution presents a computational challenge due to the dense matrix-vector multiplication needed to introduce the required correlations. This paper proposes a hardware architecture for generating random vectors, utilising the embedded block RAMs and multipliers found in contemporary FPGAs. The approach generates a new n dimensional random vector every n clock cycles, and has a raw generation rate over 200 times that of a single Opteron 2.2GHz using an optimised BLAS package for linear algebra computation. The generation architecture is an ideal source for both software simulations connected via high bandwidth connection, and for completely FPGA based simulations. Practical performance is explored in a case study in Delta-Gamma Value-at-Risk, where a standalone Virtex-4 xc4vsx55 solution at 400 MHz is 33 times faster than a quad Opteron 2.2GHz SMP. The FPGA solution also scales well for larger problem sizes, allowing larger portfolios to be simulation.

FPGAs have been successfully used to accelerate many computationally bound applications, such as high-performance Monte-Carlo simulations, but the amount of programmer effort required in development, testing, and tuning is also very high, requiring a new custom design for each application. This paper presents Contessa, a pure-functional continuation-based language for describing path-based Monte-Carlo simulations, and a completely automated method for turning platform-independent Contessa programs into high-performance hardware implementations. Our approach exploits the large degree of thread-based parallelism available in Monte-Carlo simulations, allowing data-dependent control-flow and loop-carried dependencies to be expressed, while retaining high-performance. The Contessa toolchain is evaluated using five different simulation kernels, in comparison to both software and manually described hardware. When compared to an existing FPGA implementation, Contessa requires a quarter of the Handel-C source-code length, and doubles the clock rate to over 300MHz while requiring a similar number of resources, and also provides a 35 times speedup over a C++ implementation using an Opteron 2.2GHz.

This paper presents a technique for efficiently generating random numbers from a given probability distribution. This is achieved by using a generic hardware architecture, which transforms uniform random numbers according to a distribution mapping stored in RAM, and a software approximation generator that creates distribution mappings for any given target distribution. This technique has many features not found in current non-uniform random number generators, such as the ability to adjust the target distribution while the generator is running, per-cycle switching between distributions, and the ability to generate distributions with discontinuities in the probability density function

This paper presents a hardware architecture for non-uniform random number generation, which allows the generator's distribution to be modified at run-time without reconfiguration. The architecture is based on a piecewise linear approximation, using just one table lookup, one comparison and one subtract operation to map from a uniform source to an arbitrary non-uniform distribution, resulting in very low area utilisation and high speeds. Customisation of the distribution is fully automatic, requiring less than a second of CPU time to approximate a new distribution, and around 1000 cycles to switch distributions at run-time. Comparison with Gaussian specific generators show that the new architecture uses less than half the resources, provides a higher sample rate, and retains statistical quality for up to 50 billion samples, but can also generate other distributions.

This paper presents a methodology and the results of implementing Monte-Carlo financial simulations in reconfigurable devices. Five different Monte-Carlo simulations are explored, including log-normal price movements, correlated asset value-at-risk calculation, and price movements under the GARCH model. Our results show that hardware implementations from our approach on a Xilinx Virtex-4 XC4VSX55 device run on-average 80 times faster than software on a 2.66GHz PC

This work explores the reconfigurable dataflow approach in producing efficient hardware pipelines for programs with loop-carry dependencies in nested loops. Reconfigurable dataflow combines static and dynamic scheduling, and employs tagged tokens to enable reassembling of results which can retire out of order. The effectiveness of this approach is illustrated using a fractal set generator and a Newton-Raphson root polisher: implementations targeting Xilinx Virtex and Virtex-II FPGAs can run up to 55 times faster than hardware pipelines developed using other methods, at the expense of a 50% increase in area.