How Many CPU Cores is an FPGA Worth? Lessons Learned from Accelerating String Sorting on a CPU-FPGA System

String sorting is a fundamental kernel of string matching and database index construction; yet, it has not been studied as extensively as fixed-length keys sorting. Because processing variable-length keys in hardware is challenging, it is no surprise that no hardware-accelerated string sorters have been proposed yet. In this paper, we present Parallel Hybrid Super Scalar String Sample Sort (pHS(5)) on Intel HARPv2, a heterogeneous CPU-FPGA system with a server-grade CPU. Our pHS(5) extends pS(5), the state-of-the-art string sorting algorithm for multi-core shared memory CPUs, by adding multiple processing elements (PEs) on the FPGA. Each PE accelerates one instance of the most effectively parallelizable among the dominant kernels of pS(5) by up to 33% compared to a single Intel Xeon Broadwell core despite a clock frequency that is 17 times slower. Furthermore, we extended the job scheduling mechanism of pS(5) to schedule the accelerable kernel not only among available CPU cores but also on our PEs, while retaining the complex high-level control flow and the sorting of the smaller data sets on the CPU. Overall, we accelerate the entire algorithm by up to 10% with respect to the 28-thread software baseline running on the Xeon processor and by up to 36% at lower thread counts. Finally, we generalize our results assuming pS(5) as representative of software that is heavily optimized for modern multi-core CPUs and investigate the performance and energy advantage that an FPGA in a datacenter setting can offer to regular RTL users compared to additional CPU cores.

FPGAs in the Datacenters: the Case of Parallel Hybrid Super Scalar String Sample Sort

Mikhail Asiatici, Paolo Ienne, Damian Maiorano

String sorting is an important part of database and MapReduce applications; however, it has not been studied as extensively as sorting of fixed-length keys. Handling variable-length keys in hardware is challenging and it is no surprise that no string sorters on FPGA have been proposed yet. In this paper, we present Parallel Hybrid Super Scalar String Sample Sort (pHS(5)) on Intel HARPv2, a heterogeneous CPU-FPGA system with a server-grade multi-core CPU. Our pHS(5) is based on the state-of-the-art string sorting algorithm for multi-core shared memory CPUs, pS(5), which we extended with multiple processing elements (PEs) on the FPGA. Each PE accelerates one instance of the most effectively parallelizable dominant kernel of pS(5) by up to 33% compared to a single Intel Xeon Broadwell core running at 3.4 GHz. Furthermore, we extended the job scheduling mechanism of pS(5) to enable our PEs to compete with the CPU cores for processing the accelerable kernel, while retaining the complex high-level control flow and the sorting of the smaller data sets on the CPU. We accelerate the whole algorithm by up to 10% compared to the 28 thread software baseline running on the 14-core Xeon processor and by up to 36% at lower thread counts.

IEEE COMPUTER SOC2020

Processeur à haut degré de parallélisme basé sur des composantes sérielles

Ralph Hoffmann

Nowaday, the world of processors is still dominated by the RISC architectures, which foundations have been laid down in the 70's. The RISC concept may be summarized by one word : simplicity. With this concept, much simpler architectures are born, in particular from their instruction sets point of view. As a result, these architectures have a more efficient instruction decoding and smaller computing units which in turn provides the ability to have more of these units for the same price, a reduced clock per instruction ratio — a single cycle per instruction ideally — and increased clock frequencies. As time goes by, RISC architectures have shown outstanding performances, on one hand with the spectacular improvements of semiconductor technologies, and on the other hand with the use of large cache memories and with the development of new ways of execution such as speculative execution. Later developments have greatly altered the original spirit of the simplicity of the RISC concept. Current high performance processors are extremely complex and difficult to design. Moreover, semiconductor technologies begin to show serious problems ignored or neglected for a long time. In this thesis, we would like to introduce a new architecture. Two complementary aspects have been taken in consideration : the design of the processor's units (arithmetic operators, control logic, and so on) and the architectural model, the way the processing units are used. The first aspect has been addressed with an unusual and original approach which involves the use of the serial arithmetic principles. Serial arithmetic tends to reduce the hardware cost, enables higher clock rates, and shows interesting properties which will be developped later on. The research of an architectural model is driven by the same wish of simplicity, recurrent in this field, and will inevitably shift the complexity from the processor to the compiler. This simplification relies on two things : first, the way we think of the problem is inspired by the EPIC philosophy (Explicitly Parallel Instruction Computer), the latest offspring of the VLIW model which advocates the delegation of decisions from the hardware to the software. In one sentence, "the compiler decides, the hardware executes". Second, the way we act has been given by the TTA model (Transport Triggered Architecture), the last offspring of the MOVE model which not only removes from the processor the responsability to decide which processing unit to be used for each instruction (it's already the case in a VLIW processor), but also releases the processor from scheduling the data flows. In doing so, the processor is confined to provide a set of computing units, storage units and means of communication, and the compiler decides how to move the data. In this way, a part of the control logic is removed, communication resources may be fine-tuned and the compiler's code-optimization can be enhanced. With the combination of those elements, we wish to get an architecture which exhibits a better computing power/consumption ratio, which is more flexible, easier to developp and to evolve.

EPFL2004

Processeur à haut degré de parallélisme basé sur des composantes sérielles

Ralph Hoffmann

EPFL2004