[go: up one dir, main page]

Choi et al., 2004 - Google Patents

A general framework for prefetch scheduling in linked data structures and its application to multi-chain prefetching

Choi et al., 2004

View PDF
Document ID
6356803692350203097
Author
Choi S
Kohout N
Pamnani S
Kim D
Yeung D
Publication year
Publication venue
ACM Transactions on Computer Systems (TOCS)

External Links

Snippet

Pointer-chasing applications tend to traverse composite data structures consisting of multiple independent pointer chains. While the traversal of any single pointer chain leads to the serialization of memory operations, the traversal of independent pointer chains provides …
Continue reading at dl.acm.org (PDF) (other versions)

Classifications

    • 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
    • G06F8/443—Optimisation
    • G06F8/4441—Reducing the execution time required by the program code
    • G06F8/4442—Reducing the number of cache misses; Data prefetching
    • 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
    • G06F8/445—Exploiting fine grain parallelism, i.e. parallelism at instruction level
    • 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
    • G06F9/3824—Operand accessing
    • G06F9/383—Operand prefetching
    • 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/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/456—Parallelism detection
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/30—Monitoring
    • G06F11/34—Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation; Recording or statistical evaluation of user activity, e.g. usability assessment
    • G06F11/3409—Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation; Recording or statistical evaluation of user activity, e.g. usability assessment for performance assessment
    • 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/36—Preventing errors by testing or debugging software
    • G06F11/362—Software debugging
    • G06F11/3636—Software debugging by tracing the execution of the program
    • 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
    • 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
    • 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
    • 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
Liao et al. Post-pass binary adaptation for software-based speculative precomputation
Oplinger et al. Software and hardware for exploiting speculative parallelism with a multiprocessor
Luk Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors
US8612949B2 (en) Methods and apparatuses for compiler-creating helper threads for multi-threading
Ottoni et al. Automatic thread extraction with decoupled software pipelining
Kistler et al. Continuous program optimization: A case study
Tian et al. Copy or discard execution model for speculative parallelization on multicores
Oplinger et al. In search of speculative thread-level parallelism
Wang et al. Guided region prefetching: A cooperative hardware/software approach
Yang et al. Push vs. pull: Data movement for linked data structures
EP1668500B1 (en) Methods and apparatuses for thread management of multi-threading
US8037465B2 (en) Thread-data affinity optimization using compiler
González et al. Trace-level reuse
Vera et al. Data caches in multitasking hard real-time systems
Krishnamurthy et al. Analyses and optimizations for shared address space programs
Luk et al. Automatic compiler-inserted prefetching for pointer-based applications
Faraboschi et al. Instruction scheduling for instruction level parallel processors
Cohn et al. Hot cold optimization of large Windows/NT applications
US8886887B2 (en) Uniform external and internal interfaces for delinquent memory operations to facilitate cache optimization
Pai et al. Code transformations to improve memory parallelism
US7243195B2 (en) Software managed cache optimization system and method for multi-processing systems
Choi et al. A general framework for prefetch scheduling in linked data structures and its application to multi-chain prefetching
Kim et al. A study of source-level compiler algorithms for automatic construction of pre-execution code
Kohout et al. Multi-chain prefetching: Effective exploitation of inter-chain memory parallelism for pointer-chasing codes
Barua et al. Cost-driven thread coarsening for GPU kernels