اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithmic Building Blocks for Asymmetric Memories
430
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The future of main memory appears to lie in the direction of new non-volatile memory technologies that provide strong capacity-to-performance ratios, but have write operations that are much more expensive than reads in terms of energy, bandwidth, and latency. This asymmetry can have a significant effect on algorithm design, and in many cases it is possible to reduce writes at the cost of reads. In this paper, we study which algorithmic techniques are useful in designing practical write-efficient algorithms. We focus on several fundamental algorithmic building blocks including unordered set/map implemented using hash tables, ordered set/map implemented using various binary search trees, comparison sort, and graph traversal algorithms including breadth-first search and Dijkstras algorithm. We introduce new algorithms and implementations that can reduce writes, and analyze the performance experimentally using a software simulator. Finally we summarize interesting lessons and directions in designing write-efficient algorithms.
قيم البحث
اقرأ أيضاً
The stellar halos of galaxies encode their accretion histories. In particular, the median metallicity of a halo is determined primarily by the mass of the most massive accreted object. We use hydrodynamical cosmological simulations from the APOSTLE p
roject to study the connection between the stellar mass, the metallicity distribution, and the stellar age distribution of a halo and the identity of its most massive progenitor. We find that the stellar populations in an accreted halo typically resemble the old stellar populations in a present-day dwarf galaxy with a stellar mass $sim 0.2-0.5$ dex greater than that of the stellar halo. This suggest that had they not been accreted, the primary progenitors of stellar halos would have evolved to resemble typical nearby dwarf irregulars.
The notion of directed treewidth was introduced by Johnson, Robertson, Seymour and Thomas [Journal of Combinatorial Theory, Series B, Vol 82, 2001] as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete prop
erties such as Hamiltonicity can be decided in polynomial time on digraphs of constant directed treewidth. Nevertheless, despite more than one decade of intensive research, the list of hard combinatorial problems that are known to be solvable in polynomial time when restricted to digraphs of constant directed treewidth has remained scarce. In this work we enrich this list by providing for the first time an algorithmic metatheorem connecting the monadic second order logic of graphs to directed treewidth. We show that most of the known positive algorithmic results for digraphs of constant directed treewidth can be reformulated in terms of our metatheorem. Additionally, we show how to use our metatheorem to provide polynomial time algorithms for two classes of combinatorial problems that have not yet been studied in the context of directed width measures. More precisely, for each fixed $k,w in mathbb{N}$, we show how to count in polynomial time on digraphs of directed treewidth $w$, the number of minimum spanning strong subgraphs that are the union of $k$ directed paths, and the number of maximal subgraphs that are the union of $k$ directed paths and satisfy a given minor closed property. To prove our metatheorem we devise two technical tools which we believe to be of independent interest. First, we introduce the notion of tree-zig-zag number of a digraph, a new directed width measure that is at most a constant times directed treewidth. Second, we introduce the notion of $z$-saturated tree slice language, a new formalism for the specification and manipulation of infinite sets of digraphs.
We study numerically the formation of dSph galaxies. Intense star bursts, e.g. in gas-rich environments, typically produce a few to a few hundred young star clusters, within a region of just a few hundred pc. The dynamical evolution of these star clu
sters may explain the formation of the luminous component of dwarf spheroidal galaxies (dSph). Here we perform a numerical experiment to show that the evolution of star clusters complexes in dark matter haloes can explain the formation of the luminous components of dSph galaxies.
One-time memories (OTMs) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTMs usi
ng quantum mechanical devices. It is known that OTMs cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on isolated qubits -- qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTMs that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements. Our construction resembles Wiesners old idea of quantum conjugate coding, implemented using random error-correcting codes; our proof of security uses entropy chaining to bound the supremum of a suitable empirical process. In addition, we conjecture that our random codes can be replaced by some class of efficiently-decodable codes, to get computationally-efficient OTMs that are secure against computationally-bounded LOCC adversaries. In addition, we construct data-hiding states, which allow an LOCC sender to encode an (n-O(1))-bit messsage into n qubits, such that at most half of the message can be extracted by a one-pass LOCC receiver, but the whole message can be extracted by a general quantum receiver.
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $kge 3$ and $varepsilon>0$, a randomised polynomial-time algorith
m for colouring graphs of maximum degree $Delta$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2le tle Delta^frac{2varepsilon}{1+2varepsilon}/(logDelta)^2$, with $lfloor(1+varepsilon)Delta/log(Delta/sqrt t)rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
