[go: up one dir, main page]

Wolfe, 1988 - Google Patents

Multiprocessor synchronization for concurrent loops

Wolfe, 1988

Document ID
4928732786812253714
Author
Wolfe M
Publication year
Publication venue
IEEE software

External Links

Snippet

Execution of concurrent loops on multiprocessor computers often requires synchronizing the processors. Synchronization schemes are surveyed that are suitable for automatic problem decomposition. The model of a shared-memory multiprocessor is used, as is the concurrent …
Continue reading at ieeexplore.ieee.org (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/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/451—Code distribution
    • G06F8/452—Loops
    • 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
    • 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
    • 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/3885—Concurrent instruction execution, e.g. pipeline, look ahead using a plurality of independent parallel functional units
    • G06F9/3889—Concurrent instruction execution, e.g. pipeline, look ahead using a plurality of independent parallel functional units controlled by multiple instructions, e.g. MIMD, decoupled access or execute
    • 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
    • G06F8/4452—Software pipelining
    • 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/43—Checking; Contextual analysis
    • G06F8/433—Dependency analysis; Data or control flow analysis
    • 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/3836—Instruction issuing, e.g. dynamic instruction scheduling, out of order instruction execution
    • 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/32—Address formation of the next instruction, e.g. incrementing the instruction counter, jump
    • G06F9/322—Address formation of the next instruction, e.g. incrementing the instruction counter, jump for non-sequential address
    • 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/42—Syntactic analysis
    • 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/44—Arrangements for executing specific programmes
    • G06F9/4421—Execution paradigms
    • G06F9/4436—Data-driven
    • 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
    • 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/30003—Arrangements for executing specific machine instructions
    • G06F9/30076—Arrangements for executing specific machine instructions to perform miscellaneous control operations, e.g. NOP
    • G06F9/30087—Synchronisation or serialisation instructions
    • 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/30—Creation or generation of source code
    • G06F8/31—Programming languages or programming paradigms
    • 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/80—Architectures of general purpose stored programme computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication Publication Date Title
Wolfe Multiprocessor synchronization for concurrent loops
Midkiff Automatic parallelization: an overview of fundamental compiler techniques
US5966534A (en) Method for compiling high level programming languages into an integrated processor with reconfigurable logic
Padua et al. Advanced compiler optimizations for supercomputers
Dehnert et al. Overlapped loop support in the Cydra 5
Dehnert et al. Compiling for the Cydra
Ackerman Data flow languages
US5093916A (en) System for inserting constructs into compiled code, defining scoping of common blocks and dynamically binding common blocks to tasks
Moon et al. Parallelizing nonnumerical code with selective scheduling and software pipelining
JPH09282179A (en) Method and device for instruction scheduling in optimized compiler for minimizing overhead instruction
Krishnamurthy et al. Optimizing parallel programs with explicit synchronization
Traub et al. Global analysis for partitioning non-strict programs into sequential threads
Lin Static nonconcurrency analysis of openmp programs
Hendren et al. Designing programming languages for analyzability: a fresh look at pointer data structures.
Gupta et al. High speed synchronization of processors using fuzzy barriers
Pancake Multithreaded languages for scientific and technical computing
Vachharajani Intelligent speculation for pipelined multithreading
Dietz Common Subexpression Induction?
JP3311381B2 (en) Instruction scheduling method in compiler
Midkiff et al. A Comparison of Four Synchronization Optimization Techniques.
Philippsen et al. Automatic synchronisation elimination in synchronous FORALLs
Graham et al. Orchestrating interactions among parallel computations
Keßler et al. Integrating synchronous and asynchronous paradigms: The Fork95 parallel programming language
Gokhale et al. An introduction to compilation issues for parallel machines
Cox et al. Adding parallelism to visual data flow programs