The Experts below are selected from a list of 2538 Experts worldwide ranked by ideXlab platform

Torsten Hoefler - One of the best experts on this subject based on the ideXlab platform.

  • SC - Network-accelerated non-Contiguous Memory transfers
    Proceedings of the International Conference for High Performance Computing Networking Storage and Analysis, 2019
    Co-Authors: Salvatore Di Girolamo, Konstantin Taranov, Andreas Kurth, Michael Schaffner, Timo Schneider, Jakub Beránek, Maciej Besta, Luca Benini, Duncan Roweth, Torsten Hoefler
    Abstract:

    Applications often communicate data that is non-Contiguous in the send- or the receive-buffer, e.g., when exchanging a column of a matrix stored in row-major order. While non-Contiguous transfers are well supported in HPC (e.g., MPI derived datatypes), they can still be up to 5x slower than Contiguous transfers of the same size. As we enter the era of network acceleration, we need to investigate which tasks to offload to the NIC: In this work we argue that non-Contiguous Memory transfers can be transparently network-accelerated, truly achieving zero-copy communications. We implement and extend sPIN, a packet streaming processor, within a Portals 4 NIC SST model, and evaluate strategies for NIC-offloaded processing of MPI datatypes, ranging from datatype-specific handlers to general solutions for any MPI datatype. We demonstrate up to 8x speedup in the unpack throughput of real applications, demonstrating that non-Contiguous Memory transfers are a first-class candidate for network acceleration.

