NDLI: Tuning Strassen's matrix multiplication for memory efficiency

Please wait, while we are loading the content...

PDS/PIO: lightweight libraries for collective parallel I/O

Multi-processor performance on the Tera MTA

An initial evaluation of the Tera Multithreaded Architecture and programming system using the C3I parallel benchmark suite

High Performance Simulation of Internal Combustion Engines

A parallel linear algebra server for Matlab-like environments

Multilevel algorithms for multi-constraint graph partitioning

Pthreads for dynamic and irregular parallelism

Communication overlap in multi-tier parallel algorithms

Making sparse Gaussian elimination scalable by static pivoting

The large scale parallelization of a conformational 3D Protein structure prediction application

Real-time image segmentation for image-guided surgery

Highly efficient gang scheduling implementation

The Penn State computing condominium scheduling system

A grid-enabled MPI: message passing in heterogeneous distributed computing systems

Measurement of a scientific workload using the IBM hardware performance monitor

An infrastructure for efficient parallel job execution in Terascale computing environments

QCDSP machines: design, performance and cost

Scientific visualization in the classroom

Modeling orbiting and rotating bodies using VRML

High performance first principles method for complex magnetic properties

A hierarchical load-balancing framework for dynamic multithreaded computations

The UCLA AGCM in high performance computing environments

Adaptive parallel computation of a grand-challenge problem: prediction of the path of a solar-corona mass ejection

Efficient selection algorithms on distributed memory computers

Optimizing software cache-coherent cluster architectures

StarT-Voyager: a flexible platform for exploring scalable SMP issues

Reducing coherence overhead of barrier synchronization in software DSMs

A new Lanczos method for electronic structure calculations

Linger Longer: fine-grain cycle stealing for networks of workstations

Scaling of Beowulf-class distributed systems

Application of a high performance parallel eigensolver to electronic structure calculations

Synchronous learning at a distance: experiences with Tango

New directions for computational science and supercomputing in secondary school

Internet based audiovisual communication tools used in a joint engineering design class at the University of Alabama in Huntsville and the Ecole Superieure et de Construction Automobile (ESTACA) in Paris, France

A proposal for preservice student technology competence

A virtual university as a distributed computing network

Avalon: an Alpha/Linux cluster achieves 10 Gflops for \$15k

A case for using MPI's derived datatypes to improve I/O performance

Techniques for speculative run-time parallelization of loops

An implementation and analysis of the virtual interface architecture

MPI-StarT: delivering network performance to numerical applications

High performance multidimensional analysis and data mining

A prototype notebook-based environment for computational tools

Dynamic repartitioning of adaptively refined meshes

Supporting runtime tool interaction for parallel simulations

Automatically tuned linear algebra software

An out-of-core implementation of the COLUMBUS massively-parallel multireference configuration interaction program

A parallel rendezvous algorithm for interpolation between multiple grids

3D in the Pines and on the Plains

Secondary Science & Mathematics Teachers Communicating Using Collaborative Tools via Distance Learning Technology: hands-on session

Building the infrastructure for high performance computing in undergraduate curricula: ten Grand Challenges and the response of the NPACI education center

TFLOPS PFS: architecture and design of a highly efficient parallel file system

Efficient algorithms for block-cyclic array redistribution between processor sets

High performance Fortran compilation techniques for parallelizing scientific codes

Overture: an object-oriented framework for high performance scientific computing

Agent middleware for heterogeneous scientific simulations

User-space communication: a quantitative study

Analyzing the error bounds of multipole-based treecodes

CCF: Collaborative Computing Frameworks

A collaborative framework for distributed microscopy

S-HARP: a scalable parallel dynamic partitioner for adaptive mesh-based computations

OpenMP on networks of workstations

Tuning Strassen's matrix multiplication for memory efficiency

A scalable and highly available system for serving dynamic data at frequently accessed web sites

WebFlow: high-level programming environment and visual authoring toolkit for high performance distributed computing

Accurate performance evaluation, modelling and prediction of a message passing simulation code based on middleware

The RiverWeb Toolsuite™: bridging the gap between high-end environmental science and the classroom

REU PACI---undergraduate student research experiences

Using high performance GIS software to visualize data: a hands-on software demonstration

A comparison of automatic parallelization tools/compilers on the SGI origin 2000

Training teachers to use information technology to support integrated instruction: what teacher trainers learned from their students

Every picture tells a story: learning to look at space scientific data images

Tuning Strassen's matrix multiplication for memory efficiency

Content Provider	ACM Digital Library
Author	Lebeck, Alvin R. Chatterjee, Siddhartha Thottethodi, Mithuna
Abstract	Strassen's algorithm for matrix multiplication gains its lower arithmetic complexity at the expense of reduced locality of reference, which makes it challenging to implement the algorithm efficiently on a modern machine with a hierarchical memory system. We report on an implementation of this algorithm that uses several unconventional techniques to make the algorithm memory-friendly. First, the algorithm internally uses a non-standard array layout known as Morton order that is based on a quad-tree decomposition of the matrix. Second, we dynamically select the recursion truncation point to minimize padding without affecting the performance of the algorithm, which we can do by virtue of the cache behavior of the Morton ordering. Each technique is critical for performance, and their combination as done in our code multiplies their effectiveness.Performance comparisons of our implementation with that of competing implementations show that our implementation often outperforms the alternative techniques (up to 25%). However, we also observe wide variability across platforms and across matrix sizes, indicating that at this time, no single implementation is a clear choice for all platforms or matrix sizes. We also note that the time required to convert matrices to/from Morton order is a noticeable amount of execution time (5% to 15%). Eliminating this overhead further reduces our execution time.
Starting Page	1
Ending Page	14
Page Count	14
File Format	HTM / HTML
ISBN	089791984X
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1998-11-07
Access Restriction	Subscribed
Subject Keyword	Matrix multiply Strassen's algorithm Cache memory Data layout
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in