Associative array

Summary

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a function with finite domain. It supports 'lookup', 'remove', and 'insert' operations. The dictionary problem is the classic problem of designing efficient data structures that implement associative arrays. The two major solutions to the dictionary problem are hash tables and search trees. In some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures. Many programming languages include associative arrays as primitive data types, and they are available in software libraries for many others. Content-addressable memory is a form of direct hardware-level support for associative arrays. Associative arrays have m

Official source

https://en.wikipedia.org/wiki/Associative_array

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (9)

Related publications

Related people

Related units

Related concepts (55)

Related concepts

Related courses (21)

The purpose of the course is to introduce the basic notions of linear algebra and its applications.

The aim of this course is to provide a solid foundation of theory of distributions, Sobolev spaces and an introduction to the more general theory of interpolation spaces.

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.

Related courses

Related lectures (28)

Related lectures

Stop Crying Over Your Cache Miss Rate: Handling Efficiently Thousands of Outstanding Misses in FPGAs

Mikhail Asiatici, Paolo Ienne

FPGAs rely on massive datapath parallelism to accelerate applications even with a low clock frequency. However, applications such as sparse linear algebra and graph analytics have their throughput limited by irregular accesses to external memory for which typical caches provides little benefit because of very frequent misses. Non-blocking caches are widely used on CPUs to reduce the negative impact of misses and thus increase performance of applications with low cache hit rate; however, they rely on associative lookup for handling multiple outstanding misses, which limits their scalability, especially on FPGAs. This results in frequent stalls whenever the application has a very low hit rate. In this paper, we show that by handling thousands of outstanding misses without stalling we can achieve a massive increase of memory-level parallelism, which can significantly speed up irregular memory-bound latency-insensitive applications. By storing miss information in cuckoo hash tables in block RAM instead of associative memory, we show how a non-blocking cache can be modified to support up to three orders of magnitude more misses. The resulting miss-optimized architecture provides new Pareto-optimal and even Pareto-dominant design points in the area-delay space for twelve large sparse matrix-vector multiplication benchmarks, providing up to 25% speedup with 24x area reduction or to 2x speedup with similar area compared to traditional hit-optimized architectures.

ASSOC COMPUTING MACHINERY2019

Applications such as large-scale sparse linear algebra and graph analytics are challenging to accelerate on FPGAs due to the short irregular memory accesses, resulting in low cache hit rates. Nonblocking caches reduce the bandwidth required by misses by requesting each cache line only once, even when there are multiple misses corresponding to it. However, such reuse mechanism is traditionally implemented using an associative lookup. This limits the number of misses that are considered for reuse to a few tens, at most. In this article, we present an efficient pipeline that can process and store thousands of outstanding misses in cuckoo hash tables in on-chip SRAM with minimal stalls. This brings the same bandwidth advantage as a larger cache for a fraction of the area budget, because outstanding misses do not need a data array, which can significantly speed up irregular memory-bound latency-insensitive applications. In addition, we extend nonblocking caches to generate variable-length bursts to memory, which increases the bandwidth delivered by DRAMs and their controllers. The resulting miss-optimized memory system provides up to 25% speedup with 24x area reduction on 15 large sparse matrix-vector multiplication benchmarks evaluated on an embedded and a datacenter FPGA system.

ASSOC COMPUTING MACHINERY2022

Twisting structures and strongly homotopy morphisms

Kathryn Hess Bellwald

In an application of the notion of twisting structures introduced by Hess and Lack, we define twisted composition products of symmetric sequences of chain complexes that are degreewise projective and finitely generated. Let Q be a cooperad and let BP be the bar construction on the operad P. To each morphism of cooperads g from Q to BP is associated a P-co-ring, K(g), which generalizes the two-sided Koszul and bar constructions. When the co-unit from K(g) to P is a quasi-isomorphism, we show that the Kleisli category for K(g) is isomorphic to the category of P-algebras and of their morphisms up to strong homotopy, and we give the classifying morphisms for both strict and homotopy P-algebras. Parametrized morphisms of (co)associative chain (co)algebras up to strong homotopy are also introduced and studied, and a general existence theorem is proved. In the appendix, we study the particular case of the two-sided Koszul resolution of the associative operad.

2010