Scientific Programming - Volume 17, issue 1-2

Authors: Gschwind, Michael | Gustavson, Fred | Prins, Jan F.

Article Type: Other

DOI: 10.3233/SPR-2009-0279

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 1-2, 2009

Authors: Vishwas, B.C. | Gadia, Abhishek | Chaudhuri, Mainak

Article Type: Research Article

Abstract: Matrix factorization (or often called decomposition) is a frequently used kernel in a large number of applications ranging from linear solvers to data clustering and machine learning. The central contribution of this paper is a thorough performance study of four popular matrix factorization techniques, namely, LU, Cholesky, QR and SVD on the STI Cell broadband engine. The paper explores algorithmic as well as implementation challenges related to the Cell chip-multiprocessor and explains how we achieve near-linear speedup on most of the factorization techniques for a range of matrix sizes. For each of the factorization routines, we identify the bottleneck kernels …and explain how we have attempted to resolve the bottleneck and to what extent we have been successful. Our implementations, for the largest data sets that we use, running on a two-node 3.2 GHz Cell BladeCenter (exercising a total of sixteen SPEs), on average, deliver 203.9, 284.6, 81.5, 243.9 and 54.0 GFLOPS for dense LU, dense Cholesky, sparse Cholesky, QR and SVD, respectively. The implementations achieve speedup of 11.2, 12.8, 10.6, 13.0 and 6.2, respectively for dense LU, dense Cholesky, sparse Cholesky, QR and SVD, when running on sixteen SPEs. We discuss the interesting interactions that result from parallelization of the factorization routines on a two-node non-uniform memory access (NUMA) Cell Blade cluster. Show more

Keywords: Parallel matrix factorization, cell broadband engine, scalability, LU, Cholesky, QR, singular value decomposition, new data structures

DOI: 10.3233/SPR-2009-0265

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 3-29, 2009

Authors: Kurzak, Jakub | Dongarra, Jack

Article Type: Research Article

Abstract: The QR factorization is one of the most important operations in dense linear algebra, offering a numerically stable method for solving linear systems of equations including overdetermined and underdetermined systems. Modern implementations of the QR factorization, such as the one in the LAPACK library, suffer from performance limitations due to the use of matrix–vector type operations in the phase of panel factorization. These limitations can be remedied by using the idea of updating of QR factorization, rendering an algorithm, which is much more scalable and much more suitable for implementation on a multi-core processor. It is demonstrated how the potential …of the cell broadband engine can be utilized to the fullest by employing the new algorithmic approach and successfully exploiting the capabilities of the chip in terms of single instruction multiple data parallelism, instruction level parallelism and thread-level parallelism. Show more

Keywords: Cell broadband engine, multi-core, numerical algorithms, linear algebra, matrix factorization

DOI: 10.3233/SPR-2009-0268

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 31-42, 2009

Authors: Kistler, Michael | Gunnels, John | Brokenshire, Daniel | Benton, Brad

Article Type: Research Article

Abstract: In this paper we present the design and implementation of the Linpack benchmark for the IBM BladeCenter QS22, which incorporates two IBM PowerXCell 8i1 processors. The PowerXCell 8i is a new implementation of the Cell Broadband Engine™2 architecture and contains a set of special-purpose processing cores known as Synergistic Processing Elements (SPEs). The SPEs can be used as computational accelerators to augment the main PowerPC processor. The added computational capability of the SPEs results in a peak double precision floating point capability of 108.8 GFLOPS. We explain how we modified the standard open source implementation of Linpack to …accelerate key computational kernels using the SPEs of the PowerXCell 8i processors. We describe in detail the implementation and performance of the computational kernels and also explain how we employed the SPEs for high-speed data movement and reformatting. The result of these modifications is a Linpack benchmark optimized for the IBM PowerXCell 8i processor that achieves 170.7 GFLOPS on a BladeCenter QS22 with 32 GB of DDR2 SDRAM memory. Our implementation of Linpack also supports clusters of QS22s, and was used to achieve a result of 11.1 TFLOPS on a cluster of 84 QS22 blades. We compare our results on a single BladeCenter QS22 with the base Linpack implementation without SPE acceleration to illustrate the benefits of our optimizations. Show more

