Narrow Results

The usual QR algorithm for finding the eigenvalues of a Hessenberg matrix H is based on vector-vector operations, e.g. adding a multiple of one row to another. The opportunities for parallelism in such an algorithm are limited. In this paper, we describe a reorganization of the QR algorithm to permit either matrix-vector or matrix-matrix operations to be performed, both of which yield more efficient implementations on vector and parallel machines. The idea is to chase a k by k bulge rather than a 1 by 1 or 2 by 2 bulge as in the standard QR algorithm. We report our preliminary numerical experiments on the CONVEX C-1 and CYBER 205 vector machines.

We evaluate the impact of the memory hierarchy of virtual shared memory computers on the design of algorithms for linear algebra. On classical shared memory multiprocessor computers, block algorithms are used for efficiency. We study here the potential and the limitations of such approaches on globally addressable distributed memory computers. The BBN TC2000 belongs to this class of computers and will be used to illustrate our discussion.

We describe the implementation of Level 3 BLAS and examine the performance of some of the LAPACK routines. The impact of the number of processors with respect to the choice of the variants of classical matrix factorizations (for example, KJI, JKI, JIK for the LU factorization) is discussed. We also study the factorization of sparse matrices based on a multifrontal approach. The ideas introduced for the parallelization of full linear algebra codes are applied to the sparse case. We discuss and illustrate the limitations of this approach in sparse multifrontal factorization.

We show that the speed-ups obtained on the BBN TC2000 for the class of methods presented here are comparable to those obtained on more classical shared memory computers, such as the Alliant FX/80, the CRAY-2 and the IBM 3090/VF.

Recently GPUs have acquired the ability to perform fast general purpose computation by running thousands of threads concurrently. This paper presents a new algorithm for dense matrix-vector multiplication on the NVIDIA CUDA architecture. The experiments are conducted on a PC with GeForce 8800GTX and 2.0 GHz Intel Xeon E5335 CPU. The results show that the proposed algorithm runs a maximum of 11.19 times faster than NVIDIA's BLAS library CUBLAS 1.1 on the GPU and 35.15 times faster than the Intel Math Kernel Library 9.1 on a single core x86 with SSE3 SIMD instructions. The performance of Jacobi's iterative method for solving linear equations, which includes the data transfer time between CPU and GPU, shows that the proposed algorithm is practical for real applications.

Multi-core technology is a natural next step in delivering the benefits of Moore's law to computing platforms. On multi-core processors, the performance of many applications would be improved by parallel processing threads of codes using multi-threading techniques. This paper evaluates the performance of the multi-core Intel Xeon processors on the widely used basic linear algebra subprograms (BLAS). On two dual-core Intel Xeon processors with Hyper-Threading technology, our results show that a performance of around 20 GFLOPS is achieved on Level-3 (matrix-matrix operations) BLAS using multi-threading, SIMD, matrix blocking, and loop unrolling techniques. However, on a small size of Level-2 (matrix-vector operations) and Level-1 (vector operations) BLAS, the use of multi-threading technique speeds down the execution because of the thread creation overheads. Thus the use of Intel SIMD instruction set is the way to improve the performance of single-threaded Level-2 (6 GFLOPS) and Level-1 BLAS (3 GFLOPS). When the problem size becomes large (cannot fit in L2 cache), the performance of the four Xeon cores is less than 2 and 1 GFLOPS on Level-2 and Level-1 BLAS, respectively, even though eight threads are executed in parallel on eight logical processors.

The new-generation Sunway supercomputer has ultra-high computing capacity. But due to the unique heterogeneous architecture of the supercomputer, the open-source versions of basic linear algebra subprograms (BLAS) are insufficient for performance or compatibility. In addition, due to the update of the architecture, BLAS based on the previous Sunway could not fully exploit the performance of the successor. To address the challenges, we propose an optimized BLAS on the new-generation Sunway supercomputer in this paper. Specially, for achieving efficient computation, a parallel optimization method based on the new-generation Sunway for the Level-1 BLAS computing between vectors and the Level-2 BLAS computing between vectors and matrices is first proposed. Then, an adaptive scheduling algorithm for various data sizes is proposed, which is used to balance the tasks of core groups. Finally, to achieve highly efficient general matrix multiplication (GEMM) kernels, a parallel optimization method based on the new-generation Sunway for the Level-3 BLAS computing between matrices is proposed, which includes source-level optimization as well as assembly-level optimization. Experimental results show that the memory bandwidth utilization of the optimized Level-1/2 BLAS exceeds 95%, and the computational efficiency of the optimized GEMM kernel exceeds 94%.

ScalaLab is a MATLAB-like environment for the Java Virtual Machine (JVM). ScalaLab is based on the Scala programming language. It utilizes an extensive set of Java and Scala scientific libraries and also has access to many native C/C$++$ scientific libraries by using mainly the Java Native Interface (JNI).

The performance of the JVM platform is continuously improved at a fast pace. Today JVM can effectively support demanding high-performance computing and scales well on multicore platforms. However, sometimes optimized native C/$\mathrm{\text{C}}++$ code can yield even better performance, by exploiting low-level programming issues, such as optimization of caches and architecture-dependent instruction sets.

The present work reports some of the experiences that we gained with experiments with both Just in Time (JIT) JVM code and native code. We compare some aspects of Scala and C$++$ that concern the requirements of scientific computing and highlight some strong features of the Scala language that facilitate the implementation of scientific scripting. This paper describes how ScalaLab tries to combine the best features of the JVM with those of the C/C$++$ technology, in order to implement an effective scientific computing environment.