Tesser Federico - One of the best experts on this subject based on the ideXlab platform.

  • Parallel solver for the Poisson equation on a hierarchy of superimposed meshes, under a Python framework
    2020
    Co-Authors: Tesser Federico
    Abstract:

    Les discrétisations adaptatives sont importantes dans les problèmes de fluxcompressible/incompressible puisqu'il est souvent nécessaire de résoudre desdétails sur plusieurs niveaux, en permettant de modéliser de grandes régionsd'espace en utilisant un nombre réduit de degrés de liberté (et en réduisant letemps de calcul).Il existe une grande variété de méthodes de discrétisation adaptative, maisles grilles cartésiennes sont les plus efficaces, grâce à leurs stencilsnumériques simples et précis et à leurs performances parallèles supérieures.Et telles performance et simplicité sont généralement obtenues en appliquant unschéma de différences finies pour la résolution des problèmes, mais cetteapproche de discrétisation ne présente pas, au contraire, un chemin faciled'adaptation.Dans un schéma de volumes finis, en revanche, nous pouvons incorporer différentstypes de maillages, plus appropriées aux raffinements adaptatifs, en augmentantla complexité sur les stencils et en obtenant une plus grande flexibilité.L'opérateur de Laplace est un élément essentiel des équations de Navier-Stokes,un modèle qui gouverne les écoulements de fluides, mais il se produit égalementdans des équations différentielles qui décrivent de nombreux autres phénomènesphysiques, tels que les potentiels électriques et gravitationnels. Il s'agitdonc d'un opérateur différentiel très important, et toutes les études qui ontété effectuées sur celui-ci, prouvent sa pertinence.Dans ce travail seront présentés des approches de différences finies et devolumes finis 2D pour résoudre l'opérateur laplacien, en appliquant des patchsde grilles superposées où un niveau plus fin est nécessaire, en laissant desmaillages plus grossiers dans le reste du domaine de calcul.Ces grilles superposées auront des formes quadrilatérales génériques.Plus précisément, les sujets abordés seront les suivants:1) introduction à la méthode des différences finies, méthode des volumes finis,partitionnement des domaines, approximation de la solution;2) récapitulatif des différents types de maillages pour représenter de façondiscrète la géométrie impliquée dans un problème, avec un focussur la structure de données octree, présentant PABLO et PABLitO. Le premier estune bibliothèque externe utilisée pour gérer la création de chaque grille,l'équilibrage de charge et les communications internes, tandis que la secondeest l'API Python de cette bibliothèque, écrite ad hoc pour le projet en cours;3) la présentation de l'algorithme utilisé pour communiquer les données entreles maillages (en ignorant chacune l'existence de l'autre) en utilisant lesintercommunicateurs MPI et la clarification de l'approche monolithique appliquéeà la construction finale de la matrice pour résoudre le système, en tenantcompte des blocs diagonaux, de restriction et de prolongement;4) la présentation de certains résultats; conclusions, références.Il est important de souligner que tout est fait sous Python comme framework deprogrammation, en utilisant Cython pour l'écriture de PABLitO, MPI4Py pour lescommunications entre grilles, PETSc4py pour les parties assemblage et résolutiondu système d'inconnues, NumPy pour les objets à mémoire continue.Le choix de ce langage de programmation a été fait car Python, facile àapprendre et à comprendre, est aujourd'hui un concurrent significatif pourl'informatique numérique et l'écosystème HPC, grâce à son style épuré, sespackages, ses compilateurs et pourquoi pas ses versions optimisées pour desarchitectures spécifiques.Adaptive discretizations are important in compressible/incompressible flow problems since it is often necessary to resolve details on multiple levels,allowing large regions of space to be modeled using a reduced number of degrees of freedom (reducing the computational time).There are a wide variety of methods for adaptively discretizing space, but Cartesian grids have often outperformed them even at high resolutions due totheir simple and accurate numerical stencils and their superior parallel performances.Such performance and simplicity are in general obtained applying afinite-difference scheme for the resolution of the problems involved, but this discretization approach does not present, by contrast, an easy adapting path.In a finite-volume scheme, instead, we can incorporate different types of grids,more suitable for adaptive refinements, increasing the complexity on thestencils and getting a greater flexibility.The Laplace operator is an essential building block of the Navier-Stokes equations, a model that governs fluid flows, but it occurs also in differential equations that describe many other physical phenomena, such as electric and gravitational potentials, and quantum mechanics. So, it is a very importantdifferential operator, and all the studies carried out on it, prove itsrelevance.In this work will be presented 2D finite-difference and finite-volume approaches to solve the Laplacian operator, applying patches of overlapping grids where amore fined level is needed, leaving coarser meshes in the rest of the computational domain.These overlapping grids will have generic quadrilateral shapes.Specifically, the topics covered will be:1) introduction to the finite difference method, finite volume method, domainpartitioning, solution approximation;2) overview of different types of meshes to represent in a discrete way thegeometry involved in a problem, with a focuson the octree data structure, presenting PABLO and PABLitO. The first one is anexternal library used to manage each single grid’s creation, load balancing and internal communications, while the second one is the Python API ofthat library written ad hoc for the current project;3) presentation of the algorithm used to communicate data between meshes (beingall of them unaware of each other’s existence) using MPI inter-communicators and clarification of the monolithic approach applied building the finalmatrix for the system to solve, taking into account diagonal, restriction and prolongation blocks;4) presentation of some results; conclusions, references.It is important to underline that everything is done under Python as programmingframework, using Cython for the writing of PABLitO, MPI4Py for the communications between grids, PETSc4py for the assembling and resolution partsof the system of unknowns, NumPy for Contiguous Memory buffer objects.The choice of this programming language has been made because Python, easy to learn and understand, is today a significant contender for the numerical computing and HPC ecosystem, thanks to its clean style, its packages, its compilers and, why not, its specific architecture optimized versions

  • Solveur parallèle pour l’équation de Poisson sur mailles superposées et hiérarchiques, dans le cadre du langage Python
    HAL CCSD, 2018
    Co-Authors: Tesser Federico
    Abstract:

    Adaptive discretizations are important in compressible/incompressible flow problems since it is often necessary to resolve details on multiple levels,allowing large regions of space to be modeled using a reduced number of degrees of freedom (reducing the computational time).There are a wide variety of methods for adaptively discretizing space, but Cartesian grids have often outperformed them even at high resolutions due totheir simple and accurate numerical stencils and their superior parallel performances.Such performance and simplicity are in general obtained applying afinite-difference scheme for the resolution of the problems involved, but this discretization approach does not present, by contrast, an easy adapting path.In a finite-volume scheme, instead, we can incorporate different types of grids,more suitable for adaptive refinements, increasing the complexity on thestencils and getting a greater flexibility.The Laplace operator is an essential building block of the Navier-Stokes equations, a model that governs fluid flows, but it occurs also in differential equations that describe many other physical phenomena, such as electric and gravitational potentials, and quantum mechanics. So, it is a very importantdifferential operator, and all the studies carried out on it, prove itsrelevance.In this work will be presented 2D finite-difference and finite-volume approaches to solve the Laplacian operator, applying patches of overlapping grids where amore fined level is needed, leaving coarser meshes in the rest of the computational domain.These overlapping grids will have generic quadrilateral shapes.Specifically, the topics covered will be:1) introduction to the finite difference method, finite volume method, domainpartitioning, solution approximation;2) overview of different types of meshes to represent in a discrete way thegeometry involved in a problem, with a focuson the octree data structure, presenting PABLO and PABLitO. The first one is anexternal library used to manage each single grid’s creation, load balancing and internal communications, while the second one is the Python API ofthat library written ad hoc for the current project;3) presentation of the algorithm used to communicate data between meshes (beingall of them unaware of each other’s existence) using MPI inter-communicators and clarification of the monolithic approach applied building the finalmatrix for the system to solve, taking into account diagonal, restriction and prolongation blocks;4) presentation of some results; conclusions, references.It is important to underline that everything is done under Python as programmingframework, using Cython for the writing of PABLitO, MPI4Py for the communications between grids, PETSc4py for the assembling and resolution partsof the system of unknowns, NumPy for Contiguous Memory buffer objects.The choice of this programming language has been made because Python, easy to learn and understand, is today a significant contender for the numerical computing and HPC ecosystem, thanks to its clean style, its packages, its compilers and, why not, its specific architecture optimized versions.Les discrétisations adaptatives sont importantes dans les problèmes de fluxcompressible/incompressible puisqu'il est souvent nécessaire de résoudre desdétails sur plusieurs niveaux, en permettant de modéliser de grandes régionsd'espace en utilisant un nombre réduit de degrés de liberté (et en réduisant letemps de calcul).Il existe une grande variété de méthodes de discrétisation adaptative, maisles grilles cartésiennes sont les plus efficaces, grâce à leurs stencilsnumériques simples et précis et à leurs performances parallèles supérieures.Et telles performance et simplicité sont généralement obtenues en appliquant unschéma de différences finies pour la résolution des problèmes, mais cetteapproche de discrétisation ne présente pas, au contraire, un chemin faciled'adaptation.Dans un schéma de volumes finis, en revanche, nous pouvons incorporer différentstypes de maillages, plus appropriées aux raffinements adaptatifs, en augmentantla complexité sur les stencils et en obtenant une plus grande flexibilité.L'opérateur de Laplace est un élément essentiel des équations de Navier-Stokes,un modèle qui gouverne les écoulements de fluides, mais il se produit égalementdans des équations différentielles qui décrivent de nombreux autres phénomènesphysiques, tels que les potentiels électriques et gravitationnels. Il s'agitdonc d'un opérateur différentiel très important, et toutes les études qui ontété effectuées sur celui-ci, prouvent sa pertinence.Dans ce travail seront présentés des approches de différences finies et devolumes finis 2D pour résoudre l'opérateur laplacien, en appliquant des patchsde grilles superposées où un niveau plus fin est nécessaire, en laissant desmaillages plus grossiers dans le reste du domaine de calcul.Ces grilles superposées auront des formes quadrilatérales génériques.Plus précisément, les sujets abordés seront les suivants:1) introduction à la méthode des différences finies, méthode des volumes finis,partitionnement des domaines, approximation de la solution;2) récapitulatif des différents types de maillages pour représenter de façondiscrète la géométrie impliquée dans un problème, avec un focussur la structure de données octree, présentant PABLO et PABLitO. Le premier estune bibliothèque externe utilisée pour gérer la création de chaque grille,l'équilibrage de charge et les communications internes, tandis que la secondeest l'API Python de cette bibliothèque, écrite ad hoc pour le projet en cours;3) la présentation de l'algorithme utilisé pour communiquer les données entreles maillages (en ignorant chacune l'existence de l'autre) en utilisant lesintercommunicateurs MPI et la clarification de l'approche monolithique appliquéeà la construction finale de la matrice pour résoudre le système, en tenantcompte des blocs diagonaux, de restriction et de prolongement;4) la présentation de certains résultats; conclusions, références.Il est important de souligner que tout est fait sous Python comme framework deprogrammation, en utilisant Cython pour l'écriture de PABLitO, MPI4Py pour lescommunications entre grilles, PETSc4py pour les parties assemblage et résolutiondu système d'inconnues, NumPy pour les objets à mémoire continue.Le choix de ce langage de programmation a été fait car Python, facile àapprendre et à comprendre, est aujourd'hui un concurrent significatif pourl'informatique numérique et l'écosystème HPC, grâce à son style épuré, sespackages, ses compilateurs et pourquoi pas ses versions optimisées pour desarchitectures spécifiques

  • Solveur Parallèle pour l'Equation de Poisson sur Mailles Superposées et Hiérarchiques, dans le Cadre du Langage Python
    HAL CCSD, 2018
    Co-Authors: Tesser Federico
    Abstract:

    Adaptive discretizations are important in compressible/incompressible flow problems since it is often necessary to resolve details on multiple levels, allowing large regions of space to be modeled using a reduced number of degrees of freedom (reducing the computational time). There are a wide variety of methods for adaptively discretizing space, but Cartesian grids have often outperformed them even at high resolutions due to their simple and accurate numerical stencils and their superior parallel performances. Such performance and simplicity are in general obtained applying a finite-difference scheme for the resolution of the problems involved, but this discretization approach does not present, by contrast, an easy adapting path. In a finite-volume scheme, instead, we can incorporate different types of grids, more suitable for adaptive refinements, increasing the complexity on the stencils and getting a greater flexibility. The Laplace operator is an essential building block of the Navier-Stokes equations, a model that governs fluid flows, but it occurs also in differential equations that describe many other physical phenomena, such as electric and gravitational potentials, and quantum mechanics. So, it is a very important differential operator, and all the studies carried out on it, prove its relevance. In this work will be presented 2D finite-difference and finite-volume approaches to solve the Laplacian operator, applying patches of overlapping grids where a more fined level is needed, leaving coarsermeshes in the rest of the computational domain. These overlapping grids will have generic quadrilateral shapes. Specifically, the topics covered will be: 1) introduction to the finite difference method, finite volume method, domain partitioning, solution approximation; 2)overview of different types of meshes to represent in a discrete way the geometry involved in a problem, with a focus on the octree data structure, presenting PABLO and PABLitO. The first one is an external library used to manage each single grid’s creation, load balancing andinternal communications, while the second one is the Python API of that library written ad hoc for the current project; 3) presentation of the algorithm used to communicate data between meshes (being all of them unaware of each other’s existence) using MPI inter-communicators and clarification of the monolithic approach applied building the final matrix for the system to solve, taking into account diagonal, restriction and prolongation blocks; 4) presentation of some results; conclusions, references. It is important to underline that everything is done under Python as programming framework, using Cython for the writing of PABLitO, MPI4Py for the communications between grids, PETSc4py for the assembling and resolution parts of the system of unknowns, NumPy for Contiguous Memory buffer objects. The choice of this programming language has been made because Python, easy to learn and understand, is today a significant contender for the numerical computing and HPC ecosystem, thanks to its clean style, its packages, its compilers and, why not, its specific architecture optimized versions.Les discrétisations adaptatives sont importantes dans les problèmes de flux compressible/incompressible puisqu'il est souvent nécessaire de résoudre des détails sur plusieurs niveaux, en permettant de modéliser de grandes régions d'espace en utilisant un nombre réduit de degrés de liberté (et en réduisant le temps de calcul). Il existe une grande variété de méthodes de discrétisation adaptative, mais les grilles cartésiennes sont les plus efficaces, grâce à leurs stencils numériques simples et précis et à leurs performances parallèles supérieures. Et telles performance et simplicité sont généralement obtenues en appliquant un schéma de différences finies pour la résolution des problèmes, mais cette approche de discrétisation ne présente pas, au contraire, un chemin facile d'adaptation.Dans un schéma de volumes finis, en revanche, nous pouvons incorporer différents types de maillages, plus appropriées aux raffinements adaptatifs, en augmentant la complexité sur les stencils et en obtenant une plus grande flexibilité. L'opérateur de Laplace est un élémentessentiel des équations de Navier-Stokes, un modèle qui gouverne les écoulements de fluides, mais il se produit également dans des équations différentielles qui décrivent de nombreux autres phénomènes physiques, tels que les potentiels électriques et gravitationnels. Il s'agit donc d'un opérateur différentiel très important, et toutes les études qui ont été effectuées sur celui-ci, prouvent sa pertinence. Dans ce travail seront présentés des approches de différences finies et de volumes finis 2D pour résoudre l'opérateur laplacien, en appliquant des patchs de grilles superposées où un niveau plus fin est nécessaire, en laissant des maillages plus grossiers dans le reste du domaine de calcul. Ces grilles superposées auront des formes quadrilatérales génériques. Plus précisément, les sujets abordés seront les suivants: 1) introduction à la méthode des différences finies, méthode des volumes finis, partitionnement des domaines, approximation de la solution; 2)récapitulatif des différents types de maillages pour représenter de façon discrète la géométrie impliquée dans un problème, avec un focus sur la structure de données octree, présentant PABLO et PABLitO. Le premier est une bibliothèque externe utilisée pour gérer la création de chaque grille, l'équilibrage de charge et les communications internes, tandis que la seconde est l'API Python de cette bibliothèque, écrite ad hoc pour le projet en cours; 3) la présentation de l'algorithme utilisé pour communiquer les données entre les maillages (en ignorant chacune l'existence de l'autre) en utilisant les intercommunicateurs MPI et la clarification de l'approche monolithique appliquée à la construction finale de la matrice pour résoudre le système, en tenant compte des blocs diagonaux, de restriction et de prolongement; 4) la présentation de certains résultats; conclusions, références. Il est important de souligner que tout est fait sous Python comme framework de programmation, en utilisant Cython pour l'écriture de PABLitO, MPI4Py pour les communications entre grilles, PETSc4py pour les parties assemblage et résolution du système d'inconnues, NumPy pour les objets à mémoire continue. Le choix de ce langage de programmation a été fait car Python, facile à apprendre et à comprendre, est aujourd'hui un concurrent significatif pour l'informatique numérique et l'écosystème HPC, grâce à son style épuré, ses packages, ses compilateurs et pourquoi pas ses versions optimisées pour des architectures spécifiques

