4.5 Article

Coded Sparse Matrix Computation Schemes That Leverage Partial Stragglers

相关参考文献

注意:仅列出部分参考文献,下载原文获取全部文献信息。
Article Computer Science, Information Systems

Hierarchical Coded Matrix Multiplication

Shahrzad Kianidehkordi et al.

Summary: This paper introduces hierarchical coded computing that leverages the work completed by all nodes in a distributed system, automatically integrating the potential contribution of each node. Three methods are developed in this paradigm, enabling the system to use partial work completed by slower nodes, and potentially accelerate the overall computation process. Under a widely studied statistical model, the approach shows a 66% improvement in the expected finishing time, with a 27% gain observed on Amazon EC2 when simulating stragglers.

IEEE TRANSACTIONS ON INFORMATION THEORY (2021)

Article Computer Science, Information Systems

Efficient and Robust Distributed Matrix Computations via Convolutional Coding

Anindya Bijoy Das et al.

Summary: In distributed matrix computations, the problem of stragglers can be addressed by a convolutional coding approach that offers optimal straggler resilience and numerical robustness. Another approach with slightly higher decoding complexity allows operation close to the storage capacity lower bound while its numerical robustness can be quantified theoretically. Extensive experiments on the AWS cloud platform support these claims.

IEEE TRANSACTIONS ON INFORMATION THEORY (2021)

Proceedings Paper Computer Science, Theory & Methods

Adaptive Coding for Matrix Multiplication at Edge Networks

Elahe Vedadi et al.

Summary: Edge computing is a new paradigm that allows processing data at the edge of the network, exploiting multiple devices collectively. The heterogeneous and time-varying nature of edge devices makes exploiting the potential of edge computing challenging. Coded computation, which mixes data in sub-tasks using erasure codes, is gaining interest due to its reliability, lower delay, and communication cost. The focus of this paper is on characterizing the cost-benefit trade-offs of coded computation for practical edge computing systems, and developing an adaptive coded computation framework, particularly for matrix multiplication tasks. This framework, called ACM(2), dynamically selects coding policies based on computing time, storage requirements, and successful decoding probability to significantly improve task completion delay compared to existing algorithms.

2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2021)

Proceedings Paper Computer Science, Theory & Methods

Speeding Up Private Distributed Matrix Multiplication via Bivariate Polynomial Codes

Burak Hasircioglu et al.

Summary: This work proposes a method that utilizes bivariate polynomial codes to accelerate private distributed matrix multiplication, which reduces the average computation time and improves the upload communication cost and workers' storage efficiency compared to existing methods.

2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2021)

Proceedings Paper Computer Science, Theory & Methods

Numerically stable coded matrix computations via circulant and rotation matrix embeddings

Aditya Ramamoorthy et al.

Summary: The paper introduces a novel coded computation approach that leverages circulant permutation and rotation matrices to mitigate the effect of stragglers in distributed matrix computations. This approach has an optimal recovery threshold and an upper bound on the worst case condition number, showing significant improvement compared to prior work.

2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2021)

Article Computer Science, Information Systems

On the Optimal Recovery Threshold of Coded Matrix Multiplication

Sanghamitra Dutta et al.

IEEE TRANSACTIONS ON INFORMATION THEORY (2020)

Article Computer Science, Information Systems

Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding

Qian Yu et al.

IEEE TRANSACTIONS ON INFORMATION THEORY (2020)

Article Engineering, Electrical & Electronic

Straggler-Resistant Distributed Matrix Computation via Coding Theory: Removing a Bottleneck in Large-Scale Data Processing

Aditya Ramamoorthy et al.

IEEE SIGNAL PROCESSING MAGAZINE (2020)

Article Computer Science, Hardware & Architecture

Resolvable Designs for Speeding Up Distributed Computing

Konstantinos Konstantinidis et al.

IEEE-ACM TRANSACTIONS ON NETWORKING (2020)

Proceedings Paper Computer Science, Theory & Methods

Product Lagrange Coded Computing

Adarsh M. Subramaniam et al.

2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2020)

Proceedings Paper Computer Science, Artificial Intelligence

Bivariate Hermitian Polynomial Coding for Efficient Distributed Matrix Multiplication

Burak Hasircioglu et al.

2020 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM) (2020)

Article Computer Science, Theory & Methods

Private and Secure Distributed Matrix Multiplication With Flexible Communication Load

Malihe Aliasgari et al.

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY (2020)

Article Telecommunications

Erasure Coding for Distributed Matrix Multiplication for Matrices With Bounded Entries

Li Tang et al.

IEEE COMMUNICATIONS LETTERS (2019)

Proceedings Paper Computer Science, Information Systems

Universally Decodable Matrices for Distributed Matrix-Vector Multiplication

Aditya Ramamoorthy et al.

2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2019)

Proceedings Paper Computer Science, Information Systems

Distributed Matrix-Vector Multiplication: A Convolutional Coding Approach

Anindya B. Das et al.

2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2019)

Proceedings Paper Computer Science, Information Systems

Numerically Stable Polynomially Coded Computing

Mohammad Fahim et al.

2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) (2019)

Proceedings Paper Automation & Control Systems

Random Khatri-Rao-Product Codes for Numerically-Stable Distributed Matrix Multiplication

Adarsh M. Subramaniam et al.

2019 57TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON) (2019)

Article Computer Science, Hardware & Architecture

Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication

Ankur Mallick et al.

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS (2019)

Article Computer Science, Information Systems

Sum-Networks From Incidence Structures: Construction and Capacity Analysis

Ardhendu Tripathy et al.

IEEE TRANSACTIONS ON INFORMATION THEORY (2018)

Article Computer Science, Information Systems

Speeding Up Distributed Machine Learning Using Codes

Kangwook Lee et al.

IEEE TRANSACTIONS ON INFORMATION THEORY (2018)

Article Computer Science, Information Systems

Fractional Repetition Codes With Flexible Repair From Combinatorial Designs

Oktay Olmez et al.

IEEE TRANSACTIONS ON INFORMATION THEORY (2016)

Article Computer Science, Information Systems

On the existence of universally decodable matrices

Ashwin Ganesan et al.

IEEE TRANSACTIONS ON INFORMATION THEORY (2007)