Algorithmic Complexity with Page-Based Intelligent Memory

Autor:	Mark Oskin, Lucian-Vlad Lita, Frederic T. Chong, Justin Hensley, Diana Keen
Rok vydání:	2000
Předmět:	Hardware and Architecture Software Theoretical Computer Science
Zdroj:	Parallel Processing Letters. 10:99-109
ISSN:	1793-642X 0129-6264
DOI:	10.1142/s0129626400000111
Popis:	High DRAM densities will make intelligent memory chips a commodity in the next five years [1] [2]. This paper focuses upon a promising model of computation in intelligent memory, Active Pages [3], where computation is associated with each page of memory. Computational hardware scales linearly and inexpensively with data size in this model, reducing the order of many algorithms. This scaling can, for example, reduce linear-time algorithms to [Formula: see text]. When page-based intelligent memory chips become available in commodity, they will change the way programmers select and utilize algorithms. In this paper, we analyze the asymptotic performance of several common algorithms as problem sizes scale. We also derive the optimal page size, as a function of problem size, for each algorithm running with intelligent memory. Finally, we validate these analyses with simulation results.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b42f06e0958c17f434acb26b2767904c https://doi.org/10.1142/s0129626400000111 Zobrazit plný text záznamu