Ido Shahaf - One of the best experts on this subject based on the ideXlab platform.

  • Tight Tradeoffs in Searchable Symmetric Encryption
    Journal of Cryptology, 2021
    Co-Authors: Gilad Asharov, Gil Segev, Ido Shahaf
    Abstract:

    A searchable symmetric encryption (SSE) scheme enables a client to store data on an untrusted server while supporting keyword searches in a secure manner. Recent experiments have indicated that the practical relevance of such schemes heavily relies on the tradeoff between their space overhead , locality (the number of non-Contiguous Memory locations that the server accesses with each query), and read efficiency (the ratio between the number of bits the server reads with each query and the actual size of the answer). These experiments motivated Cash and Tessaro (EUROCRYPT ’14) and Asharov et al. (STOC ’16) to construct SSE schemes offering various such tradeoffs and to prove lower bounds for natural SSE frameworks. Unfortunately, the best-possible tradeoff has not been identified, and there are substantial gaps between the existing schemes and lower bounds, indicating that a better understanding of SSE is needed. We establish tight bounds on the tradeoff between the space overhead, locality and read efficiency of SSE schemes within two general frameworks that capture the Memory access pattern underlying all existing schemes. First, we introduce the “pad-and-split” framework, refining that of Cash and Tessaro while still capturing the same existing schemes. Within our framework we significantly strengthen their lower bound, proving that any scheme with locality L must use space $$\Omega ( N \log N / \log L )$$ Ω ( N log N / log L ) for databases of size N . This is a tight lower bound, matching the tradeoff provided by the scheme of Demertzis and Papamanthou (SIGMOD ’17) which is captured by our pad-and-split framework. Then, within the “statistical-independence” framework of Asharov et al. we show that their lower bound is essentially tight: We construct a scheme whose tradeoff matches their lower bound within an additive $$O(\log \log \log N)$$ O ( log log log N ) factor in its read efficiency, once again improving upon the existing schemes. Our scheme offers optimal space and locality, and nearly optimal read efficiency that depends on the frequency of the queried keywords: For a keyword that is associated with $$n = N^{1 - \epsilon (n)}$$ n = N 1 - ϵ ( n ) document identifiers, the read efficiency is $$\omega (1) \cdot {\epsilon }(n)^{-1}+ O(\log \log \log N)$$ ω ( 1 ) · ϵ ( n ) - 1 + O ( log log log N ) when retrieving its identifiers (where the $$\omega (1)$$ ω ( 1 ) term may be arbitrarily small, and $$\omega (1) \cdot {\epsilon }(n)^{-1}$$ ω ( 1 ) · ϵ ( n ) - 1 is the lower bound proved by Asharov et al.). In particular, for any keyword that is associated with at most $$N^{1 - 1/o(\log \log \log N)}$$ N 1 - 1 / o ( log log log N ) document identifiers (i.e., for any keyword that is not exceptionally common), we provide read efficiency $$O(\log \log \log N)$$ O ( log log log N ) when retrieving its identifiers.

  • tight tradeoffs in searchable symmetric encryption
    International Cryptology Conference, 2018
    Co-Authors: Gilad Asharov, Gil Segev, Ido Shahaf
    Abstract:

    A searchable symmetric encryption (SSE) scheme enables a client to store data on an untrusted server while supporting keyword searches in a secure manner. Recent experiments have indicated that the practical relevance of such schemes heavily relies on the tradeoff between their space overhead, locality (the number of non-Contiguous Memory locations that the server accesses with each query), and read efficiency (the ratio between the number of bits the server reads with each query and the actual size of the answer). These experiments motivated Cash and Tessaro (EUROCRYPT ’14) and Asharov et al. (STOC ’16) to construct SSE schemes offering various such tradeoffs, and to prove lower bounds for natural SSE frameworks. Unfortunately, the best-possible tradeoff has not been identified, and there are substantial gaps between the existing schemes and lower bounds, indicating that a better understanding of SSE is needed.

  • searchable symmetric encryption optimal locality in linear space via two dimensional balanced allocations
    Symposium on the Theory of Computing, 2016
    Co-Authors: Gilad Asharov, Gil Segev, Moni Naor, Ido Shahaf
    Abstract:

    Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of non-Contiguous Memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer). We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly-optimal read efficiency. Specifically, for a database of size N, under the modest assumption that no keyword appears in more than N1 − 1/loglogN documents, we construct a scheme with read efficiency O(loglogN). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT ’14) showing that any SSE scheme must be sub-optimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency O(logN). Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations (“balls and bins”) problem that we put forward. We construct nearly-optimal two-dimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques.

  • searchable symmetric encryption optimal locality in linear space via two dimensional balanced allocations
    IACR Cryptology ePrint Archive, 2016
    Co-Authors: Gilad Asharov, Gil Segev, Moni Naor, Ido Shahaf
    Abstract:

    Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of non-Contiguous Memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer). We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly-optimal read efficiency. Specifically, for a database of size N , under the modest assumption that no keyword appears in more than N1−1/ log logN documents, we construct a scheme with read efficiency O(log logN). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT ’14) showing that any SSE scheme must be sub-optimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency O(logN). Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations (“balls and bins”) problem that we put forward. We construct nearly-optimal twodimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques. ∗IBM Research. Email: gsasharo@us.ibm.com. This work was completed while the author was a post-doctoral researcher at the Hebrew University’s School of Computer Science and Engineering. †Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel. Email: moni.naor@weizmann.ac.il. Research supported in part by the Israel Science Foundation and by the Israeli Centers of Research Excellence (I-CORE) Program (Center No. 4/11). ‡School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 91904, Israel. Email: {segev,ido shahaf}@cs.huji.ac.il. Supported by the Israel Science Foundation (Grant No. 483/13) and by the Israeli Centers of Research Excellence (I-CORE) Program (Center No. 4/11).

