SCHEDULE: NOV 10-16, 2012
When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.
Communication-Avoiding Parallel Strassen - Implementation and Performance
SESSION: Linear Algebra Algorithms
EVENT TYPE: Papers
TIME: 4:00PM - 4:30PM
SESSION CHAIR: X. Sherry Li
AUTHOR(S):Benjamin Lipshitz, Grey Ballard, Oded Schwartz, James Demmel
ROOM:355-D
ABSTRACT:
Matrix multiplication is a fundamental kernel of many high performance and scientific computing applications. Most parallel implementations use classical $O(n^3)$ matrix multiplication, even though there exist algorithms with lower arithmetic complexity. We recently presented a new Communication-Avoiding Parallel Strassen algorithm (CAPS), based on Strassen's fast matrix multiplication, that minimizes communication (SPAA '12). It communicates asymptotically less than all classical and all previous Strassen-based algorithms, and it attains theoretical lower bounds.
In this paper we show that CAPS is also faster in practice. We benchmark and compare its performance to previous algorithms on Hopper (Cray XE6), Intrepid (IBM BG/P), and Franklin (Cray XT4). We demonstrate significant speedups over previous algorithms both for large matrices and for small matrices on large numbers of processors. We model and analyze the performance of CAPS and predict its performance on future exascale platforms.
Chair/Author Details:
X. Sherry Li (Chair) - Lawrence Berkeley National Laboratory
Benjamin Lipshitz - University of California, Berkeley
Grey Ballard - University of California, Berkeley
Oded Schwartz - University of California, Berkeley
James Demmel - University of California, Berkeley
Click here to download .ics calendar file
Click here to download .vcs calendar file
Click here to add event to your Google Calendar
Communication-Avoiding Parallel Strassen - Implementation and Performance
SESSION: Linear Algebra Algorithms
EVENT TYPE:
TIME: 4:00PM - 4:30PM
SESSION CHAIR: X. Sherry Li
AUTHOR(S):Benjamin Lipshitz, Grey Ballard, Oded Schwartz, James Demmel
ROOM:355-D
ABSTRACT:
Matrix multiplication is a fundamental kernel of many high performance and scientific computing applications. Most parallel implementations use classical $O(n^3)$ matrix multiplication, even though there exist algorithms with lower arithmetic complexity. We recently presented a new Communication-Avoiding Parallel Strassen algorithm (CAPS), based on Strassen's fast matrix multiplication, that minimizes communication (SPAA '12). It communicates asymptotically less than all classical and all previous Strassen-based algorithms, and it attains theoretical lower bounds.
In this paper we show that CAPS is also faster in practice. We benchmark and compare its performance to previous algorithms on Hopper (Cray XE6), Intrepid (IBM BG/P), and Franklin (Cray XT4). We demonstrate significant speedups over previous algorithms both for large matrices and for small matrices on large numbers of processors. We model and analyze the performance of CAPS and predict its performance on future exascale platforms.
Chair/Author Details:
X. Sherry Li (Chair) - Lawrence Berkeley National Laboratory
Benjamin Lipshitz - University of California, Berkeley
Grey Ballard - University of California, Berkeley
Oded Schwartz - University of California, Berkeley
James Demmel - University of California, Berkeley
Click here to download .ics calendar file