Keywords: Accelerators, hybrid programming

DOI: 10.3233/SPR-2009-0278

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 43-57, 2009

Authors: Rico, Alejandro | Ramirez, Alex | Valero, Mateo

Article Type: Research Article

Abstract: There is a clear industrial trend towards chip multiprocessors (CMP) as the most power efficient way of further increasing performance. Heterogeneous CMP architectures take one more step along this power efficiency trend by using multiple types of processors, tailored to the workloads they will execute. Programming these CMP architectures has been identified as one of the main challenges in the near future, and programming heterogeneous systems is even more challenging. High-level programming models which allow the programmer to identify parallel tasks, and the runtime management of the inter-task dependencies, have been identified as a suitable model for programming such heterogeneous …CMP architectures. In this paper we analyze the performance of Cell Superscalar, a task-based programming model for the Cell Broadband Engine Architecture, in terms of its scalability to higher number of on-chip processors. Our results show that the low performance of the PPE component limits the scalability of some applications to less than 16 processors. Since the PPE has been identified as the limiting element, we perform a set of simulation studies evaluating the impact of out-of-order execution, branch prediction and larger caches on the task management overhead. We conclude that out-of-order execution is a very desirable feature, since it increases task management performance by 50%. We also identify memory latency as a fundamental aspect in performance, while the working set is not that large. We expect a significant performance impact if task management would run using a fast private memory to store the task dependency graph instead of relying on the cache hierarchy. Show more

Keywords: Scalability, multicore, task-based programming models, Cell BE

DOI: 10.3233/SPR-2009-0269

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 59-76, 2009

Authors: Bellens, Pieter | Perez, Josep M. | Cabarcas, Felipe | Ramirez, Alex | Badia, Rosa M. | Labarta, Jesus

Article Type: Research Article

Abstract: Cell Superscalar's (CellSs) main goal is to provide a simple, flexible and easy programming approach for the Cell Broadband Engine (Cell/B.E.) that automatically exploits the inherent concurrency of the applications at a task level. The CellSs environment is based on a source-to-source compiler that translates annotated C or Fortran code and a runtime library tailored for the Cell/B.E. that takes care of the concurrent execution of the application. The first efforts for task scheduling in CellSs derived from very simple heuristics. This paper presents new scheduling techniques that have been developed for CellSs for the purpose of improving an application's …performance. Additionally, the design of a new scheduling algorithm is detailed and the algorithm evaluated. The CellSs scheduler takes an extension of the memory hierarchy for Cell/B.E. into account, with a cache memory shared between the SPEs. All new scheduling practices have been evaluated showing better behavior of our system. Show more

Keywords: Cell superscalar, task scheduling, Cell/B.E., locality exploitation

DOI: 10.3233/SPR-2009-0272

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 77-95, 2009

Authors: Wirawan, Adrianto | Schmidt, Bertil | Zhang, Huiliang | Kwoh, Chee Keong

Article Type: Research Article

Abstract: The enormous growth of biological sequence databases has caused bioinformatics to be rapidly moving towards a data-intensive, computational science. As a result, the computational power needed by bioinformatics applications is growing rapidly as well. The recent emergence of low cost parallel multicore accelerator technologies has made it possible to reduce execution times of many bioinformatics applications. In this paper, we demonstrate how the Cell Broadband Engine can be used as a computational platform to accelerate two approaches for protein sequence database scanning: exhaustive and heuristic. We present efficient parallelization techniques for two representative algorithms: the dynamic programming based Smith–Waterman algorithm …and the popular BLASTP heuristic. Their implementation on a Playstation® 3 leads to significant runtime savings compared to corresponding sequential implementations. Show more

Keywords: Heterogeneous multi-cores, Cell BE, bioinformatics, dynamic programming, BLAST

DOI: 10.3233/SPR-2009-0274

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 97-111, 2009

