NDLI: On approximating the ideal random access machine by physical machines

Content Provider	ACM Digital Library
Author	Bilardi, Gianfranco Ekanadham, Kattamuri Pattnaik, Pratap
Copyright Year	2009
Abstract	The capability of the Random Access Machine (RAM) to execute any instruction in constant time is not realizable, due to fundamental physical constraints on the minimum size of devices and on the maximum speed of signals. This work explores how well the ideal RAM performance can be approximated, for significant classes of computations, by machines whose building blocks have constant size and are connected at a constant distance. A novel memory structure is proposed, which is $\textit{pipelined}$ (can accept a new request at each cycle) and $\textit{hierarchical},$ exhibiting optimal latency $\textit{a}(\textit{x})$ = $O(x^{1/d})$ to address $\textit{x},$ in $\textit{d}-dimensional$ realizations. In spite of block-transfer or other memory-pipeline capabilities, a number of previous machine models do not achieve a full overlap of memory accesses. These are examples of machines with explicit data movement. It is shown that there are $\textit{direct-flow}$ computations (without branches and indirect accesses) that require time superlinear in the number of instructions, on all such machines. To circumvent the explicit-data-movement constraints, the Speculative Prefetcher (SP) and the Speculative Prefetcher and Evaluator (SPE) processors are developed. Both processors can execute any $\textit{direct-flow}$ program in linear time. The SPE also executes in linear time a class of loop programs that includes many significant algorithms. Even quicksort, a somewhat irregular, recursive algorithm admits a linear-time SPE implementation. A relation between instructions called address dependence is introduced, which limits memory-access overlap and can lead to superlinear time, as illustrated with the classical merging algorithm.
Starting Page	1
Ending Page	57
Page Count	57
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1552285.1552288
Journal	Journal of the ACM (JACM)
Volume Number	56
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Physical constraints on machines Pipelined hierarchical memory Speculative processors
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the complexity of functions for random access machines

Time Bounded Random Access Machines with Parallel Processing

Lower bounds for solving linear diophantine equations on random access machines

On pointers versus addresses

Software protection and simulation on oblivious RAMs

Random-Access Stored-Program Machines, an Approach to Programming Languages

Some Aspects of Hierarchical Memory Systems

A nonlinear lower bound for random-access machines under logarithmic cost

Memory-constrained task scheduling on a network of dual processors

On approximating the ideal random access machine by physical machines

Similar Documents

On the complexity of functions for random access machines

Time Bounded Random Access Machines with Parallel Processing

Lower bounds for solving linear diophantine equations on random access machines

On pointers versus addresses

Software protection and simulation on oblivious RAMs

Random-Access Stored-Program Machines, an Approach to Programming Languages

Some Aspects of Hierarchical Memory Systems

A nonlinear lower bound for random-access machines under logarithmic cost

Memory-constrained task scheduling on a network of dual processors

On approximating the ideal random access machine by physical machines