Sparse Computations: Better, Faster, Cheaper! Padma Raghavan Department

Sparse Computations: Better, Faster, Cheaper! Padma Raghavan Department

Sparse Computations: Better, Faster, Cheaper!
Padma Raghavan
Department of Computer Science and Engineering, The Pennsylvania State University
[email protected]

Challenges in Processing
High Dimensional Sparse Data

User

Will my application speed-up, compute high quality solutions?

Can I make sparse codes better, faster, cheaper?
One sparse dataset: 3 forms
Matrix
Graph
Mesh
Algebraic Combinatorial Geometry

WHERE DOES SPARSITY COME FROM?
WHAT IS SPARSITY?
Consider N interacting variables
NxN pair-wise interactions
Dense:
elements, NxN
matrix/array
Sparse: c N elements, c is a small
number

Developer

SPARSITY PROPERTIES
Compact representation
Memory and computational
cost scaling
O(N) per sweep through data

Graph

Discretization

Data mining
Approximations

Matrix

Issue: Can we transform data for BETTER
classification?
Focus: Quality of classification
Method: Feature subspace transformation (FST)
by force-directed graph embedding. Apply KMeans on transformed data (FST K-Means)

Issue: Can we make sparse matrix vector
multiplication (SMV) FASTER on multicores?
Focus: Performance
Method: Identify and use smaller dense submatrices hidden in the sparse matrix -- Sparsityexploiting effectively dense (SpEED-SMV )
Obtaining a supernodal ordered matrix

Mesh

Issue: Can we schedule for energy efficiency
(CHEAPER)?
Focus: Reduce energy delay product (EDP)
Method: Dynamic scheduling with helper threads
that learn application profile to select number of
cores, threads and voltage/frequency levels
EnergyDelayProduct [EDP]
(Energy X Time) is lower
for faster system A

Run away
leakage on idle
cores
Thermal
emergencies
Transient errors

Ordering supernodal matrix using RCM ordering scheme

Decreasing memory loads by reducing index overheads
Classification Accuracy (P)

Classification Accuracy (P)

100
90
80
70
60

Total number of documents

FST-K-Means improves the
classification accuracy of 5 out of
8 datasets.

50
Percent

P
N

Number of correctly classified
documents

K-Means
GraClus
FST-K-Means

40
30
20

J ( M1 , M 2 M k )

M

ij

w1

M ij M1

Helper threads recipe
Collect performance/energy
statistics as the execution
progresses
Calculate EDP values
Use data fitting with
available data and interpolate
to predict configuration

10
0

a
n
er
a2
lia
nc
a
t_
a
r
l
u
st
t-c
ad
au
as
e
br

a
dn

e
lic
sp

0
18

t
tx

0
30

t
tx

Performance comparison: SpEED-SMV vs. RxC-SMV

Data Sets

Cluster Cohesiveness (J)
2

B

M

ij

wk

2

M ij M k

jth document of cluster Mi

Centroid of cluster
Mk
Best EDP adaptivity?

Cluster Cohesiveness (J)
90,000

Monitor- ModelAdapt

80,000
70,000
60,000
50,000
Cohesiveness

FST-K-Means improves the
cluster cohesiveness for K-Means
and is competitive with GraClus on
the benchmark datasets.

K-Means
GraClus
FST-K-Means

40,000
30,000
20,000
10,000
0

r
a
a
n
ce
a2
lia
dn
n
a
a
a
r
a2
st
t-c
lt_
au
as
Data Sets
u
e
ad
br

sp

e
lic

18

xt
0t

30

xt
0t

Anirban Chatterjee, Sanjukta Bhowmick, Padma Raghavan: Feature subspace transformations
for enhancing k-means clustering. CIKM 2010: 1801-1804

SpEED-SMV improves the performance of SMV by as much as
59.35% and 50.32%, and on average, 37.35% and 6.07%, compared
to traditional compressed sparse row and blocked compressed
sparse row schemes
Manu Shantharam, Anirban Chatterjee, Padma Raghavan: Exploiting dense substructures for fast
sparse matrix vector multiplication. IJHPCA 25(3): 328-341 (2011)

Achieve up to 66:3% and 83:3% savings in EDP when adjusting
all the parameters properly in applications FFT and MG, respectively
Yang Ding, Mahmut T. Kandemir, Padma Raghavan, Mary Jane Irwin: A helper thread based EDP
reduction scheme for adapting application execution in CMPs. IPDPS 2008: 1-14

Software for sparse computations can deliver high quality solutions that are scalable and energy efficient by exploiting latent structure in the data and adapting to
match hardware attributes
This research was funded in part by the NSF Grants CSR-SMA 0720769, CCF 0830679 and OCI 0821527

Recently Viewed Presentations

  • County Profiles - Indiana

    County Profiles - Indiana

    Asthma hospitalizations and ED visits were defined as a primary diagnosis asthma encounter using ICD-9-CM diagnosis code 493 (inclusive) for an Indiana resident (all ages) discharged from an Indiana hospital/emergency department during the 2014 calendar year (January 1, 2014 to...
  • ZoomWV: The single source for Pre-K through Grade

    ZoomWV: The single source for Pre-K through Grade

    ZoomWV: The single source for Pre-K through Grade 12 education information.. Provide high-level overview and explanation of what ZoomWV is: Single source for PK-12 education information in West Virginia. Reporting tools to support decision making
  • A. Gears - الصفحات الشخصية | الجامعة ...

    A. Gears - الصفحات الشخصية | الجامعة ...

    A. Gears. Gear wheels, or gears, are wheels with teeth (or cogs).The teeth interlock (fit together) with those of other gear wheels. When one gear wheel revolves, the other revolves with it - in the opposite direction - as their...
  • University of Southern Denmark - ISUAbroad

    University of Southern Denmark - ISUAbroad

    Uxbridge also houses the Battle of Britain Bunker, from where the air defense of the south-east of England was coordinated during the Battle of Britain. Situated in RAF Uxbridge, the No. 11 Group Operations Room within the bunker took on...
  • CSCE 330 Programming Language Structures

    CSCE 330 Programming Language Structures

    Times New Roman Arial Tw Cen MT Baskerville Old Face 330Lect1 Microsoft Photo Editor 3.0 Photo CSCE 390 Professional Issues in Computer Science and Engineering Ch.8: The Computing Field as a Profession Expert Knowledge Autonomy Internal Governance Service to Society...
  • Anglicare Australia conference 2017

    Anglicare Australia conference 2017

    Hart's Ladder of Participation. How Did the eastern Melbourne region become an advocate for youth voice? Outer East Child and Youth Area Partnerships. The Outer East Child and Youth Area Partnership is a collaborative model of governance to help drive...
  • Type 2 Diabetes Management Goals - outpatient.aace.com

    Type 2 Diabetes Management Goals - outpatient.aace.com

    Increase in Diabetes Parallels the Increase in Obesity in the United States *BMI ≥30 kg/m2. CDC. National diabetes statistics report, 2014. Atlanta, GA: US Department of Health and Human Services, Centers for Disease Control and Prevention, 2014.Mokdad AH, et al.
  • The Outsiders - Liberty Hill J High School

    The Outsiders - Liberty Hill J High School

    The Outsiders. Vocabulary Warm-Up. Section 1. ... Feeling that you don't like or trust something . Aloof. Acting distant, indifferent. Rivalry. Competitionover a long period of time ... Now use your own words to fill in the sentence under the...