NDLI: Lower Bounds in the Asymmetric External Memory Model

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

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems

Randomized Composable Coresets for Matching and Vertex Cover

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling

Bounding Laconic Proof Systems by Solving CSPs in Parallel

Some Sequential Algorithms are Almost Always Parallel

Distributed Partial Clustering

Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions

Concurrent Data Structures for Near-Memory Computing

Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

Online Tree Caching

Almost Optimal Streaming Algorithms for Coverage Problems

Online Flexible Job Scheduling for Minimum Span

Matrix Multiplication, a Little Faster

Distributed Detection of Cycles

Optimal Reissue Policies for Reducing Tail Latency

Lower Bounds in the Asymmetric External Memory Model

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

Provably Efficient Scheduling of Cache-oblivious Wavefront Algorithms

Bicriteria Distributed Submodular Maximization in a Few Rounds

Minimizing Total Weighted Flow Time with Calibrations

A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem

Distributed Graph Clustering by Load Balancing

Impact of Knowledge on Election Time in Anonymous Networks

Hand-Over-Hand Transactions with Precise Memory Reclamation

Improved Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

On Energy Conservation in Data Centers

Tight Bounds for Clairvoyant Dynamic Bin Packing

Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

Fast Scheduling in Distributed Transactional Memory

Swarm-based Incast Congestion Control in Datacenters Serving Web Applications

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

The Mobile Server Problem

Brief Announcement: Meeting the Challenges of Parallelizing Sequential Programs

Brief Announcement: Scheduling Parallelizable Jobs Online to Maximize Throughput

Brief Announcement: Graph Matching in Massive Datasets

Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation

Brief Announcement: A New Improved Bound for Coflow Scheduling

Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation

Brief Announcement: STAR (Space-Time Adaptive and Reductive) Algorithms for Dynamic Programming Recurrences with more than O(1) Dependency

Brief Announcement: Complete Visibility for Oblivious Robots in Linear Time

Brief Announcement: Extending Transactional Memory with Atomic Deferral

Brief Announcement: Hardware Transactional Storage Class Memory

Lower Bounds in the Asymmetric External Memory Model

Content Provider	ACM Digital Library
Author	Jacob, Riko Sitchinava, Nodari
Abstract	Motivated by the asymmetric read and write costs of emerging non-volatile memory technologies, we study lower bounds for the problems of sorting, permuting and multiplying a sparse matrix by a dense vector in the asymmetric external memory model (AEM). Given an AEM with internal (symmetric) memory of size M, transfers between symmetric and asymmetric memory in blocks of size B and the ratio ω between write and read costs, we show Ω(min (N, ωN/B logω M/B N/B) lower bound for the cost of permuting N input elements. This lower bound also applies to the problem of sorting N elements. This proves that the existing sorting algorithms in the AEM model are optimal to within a constant factor for reasonable ranges of parameters N, M, B, and ω. We also show a lower bound of Ω(min {H, ω H/B logω M/B N/ max{δ ,M}}) for the cost of multiplying an N x N matrix with at most H= δ N non-empty entries by a vector with N elements.
Starting Page	247
Ending Page	254
Page Count	8
File Format	PDF
ISBN	9781450345934
DOI	10.1145/3087556.3087583
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Lower bounds Permuting Asymmetric read-write Sparse matrix vector multiplication Aem Spmxv Asymmetric external memory Nvms Sorting
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