[go: up one dir, main page]

Chi et al., 2022 - Google Patents

Accelerating SSSP for power-law graphs

Chi et al., 2022

View PDF
Document ID
8487690042837560213
Author
Chi Y
Guo L
Cong J
Publication year
Publication venue
Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

External Links

Snippet

The single-source shortest path (SSSP) problem is one of the most important and well- studied graph problems widely used in many application domains, such as road navigation, neural image reconstruction, and social network analysis. Although we have known various …
Continue reading at dl.acm.org (PDF) (other versions)

Classifications

    • 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
    • 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
    • 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
    • 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/48—Programme initiating; Programme switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • 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
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored programme computers
    • G06F15/78—Architectures of general purpose stored programme computers comprising a single central processing unit
    • 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/30—Arrangements for executing machine-instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline, look ahead
    • 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/50—Computer-aided design
    • 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
    • G06F8/44—Encoding
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F1/00—Details of data-processing equipment not covered by groups G06F3/00 - G06F13/00, e.g. cooling, packaging or power supply specially adapted for computer application
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2201/00—Indexing scheme relating to error detection, to error correction, and to monitoring
    • G06F2201/885—Monitoring specific for caches

Similar Documents

Publication Publication Date Title
Chi et al. Accelerating SSSP for power-law graphs
Rahman et al. Graphpulse: An event-driven hardware accelerator for asynchronous graph processing
Talati et al. Prodigy: Improving the memory latency of data-indirect irregular workloads using hardware-software co-design
Blelloch et al. Provably good multicore cache performance for divide-and-conquer algorithms
Zhang et al. Minnow: Lightweight offload engines for worklist management and worklist-directed prefetching
US8200992B2 (en) Parallel processing computer systems with reduced power consumption and methods for providing the same
Zuckerman et al. Cohmeleon: Learning-based orchestration of accelerator coherence in heterogeneous SoCs
Neele et al. Partial-order reduction for GPU model checking
Tendulkar Mapping and scheduling on multi-core processors using SMT solvers
Manocha et al. Graphattack: Optimizing data supply for graph applications on in-order multicore architectures
Jung et al. Scalable, programmable and dense: The HammerBlade open-source RISC-V manycore
Lebedev et al. Exploring Many‐Core Design Templates for FPGAs and ASICs
Pal et al. OnSRAM: Efficient inter-node on-chip scratchpad management in deep learning accelerators
Shao et al. Processing grid-format real-world graphs on DRAM-based FPGA accelerators with application-specific caching mechanisms
Bandyopadhyay et al. A scratchpad memory allocation scheme for dataflow models
Wang Accelerating graph processing on a shared-memory fpga system
Li et al. The high performance computing applications for bioinformatics research
Xing et al. HPGraph: A high parallel graph processing system based on flash array
Ha et al. D2. 4 report on the final prototype of programming abstractions for energy-efficient inter-process communication
Cérin et al. Where are the optimization potential of machine learning kernels?
Dublish Managing the memory hierarchy in GPUs
Rahman Hardware Acceleration of Irregular Applications Using Event-Driven Execution
Liu et al. Ad-heap: An efficient heap data structure for asymmetric multicore processors
Gunarathne et al. Iterative statistical kernels on contemporary GPUs
Fariborz et al. NOVA: A Novel Vertex Management Architecture for Scalable Graph Processing