[go: up one dir, main page]

Chhugani et al., 2012 - Google Patents

Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency

Chhugani et al., 2012

Document ID
18018151738494140927
Author
Chhugani J
Satish N
Kim C
Sewall J
Dubey P
Publication year
Publication venue
2012 IEEE 26th International Parallel and Distributed Processing Symposium

External Links

Snippet

Graph-based structures are being increasingly used to model data and relations among data in a number of fields. Graph-based databases are becoming more popular as a means to better represent such data. Graph traversal is a key component in graph algorithms such …
Continue reading at ieeexplore.ieee.org (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/505—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the load
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5061—Partitioning or combining of resources
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
    • G06F12/0842—Multiuser, multiprocessor or multiprocessing cache systems for multiprocessing or multitasking
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30386—Retrieval requests
    • G06F17/30424—Query processing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes

Similar Documents

Publication Publication Date Title
Chhugani et al. Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency
Nagasaka et al. High-performance sparse matrix-matrix products on Intel KNL and multicore architectures
Hu et al. Tricore: Parallel triangle counting on gpus
US9471377B2 (en) Systems and methods for parallelizing and optimizing sparse tensor computations
Satish et al. Navigating the maze of graph analytics frameworks using massive graph datasets
Merrill et al. High-performance and scalable GPU graph traversal
Ahmad et al. Crono: A benchmark suite for multithreaded graph algorithms executing on futuristic multicores
Landaverde et al. An investigation of unified memory access performance in cuda
Nagasaka et al. Performance optimization, modeling and analysis of sparse matrix-matrix products on multi-core and many-core processors
Chang et al. A scalable, numerically stable, high-performance tridiagonal solver using GPUs
Deveci et al. Performance-portable sparse matrix-matrix multiplication for many-core architectures
Ueno et al. Parallel distributed breadth first search on GPU
Liu et al. Get out of the valley: Power-efficient address mapping for GPUs
Bisson et al. Parallel distributed breadth first search on the Kepler architecture
Fu et al. Parallel breadth first search on GPU clusters
Iwabuchi et al. Towards a distributed large-scale dynamic graph data store
Dehne et al. Deterministic sample sort for GPUs
Delorme et al. Parallel radix sort on the AMD fusion accelerated processing unit
Hiragushi et al. Efficient hybrid breadth-first search on GPUs
Zhou et al. Ultra efficient acceleration for de novo genome assembly via near-memory computing
Nisa et al. Distributed-memory k-mer counting on GPUs
Kaufmann et al. Parallel Array-Based Single-and Multi-Source Breadth First Searches on Large Dense Graphs.
Chatterjee et al. Counting problems on graphs: GPU storage and parallel computing techniques
Belviranli et al. Designing Algorithms for the EMU Migrating-threads-based Architecture
Vikranth et al. Topology aware task stealing for on-chip NUMA multi-core processors