1401.7494

# Unknown Title ## Abstract Single Instruction, Multiple Data (SIMD) vectorization is a major driver of performance in current architectures, and is mandatory for achieving good performance with codes that are limited by instruction throughput. We investigate the efficiency of different SIMDvectorized implementations of the RabbitCT benchmark. RabbitCT performs 3D image reconstruction by back projection, a vital operation in computed tomography applications. The underlying algorithm is a challenge for vectorization because it consists, apart from a streaming part, also of a bilinear interpolation requiring scattered access to image data. We analyze the performance of SSE (128 bit), AVX (256bit), AVX2 (256 bit), and IMCI (512 bit) implementations on recent Intel x86 systems. A special emphasis is put on the vector gather implementation on Intel Haswell and Knights Corner microarchitectures. Finally we discuss why GPU implementations perform much better for this specific algorithm. Keywords SIMD, Intel MIC, gather, computed tomography, back projection, performance ## 1. Introduction Single Instruction, Multiple Data (SIMD) is a data-parallel execution model enabling to do more work with the same number of instructions. Because of its integration in existing microarchitectures it is a standard technology for increasing performance in modern processors. While the idea originated in the early seventies, the first implementation in a commodity processor was Intel's MMX instruction set extension for the x86 Pentium processor line in 1996. With AltiVec/VMX (1998) for PowerPC and SSE (1999) for x86 more capable 128 bit-wide SIMD instruction set extensions followed. For the software the introduction of SIMD was a paradigm shift as in contrast to previous hardware optimizations, which were designed to work transparently, the software must make explicit use of the new instructions in order to leverage the full potential of new processors. Vendors promised that optimizing compilers would enable the efficient use of the new instructions, but it soon turned Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. ## Comparing the Performance of Different x86 SIMD Instruction Sets for a Medical Imaging Application on Modern Multi- and Manycore Chips Johannes Hofmann Chair for Computer Architecture University Erlangen-Nuremberg johannes.hofmann@fau.de J. Treibig G. Hager G. Wellein Erlangen Regional Computing Center University Erlangen-Nuremberg jan.treibig@rrze.fau.de out that in many cases data structures must be adapted and kernels must be rewritten with the help of compiler intrinsics or even in assembly code. Intel incrementally updated the SIMD capabilities by introducing new instruction set extensions. SSE comprised 70 instructions, SSE2 (2001) added 144, SSE3 (2004) 29, and SSE4 (2006) 54 new instructions, for a total of 297 instructions [2]. In 2011 Intel doubled the SIMD width to 256 bit with A VX. Still of the total 349 instructions introduced with A VX only a subset of 92 instructions supported the 256 bit registers and only few new instructions were added. This was changed in 2013 with AVX2, which promoted most instructions to 256 bit and again added new ones. The new instructions can be grouped into complex instructions for arithmetic targeted at specific application classes, horizontal operations, more powerful in-register reordering instructions, and operations promoted to vectorized execution. While most of this can be seen as incremental improvements, AVX2 introduces instructions that change the way SIMD can be employed. This is the gather instruction together with the ability to mask out SIMD lanes with predicate registers. The hope is that this enables the use of SIMD in new application classes with more complex data access patterns where SIMD could not be used efficiently up to now. The first implementation of the AVX2 instruction set is in the Intel Haswell microarchitecture. Haswell also features Fused Multiply-Add (FMA) instructions in a separate instruction set extension (FMA3). In 2006 Intel started developing an x86 many-core design (codename Larrabee), initially targeted as an alternative to existing graphics processors. It uses a 512 bit SIMD instruction set called IMCI (Initial Many Core Instructions). While in 2010 the usage as a GPU was terminated, the design was refined and eventually retargeted as an accelerator card. The first product based on this design, the Intel Xeon Phi, was available in early 2013 with 60 cores and 8 GB of main memory. IMCI already anticipated and implemented many current developments in SIMD instruction sets and allowed to gain experience with a working implementation. The instruction set comprises gather/scatter instructions, predicate registers, and FMA. This paper studies the efficiency of an important algorithm from medical imaging when mapped to different Intel SIMD instruction set extensions. We look at the Instruction Set Architecture (ISA) interface as well as its implementation in a concrete microarchitecture. Although we also present results for compiler-generated code, a detailed analysis of the conditions under which a compiler would be able to achieve the same performance level as hand-crafted assembly is out of scope for this paper. Still we discuss how well an instruction set extension is suited for automatic generation of efficient code. We have chosen the RabbitCT benchmarking framework as test case [7]. RabbitCT implements volume reconstruction by back projection, which is the performance limiting part of many Computed Tomography (CT) applications. This operation is well suited for evaluating SIMD implementations, because it consists of streaming as well as scattered data access patterns and is therefore non-trivial to vectorize. Although a naive performance model suggests that the runtime of the algorithm should be determined by main memory bandwidth, its implementation with existing instruction sets introduces so much overhead that instruction throughput becomes the bottleneck. Therefore it can be seen as a prototype for applications in which the data cannot be loaded block-wise, but instead requires in-register shuffles. An interesting aspect of RabbitCT is that it is also a popular target for GPU-based efforts and therefore provides a good case to compare general purpose multi- and manycore designs with GPUs. We picked an Intel Xeon IvyBridge-EP two-socket system for executing the SSE and AVX code variants and an Intel Xeon Phi accelerator card for the IMCI kernels. Unfortunately a multi-socket system implementing AVX2 and FMA3 is not yet available. Therefore we choose a single socket Intel Xeon Haswell system to execute the AVX2/FMA3 kernel. This paper is structured as follows. Section 2 gives an overview of previous work about the performance optimization of this algorithm. The test systems used are described in Section 3. Section 4 introduces the RabbitCT benchmark and motivates its use for this study. Next we cover the SIMD kernel implementations in Section 5. We briefly introduce all optimizations applied and specifically cover the SIMD vectorization with an emphasis on the gather instruction in IMCI and AVX2. The section closes with a detailed instruction code analysis for the resulting kernels. The results are presented in Section 6. We separate single core from full system results to be able to clearly analyze the SIMD speedup efficiency. We also present microbenchmarking results showing the instruction latency for different settings in the current gather implementations. In Section 7 we compare our results with the fastest published GPU result and try to explain why this specific application is well suited for GPUs. We also present performance numbers for generated code in Section 8. To conclude we summarize our results and give an outlook. ## 2. Related Work Due to its relevance in medical applications, reconstruction in computed tomography is a well-studied problem. As vendors for CT devices are constantly looking for ways to speed up the reconstruction time, many computer architectures have been evaluated over time. Initial products in this field used special purpose hardware based on FPGAs (Field Programmable Gate Arrays) and DSPs (Digital Signal Processors) [1]. The Cell Broadband Engine, which at the time of its release provided unrivaled memory bandwidth, was also subject to experimentation [3, 8]. It is noteworthy that CT reconstruction was among the first non-graphics applications that were run on graphics processors [6]. However, the use of varying data sets and reconstruction parameters limited the comparability of all these implementations. In an attempt to remedy this problem, the RabbitCT framework [7] provides a standardized, freely available CT scan data set and a uniform benchmarking interface that evaluates both reconstruction performance and accuracy. Current noteworthy entries in the RabbitCT ranking include Thumper by Zinsser and Keck [11], a Kepler-based implementation which currently dominates all other implementations, and fastrabbit by Treibig et al. [10], a highly optimized CPU-based implementation. The presented work is partly based on the results of fastrabbit , improving it and providing an implementation for the Intel IMCI and AVX2 instruction sets. ## 3. Experimental Testbed A standard two-socket server based on the IvyBridge-EP microarchitecture was chosen for executing the SSE/AVX kernels. It employs two-way SMT and has ten moderately clocked (2.2 GHz base frequency) cores per socket. Sixteen vector registers are available for use with SSE and AVX. Using floating-point arithmetic, each core can execute one multiply and one add instruction per cycle, leading to a peak performance of eight Double Precision (DP) or 16 Single Precision (SP) Flops per cycle. Memory bandwidth is provided by means of a ccNUMA memory subsystem with four DDR3-1600 memory channels per socket. For the AVX2/FMA3 kernel a single-socket Intel Xeon server based on the Haswell microarchitecture was used. This system has four cores (two-way SMT) and 8 MB of L3 cache. The Intel Xeon Phi is located on a PCIe card and runs its own operating system. It consists of a single chip providing 60 lowfrequency cores with four-way SMT. The cores are based on a modified version of P54C design used in the original Pentium processor (1995). Each core is in-order and two-way superscalar, featuring a scalar pipeline (V-pipe) and a vector pipeline (U-pipe). The Vector Processing Unit (VPU) connected to the U-pipe features a total of 32 512 bit vector registers and is capable of FMA operations, yielding a total of 16 DP (32 SP) Flops per cycle. The cores are connected via a bidirectional ring bus. Eight GDDR5 memory controllers with two channels each are connected to the ring bus. The Xeon Phi offers different settings for usage, such as offload (common for GPUs) and native mode. We have used the native execution model in which everything is executed on the accelerator card and data transfers to and from the card are not taken into account. An overview of the test machine specifications is given in Table 1. ## 4. RabbitCT Benchmark In CT an X-ray source and a flat-panel detector positioned on opposing ends of a gantry move along a defined trajectory-mostly a circle-around the volume that holds the object to be investigated. X-ray images are taken at regular angular increments along the way. In general 3D image reconstruction works by back projecting the information recorded in the individual X-ray images (also called projection images) into a 3D volume, which is made up of individual voxels (volume elements). In medical applications, this volume almost always has an extent of 512 3 voxels. To obtain the intensity value for a particular voxel of the volume from one of the recorded projection images we forward project a ray originating from the X-ray source through the center of the voxel to the detector; the intensity value at the resulting detector coordinates is then read from the recorded projection image and added to the voxel. This process is performed for each voxel of the volume and all recorded projection images, yielding the reconstructed 3D volume as the result. Performance comparisons of different optimized back projection implementations found in the literature can be difficult because of variations in data acquisition and preprocessing, as well as different geometry conversions and the use of proprietary data sets. The RabbitCT framework was designed as an open platform that tries to remedy these problems. It features a benchmarking interface, a prototype back projection implementation, and a filtered, high resolution CT dataset of a rabbit; it also includes a reference volume that is used to derive various image quality metrics. The preprocessed dataset consists of 496 projection images that were acquired using a commercial C-arm CT system. Each projection is 1248 × 960 pixels wide and contains the filtered and weighted intensity values as single-precision floating-point numbers. In addition, each projection image pi comes with a separate projection matrix Ai ∈ R 3 × 4 , which is used to perform the forward projection. The framework takes care of all required steps to set up the benchmark, Table 1. Test machine specifications. 'Node Update' is a streaming multi-threaded benchmark that modifies an array in memory. | Microarchitecture Model | Intel IvyBridge-EP Xeon E5-2660 v2 | Intel Haswell Xeon E3-1240 v3 | Intel Knights Corner Xeon Phi 5110P | |-----------------------------------------------------------------------------------------------------|------------------------------------------------------------------------|--------------------------------------------------------------------|--------------------------------------------------------------------| | Base/Max. Turbo Clock Speed Sockets/Cores/Threads per Node SIMD Support Vector Register File | 2.2GHz/3.0GHz 2/20/40 SSE (128 bit), AVX (256 bit) 16 Registers | 3.4GHz/3.8GHz 1/4/8 (256 bit), FMA3 (256 bit) | 1.053GHz/- 1/60/240 IMCI (512 bit) 32 Registers | | Node L1/L2/L3 Cache Node Main Memory Configuration Node Peak Memory Bandwidth Node Update Benchmark | 20 × 32 kB/20 × 256 kB/2 × 8 channels DDR3-1866 119.4GB/s 98GB/s (81%) | 4 × 32 kB/4 × 256kB/8MB 2 channels DDR3-1600 25.6GB/s 23GB/s (90%) | 60 × 32 kB/60 × 512 kB/- channels GDDR5 5GHz 320GB/s 168GB/s (53%) | | | | AVX2 | | | | | 16 Registers | | | | 25MB | | | | | | | 16 | | Bandwidth | | | | so the programmer can focus entirely on the actual back projection implementation, which is provided as a module (shared library) to the framework. ## 4.1 Algorithm A slightly compressed version of the unoptimized reference implementation that comes with RabbitCT is shown in Listing 1. This code is called once for every projection image. The three outer for loops (lines 1-3) are used to iterate over all voxels in the volume; note that we refer to the innermost x -loop, which updates one 'line' of voxels in the volume, as the 'line update kernel.' The loop variables x , y , and z are used to logically address all voxels in memory. To perform the forward projection these logical coordinates used for addressing must first be converted to the World Coordinate System (WCS), whose origin coincides with the center of the voxel volume; this conversion happens in lines 6-8. The variables O and MM that are required to perform this conversion are precalculated by the RabbitCT framework and made available to the back projection implementation in a struct pointer that is passed to the back projection function as a parameter. After this the forward projection is performed using the corresponding projection matrix in lines 10-12. In order to transform the affine mapping that implements the forward projection into a linear mapping homogeneous coordinates are used. Thus the detector coordinates are obtained in lines 14 and 15 by dehomogenization. The next step is a bilinear interpolation, which requires converting the previously obtained detector coordinates from floatingpoint to integer (lines 17-18) to address the intensity values in the projection image buffer I . The interpolation weights scalex and scaley are calculated in lines 20-21. The four intensity values needed for the bilinear interpolation are fetched from the buffer containing the intensity values in lines 26-36. The if statements ensure that the image coordinates lie inside the projection image; in case the ray does not hit the detector, i.e., if the coordinates lie outside the projection image, an intensity value of zero is assumed (lines 24-25). Note that the projection image is linearized, which is why we need the projection image width in the variable width (also made available by the framework via the struct pointer passed to the function) to correctly address data inside the buffer. The actual bilinear interpolation is performed in lines 39-41. Before the result is written back into the volume, it is weighted according to the inverse-square law (line 43). The variable w holds the homogeneous coordinate, which is an approximation of the distance from the X-ray source to the voxel under consideration, and can be used to perform the weighting. For all further analysis we will structure the overall algorithm in three main parts. Part 1 consists of the geometry computation involving the calculation of the index in detector coordinates. Part 2 involves of the actual loading of the intensity values from the ``` ``` Listing 1. Unoptimized reference back projection implementation processing a single projection image. projection image. Finally in Part 3 the bilinear interpolation and the update of the voxel data is performed. ## 4.2 Code Analysis One voxel sweep incurs a data transfer volume which consists of the loads from the projection image and an update operation ( VOL[i]+=s for all i ) to the voxel array. The latter causes 8 bytes of traffic per voxel and for the medically relevant problem size of 512 3 voxels results in a data volume of 1 GB per projection image, or 496 GB for all projections. The main memory traffic caused by loading the intensity values from the projection images is hard to quantify since it is not a simple stream; it is defined by a 'beam' of locations slowly moving over the projection image as the voxel update loop nest progresses. It exhibits some temporal locality, which allows for a certain degree of caching, since neighboring voxels are projected on proximate regions in the image, but there may also be multiple streams with large strides if the beam sweeps across the image orthogonal to the rows. On the computational side, the basic version of this algorithm performs 13 additions, 5 subtractions, 17 multiplications, and 3 divides. ## 5. Implementation Task parallel programming is based on OpenMP: The voxel volume is segmented into voxels planes that can be processed independent from each other. All line update kernels (SSE, A VX, A VX2/FMA3, IMCI) are written in assembly language and use all of the optimizations found in the original fastrabbit implementation [10]. The presented work improves on these achievements. The original algorithm calculating the clipping mask 1 had minor flaws, which have been remedied. For a 512 3 volume we can reduce the number of voxels that have to be processed by almost 10% when using the improved instead of the original clipping mask. Moreover parameter handling and instruction scheduling inside the kernel was improved leading to an overall speedup of a factor of 1.25 compared to the original fastrabbit implementation. ## 5.1 SIMD Vectorization Part 1 of the algorithm is straightforward to vectorize. A viable optimization on all architectures is to replace the divide with a reciprocal instruction. The reciprocal is pipelined with a throughput of one cycle and has a lower latency compared to the standard divide. On KNC the reciprocal provides full accuracy; on the CPU, however, it has a reduced accuracy (11 bits of mantissa). Nevertheless, the quality of the resulting reconstruction is similar to that of GPU implementations. As a result of Part 1, the detector indices have been computed and are located in SIMD registers. Part 2 is the most difficult part of the algorithm, because the required detector values are not contiguous in memory. Moreover, the contents of a SIMD register cannot be used for addressing (i.e., as pointers or offsets) in SSE and A VX. Therefore the SIMD register containing the indices must be stored back to memory and loaded again into a general purpose register for addressing. Since two adjacent values are always needed (cf. bilinear interpolation), the image data can be loaded in pairs. The interpolation weights need to be rearranged to match the order of the intensity values. While Part 2 looks simple in C code, it requires a lot of instructions to implement it efficiently using SSE and A VX. This part therefore does not scale very well with increased register width. In Part 3 the actual bilinear interpolation is performed. It requires some additional reordering of the data in the SIMD registers, but is otherwise straightforward to vectorize. The SSE and 1 For some projection angles several voxels are not projected onto the flatpanel detector. For these voxels a zero intensity is assumed. Such voxels can be 'clipped' off by providing proper start and stop values for each x -loop. AVX implementations are very similar, the latter requiring more reordering and adding more overhead for loading the data due to its doubled SIMD width. The main difference between SSE/AVX and AVX2/IMCI is the availability of FMA and gather instructions in the latter. A significant part of the arithmetic operations can be mapped to FMAs. The gather instruction simplifies the implementation considerably, since it enables using the indices in the SIMD register directly for addressing. However, some peculiarities of the IMCI ISA diminish this benefit. The A VX2 implementation is very similar to IMCI but provides a much simpler interface to the gather instruction, saving 50% instructions compared to the IMCI version. Instruction setwise, the gather instruction is a main benefit for this algorithm, so we introduce it in more detail in the following section. ## 5.1.1 Gather Instruction Interfaces ``` <doc> k2 3(k2), [rdi + zmm17 * 4] .L101 3(k2), [rdi + zmm17 * 4] .L100 </doc> ``` Listing 2. Gather instruction interface in IMCI. Listing 2 shows the instruction code for one gather construct with IMCI. The vgatherdps instruction loads 16 single-precision values (or fewer, depending on which bits of the mask registerk2 in our example-are set) into a register from the 16 addresses specified in its second argument. Instead of fetching all data with one instruction, vgatherdps works by getting the data cache line-wise per invocation; this means that every time the gather instruction is used, it will fetch only one cache line (CL), load all the values that it is supposed to gather from it, store them in the destination vector register, and finally zero out the bits of the components that have been filled in the vector mask register. As a consequence, the number of gather instruction depends on the distribution of the data: If all data resides in one CL then one gather instruction is sufficient; in the worst case, each value is located in a different CL, which will require sixteen gather instructions. The jkzd instruction in line 3 checks the contents of the vector mask register that was updated in the line before by the vgatherdps instruction. If the mask register is zero, i.e., all zero bits indicating that all data has been gathered, control flow continues at label ..L101 in line 6; if the mask register is non-zero, i.e., if one or more bits are set, indicating that there is still data to be fetched, no jump is performed and the vgatherdps in line 4 is scheduled next. After more data has been gathered and k2 has been updated, the vector mask register is tested again for zero by the jknzd in line 5. If there is still data to be fetched, control flow will jump back to label ..L100 in line 2, starting the gather construct all over. If all data has been fetched, the construct is left. This two-stage strategy was obtained by examining the compiler output for non-contiguous data access and turns out to be faster than a simple loop with only one gather instruction. The authors have as yet no plausible explanation for this. vpcmpeqw ymm7, ymm7, ymm7 vgatherdps ymm15, [rdi + ymm11 * 4], ymm7 Listing 3. Gather instruction interface in A VX2. Listing 3 shows the respective code for AVX2. In contrast to IMCI, no loop construct is required and a single instruction is sufficient. This allows for a very compact and elegant code. Instead of using dedicated vector mask registers, A VX2 uses regular vector registers (supplied as third argument) as mask for the operation. Note that for our application we always gather all vector components without checking whether the intensity values are located inside the projection images or not. This is achieved by setting the vector (mask) registers to all one bits ( kxnor , vpcmpeqw ). We found that copying the projection images into a zero-padded buffer and removing the conditionals (cf. lines 26-36 in Listing 1) resulted in a better performance than setting the mask registers, which causes too much instruction overhead. ## 5.2 Instruction Code Analysis The main benefit of SIMD is that a given amount of work can be finished with fewer instructions than with scalar execution. Therefore the number of instructions and their composition in terms of instruction types (memory, in-register, arithmetic, etc.) are interesting metrics for our case. These are influenced by the register width and by the availability of instruction types, such as FMA or gather instructions. Table 2 shows an overview for the three parts of this algorithm for all five hand-written assembly implementations. Note that for Haswell in addition to an A VX2 version we also devised an AVX/FMA3 implementation that uses Haswell's FMA3 instruction but is otherwise identical to the A VX implementation-i.e. it uses no gather instructions. Part 1 is trivial to vectorize and exhibits good scalability: In Table 2 this is reflected by the fact that hardly any additional instructions are required when switching from SSE to AVX. Apart from reducing the total number of arithmetic instructions, the use of FMA has the additional benefit of reducing memory instruction in Part 1: Because a FMA doesn't require an intermediate register for the result of the multiplication, register pressure and-as a consequence-the amount of register spilling is lower. In contrast to the first part, the second part of the algorithm scales poorly instruction-wise. Due to the sequential loads, the number of memory operations almost doubles when switching from SSE to AVX. For IMCI the gather instruction simplifies the implementation, because no additional in-register reordering is necessary. In contrast to the slim AVX2 gather interface, the bold IMCI loop interface cancels out the advantage instruction-wise and ends up with an instruction count similar to A VX. In Part 3, while in theory simple to vectorize, all non-gather implementations suffer from in-register reordering overhead. Overall, the overhead of switching from SSE to AVX is 19 instructions. IMCI roughly ends up with the same instruction count as the SSE code. While we would anticipate a lower instruction count for IMCI considering FMA and gather, the fact prefetching has to be implemented in software and the design of the gather interface cause a lot of instruction overhead. The AVX2 gather interface does not suffer from this shortcoming and has the lowest instruction count. In Table 3 we compare the number of instructions required by different SIMD instruction sets compared to baseline scalar code. The baseline code was generated using the Intel 13.1 compiler together with the -O3 -no-vec -x flag for each of the instruction sets. This means that for A VX and AVX2 the scalar version makes use of the new VEX (vector extensions) prefix introduced by AVX, allowing instructions to use more than two operands; the AVX2 and AVX/FMA3 versions use FMA instructions. We omit IMCI in this comparison, because there exist no dedicated scalar instructions in this instruction set. The 'instruction count efficiency' metric is the ratio of instruction counts between the scalar and the vectorized code versions-e.g. an efficiency of 100% means that both versions require the same amount of instructions, whereas an efficiency of 50% means that the vectorized code requires twice as many instructions as the scalar code. Additionally we also list Table 2. Instruction count and composition. The instruction types are categorized into three classes: memory for all instructions with a memory reference, shuffle for register manipulation instructions, and arithmetic for computational instructions. All remaining instructions such as, e.g., loop instructions are contained in other . | | Type | SSE | AVX | AVX2 | AVX/FMA3 | IMCI | |--------|---------|-------|-------|--------|------------|--------| | Part 1 | Memory | 4 | 3 | 0 | 3 | 0 | | | Arith. | 17 | 17 | 12 | 12 | 15 | | | All | 21 | 20 | 12 | 15 | 15 | | Part 2 | Memory | 18 | 34 | 4 | 34 | 16 | | Part 2 | Shuffle | 6 | 10 | 0 | 10 | 0 | | Part 2 | Arith. | 2 | 2 | 12 | 2 | 24 | | Part 2 | All | 26 | 46 | 16 | 46 | 40 | | Part 3 | Memory | 2 | 2 | 2 | 2 | 2 | | Part 3 | Arith. | 20 | 20 | 15 | 16 | 12 | | Part 3 | All | 22 | 22 | 17 | 18 | 14 | | Other | All | 4 | 4 | 4 | 3 | 8 | | Total | | 73 | 92 | 49 | 82 | 77 | Table 3. Overview of static instruction code analysis. Runtime Efficiency results pertain to one core using SMT. | | SSE | AVX | AVX2 | AVX/FMA3 | |----------------------------|-------|-------|--------|------------| | Voxels per Vectorized Loop | 4 | 8 | 8 | 8 | | Instr. per Loop (SIMD) | 73 | 92 | 49 | 82 | | Instr. per Voxel (Scalar) | 57 | 46 | 41 | 46 | | Instr. Count Efficiency | 78% | 50% | 84% | 56% | | SIMD Runtime Efficiency | 82% | 51% | 33% | 42% | the 'SIMD runtime efficiency,' which we define as the achieved runtime speedup divided by the number of SIMD lanes. Interestingly, the SIMD efficiency numbers for SSE and AVX are almost identical to the respective instruction count efficiencies. For both the AVX2 and AVX/FMA3 implementations the baseline scalar code was generated using the -xCORE-AVX2 , which is why the AVX/FMA3 code shows a lower runtime efficiency than AVX. Interestingly we find that while instruction count efficiency is higher using AVX2, AVX/FMA3 provides better runtime efficiency, i.e. performance. The reason for this is the high latency of the gather instruction that is used in the A VX2 variant (cf. Section 6.3). ## 6. Results Section 5.2 has already described the SIMD efficiency of various implementations in terms of instruction overhead. Here we present results illustrating how well the instruction set was implemented in the microarchitectures and how efficient the implementation is in terms of speedup. To do so we distinguish two cases: Single core (to pinpoint the SIMD influence alone) and full-system scaling. It was shown previously [10] that the performance of the code is limited by instruction execution, and that data transfers through the cache hierarchy do not play a significant role on modern multi-core architectures. Thread pinning was done with likwid-pin [9]. ## 6.1 Analysis of SIMD and SMT Speedup Figure 1 shows the results for single core performance. Again, scalar code was generated using the Intel 13.1 compiler. It is instructive to analyze the benefit of Simultaneous Multi-Threading (SMT) together with SIMD, since a considerable speedup with SMT points to inefficient pipeline utilization. On IvyBridge-EP, SSE yields a 3.3 × speedup with SMT (out of a possible 4 × ). As Figure 1. Single core performance of different SIMD implementations on IvyBridge-EP, Haswell and Knights Corner (KNC) in billions of voxel updates per second (GUP/s). The black bars are sequential results. The yellow bar is the speedup using all available SMT threads. The scalar version on IvyBridge-EP based on AVX and on Haswell on AVX2. <details> <summary>Image 1 Details</summary>  ### Visual Description ## Horizontal Bar Chart: Performance Comparison Across CPU Architectures and Instruction Sets ### Overview This image is a horizontal bar chart comparing computational performance, measured in Giga Updates Per Second (GUP/s), across three different CPU microarchitectures (IvyBridge-EP, Haswell, KNC). For each architecture, performance is shown for different instruction sets, comparing a "Scalar" (black bar) baseline to a "Vector" (yellow bar) implementation. The percentage improvement of the vector version over the scalar version is explicitly labeled for each pair. ### Components/Axes * **Chart Type:** Horizontal grouped bar chart. * **X-Axis (Top):** Labeled "Performance [GUP/s]". The scale runs from 0 to 0.5, with major tick marks at 0, 0.1, 0.2, 0.3, 0.4, and 0.5. * **Y-Axis (Left):** Lists three CPU microarchitecture groups, separated by horizontal lines. Within each group, specific instruction set extensions are listed. * **Legend:** Located in the top-right corner of the chart area. * **Black Bar:** Labeled "Scalar". * **Yellow Bar:** Labeled "Vector". * **Data Labels:** Each yellow "Vector" bar has a text label indicating the percentage improvement (e.g., "+27%") relative to its paired black "Scalar" bar. ### Detailed Analysis The chart is segmented into three distinct regions from top to bottom: **1. IvyBridge-EP Architecture (Top Section)** * **Scalar (Black):** Performance is approximately 0.12 GUP/s. * **Vector (Yellow):** Performance is approximately 0.15 GUP/s. * **Improvement:** Labeled as **+27%**. * **Scalar (Black):** Performance is approximately 0.22 GUP/s. * **Vector (Yellow):** Performance is approximately 0.27 GUP/s. * **Improvement:** Labeled as **+22%**. * **AVX:** * **Scalar (Black):** Performance is approximately 0.28 GUP/s. * **Vector (Yellow):** Performance is approximately 0.38 GUP/s. * **Improvement:** Labeled as **+37%**. **2. Haswell Architecture (Middle Section)** * **Scalar (Black):** Performance is approximately 0.14 GUP/s. * **Vector (Yellow):** Performance is approximately 0.15 GUP/s. * **Improvement:** Labeled as **+7%**. * **SSE:** * **Scalar (Black):** Performance is approximately 0.35 GUP/s. * **Vector (Yellow):** Performance is approximately 0.40 GUP/s. * **Improvement:** Labeled as **+13%**. * **AVX:** * **Scalar (Black):** Performance is approximately 0.35 GUP/s. * **Vector (Yellow):** Performance is approximately 0.50 GUP/s (the bar extends slightly past the 0.5 mark). * **Improvement:** Labeled as **+44%**. * **AVX/FMA3:** * **Scalar (Black):** Performance is approximately 0.35 GUP/s. * **Vector (Yellow):** Performance is approximately 0.50 GUP/s (the bar extends slightly past the 0.5 mark). * **Improvement:** Labeled as **+44%**. * **AVX2/FMA3:** * **Scalar (Black):** Performance is approximately 0.35 GUP/s. * **Vector (Yellow):** Performance is approximately 0.46 GUP/s. * **Improvement:** Labeled as **+31%**. **3. KNC (Knights Corner) Architecture (Bottom Section)** * **Scalar (Black):** Performance is very low, approximately 0.02 GUP/s. * **Vector (Yellow):** Performance is approximately 0.07 GUP/s. * **Improvement:** Labeled as **+126%**. * **IMCI:** * **Scalar (Black):** Performance is approximately 0.08 GUP/s. * **Vector (Yellow):** Performance is approximately 0.21 GUP/s. * **Improvement:** Labeled as **+160%**. ### Key Observations 1. **Universal Vectorization Benefit:** In every single case, the yellow "Vector" bar is longer than its paired black "Scalar" bar, demonstrating that vectorization improves performance for this workload across all tested architectures and instruction sets. 2. **Magnitude of Improvement Varies:** The performance gain from vectorization is not uniform. It ranges from a modest **+7%** (Haswell, Scalar vs. Vector) to a very substantial **+160%** (KNC, IMCI). 3. **Architecture Performance Tiers:** The Haswell architecture, particularly with AVX and FMA3 instructions, achieves the highest absolute performance, reaching or exceeding 0.5 GUP/s. IvyBridge-EP shows moderate performance, while the KNC architecture shows the lowest absolute performance but the highest relative gains from vectorization. 4. **Instruction Set Impact:** Within Haswell, moving from SSE to AVX/AVX2 with FMA3 shows a clear performance jump for the vectorized code. The Scalar performance for AVX, AVX/FMA3, and AVX2/FMA3 appears similar (~0.35 GUP/s), suggesting the scalar bottleneck is elsewhere. 5. **KNC's Unique Profile:** The KNC (a many-core Xeon Phi architecture) shows dramatically different behavior. Its scalar performance is extremely low, but vectorization (especially with IMCI) unlocks massive relative gains, highlighting its design as a vector-oriented processor. ### Interpretation This chart provides a clear technical demonstration of the performance impact of **vectorization** (using SIMD instructions) on a specific computational workload (measured in GUP/s). The data suggests: * **Vectorization is a critical optimization:** For this workload, failing to use vector instructions leaves significant performance on the table, especially on architectures designed for it like KNC. * **Architectural design dictates optimization payoff:** The benefit of vectorization is highly dependent on the underlying CPU microarchitecture. A modern core like Haswell sees good gains (+44%), but a many-core, vector-centric design like KNC sees transformative gains (+160%), as its scalar units are likely a severe bottleneck. * **Instruction set evolution matters:** The progression from SSE to AVX to AVX2/FMA3 on Haswell shows increasing peak vector performance, indicating that newer, more capable instruction sets are essential for extracting maximum performance from the hardware. * **The "why" behind the numbers:** The low scalar performance on KNC is likely because its cores are simplified and heavily reliant on wide vector units for throughput. The high vector gains confirm that the workload is well-suited to parallel data processing. The similar scalar performance across Haswell's AVX variants suggests the scalar code path is not utilizing the advanced features of FMA or AVX2, hitting a different bottleneck. In essence, the chart is a compelling case study for performance engineers: to achieve high throughput (GUP/s), one must not only use vectorization but also select the appropriate architecture and instruction set for the target workload. The KNC data, in particular, acts as a stark warning about the performance penalty of running non-vectorized code on vector-optimized hardware. </details> expected, the AVX kernel is significantly less efficient, with 4.1 × out of 8 × . It is known that the A VX kernel suffers from critical path dependencies [10], which is confirmed by the large benefit gained with SMT. In a sense, inefficient SIMD code can be partly compensated by multi-threading in this particular case. On Haswell the SSE kernel performs surprisingly well, even without SMT, but the best possible variant is A VX/FMA3 with SMT. The AVX2 kernel is the slowest of all variants despite its instruction count advantage: The bilinear interpolation requires four intensity values for each voxel, which results in four gather instructions. These incur a latency of about 42 clock cycles (cf. Sec. 6.3). In contrast the A VX and AVX/FMA3 implementations use 16 pairwise loads to gather the intensity values; although these version require about 10 additional in-register shuffling instructions overall this approach yields a much better performance. On KNC the SIMD speedup is 10 × out of a possible 16 × . This result emerges from a combination of slow scalar code (see above) with an inefficient and dominating gather instruction in the SIMD case. We will analyze the latter in more depth in Section 6.3. ## 6.2 Full Device Results Figure 2 shows the performance of scalar and vectorized implementations on IvyBridge-EP and KNC. Results for Haswell are omitted because at the time of writing no two-socket system was available. The full system results were measured with Turbo mode enabled and all available SMT threads. A naive peak performance comparison gives reason to expect a 3 × advantage for KNC. For our algorithm, one KNC device is only 1.2 × faster than one IvyBridge-EP node. This is a disappointing result, considering that IvyBridge-EP is also available with 12 instead of 10 cores and with a faster clock speed. Both architectures suffer from the impact of the inefficient Part 2 execution, but this problem is more severe on KNC, as will be demonstrated in Section 6.4. Figure 2. Full system performance on IvyBridge-EP and KNC <details> <summary>Image 2 Details</summary>  ### Visual Description ## Bar Chart: Performance Comparison of Instruction Sets on IvyBridge-EP and KNC Architectures ### Overview The image is a horizontal bar chart comparing the performance, measured in Giga Updates Per Second (GUPS/s), of different computational instruction sets on two distinct processor architectures: Intel IvyBridge-EP and Intel Xeon Phi Knights Corner (KNC). The chart demonstrates the performance scaling achieved by moving from scalar code to vectorized instruction sets. ### Components/Axes * **Chart Type:** Horizontal bar chart. * **X-Axis (Bottom):** Labeled "Performance [GUPS/s]". It has a linear scale with major tick marks at every integer from 0 to 9. * **Y-Axis (Left):** Lists the processor architectures and their respective instruction sets. The architectures are grouped with a label and a horizontal dividing line. * **Top Group:** Labeled "IvyBridge-EP". Contains three bars for: "Scalar", "SSE", and "AVX". * **Bottom Group:** Labeled "KNC". Contains two bars for: "Scalar" and "IMCI". * **Legend:** There is no separate legend box. The instruction set labels are placed directly to the left of their corresponding bars on the y-axis. * **Bar Color:** All bars are solid black. ### Detailed Analysis **IvyBridge-EP Architecture (Top Section):** 1. **Scalar:** The bar extends from 0 to approximately **1.8 GUPS/s**. This is the baseline performance. 2. **SSE (Streaming SIMD Extensions):** The bar extends from 0 to approximately **5.5 GUPS/s**. This represents a significant performance increase over the scalar version. 3. **AVX (Advanced Vector Extensions):** The bar extends from 0 to approximately **7.2 GUPS/s**. This is the highest performance within the IvyBridge-EP group. **KNC Architecture (Bottom Section):** 1. **Scalar:** The bar extends from 0 to approximately **1.0 GUPS/s**. This is the lowest performance value on the entire chart. 2. **IMCI (Intel Many Core Instruction Set):** The bar extends from 0 to approximately **8.5 GUPS/s**. This is the highest performance value shown in the chart. ### Key Observations * **Performance Hierarchy:** For both architectures, the vectorized instruction sets (SSE/AVX for IvyBridge-EP, IMCI for KNC) dramatically outperform their respective scalar implementations. * **Architecture Comparison:** The KNC's specialized IMCI instruction set achieves the highest absolute performance (~8.5 GUPS/s), surpassing the best performance from the general-purpose IvyBridge-EP (~7.2 GUPS/s for AVX). * **Scalar Performance:** The scalar performance on KNC (~1.0 GUPS/s) is notably lower than the scalar performance on IvyBridge-EP (~1.8 GUPS/s). * **Scaling Factor:** The performance scaling from Scalar to the best vector set is more pronounced on KNC (an increase of ~7.5x) compared to IvyBridge-EP (an increase of ~4x from Scalar to AVX). ### Interpretation This chart visually argues for the critical importance of utilizing vectorized instruction sets to achieve high performance on modern processor architectures. The data suggests that: 1. **Vectorization is Essential:** Writing code to leverage SIMD (Single Instruction, Multiple Data) extensions is not optional for high-throughput computing; it provides a multi-fold performance increase. 2. **Architecture-Specific Optimization Yields Best Results:** The KNC's IMCI, designed specifically for its many-core architecture, delivers superior peak performance compared to the more general AVX instructions on a standard CPU core. This highlights the performance advantage of specialized hardware and instruction sets. 3. **The Cost of Generality:** The lower scalar performance on KNC may indicate that its individual cores are less optimized for traditional scalar code, reinforcing that its strength lies in massively parallel, vectorized workloads. 4. **Practical Implication:** For developers working on high-performance computing (HPC) or numerical simulation tasks (where GUPS is a relevant metric), the chart provides clear evidence that targeting AVX on CPUs or IMCI on Xeon Phi coprocessors is necessary to unlock the hardware's potential. The significant gap between scalar and vector performance underscores the performance penalty of failing to optimize code for vectorization. </details> Scalability across the cores is very similar on both systems, with a parallel efficiency of 93%. 2 This corroborates the expectation that code execution is highly core-bound. ## 6.3 Detailed Performance Analysis of Vector Gather Implementations The vector gather instruction in the KNC microarchitecture has attracted major attention as it is the first gather implementation in an x86-based design. In this section we conduct a more detailed analysis of the gather performance on KNC, and compare with the situation on Haswell (with AVX2). As introduced in Section 5.1.1 the KNC ISA requires the gather instructions to be invoked multiple times in order to load all required data elements. The exact number of executions depends on the total number of cache lines the data is loaded from. Using the likwid-bench tool [9] we implemented a microbenchmark which allows to measure the average instruction latency depending on how many values are loaded per call (cache line). All hardware threads of a single core were used to measure the latencies to gather 16 elements from L1 cache and L2 cache, depending on how the data is distributed. The results are shown in Table 4. We find that the latency for a single vgatherdps instruction on KNC varies depending on how many elements it has to fetch from a cache line. The reason for this effect is that the vgatherdps instruction itself is implemented as another loop, not visible on the ISA level: the more elements it has to fetch from a single CL, the higher the latency. Nevertheless we find that it is beneficial for the data to reside in as few CLs as possible: Although the latency for a single vgatherdps instruction increases with the number of elements per cache line, the impact of calling the vgatherdps instruction multiple times is generally more severe. On the Haswell microarchitecture, the gather latency is largely independent of the number of cache lines touched when data is in the L1 or the L2 cache. From the numbers it is evident that it may be faster in some cases to ignore the hardware-based gather. The good performance of the AVX/FMA3 algorithm implementation on Haswell compared to AVX2 (see Fig. 1) is a direct consequence of this. On KNC, which has no L1 hardware prefetcher, there is a noticeable impact when dropping from L1 to L2 cache. Due to the streaming access pattern in the microbenchmark we find that on Haswell there is almost no difference in latency depending on whether data is gathered from L1 or L2 cache due to hardware prefetching. Overall, the performance impact of the gather operation is much more severe on KNC than on Haswell. In Section 6.4 we will show that the gather instructions do indeed account for the dominant part of the kernel runtime on KNC, leading to the observed mediocre KNC performance. 2 To obtain results unbiased by Turbo mode artifacts we disabled Turbo mode on IvyBridge during the scalability measurements. Table 4. Latencies in clock cycles encountered when gathering data from different levels of the memory hierarchy for different distributions of the data to be gathered. 'Instruction' and 'Loop' refer to the average latency of a single vgatherdps instruction and the total time required to gather all 16 (IMCI) or 8 (A VX2) elements, respectively. | Microarchitecture | Knights Corner | Knights Corner | Knights Corner | Knights Corner | Haswell | Haswell | |---------------------|------------------|------------------|------------------|------------------|-------------|-------------| | Distribution | L1 Cache | L1 Cache | L2 Cache | L2 Cache | L1 Cache | L2 Cache | | | Instruction | Loop | Instruction | Loop | Instruction | Instruction | | 16 per CL | 9.0 | 9.0 | 13.6 | 13.6 | | | | 8 per CL | 4.2 | 8.4 | 9.4 | 18.8 | 10.0 | 10.0 | | 4 per CL | 3.7 | 14.8 | 9.1 | 36.4 | 11.0 | 11.2 | | 2 per CL | 2.9 | 23.2 | 8.6 | 68.8 | 10.0 | 12.0 | | 1 per CL | 2.3 | 36.8 | 8.1 | 129.6 | 11.2 | 11.2 | ## 6.4 Performance Analysis for Knights Corner We start by estimating how many cycles are needed to execute one loop iteration of the kernel. Neglecting the variable influence of the gather constructs in Part 2 for the time being, we created a variant of the full kernel without gather instructions. Based on a static instruction code analysis taking into account instruction pairing (superscalar execution) we estimate 34 cycles for the gather-less kernel. This was verified by measurement which resulted in about 37.5 cycles. For our model, we use the measured value of 37.5 clock cycles because it contains non-negligible overhead such as backing up caller-save registers when calling the line update kernel that was not accounted for in the analytical prediction. By instrumentation of the gather loops it was determined that for one loop iteration the gather instruction was executed 16 times on average. Distributing that number over the four gather loop constructs (one for each of the four values required for the bilinear interpolation) we arrive at 4 gather instructions per gather loopindicating that the data is, on average, distributed across four CLs. From this we can infer the runtime contribution based on our previous findings (cf. Table 4). The latency of each gather instruction in the situation where the data is distributed across four CLs is 3.7 clock cycles. With a total of 16 gather instructions per iteration, the contribution is 59.2 clock cycles. Together with the remaining part of one kernel loop iteration (37.5 clock cycles), the total execution time is approximately 97 clock cycles. Up until now we assumed that all data is already located in the L1 cache. Using likwid-perfctr [9] we found that 88.5% of the projection data can be serviced from the local L1 cache and the remaining 11.5% can be serviced from the local L2 cache. Since each gather transfers a full CL, this amounts to approximately 16CLs · 64byte/CL · 11 . 5% ≈ 118byte. We estimate the effective L2 bandwidth in conjunction with the gather instruction to be the following: The latency of a single gather instruction (with data distributed across four CLs) was previously measured to be 3.7 clock cycles with data in L1 cache, respectively 9.1 clock cycles with data in the L2 cache (cf. Table 4). Assuming the difference of 5.4 clock cycles to be the exclusive L2 cache contribution, we arrive at an effective bandwidth of 64byte / 5 . 4cycle = 11 . 85byte/cycle. The additional cost is thus 118byte / 11 . 85byte/cycle ≈ 10cycles, resulting in a total runtime of 107 clock cycles. Several unsuccessful attempts to improve the L1 hit rate of the gather instructions were made. We found that the gather hint instruction, vgatherpf0hintdps , is implemented as a dummy operation-it has no effect whatsoever apart from instruction overhead. Another prefetching instruction, vgatherpf0dps , appeared to be implemented exactly the same as the actual gather instruction, vgatherdps : Instead of returning control back to the hardware context after the instruction is executed, we found that control was relinquished only after the data has been fetched into the L1 cache, rendering the instruction useless. Finally, scalar prefetching using the vprefetch0 instruction was evaluated. Unfortunately the instruction overhead of moving the offsets from vector registers onto the stack to get them into general purpose registers for scalar prefetching far outweighed the benefit of improving the L1 hit rate (even when prefetching only the CLs containing every second, forth, or even eight value). To summarize, out of the 107 clock cycles 69 can be attributed to gathering the required data, clearly indicating that the gather implementation is the factor limiting SIMD scalability. If pairwise loads and an adequate latency hiding mechanism were available, this could be reduced to a mere 32 cycles (2 × 16 pairwise loads for the 16 voxels that are processed in one loop iteration). ## 7. Comparison to GPU Implementations In order to integrate our findings with today's state-of-the-art in CT image reconstruction, a comparison with the fastest currently available GPU implementation called Thumper [11] shows that the GeForce GTX 680 is almost 8 × faster than KNC, although Intel had originally intended the KNC to compete with GPU accelerators from other vendors. This discrepancy can not be explained by simply examining the platforms' specifications such as peak Flop/s and memory bandwidth. Two of the main causes contributing to the GPU's superior performance in this particular application are: 1. Most computations involved in the reconstruction kernel, such as the projection of voxels onto the detector panel or the bilinear interpolation, are typical for graphics applications (which GPUs are designed for). While the matrix-vector multiplication is performed efficiently on both the GPU and the KNC, the bilinear interpolation is much faster on the GPU: GPUs have additional hardware (texture units) that can perform multiple bilinear interpolations in each clock cycle for data in the texture cache. To emphasize the implications, consider that out of the total of 107 clock cycles for one loop iteration of the kernel, 94 clock cycles, i.e., almost 90%, are spent on the bilinear interpolation, which can be performed with a single instruction on a GPU. 2. Given a sufficient amount of work, Nvidia's CUDA programming model does a better job at hiding latencies. As seen before, even in the ideal case, where all data can be serviced from the L1 cache, on average each of the gather instructions has a latency of 3.7 clock cycles. Although the KNC can hide the latencies of most instructions when using all four hardware contexts of a core, 4-way SMT is not sufficient to hide latencies caused by loading non-contiguous data, and is still plagued by excess traffic due to the cache line concept. The massive threading on Nvidia's multiprocessors ensures that there is always a Figure 3. Performance comparison of different programming models on full systems. <details> <summary>Image 3 Details</summary>  ### Visual Description ## Grouped Bar Chart: Performance Comparison Across Processors and Compilers ### Overview The image is a grouped bar chart comparing computational performance, measured in Giga Updates Per Second (GUP/s), across three different processor architectures using four different programming/compiler approaches. The chart visually demonstrates significant performance variations based on both the hardware platform and the software optimization method. ### Components/Axes * **Chart Type:** Grouped Bar Chart. * **Y-Axis (Vertical):** * **Label:** "Performance (GUP/s)" * **Scale:** Linear scale from 0 to 8, with major tick marks at intervals of 2 (0, 2, 4, 6, 8). * **X-Axis (Horizontal):** * **Categories (Processor Architectures):** Three distinct groups labeled from left to right: "IvyBridge-EP", "KNC", and "Haswell". * **Legend:** * **Position:** Top-right corner of the chart area. * **Entries (with visual encoding):** 1. `icc` - Solid black bar. 2. `OpenMP 4` - Solid red bar. 3. `ISPC` - Black bar with diagonal white stripes (hatching). 4. `Assembly` - Red bar with diagonal white stripes (hatching). ### Detailed Analysis The performance for each compiler/method within each processor category is as follows (values are approximate visual estimates): **1. IvyBridge-EP (Left Group):** * **Trend:** Performance increases from left to right within the group (icc < OpenMP 4 < ISPC < Assembly). * **Data Points:** * `icc` (Solid Black): ~4.5 GUP/s * `OpenMP 4` (Solid Red): ~4.4 GUP/s (marginally lower than icc) * `ISPC` (Striped Black): ~5.3 GUP/s * `Assembly` (Striped Red): ~6.2 GUP/s **2. KNC (Middle Group):** * **Trend:** Performance is highest for Assembly, with ISPC and icc performing similarly, and OpenMP 4 being the lowest in this group. * **Data Points:** * `icc` (Solid Black): ~6.3 GUP/s * `OpenMP 4` (Solid Red): ~5.6 GUP/s * `ISPC` (Striped Black): ~6.2 GUP/s (very close to icc) * `Assembly` (Striped Red): ~8.4 GUP/s (the highest value in the entire chart) **3. Haswell (Right Group):** * **Trend:** All performance values are substantially lower than the other two architectures. The relative order is similar to IvyBridge-EP (Assembly highest, OpenMP 4 lowest). * **Data Points:** * `icc` (Solid Black): ~1.3 GUP/s * `OpenMP 4` (Solid Red): ~1.3 GUP/s (approximately equal to icc) * `ISPC` (Striped Black): ~1.7 GUP/s * `Assembly` (Striped Red): ~2.0 GUP/s ### Key Observations 1. **Dominant Method:** The `Assembly` implementation (striped red bar) delivers the highest performance on all three processor architectures. 2. **Architecture Impact:** The KNC architecture achieves the highest absolute performance values, particularly with Assembly. The Haswell architecture shows a dramatic performance drop (roughly 3-4x lower) compared to IvyBridge-EP and KNC for all tested methods. 3. **Compiler/Method Hierarchy:** A consistent performance hierarchy is visible across architectures: `Assembly` > `ISPC` > `icc` ≈ `OpenMP 4`. The gap between `Assembly` and the others is most pronounced on KNC. 4. **Pattern Consistency:** The striped bars (`ISPC` and `Assembly`) consistently outperform their solid-color counterparts (`icc` and `OpenMP 4`) within each hardware group. ### Interpretation This chart provides a clear technical comparison for performance optimization. The data suggests that for this specific computational workload (measured in GUP/s): * **Low-level optimization matters:** Hand-tuned or highly specialized `Assembly` code provides a significant performance advantage over higher-level compilers (`icc`) and parallel programming models (`OpenMP 4`, `ISPC`). This advantage is not marginal; it represents a 20-50%+ improvement over the next best method in most cases. * **Hardware-software co-design is critical:** The KNC architecture, likely a many-core processor (Intel Xeon Phi), shows the greatest benefit from optimized code, indicating its performance is highly sensitive to software tuning. The poor showing of Haswell could indicate the workload is not well-suited to its architecture, or that the compilers/optimizations used were not effectively targeting its specific features. * **Practical Implication:** For developers seeking maximum performance on these platforms for this type of workload, investing in low-level optimization (Assembly or ISPC) appears justified, especially on KNC hardware. The relatively similar performance of `icc` and `OpenMP 4` suggests that simply enabling OpenMP parallelization without further tuning may not yield benefits over the base compiler for this specific task. **Language Declaration:** All text in the image is in English. </details> sufficient number of warps to choose from when a particular warp stalls. This approach can hide much longer latencies than the 4-way SMT in-order approach of KNC. ## 8. Performance Comparison to Generated Code Figure 3 compares our best implementations on the three platforms with compiler-generated code. We consider three different variants: C code, C code with the #pragma simd directive from the latest OpenMP 4 standard [4], and ISPC [5]. The Intel C compiler version 13.1.3 with optimization flags -O3 -xHost was used on all systems. It is noteworthy that the performance using #pragma simd is worse than without the directive. ISPC (Intel SPMD Program Compiler, Version 1.5.0) is an Open Source implementation of the SPMD programming model. It provides the same performance as the Intel C compiler on KNC but on both CPUs it offers performance superior to that of the commercial Intel compiler. The hand-written assembly kernels outperform compiler-generated code on every architecture. On IvyBridge the AVX version is 10% faster than the ISPC-generated code. The effect is more pronounced on Haswell: Because the ISPC-generated code makes use of the vector gather instruction, the hand-written assembly using pairwise loads is 22% faster. On KNC the Intel compiler provided the fastest auto-vectorized code; the hand-written IMCI version is 34% faster. ## 9. Conclusion We have implemented the RabbitCT benchmark algorithm using different SIMD instruction set extensions and have benchmarked the resulting kernels on three recent Intel x86 architectures. The SIMDinstruction sets exhibit different register widths ranging from 128 to 512 bits. Moreover, A VX2/FMA3 and IMCI provide instructions for vector gather and FMA. Using an instruction code analysis we have shown that it is not efficient to employ wider SIMD widths for this algorithm due to its partially scattered data access pattern. We also show that FMA and gather have a significant impact on the implementation, not only with regard to instruction count but also in terms of simplicity. By far the most compact and straightforward variant is the A VX2/FMA3 kernel. From the ISA point of view we think this is instruction code which is well suited to be automatically generated. We have then benchmarked the kernels to test the hardware implementations. The advantages at the ISA level of the gather-enabled SIMD instruction sets are currently thwarted by inefficient hardware implementations. On KNC and Haswell the current gather throughput is the dominating performance bottleneck for these kernels. An in-detail microbenchmarking analysis on these two systems revealed that the implementations suffer from significant overhead. Another issue is the fact that there is no functional latency hiding for the gather operation on KNC. Still the new instruction sets make it easier for a compiler to generate competitive code. Therefore we think that the problem is solved on the ISA side and the vendors have to provide improved implementations to further increase the benefit of using these instructions. The advantage of GPUs for this algorithm can be explained by the bilinear interpolation being implemented completely in hardware. The second advantage is the more robust and easier to use latency hiding strategies on GPUs compared to the available multi- and many-core architectures. We believe that RabbitCT is a very good benchmarking case to test the efficiency of available instruction sets, code generators, and microarchitectures. Future work will cover the port of our kernels on further SIMD instruction sets such as IBM VSX. ## Acknowledgments We thank IBM Research for giving Jan Treibig the opportunity for a scientific visit at the T.J.Watson Research Center, which was the starting point for this work. Special acknowledgments go to Jose Moreira for fruitful discussions. ## References - [1] B. Heigl and M. Kowarschik. High-speed reconstruction for C-arm computed tomography. In In Proceedings Fully 3D Meeting and HPIR Workshop , pages 25-28, July 2007. - [2] Intel Corporation. Intel R © 64 and IA-32 Architectures Software Developers Manual . Number 325462-048US. September 2013. - [3] M. Kachelriess, M. Knaup, and O. Bockenbach. Hyperfast parallelbeam and cone-beam backprojection using the cell general purpose hardware. Med Phys , 34(4):1474-86, 2007. ISSN 0094-2405. - [4] OpenMP Architecture Review Board. OpenMP Application Program Interface - Version 4.0 . July 2013. - [5] M. Pharr and W. R. Mark. ispc: A SPMD Compiler for HighPerformance CPU Programming. In In Proceedings Innovative Parallel Computing (InPar) , San Jose, CA, May 2012. - [6] G. Pratx and L. Xing. Gpu computing in medical physics: A review. Medical Physics , 38(5):2685-2697, 2011. . URL http://link. aip.org/link/?MPH/38/2685/1 . - [7] C. Rohkohl, B. Keck, H. Hofmann, and J. Hornegger. RabbitCT - an open platform for benchmarking 3D cone-beam reconstruction algorithms. Medical Physics , 36(9):3940-3944, 2009. . - [8] H. Scherl, M. Kowarschik, H. G. Hofmann, B. Keck, and J. Hornegger. Evaluation of state-of-the-art hardware architectures for fast cone-beam ct reconstruction. Parallel Comput. , 38(3):111-124, Mar. 2012. ISSN 0167-8191. . URL http://dx.doi.org/10.1016/j. parco.2011.10.004 . - [9] J. Treibig, G. Hager, and G. Wellein. LIKWID: A lightweight performance-oriented tool suite for x86 multicore environments. In PSTI2010, the First International Workshop on Parallel Software Tools and Tool Infrastructures , pages 207-216, Los Alamitos, CA, USA, 2010. IEEE Computer Society. URL http://dx.doi.org/ 10.1109/ICPPW.2010.38 . - [10] J. Treibig, G. Hager, H. G. Hofmann, J. Hornegger, and G. Wellein. Pushing the limits for medical image reconstruction on recent standard multicore processors. Int. J. High Perform. Comp. Appl. , 27(2):162177, 2013. . - [11] T. Zinsser and B. Keck. Systematic Performance Optimization of Cone-Beam Back-Projection on the Kepler Architecture. In F. committee, editor, Proceedings of the 12th Fully Three-Dimensional Image Reconstruction in Radiology and Nuclear Medicine , page 225228, 2013.