The Experts below are selected from a list of 18996 Experts worldwide ranked by ideXlab platform
Syed A Jafar - One of the best experts on this subject based on the ideXlab platform.
-
cross subspace alignment codes for coded distributed batch computation
IEEE Transactions on Information Theory, 2021Co-Authors: Zhuqing Jia, Syed A JafarAbstract:The goal of coded distributed computation is to efficiently distribute a computation task, such as matrix multiplication, $N$ -linear computation, or multivariate Polynomial Evaluation, across $S$ servers through a coding scheme, such that the response from any $R$ servers ( $R$ is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current state-of-art approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC) for $N$ -linear computations or multivariate Polynomial Evaluations). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of secure and private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes are shown to unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general in download-limited settings. While matrix-partitioning approaches (EP codes) for distributed matrix multiplication have the advantage of flexible server computation latency, batch processing approaches (CSA, LCC) have significant advantages in communication costs as well as encoding and decoding complexity per matrix multiplication. In order to combine the benefits of these approaches, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches and demonstrate synergistic gains due to cross subspace alignment. Finally, we introduce $N$ -CSA codes for $N$ -linear distributed batch computations and multivariate batch Polynomial Evaluations. $N$ -CSA codes include LCC codes as a special case, and are in general capable of outperforming LCC codes in download-constrained settings by upto a factor of $N$ . Generalizations of $N$ -CSA codes to include $X$ -secure data and $B$ -byzantine servers are also provided.
-
cross subspace alignment codes for coded distributed batch computation
arXiv: Information Theory, 2019Co-Authors: Zhuqing Jia, Syed A JafarAbstract:Coded distributed batch computation distributes a computation task, such as matrix multiplication, $N$-linear computation, or multivariate Polynomial Evaluation, across $S$ servers through a coding scheme, such that the response from any $R$ servers ($R$ is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC)). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general over strictly download-limited settings. Next, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches. Finally, we introduce $N$-CSA codes for $N$-linear distributed batch computations and multivariate batch Polynomial Evaluations. $N$-CSA codes include LCC codes as a special case, and are in general capable of achieving significantly lower downloads than LCC codes due to cross-subspace alignment. Generalizations of $N$-CSA codes to include $X$-secure data and $B$-byzantine servers are also obtained.
Zhuqing Jia - One of the best experts on this subject based on the ideXlab platform.
-
cross subspace alignment codes for coded distributed batch computation
IEEE Transactions on Information Theory, 2021Co-Authors: Zhuqing Jia, Syed A JafarAbstract:The goal of coded distributed computation is to efficiently distribute a computation task, such as matrix multiplication, $N$ -linear computation, or multivariate Polynomial Evaluation, across $S$ servers through a coding scheme, such that the response from any $R$ servers ( $R$ is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current state-of-art approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC) for $N$ -linear computations or multivariate Polynomial Evaluations). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of secure and private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes are shown to unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general in download-limited settings. While matrix-partitioning approaches (EP codes) for distributed matrix multiplication have the advantage of flexible server computation latency, batch processing approaches (CSA, LCC) have significant advantages in communication costs as well as encoding and decoding complexity per matrix multiplication. In order to combine the benefits of these approaches, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches and demonstrate synergistic gains due to cross subspace alignment. Finally, we introduce $N$ -CSA codes for $N$ -linear distributed batch computations and multivariate batch Polynomial Evaluations. $N$ -CSA codes include LCC codes as a special case, and are in general capable of outperforming LCC codes in download-constrained settings by upto a factor of $N$ . Generalizations of $N$ -CSA codes to include $X$ -secure data and $B$ -byzantine servers are also provided.
-
cross subspace alignment codes for coded distributed batch computation
arXiv: Information Theory, 2019Co-Authors: Zhuqing Jia, Syed A JafarAbstract:Coded distributed batch computation distributes a computation task, such as matrix multiplication, $N$-linear computation, or multivariate Polynomial Evaluation, across $S$ servers through a coding scheme, such that the response from any $R$ servers ($R$ is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC)). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general over strictly download-limited settings. Next, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches. Finally, we introduce $N$-CSA codes for $N$-linear distributed batch computations and multivariate batch Polynomial Evaluations. $N$-CSA codes include LCC codes as a special case, and are in general capable of achieving significantly lower downloads than LCC codes due to cross-subspace alignment. Generalizations of $N$-CSA codes to include $X$-secure data and $B$-byzantine servers are also obtained.
Guillaume Revy - One of the best experts on this subject based on the ideXlab platform.
-
Range reduction based on Pythagorean triples for trigonometric function Evaluation
2015 IEEE 26th International Conference on Application-specific Systems Architectures and Processors (ASAP), 2015Co-Authors: Hugues De Lassus Saint-geniès, David Defour, Guillaume RevyAbstract:Software Evaluation of elementary functions usually requires three steps: a range reduction, a Polynomial Evaluation, and a reconstruction step. These Evaluation schemes are designed to give the best performance for a given accuracy, which requires a fine control of errors. One of the main issues is to minimize the number of sources of error and/or their influence on the final result. The work presented in this article addresses this problem as it removes one source of error for the Evaluation of trigonometric functions. We propose a method that eliminates rounding errors from tabulated values used in the second range reduction for the sine and cosine Evaluation. When targeting correct rounding, we show that such tables are smaller and make the reconstruction step less expensive than existing methods. This approach relies on Pythagorean triples generators. Finally, we show how to generate tables indexed by up to 10 bits in a reasonable time and with little memory consumption.
-
automatic generation of fast and certified code for Polynomial Evaluation
Symposium on Computer Arithmetic, 2011Co-Authors: Christophe Mouilleron, Guillaume RevyAbstract:Designing an efficient floating-point implementation of a function based on Polynomial Evaluation requires being able to find an accurate enough Evaluation code, exploiting at most the target architecture features. This article introduces CGPE, a tool dealing with the generation of fast and certified codes for the Evaluation of bivariate Polynomials. First we discuss the issue underlying the Evaluation scheme combinatorics before giving an overview of the CGPE tool. The approach we propose consists in two steps: the generation of Evaluation schemes by using some heuristics so as to quickly find some of low latency, and the selection that mainly consists in automatically checking their scheduling on the given target and validating their accuracy. Then, we present on-going development and ideas for possible improvements of the whole process. Finally, we illustrate the use of CGPE on some examples, and show how it allows us to generate fast and certified codes in a few seconds and thus to reduce the development time of libms like FLIP.
-
computing floating point square roots via bivariate Polynomial Evaluation
IEEE Transactions on Computers, 2011Co-Authors: Claudepierre Jeannerod, Herve Knochel, Christophe Monat, Guillaume RevyAbstract:In this paper, we show how to reduce the computation of correctly rounded square roots of binary floating-point data to the fixed-point Evaluation of some particular integer Polynomials in two variables. By designing parallel and accurate Evaluation schemes for such bivariate Polynomials, we show further that this approach allows for high instruction-level parallelism (ILP) exposure, and thus, potentially low-latency implementations. Then, as an illustration, we detail a C implementation of our method in the case of IEEE 754-2008 binary32 floating-point data (formerly called single precision in the 1985 version of the IEEE 754 standard). This software implementation, which assumes 32-bit unsigned integer arithmetic only, is almost complete in the sense that it supports special operands, subnormal numbers, and all rounding-direction attributes, but not exception handling (that is, status flags are not set). Finally, we have carried out experiments with this implementation on the ST231, an integer processor from the STMicroelectronics' ST200 family, using the ST200 family VLIW compiler. The results obtained demonstrate the practical interest of our approach in that context: for all rounding-direction attributes, the generated assembly code is optimally scheduled and has indeed low latency (23 cycles).
-
Implementation of binary floating-point arithmetic on embedded integer processors - Polynomial Evaluation-based algorithms and certified code generation
2009Co-Authors: Guillaume RevyAbstract:Today some embedded systems still do not integrate their own floating-point unit, for area, cost, or energy consumption constraints. However, this kind of architectures is widely used in application domains highly demanding on floating-point calculations (multimedia, audio and video, or telecommunications). To compensate this lack of floating-point hardware, floating-point arithmetic has to be emulated efficiently through a software implementation. This thesis addresses the design and implementation of an efficient software support for IEEE 754 floating-point arithmetic on embedded integer processors. More specifically, it proposes new algorithms and tools for the efficient generation of fast and certified programs, allowing in particular to obtain C codes of very low latency for Polynomial Evaluation in fixed-point arithmetic. Compared to fully hand-written implementations, these tools allow to significantly reduce the development time of floating-point operators. The first part of the thesis deals with the design of optimized algorithms for some binary floating-point operators, and gives details on their software implementation for the binary32 floating-point format and for some embedded VLIW integer processors like those of the STMicroelectronics ST200 family. In particular, we propose here a uniform approach for correctly-rounded roots and their reciprocals, and an extension to division. Our approach, which relies on the Evaluation of a single bivariate Polynomial, allows higher ILP-exposure than previous methods and turns out to be particularly efficient in practice. This work allowed us to produce a fully revised version of the FLIP library, leading to significant gains compared to the previous version. The second part of the thesis presents a methodology for automatically and efficiently generating fast and certified C codes for the Evaluation of bivariate Polynomials in fixed-point arithmetic. In particular, it consists of some heuristics for computing highly parallel, low-latency Evaluation schemes, as well as some techniques to check if those schemes remain efficient on a real target, and accurate enough to ensure correct rounding of the underlying operator implementations. This approach has been implemented in the software tool CGPE (Code Generation for Polynomial Evaluation). We have used our tool to quickly generate and certify significant parts of the codes of FLIP.
Irina Voiculescu - One of the best experts on this subject based on the ideXlab platform.
-
affine arithmetic in matrix form for Polynomial Evaluation and algebraic curve drawing
Progress in Natural Science, 2002Co-Authors: Irina VoiculescuAbstract:This paper shows how tight bounds for the range of a bivariate Polynomial can be found using a matrix method based on affine arithmetic. Then, this method is applied to drawing an algebraic curve with a hierarchical algorithm, which demonstrates that more accurate answers can be obtained more rapidly than using conventional interval arithmetic.
Gordon Procter - One of the best experts on this subject based on the ideXlab platform.
-
on weak keys and forgery attacks against Polynomial based mac schemes
Fast Software Encryption, 2013Co-Authors: Gordon ProcterAbstract:Universal hash functions are commonly used primitives for fast and secure message authentication in the form of Message Authentication Codes (MACs) or Authenticated Encryption with Associated Data (AEAD) schemes. These schemes are widely used and standardised, the most well known being McGrew and Viega’s Galois/Counter Mode (GCM). In this paper we identify some properties of hash functions based on Polynomial Evaluation that arise from the underlying algebraic structure. As a result we are able to describe a general forgery attack, of which Saarinen’s cycling attack from FSE 2012 is a special case. Our attack removes the requirement for long messages and applies regardless of the field in which the hash function is evaluated. Furthermore we provide a common description of all published attacks against GCM, by showing that the existing attacks are the result of these algebraic properties of the Polynomial-based hash function. Finally, we greatly expand the number of known weak GCM keys and show that almost every subset of the keyspace is a weak key class.