Authors: Varbanescu, Ana Lucia | van Amesfoort, Alexander S. | Cornwell, Tim | van Diepen, Ger | van Nieuwpoort, Rob | Elmegreen, Bruce G. | Sips, Henk

Article Type: Research Article

Abstract: The performance potential of the Cell/B.E., as well as its availability, have attracted a lot of attention from various high-performance computing (HPC) fields. While computation intensive kernels proved to be exceptionally well suited for running on the Cell, irregular data-intensive applications are usually considered as poor matches. In this paper, we present our complete solution for enabling such a data-intensive application to run efficiently on the Cell/B.E. processor. Specifically, we target radioastronomy data gridding and degridding, two resembling imaging filters based on convolutional resampling. Our solution is based on building a high-level application model, used to evaluate parallelization alternatives. Next, …we choose the one with the best performance potential, and we gradually exploit this potential by applying platform-specific and application-specific optimizations. After several iterations, our target application shows a speed-up factor between 10 and 20 on a dual-Cell blade when compared with the original application running on a commodity machine. Given these results, and based on our empirical observations, we are able to pinpoint a set of ten guidelines for parallelizing similar applications on the Cell/B.E. Finally, we conclude the Cell/B.E. can provide high performance for data-intensive applications at the price of increased programming efforts and with a significant aid from aggressive application-specific optimizations. Show more

Keywords: Multi-core processors, radioastronomy, data-intensive memory-bound applications, Cell/B.E

DOI: 10.3233/SPR-2009-0276

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 113-134, 2009

Authors: Shi, Guochun | Kindratenko, Volodymyr V. | Ufimtsev, Ivan S. | Martinez, Todd J. | Phillips, James C. | Gottlieb, Steven A.

Article Type: Research Article

Abstract: The Cell Broadband Engine architecture is a revolutionary processor architecture well suited for many scientific codes. This paper reports on an effort to implement several traditional high-performance scientific computing applications on the Cell Broadband Engine processor, including molecular dynamics, quantum chromodynamics and quantum chemistry codes. The paper discusses data and code restructuring strategies necessary to adapt the applications to the intrinsic properties of the Cell processor and demonstrates performance improvements achieved on the Cell architecture. It concludes with the lessons learned and provides practical recommendations on optimization techniques that are believed to be most appropriate.

Keywords: Cell Broadband Engine, molecular dynamics, NAMD, quantum chromodynamics, MILC, quantum chemistry, direct SCF, ERIs

DOI: 10.3233/SPR-2009-0273

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 135-151, 2009

Authors: Ibrahim, Khaled Z. | Bodin, François

Article Type: Research Article

Abstract: Lattice Quantum Chromodynamic (QCD) models subatomic interactions based on a four-dimensional discretized space–time continuum. The Lattice QCD computation is one of the grand challenges in physics especially when modeling a lattice with small spacing. In this work, we study the implementation of the main kernel routine of Lattice QCD that dominates the execution time on the Cell Broadband Engine. We tackle the problem of efficient SIMD execution and the problem of limited bandwidth for data transfers with the off-chip memory. For efficient SIMD execution, we present runtime data fusion technique that groups data processed similarly at runtime. We also …introduce analysis needed to reduce the pressure on the scarce memory bandwidth that limits the performance of this computation. We studied two implementations for the main kernel routine that exhibit different patterns of accessing the memory and thus allowing different sets of optimizations. We show the attributes that make one implementation more favorable in terms of performance. For lattice size that is significantly larger than the local store, our implementation achieves 31.2 GFlops for single precision computations and 16.6 GFlops for double precision computations on the PowerXCell 8i, an order of magnitude better than the performance achieved on most general-purpose processors. Show more

Keywords: Lattice QCD calculations, Cell Broadband Engine, SIMD computer architecture

DOI: 10.3233/SPR-2009-0275

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 153-172, 2009

Authors: Kim, Jusub | JaJa, Joseph

Article Type: Research Article