Koen De Bosschere - One of the best experts on this subject based on the ideXlab platform.

  • Java object header elimination for reduced Memory consumption in 64-bit virtual machines
    ACM Transactions on Architecture and Code Optimization, 2007
    Co-Authors: Kris Venstermans, Koen De Bosschere
    Abstract:

    Memory performance is an important design issue for contemporary computer systems given the huge processor/Memory speed gap. This paper proposes a space-efficient Java object model for reducing the Memory consumption of 64-bit Java virtual machines. We completely eliminate the object header through typed virtual addressing (TVA) or implicit typing. TVA encodes the object type in the object's virtual address by allocating all objects of a given type in a Contiguous Memory segment. This allows for removing the type information as well as the status field from the object header. Whenever type and status information is needed, masking is applied to the object's virtual address for obtaining an offset into type and status information structures. Unlike previous work on implicit typing, we apply TVA to a selected number of frequently allocated object types, hence, the name selective TVA (STVA); this limits the amount of Memory fragmentation. In addition to applying STVA, we also compress the type information block (TIB) pointers for all objects that do not fall under TVA. We implement the space-efficient Java object model in the 64-bit version of the Jikes RVM on an AIX IBM platform and compare its performance against the traditionally used Java object model using a multitude of Java benchmarks. We conclude that the space-efficient Java object model reduces Memory consumption by on average 15p (and up to 45p for some benchmarks). About one-half the reduction comes from TIB pointer compression; the other one-half comes from STVA. In terms of performance, the space-efficient object model generally does not affect performance; however, for some benchmarks we observe statistically significant performance speedups, up to 20p.

  • space efficient 64 bit java objects through selective typed virtual addressing
    Symposium on Code Generation and Optimization, 2006
    Co-Authors: Kris Venstermans, Lieven Eeckhout, Koen De Bosschere
    Abstract:

    Memory performance is an important design issue for contemporary systems given the ever increasing Memory gap. This paper proposes a space-efficient Java object model for reducing the Memory consumption of 64-bit Java virtual machines. We propose selective typed virtual addressing (STVA) which uses typed virtual addressing (TVA) or implicit typing for reducing the header of 64-bit Java objects. The idea behind TVA is to encode the object's type in the object's virtual address. In other words, all objects of a given type are allocated in a Contiguous Memory segment. As such, the type information can be removed from the object's header which reduces the number of allocated bytes per object. Whenever type information is needed for the given object, masking is applied to the object's virtual address. Unlike previous work on implicit typing, we apply TVA to a selected number of frequently allocated and/or long-lived object types. This limits the amount of Memory fragmentation. We implement STVA in the 64-bit version of the Jikes RVM on an AIX IBM platform and compare its performance against a traditional VM implementation without STVA using a multitude of Java benchmarks. We conclude that STVA reduces Memory consumption by on average 15.5% (and up to 39% for some benchmarks). In terms of performance, STVA generally does not affect performance, however for some benchmarks we observe statistically significant performance speedups, up to 24%.

