NDLI: Tight competitive ratios for parallel disk prefetching and caching

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

Utilizing shared data in chip multiprocessors with the Nahalal architecture

What can be approximated locally?: case study: dominating sets in planar graphs

Online multicast with egalitarian cost sharing

Against lock-based semantics for transactional memory

Many random walks are faster than one

Automatic data partitioning in software transactional memories

Operational analysis of processor speed scaling

Fundamental parallel algorithms for private-cache chip multiprocessors

Fast distributed scheduling via primal-dual

Kicking the tires of software transactional memory: why the going gets tough

On obstruction-free transactions

Partial snapshot objects

The adaptive transactional memory test platform: a tool for experimenting with transactional code for rock (poster)

A consistency architecture for hierarchical shared caches

Distributed packing in planar graphs

Trade-offs between the size of advice and broadcasting time in trees

A transactional approach to lock scalability

Improved distributed approximate matching

Checkpoints and continuations instead of nested transactions

A temperature-aware virtual submesh allocation scheme for noc-based manycore chips

Cache-efficient dynamic programming algorithms for multicores

A primal-dual resource augmentation analysis of a constant approximate algorithm for stable coalitions in a cluster

RingSTM: scalable transactions with a single atomic instruction

Practical weak-atomicity semantics for java stm

Communication in wireless networks with directional antennas

Improving software concurrency with hardware-assisted memory snapshot

Combinable memory-block transactions

Polylogarithmic network navigability using compact metrics with small stretch

Cost sharing mechanisms for near-optimal traffic aggregation and network design

RaceTM: detecting data races using transactional memory

Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

Adaptive transaction scheduling for transactional memory systems

Optimal speedup on a low-degree multi-core parallel architecture (LoPRAM)

Scheduling strategies for optimistic parallel execution of irregular programs

Improved approximations for multiprocessor scheduling under uncertainty

Irrevocable transactions and their applications

Commit phase in timestamp-based stm

Tight competitive ratios for parallel disk prefetching and caching

Distributed voronoi diagram computation in wireless sensor networks

Parallelizing dynamic information flow tracking

On spreading recommendations via social gossip

A first insight into object-aware hardware transactional memory

Finding strongly connected components in parallel using $O(log^{2}n)$ reachability queries

Energy-optimal distributed algorithms for minimum spanning trees

Competitive non-migratory scheduling for flow time and energy

Dreadlocks: efficient deadlock detection

Directed transmission method, a fully asynchronous approach to solve sparse linear systems in parallel

Safe open-nested transactions through ownership

Data replication in p2p environments

Ased: availability, security, and debugging support usingtransactional memory

Leveraging non-blocking collective communication in high-performance applications

Graphical congestion games with linear latencies

Fractal communication in software data dependency graphs

Tight competitive ratios for parallel disk prefetching and caching

Content Provider	ACM Digital Library
Author	Shah, Rahul Varman, Peter J. Vitter, Jeffrey Scott Hon, Wing-Kai
Abstract	We consider the natural extension of the well-known single disk caching problem to the parallel disk I/O model (PDM) [17]. The main challenge is to achieve as much parallelism as possible and avoid I/O bottlenecks. We are given a fast memory (cache) of size M memory blocks along with a request sequence Σ $=(b_{1},b_{2},.,b_{n})$ where each block $b_{i}$ resides on one of D disks. In each parallel I/O step, at most one block from each disk can be fetched. The task is to serve Σ in the minimum number of parallel I/Os. Thus, each I/O is analogous to a page fault. The difference here is that during each page fault, up to D blocks can be brought into memory, as long as all of the new blocks entering the memory reside on different disks. The problem has a long history [18, 12, 13, 26]. Note that this problem is non-trivial even if all requests in Σ are unique. This restricted version is called read-once. Despite the progress in the offline version [13, 15] and read-once version [12], the general online problem still remained open. Here, we provide comprehensive results with a full general solution for the problem with asymptotically tight competitive ratios. To exploit parallelism, any parallel disk algorithm needs a certain amount of lookahead into future requests. To provide effective caching, an online algorithm must achieve o(D) competitive ratio. We show a lower bound that states, for lookahead L ≤ M, any online algorithm must be Ω(D)-competitive. For lookahead L greater than M(1+1/ε), where ε is a constant, the tight upper bound of O(√MD/L) on competitive ratio is achieved by our algorithm SKEW. The previous algorithm tLRU [26] was $O((MD/L)^{2/3})-competitive$ and this was also shown to be tight [26] for an LRU-based strategy. We achieve the tight ratio using a fairly different strategy than LRU. We also show tight results for randomized algorithms against oblivious adversary and give an algorithm achieving better bounds in the resource augmentation model.
Starting Page	352
Ending Page	361
Page Count	10
File Format	PDF
ISBN	9781595939739
DOI	10.1145/1378533.1378593
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Online algorithms Parallel disk model Competitive analysis
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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