[Crib-list] SPEAKER: Peter James Ahrens (MIT) / CRIBB Seminar / Friday, May 7, 2021 / TIME: 12:00 PM - 1:00 PM / (ZOOM Info below)

[Shirley Entzminger]

 		   COMPUTATIONAL RESEARCH in BOSTON and BEYOND SEMINAR
                                            (CRIBB)


ZOOM MEETING info:

 	https://mit.zoom.us/j/96155042770

 	Meeting ID: 961 5504 2770

-------------------------------------------------

DATE:	Friday, May 7, 2021

TIME:	12:00 Noon to 1:00 PM


TItLE:  On Optimal Partitioning for Variable Block Row Format


SPEAKER: Peter James Ahrens  (MIT)


ABSTRACT:

The Variable Block Row (VBR) format is an influential blocked sparse 
matrix format designed for matrices with shared sparsity structure between 
adjacent rows and columns. VBR groups adjacent rows and columns, storing 
the resulting blocks that contain nonzeros in a dense format. This reduces 
the memory footprint and enables optimizations such as register blocking 
and instruction-level parallelism. Existing approaches use heuristics to 
determine which rows and columns should be grouped together. We show that 
finding the optimal grouping of rows and columns for VBR is NP-hard under 
several reasonable cost models. In light of this finding, we propose a 
1-dimensional variant of VBR, called 1D-VBR, which achieves better 
performance than VBR by only grouping rows. We describe detailed cost 
models for runtime and memory consumption. Then, we describe a linear time 
dynamic programming solution for optimally grouping the rows for 1D-VBR 
format. We extend our algorithm to produce a heuristic VBR partitioner 
which alternates between optimally partitioning rows and columns, assuming 
the columns or rows to be fixed, respectively. Our alternating heuristic 
produces VBR matrices with the smallest memory footprint of any 
partitioner we tested.

BIO:

Peter Ahrens is a DOE CSGF (Computational Science Graduate Fellow) at MIT 
working with Professor Saman Amarasinghe. Peter focuses on problems of 
efficiently allocating machine resources to sparse computations.

================================================

Massachusetts Institute of Technology
Cambridge, MA  02139


For information about the CRIBB Seminar, please visit:

 	https://math.mit.edu/sites/crib/


Seminar will be virtual.  ZOOM Info is at the top of this page, on the attached
poster and on the CRIBB website:


Please contact me if you have any questions.

===

Shirley A. Entzminger
Administrative Assistant II
Department of Mathematics
Massachusetts Institute of Technology
77 Massachusetts Avenue
Building 2, Room 350A
Cambridge, MA 02139
PHONE: 	(617) 253-4994
E-mail:	daisymae at math.mit.edu
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CRIBB Seminar Spk, Peter James Ahrens (MIT) -- Friday, May 7, 	2021.pdf
Type: application/pdf
Size: 174852 bytes
Desc: 
Url : http://mailman.mit.edu/pipermail/crib-list/attachments/20210503/f7722b3d/attachment.pdf