NDLI: Computational power of pipelined memory hierarchies

Please wait, while we are loading the content...

Compact routing schemes

Routing without flow control

Fast, minimal and oblivious routing algorithms on the mesh with bounded queues

One-to-Many routing on the mesh

Simple on-line algorithms for the maximum disjoint paths problem

Stability and non-stability of the FIFO protocol

Competitve buffer management for shared-memory switches

Tradeoffs between knowledge and time of communication in geometric radio networks

Attack propagation in networks

Deterministic resource discovery in distributed networks

Latency effects on reachability in large-scale peer-to-peer networks

Towards a first vertical prototyping of an extremely fine-grained parallel programming approach

A cost effective architecture for vectorizable numerical and multimedia applications

Automatable verification of sequential consistency

Room synchronizations

A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems

Computational power of pipelined memory hierarchies

Optimal semi-oblique tiling

Finding large independent sets of hypergraphs in parallel

Columnsort lives! an efficient out-of-core sorting program

Efficient parallel exponentiation in GF(2n) using normal basis representations

Low-contention depth-first scheduling of parallel computations with write-once synchronization variables

Scheduling on hierarchical clusters using malleable tasks

Scheduling best-effort and real-time pipelined applications on time-shared clusters

Optimal prefetching and caching for parallel I/O sytems

Ordering disks for double erasure codes

Approximation algorithms for data management in networks

A data tracking scheme for general networks

New spectral bounds on k-partitioning of graphs

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Towards practical deteministic write-all algorithms

Estimating simple functions on the union of data streams

Randomized k-set agreement

Periodic, random-fault-tolerant correction networks

D-CAT: A distributed channel allocation strategy based on a threshold scheme for cellular mobile networks

A note on cycle covering

Pursuit and evasion on a ring: An infinite hierarchy for parallel real—time systems

Scheduling tasks with small communication delays for clusters of processors

Library support for orthogonal processor groups

The push tree problem

Parallel controlled conspiracy number search

On tiling space-time mapped loop nests

A parallel block algorithm for exact triangularization of rectangular matrices

Eventually consistent failure detectors

Finding strongly connected components in parallel in particle transport sweeps

A work-optimal CGM algorithm for the LIS problem

Modeling weakly consistent memories with locks

The power of duality for prefetching and sorting with parallel disks

Computational power of pipelined memory hierarchies

Content Provider	ACM Digital Library
Author	Bilardi, Gianfranco Ekanadham, Kattamuri Pattnaik, Pratap
Abstract	We define a model of computation, called the Pipelined Hierarchical Random Access Machine with access function a (x), denoted the a(x)-PH-RAM. In this model, a processor interacts with a memory which can accept requests at a constant rate and satisfy each of the requests to the location x within a(x) units of time.We investigate memory management strategies that lead to time efficient implementations of arbitrary computations on a PH-RAM. We begin by developing the so called pipeline d decomposition-treememory management strategy, which can be tuned to the memory access function. Specifically, for a linear or sublinear access function a(x), w e define the concept of latency-hiding depth da(x) and show ho w an y computation of N operations can be implemented on an a(x)-PH-RAM in time T(N) = &Ogr;(Nda(N)). In particular, T(N) = &Ogr;(N log N) if a(x) = &Ogr;(x), T(N) = &Ogr;(N log log N) if a(x) = $&Ogr;(x^{Β})$ with 0 < Β < 1, and T(N) = O(N log* N) if a(x) = &Ogr;(log x).We develop lower bound techniques that allow to establish existential lower bounds on PH-RAMs. In particular, we exhibit computations for which T(N) = &OHgr;(Nlog N/ log log N) when a(x) = &OHgr;(x), T(N) = &OHgr;(Nlog logN) when a(x) = $&OHgr;(x^{Β})$ with 0 < Β < 1, and T(N) = &OHgr;(N log* N) when a(x) = &OHgr;(log x).The stated lower bounds show that the pipelined decomposition-tree strategy is existentially optimal for the latter case but indicates the potential for a modest, &Ogr;(log log N) improvement for linear access functions. To realize this potential, a superpipelined decomposition-tree memory manager is proposed, which achieves T(N) = &Ogr;(N log N/log log N).The pipelined decomposition-tree strategy can also be tuned to the computation, in order to exploit its temporal locality as characterized by the width parameters [9]. When the latter are suitably bounded, then T(N) = &Ogr;(N) on any PH-RAM with linear or sublinear access function. Finally, we discuss how performance could benefit from parallelism in the data-dependence dag of the computation or from architectural enhancements, such as block-transfer primitives, and formulate various questions that deserve further investigation.
Starting Page	144
Ending Page	152
Page Count	9
File Format	PDF
ISBN	1581134096
DOI	10.1145/378580.378615
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-07-03
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

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

Pipelined memory hierarchies: scalable organizations and application performance

Analysis of power consumption in memory hierarchies

Exploring latency-power tradeoffs in deep nonvolatile memory hierarchies

A DVS-based pipelined reconfigurable instruction memory

Hierarchies of memory limited computations

A low-power content-addressable memory (CAM) using pipelined search scheme

The Speculative Prefetcher and Evaluator Processor for Pipelined Memory Hierarchies

BTL: A Framework for Measuring and Modeling Energy in Memory Hierarchies

Novel nonvolatile memory hierarchies to realize "normally-off mobile processors"

Computational power of pipelined memory hierarchies

Similar Documents

Pipelined memory hierarchies: scalable organizations and application performance

Analysis of power consumption in memory hierarchies

Exploring latency-power tradeoffs in deep nonvolatile memory hierarchies

A DVS-based pipelined reconfigurable instruction memory

Hierarchies of memory limited computations

A low-power content-addressable memory (CAM) using pipelined search scheme

The Speculative Prefetcher and Evaluator Processor for Pipelined Memory Hierarchies

BTL: A Framework for Measuring and Modeling Energy in Memory Hierarchies

Novel nonvolatile memory hierarchies to realize "normally-off mobile processors"

Computational power of pipelined memory hierarchies