Abstract: Interactive high quality volume rendering is becoming increasingly more important as the amount of more complex volumetric data steadily grows. While a number of volumetric rendering techniques have been widely used, ray casting has been recognized as an effective approach for generating high quality visualization. However, for most users, the use of ray casting has been limited to datasets that are very small because of its high demands on computational power and memory bandwidth. However the recent introduction of the Cell Broadband Engine (Cell B.E.) processor, which consists of 9 heterogeneous cores designed to handle extremely demanding computations with large …streams of data, provides an opportunity to put the ray casting into practical use. In this paper, we introduce an efficient parallel implementation of volume ray casting on the Cell B.E. The implementation is designed to take full advantage of the computational power and memory bandwidth of the Cell B.E. using an intricate orchestration of the ray casting computation on the available heterogeneous resources. Specifically, we introduce streaming model based schemes and techniques to efficiently implement acceleration techniques for ray casting on Cell B.E. In addition to ensuring effective SIMD utilization, our method provides two key benefits: there is no cost for empty space skipping and there is no memory bottleneck on moving volumetric data for processing. Our experimental results show that we can interactively render practical datasets on a single Cell B.E. processor. Show more

Keywords: Raytracing, parallel processing, Cell B.E

DOI: 10.3233/SPR-2009-0267

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 173-184, 2009

Authors: Araya-Polo, Mauricio | Rubio, Félix | de la Cruz, Raúl | Hanzich, Mauricio | Cela, José María | Scarpazza, Daniele Paolo

Article Type: Research Article

Abstract: Reverse-Time Migration (RTM) is a state-of-the-art technique in seismic acoustic imaging, because of the quality and integrity of the images it provides. Oil and gas companies trust RTM with crucial decisions on multi-million-dollar drilling investments. But RTM requires vastly more computational power than its predecessor techniques, and this has somewhat hindered its practical success. On the other hand, despite multi-core architectures promise to deliver unprecedented computational power, little attention has been devoted to mapping efficiently RTM to multi-cores. In this paper, we present a mapping of the RTM computational kernel to the IBM Cell/B.E. processor that reaches close-to-optimal performance. …The kernel proves to be memory-bound and it achieves a 98% utilization of the peak memory bandwidth. Our Cell/B.E. implementation outperforms a traditional processor (PowerPC 970MP) in terms of performance (with an 15.0× speedup) and energy-efficiency (with a 10.0× increase in the GFlops/W delivered). Also, it is the fastest RTM implementation available to the best of our knowledge. These results increase the practical usability of RTM. Also, the RTM-Cell/B.E. combination proves to be a strong competitor in the seismic arena. Show more

Keywords: Seismic imaging, multi-core, reverse-time migration, performance

DOI: 10.3233/SPR-2009-0271

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 185-198, 2009

Authors: Lubeck, Olaf | Lang, Michael | Srinivasan, Ram | Johnson, Greg

Article Type: Research Article

Abstract: The IBM Cell Broadband Engine (BE) is a novel multi-core chip with the potential for the demanding floating point performance that is required for high-fidelity scientific simulations. However, data movement within the chip can be a major challenge to realizing the benefits of the peak floating point rates. In this paper, we present the results of implementing Sweep3D on the Cell/B.E. using an intra-chip message passing model that minimizes data movement. We compare the advantages/disadvantages of this programming model with a previous implementation using a master–worker threading strategy. We apply a previously validated micro-architecture performance model for the application executing …on the Cell/B.E. (based on our previous work in Monte Carlo performance models), that predicts overall CPI (cycles per instruction), and gives a detailed breakdown of processor stalls. Finally, we use the micro-architecture model to assess the performance of future design parameters for the Cell/B.E. micro-architecture. The methodologies and results have broader implications that extend to multi-core architectures. Show more

Keywords: Cell/B.E. Broadband Engine (CBE), performance modeling, Monte Carlo, Sweep3D

DOI: 10.3233/SPR-2009-0266

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 199-208, 2009

Article Type: Other

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 209-209, 2009

Article Type: Other

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 211-211, 2009

Article Type: Correction

DOI: 10.3233/SPR-2009-0282

Citation: Scientific Programming, vol. 17, no. 1-2, pp. 213-213, 2009