text: Achieving high efficiency with numerical kernels for sparse matrices is of utmost importance, since they are part of many simulation codes and tend to use most of the available compute time and resources. In addition, especially in large scale simulation frameworks the readability and ease of use of mathematical expressions are essential components for the continuous maintenance, modification, and extension of software. In this context, the sparse matrix-matrix multiplication is of special interest. In this paper we thoroughly analyze the single-core performance of sparse matrix-matrix multiplication kernels in the Blaze Smart Expression Template (SET) framework. We develop simple models for estimating the achievable maximum performance, and use them to assess the efficiency of our implementations. Additionally, we compare these kernels with several commonly used SET-based C++ libraries, which, just as Blaze, aim at combining the requirements of high performance with an elegant user interface. For the different sparse matrix structures considered here, we show that our implementations are competitive or faster than those of the other SET libraries for most problem sizes on a current Intel multicore processor.
  @cite_8: The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. Its modification, the BSPRAM model, allows one to combine the advantages of distributed and shared-memory style programming. In this paper we study the BSP memory complexity of matrix multiplication. We propose new memory-efficient BSP algorithms both for standard and for fast matrix multiplication. The BSPRAM model is used to simplify the description of the algorithms. The communication and synchronization complexity of our algorithms is slightly higher than that of known time-efficient BSP algorithms. The current time-efficient and new memory-efficient algorithms are connected by a continuous tradeoff.
  @cite_3: Parallel algorithms for sparse matrix-matrix multiplication typically spend most of their time on inter-processor communication rather than on computation, and hardware trends predict the relative cost of communication will only increase. Thus, sparse matrix multiplication algorithms must minimize communication costs in order to scale to large processor counts. In this paper, we consider multiplying sparse matrices corresponding to Erdős-Renyi random graphs on distributed-memory parallel machines. We prove a new lower bound on the expected communication cost for a wide class of algorithms. Our analysis of existing algorithms shows that, while some are optimal for a limited range of matrix density and number of processors, none is optimal in general. We obtain two new parallel algorithms and prove that they match the expected communication cost lower bound, and hence they are optimal.
  @cite_0: The effect of harmonic excitation on suspension bridges is examined as a first step towards the understanding of wind excitation upon such structures. The simplest asymmetric oscillator model is studied systematically and an unexpectedly rich dynamical structure is revealed. The methodology employed has been previously applied to models of rocking blocks and other free-standing rigid structures. Conditions for the existence of asymptotic periodic responses can be established; and a two part Poincare map is used to study the orbital stability of such solutions. Numerical results are reviewed which illustrate multiple coexistence of sub- and superharmonics over broad intervals of forcing and frequency. Observed dynamics include fold and flip bifurcations, (truncated and reversed) period doublings, and period adding. Numerical solutions are obtained via direct simulation, and as Poincare map fixed points under parameter continuation using the package AUT094. The results illustrate the possibility of the coexistence of 'dangerous' large amplitude (nonlinear) responses at the same point of parameter space as 'safe' (linear) solutions.
  @cite_2: We evaluate optimized parallel sparse matrix-vector operations for several representative application areas on widespread multicore-based cluster configurations. First the single-socket baseline performance is analyzed and modeled with respect to basic architectural properties of standard multicore chips. Beyond the single node, the performance of parallel sparse matrix-vector operations is often limited by communication overhead. Starting from the observation that nonblocking MPI is not able to hide communication cost using standard MPI implementations, we demonstrate that explicit overlap of communication and computation can be achieved by using a dedicated communication thread, which may run on a virtual core. Moreover we identify performance benefits of hybrid MPI OpenMP programming due to improved load balancing even without explicit communication overlap. We compare performance results for pure MPI, the widely used "vector-like" hybrid programming strategies, and explicit overlap on a modern multicore-based cluster and a Cray XE6 system.
  @cite_12: We are witnessing a dramatic change in computer architecture due to the multicore paradigm shift, as every electronic device from cell phones to supercomputers confronts parallelism of unprecedented scale. To fully unleash the potential of these systems, the HPC community must develop multicore specific-optimization methodologies for important scientific computations. In this work, we examine sparse matrix-vector multiply (SpMV) - one of the most heavily used kernels in scientific computing - across a broad spectrum of multicore designs. Our experimental platform includes the homogeneous AMD quad-core, AMD dual-core, and Intel quad-core designs, the heterogeneous STI Cell, as well as one of the first scientific studies of the highly multithreaded Sun Victoria Falls (a Niagara2 SMP). We present several optimization strategies especially effective for the multicore environment, and demonstrate significant performance improvements compared to existing state-of-the-art serial and parallel SpMV implementations. Additionally, we present key insights into the architectural trade-offs of leading multicore design strategies, in the context of demanding memory-bound numerical algorithms.
summary: Much work has been devoted to sparse matrix based algorithms and efficient implementations in the past. However, most publications deal with parallel sparse matrix-vector multiplication @cite_0 @cite_12 @cite_2 , since it is of pivotal importance in solving sparse linear systems and sparse eigenvalue problems. While there has also been substantial work on sparse matrix-matrix multiplication, it mostly deals with execution and communication efficiency in the parallel case @cite_8 @cite_3 . Here, however, we only cover the sequential kernel any try to understand its features in a well-defined setting, and especially in the context of SET frameworks. Consequently, issues of load and communication balancing, which would be crucial in the parallel case, do not arise.