NDLI logo
  • Content
  • Similar Resources
  • Metadata
  • Cite This
  • Log-in
  • Fullscreen
Log-in
Do not have an account? Register Now
Forgot your password? Account recovery
  1. Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '15)
  2. Kinetic Dependence Graphs
Loading...

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

Architectural Support for Cyber-Physical Systems
Mojim: A Reliable and Highly-Available Non-Volatile Memory System
Temporally Bounding TSO for Fence-Free Asymmetric Synchronization
GhostRider: A Hardware-Software System for Memory Trace Oblivious Computation
Supporting Differentiated Services in Computers via Programmable Architecture for Resourcing-on-Demand (PARD)
Protecting Data on Smartphones and Tablets from Memory Attacks
DIABLO: A Warehouse-Scale Computer Network Simulator using FPGAs
Automated OS-level Device Runtime Power Management
Memory Errors in Modern Systems: The Good, The Bad, and The Ugly
rIOMMU: Efficient IOMMU for I/O Devices that Employ Ring Buffers
ApproxHadoop: Bringing Approximations to MapReduce Frameworks
Watson and the Era of Cognitive Computing
Ziria: A DSL for Wireless Systems Programming
Targeted Automatic Integer Overflow Discovery Using Goal-Directed Conditional Branch Enforcement
Asymmetric Memory Fences: Optimizing Both Performance and Implementability
GPU Concurrency: Weak Behaviours and Programming Assumptions
On-the-Fly Principled Speculation for FSM Parallelization
NumaGiC: a Garbage Collector for Big Data on Big NUMA Machines
SD-PCM: Constructing Reliable Super Dense Phase Change Memory under Write Disturbance
Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory
Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM
Improving Agility and Elasticity in Bare-metal Clouds
Nested Kernel: An Operating System Architecture for Intra-Kernel Privilege Separation
Sirius: An Open End-to-End Voice and Vision Personal Assistant and Its Implications for Future Warehouse Scale Computers
CoolAir: Temperature- and Variation-Aware Management for Free-Cooled Datacenters
CommGuard: Mitigating Communication Errors in Error-Prone Parallel Execution
PuDianNao: A Polyvalent Machine Learning Accelerator
Monitoring and Debugging the Quality of Results in Approximate Programs
PolyMage: Automatic Optimization for Image Processing Pipelines
Architectural Support for Software-Defined Metadata Processing
DeNovoSync: Efficient Support for Arbitrary Synchronization without Writer-Initiated Invalidations
Chimera: Collaborative Preemption for Multitasking on a Shared GPU
Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures
FACADE: A Compiler and Runtime for (Almost) Object-Bounded Big Data Applications
DEUCE: Write-Efficient Encryption for Non-Volatile Memories
Synchronization Using Remote-Scope Promotion
Beyond the PDP-11: Architectural Support for a Memory-Safe C Abstract Machine
Few-to-Many: Incremental Parallelism for Reducing Tail Latency in Interactive Services
A Probabilistic Graphical Model-based Approach for Minimizing Energy Under Performance Constraints
Dual Execution for On the Fly Fine Grained Execution Comparison
Compiler Management of Communication and Parallelism for Quantum Computation
A Hardware Design Language for Timing-Sensitive Information-Flow Security
Hybrid Static–Dynamic Analysis for Statically Bounded Region Serializability
Page Placement Strategies for GPUs within Heterogeneous Memory Systems
iThreads: A Threading Library for Parallel Incremental Computation
Architectural Support for Dynamic Linking
More is Less, Less is More: Molecular-Scale Photonic NoC Power Topologies
VARAN the Unbelievable: An Efficient N-version Execution Framework
Kinetic Dependence Graphs
SPECS: A Lightweight Runtime Mechanism for Protecting Software from Security-Critical Processor Bugs

Similar Documents

...
Kinetic Dependence Graphs (CARN, Vol. 43, Issue. 1)

Article

...
Kinetic Dependence Graphs (SIGP, Vol. 50, Issue. 4)

Article

...
Treewidth and Pathwidth of Permutation Graphs

Article

...
On the Complexity of Ordered Colorings

Article

...
On the Power of Graph Searching for Cocomparability Graphs

Article

...
Encoding numbers into reducible permutation graphs using heap-ordered trees

Article

...
Structural recursion for querying ordered graphs

Article

...
Partitioning Planar Graphs

Article

...
Domination on Cocomparability Graphs

Article

Kinetic Dependence Graphs

Content Provider ACM Digital Library
Author Hassaan, Muhammad Amber Nguyen, Donald D. Pingali, Keshav K.
Abstract Task graphs or dependence graphs are used in runtime systems to schedule tasks for parallel execution. In problem domains such as dense linear algebra and signal processing, dependence graphs can be generated from a program by static analysis. However, in emerging problem domains such as graph analytics, the set of tasks and dependences between tasks in a program are complex functions of runtime values and cannot be determined statically. In this paper, we introduce a novel approach for exploiting parallelism in such programs. This approach is based on a data structure called the kinetic dependence graph (KDG), which consists of a dependence graph together with update rules that incrementally update the graph to reflect changes in the dependence structure whenever a task is completed. We have implemented a simple programming model that allows programmers to write these applications at a high level of abstraction, and a runtime within the Galois system [15] that builds the KDG automatically and executes the program in parallel. On a suite of programs that are difficult to parallelize otherwise, we have obtained speedups of up to 33 on 40 cores, out-performing third-party implementations in many cases.
Starting Page 457
Ending Page 471
Page Count 15
File Format PDF
ISBN 9781450328357
DOI 10.1145/2694344.2694363
Language English
Publisher Association for Computing Machinery (ACM)
Publisher Date 2015-03-14
Publisher Place New York
Access Restriction Subscribed
Subject Keyword Kinetic dependence graph Ordered algorithms Stable-source and unstable-source algorithms
Content Type Text
Resource Type Article
  • About
  • Disclaimer
  • Feedback
  • Sponsor
  • Contact
  • Chat with Us
About National Digital Library of India (NDLI)
NDLI logo

National Digital Library of India (NDLI) is a virtual repository of learning resources which is not just a repository with search/browse facilities but provides a host of services for the learner community. It is sponsored and mentored by Ministry of Education, Government of India, through its National Mission on Education through Information and Communication Technology (NMEICT). Filtered and federated searching is employed to facilitate focused searching so that learners can find the right resource with least effort and in minimum time. NDLI provides user group-specific services such as Examination Preparatory for School and College students and job aspirants. Services for Researchers and general learners are also provided. NDLI is designed to hold content of any language and provides interface support for 10 most widely used Indian languages. It is built to provide support for all academic levels including researchers and life-long learners, all disciplines, all popular forms of access devices and differently-abled learners. It is designed to enable people to learn and prepare from best practices from all over the world and to facilitate researchers to perform inter-linked exploration from multiple sources. It is developed, operated and maintained from Indian Institute of Technology Kharagpur.

Learn more about this project from here.

Disclaimer

NDLI is a conglomeration of freely available or institutionally contributed or donated or publisher managed contents. Almost all these contents are hosted and accessed from respective sources. The responsibility for authenticity, relevance, completeness, accuracy, reliability and suitability of these contents rests with the respective organization and NDLI has no responsibility or liability for these. Every effort is made to keep the NDLI portal up and running smoothly unless there are some unavoidable technical issues.

Feedback

Sponsor

Ministry of Education, through its National Mission on Education through Information and Communication Technology (NMEICT), has sponsored and funded the National Digital Library of India (NDLI) project.

Contact National Digital Library of India
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
I will try my best to help you...
Cite this Content
Loading...