Bineng Zhong - One of the best experts on this subject based on the ideXlab platform.

  • residual dense network for image restoration
    IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020
    Co-Authors: Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong
    Abstract:

    Recently, deep convolutional neural network (CNN) has achieved great success for image restoration (IR) and provided hierarchical features at the same time. However, most deep CNN based IR models do not make full use of the hierarchical features from the original low-quality images, thereby resulting in relatively-low performance. In this work, we propose a novel and efficient residual dense network (RDN) to address this problem in IR, by making a better tradeoff between efficiency and effectiveness in exploiting the hierarchical features from all the convolutional layers. Specifically, we propose residual dense block (RDB) to extract abundant local features via densely connected convolutional layers. RDB further allows direct connections from the state of preceding RDB to all the layers of current RDB, leading to a Contiguous Memory mechanism. To adaptively learn more effective features from preceding and current local features and stabilize the training of wider network, we proposed local feature fusion in RDB. After fully obtaining dense local features, we use global feature fusion to jointly and adaptively learn global hierarchical features in a holistic way. We demonstrate the effectiveness of RDN with several representative IR applications, single image super-resolution, Gaussian image denoising, image compression artifact reduction, and image deblurring. Experiments on benchmark and real-world datasets show that our RDN achieves favorable performance against state-of-the-art methods for each IR task quantitatively and visually.

  • residual dense network for image restoration
    arXiv: Computer Vision and Pattern Recognition, 2018
    Co-Authors: Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong
    Abstract:

    Convolutional neural network has recently achieved great success for image restoration (IR) and also offered hierarchical features. However, most deep CNN based IR models do not make full use of the hierarchical features from the original low-quality images, thereby achieving relatively-low performance. In this paper, we propose a novel residual dense network (RDN) to address this problem in IR. We fully exploit the hierarchical features from all the convolutional layers. Specifically, we propose residual dense block (RDB) to extract abundant local features via densely connected convolutional layers. RDB further allows direct connections from the state of preceding RDB to all the layers of current RDB, leading to a Contiguous Memory mechanism. To adaptively learn more effective features from preceding and current local features and stabilize the training of wider network, we proposed local feature fusion in RDB. After fully obtaining dense local features, we use global feature fusion to jointly and adaptively learn global hierarchical features in a holistic way. We demonstrate the effectiveness of RDN with several representative IR applications, single image super-resolution, Gaussian image denoising, image compression artifact reduction, and image deblurring. Experiments on benchmark and real-world datasets show that our RDN achieves favorable performance against state-of-the-art methods for each IR task quantitatively and visually.

  • residual dense network for image super resolution
    Computer Vision and Pattern Recognition, 2018
    Co-Authors: Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong, Yun Fu
    Abstract:

    A very deep convolutional neural network (CNN) has recently achieved great success for image super-resolution (SR) and offered hierarchical features as well. However, most deep CNN based SR models do not make full use of the hierarchical features from the original low-resolution (LR) images, thereby achieving relatively-low performance. In this paper, we propose a novel residual dense network (RDN) to address this problem in image SR. We fully exploit the hierarchical features from all the convolutional layers. Specifically, we propose residual dense block (RDB) to extract abundant local features via dense connected convolutional layers. RDB further allows direct connections from the state of preceding RDB to all the layers of current RDB, leading to a Contiguous Memory (CM) mechanism. Local feature fusion in RDB is then used to adaptively learn more effective features from preceding and current local features and stabilizes the training of wider network. After fully obtaining dense local features, we use global feature fusion to jointly and adaptively learn global hierarchical features in a holistic way. Experiments on benchmark datasets with different degradation models show that our RDN achieves favorable performance against state-of-the-art methods.

  • residual dense network for image super resolution
    arXiv: Computer Vision and Pattern Recognition, 2018
    Co-Authors: Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong, Yun Fu
    Abstract:

    A very deep convolutional neural network (CNN) has recently achieved great success for image super-resolution (SR) and offered hierarchical features as well. However, most deep CNN based SR models do not make full use of the hierarchical features from the original low-resolution (LR) images, thereby achieving relatively-low performance. In this paper, we propose a novel residual dense network (RDN) to address this problem in image SR. We fully exploit the hierarchical features from all the convolutional layers. Specifically, we propose residual dense block (RDB) to extract abundant local features via dense connected convolutional layers. RDB further allows direct connections from the state of preceding RDB to all the layers of current RDB, leading to a Contiguous Memory (CM) mechanism. Local feature fusion in RDB is then used to adaptively learn more effective features from preceding and current local features and stabilizes the training of wider network. After fully obtaining dense local features, we use global feature fusion to jointly and adaptively learn global hierarchical features in a holistic way. Extensive experiments on benchmark datasets with different degradation models show that our RDN achieves favorable performance against state-of-the-art methods.